KR-102962350-B1 - Transparent polynomial commitment scheme and apparatus for performing the same

KR102962350B1KR 102962350 B1KR102962350 B1KR 102962350B1KR-102962350-B1

Abstract

A method for polynomial agreement without reliance assumptions and an apparatus for performing the same are disclosed. A method for performing polynomial agreement, performed by a verification device that performs polynomial agreement with a proof device, comprises the steps of: performing a polynomial-related agreement with the proof device; setting a verification unknown for verifying the agreed polynomial and transmitting the set verification unknown to the proof device; receiving information from the proof device for verifying the proof of the polynomial; performing verification of the proof of the polynomial using the received information; and transmitting the verified verification result to the proof device.

Inventors

김성욱
오현옥
김지혜

Assignees

서울여자대학교 산학협력단
한양대학교 산학협력단
국민대학교산학협력단

Dates

Publication Date: 20260508
Application Date: 20231016

Claims (9)

In a method of polynomial agreement performed by a verification device that performs a polynomial agreement with a proof device, Step of performing the above-mentioned proof device and polynomial-related agreement; A step of setting a verification unknown for verifying the above-mentioned agreed polynomial, and transmitting the set verification unknown to the verification device; A step of receiving information for verifying the proof of the polynomial from the proof device; A step of performing verification of the proof of the polynomial using the received information; and The method includes the step of transmitting the result of verification for the proof of the above polynomial to the proof device; The above proof is, μ group elements generated by repeatedly performing a folding step that sequentially reduces the variable of the above polynomial to a constant, and A polynomial agreement method characterized by decomposing the quotient and remainder of each verification unknown and having a total of μ+1 group elements including one group element generated using the decomposed quotient.
In Article 1, The step of performing the above agreement is, A polynomial agreement method characterized by performing the agreement using a public parameter required for the polynomial agreement received from the above-mentioned proof device and an agreement value of the polynomial to be agreed upon with the said public parameter.
In Paragraph 2, The step of receiving information to verify the above proof is, A polynomial agreement method characterized by receiving information including at least one of the above-mentioned public parameter, above-mentioned agreed value, above-mentioned verification unknown, the calculated result value for the verification unknown calculated by the above-mentioned verification device, and a proof for verifying that the polynomial for the verification unknown is correctly calculated by the above-mentioned verification device.
In Paragraph 3, The step of performing verification for the above proof is, A polynomial agreement method characterized by verifying the above proof to determine whether it is true or false.
In a method of polynomial agreement performed by a verification device and a proof device that performs polynomial agreement, A step of generating public parameters required for the above polynomial agreement; A step of calculating the agreed value of the polynomial using the publicly generated parameters and the polynomial to be agreed upon; A step of performing a verification device and a polynomial-related agreement using the above-determined agreed value; A step of receiving a verification unknown for verifying the agreed polynomial from the verification device; A step of generating a proof to verify that the polynomial for the verification unknown is correctly calculated using the above public parameter, the above agreed value, the above verification unknown, and the above polynomial; The step of transmitting the generated proof to the verification device; and The method includes the step of receiving a verification result for the proof from the verification device; The step of generating the above proof is, μ group elements generated by repeatedly performing a folding step that sequentially reduces the variables of the above polynomial to constants, and A polynomial agreement method characterized by decomposing the quotient and remainder of each verification unknown and generating the proof having a total of μ+1 group elements, including one group element generated using the decomposed quotient.
In Paragraph 5, The step of generating the above-mentioned public parameters is, A polynomial agreement method characterized by generating the public parameter using a cryptographic security parameter (λ), a maximum number of unknowns, and a prime number of length λ.
In Paragraph 5, The step of calculating the above-mentioned agreed value is, A polynomial agreement method characterized by compressing the polynomial into integers to calculate the agreed value for the above verification.
delete
In a verification device that makes a polynomial agreement with a proof device, A verification communication unit communicating with the above-mentioned certification device; and A verification control unit comprising: performing an agreement related to a polynomial with the proof device and the polynomial, setting a verification unknown for verifying the agreed polynomial, transmitting the set verification unknown to the proof device, and, upon receiving information for verifying the proof of the polynomial from the proof device, performing verification of the proof of the polynomial using the received information, and transmitting the result of the verification of the proof of the polynomial to the proof device; The above proof is, μ group elements generated by repeatedly performing a folding step that sequentially reduces the variable of the above polynomial to a constant, and A verification device characterized by decomposing the quotient and remainder of each verification unknown and having a total of μ+1 group elements including one group element generated using the decomposed quotient.

