EP-4646814-B1 - CRYPTOGRAPHIC METHOD FOR DEMONSTRATING A VECTOR IS BINARY

EP4646814B1EP 4646814 B1EP4646814 B1EP 4646814B1EP-4646814-B1

Inventors

LIBERT, Benoît Pascal

Dates

Publication Date: 20260513
Application Date: 20240206

Claims (20)

A computer implemented, cryptographic method (300) for demonstrating by a prover to a verifier that a main vector ( x = ( x 1 , ... , x n )) is a binary vector using a vector commitment scheme, wherein the vector commitment scheme is arranged to compute a proof allowing a partial opening for an element ( x i ) at a position ( i ∈ [ n ]) of a committed vector, - computing (310) by a prover a main commitment ( Ĉ ; C ), the main commitment committing to the main vector ( x ), - obtaining (320) by the prover a randomizing vector ( y = ( y 1 ,... , y n )), the randomizing vector being made available to the verifier, wherein the randomizing vector is chosen by the verifier or derived from the output of a cryptographic hash function, - computing (330) by the prover a first auxiliary commitment ( C y ; Ĉ y ), the first auxiliary commitment committing to, in reverse order as the main vector, an auxiliary vector comprising a Hadamard product of the main vector ( x ) and the randomizing vector ( y ), - generating (340) a first proof ( π y ) demonstrating that a further vector comprising the product of the randomizing vector and the main vector minus 1 in each component ( y i (x i - 1)) is orthogonal to the main vector ( x i ), the first proof being arranged for verification by the verifier - generating (350) a second proof ( π eq ) demonstrating that the main vector in the Hadamard product committed to in the first auxiliary commitment is the main vector committed to in the main commitment.
A method as in Claim 1, wherein - the main commitment ( Ĉ ; C ) is computed by evaluating a commitment function of the vector commitment scheme for the main vector ( x ), and/or - the auxiliary commitment ( Ĉ ; C ) is computed by evaluating a commitment function of the vector commitment scheme for the auxiliary vector, or a linear combination of the auxiliary vector and the randomizing vector, or for the auxiliary vector minus the randomizing vector.
A method as in Claim 1 or 2, the second proof comprising a product of proofs ranging over the elements of the main vector divided by a product of proofs ranging over the elements of the auxiliary vector.
A method as in any of the preceding claims, wherein the main commitment, the auxiliary commitment, the first proof and the second proof each have a size which is independent on the dimension of the main vector.
A method as in any of the preceding claims, wherein the vector commitment scheme is additively homomorphic.
A method as in any of the preceding claims, the verification further comprising obtaining a second auxiliary commitment C y ⋅ ∏ j = 1 n g n + 1 − j − y j from the first auxiliary commitment.
A method as in Claim 6, wherein the second auxiliary commitment is obtained from the first auxiliary commitment and the randomizing vector using an additive homomorphic property of the commitment scheme.
A method as in any of the preceding claims, wherein a bilinear map ( e (,)) is defined from a first group and a second group ( , G ^ ) to a third group ( G T ), a vector commitment being an element in one of the first and second groups ( G ^ ; ), - verification of the first proof comprising a first application of the bilinear map to the first proof and a generator of the second group ( e ( π y , ĝ )).
A method as in Claim 8, wherein verification of the first proof comprises a second application of the bilinear map ( e ( C y , Ĉ )) to the main commitment and the auxiliary commitment, the verification comprises comparing the results of the first and second application in the third group.
A method as in Claim 9, and Claim 6 or 7, wherein verification of the first proof comprises a third application of the bilinear map ( e C y ⋅ ∏ j = 1 n g n + 1 − j − y j , C ^ ) to the main commitment and the second auxiliary commitment, the verification comprises comparing the results of the first and second application in the third group.
A method as in Claim 8, and any of the preceding claims, wherein the second proof ( π eq ) is an element of the first group ( ), the second proof being arranged for verification by a verifier, said verification comprising comparing applications of the bilinear map to the second proof ( e ( π eq , ĝ )), the main commitment ( e ∏ i = 1 n g n + 1 − i t i ⋅ y i , C ^ ), and the auxiliary commitment ( e C y ∏ i = 1 n g ^ i t i ) or a second auxiliary commitment derived from the auxiliary commitment and the randomization vector.
A method as in Claim 11, wherein the applications of the bilinear map are with products of selected group generators, wherein the group generators are selected for the comparison to balance if the main commitment and the first auxiliary commitment both correspond to the same main vector.
A method as in Claim 3, Claim 8 and any of the preceding claims, wherein - the bilinear map applied to a selected group element of the first group and the main commitment ( e ( g n +1- i , Ĉ )) equals in the third group the product of the bilinear map applied to an opening proof for an element at a position and a selected group element of the second group ( e ( π x , i , ĝ )) and the bilinear map applied to a selected group element of the first group and a selected element of the second group, raised to the value of the element at the position ( e ( g 1 , ĝ n ) x i ) and/or - the bilinear map applied to the auxiliary commitment and a selected group element of the second group ( e ( C y , ĝ i )) equals in the third group the product of the bilinear map applied to an opening proof for an element at an position and a selected group element of the second group ( e (ε yx,i , ĝ )) and the bilinear map applied to a selected group element of the first group and a selected element of the second group, raised to the value of the element at the position ( e ( g 1, ĝ n ) y i · x i ).
A method as in any one of the preceding claims, wherein the second proof ( π eq ) is obtained aggregating randomized openings for vector elements.
A method as in any of the preceding claims, comprising - making the commitment and the auxiliary commitment available to the verifier, and making the first proof and/or the second proof or an aggregation thereof available to the verifier.
A method as in any of the preceding claims, wherein the vector commitment scheme comprises a Pedersen commitment scheme.
A method for demonstrating that a number (x) is smaller than a threshold, comprising - obtaining a bit vector comprising a bit representation (( x 1 , ... , x ℓ ) ∈ {0,1} ℓ ) of the number (x) and computing a commitment for the vector, and generating at least the first proof according to any of the preceding claims, - generating a proof demonstrating the equality of the bit representation to the number (x), - demonstrating that the number (x) is smaller than the threshold by opening one or more most significant bits of the bit vector.
A method for demonstrating validity of a ring LWE ciphertext over a ring R = ℤ X / Φ , the ciphertext comprising a first vector s = ( s 1 , ... , s M ) ∈ R M , and a second vector a, satisfying the equation ∑ i = 1 M a i ⋅ s i = t mod q Φ , for t ∈ R q N and a 1 , … , a M ∈ R q N , and R q = R /( qR ) for an integer q, comprising representing vector s as a binary vector, generating at least a first proof as in any of claim 1-16, generating a proof that the vector s satisfies the equation.
A method for demonstrating a vector x is ternary, comprising write x as the difference x = x 0 - x 1 between two binary vectors x 0 , x 1 ∈ {0,1} ℓ and generating at least a first proof as in any of claim 1-16, for the concatenated vector of the two binary vectors.
A method as in any of the preceding claims, wherein the randomizing vector ( y = ( y 1 , ... , y n )) is obtained from a scalar ( u ) chosen by the verifier or derived from the output of a hash function, the randomizing vector being obtained by a series of polynomial functions applied to the scalar, e.g., y = (1, u, u 2 , ... , u n-1 ).

