2
0

README.md 19 KB

Zero-Knowledge Proof Module

This module defines the zero-knowledge proof API for Scytl's JavaScript cryptographic library. The starting point for using this module is the instantiation of a zero-knowledge proof service.

How to view, build and test the source code of this module

Start by git cloning the project comm/scytl-cryptolib from Stash.

The source code of this module will be found in the directory scytl-cryptolib/cryptolib-js-zkproof/lib.

To build this module, change to the directory scytl-cryptolib/cryptolib-js-zkproof and do the following:

npm install
--or--
mvn clean install -DskipTests

The unit tests of this module will be found in the directory scytl-cryptolib/cryptolib-js-zkproof/spec. To run the tests, change to the directory scytl-cryptolib/cryptolib-js-zkproof and do the following:

karma test
--or--
mvn test

To only run a chosen test suite, add an f in front of the corresponding describe statement. For example:

fdescribe('create an exponentiation proof handler that should be able to', function()
...

To only run a chosen test, add an f in front of the corresponding it statement. For example:

fit('generate and verify an exponentiation proof', function()
...

Note: To build and test the entire scytl-cryptolib project, change to the directory scytl-cryptolib and do the following:

mvn clean install

How to generate the JSDoc for this module

To generate the JSDoc for this module, change to the directory scytl-cryptolib/cryptolib-js-zkproof, build the module (if not already done) and do the following:

node_modules/.bin/jsdoc lib

This will generate a file called out. Double click on the file out/index.html to view the JSDoc.

How to npm install this module

To npm install this module in standalone mode, do the following:

npm install --registry https://nexus.scytl.net/content/groups/public-npm/ scytl-zkproof

To npm install this module as a dependency of your own module, do the following:

  1. Add the following lines to the dependencies section of your module's package.json file.

    "scytl-codec": "^2.1.0",
    "scytl-cryptopolicy": "^2.1.0",
    "scytl-messagedigest": "^2.1.0",
    "scytl-securerandom": "^2.1.0",
    "scytl-mathematical": "^2.1.0",
    "scytl-elgamal": "^2.1.0",
    "scytl-zkproof": "^2.1.0",
    
  2. Make sure that the .npmrc file of your module contains the following line.

    registry=https://nexus.scytl.net/content/groups/public-npm/
    
  3. Install all dependencies.

    npm install
    

    How to instantiate a zero-knowledge proof service

The following example shows the default way to create a new instance of a zero-knowledge proof service.

var zkProof = require('scytl-zkproof');

var proofService = zkProof.newService();

The following example shows how to override the default cryptographic policy used for zero-knowledge proof operations, by changing the message digest algorithm to SHA-512/224.

var cryptoPolicy = require('scytl-cryptopolicy');
var zkProof = require('scytl-zkproof');

var myPolicy = cryptoPolicy.newInstace();

myPolicy.proofs.messagedigest.algorithm =
  cryptoPolicy.options.proofs.messageDigest.algorithm.SHA512_224;

var proofService = zkProof.newService({policy: myPolicy});

Note It is desirable to use the property CryptographicPolicy.options to override the default policy, as shown above, in order to ensure that one is using an option that is allowed by the cryptographic policy.

The following example shows how to supply one's own mathematical service and message digest service to the zero-knowledge proof service.

var zkProof = require('scytl-zkproof');
var mathematical = require('scytl-mathematical');
var messageDigest = require('scytl-messagedigest');

var myMathematicalService = mathematical.newService();
var myMessageDigistService = messageDigest.newService({policy: myPolicy}})

var proofService = zkProof.newService({
  policy: myPolicy,
  mathematicalService: myMathematicalService,
  messageDigestService: myMessageDigestService
});

Note When both a service and the cryptographic policy are specified as options, one must ensure that the specified service uses the specified policy, as shown above.

How to instantiate and initialize a zero-knowledge proof handler

The following example shows how to create and initialize a plaintext proof handler that can be used to generate, pre-compute or verify a plaintext zero-knowledge proof of knowledge (see next section). The input for handler creation consists of the Zp subgroup pertaining to all mathematical operations used by the handler. The handler is initialized with the ElGamal public used to generate any ciphertext used for plaintext proof operations.

var zkProof = require('scytl-zkproof');
var elGamal = require('scytl-elgamal');
var mathematical = require('scytl-mathematical');
var forge = require('node-forge');

var BigInteger = forge.jsbn.BigInteger;

var mathService = mathematical.newService();
var elGamalService = elGamal.newService();
var proofService = zkProof.newService();

var g = new BigInteger('2');
var p = new BigInteger('23');
var q = new BigInteger('11');
var group = mathService.newZpSubgroup(g, p, q);

var keyElement1 = mathService.newZpGroupElement(p, q, new BigInteger('2'));
var keyElement2 = mathService.newZpGroupElement(p, q, new BigInteger('4'));
var publicKey_ = elGamalService.newPublicKey(group, [keyElement1, keyElement2]]);

