prover.js 6.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195
  1. /*
  2. * Copyright 2018 Scytl Secure Electronic Voting SA
  3. *
  4. * All rights reserved
  5. *
  6. * See our extended copyright notice in *file 'Copyright.txt' which is part of this source code package
  7. */
  8. /* jshint node:true */
  9. 'use strict';
  10. var ZeroKnowledgeProof = require('./proof.js');
  11. var ZeroKnowledgeProofPreComputation = require('./pre-computation.js');
  12. var HashGenerator = require('./hash-generator');
  13. var codec = require('scytl-codec');
  14. module.exports = ZeroKnowledgeProofProver;
  15. /**
  16. * @class ZeroKnowledgeProofProver
  17. * @classdesc Encapsulates a zero-knowledge proof of knowledge prover that uses
  18. * the PHI function defined in Maurer's unified framework.
  19. * @private
  20. * @param {MessageDigestService}
  21. * messageDigestService The message digest service to use.
  22. * @param {MathematicalService}
  23. * mathService The mathematical service to use.
  24. */
  25. function ZeroKnowledgeProofProver(messageDigestService, mathService) {
  26. var mathRandomGenerator_ = mathService.newRandomGenerator();
  27. /**
  28. * Generates a zero-knowledge proof of knowledge.
  29. *
  30. * @function prove
  31. * @memberof ZeroKnowledgeProofProver
  32. * @param {ZpSubgroup}
  33. * group The Zp subgroup to which all exponents and Zp group
  34. * elements required for the proof generation are associated or
  35. * belong, respectively.
  36. * @param {Exponent[]}
  37. * privateValues The private values used to generate the proof.
  38. * @param {ZpGroupElement[]}
  39. * publicValues The public values used to generate the proof.
  40. * @param {Uint8Array|string}
  41. * data Auxiliary data.
  42. * @param {ZeroKnowledgeProofPreComputation}
  43. * preComputation The zero-knowledge proof of knowledge
  44. * pre-computation.
  45. * @param {ZpGroupElement[]}
  46. * [elements] A parameter to be used only for the generation of
  47. * OR zero-knowledge proofs of knowledge. It consists of the
  48. * possible Zp group elements used to generate the ciphertext.
  49. * @param {number}
  50. * [index] A parameter that is only to be used if the previous
  51. * parameter was used. It is the secret index of the Zp group
  52. * element that was used to generate the ciphertext of an OR
  53. * zero-knowledge proof of knowledge.
  54. * @returns {ZeroKnowledgeProof} The generated zero-knowledge proof of
  55. * knowledge.
  56. */
  57. this.prove = function(
  58. group, privateValues, publicValues, data, preComputation, elements,
  59. index) {
  60. if (typeof elements !== 'undefined') {
  61. preComputation = updatePreComputation(
  62. group, preComputation, publicValues, elements, index);
  63. }
  64. var hash =
  65. generateHash(group, publicValues, preComputation.phiOutputs, data);
  66. var proofValues = generateProofValues(
  67. group, privateValues, hash, preComputation.exponents, index);
  68. return new ZeroKnowledgeProof(hash, proofValues);
  69. };
  70. /**
  71. * Pre-computes a Schnorr zero-knowledge proof of knowledge. IMPORTANT: The
  72. * same pre-computed values must not be used twice.
  73. *
  74. * @function preComputeSchnorrProof
  75. * @memberof ZeroKnowledgeProofProver
  76. * @param {ZpSubgroup}
  77. * group The Zp subgroup to which all exponents and Zp group
  78. * elements required for the pre-computation are associated or
  79. * belong, respectively.
  80. * @param {PhiFunction}
  81. * phiFunction The PHI function used for the pre-computation.
  82. * @param {ProgressMeter}
  83. * [progressMeter=Not used] A progress meter.
  84. * @returns {ZeroKnowledgeProofPreComputation} The Schnorr zero-knowledge
  85. * proof of knowledge pre-computation.
  86. */
  87. this.preCompute = function(group, phiFunction, progressMeter) {
  88. var exponents = generateExponents(group, phiFunction.numInputs);
  89. var phiOutputs = phiFunction.calculate(exponents, progressMeter);
  90. return new ZeroKnowledgeProofPreComputation(exponents, phiOutputs);
  91. };
  92. function generateHash(group, publicValues, phiOutputs, data) {
  93. var hashGenerator = new HashGenerator(messageDigestService);
  94. var hashBytes = hashGenerator.generate(publicValues, phiOutputs, data);
  95. var hashByteArray = Array.apply([], hashBytes);
  96. hashByteArray.unshift(0);
  97. var value = codec.bytesToBigInteger(hashBytes);
  98. return mathService.newExponent(group.q, value);
  99. }
  100. function generateProofValues(group, privateValues, hash, exponents, index) {
  101. var proofValues = [];
  102. var proofValue;
  103. if (typeof index === 'undefined') {
  104. for (var i = 0; i < privateValues.length; i++) {
  105. proofValue =
  106. exponents[i].value.add(privateValues[i].value.multiply(hash.value));
  107. proofValues.push(mathService.newExponent(group.q, proofValue));
  108. }
  109. } else {
  110. var numElements = exponents.length / 2;
  111. var updatedHash = hash;
  112. for (var j = 0; j < numElements; j++) {
  113. if (j === index) {
  114. for (var k = 0; k < numElements; k++) {
  115. if (k !== index) {
  116. updatedHash = updatedHash.subtract(exponents[k]);
  117. }
  118. }
  119. proofValues.push(updatedHash);
  120. } else {
  121. proofValues.push(exponents[j]);
  122. }
  123. }
  124. for (var m = numElements; m < (numElements * 2); m++) {
  125. if (m === (numElements + index)) {
  126. proofValue = exponents[m].value.add(
  127. privateValues[0].value.multiply(updatedHash.value));
  128. proofValues.push(mathService.newExponent(group.q, proofValue));
  129. } else {
  130. proofValues.push(exponents[m]);
  131. }
  132. }
  133. }
  134. return proofValues;
  135. }
  136. function updatePreComputation(
  137. group, preComputation, publicValues, elements, index) {
  138. var gamma = publicValues[0];
  139. var phi = publicValues[1];
  140. var numElements = elements.length;
  141. var challenges = generateExponents(group, numElements);
  142. var updatedExponents = challenges.concat(preComputation.exponents);
  143. var updatedPhiOutputs = [];
  144. var phiOutputs = preComputation.phiOutputs;
  145. for (var j = 0; j < numElements; j++) {
  146. var offset = 2 * j;
  147. if (j === index) {
  148. updatedPhiOutputs.push(phiOutputs[offset]);
  149. updatedPhiOutputs.push(phiOutputs[offset + 1]);
  150. } else {
  151. var gammaFactor = gamma.invert().exponentiate(challenges[j]);
  152. var phiFactor =
  153. (phi.invert().multiply(elements[j])).exponentiate(challenges[j]);
  154. updatedPhiOutputs.push(phiOutputs[offset].multiply(gammaFactor));
  155. updatedPhiOutputs.push(phiOutputs[offset + 1].multiply(phiFactor));
  156. }
  157. }
  158. return new ZeroKnowledgeProofPreComputation(
  159. updatedExponents, updatedPhiOutputs);
  160. }
  161. function generateExponents(group, numExponents) {
  162. var exponents = [];
  163. for (var i = 0; i < numExponents; i++) {
  164. exponents.push(mathRandomGenerator_.nextExponent(group));
  165. }
  166. return exponents;
  167. }
  168. }