Lattice-based public key cryptosystem and electronic device included in the same

A key generation device of a lattice-based public key cryptosystem, the key generation device comprising:

• a communication circuit configured to send and receive data;
• a memory;
• and
• a processor coupled to the communication circuit and the memory, and configured to control the key generation device to perform a plurality of operations by loading instructions stored in the memory,
• wherein the plurality of operations include:
• obtaining a public key seed and a secret key seed;
• generating a public key polynomial belonging to a first polynomial ring that is a quotient ring by a polynomial φ(X), by determining a degree and coefficients of the public key polynomial according to the public key seed;
• generating a public key based on the public key polynomial;
• generating a secret key polynomial belong to a second polynomial ring that is a quotient ring by the polynomial φ(X), by determining a degree and coefficients of the secret key polynomial from the secret key seed;
• and
• generating a secret key based on the secret key polynomial;
• storing the public key and the secret key,
• wherein the polynomial φ(X) is defined as Xp−X−1 (p is a prime number) or
• X
• n
• -
• X
• n
• 2
• +
• 1
• (n=2a3b (a and b are positive integers)) such that the public key and the secret key are secure against attacks based on decomposition of the polynomial φ(X).