var proofService = zkProof.newService();

var plaintextProofHandler = proofService.newPlaintextProofHandler(group);
plaintextProofHandler.init(publicKey);
          --or--
var plaintextProofHandler = proofService.newPlaintextProofHandler(group).init(publicKey);

The following examples show how to create and initialize handlers for the six additional supported zero-knowledge proofs of knowledge. Note The Schnorr proof handler does not require initialization because it only requires information from its associated group to perform proof operations.

var schnorrProofHandler = proofService.newSchnorrProofHandler(group);
var exponentiationProofHandler = proofService.newExponentiationProofHandler(group).init(baseElements);
var simplePlaintextEqualityProofHandler = proofService.newSimplePlaintextEqualityProofHandler(group).init(primaryPublicKey, secondaryPublicKey);
var plaintextEqualityProofHandler = proofService.newPlaintextEqualityProofHandler(group).init(primaryPublicKey, secondaryPublicKey);
var plaintextExponentEqualityProofHandler = proofService.newPlaintextExponentEqualityProofHandler(group).init(baseElements);
var orProofHandler = proofService.newOrProofHandler(group).init(publicKey);

How to generate zero-knowledge proofs

The following example shows how to generate a plaintext zero-knowledge proof of knowledge, given the secret ElGamal exponent of whose knowledge is to be proved, the plaintext and the ciphertext generated from the secret exponent and the plaintext, as input.

var zkProof = require('scytl-zkproof');
var elGamal = require('scytl-elgamal');
var mathematical = require('scytl-mathematical');
var forge = require('node-forge');

var BigInteger = forge.jsbn.BigInteger;

var mathService = mathematical.newService();
var elGamalService = elGamal.newService();
var proofService = zkProof.newService();
...

var element1 = mathService.newZpGroupElement(p, q, new BigInteger('3'));
var element2 = mathService.newZpGroupElement(p, q, new BigInteger('6'));
var plaintext = [element1, element2];

var elGamalEncrypter = elGamalService.newEncrypter().init(publicKey);
var plaintextProofHandler = proofService.newPlaintextProofHandler(group).init(publickey);

var encryptedElementsAndSecret = elGamalEncrypter.encrypt(plaintext, {saveSecret: true});
var secret = encryptedElementsAndSecret.secret;
var ciphertext = elGamalService.newEncryptedElements(encryptedElementsAndSecret.gamma, encryptedElementsAndSecret.phis);

var plaintextProof = plaintextProofHandler.generate(secret, plaintext, ciphertext);

The following examples show how to generate zero-knowledge proofs of knowledge for the six additional supported proof types.

var schnorrProof = schnorrProofHandler.generate(secret, gamma);
var exponentiationProof = exponentiationProofHandler.generate(secret, exponentiatedElements);
var simplePlaintextEqualityProof = simplePlaintextEqualityProofHandler.generate(secret, primaryCiphertext, secondaryCiphertext);
var plaintextEqualityProof = plaintextEqualityProofHandler.generate(primarySecret, secondarySecret, primaryCiphertxt, secondaryCiphertext);
var plaintextExponentEqualityProof = plaintextExponentEqualityProofHandler.generate(firstSecret, secondSecret, ciphertext);
var OrProof = orProofHandler.generate(secret, elements, index, ciphertext);

