分野別セミナー

Solving Diophantine equations is well-known to be a hard problem. We expect that this problem is also hard after quantum computers are built. We proposed a new public key cryptosystem based on the equations which we call the Diophantine equations of degree increasing type. Our cryptosystem is a number field analogue of the Algebraic Surface Cryptosystem (ASC). There are the following two main differences between our cryptosystem and ASC:
1) We twist a plaintext using some modular arithmetic to increase the number of candidates of the plaintext in order to make the correct plaintext hard to find.
2) We use a polynomial of degree increasing type to recover the plaintext uniquely even if the plaintext was twisted.
In this talk, we will first give a brief review of ASC, and then present our cryptosystem. Although we have not been able to give a security proof, we provide some evidences about security of our cryptosystem against the ideal decomposition attack, which can break the one-wayness of ASC.