[GNUnet-SVN] r23905 - in gnunet-java: . src/org/gnunet src/org/gnunet/voting

[gnunet]

Author: dold
Date: 2012-09-20 11:38:15 +0200 (Thu, 20 Sep 2012)
New Revision: 23905

Added:
   gnunet-java/src/org/gnunet/voting/
   gnunet-java/src/org/gnunet/voting/CryptoUtil.java
   gnunet-java/src/org/gnunet/voting/ElGamalParameters.java
   gnunet-java/src/org/gnunet/voting/VotingSimulation.java
Modified:
   gnunet-java/ISSUES
Log:
started implementing secure voting

Modified: gnunet-java/ISSUES
===================================================================
--- gnunet-java/ISSUES  2012-09-20 08:55:20 UTC (rev 23904)
+++ gnunet-java/ISSUES  2012-09-20 09:38:15 UTC (rev 23905)
@@ -248,3 +248,35 @@
  * what encoding are config files in? utf-8, i assume?
  * in general, when do we want gnunet-java to crash (=uncatched exception)
   * currently: on definite programmer's error, e.g. in Construct, when an 
annotation is just wrong
+
+
+-----------------------------------------------------------
+
+
+how is the formula for the first zero knowledge proof derived?
+ * i understand why we have to do a zero knowledge proof for the validity of 
the shares, but why does this work?
+
+is fiat-shamir just choosing a hash as the challenge in zero knowledge proofs?
+
+verification / commitment to the shares: the big F in the Pederson paper, the 
formula is not legible
+
+the voting process itself: is this understanding correct:
+ * either the correct vote is cast when a voter wants to vote (expensive)
+ * or a prepared, random vote is casted (expensive), and later, when the voter 
wants to vote he posts a bit (cheap) to possibly invert the random vote so it 
corresponds to his choice
+ * the paper mentions the first vote as masked vote, but the protocol is not 
witness hiding
+
+The Chaum-Pedersen protocol is a three-move, public coin proof of
+knowledge for the relation log_g(x) = log_h(y). The proof satifies special 
soundness,
+and is special honest-verfier zero-knowledge.
+
+ * What does that mean, exactly?
+ * what is i coin proof of knowledge?
+
+what set do the shares belong to? can I do the computations modulo something?
+
+can/should I use horner's method for evaluation of polynomials?
+
+what about the signing process in [Ped91]?
+
+notation: what is Zp(z)? polynomials with variable z over Zp*?
+(ped91, §3.1, choosing a random polynomial)
\ No newline at end of file

Added: gnunet-java/src/org/gnunet/voting/CryptoUtil.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/CryptoUtil.java                           
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/CryptoUtil.java   2012-09-20 09:38:15 UTC 
(rev 23905)
@@ -0,0 +1,48 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+
+/**
+ * Miscellaneous helper functions.
+ *
+ * @author Florian Dold
+ */
+public class CryptoUtil {
+    /**
+     * Return a random BigInteger not less than 'min' and not greater than 
'max'
+     *
+     * @param min    the least value that may be generated
+     * @param max    the greatest value that may be generated
+     * @param random the source of randomness
+     * @return a random BigInteger value in the range [min,max]
+     */
+    public static BigInteger createRandomInRange(BigInteger min,
+                                                 BigInteger max,
+                                                 SecureRandom random) {
+        int cmp = min.compareTo(max);
+        if (cmp >= 0) {
+            if (cmp > 0) {
+                throw new IllegalArgumentException("'min' may not be greater 
than 'max'");
+            }
+
+            return min;
+        }
+
+        if (min.bitLength() > max.bitLength() / 2) {
+            return createRandomInRange(BigInteger.ZERO, max.subtract(min), 
random).add(min);
+        }
+
+        for (int i = 0; i < 1000; ++i) {
+            BigInteger x = new BigInteger(max.bitLength(), random);
+            if (x.compareTo(min) >= 0 && x.compareTo(max) <= 0) {
+                return x;
+            }
+        }
+
+        // fall back to a faster (restricted) method
+        // (using only this distribution would lead to a non-uniform 
distribution, see the BigInteger constructor)
+        return new BigInteger(max.subtract(min).bitLength() - 1, 
random).add(min);
+    }
+
+}

Added: gnunet-java/src/org/gnunet/voting/ElGamalParameters.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/ElGamalParameters.java                    
        (rev 0)