Description

TECHNICAL FIELD The presently disclosed subject matter relates to a cryptographic method for demonstrating by a prover to a verifier that a main vector is a binary vector, a cryptographic method for verifying by a verifier a proof, a system, a computer storage medium, BACKGROUND A commitment scheme commits the sender, e.g., the prover or committer, to a secret message that remains secret until the commitment is opened. In a non-interactive commitment, the commitment and the opening phase may each comprise a single message from the committer to the verifier. A commitment scheme has two properties called hiding and binding. The former means that a commitment string C reveals no information about the committed message. The latter means that no adversary should be able to compute a commitment that can be opened for two distinct messages. An example of a commitment scheme is the Pedersen commitment. In a cyclic group G or prime order p with generators g,h∈G, the sender commits to a message m∈ℤp by choosing r←Rℤp and computing C = gm · hr, for a random r←Rℤp. In the opening phase, the sender reveals m and r. The commitment C perfectly hides m thanks to the uniform randomness r∈ℤp. At the same time, no efficient committer can come up with a commitment C that can be opened in two different ways by revealing distinct pairs (m,r) ≠ (m',r') such that C = gm · hr = gm' · hr' unless it can compute the discrete logarithm logg (h). The Pedersen commitment naturally extends to commit to vectors of messages m1,…,mn∈ℤp. To this end, the committer needs public parameters containing generators g1,…,gn,h∈Gn+1 and computes C=hr⋅∏i=1ngimi. Vector commitments allow a prover to commit to a vector of messages m = (m1, ..., mn) ∈ Dn over some domain D by generating a short commitment string. Later, the committer is able to succinctly reveal individual coordinates of m. Here, succinctly means that the partial opening information, also referred to as a proof, should have constant size, e.g., independent of the dimension of the committed vector, yet still convince the verifier that the opened coordinate is correct. As in standard commitments, a vector commitment scheme preferably satisfies two security properties: (i) The binding property asserts that no efficient adversary can generate a commitment that can be opened to two different values at the same position i ∈ [n]; and (ii) The hiding property which guarantees that revealing a subset of components does not reveal any information about messages at non-revealed positions. Vector commitments enable significant savings in terms of storage, by storing only a constant-size commitment to a vector instead of commitments to individual coordinates, and bandwidth, thanks to the ability to provably and succinctly open individual positions. Other succinct vector commitments may be based on the RSA assumption, or the Diffie-Hellman-like assumption in pairing-friendly groups. Thibauld Feneuil et Al.: "Zero-Knowledge Protocols for the Subset Sum Problem from MPC-in-the-Head with Rejection", IACR, INTERNATIONAL ASSOCIATION FOR CRYPTOLOGIC RESEARCH,vol. 20221123:165319 23 November 2022 (2022-11-23), pages 1-51, discloses a methof for generating a proof that a vector is a binary vector. Izabachène Malika et Al.: "Block-Wise P-Signatures and Non-interactive Anonymous Credentials with Efficient Attributes", 12 December 2011 (2011-12-12), SAT 2015 18TH INTERNATIONAL CONFERENCE, AUSTIN, TX, USA, SEPTEMBER 24-27, 2015; [LECTURE NOTES IN COMPUTER SCIENCE; LECT.NOTES COMPUTER], SPRINGER, BERLIN, HEIDELBERG, PAGE(S) 431 - 450, ISBN: 978-3-540-74549-5, discloses a vector commitment committing to a vector of scalars that allows the committer to can open for an individual position. One limitation of all known vector commitments with short proofs is that there is no efficient way to generate a short proof that the committed vector m is small, e.g., having elements in a given range, e.g., below and/or above a threshold, e.g., binary. One solution to this problem would be to generically use a general-purpose succinct non-interactive argument (SNARK) for all NP languages. While SNARKs could give constant-size proofs, they would require representing the statement as an arithmetic circuits. Then, the arithmetic circuit would have to compute the opening algorithm (and thus compute an exponentiation in a group ) of the commitment scheme, which would result in a complex arithmetic circuit. In turn, this would require a large common reference string (CRS) and make the proof generation very expensive since, in pairing-based SNARKs that give the smallest proof size, the CRS size and the computational cost of the prover both grow at least linearly with the number of multiplication gates in the arithmetic circuit. SUMMARY There is a desire to have an improved method for demonstrating by a prover to a verifier that a main vector is a binary vector. A demonstrating method, verifying method, system and computer-readable medium