国際会議MQC2019で2件の発表を行いました

Sep 25, 2019 1 min read 暗号

九州大で開催された国際会議MQC2019（2019年9月25日-27日）で研究室から2件の発表を行いました．

タイトル：Quantum Factoring Algorithm: Resource Estimation and Survey of Experiments
著者：Noboru Kunihiro
スライド
概要：It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption if large-scale quantum computers are realized. So far, several factorization experiments of the small composite such as 15 and 21 have been conducted by small-scale quantum computers. We investigate the details of quantum circuits used in the experiments for factoring. We then point out that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is a priori known. Since the order must be unknown between the experiment, it is inappropriate as the quantum circuit for Shor’s factoring algorithm. We also point out that the circuits in the other experiments are constructed heavily relying on the composite number to be factorized.

タイトル：Ramanujan graphs for post-quantum cryptography
著者：Hyungrok Jo, Shingo Sugiyama, Yoshinori Yamasaki
スライド
概要：We introduce a cryptographic hash function based on expander graphs, suggested by Charles et al. ‘09, as one of prominent candidates in post-quantum cryptography. We propose a generalized version of explicit constructions of Ramanujan graphs, which are seen as an optimal structure of expander graphs in a view of spectral sense, from the previous works of Lubotzky, Phillips, Sarnak ‘88 and Chiu ‘92. We also describe the relationship between the security of Cayley hash functions and word problems for group theory. We also give a brief comparison of the present works and Pizer’s graphs as a matter of the underlying hard problems in cryptography.