Additively-homomorphic method and apparatus specialized for non-interactive zero-knowledge proof

Abstract

Disclosed are homomorphic encryption method and apparatus specialized for zero-knowledge proof. The homomorphic encryption method specialized for zero-knowledge proof includes (a) dividing a message M into n message blocks; (b) generating a ciphertext CT by encrypting the n message blocks, wherein the ciphertext CT includes each encryption block for each of the n message blocks, and each encryption block includes the message block in the form G.sub.i.sup.m.sup.i of an exponentiation of a generator G; and (c) generating a zero-knowledge proof key π for the n message blocks by applying the n message blocks as inputs to a preset zero-knowledge proof algorithm.

Claims

1. A homomorphic encryption method specialized for zero-knowledge proof, comprising: (a) dividing a message M into n message blocks; (b) generating a ciphertext CT by encrypting the n message blocks, wherein the ciphertext CT includes each encryption block for each of the n message blocks, and the each encryption block includes the each message block in the form G.sub.i.sup.m.sup.i of an exponentiation of a generator G; (c) generating a common reference string (CRS) using a relation R; (d) generating a zero-knowledge proof key π for the n message blocks by applying the n message blocks as inputs to a preset zero-knowledge proof algorithm; (e) acquiring the n message blocks by decrypting the ciphertext CT using the CRS, a secret key, and a verification key; and (f) restoring the message M by combining the n message blocks, wherein i represents an index of the each message block.

2. The homomorphic encryption method specialized for zero-knowledge proof of claim 1, further comprising: wherein the relation R includes the n message blocks as input/output statements, and the CRS includes , wherein G.sup.−γ, represents the generator and r represents a random value.

3. The homomorphic encryption method specialized for zero-knowledge proof of claim 1, wherein each of the encryption blocks further includes a blind factor X.sup.r.

4. The homomorphic encryption method specialized for zero-knowledge proof of claim 1, further comprising: verifying the zero-knowledge proof key π by using the CRS, the ciphertext CT, and a part of the relation R.

5. The homomorphic encryption method specialized for zero-knowledge proof of claim 1, further comprising: before step (c), rerandomizing the ciphertext CT and the zero-knowledge proof key π using a public key.

6. A recording media product as a non-transitory computer-readable recording medium product for recording program codes for performing a homomorphic encryption method specialized for zero-knowledge proof, comprising: (a) dividing a message M into n message blocks; (b) generating a ciphertext CT by encrypting the n message blocks, wherein the ciphertext CT includes each encryption block for each of the n message blocks, and the each encryption block includes the each message block in the form G.sub.i.sup.m.sup.i of an exponentiation of a generator G; (c) generating a common reference string (CRS) using a relation R; (e) generating a zero-knowledge proof key π for the n message blocks by applying the n message blocks as inputs to a preset zero-knowledge proof algorithm; (e) acquiring the n message blocks by decrypting the ciphertext CT using the CRS, a secret key, and a verification key; and (f) restoring the message M by combining the n message blocks, wherein i represents an index of the each message block.

7. A computing device comprising: a division processor configured to divide a message M into n message blocks; an encryption processor configured to generate a ciphertext CT by encrypting the n message blocks and generate a zero-knowledge proof key π for the n message blocks by applying the n message blocks as inputs to a preset zero-knowledge proof algorithm, wherein the ciphertext CT includes each encryption block for each of the n message blocks, and the each encryption block includes the each message block in the form G.sub.i.sup.m.sup.i of an exponentiation of a generator G; an initial setting processor configured to generate a common reference string (CRS) using a relation R; a decryption processor configured to acquire the n message blocks by decrypting the ciphertext CT using the CRS, a secret key, and a verification key and restore the message M by combining the n message blocks, wherein i represents an index of the each message block.

8. The computing device of claim 7, further comprising: wherein the relation R includes the n message blocks as input/output statements, and the CRS includes G.sup.−γ, wherein G represents thea generator and r represents a random value.

9. The computing device of claim 7, wherein each of the encryption blocks furtheer includes a blind factor X.sup.r.

10. The computing device of claim 7, further comprising: a verification unit configured to verify the zero-knowledge proof key π by using the CRS, the ciphertext CT, and a part of the relation R.

11. The computing device of claim 7, further comprising: a rerandomization unit configured to rerandomize the ciphertext CT and the zero-knowledge proof π using a public key.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flowchart illustrating a homomorphic encryption method specialized for non-interactive zero-knowledge proof according to an embodiment of the present invention.

(2) FIG. 2 is a diagram illustrating pseudo codes of a zero-knowledge proof algorithm to which an in-circuit encryption method is applied.

