Method for performing a disjunctive proof for two relations

A method for performing a disjunctive proof for two relations R0 and R1, the relation R0 being between an instance set X0 and a witness set W0 and defining a language L(R0) containing those elements x0∈X0 for which there exists a witness w0 that is related to x0 in accordance with R0, the relation R1 being between an instance set X1 and a witness set W1 and defining a language L(R1) containing those elements x1∈X1 for which there exists a witness w1 that is related to x1 in accordance with R1, wherein for proving knowledge of a witness wb of at least one of instances x0 and x1, where b is 0 or 1, of the respective relations R0 and R1 the method comprises:

• providing a proving unit comprising a prover and a simulator, wherein the proving unit has an indication of the witness wb of xb;
• generating by the simulator, using the instance x1-b, a transcript of a proof of knowledge of an eventual witness of x1-b comprising a simulated commitment, a simulated challenge c1-b from a challenge set C and a simulated response;
• generating by the prover a real commitment as the first step in a real proof of knowledge of a witness wb to xb;
• 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 iv mapping elements from challenge set C0 to challenge set C1;
• computing by the prover a real challenge cb so that cb=π2b-1(c1-b);
• creating by the prover a real proof of knowledge using as input a witness wb of xb comprising the real commitment, the real challenge cb, 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.

A proving unit for performing a disjunctive proof for two relations R0 and R1, the relation R0 being between an instance set X0 and a witness set W0 and defining a language L(R0) containing those elements x0∈X0 for which there exists a witness w0 that is related to x0 in accordance with R0, the relation R1 being between an instance set X1 and a witness set W1 and defining a language L(R1) containing those elements x1∈X1 for which there exists a witness w1 that is related to x1 in accordance with R1, wherein for proving knowledge of a witness of at least one of instances xb and x1-b, b is 0 or 1, of the respective relations Rb and R1-b, the proving unit comprising a prover and a simulator, the proving unit having an indication of the witness of xb;

• wherein the simulator is configured for generating using the instance x1-b, a transcript of a proof of knowledge of an eventual witness of x1-b comprising a simulated commitment, a simulated challenge from a challenge set C1-b, and a simulated response;
• wherein the prover is configured for
• generating a real commitment in a proof of knowledge of a witness wb for the instance xb;
• 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 C0 to challenge set C1;
• generating a real challenge cb from challenge set Cb by such that cb=π2b-1(c1-b);
• creating a real proof of knowledge of the witness of xb using as inputs the instance xb and the corresponding witness wb, comprising of the real commitment, the real challenge cb and a real response;
• and
• ending the real and simulated proofs of knowledge causing the verifier to accept the proofs.