Class: SigmaProofOr

verificatum.crypto.SigmaProofOr(challengeSpace, param, copies)

new SigmaProofOr(challengeSpace, param, copies)

Let R be an NP relation for which there is a Sigma proof (P, V), let c > 0 be an integer, and define the NP relation R(c) to consist of all pairs of the form (x, (w, i)) such that (x[i], w) is contained in R for some 0 <= i < c. This class gives a Sigma proof for R(c) provided that:
  1. The challenge space of V is a finite additive group, i.e., challenges implement add() and sub() for addition and subtraction, and toByteTree().
  2. The challenge is uniquely determined by the proof commitment and the reply. It may suffice that it is infeasible to find two distinct challenges that give accepting transcripts, but great care is needed.
Parameters:
Name Type Description
challengeSpace Space of challenges. This must implement a method toElement() that converts a byte tree to a challenge.
param Array of proofs in which case the second parameter must not be used, or a single sigma proof in which case the second parameter must be a positive integer.
copies Number of copies in case the first parameter is a single sigma proof.
Source:

Extends

Methods

byteTreeToCommitment(byteTree)

Converts a byte tree to a commitment.
Parameters:
Name Type Description
byteTree Byte tree representation of a commitment.
Inherited From:
Source:
Returns:
Commitment.

byteTreeToReply(byteTree)

Converts a byte tree to a reply.
Parameters:
Name Type Description
byteTree Byte tree representation of a reply.
Overrides:
Source:
Returns:
Reply.

challenge(first, second)

Computes the challenge of the verifier using either a source of randomness or by applying the Fiat-Shamir heuristic to a byte tree using a given hash function.
Parameters:
Name Type Description
first Source of randomness, or data to be hashed.
second Statistical distance from the uniform distribution assuming a perfect random source, or a hash function used to implement the Fiat-Shamir heuristic.
Inherited From:
Source:
Returns:
Challenge of the verifier.

check(instance, commitment, challenge, witness, reply)

Computes the verdict of the verifier on a transcript.
Parameters:
Name Type Description
instance Instance.
commitment Commitment.
challenge Challenge of the prover.
witness Witness.
reply Reply.
Overrides:
Source:
Returns:
Verdict of the verifier as a boolean.

commit(precomputed, instance, witness, randomSource, statDist)

Computes a pair of updated pre-computed values and a commitment.
Parameters:
Name Type Description
precomputed Pre-computed values.
instance Instance.
witness Witness.
randomSource Source of randomness.
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Overrides:
Source:
Returns:
Pair of updated pre-computed values and a commitment.

commitmentToByteTree(commitment)

Converts a commitment to a byte tree.
Parameters:
Name Type Description
commitment Commitment.
Inherited From:
Source:
Returns:
Byte tree representation of the commitment.

completeProof(precomputed, label, instance, witness, hashfunction, randomSource, statDist)

Completes a proof using pre-computed values.
Parameters:
Name Type Description
precomputed Pre-computed values.
label Label as an array of bytes or byte tree.
instance Instance.
witness Witness of instance belonging to the right language.
hashfunction Hash function used to implement the random oracle.
randomSource Source of randomness.
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Inherited From:
Source:
Returns:
Proof in the form of a byte array.

instanceToByteTree(instance)

Converts an instance to a byte tree.
Parameters:
Name Type Description
instance Instance.
Inherited From:
Source:
Returns:
Byte tree representation of the instance.

precompute(randomSource, statDist)

Performs pre-computation.
Parameters:
Name Type Description
randomSource Source of randomness.
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Inherited From:
Source:
Returns:
Pre-computed values.

precomputeRequiresInstance()

Indicates if pre-computation requires the instance. This allows choosing the right pre-computation function.
Overrides:
Source:
Returns:
True or false depending on if pre-computation requires the instance or not.

precomputeWithInstance(instance, randomSource, statDist)

Performs pre-computation when the instance is needed.
Parameters:
Name Type Description
instance Instance.
randomSource Source of randomness.
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Overrides:
Source:
Returns:
Pre-computed values.

prove(label, instance, witness, hashfunction, randomSource, statDist)

Computes a proof.
Parameters:
Name Type Description
label Label as an array of bytes or byte tree.
instance Instance.
witness Witness of instance belonging to the right language.
hashfunction Hash function used to implement the random oracle.
randomSource Source of randomness.
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Inherited From:
Source:
Returns:
Proof in the form of a byte array.

randomnessByteLength(statDist)

Number of bytes or randomness needed to compute a proof.
Parameters:
Name Type Description
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Inherited From:
Source:
Returns:
Number of bytes needed to compute a proof.

reply(precomputed, witness, challenge, randomness)

Computes the reply of the prover.
Parameters:
Name Type Description
precomputed Pre-computed values needed to compute the reply.
witness Witness.
challenge Challenge of the verifier.
randomness Randomness used to form the commitment.
Overrides:
Source:
Returns:
Reply of the prover.

replyToByteTree(reply)

Converts a reply to a byte tree.
Parameters:
Name Type Description
reply Reply.
Overrides:
Source:
Returns:
Byte tree representation of the reply.

simulate(instance, challenge, randomSource, statDist)

Simulates a commitment and reply for the given challenge.
Parameters:
Name Type Description
instance Instance.
challenge Challenge of the verifier.
randomSource Source of randomness.
statDist Statistical distance from the uniform distribution assuming a perfect random source.
Overrides:
Source:
Returns:
Pair of a commitment and reply.

verify(label, instance, hashfunction, proof)

Verifies a proof. This is meant to be used for debugging, so the granularity in error handling is rudimentary.
Parameters:
Name Type Description
label Label as an array of bytes or byte tree.
instance Instance.
hashfunction Hash function used to implement the random oracle.
proof Candidate proof in the form of a byte array.
Inherited From:
Source:
Returns:
True or false depending on if the candidate proof is valid or not.