(3) FIG. 3 is a diagram illustrating pseudo codes of a homomorphic encryption method specialized for zero-knowledge proof according to an embodiment of the present invention.

(4) FIG. 4 is a block diagram schematically illustrating an internal configuration of a computing device according to an embodiment of the present invention.

DETAILED DESCRIPTION

(5) A singular form used in the present specification may include a plural form if there is no clearly opposite meaning in the context. In this specification, terms such as “comprising” or “including” should not be interpreted as necessarily including all various components or various steps disclosed in the specification, and it should be interpreted that some component or some steps among them may not be included or additional components or steps may be further included. In addition, terms including “unit’, “module”, and the like disclosed in the specification mean a unit that processes at least one function or operation and this may be implemented by hardware or software or a combination of hardware and software.

(6) Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.

(7) Unlike a conventional method in which encryption is added to zero-knowledge proof, in a homomorphic encryption method specialized for zero-knowledge proof according to an embodiment of the present invention, an encryption method may not be included in a circuit input of zero-knowledge proof by a method of linking the encryption and the zero-knowledge proof for a message.

(8) Through this, the present invention has an advantage of enabling homomorphic encryption and zero-knowledge proof for a message, and enabling zero-knowledge proof for a message without exposing a secret key and the like to the outside.

(9) As such, in order to enable the linkage of the homomorphic encryption of the message and the zero-knowledge proof thereof, in an embodiment of the present invention, a relation set R will be defined as follows.

(10) Relation Set R (Relations)

(11) A security parameter is denoted by 1.sup.λ. When the security parameter 1.sup.λ is given, a relation generator returns a polynomial time-determinable relation ←(1.sup.λ). In (Φ,ω)∈, ω is a witness to an input/output (I/O) statement Φ that belongs to a relation. Φ consists of M={m.sub.1, . . . , m.sub.n} and Φ=M∪{circumflex over (Φ)} for any {circumflex over (Φ)}={ϕ.sub.n+1, . . . , ϕ.sub.l}. Here, l represents the number of I/O statements.

(12) In addition, even if there is no separate description below, it should be understood that a generator according to an embodiment of the present invention generates a bilinear group. This will be described in brief.

(13) A bilinear group generator takes a secret parameter as an unary input and returns a nonlinear group (p, .sub.1, .sub.2, .sub.T, e, aux). Here, the nonlinear group consists of a cyclic group .sub.1, .sub.2, .sub.T of a basic order p and a bilinear map e:.sub.1×.sub.2.fwdarw..sub.T. e:.sub.1×.sub.2.fwdarw..sub.T may include auxiliary information aux.

(14) An efficient algorithm exists for calculating a group task, evaluating a bilinear map, determining a group membership, and a sampling generator for a group generator.

(15) The map is bilinear for all G∈.sub.1 and H∈.sub.2. The following equation may be acquired for a, b ∈.
e(G.sup.a,H.sup.b)=e(G,H).sup.ab

(16) Also, the map is non-degenerate. For example, if e(G,H)=1, G=1 or H=1.

(17) Usually, the bilinear group consists of an elliptic curve with pairs and may be adjusted to generate a non-degenerate nonlinear map. There are many methods to configure the nonlinear groups. For example, there are a symmetric nonlinear group such as .sub.1=.sub.2, an asymmetric nonlinear group such as .sub.1≠.sub.2, and the like.

(18) In an embodiment of the present invention, it is assumed that the nonlinear group is configured as an asymmetric group (type III) without non-trivial homogeneity that may be efficiently calculated in any direction between .sub.1 and .sub.2, and it will be mainly described.

(19) A type III bilinear group is the most efficient type of bilinear group, and is most suitable to be applied to a practical application.

(20) As described above, in an embodiment of the present invention, a homomorphic encryption method for a message M is not used as a circuit input for zero-knowledge proof, and may be provided to have connectivity between the encryption method and an attribute proof.

(21) This will be more clearly understood by the following description. In the following description, since the zero-knowledge proof method itself is a known matter, a detailed description of the zero-knowledge proof method will not be separately described, and only technical matters required for the description of the main subject matter of the present invention will be described.

(22) FIG. 1 is a flowchart illustrating a homomorphic encryption method specialized for non-interactive zero-knowledge proof according to an embodiment of the present invention, FIG. 2 is a diagram illustrating pseudo codes of a zero-knowledge proof algorithm to which an in-circuit encryption method is applied, and FIG. 3 is a diagram illustrating pseudo codes of a homomorphic encryption method specialized for zero-knowledge proof according to an embodiment of the present invention.

(23) In step 110, a computing device 100 divides a message M into n message blocks.

