Method for performing a disjunctive proof for two relations

1. A method of providing a secure protocol in a computer network by performing a cryptographic protocol in the computer network, the cryptographic protocol including a disjunctive proof for two relations R 0 and R 1 , the relation R 0 being between an instance set X 0 and a witness set W 0 and defining a language L(R 0 ) containing those elements x 0 ∈X 0 for which there exists a witness w 0 that is related to x 0 in accordance with R 0 , the relation R 1 being between an instance set X 1 and a witness set W 1 and defining a language L(R 1 ) containing those elements x 1 ∈ X 1 for which there exists a witness w 1 that is related to x 1 in accordance with R 1 , wherein for proving knowledge of a witness w b of at least one of instances x b and x 1-b , where b is 0 or 1, of the respective relations R b and R 1-b , wherein the method comprises:

providing a proving unit configured in a hardware device, the proving unit comprising a prover and a simulator, wherein the proving unit has an indication of the witness w b of x b ;

generating by the simulator, using the instance x 1-b , a transcript of a proof of knowledge of an eventual witness of x 1-b comprising a simulated commitment, a simulated challenge c 1-b from a challenge set C 1-b , and a simulated response;

generating by the prover a real commitment as a first step in a real proof of knowledge of a witness w b to x b ;

sending by the prover the real and simulated commitments to a verifier;

in response to the sending of the commitments, receiving by the prover from the verifier a bijective function π mapping elements from challenge set C 0 to challenge set C 1 ;

computing by the prover a real challenge c b so that c b =π 2b-1 (c 1-b );

creating by the prover a real proof of knowledge using as input a witness w b of x b comprising the real commitment, the real challenge c b , and a real response; and

sending by the prover the real and simulated proofs of knowledge to the verifier causing the verifier to accept the proofs,

wherein a secure two-party protocol for cryptography without having to share a secret is provided in the computer network.

2. The method of claim 1 , wherein the challenge sets C 0 and C 1 are identical, and where the bijective function π is a permutation over C 0 =C 1 .

3. The method of claim 1 , wherein the challenge sets C 0 and C 1 are sets of integers, and where the bijective function π is a bijective function of the bit positions in a binary representation of elements of C 0 .

4. The method of claim 1 , wherein the challenge sets C 0 and C 1 are sets of polynomials, and where the bijective function π is a permutation of the coefficients of the polynomials.

5. The method of claim 4 , where the challenge sets C 0 and C 1 are a subset C of [X]/X n +1 for a predefined integer value n.

6. A method of providing a secure protocol in computer network by performing a cryptographic protocol in the computer network, the cryptographic protocol including a disjunctive proof for two relations R 0 and R 1 , the relation R 0 being between an instance set X 0 and a witness set W 0 and defining a language L(R 0 ) containing those elements x 0 ∈X 0 for which there exists a witness w 0 that is related to x 0 in accordance with R 0 , the relation R 1 being between an instance set X 1 and a witness set W 1 and defining a language L(R 1 ) containing those elements x 1 ∈X 1 for which there exists a witness w 1 that is related to x 1 in accordance with R 1 , wherein for proving knowledge of a witness w b of at least one of instances x 0 and x 1 , where b is 0 or 1, of the respective relations R 0 and R 1 the method comprises:

providing a proving unit configured in a hardware device, the proving unit comprising a prover and a simulator, wherein the proving unit has an indication of the witness w b of x b ;

generating by the simulator, using the instance x 1-b , a transcript of a proof of knowledge of an eventual witness of x 1-b comprising a simulated commitment, a simulated challenge C 1-b from a challenge set C 1-b , and a simulated response;

generating by the prover a real commitment as the first step in a real proof of knowledge of a witness w b to x b ;

generating by the prover a hash value by applying a hash function to an input comprising the true commitment and the real commitment, and interpreting said hash value as the description a bijective function π mapping elements from challenge set C 0 to challenge set C 1 ;

computing by the prover a real challenge c b so that c b =π 2b-1 (c 1-b );

creating by the prover a real proof of knowledge using as input a witness w b of x b comprising the real commitment, the real challenge c b , and a real response; and

sending by the prover the real and simulated proofs of knowledge to the verifier causing the verifier to accept the proofs,

wherein a secure two-party protocol for cryptography without having to share a secret is provided in the computer network.

7. The method of claim 1 , wherein the proving of the knowledge of a witness of at least one of instances x b and x 1-b is the proving of the following statement x 0 ∈L(R 0 ) OR x 1 ∈L(R 1 ).

8. The method of claim 1 , wherein the simulator is configured to generate for a given x k ∈L(R k ), where k=0 or 1, a transcript that is indistinguishable from a transcript that is generated by the prover from the given x k and corresponding witness w k .

9. The method of claim 1 , wherein the relation R b is defined such that a witness w b is a homomorphic commitment of corresponding instance x b , wherein polynomials f of the challenge set are defined as {f∈ [X]/X n +1|∥f∥ ∞ =1,∥f∥ 1 =60}, wherein the predefined bijective function π is a permutation that is selected from permutation set Π=Perm(n)×{0,1} 60 , where n is an integer value.

10. The method of claim 1 , wherein set X b is a cyclic group of prime order q with generator g and the set W b is group q, wherein witness w b is related to corresponding instance x b as follows x b =g w b .

11. A proving unit configured in a hardware device, the proving unit providing a secure protocol in computer network by performing a cryptographic protocol in the computer network, the cryptographic protocol including a disjunctive proof for two relations R 0 and R 1 , the relation R 0 being between an instance set X 0 and a witness set W 0 and defining a language L(R 0 ) containing those elements x 0 E X 0 for which there exists a witness w 0 that is related to x 0 in accordance with R 0 , the relation R 1 being between an instance set X 1 and a witness set W 1 and defining a language L(R 1 ) containing those elements x 1 ∈X 1 for which there exists a witness w 1 that is related to x 1 in accordance with R 1 , wherein for proving knowledge of a witness of at least one of instances x b and x 1-b , b is 0 or 1, of the respective relations R b and R 1-b , the proving unit comprising a prover and a simulator, the proving unit having an indication of the witness of x b ;

wherein the simulator is configured for generating using the instance x 1-b , a transcript of a proof of knowledge of an eventual witness of x 1-b comprising a simulated commitment, a simulated challenge from a challenge set C 1 -b, and a simulated response;

wherein the prover is configured for

generating a real commitment in a proof of knowledge of a witness w b for the instance x b ;

sending the real and simulated commitments to a verifier;

in response to the sending of the commitments, receiving from the verifier a bijective function π mapping elements from challenge set C 0 to challenge set C 1 ;

generating a real challenge c b from challenge set C b by such that c b =π 2b-1 (c 1-b );

creating a real proof of knowledge of the witness of x b using as inputs the instance x b and the corresponding witness w b , comprising of the real commitment, the real challenge c b and a real response; and

ending the real and simulated proofs of knowledge causing the verifier to accept the proofs,

the proving unit configured to provide a secure protocol in computer network,

wherein a secure two-party protocol for cryptography without having to share a secret is provided in the computer network.

12. A proof system comprising the proving unit of claim 11 and a verifier, wherein the verifier is configured for selecting the bijective function from a set of functions and sending the bijective function to the prover in response to receiving the simulated and real commitments from the prover.

13. The method of claim 1 , wherein the method secures a lattice-based electronic voting for binary elections for proving that a ballot contains a zero or one vote.

14. The method of claim 6 , wherein the method secures a lattice-based electronic voting for binary elections for proving that a ballot contains a zero or one vote.