Construction of IND-CPA Secure Isogeny-based Cryptosystem SiGamal and Unified Coordinate Formulas for Efficient Isogeny Computation
共起 守谷
Public key cryptography is crucial in current Internet technology.In practice, Rivest, Shamir, Adleman (RSA) cryptography based on Prime Factorization Problem, and Elliptic Curve cryptography based on Discrete Logarithm Problem are typically used.However, both these systems are broken in polynomial time using quantum computers.Therefore, new cryptosystems that are secure against adversaries using quantum computers (postquantum cryptography) should be developed.Isogeny-based cryptography exhibits considerable potential for use in post-quantum cryptography.It is based on Isogeny Problem that is a problem finding an isogeny from two elliptic curves.The greatness of isogeny-based cryptography is that the key length is short and hence compact secure communication is realizable.However, isogeny-based cryptography is yet to mature, and some problems remain.Although isogeny-based cryptography is considered one of the notable candidates for post-quantum cryptography, it has several problems due to its short history.In this thesis, we focus on two problems.The first one is the lack of studies on the security of isogenybased cryptosystems.Another one is that isogeny-based cryptosystems are less efficient than other candidates for post-quantum cryptography.Because of the insufficiency of studies about security, an IND-CPA secure isogeny-based public key encryption scheme without using random functions (idealized hash functions) is yet to be obtained.Some schemes have been proposed for isogeny-based public key encryption schemes; however, these schemes are only OW-CPA secure, which is the minimum security for public key encryption.Commutative Supersingular Isogeny Diffie-Hellman (CSIDH) key exchange is an isogeny-based key exchange scheme based on group actions.Because this scheme is similar to Diffie-Hellman key exchange that has many applications, CSIDH is considered a useful scheme.CSIDH plays a crucial role in cryptography that uses group actions, and there are some applications of CSIDH for signatures and high-level cryptosystems.However, a simple public key encryption scheme based on CSIDH does not have IND-CPA security, whereas ElGamal encryption derived from Diffie-Hellman key exchange has IND-CPA security.This is because CSIDH has less mathematical structure than Diffie-Hellman, and a mathematically natural construction of key encryption based on CSIDH is yet to be obtained.In this thesis, we propose a novel public key encryption scheme, namely SiGamal.This scheme is constructed by adding auxiliary points to CSIDH key exchange.These auxiliary points extend a mathematical structure of CSIDH, and SiGamal is compatible with this extended mathematical structure.Therefore, SiGamal is a more natural ElGamal-like key encryption scheme based on CSIDH.Because SiGamal requires auxiliary points, it requires larger data than CSIDH and is less efficient.However, SiGamal has IND-CPA security without using hash functions under a new security assumption, namely the P-CSSDDH assumption.As an application of this scheme, we proposed Naor-Reingold type pseudo random function based on SiGamal.This pseudo random function (PRF) does not require hash functions, and it costs approximately 8T 3π times SiGamal, where T is the Hamming weight of the input of the PRF.Finally, experiments are conducted to verify the efficiency of SiGamal.In our experiments, the computational costs of a group action in SiGamal-512 with a 256-bit plaintext space are approximately 2.62 times that in CSIDH-512.The second problem of isogeny-based cryptography is that isogeny-based cryptosystems are more inefficient than other candidates of post-quantum cryptosystems.The inefficiency of isogeny-based cryptography could be attributed to computations of group ficients . . . . . . . . . . . .
•Mar 23, 2023•0 citations