(24) The message M is divided into n blocks to have a vector form such as M={m.sub.1, . . . , m.sub.n}. That is, M={m.sub.1, . . . , m.sub.n}.

(25) In step 110, the computing device 100 generates a ciphertext CT by encrypting the n message blocks. It is natural that an initial setting process may precede the step of generating the ciphertext CT. For example, as illustrated in FIG. 3, the computing device 100 may acquire a relation R, and generate a common reference string (CRS) using the relation R, and generate a public key, a secret key, and a verification key based on the generated CRS.

(26) The ciphertext CT consists of n+2 blocks. For example, ={c.sub.0, . . . , c.sub.n, ψ}. Here, c.sub.0 includes a random value, ψ includes encryption proof, and the remaining c.sub.i includes encryption of each message block m.sub.i. Here, 1≤i≤n.

(27) In this case, the computing device 100 may generate a ciphertext CT form to have a form similar to a proof key (zero-knowledge proof key) used for verification of the zero-knowledge proof when encrypting the n message blocks.

(28) To this end, the computing device 100 according to an embodiment of the present invention may generate the ciphertext CT so as to include each of the n message blocks as an exponentiation of a generator G. As such, by making each of the n message blocks in the form of an exponentiation of the generator G, there are advantages of not only having connectivity with the attribute proof of the zero-knowledge proof, but also blinding each message block so as to make it impossible to decrypt each message block even if each message block is exposed.

(29) In addition, the computing device 100 may be plugged into an additional isomorphic encryption based on ELGamal encryption so that each encryption block for the n message blocks satisfies an additively homomorphic encryption attribute.

(30) Accordingly, according to an embodiment of the present invention, instead of encrypting each of the n message blocks, each of the n message blocks may be generated in the form of an exponentiation of the generator G and then encrypted.

(31) In addition, encryption blocks for the n message blocks according to an embodiment of the present invention may be generated to include a blind factor in addition to generating each message block in the form of the exponentiation of the generator G. This will be more clearly understood by the following description.

(32) In order to facilitate understanding and convenience of explanation, a zero-knowledge proof algorithm to which an in-circuit encryption method is applied will be briefly described with reference to FIG. 2.

(33) In the zk-SNARK, three separate relations for relation.sub.enc, relation.sub.rerand and relation.sub.dec are required to satisfy a desired attribute of the zero-knowledge proof.

(34) In relation.sub.enc, a rerandomizable homomorphic encryption Π.sub.RR,AH such as Paillier is combined with an arbitrary relation to satisfy verifiable additively homomorphic encryption.

(35) In relation.sub.rerand for a possibility of rerandomization, the relation includes verification of a proof key π to check the relation of the ciphertext CT.

(36) For example, in a voting application, an administrator needs to first verify a vote before rerandomizing the vote to check whether the vote has been honestly generated from a legitimate user.

(37) In relation.sub.dec, a decryption algorithm should be included to provide a verifiable decryption attribute. When the encryption is verifiably performed by including the above-described relation, encryption construction is very inefficient.

(38) An ENC function needs to include Π.sub.snark.Prove(relation.sub.enc), a Rerandomize function needs to include Π.sub.snark.Prove(relation.sub.rerand), and a DEC function needs to include Π.sub.snark.Prove(relation.sub.dec).

(39) In other words, the process needs to be performed to include the attribute proof in each of the ENC, Rerandomize, and DEC processes that are essentially performed during encryption. This is very inefficient.

(40) Accordingly, in order to avoid this inefficient problem, in an embodiment of the present invention, the encryption is separated from the relation of zk-SNARK, and connectivity between hash & proof FFG.sup.+16.sup.− or commit & proof CFQ19 may be provided.

(41) Like FFG.sup.+16.sup.−, combining the zk-SNARK with encryption through commitments may require additional verification of the linkage. Instead of verifying each linkage, in an embodiment of the present invention, the ciphertext may be mixed with the original zk-SNARK verification by substituting an input/output state.

(42) In Gro16, zk-SNARK verification may be expressed as in Equation 1.

(43) $\begin{array}{cc}e\left(A,B\right)=e\left(G^{\alpha },H^{\beta }\right).Math.e\left(\underset{i=0}{\overset{l}{.Math.}}{G}_i^{{\varphi }_i},H^{\gamma }\right).Math.e\left(C,H^{\delta }\right)& \left[\mathrm{Equation}1\right]\end{array}$

(44) (ϕ.sub.1, . . . , ϕ.sub.l) may be a plaintext as well as any statement. It is assumed that ϕ.sub.1 has been encrypted. It will be referred to as a plaintext message M=ϕ.sub.1. At this time, according to an embodiment of the present invention, a ciphertext CT=G.sub.1.sup.M may be configured similar to ELGamal encryption that maintains an original verification format.

