KR-20260062364-A - APPARATUS AND METHOD FOR OPTIMIZING ISOGENY-BASED HASH FUNCTION

Abstract

The present invention relates to an apparatus and method for optimizing an isogeny-based hash function, and more specifically, in a GCL hash function of isogeny-based encryption, the invention is characterized by enhancing security against collision attacks of a hash function by adding a checksum to a message and aiming to find a random message corresponding to an isogeny that induces the same image curve. According to the isogeny-based hash function optimization device and method proposed in the present invention, by utilizing a checksum to perform hash operations, security can be enhanced because, unlike previous CGL hash functions, it is not sufficient for an attack to simply find a hash input that induces a collision, but instead, for the attack to succeed, a message of a specific form must be found. In addition, according to the isogeny-based hash function optimization apparatus and method proposed in the present invention, since it can be implemented in a finite field using λ-bit primes for a λ-bit security level, although additional rounds centered on the isogeny graph are required, the computational cost of isogeny and finite field operations is reduced compared to existing CGL hash functions that require 2λ-bit primes for the same security level, thereby obtaining more efficient performance.

Inventors

• 윤기순
• 이영도
• 김수리

Assignees

• 주식회사 엔에스에이치씨

Dates

Publication Date

20260507

Application Date

20241029

Claims (7)

1. An isogeny-based hash function optimization method characterized by enhancing security against collision attacks of a hash function, which aims to find a random message corresponding to an isogeny that induces the same image curve by adding a checksum to a message in a GCL hash function of isogeny-based encryption.
2. In paragraph 1, An isogeny-based hash function optimization method characterized by traversing an isogeny graph using the above message and then traversing the isogeny graph one more time using the above checksum.
3. In paragraph 2, An isogeny-based hash function optimization method characterized by using the result of XORing the above message as the above checksum.
4. In paragraph 2, An isogeny-based hash function optimization method characterized by parsing the above message into n-bit message blocks, traversing the isogeny graph using the parsed message blocks and a start curve to obtain a result curve, and then traversing the isogeny graph once more using the result curve as a start curve and the checksum to obtain a final result curve.
5. In paragraph 4, An isogeny-based hash function optimization method characterized by using invariants of the above-mentioned final result curve as the hash output.
6. A computer program stored on a computer-readable recording medium for executing the isogeny-based hash function optimization method of any one of claims 1 to 5 on a computer.
7. An isogeny-based hash function optimizer characterized by enhancing security against collision attacks of a hash function, which aims to find a random message corresponding to an isogeny that induces the same image curve by adding a checksum to a message in a GCL hash function of isogeny-based encryption.

Description

Apparatus and Method for Optimizing Isogeny-Based Hash Function The present invention relates to a hash function optimization apparatus and method, and more specifically, to an isogeny-based hash function optimization apparatus and method. The content described in this section merely provides background information regarding an embodiment of the present invention and does not constitute prior art. Elliptic curve isogeny was first introduced to cryptography in a 1997 lecture by Couveignes [Non-patent Document 0001]. Subsequently, in [Non-patent Document 0002], isogeny was used in cryptography as a method to instantiate provable hash functions in expander graphs; the idea proposed in the 1997 lecture was developed into a key exchange method by Rostovtsew and Stolbunov and is currently known as the CRS system. Meanwhile, CRS did not receive much attention at the time due to the quantum sub-exponential attack proposed by Charles et al. in [Non-patent Document 0002], which exploits the commutability of the endomorphism ring of general elliptic curves. Furthermore, cryptographic systems utilizing isogeny itself did not receive significant attention due to their slow speed. Isogeny-based encryption began to receive significant attention following the introduction of the Supersingular Isogeny Diffie-Hellman (SIDH) proposed by Jao and De Feo in [Non-Patent Literature 0003]. SIDH can counter the attack described in [Non-Patent Literature 0002] because its self-mapping ring uses non-commutative supersingular elliptic curves. In fact, SIDH was considered to have quantum exponential complexity. Meanwhile, if Shor's algorithm is implemented on a sufficiently large scale on a quantum computer, the security foundation of currently used public-key algorithms such as RSA, DSA, and ECC could be compromised. As the advancement of quantum computing becomes increasingly visible in recent years, research on post-quantum cryptography (PQC)—cryptographic algorithms that are secure in a quantum computing environment but implemented on classical computers—is actively underway. Therefore, the quantum resistance of SIDH was considered a significant advantage, and efficient key size and speed were achieved through the optimization technique of [Non-patent Literature 0004]. The SIDH-based key encapsulation method SIKE was selected as a replacement candidate in NIST PQC Round 4. For 10 years since its proposal, no attack method more efficient than the Meet-in-the-Middle (MitM) attack against SIDH-based encryption has been proposed [Non-patent Literature 0005]. Research has shown that attacks using classical computers can be more efficient than attacks using quantum computers, establishing it as a strong candidate for the NIST PQC standardization project. However, in 2023, a key recovery attack proposed by Castryck and Decru based on Kani's theorem rendered SIDH-based encryption unusable by enabling the analysis of private keys in polynomial time at all security levels [Non-patent Literature 0006]. On the other hand, the attack by Castryck and Decru does not solve the isogeny problem itself, which is related to the difficulty of finding isogenies between two supersingular elliptic curves defined in a finite field. Instead, it breaks SIDH-based cryptographic schemes specifically designed for encryption use. Therefore, cryptographic schemes such as CSIDH [Non-patent Literature 0007], which utilizes ultra-singular curves to optimize the CRS scheme, can maintain security. SQISign, a candidate for the NIST PQC digital signature standardization project, is also safe from this attack because it uses a different fundamental problem than SIDH. In fact, a new computational method for SQISign was proposed using Kani's theorem applied to the Castryck-Decru attack, which improved performance [Non-patent Literature 0008]–[Non-patent Literature 0010]. Additionally, provable hash functions designed using the isogeny problem are safe from the Castryck-Decru attack. A provable hash function is a hash function that can reduce collision detection to solve well-known computationally difficult problems. [Non-patent document 0002] proposes a provable hash function utilizing an expander graph. The hash function takes an input and uses it as a direction to walk around the graph, with the final vertex serving as the function's output. The proposed hash function can be applied to any expander graph. One well-known instantiation uses the ℓ-isogeny graph of a supersingular elliptic curve, and Pizer proved that this graph possesses the Ramanujan property, a special type of expander graph. Instantiating such a hash function using an isogeny graph is known today as a CGL hash function. In a CGL hash function, collision detection means This means finding two different isogenies, ψ and φ, connecting two supersingular elliptic curves E and E1 defined in . This problem can be considered collision-resistant because it exhibits exponential complexity in both classical and quan