+++ gnunet-java/src/org/gnunet/voting/ElGamalParameters.java    2012-09-20 
09:38:15 UTC (rev 23905)
@@ -0,0 +1,114 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+
+/**
+ * Parameters for the ElGamal algorithms.
+ *
+ * p is a large prime, and g is a high-order element (or even a generator) of 
Zp*
+ *
+ * @author Florian Dold
+ */
+public class ElGamalParameters {
+
+    private BigInteger p;
+    private BigInteger g;
+
+    public ElGamalParameters(BigInteger p, BigInteger g) {
+        this.p = p;
+        this.g = g;
+    }
+
+    /**
+     * which generates the p and g values from the given parameters,
+     * returning the ElGamalParameters object.
+     * <p/>
+     * Note: can take a while...
+     */
+    public static ElGamalParameters generate(int size, int certainty, 
SecureRandom random) {
+        BigInteger[] safePrimes = generateSafePrimes(size, certainty, random);
+
+        BigInteger p = safePrimes[0];
+        BigInteger q = safePrimes[1];
+        BigInteger g = selectGenerator(p, q, random);
+
+        return new ElGamalParameters(p, g);
+    }
+
+    /**
+     * Finds a pair of prime BigInteger's {p, q: p = 2q + 1}, called safe 
primes.
+     *
+     * (see: Handbook of Applied Cryptography 4.86)
+     *
+     * @return A 2-element array {p,q} of safe primes.
+     */
+    private static BigInteger[] generateSafePrimes(int size, int certainty, 
SecureRandom random) {
+        BigInteger p, q;
+        int qLength = size - 1;
+
+        while (true) {
+            q = new BigInteger(qLength, 2, random);
+
+            // p <- 2q + 1
+            p = q.shiftLeft(1).add(BigInteger.ONE);
+
+            // XXX(dold): why do we test q for primality again?
+            if (p.isProbablePrime(certainty) && (certainty <= 2 || 
q.isProbablePrime(certainty))) {
+                break;
+            }
+        }
+
+        return new BigInteger[]{p, q};
+    }
+
+    /*
+    * Select a high order element of the multiplicative group Zp*
+    *
+    * p and q must be s.t. p = 2*q + 1, where p and q are prime (see 
generateSafePrimes)
+    */
+    private static BigInteger selectGenerator(BigInteger p, BigInteger q, 
SecureRandom random) {
+        BigInteger g;
+        final BigInteger pMinusTwo = p.subtract(BigInteger.valueOf(2));
+        /*
+        * RFC 2631 2.2.1.2 (and see: Handbook of Applied Cryptography 4.81)
+        */
+        do {
+            BigInteger h = 
CryptoUtil.createRandomInRange(BigInteger.valueOf(2), pMinusTwo, random);
+            g = h.modPow(BigInteger.valueOf(2), p);
+        }
+        while (g.equals(BigInteger.ONE));
+
+        return g;
+    }
+
+    /**
+     * Get the size of the cyclic group Gp used for ElGamal
+     *
+     * @return the size of the cyclic group Gp used for ElGamal
+     */
+    public BigInteger getP() {
+        return p;
+    }
+
+    /**
+     * Get the generator of Zp*
+     * @return the generator of Zp*
+     */
+    public BigInteger getG() {
+        return g;
+    }
+
+    /**
+     * Compute g^x mod p.
+     *
+     */
+    public BigInteger pow(BigInteger exponent) {
+        return g.modPow(exponent, p);
+    }
+
+    public BigInteger mod(BigInteger x) {
+        return x.mod(p);
+    }
+
+}

Added: gnunet-java/src/org/gnunet/voting/VotingSimulation.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/VotingSimulation.java                     
        (rev 0)
