Statement proof and verification
A method of proving that a secret committed in a commitment is a discrete logarithm of a public element of a finite group of data elements, comprising: obtaining a first vector used to generate the commitment, the first vector comprising n components, wherein one of the n components of the first vector is at a position which corresponds to the secret; generating a second vector comprising n components, wherein a component of the second vector, at a predetermined position corresponding to the position in the first vector, is set to zero; generating a further commitment to the second vector; transmitting the further commitment to a verifying device; receiving a random challenge from the verifying device; generating a response using the first vector, the second vector and the random challenge; and transmitting the response to the verifying device to prove that the secret is the discrete logarithm of the public element.
1 . A computer implemented method of proving that a secret that is committed in a batched commitment is a discrete logarithm of a public element of a finite group of data elements, the method performed on a computing device and comprising:
obtaining a first vector used to generate the batched commitment, the first vector comprising n components, wherein the secret is one of the n components of the first vector at a position in the first vector;
generating a second vector comprising n components, wherein a component of the second vector, at a predetermined position corresponding to the position in the first vector, is set to zero;
generating a further batched commitment to the second vector;
transmitting the further batched commitment to a verifying computing device;
receiving a random challenge from the verifying computing device;
generating a response to the random challenge using the first vector, the second vector and the random challenge; and
transmitting the response to the verifying computing device to prove that the secret is the discrete logarithm of the public element.
2 . The computer implemented method of claim 1 , wherein the finite group of data elements are of an elliptic curve.
3 . The computer implemented method of claim 2 , wherein the element of said finite group of data elements is a public key and the secret is a signing key.
4 . The computer implemented method of claim 2 , wherein generating the further batched commitment to the second vector uses a commitment key vector comprising n components from the finite group of data elements and one of the n components of the commitment key vector is a base point of the elliptic curve at a predetermined position which corresponds to the position in the first vector, the public element obtained by multiplying said base point with the secret.
5 . The computer implemented method of claim 1 , wherein generating the response to the random challenge comprises:
modifying the first vector by replacing the secret at said position with a zero to generate a modified first vector;
generating a response vector by combining the modified first vector with the second vector using the random challenge;
wherein the response comprises the response comprising the response vector.
6 . The computer implemented method of claim 1 , wherein remaining components of the second vector are random values.
7 . The computer implemented method of claim 1 , further comprising generating a random element, and generating the further batched commitment using the random element.
8 . The computer implemented method of claim 7 , wherein the method further comprises generating a combined random element by combining the random element with a further random element used to generate the batched commitment, wherein the response comprises the combined random element.
9 . The computer implemented method of claim 1 , wherein the batched commitment is a batched Pedersen commitment.
10 . The computer implemented method of claim 1 , wherein the further batched commitment is a batched Pedersen commitment.
11 . A computer implemented method of verifying that a secret that is committed in a batched commitment is a discrete logarithm of a public element of a finite group of data elements, the method performed on a computing device and comprising:
obtaining the batched commitment, wherein the batched commitment is a commitment to a first vector comprising n components and one of the n components of the first vector is the secret and is at a position in the first vector;
receiving a further batched commitment from a proving computing device, wherein the further batched commitment is a commitment to a second vector comprising n components, wherein a component of the second vector, at a predetermined position corresponding to the position in the first vector, is set to zero;
in response to receiving the further batched commitment generating a random challenge and transmitting the random challenge to the proving computing device;
receiving a response to the random challenge from the proving computing device; and
verifying that the secret is the discrete logarithm of the public element using the response, the batched commitment, the further batched commitment, and the random challenge.
12 . The computer implemented method of claim 11 , wherein the response comprises a response vector that is a combination of a modified first vector and the second vector using the random challenge, the modified first vector corresponding to the first vector wherein the secret at said position has been replaced with a zero.
13 . The computer implemented method of claim 12 , wherein the response vector comprises a plurality of components, and said verifying comprises determining that a component of the plurality of components of the response vector, at a predetermined position which corresponds to the position in the first vector, is non-zero.
14 . The computer implemented method of claim 11 , wherein the finite group of data elements are of an elliptic curve.
15 . The computer implemented method of claim 12 , wherein the public element of said finite group of data elements is a public key and the secret is a signing key.
16 . The computer implemented method of claim 14 , the method comprising:
computing a combined commitment using the batched commitment, the random challenge, the further batched commitment and the public element of said finite group of data elements; and
verifying that the secret is the discrete logarithm of the public element using the response, the combined commitment, and a commitment key vector, wherein the commitment key vector comprises n components from the finite group of data elements and one of the n components of the commitment key vector is a base point of the elliptic curve at a predetermined position which corresponds to the position in the first vector, the public element obtained by multiplying said base point with the secret.
17 . The computer implemented method of claim 1 , wherein remaining components of the second vector are random values.
18 . The computer implemented method of claim 1 , wherein the batched commitment is a batched Pedersen commitment.
19 . A non-transitory computer readable storage medium comprising computer readable instructions that, when executed by a computing device, cause the computing device to perform a method of proving that a secret that is committed in a batched commitment is a discrete logarithm of a public element of a finite group of data elements, the method performed on a computing device and comprising:
obtaining a first vector used to generate the batched commitment, the first vector comprising n components, wherein the secret is one of the n components of the first vector at a position in the first vector;
generating a second vector comprising n components, wherein a component of the second vector, at a predetermined position corresponding to the position in the first vector, is set to zero;
generating a further batched commitment to the second vector;
transmitting the further batched commitment to a verifying computing device;
receiving a random challenge from the verifying computing device;
generating a response to the random challenge using the first vector, the second vector and the random challenge; and
transmitting the response to the verifying computing device to prove that the secret is the discrete logarithm of the public element.