A detailed description of these methods can be found in the JSDoc for the zero-knowledge proof module. Examples of usage may found in the associated spec tests.

How to pre-compute zero-knowledge proofs

The following example shows how to generate a plaintext zero-knowledge proof of knowledge by performing a pre-computation step. The pre-computation step does not require knowledge of the secret, plaintext or ciphertext. Therefore, it can be handled by a web worker during a voting session. Since the operations performed during the pre-computation step are computationally dominant in the proof generation process, passing this step to a worker can significantly improve performance. The output of the pre-computation step will be a ZeroKnowledgeProofPreComputation object, which may then be used as an input argument to the proof generation method.

/* The following can be performed by a web worker. The result of the pre-computation is serialized in order to send it back to the main thread. */
var preComputation = plaintextProofHandler.preCompute();
var preComputationJson = preComputation.toJson();

/* The following can be performed by the main thread. The result of the pre-computation is deserialized after receiving it from the web worker. */
var preComputation = proofService.newPreComputation(preComputationJson);
var plaintextProof = plaintextProofHandler.generate(secret, plaintext, ciphertext, {preComputation: preComputation});

The preCompute method does not require input arguments for any of the supported zero-knowledge proofs of knowledge except that of the OR proofs, which requires one to specify the number of Zp group element candidates for encryption.

How to verify zero-knowledge proofs

The following example shows how to verify a plaintext zero-knowledge proof of knowledge. The result will be true if the proof was successfully verified, false otherwise.

var verified = plaintextProofHandler.verify(plaintextProof, plaintext, ciphertext);

The following examples show how to verify zero-knowledge proofs of knowledge for the six additional supported proof types.

var verified = schnorrProofHandler.verify(schnorrProof, gamma);
var verified = exponentiationProofHandler.verify(exponentationProof, exponentiatedElements);
var verified = simplePlaintextEqualityProofHandler.verify(simplePlaintextEqualityProof, primaryCiphertxt, secondaryCiphertext);
var verified = plaintextEqualityProofHandler.verify(plaintextEqualityProof, primaryCiphertxt, secondaryCiphertext);
var verified = plaintextExponentEqualityProofHandler.verify(plaintextExponentEqualityProof, ciphertext);
var verified = orProofHandler.verify(orProof, elements, ciphertext);

A detailed description of these methods can be found in the JSDoc for the zero-knowledge proof module. Examples of usage may found in the associated spec tests.

How to supply optional auxiliary data for zero-knowledge proof generation or verification.

The following examples show how to supply optional auxiliary data for the generation and verification of a plaintext zero-knowledge proof of knowledge. The data may be be provided as a string or as a byte array, wrapped in a Uint8Array object.

var codec = require('scytl-codec');
...

var myData = 'my auxiliary data';

var plaintextProof = plaintextProofHandler.generate(secret, plaintext, ciphertext, {data: myData});
var verified = plaintextProofHandler.verify(plaintextProof, plaintext, ciphertext, {data: myData});

var plaintextProof = plaintextProofHandler.generate(secret, plaintext, ciphertext, {data: codec.utf8Encode(myData)});
var verified = plaintextProofHandler.verify(plaintextProof, plaintext, ciphertext, {data: codec.utf8Encode(myData)});

Note If auxiliary data is provided when generating a proof, then the same data must be provided when verifying the proof.

The following example shows how to provide a voter ID and and election ID when generating and verifying a Schnorr zero-knowledge proof of knowledge.

var myVoterId = 'a voter ID';
var myElectionId = 'an election ID';

var schnorrProof = schnorrProofHandler.generate(secret, gamma, {voterId: myVoterId, electionId: myElectionId});
var verified = schnorrProofHandler.verify(schnorrProof, gamma, {voterId: myVoterId, electionId: myElectionId});

Note This feature is only available for Schnorr zero-knowledge proofs, in order to make them compatible with the way Schnorr zero-knowledge proofs are presently generated by cryptoLib, implemented in Java. If a voter ID is provided as input then an election ID must also be provided, and vise versa. When these input arguments are provided, the supply of any additional auxiliary data will have no effect.

How to create new proof objects