+++ gnunet-java/src/org/gnunet/voting/VotingSimulation.java     2012-09-20 
09:38:15 UTC (rev 23905)
@@ -0,0 +1,121 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+import java.util.Random;
+
+public class VotingSimulation {
+
+    /**
+     * Evaluate a polynomial over Zp*.
+     *
+     * @param coeffs coefficients of the polynomial, where coeffs[i] is the 
coefficient of x^i
+     * @param x the polynomial is evaluated at this value
+     * @param p order or group Zp*
+     * @return the result of evaluating the polynomial at x
+     */
+    public static BigInteger evaluateHorner(BigInteger[] coeffs, BigInteger x, 
BigInteger p) {
+        BigInteger z = BigInteger.ZERO;
+        for (int i = coeffs.length - 1; i != 0; --i) {
+            z = coeffs[i].add(z.multiply(x).mod(p)).mod(p);
+        }
+        return z;
+    }
+
+    public static void main(String... args) {
+        final SecureRandom random = new SecureRandom();
+        final ElGamalParameters parameters = ElGamalParameters.generate(64, 
10, random);
+
+        final BigInteger p = parameters.getP();
+        final BigInteger g = parameters.getP();
+
+        final int authorityCount = 5;
+        final int k = 3;
+
+        BigInteger[] xParts = new BigInteger[authorityCount];
+        BigInteger[] hParts = new BigInteger[authorityCount];
+
+        BigInteger x = BigInteger.ZERO;
+        BigInteger h = BigInteger.ONE;
+
+        for (int j = 0; j < authorityCount; ++j) {
+            xParts[j] = CryptoUtil.createRandomInRange(BigInteger.ZERO, 
p.subtract(BigInteger.ONE), random);
+            hParts[j] = g.modPow(xParts[j], p);
+            x = x.add(xParts[j]);
+            h = h.multiply(hParts[j]);
+        }
+
+        if (!g.modPow(x, p).equals(h)) {
+            throw new AssertionError("math problem");
+        }
+
+
+        // f[j][i] is the coefficient of x^i for the polynomial of authority j.
+        BigInteger[][] f = new BigInteger[authorityCount][];
+        // checkF[j][i] = g^(f[j][i]) mod g
+        // used to check the share parts of each authority
+        BigInteger[][] checkF = new BigInteger[authorityCount][];
+
+        for (int j = 0; j < authorityCount; ++j) {
+            f[j] = new BigInteger[k];
+            f[j][0] = hParts[j];
+            checkF[j] = new BigInteger[k];
+            for (int i = 1; i < k; ++i) {
+                f[j][i] = CryptoUtil.createRandomInRange(BigInteger.ZERO, 
p.subtract(BigInteger.ONE), random);
+                checkF[j][i] = g.modPow(f[j][i], p);
+            }
+        }
+
+        // shareParts[j][i] is the polynomial f_j of authority j evaluated at i
+        // note that shareParts[j][0] is the private key part of authority j
+        BigInteger[][] shareParts = new BigInteger[authorityCount][];
+
+        for (int j = 0; j < authorityCount; ++j) {
+            shareParts[j] = new BigInteger[authorityCount];
+            for (int i = 0; i < authorityCount; ++i) {
+                shareParts[j][i] = evaluateHorner(f[j], BigInteger.valueOf(i), 
p);
+            }
+        }
+
+        // verification of the received shares: TODO (I can't read the formula 
in the paper)
+
+        BigInteger[] shares = new BigInteger[authorityCount];
+
+        // compute each authority's share as the sum of parts it received
+        for (int j = 0; j < authorityCount; j++) {
+            shares[j] = BigInteger.ZERO;
+            for (int i = 0; i < k; ++i) {
+                shares[j] = shares[j].add(shareParts[j][i]);
+            }
+        }
+
+        // now we do lagrange interpolation with all shares as points
+        BigInteger[] lagrangeBase = new BigInteger[authorityCount];
+        // we assume here that all authorities participate
+        for (int j = 0; j < authorityCount; ++j) {
+            BigInteger z = BigInteger.ONE;
+            for (int l = 0; l <= authorityCount; ++l) {
+                if (l == j) {
+                    break;
+                }
+                BigInteger n = BigInteger.valueOf(l);
+                BigInteger d = BigInteger.valueOf(l-j);
+                // todo: is this correct?
+                BigInteger dInv = d.modInverse(p);
+                z = z.multiply(n).multiply(dInv);
+            }
+            lagrangeBase[j] = z;
+        }
+
+        BigInteger xReconstructed = BigInteger.ZERO;
+        for (int j = 0; j < authorityCount; ++j) {
+            xReconstructed = 
xReconstructed.add(shares[j].multiply(lagrangeBase[j])).mod(g);
+        }
+
+        // todo: get this to work!
+
+        // todo: cooperative decryption
+        // todo: zero knowledge proof for key
+
+    }
+}
\ No newline at end of file