(45) This may be expressed as Equation 2.

(46) $\begin{array}{cc}e\left(A,B\right)=e\left(G^{\alpha },H^{\beta }\right).Math.e\left(\mathrm{𝒞𝒯}.Math.\underset{i=2}{\overset{l}{.Math.}}{G}_i^{{\varphi }_i},H^{\gamma }\right).Math.e\left(C,H^{\delta }\right)& \left[\mathrm{Equation}2\right]\end{array}$

(47) It is obvious that the CT should include an additional blind factor in G.sub.1.sup.M. Assuming that the blind factor is X.sup.r, it becomes CT=X.sup.r.Math.G.sub.1.sup.M, and e(X.sup.r.Math.G.sub.1.sup.M.Math.Π.sub.i=2.sup.lG.sub.i.sup.ϕ.sup.l,H.sup.γ) pairing generates an unintended term γ.sup.r that breaks an inequality of Equation 2 in e(X.sup.r,H.sup.γ).

(48) In order to solve this problem, in an embodiment of the present invention, G.sup.−γ may be included in a common reference string (CRS). A prover can modify a proof factor C to C=C.Math.G.sup.−γr so that the term γ.sup.r may be removed from e(C,H.sup.δ) with respect to δ. As a result, the verification of zk-SNARK may ensure the integrity of M within the relation with existence of M in the ciphertext.

(49) According to an embodiment of the present invention, the G.sub.i.sup.M form may be plugged into an additively homomorphic cipher based on ELGamal encryption. It is easy to modify the ELGamal encryption by encrypting G.sub.i.sup.M instead of M to achieve the additively homomorphic cipher such as G.sub.i.sup.M.sup.1.Math.G.sub.i.sup.M.sup.2=G.sub.i.sup.M.sup.1.sup.+M.sup.2. In this case, since the decryption needs to find a short discrete log of G.sub.i.sup.M, the messages are limited to be short.

(50) Accordingly, in an embodiment of the present invention, the message M is divided into n message blocks such as M=(m.sub.1∥ . . . ∥m.sub.n) (e.g. |m.sub.i|=4 bits), and each message block m.sub.i is encrypted in the form of X.sub.i.sup.r.Math.G.sub.i.sup.m.sup.i. Here, X.sub.i.sup.r is the blind factor.

(51) A decrypter capable of removing the blind factor may acquire a message block m.sub.i by a simple brute-forcing technique.

(52) Pseudo codes for the homomorphic encryption method specialized for zero-knowledge proof according to an embodiment of the present invention is as illustrated in FIG. 3. This will be described in brief.

(53) The relation function represents an arbitrary relation R for zk-SNARK. In addition, α, β, γ, and δ in the function are derived from a common reference string (CRS) of the adopted zk-SNARK.

(54) SAVER receives an arbitrary relation consisting of two I/O states. Here, m.sub.1, . . . , m.sub.n is encrypted, and ϕ.sub.n+1, . . . , ϕ.sub.1 may be used as a normal I/O state in the plaintext.

(55) For the given relation, a setup function generates a CRS using the adopted zk-SNARK. Here, the CRS may be generated to include G.sup.−γ.

(56) A KeyGen function generates a private key, a public key, and a verification key, respectively.

(57) An Enc function encrypts n message blocks and generates a zero-knowledge proof key π for the n message blocks. At this time, the zero-knowledge proof key π may be the proof of Φ=(m.sub.1, . . . , m.sub.n, ϕ.sub.n+1, . . . , ϕ.sub.l).

(58) Verify_Enc may take the ciphertext CT and the zero-knowledge proof key π as inputs for verification in order to check the zero-knowledge proof key π.

(59) A Rerandomize function rerandomizes the given ciphertext and proof.

(60) Dec may decrypt a ciphertext. In other words, Dec may decrypt each decrypted block c.sub.1, . . . , c.sub.n and output m.sub.1, . . . , m.sub.n and a decryption proof v:

(61) An original message M may be restored like M=(m.sub.1∥ . . . ∥m.sub.n).

(62) A Verify_Dec function verifies whether the ciphertext CT is properly decrypted. Verify_Dec may verify whether the ciphertext CT is legitimately decrypted using the message M and the decryption proof v.