Although, in most cases, the ZeroKnowledgeProof and ZeroKnowldegeProofPreComputation objects will be created via generation or pre-computation operations, respectively, there might be some cases where these objects need to be constructed manually. These operations should always be performed via the service.

The following example shows how to construct a new ZeroKnowledgeProof object, given its hash exponent and array of value exponents.

var proof = proofService.newProof(hash, values);

The following example shows how to construct a new ZeroKnowldegeProofPreComputation object, given its array of randomly generated exponents and array of PHI function output elements.

var preComputation = proofService.newPreComputation(exponents, phiOutputs);

How to serialize and deserialize zero-knowledge proof objects.

The following examples illustrate how to serialize and deserialize ZeroKnowledgeProof and ZeroKnowldegeProofPreComputation objects to and from their corresponding JSON representations.

var proofJson = proof.toJson();
var proof = proofService.newProof(proofJson);
var preComputationJson = preComputation.toJson();
var preComputation = proofService.newPreComputation(preComputationJson);

How to use a progress meter

The following example shows how to use a progress meter and an associated callback function for the plaintext proof generation, pre-computation and verification processes.

function myCallbackFunction() {
   <do something here every time progress is checked>
}

var preComputation = plaintextProofHandler.measureProgress(myCallBackFunction).preCompute();
var plaintextProof = plaintextProofHandler.measureProgress(myCallBackFunction).generate(secret, plaintext, ciphertext);
var verified = plaintextProofHandler.measureProgress(myCallBackFunction).verify(plaintextProof, plaintext, ciphertext);

By default, the progress will be measured every time that it increases by 10% of its final expected value. This check interval is referred to as the progress percent minimum check interval and it can be overridden by providing it as a second argument to the method measureProgress, as shown in the following examples.

var minCheckInterval = 5;

var preComputation = plaintextProofHandler.measureProgress(myCallBackFunction, minCheckInterval).preCompute();
var plaintextProof = plaintextProofHandler.measureProgress(myCallBackFunction, minCheckInterval).generate(secret, plaintext, ciphertext);
var verified = plaintextProofHandler.measureProgress(myCallBackFunction, minCheckInterval).verify(plaintextProof, plaintext, ciphertext);

In this example, the progress will be measured every time that it increases by 5% of its final expected value.

Note Progress measurement will have no effect for the generate method if a pre-computation is provided as input. This is because progress is only measured for the pre-computation part of the proof generation, which dominates the performance.

The measureProgress methods for the other supported types of zero-knowledge proofs of knowledge work in the same way as the above example.

How to perform zero-knowledge proof operations using method chaining

While it is not always recommended, it is possible to combine several zero-knowledge proof operations into one step, by making use of method chaining.

The following examples show how to pre-compute, generate and verify a plaintext zero-knowledge proof of knowledge, each in one step.

var preComputation = proofService.newPlaintextProofHandler(group).init(publicKey).preCompute();
var plaintextProof = proofService.newPlaintextProofHandler(group).init(publicKey).generate(secret, plaintext, ciphertext);
var verified = proofService.newPlaintextProofHandler(group).init(publicKey).verify(plaintextProof, plaintext, ciphertext);

The following examples show how to perform the same operations as above, while also measuring progress.

var preComputation = proofService.newPlaintextProofHandler(group).measureProgress(callback).init(publicKey).preCompute();
var plaintextProof = proofService.newPlaintextProofHandler(group).measureProgress(callback).init(publicKey).generate(secret, plaintext, ciphertext);
var verified = proofService.newPlaintextProofHandler(group).measureProgress(callback).init(publicKey).verify(plaintextProof, plaintext, ciphertext);

Note regarding input data validation and Zp subgroup membership checks

In general, the input data validation performed by the zero-knowledge proof service does not include checking that the values of a Zp group element array or the element values of an ElGamal encryption provided as input are members of the Zp subgroup provided as input (either directly or via an ElGamal key). The reason for this, is that the group membership check involves the modPow mathematical operation, which is computationally costly and is linearly proportional to the number of values to check. The mathematical service provides a method called checkGroupMembership that can, for example, be used to check an array of Zp group elements against a Zp subgroup before providing this data as input to a proof generation, pre-computation or verification method of the zero-knowledge proof service.