The cryptographic schemes used in recent years have a certain degree of security against current com- puter systems. However, it is known that these cryptographic schemes may be deciphered in polynomial time in the near future when quantum computers are realized. To prepare for them, the pq method and its improved pqe method were proposed using the techniques of lattice-based cryptography and multi- variable public-key cryptography (MPKC), which are candidates for quantum computer cryptography. In addition, the linear-pq method and the linear-pqe method, and its ring versions, the ring-pqe method, were proposed to improve the security of MPKC by using linear polynomials instead of quadratic polyno- mials in those methods, in order to enjoy the fast computation and low cost of the lattice and to increase the security of MPKC. In this study, we examine the provable safety of the linear-pqe-method and the ring-pqe-method, of which safety has not been considered.

Top