Description

Transparent polynomial commitment scheme and apparatus for performing the same The present invention relates to a polynomial agreement method, and more specifically, to a polynomial agreement method without trust assumptions that supports a transparent polynomial agreement technique with a small proof size, and an apparatus for performing the same. Data plays a crucial role in technologies of the Fourth Industrial Revolution, such as cloud computing, artificial intelligence, big data, distributed authentication, and distributed finance. In particular, the importance of technologies for protecting and processing data containing sensitive information, such as personal information, is increasing. For example, zk-SNARK (Zero-Knowledge Succinct Non-interactive Arguments of Knowledge), a cryptographic application technology, is gaining attention as a solution that can publicly verify the legitimacy of data services while maintaining data privacy. Recently proposed zk-SNARKs are designed using polynomial interactive oracle proof techniques. One of the core cryptographic components of a polynomial interactive oracle proof is the polynomial commitment scheme. Here, the polynomial commitment scheme is a cryptographic technique in which a prover commits a low-order polynomial f(X) and later allows the verifier to verify that f(X) was correctly calculated at X=z, which is arbitrarily chosen by the verifier. The metrics for evaluating the performance of a polynomial commitment scheme largely consist of 1) the proof size indicating that the prover correctly calculated the polynomial f(X) at X=z, and 2) the amount of verification operations required for the verifier to verify the proof. Representative transparent polynomial commitment schemes that achieve O(log d), which can be considered the asymptotic minimum for both proof size and verification operations for a polynomial f(X) of a given order d, include Dory and Dark. Meanwhile, the zk-SNARK desired in actual applications is one that does not require trust assumptions (i.e., transparent zk-SNARK); however, in polynomial interactive oracle proofs, the transparency of the zk-SNARK depends precisely on the transparency of the underlying polynomial agreement technique. For this reason, various studies are being conducted to develop polynomial agreement techniques that provide transparency with good efficiency. FIG. 1 is a configuration diagram for explaining a polynomial agreement system according to an embodiment of the present invention. FIG. 2 is a block diagram for explaining a proof device according to an embodiment of the present invention. FIG. 3 is a block diagram for explaining a verification device according to an embodiment of the present invention. FIG. 4 is a diagram illustrating the PoKRep algorithm used in the polynomial agreement method according to an embodiment of the present invention. FIG. 5 is a diagram illustrating the PC.Setup algorithm, which is one of the polynomial agreement techniques according to an embodiment of the present invention. FIG. 6 is a diagram illustrating the PC.Commit algorithm, which is another polynomial agreement method according to an embodiment of the present invention. FIG. 7 is a diagram illustrating the PC.Open algorithm, which is another polynomial agreement method according to an embodiment of the present invention. FIG. 8 is a diagram illustrating the PC.Ver algorithm, which is another polynomial agreement method according to an embodiment of the present invention. FIG. 9 is a flowchart illustrating a polynomial agreement method according to an embodiment of the present invention. FIG. 10 is a diagram comparing the proof performance of a conventional polynomial agreement method, Dark, and a polynomial agreement method according to an embodiment of the present invention. FIG. 11 is a block diagram illustrating a computing device according to an embodiment of the present invention. Embodiments of the present invention are described below with reference to the attached drawings so that those skilled in the art can easily implement them. However, the present invention may be embodied in various different forms and is not limited to the embodiments described herein. Furthermore, in order to clearly explain the present invention in the drawings, parts unrelated to the explanation have been omitted, and similar parts throughout the specification are denoted by similar reference numerals. In this specification and drawings (hereinafter referred to as the 'this specification'), redundant descriptions of identical components are omitted. Furthermore, when a component is described in this specification as being 'connected' or 'connected' to another component, it should be understood that it may be directly connected to or connected to the other component, or that there may be other components in between. On the other hand, when a component is described in this specification as being 'directly connected' or 'directly connected' to