(63) In SAVER, the ciphertext CT satisfies an additively homomorphic encryption attribute. For example, it is assumed that =(X.sub.0.sup.r,{X.sub.i.sup.rG.sub.i.sup.m.sup.i}.sub.i=1.sup.n,P.sub.1.sup.rΠ.sub.j=1.sup.nY.sub.j.sup.m.sup.j) and .sup.l=(X.sub.0.sup.r′,{X.sub.i.sup.r′G.sub.i.sup.m′.sup.i}.sub.i=1.sup.n,P.sub.1.sup.r′Π.sub.j=1.sup.nY.sub.j.sup.m′.sup.j) have been given.

(64) Since .sup.l=(X.sub.0.sup.r+r′,{X.sub.i.sup.r+r′G.sub.i.sup.m.sup.i.sup.+m′.sup.i}.sub.i=1.sup.n, P.sub.1.sup.r+r′Π.sub.j=1.sup.nY.sub.j.sup.m.sup.j.sup.+m′.sup.j), it can be seen that the additively homomorphic encryption attribute is satisfied.

(65) In step 120, the computing device 100 generates a zero-knowledge proof key π by applying n message blocks to a preset zero-knowledge proof algorithm as inputs.

(66) In step 125, the computing device 100 rerandomizes the ciphertext CT and the zero-knowledge proof key π using a public key PK.

(67) Thereafter, in step 130, the computing device 100 verifies the zero-knowledge proof key by using the CRS, the ciphertext CT, the zero-knowledge proof key π, and ϕ.sub.n+1, . . . , ϕ.sub.l.

(68) In step 135, the computing device 100 decrypts the ciphertext CT using the CRS, a secret key, and a verification key to acquire a plurality of message blocks, and restores the message M by combining the message blocks. Step 135 may also be performed on another computing device.

(69) Thereafter, the computing device 100 verifies whether the ciphertext CT has been legitimately decrypted. For example, the computing device 100 may verify whether the ciphertext CT is legitimately decrypted using the message M and the decryption proof v.

(70) FIG. 4 is a block diagram schematically illustrating an internal configuration of a computing device according to an embodiment of the present invention.

(71) Referring to FIG. 4, the computing device 100 according to an embodiment of the present invention is configured to include an initial setting unit 410, a key generation unit 415, a division unit 420, an encryption unit 425, a rerandomization unit 430, a verification unit 435, a decryption unit 440, a decryption verification unit 445, a memory 450, and a processor 455.

(72) The initial setting unit 410 is a means for generating a common reference string (CRS) using a relation R. As already described above, the CRS may include a random value as an exponentiation of a generator G for zero-knowledge proof verification for a ciphertext CT.

(73) The key generation unit 415 is a means for generating a secret key, a public key, and a verification key by using the CRS generated by the initial setting unit 410.

(74) The division unit 420 is a means for dividing the message M into n message blocks.

(75) The encryption unit 425 is a means that encrypts the n message blocks to generate a ciphertext CT, and applies the n message blocks as an input to a preset zero-knowledge proof algorithm to generate a zero-knowledge proof key π for the n message blocks.

(76) The pseudo codes for this are as illustrated in FIG. 3.

(77) The rerandomization unit 430 is a means for rerandomizing the ciphertext CT and the zero-knowledge proof π key using a public key.

(78) The verification unit 435 is a means for verifying the zero-knowledge proof key π by using the CRS, the ciphertext CT, the zero-knowledge proof key π, and a part of the relation R.

(79) The decryption unit 440 is a means for decrypting the ciphertext CT using the CRS, a secret key, and a verification key to acquire a plurality of message blocks, and restoring the message M by combining the message blocks.

(80) The decryption verification unit 445 is a means for verifying whether the ciphertext CT is legitimately decrypted using the message M and the decryption verification key.

(81) The memory 450 is a means for storing instructions (program codes) required for performing the homomorphic encryption method specialized for zero-knowledge proof according to an embodiment of the present invention.

(82) The processor 455 is a means for controlling internal components of the computing device 100 according to an embodiment of the present invention (e.g., the initial setting unit 410, the key generation unit 415, the division unit 420, the encryption unit 425, the rerandomization unit 430, the verification unit 435, the decryption unit 440, the decryption verification unit 445, the memory 450, and the like).

(83) Besides, it is natural that the computing device according to an embodiment of the present invention may further include a communication unit. That is, the computing device may receive information on the relation R from the outside through the communication unit.

(84) Hereinabove, the present invention has been described with reference to the embodiments thereof. It is understood to those skilled in the art that the present invention may be implemented as a modified form without departing from an essential characteristic of the present invention. Therefore, the disclosed embodiments should be considered in an illustrative viewpoint rather than a restrictive viewpoint. The scope of the present invention is defined by the appended claims rather than by the foregoing description, and all differences within the scope of equivalents thereof should be construed as being included in the present invention.