[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r24259 - in gnunet-java: . src/org/gnunet/util src/org/gnun
From: |
gnunet |
Subject: |
[GNUnet-SVN] r24259 - in gnunet-java: . src/org/gnunet/util src/org/gnunet/voting |
Date: |
Wed, 10 Oct 2012 23:31:53 +0200 |
Author: dold
Date: 2012-10-10 23:31:53 +0200 (Wed, 10 Oct 2012)
New Revision: 24259
Added:
gnunet-java/src/org/gnunet/voting/Authority.java
gnunet-java/src/org/gnunet/voting/Ballot.java
gnunet-java/src/org/gnunet/voting/FullPublicKey.java
gnunet-java/src/org/gnunet/voting/ShareVerification.java
gnunet-java/src/org/gnunet/voting/SpecializedKeyShare.java
gnunet-java/src/org/gnunet/voting/VotingAlgorithm.java
gnunet-java/src/org/gnunet/voting/VotingParameters.java
gnunet-java/src/org/gnunet/voting/VotingSimulation.java
Removed:
gnunet-java/src/org/gnunet/voting/ElGamalScheme.java
gnunet-java/src/org/gnunet/voting/VotingSimulation.java
Modified:
gnunet-java/ISSUES
gnunet-java/src/org/gnunet/util/Server.java
gnunet-java/src/org/gnunet/voting/CryptoUtil.java
Log:
more readable reimplementation of the voting simulation, arbitrary authorized
subgroups can decrypt the final tally
Modified: gnunet-java/ISSUES
===================================================================
--- gnunet-java/ISSUES 2012-10-10 19:33:49 UTC (rev 24258)
+++ gnunet-java/ISSUES 2012-10-10 21:31:53 UTC (rev 24259)
@@ -1,303 +1,38 @@
-in gnunet-java-ext there is a working example of a service and a corresponding
client program, that actually work ;)
- * simple greeting server, client gives name and server returns greeting
- * illustrates using program/service, using the configuration, creating
messages
- * works with os control pipe / arm (see below for problems with arm)
-RE: Great.
+* the voting protocol needs a broadcast channel with memory, mesh does not
really do this
+ * so the bulletin board is implemented by the authorities
-* i tried merging gnunet-testing and gunet-testing-run-service, but failed :(
- * gnunet-testing-run-service uses GNUNET_TESTING_service_run
- * which can't be run from within the main called by GNUNET_PROGRAM_run (as
the scheduler is already running)
- * so we can either run one or the other
- * but we have to parse arguments to decide which!
- * so what about the default arguments?
- * does it really make sense to merge them, functionality-wise?
+* in general, what are the necessary communication patterns?
+ * a clients asks all authorities to
+ * accept a vote
+ * show the election status
+ * hand out e.g. the one-purpose-key for encryption of the final tally
-RE: Hard to say; while there are ways to work around the problem you mention,
there is clearly
-no need for great hacks to force the merge; let's leave them separate. Maybe
rename gnunet-testing-run-service
-to gnunet-helper-testing-run-service to make clear that it is a "helper"
process and not something meant to be
-run by users from the command-line...
+questions:
+ * how do the authorities know the voter sent them the same votes?
+ * in a naive implementation, after only one vote, Theta(n^2) messages have
to be exchanged
+ * => probably have to exchange their information
+ * is it really necessary for the voter to check all authorities?
+=> how about a separate realization / abstraction of the bulletin board?
+ * the voter only has to query one authority (values should be signed by
multiple authorities)
+ * the voter only has to send her vote to one authority
+ * ... and it is thus less complex for the authorities to register the unique
vote
-arm-4477 WARNING Configuration file `(null)' for service `greeting' not valid:
option missing
-RE: you need an entry "CONFIG = $DEFAULTCONFIG" in [greeting] in your
greeting.conf[.in]
+* the implementation is (hopefully) much more readable by now
+ * suggestions?
-even when not using the signal pipe, does arm really kill processes?
- * arm does never seem to send a sigkill if process does not respond
- * sometimes arm command hangs!
+how does the process of voting work?
+ * a single party (the election initiator) should create the election, with a
description
+ * the initiator creates certificates that allows someone to act as an
authority
+ * generally, we don't want just anybody to be able to be a authority, as one
could just contribute enough authorities
+ to break the threshold
+ * the initiator creates certificates for the voters
+ * what are use-cases where this does not work?
+ * when has an election ended? a point in time?
-RE: ARM waits for the child to terminate, this would seem like hanging; when
not using a signal pipe,
-ARM will send a POSIX signal and then do "wait". What happens is then up to
the child...
-
- $ gnunet-arm -c config/greeting.conf -k greeting -LDEBUG
- Aug 29 19:25:22-808046 arm-api-5971 INFO Stopping service `greeting' within
60000 ms
- Service `greeting' was already not running.
-
-RE: might relate to the 'CONFIG' option missing above...
-
-Aug 29 18:21:19-505909 arm-4751 ERROR Failed to start service `greeting'
-Service `greeting' has been started.
-
-RE: Again, this might relate to the 'CONFIG' option missing above, but is the
inconsistency of
-the messages given is certainly a bit odd. Should be investigated.
-
-logging with arm: what gets piped to where
- * seems like service stdout->/dev/null, service stderr->arm stderr
-
-RE: stdout should never be used by services, especially not for logging; where
'stderr' goes (logfile, arm's stderr)
-depends on the configuration;
-
-
-Construct: has gotten very complex, i'm currently trying to trace a particular
bug
- * UPDATE: bug is gone!
- * unit tests for construct have gotten better, still not good enough
- * FrameSize
- * recursive messages
- * indirect recursion (over unions) (see core.SendMessage) works
- * direct recursion has problems (see test/org.gnunet.construct.FrameSizeTest)
-
-Question: Is all this too complicated? Should I invest the time to fix things
as they are now intended, or should
-we simplify?
-
-RE: How would you simplify it? I don't recall us having significant
unwanted/unnecessary functionality, do we?
-
-
-* found some problems with timeouts in client/connection.
- * should i write unit-tests for this timing-stuff?
- * UPDATE: should be fixed now!
-
-* program/service in general:
- * how to handle the return value of main?
- * java has no return value for main
- * we must use System.exit(n) instead
- * how about a (Program/Service).exit(n) that does cleanup and then calls
System.exit(n)?
-
-RE: the user writes a 'main' function which (usually indirectly via
program/service) invokes the
- scheduler; after that invocation returns to 'main', 'main' should call
System.exit(RV). I don't
- see a need to integrate this call with org.gnunet.util.
-
-* configuration: what is $DEFAULTCONFIG? and CONFIG=?
-
-RE: it is possible to pass a custom configuration file for one of the
services, instead of using the
-same configuration file for all services; rarely used feature. $DEFAULTCONFIG
== "this config".
-
-
-mesh:
- * we can't use multipe instances of org.gnunet.mesh.Mesh to test the API
- * the local peer can't be the peer on the other end!
-RE: why not? C tests do this AFAIK.
- * the C-api has practically no coverage on mesh_api.c
-RE: don't understand
- * see below for a suggestion!
- * LOCAL_TUNNEL_CREATE was used for two things, creating tunnels and being
notified about incoming tunnels
-RE: that sounds, eh, not great... => check with Bart?
-
-* extending org.gnunet.testing so that multiple peers can be started and
communicate with each other!
- * the C-testing-api allows to create multiple peers, but they don't seem to
be able to communicate with each
- other!
-RE: Matthias said that transport was having trouble again these days...
- * => the peers should somehow exchange their hellos / use a shared directory
for the hellos
-RE: yes, you'll need transport API implementations to call 'try_connect' and
to get and exchange HELLOs
-
- testbed vs testing: is this correct?
- * testbed for large-scale testing across many "real" nodes
- * testing for testcases on one host
-RE: Almost right; testing is a little helper library for testbed, useful for
small-scale tests with
- simple setups; testbed is for multi-host deployments AND for more complex
single-host setups
- (specific network topologies, etc.)
-
-* test coverage approaching a better state, any feedback?
-RE: buildbot integration to run against C SVN HEAD would be nice to have...
-
-* I think there should be some documentation in addition to the source code
and the tutorial
- * what would be the preferred format for such documentation? latex?
-RE: JavaDoc for API documentation; HTML on website for code overview-level
stuff, LaTeX for
- tutorial; we might also write something more like a paper in LaTeX at some
point, but
- I'm not sure about that yet;
- * (considering that they perhaps should end up on a website / should be
browsable)
- * examples:
- * how do unions work in construct?
-RE: JavaDoc and a webpage on Construct in HTML
- * other stuff in construct
-RE: => webpage on Construct in HTML
- * how does annotation processing work?
-RE: => sub-section in webpage on gnunet-java build system
- * project layout - what goes where
- * as there is no standard java project layout
-RE: => code overview chapter in webpage on gnunet-java
-
-
-rationale for putting org.gnunet.testing in the src/-tree, not in test/:
- * when developing an extension for gnunet-java, the developers may want to
access the testing functionality from
- the jar, so it should be included there!
- * the code itself is tested, we want coverage etc.
-RE: both are good reasons.
-
-* is there an effort to document what hostkeys files are etc.?
-RE: not yet, might not be a bad idea; do you want to write something? :-)
-
-continuous integration: using Jenkins (=Hudson, forked away from Oracle)
- * easier to configure than buildbot
- * support for displaying JUnit reports out-of-the-box
- * support for cobertura via plugin
- * but not very stable
-RE: is that a suggestion or something you already finished? If not finished,
did you try it? (just asking...)
-
-for junit reports we need ant/gradle!
-RE: I saw the gradle build file.
-
-build system: still maintaining bash scripts, trying out gradle
- * faster builds, build scripts far easier to read/write
- * no built-in integration with cobertura :(
- * main reason the build script is not finished
- * gradle has excellent Ant integration => Coverage (bash wrapper not very
usable)
- * can generate project files for eclipse/intellij
- * would make stuff like installing gnunet-java from source easier than using
izpack
-RE: As the gradle config is trivial, no harm in *also* having it; not sure
about
- obsoleting izpack (as izpack is the template for an installer for
end-users,
- not for eclipse integration...); maintaining two build systems (one for
cobertura,
- one for ant/eclipse/junit/jenkins?) might be OK, but of course is not
ideal.
-
-what's next?
- * some actual stuff built with gnunet-java?
-RE: Yes. Krista is supposed to e-mail you some papers to read, then we'll
decide on some fun protocol to implement!
-
-
-* general question: when should an api use per-connection receive, and
per-service-receive?
-RE: I don't understand the question.
-
-does this make sense / do we need it:
- * support in the scheduler for communicating asynchronously with other
processes via stdin/stdout/stderr
-RE: see util's helper API in C -- that's where we do use this; so _eventually_
we might want this.
- * currently only used in testing, uses blocking i/o
-RE: blocking IO is always deadly eventually; so we should probably add async
IO for pipes to Java scheduler
-
-* stream is implemented as a library, not as a service
- * why?
-RE: various reasons, performance, KISS, statelessness of a stream, ...
- * should GNUnet-java also implement it?
-RE: maybe, but certainly not yet, stream is still to experimental anyway
-
-
-------------------------------------------------------------------------------------------------------
-
-* build system: the gradle build script now works with cobertura!
- * test reports like these: https://gnunet.org/cobertura/tests/
- * (so many tests failed because the gnunet installation on cobertura has
some problem right now!)
-
-
-* while I'm still confused with all the details, I somewhat see where to start
implementing it with GNUnet
- * "posting" / the "bulletin board" sounds a lot like the DHT
- * I remember you talking about librarys for SMC which are only available for
java. which are these?
-
-* sometimes it would be nice to get the log of a service when testing it
- * there was a wrong comment in mesh.h regarding the size of application types
=> failed assertion would be useful
- * eventually started service manually (with gnunet-testing-run-service) and
supplied temporary config file to test case
- * not very nice
- * do you have any ideas on how to realize this?
- * probably easiest to direct log to file
-
-
-* why does mesh_api.c use data structures from mesh_protocol.h? why are fields
like ttl involved? (mesh_api.c:1366)
-
-* occurred during testing (at first i thought it was my fault / a bug in
gnunet-java):
- * when connecting a client to the tunnel with connect_by_type the owner of
the tunnel gets notified
- * but the client who is added does *not* get a inbound tunnel notification
- * ... until someone sends a message to him. this is nowhere documented.
-
-* sending/receiving in mesh is kind of complicated (ACKs / windows)
- * why is there the need for three different kinds of messages for traffic?
- * to oritin
- * unicast
- * multicast
- * why does the packet id have to be set in these messages?
-
-* does the RootTunnel extends Tunnel hierarchy make sense?
-
-=> there is a lot of "bad stuff" in mesh
-(the comments and code talk about completely different stuff, see e.g. mesh.h)
-
-i really wanted to make more progress but working with mesh is *absolutely*
frustrating!
-
-* regarding arm:
- * I understand that it's not wise to kill non-cooperating services after a
timeout
- * but shouldn't arm respond to CTRL+C in those cases? bug? intentional /
related to signal handling?
-
-
--------------------------------------------------------
-
-* gradle build script
- * now handles the "instrument" task correctly
- * can run the annotation processor ("msgtypes")
- * => should we keep/maintain the old build scripts or not?
-
-=> "gradle tasks" produces ConcurrentModificationException
-
-
-* http://docs.oracle.com/javase/1.4.2/docs/api/java/nio/channels/Pipe.html
- * "Many pipe implementations will buffer up to a certain number of bytes
between the sink and source channels"
- * reminds me of matthias' problems last monday. what to do about it?
- * i tried working with a small buffer in the call to read(...)
-
-
-* while revisiting the config API
- * 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)
-
-
---------------------------------------------------------
-
-* voting.tex
- * i learned a lot of latex, and a lot the math while writing this
- * should we keep it?
-
-* key distribution (including verification of shares) implemented
-* key can be correctly recovered from the shares
-* cooperative decryption implemented
-* first zero knowledge proof implemented
- * what kind of hash should I use for making the ZK-proofs non-interactive?
-
-* what generator should be used for voting? G=g?
- * can a cyclic group even have more than one generator? don't they mean
high-order element?
-
-* what makes more sense: passing the RNG handle explicitly every time, or
storing it in e.G. ElGamalScheme?
-
-
-* what about the 10138: DP: Use doPrivileged in runabout?
\ No newline at end of file
+one realistic use case of electronic voting would be the german e-petition
https://epetitionen.bundestag.de/
\ No newline at end of file
Modified: gnunet-java/src/org/gnunet/util/Server.java
===================================================================
--- gnunet-java/src/org/gnunet/util/Server.java 2012-10-10 19:33:49 UTC (rev
24258)
+++ gnunet-java/src/org/gnunet/util/Server.java 2012-10-10 21:31:53 UTC (rev
24259)
@@ -508,7 +508,7 @@
}
@Override
- public void finalize() throws Throwable {
+ protected void finalize() throws Throwable {
super.finalize();
if (!destroyed) {
logger.warn("Server instance not destroyed, but finalizer called");
Added: gnunet-java/src/org/gnunet/voting/Authority.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/Authority.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/Authority.java 2012-10-10 21:31:53 UTC
(rev 24259)
@@ -0,0 +1,78 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+
+/**
+ * ...
+ *
+ * @author Florian Dold
+ */
+public class Authority {
+ private final BigInteger privateKeyShare;
+ private final BigInteger[] secretPolynomial;
+ private final ShareVerification shareVerification;
+
+ private final int authorityId;
+
+ private BigInteger receivedShare;
+
+ private VotingParameters parameters;
+
+ public Authority(int authorityId, VotingParameters parameters) {
+ this.authorityId = authorityId;
+ this.parameters = parameters;
+ this.privateKeyShare = parameters.generateZq();
+ this.secretPolynomial = new BigInteger[parameters.authorityThreshold];
+
+ this.secretPolynomial[0] = privateKeyShare;
+ for (int i = 1; i < parameters.authorityThreshold; ++i) {
+ secretPolynomial[i] = parameters.generateZq();
+ }
+
+ shareVerification = new ShareVerification(secretPolynomial,
parameters);
+
+ receivedShare = BigInteger.ZERO;
+ }
+
+ public BigInteger getPublicKeyShare() {
+ return parameters.g.modPow(privateKeyShare, parameters.p);
+ }
+
+ public ShareVerification getShareVerification() {
+ return shareVerification;
+ }
+
+ public BigInteger createShareForAuthority(int j) {
+ return CryptoUtil.evaluatePolynomial(secretPolynomial,
BigInteger.valueOf(j+1), parameters.q);
+ }
+
+ public void verifyShare(BigInteger distributionShare, ShareVerification
senderVerification) {
+ BigInteger v = parameters.g.modPow(distributionShare, parameters.p);
+ BigInteger prod = BigInteger.ONE;
+ for (int l = 0; l < parameters.authorityThreshold; ++l) {
+ BigInteger exp = BigInteger.valueOf(this.getId()).pow(l);
+ BigInteger coeff = senderVerification.coeffs[l];
+ prod = prod.multiply(coeff.modPow(exp,
parameters.p)).mod(parameters.p);
+ }
+ if (!v.equals(prod)) {
+ throw new AssertionError("verification of transmitted shared
failed");
+ }
+ }
+
+ public void receiveShareFromAuthority(BigInteger distributionShare,
ShareVerification senderVerification) {
+ verifyShare(distributionShare, senderVerification);
+ receivedShare = receivedShare.add(distributionShare);
+ }
+
+ public int getId() {
+ return authorityId;
+ }
+
+ public SpecializedKeyShare generateSpecializedKeyShare(Cyphertext
encryptedTally) {
+ return new SpecializedKeyShare(encryptedTally.c1, receivedShare,
parameters);
+ }
+
+ public BigInteger getSigma() {
+ return parameters.g.modPow(receivedShare, parameters.p);
+ }
+}
Added: gnunet-java/src/org/gnunet/voting/Ballot.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/Ballot.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/Ballot.java 2012-10-10 21:31:53 UTC
(rev 24259)
@@ -0,0 +1,106 @@
+package org.gnunet.voting;
+
+import com.google.common.base.Objects;
+
+import java.math.BigInteger;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+
+/**
+ * ...
+ *
+ * @author Florian Dold
+ */
+public class Ballot {
+ public final BigInteger voterId;
+
+ // the ElGamal encryption of the vote
+ public final BigInteger x, y;
+ // values for the zero knowledge proof
+ public final BigInteger a_1, b_1, a_2, b_2, r_1, d_1, r_2, d_2, c;
+ private VotingParameters parameters;
+
+
+ public Ballot(boolean v, BigInteger voterId, FullPublicKey fullPublicKey,
VotingParameters parameters) {
+ this.voterId = voterId;
+ this.parameters = parameters;
+
+ BigInteger g = parameters.g;
+ BigInteger p = parameters.p;
+ BigInteger h = fullPublicKey.getKey();
+
+
+ if (v) {
+ BigInteger alpha = parameters.generateZq();
+ BigInteger w = parameters.generateZq();
+ r_1 = parameters.generateZq();
+ d_1 = parameters.generateZq();
+
+ x = g.modPow(alpha, p);
+ y = h.modPow(alpha, p).multiply(g).mod(p);
+
+ a_1 = g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p);
+ b_1 = h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p);
+ a_2 = g.modPow(w, p);
+ b_2 = h.modPow(w, p);
+
+
+ c = CryptoUtil.hash(voterId, x, y, a_1, b_1, a_2,
b_2).mod(parameters.q);
+
+ // prover
+ d_2 = c.subtract(d_1);
+ r_2 = w.subtract(alpha.multiply(d_2));
+ } else {
+ // prover
+ BigInteger alpha = parameters.generateZq();
+ BigInteger w = parameters.generateZq();
+ r_2 = parameters.generateZq();
+ d_2 = parameters.generateZq();
+
+ x = g.modPow(alpha, p);
+ y = h.modPow(alpha, p).multiply(g.modInverse(p)).mod(p);
+
+ a_1 = g.modPow(w, p);
+ b_1 = h.modPow(w, p);
+ a_2 = g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p);
+ b_2 = h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p);
+
+
+ c = CryptoUtil.hash(voterId, x, y, a_1, b_1, a_2,
b_2).mod(parameters.q);
+
+ // prover
+ d_1 = c.subtract(d_2);
+ r_1 = w.subtract(alpha.multiply(d_1));
+ }
+ }
+
+ public void verify(FullPublicKey fullPublicKey) {
+ BigInteger g = parameters.g;
+ BigInteger p = parameters.p;
+ BigInteger h = fullPublicKey.getKey();
+ // verifier
+
+
+ if (!c.equals(CryptoUtil.hash(voterId, x, y, a_1, b_1, a_2,
b_2).mod(parameters.q))) {
+ throw new AssertionError();
+ }
+
+ if (!c.equals(d_1.add(d_2).mod(p))) {
+ throw new AssertionError();
+ }
+ if (!a_1.equals(g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p))) {
+ throw new AssertionError();
+ }
+ if (!b_1.equals(h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p))) {
+ throw new AssertionError();
+ }
+
+ if (!a_2.equals(g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p))) {
+ throw new AssertionError();
+ }
+
+ if (!b_2.equals(h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p))) {
+ throw new AssertionError();
+ }
+ }
+}
Modified: gnunet-java/src/org/gnunet/voting/CryptoUtil.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/CryptoUtil.java 2012-10-10 19:33:49 UTC
(rev 24258)
+++ gnunet-java/src/org/gnunet/voting/CryptoUtil.java 2012-10-10 21:31:53 UTC
(rev 24259)
@@ -1,6 +1,8 @@
package org.gnunet.voting;
import java.math.BigInteger;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
import java.security.SecureRandom;
import java.util.Random;
@@ -10,17 +12,18 @@
* @author Florian Dold
*/
public class CryptoUtil {
+ public static final Random random = new Random();
+
+
/**
* Return a random BigInteger not less than 'min' and not greater than
'max' with uniform distribution.
*
* @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,
- Random random) {
+ BigInteger max) {
int cmp = min.compareTo(max);
if (cmp >= 0) {
if (cmp > 0) {
@@ -31,7 +34,7 @@
}
if (min.bitLength() > max.bitLength() / 2) {
- return createRandomInRange(BigInteger.ZERO, max.subtract(min),
random).add(min);
+ return createRandomInRange(BigInteger.ZERO,
max.subtract(min)).add(min);
}
for (int i = 0; i < 1000; ++i) {
@@ -46,4 +49,38 @@
return new BigInteger(max.subtract(min).bitLength() - 1,
random).add(min);
}
+
+
+ /**
+ * Evaluate a polynomial over Zp*. Uses Horner's scheme.
+ *
+ * @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 what group are we operating in?
+ * @return the result of evaluating the polynomial at x
+ */
+ public static BigInteger evaluatePolynomial(BigInteger[] coeffs,
BigInteger x, BigInteger p) {
+ BigInteger z = BigInteger.ZERO;
+ for (int i = 0; i < coeffs.length; ++i) {
+ // z <- zx + c
+ z = z.multiply(x).add(coeffs[coeffs.length - i - 1]);
+ }
+ return z;
+ }
+
+ public static BigInteger hash(BigInteger... x) {
+ MessageDigest md;
+ try {
+ md = MessageDigest.getInstance("SHA-512");
+ } catch (NoSuchAlgorithmException e) {
+ throw new RuntimeException("no SHA-512 available");
+ }
+
+ for (BigInteger v : x) {
+ md.update(v.toByteArray());
+ }
+
+ return new BigInteger(md.digest());
+ }
+
}
Deleted: gnunet-java/src/org/gnunet/voting/ElGamalScheme.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/ElGamalScheme.java 2012-10-10
19:33:49 UTC (rev 24258)
+++ gnunet-java/src/org/gnunet/voting/ElGamalScheme.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -1,163 +0,0 @@
-package org.gnunet.voting;
-
-import java.math.BigInteger;
-import java.security.SecureRandom;
-import java.util.Random;
-
-/**
- * Utilities the modified ElGamal algorithms.
- * <p/>
- * p is a large prime, and g is a high-order element (or even a generator) of
Zp*
- *
- * @author Florian Dold
- */
-public class ElGamalScheme {
- // large prime, p = 2q + 1
- private final BigInteger p;
- // large prime, so that q divides (p-1)
- private final BigInteger q;
- // generator of Gq
- private final BigInteger g;
-
- public ElGamalScheme(BigInteger p, BigInteger q, BigInteger g) {
- this.p = p;
- this.q = q;
- this.g = g;
- }
-
- /**
- * which generates the p and g values from the given parameters,
- * returning the ElGamalScheme object.
- * <p/>
- * Note: can take a while...
- */
- public static ElGamalScheme generateRandomParameters(int size, int
certainty, Random random) {
- BigInteger[] safePrimes = generateSafePrimes(size, certainty, random);
-
- BigInteger p = safePrimes[0];
- BigInteger q = safePrimes[1];
- BigInteger alpha = selectGenerator(p, q, random);
- BigInteger g = selectSubgroupHigherOrderElement(alpha, p, q);
- if (!g.modPow(q, p).equals(BigInteger.ONE)) {
- throw new AssertionError();
- }
- return new ElGamalScheme(p, q, g);
- }
-
- /**
- * Finds a pair of prime BigInteger's {p, q: p = 2q + 1}, called safe
primes.
- * <p/>
- * (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,
Random 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 Zn*
- */
- private static BigInteger selectHighOrderElement(BigInteger n,
SecureRandom random) {
- BigInteger g;
- final BigInteger nMinusTwo = n.subtract(BigInteger.valueOf(2));
- do {
- BigInteger h =
CryptoUtil.createRandomInRange(BigInteger.valueOf(2), nMinusTwo, random);
-
- g = h.modPow(BigInteger.valueOf(2), n);
- }
- while (g.equals(BigInteger.valueOf(1)));
-
- return g;
- }
-
- /**
- * Returns a higher-order-element of Gq, the subgroup of Zp*, with order q
where alpha is a generator of Zp*
- *
- * (see Handbook of Applied Cryptography 4.81)
- */
- private static BigInteger selectSubgroupHigherOrderElement(BigInteger
alpha, BigInteger p, BigInteger q) {
- return alpha.modPow(p.subtract(BigInteger.ONE).divide(q), p);
- }
-
- /**
- * 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 Gq
- *
- * @return the generator of Gq
- */
- public BigInteger getG() {
- return g;
- }
-
- /**
- * Get the generator of Zp*
- *
- * @return the generator of Zp*
- */
- public BigInteger getQ() {
- return q;
- }
-
- public BigInteger generateGq(Random random) {
- BigInteger r;
- while (true) {
- r = CryptoUtil.createRandomInRange(BigInteger.ZERO, this.p,
random);
- if (r.modPow(q, p).equals(BigInteger.ONE)) {
- break;
- }
- }
- return r;
- }
-
- public static BigInteger selectGenerator(BigInteger p, BigInteger q,
Random random) {
- BigInteger pMinusTwo = p.subtract(BigInteger.valueOf(2));
- BigInteger g;
- /*
- * (see: Handbook of Applied Cryptography 4.80)
- */
- do {
- g = CryptoUtil.createRandomInRange(BigInteger.valueOf(2),
pMinusTwo, random);
- }
- while (g.modPow(BigInteger.valueOf(2), p).equals(BigInteger.ONE) ||
g.modPow(q, p).equals(BigInteger.ONE));
- return g;
- }
-
- public BigInteger generateZp(Random random) {
- return CryptoUtil.createRandomInRange(BigInteger.ZERO,
this.p.subtract(BigInteger.ONE), random);
- }
-
- public BigInteger generateZq(Random random) {
- return CryptoUtil.createRandomInRange(BigInteger.ZERO,
this.q.subtract(BigInteger.ONE), random);
- }
-
- public Cyphertext encrypt(BigInteger message, BigInteger pubKey, Random
random) {
- BigInteger secret = generateZq(random);
- return new Cyphertext(g.modPow(secret, p),
message.multiply(pubKey.modPow(secret, p).mod(p)));
- }
-
-
-}
Added: gnunet-java/src/org/gnunet/voting/FullPublicKey.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/FullPublicKey.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/FullPublicKey.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -0,0 +1,24 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+
+/**
+ * ...
+ *
+ * @author Florian Dold
+ */
+public class FullPublicKey {
+ final BigInteger key;
+
+ public FullPublicKey(Authority[] authorities, VotingParameters parameters)
{
+ BigInteger h = BigInteger.ONE;
+ for (Authority authority : authorities) {
+ h = h.multiply(authority.getPublicKeyShare()).mod(parameters.p);
+ }
+ key = h;
+ }
+
+ public BigInteger getKey() {
+ return key;
+ }
+}
Added: gnunet-java/src/org/gnunet/voting/ShareVerification.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/ShareVerification.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/ShareVerification.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -0,0 +1,18 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+
+/**
+ * ...
+ *
+ * @author Florian Dold
+ */
+public class ShareVerification {
+ public final BigInteger[] coeffs;
+ public ShareVerification(BigInteger[] secretPolynomial, VotingParameters
parameters) {
+ coeffs = new BigInteger[secretPolynomial.length];
+ for (int i = 0; i < secretPolynomial.length; ++i) {
+ coeffs[i] = parameters.g.modPow(secretPolynomial[i], parameters.p);
+ }
+ }
+}
Added: gnunet-java/src/org/gnunet/voting/SpecializedKeyShare.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/SpecializedKeyShare.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/SpecializedKeyShare.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -0,0 +1,58 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+
+/**
+ * ...
+ *
+ * @author Florian Dold
+ */
+public class SpecializedKeyShare {
+ final public BigInteger specializedShare;
+
+ final public BigInteger c1;
+ final public BigInteger a, b, c, r;
+
+ final VotingParameters parameters;
+
+ public SpecializedKeyShare(BigInteger c1, BigInteger share,
VotingParameters parameters) {
+ this.parameters = parameters;
+ this.c1 = c1;
+
+ specializedShare = c1.modPow(share, parameters.p);
+
+ BigInteger p = parameters.p;
+ BigInteger g = parameters.g;
+
+ // prover
+ BigInteger beta = parameters.generateZq();
+ a = g.modPow(beta, p);
+ b = c1.modPow(beta, p);
+ // verifier
+ c = CryptoUtil.hash(a, b);
+ // prover
+ r = beta.add(share.multiply(c));
+ }
+
+ /*
+ * Sigma is the the authority's commitment to its share
+ */
+ public void verify(BigInteger sigma) {
+ BigInteger p = parameters.p;
+ BigInteger g = parameters.g;
+
+ // verifier
+ BigInteger expected1 = g.modPow(r, p);
+ BigInteger received1 = a.multiply(sigma.modPow(c, p)).mod(p);
+
+ BigInteger expected2 = c1.modPow(r, p);
+ BigInteger received2 = b.multiply(specializedShare.modPow(c,
p)).mod(p);
+
+ if ((!expected1.equals(received1)) || (!expected2.equals(received2))) {
+ System.err.println(expected1);
+ System.err.println(received1);
+ throw new AssertionError("zero knowledge proof for decryption
failed");
+ }
+ }
+}
+
Copied: gnunet-java/src/org/gnunet/voting/VotingAlgorithm.java (from rev 24168,
gnunet-java/src/org/gnunet/voting/VotingSimulation.java)
===================================================================
--- gnunet-java/src/org/gnunet/voting/VotingAlgorithm.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/VotingAlgorithm.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -0,0 +1,323 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+import java.util.Random;
+
+public class VotingAlgorithm {
+
+
+ public static void main(String... args) {
+ final int authorityCount = 10;
+ // minimum required number of cooperating authorities
+ final int k = 6;
+ final VotingParameters parameters =
VotingParameters.generateRandomParameters(64, 10, authorityCount, k);
+
+ final BigInteger p = parameters.getP();
+ final BigInteger q = parameters.getQ();
+ final BigInteger g = parameters.getG();
+
+ if (!(g.compareTo(p) < 0)) {
+ throw new AssertionError();
+ }
+
+
+
+ // parts of the private key x, one part for each authority
+ BigInteger[] xParts = new BigInteger[authorityCount];
+ // The full private key, sum of the parts. Initialized with the
additive identity.
+ BigInteger x = BigInteger.ZERO;
+
+ // parts of the public key h, one part for each authority
+ BigInteger[] hParts = new BigInteger[authorityCount];
+ // The full public key, product of the parts. Initialized with the
multiplicative identity.
+ BigInteger h = BigInteger.ONE;
+
+ for (int j = 0; j < authorityCount; ++j) {
+ xParts[j] = parameters.generateZq();
+ hParts[j] = g.modPow(xParts[j], p);
+ x = x.add(xParts[j]).mod(q);
+ h = h.multiply(hParts[j]).mod(p);
+ }
+
+ 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-1.
+ BigInteger[][] f = new BigInteger[authorityCount][];
+ // checkF[j][i] = g^(f[j][i]) mod p
+ // used to check the share parts of each authority
+ BigInteger[][] checkF = new BigInteger[authorityCount][];
+
+ // generate the random polynomials
+ for (int j = 0; j < authorityCount; ++j) {
+ f[j] = new BigInteger[k];
+ checkF[j] = new BigInteger[k];
+ for (int i = 1; i < k; ++i) {
+ f[j][i] = parameters.generateZq();
+ checkF[j][i] = g.modPow(f[j][i], p);
+ }
+ f[j][0] = xParts[j];
+ checkF[j][0] = g.modPow(f[j][0], 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][];
+
+
+ // create the transmitted shared by evaluation the polynomials
+ for (int j = 0; j < authorityCount; ++j) {
+ shareParts[j] = new BigInteger[authorityCount];
+ for (int i = 0; i < authorityCount; ++i) {
+ shareParts[j][i] = CryptoUtil.evaluatePolynomial(f[j],
BigInteger.valueOf(i + 1), q);
+ }
+ }
+
+
+ // verification of the received shares:
+ for (int j = 0; j < authorityCount; ++j) {
+ // P_j verifies that the shares he received are valid
+ for (int i = 0; i < authorityCount; ++i) {
+ BigInteger v = g.modPow(shareParts[i][j], p);
+ BigInteger prod = BigInteger.ONE;
+ for (int l = 0; l < k; ++l) {
+ BigInteger exp = BigInteger.valueOf(j+1).pow(l);
+ prod = prod.multiply(checkF[i][l].modPow(exp, p)).mod(p);
+ }
+ if (!v.equals(prod)) {
+ throw new AssertionError("verification of transmitted
shared failed");
+ }
+ }
+ }
+
+
+
+
+ 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 < authorityCount; ++i) {
+ shares[j] = shares[j].add(shareParts[i][j]);
+ }
+ }
+
+
+ BigInteger[] lagrangeBase = new BigInteger[k];
+ for (int j = 1; j <= k; ++j) {
+ BigInteger n = BigInteger.ONE;
+ BigInteger d = BigInteger.ONE;
+ for (int l = 1; l <= k; ++l) {
+ if (l == j) {
+ continue;
+ }
+ n = n.multiply(BigInteger.valueOf(l));
+ d =
d.multiply(BigInteger.valueOf(l).subtract(BigInteger.valueOf(j)));
+ }
+ lagrangeBase[j-1] = n.multiply(d.modInverse(q)).mod(q);
+ }
+
+ BigInteger xReconstructed = BigInteger.ZERO;
+ for (int j = 0; j < k; ++j) {
+ xReconstructed =
xReconstructed.add(shares[j].multiply(lagrangeBase[j])).mod(q);
+ }
+
+ //System.out.println(xReconstructed);
+ //System.out.println(x);
+
+ if (!g.modPow(xReconstructed, p).equals(h)) {
+ throw new AssertionError("key reconstruction failed");
+ }
+
+
+ BigInteger message = parameters.generateGq();
+ Cyphertext cyphertext = parameters.encrypt(message, h);
+ BigInteger[] w = new BigInteger[k];
+ for (int i = 0; i < k; ++i) {
+ w[i] = cyphertext.c1.modPow(shares[i], p);
+ }
+
+
+ // zero knowledge proof
+ for (int i = 0; i < k; ++i) {
+ // sigma is made public
+ BigInteger sigma = g.modPow(shares[i], p);
+ // prover
+ BigInteger beta = parameters.generateZq();
+ BigInteger a = g.modPow(beta, p);
+ BigInteger b = cyphertext.c1.modPow(beta, p);
+ // verifier
+ BigInteger c = parameters.generateZq();
+ // prover
+ BigInteger r = beta.add(shares[i].multiply(c));
+ // verifier
+ BigInteger expected1 = g.modPow(r, p);
+ BigInteger received1 = a.multiply(sigma.modPow(c, p)).mod(p);
+
+ BigInteger expected2 = cyphertext.c1.modPow(r, p);
+ BigInteger received2 = b.multiply(w[i].modPow(c, p)).mod(p);
+
+ if ((!expected1.equals(received1)) ||
(!expected2.equals(received2))) {
+ System.err.println(expected1);
+ System.err.println(received1);
+ throw new AssertionError("zero knowledge proof for decryption
failed");
+ }
+ }
+
+ BigInteger messageRestored = cyphertext.c2;
+
+ for (int i = 0; i < k; ++i) {
+ BigInteger v = w[i].modPow(lagrangeBase[i], p);
+ messageRestored = messageRestored.multiply(v.modInverse(p)).mod(p);
+ }
+
+ if (!message.equals(messageRestored)) {
+ throw new AssertionError("decryption failed");
+ }
+
+
+ simulateBallotZKP1(h, parameters);
+ simulateBallotZKP2(h, parameters);
+
+ final int voteCount = 25;
+ int result = 0;
+
+ Cyphertext votes[] = new Cyphertext[voteCount];
+ for (int i = 0; i < voteCount; ++i) {
+ if (CryptoUtil.random.nextBoolean()) {
+ votes[i] = parameters.encrypt(g, h);
+ result++;
+ } else {
+ votes[i] = parameters.encrypt(g.modInverse(p), h);
+ result--;
+ }
+ }
+
+ BigInteger votesX = BigInteger.ONE;
+ BigInteger votesY = BigInteger.ONE;
+ for (int i = 0; i < voteCount; ++i) {
+ votesX = votesX.multiply(votes[i].c1).mod(p);
+ votesY = votesY.multiply(votes[i].c2).mod(p);
+ }
+
+ // for convenice decrypted with the full private key, the above tests
demonstrates that this
+ // is equally possible without revealing the private key
+ BigInteger resultG = votesY.multiply(votesX.modPow(x,
p).modInverse(p)).mod(p);
+ int resultRestored = 0;
+ boolean success = false;
+
+ for (int l = -voteCount; l <= voteCount; ++l) {
+ if (resultG.equals(g.modPow(BigInteger.valueOf(l), p))) {
+ success = true;
+ resultRestored = l;
+ break;
+ }
+ }
+
+ if (!success) {
+ throw new AssertionError();
+ }
+
+ if (resultRestored != result) {
+ throw new AssertionError();
+ }
+ }
+
+ public static void simulateBallotZKP1(BigInteger h, VotingParameters
parameters) {
+ final BigInteger p = parameters.getP();
+ final BigInteger q = parameters.getQ();
+ final BigInteger g = parameters.getG();
+
+ // prover
+ BigInteger alpha = parameters.generateZq();
+ BigInteger w = parameters.generateZq();
+ BigInteger r_1 = parameters.generateZq();
+ BigInteger d_1 = parameters.generateZq();
+
+ BigInteger x = g.modPow(alpha, p);
+ BigInteger y = h.modPow(alpha, p).multiply(g).mod(p);
+
+ BigInteger a_1 = g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p);
+ BigInteger b_1 = h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p);
+ BigInteger a_2 = g.modPow(w, p);
+ BigInteger b_2 = h.modPow(w, p);
+
+ // verifier
+ BigInteger c = parameters.generateZq();
+
+ // prover
+ BigInteger d_2 = c.subtract(d_1);
+ BigInteger r_2 = w.subtract(alpha.multiply(d_2));
+
+ // verifier
+ if (!c.equals(d_1.add(d_2).mod(p))) {
+ throw new AssertionError();
+ }
+ if (!a_1.equals(g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p))) {
+ throw new AssertionError();
+ }
+ if (!b_1.equals(h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p))) {
+ throw new AssertionError();
+ }
+
+ if (!a_2.equals(g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p))) {
+ throw new AssertionError();
+ }
+
+ if (!b_2.equals(h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p))) {
+ throw new AssertionError();
+ }
+ }
+
+
+ public static void simulateBallotZKP2(BigInteger h, VotingParameters
parameters) {
+ final BigInteger p = parameters.getP();
+ final BigInteger q = parameters.getQ();
+ final BigInteger g = parameters.getG();
+
+ // prover
+ BigInteger alpha = parameters.generateZq();
+ BigInteger w = parameters.generateZq();
+ BigInteger r_2 = parameters.generateZq();
+ BigInteger d_2 = parameters.generateZq();
+
+ BigInteger x = g.modPow(alpha, p);
+ BigInteger y = h.modPow(alpha, p).multiply(g.modInverse(p)).mod(p);
+
+ BigInteger a_1 = g.modPow(w, p);
+ BigInteger b_1 = h.modPow(w, p);
+ BigInteger a_2 = g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p);
+ BigInteger b_2 = h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p);
+
+
+ // verifier
+ BigInteger c = parameters.generateZq();
+
+ // prover
+ BigInteger d_1 = c.subtract(d_2);
+ BigInteger r_1 = w.subtract(alpha.multiply(d_1));
+
+ // verifier
+ if (!c.equals(d_1.add(d_2).mod(p))) {
+ throw new AssertionError();
+ }
+ if (!a_1.equals(g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p))) {
+ throw new AssertionError();
+ }
+ if (!b_1.equals(h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p))) {
+ throw new AssertionError();
+ }
+
+ if (!a_2.equals(g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p))) {
+ throw new AssertionError();
+ }
+
+ if (!b_2.equals(h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p))) {
+ throw new AssertionError();
+ }
+ }
+}
+
Copied: gnunet-java/src/org/gnunet/voting/VotingParameters.java (from rev
24163, gnunet-java/src/org/gnunet/voting/ElGamalScheme.java)
===================================================================
--- gnunet-java/src/org/gnunet/voting/VotingParameters.java
(rev 0)
+++ gnunet-java/src/org/gnunet/voting/VotingParameters.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -0,0 +1,166 @@
+package org.gnunet.voting;
+
+import java.math.BigInteger;
+import java.security.SecureRandom;
+import java.util.Random;
+
+/**
+ * Utilities the modified ElGamal algorithms.
+ * <p/>
+ * p is a large prime, and g is a high-order element (or even a generator) of
Zp*
+ *
+ * @author Florian Dold
+ */
+public class VotingParameters {
+ // large prime, p = 2q + 1
+ public final BigInteger p;
+ // large prime, so that q divides (p-1)
+ public final BigInteger q;
+ // generator of Gq
+ public final BigInteger g;
+
+ public final int authorityCount;
+ public final int authorityThreshold;
+
+ public VotingParameters(BigInteger p, BigInteger q, BigInteger g, int
authorityCount, int authorityThreshold) {
+ this.p = p;
+ this.q = q;
+ this.g = g;
+ this.authorityCount = authorityCount;
+ this.authorityThreshold = authorityThreshold;
+ }
+
+ /**
+ * which generates the p and g values from the given parameters,
+ * returning the ElGamalScheme object.
+ * <p/>
+ * Note: can take a while...
+ */
+ public static VotingParameters generateRandomParameters(int size, int
certainty, int authorityCount, int authorityThreshold) {
+ BigInteger[] safePrimes = generateSafePrimes(size, certainty);
+ BigInteger p = safePrimes[0];
+ BigInteger q = safePrimes[1];
+ BigInteger alpha = selectGenerator(p, q);
+ BigInteger g = selectSubgroupHigherOrderElement(alpha, p, q);
+ if (!g.modPow(q, p).equals(BigInteger.ONE)) {
+ throw new AssertionError();
+ }
+ if (!(g.compareTo(p) < 0)) {
+ throw new AssertionError();
+ }
+ return new VotingParameters(p, q, g, authorityCount,
authorityThreshold);
+ }
+
+ /**
+ * Finds a pair of prime BigInteger's {p, q: p = 2q + 1}, called safe
primes.
+ * <p/>
+ * (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) {
+ BigInteger p, q;
+ int qLength = size - 1;
+
+ while (true) {
+ q = new BigInteger(qLength, 2, CryptoUtil.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 Zn*
+ */
+ private static BigInteger selectHighOrderElement(BigInteger n,
SecureRandom random) {
+ BigInteger g;
+ final BigInteger nMinusTwo = n.subtract(BigInteger.valueOf(2));
+ do {
+ BigInteger h =
CryptoUtil.createRandomInRange(BigInteger.valueOf(2), nMinusTwo);
+
+ g = h.modPow(BigInteger.valueOf(2), n);
+ }
+ while (g.equals(BigInteger.valueOf(1)));
+
+ return g;
+ }
+
+ /**
+ * Returns a higher-order-element of Gq, the subgroup of Zp*, with order q
where alpha is a generator of Zp*
+ *
+ * (see Handbook of Applied Cryptography 4.81)
+ */
+ private static BigInteger selectSubgroupHigherOrderElement(BigInteger
alpha, BigInteger p, BigInteger q) {
+ return alpha.modPow(p.subtract(BigInteger.ONE).divide(q), p);
+ }
+
+ /**
+ * 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 Gq
+ *
+ * @return the generator of Gq
+ */
+ public BigInteger getG() {
+ return g;
+ }
+
+ /**
+ * Get the generator of Zp*
+ *
+ * @return the generator of Zp*
+ */
+ public BigInteger getQ() {
+ return q;
+ }
+
+ public BigInteger generateGq() {
+ BigInteger r;
+ while (true) {
+ r = CryptoUtil.createRandomInRange(BigInteger.ZERO, this.p);
+ if (r.modPow(q, p).equals(BigInteger.ONE)) {
+ break;
+ }
+ }
+ return r;
+ }
+
+ public static BigInteger selectGenerator(BigInteger p, BigInteger q) {
+ BigInteger pMinusTwo = p.subtract(BigInteger.valueOf(2));
+ BigInteger g;
+ /*
+ * (see: Handbook of Applied Cryptography 4.80)
+ */
+ do {
+ g = CryptoUtil.createRandomInRange(BigInteger.valueOf(2),
pMinusTwo);
+ }
+ while (g.modPow(BigInteger.valueOf(2), p).equals(BigInteger.ONE) ||
g.modPow(q, p).equals(BigInteger.ONE));
+ return g;
+ }
+
+ public BigInteger generateZq() {
+ return CryptoUtil.createRandomInRange(BigInteger.ZERO,
this.q.subtract(BigInteger.ONE));
+ }
+
+ public Cyphertext encrypt(BigInteger message, BigInteger publicKey) {
+ BigInteger secret = generateZq();
+ return new Cyphertext(g.modPow(secret, p),
message.multiply(publicKey.modPow(secret, p).mod(p)));
+ }
+
+
+}
Deleted: gnunet-java/src/org/gnunet/voting/VotingSimulation.java
===================================================================
--- gnunet-java/src/org/gnunet/voting/VotingSimulation.java 2012-10-10
19:33:49 UTC (rev 24258)
+++ gnunet-java/src/org/gnunet/voting/VotingSimulation.java 2012-10-10
21:31:53 UTC (rev 24259)
@@ -1,340 +0,0 @@
-package org.gnunet.voting;
-
-import java.math.BigInteger;
-import java.security.SecureRandom;
-import java.util.Random;
-
-public class VotingSimulation {
- /**
- * Evaluate a polynomial over Zp*. Uses Horner's scheme.
- *
- * @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 what group are we operating in?
- * @return the result of evaluating the polynomial at x
- */
- public static BigInteger evaluate(BigInteger[] coeffs, BigInteger x,
BigInteger p) {
- BigInteger z = BigInteger.ZERO;
- for (int i = 0; i < coeffs.length; ++i) {
- // z <- zx + c
- z = z.multiply(x).add(coeffs[coeffs.length - i - 1]);
- }
- return z;
- }
-
- public static void main(String... args) {
- final Random random = new Random();
- final ElGamalScheme parameters =
ElGamalScheme.generateRandomParameters(64, 10, random);
-
- final BigInteger p = parameters.getP();
- final BigInteger q = parameters.getQ();
- final BigInteger g = parameters.getG();
-
- if (!(g.compareTo(p) < 0)) {
- throw new AssertionError();
- }
-
- final int authorityCount = 10;
- // minimum required number of cooperating authorities
- final int k = 6;
-
- // parts of the private key x, one part for each authority
- BigInteger[] xParts = new BigInteger[authorityCount];
- // The full private key, sum of the parts. Initialized with the
additive identity.
- BigInteger x = BigInteger.ZERO;
-
- // parts of the public key h, one part for each authority
- BigInteger[] hParts = new BigInteger[authorityCount];
- // The full public key, product of the parts. Initialized with the
multiplicative identity.
- BigInteger h = BigInteger.ONE;
-
- for (int j = 0; j < authorityCount; ++j) {
- xParts[j] = parameters.generateZq(random);
- hParts[j] = g.modPow(xParts[j], p);
- x = x.add(xParts[j]).mod(q);
- h = h.multiply(hParts[j]).mod(p);
- }
-
- 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-1.
- BigInteger[][] f = new BigInteger[authorityCount][];
- // checkF[j][i] = g^(f[j][i]) mod p
- // used to check the share parts of each authority
- BigInteger[][] checkF = new BigInteger[authorityCount][];
-
- // generate the random polynomials
- for (int j = 0; j < authorityCount; ++j) {
- f[j] = new BigInteger[k];
- checkF[j] = new BigInteger[k];
- for (int i = 1; i < k; ++i) {
- f[j][i] = parameters.generateZq(random);
- checkF[j][i] = g.modPow(f[j][i], p);
- }
- f[j][0] = xParts[j];
- checkF[j][0] = g.modPow(f[j][0], 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][];
-
-
- // create the transmitted shared by evaluation the polynomials
- for (int j = 0; j < authorityCount; ++j) {
- shareParts[j] = new BigInteger[authorityCount];
- for (int i = 0; i < authorityCount; ++i) {
- shareParts[j][i] = evaluate(f[j], BigInteger.valueOf(i + 1),
q);
- }
- }
-
-
- // verification of the received shares:
- for (int j = 0; j < authorityCount; ++j) {
- // P_j verifies that the shares he received are valid
- for (int i = 0; i < authorityCount; ++i) {
- BigInteger v = g.modPow(shareParts[i][j], p);
- BigInteger prod = BigInteger.ONE;
- for (int l = 0; l < k; ++l) {
- BigInteger exp = BigInteger.valueOf(j+1).pow(l);
- prod = prod.multiply(checkF[i][l].modPow(exp, p)).mod(p);
- }
- if (!v.equals(prod)) {
- throw new AssertionError("verification of transmitted
shared failed");
- }
- }
- }
-
-
-
-
- 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 < authorityCount; ++i) {
- shares[j] = shares[j].add(shareParts[i][j]);
- }
- }
-
-
- BigInteger[] lagrangeBase = new BigInteger[k];
- for (int j = 1; j <= k; ++j) {
- BigInteger n = BigInteger.ONE;
- BigInteger d = BigInteger.ONE;
- for (int l = 1; l <= k; ++l) {
- if (l == j) {
- continue;
- }
- n = n.multiply(BigInteger.valueOf(l));
- d =
d.multiply(BigInteger.valueOf(l).subtract(BigInteger.valueOf(j)));
- }
- lagrangeBase[j-1] = n.multiply(d.modInverse(q)).mod(q);
- }
-
- BigInteger xReconstructed = BigInteger.ZERO;
- for (int j = 0; j < k; ++j) {
- xReconstructed =
xReconstructed.add(shares[j].multiply(lagrangeBase[j])).mod(q);
- }
-
- //System.out.println(xReconstructed);
- //System.out.println(x);
-
- if (!g.modPow(xReconstructed, p).equals(h)) {
- throw new AssertionError("key reconstruction failed");
- }
-
-
- BigInteger message = parameters.generateGq(random);
- Cyphertext cyphertext = parameters.encrypt(message, h, random);
-
- BigInteger[] w = new BigInteger[k];
- for (int i = 0; i < k; ++i) {
- w[i] = cyphertext.c1.modPow(shares[i], p);
- }
-
-
- // zero knowledge proof
- for (int i = 0; i < k; ++i) {
- // sigma is made public
- BigInteger sigma = g.modPow(shares[i], p);
- // prover
- BigInteger beta = parameters.generateZq(random);
- BigInteger a = g.modPow(beta, p);
- BigInteger b = cyphertext.c1.modPow(beta, p);
- // verifier
- BigInteger c = parameters.generateZq(random);
- // prover
- BigInteger r = beta.add(shares[i].multiply(c));
- // verifier
- BigInteger expected1 = g.modPow(r, p);
- BigInteger received1 = a.multiply(sigma.modPow(c, p)).mod(p);
-
- BigInteger expected2 = cyphertext.c1.modPow(r, p);
- BigInteger received2 = b.multiply(w[i].modPow(c, p)).mod(p);
-
- if ((!expected1.equals(received1)) ||
(!expected2.equals(received2))) {
- System.err.println(expected1);
- System.err.println(received1);
- throw new AssertionError("zero knowledge proof for decryption
failed");
- }
- }
-
- BigInteger messageRestored = cyphertext.c2;
-
- for (int i = 0; i < k; ++i) {
- BigInteger v = w[i].modPow(lagrangeBase[i], p);
- messageRestored = messageRestored.multiply(v.modInverse(p)).mod(p);
- }
-
- if (!message.equals(messageRestored)) {
- throw new AssertionError("decryption failed");
- }
-
-
- simulateBallotZKP1(h, parameters, random);
- simulateBallotZKP2(h, parameters, random);
-
- final int voteCount = 25;
- int result = 0;
-
- Cyphertext votes[] = new Cyphertext[voteCount];
- for (int i = 0; i < voteCount; ++i) {
- if (random.nextBoolean()) {
- votes[i] = parameters.encrypt(g, h, random);
- result++;
- } else {
- votes[i] = parameters.encrypt(g.modInverse(p), h, random);
- result--;
- }
- }
-
- BigInteger votesX = BigInteger.ONE;
- BigInteger votesY = BigInteger.ONE;
- for (int i = 0; i < voteCount; ++i) {
- votesX = votesX.multiply(votes[i].c1).mod(p);
- votesY = votesY.multiply(votes[i].c2).mod(p);
- }
-
- // for convenice decrypted with the full private key, the above tests
demonstrates that this
- // is equally possible without revealing the private key
- BigInteger resultG = votesY.multiply(votesX.modPow(x,
p).modInverse(p)).mod(p);
- int resultRestored = 0;
- boolean success = false;
-
- for (int l = -voteCount; l <= voteCount; ++l) {
- if (resultG.equals(g.modPow(BigInteger.valueOf(l), p))) {
- success = true;
- resultRestored = l;
- break;
- }
- }
-
- if (!success) {
- throw new AssertionError();
- }
-
- if (resultRestored != result) {
- throw new AssertionError();
- }
- }
-
- public static void simulateBallotZKP1(BigInteger h, ElGamalScheme
parameters, Random random) {
- final BigInteger p = parameters.getP();
- final BigInteger q = parameters.getQ();
- final BigInteger g = parameters.getG();
-
- // prover
- BigInteger alpha = parameters.generateZq(random);
- BigInteger w = parameters.generateZq(random);
- BigInteger r_1 = parameters.generateZq(random);
- BigInteger d_1 = parameters.generateZq(random);
-
- BigInteger x = g.modPow(alpha, p);
- BigInteger y = h.modPow(alpha, p).multiply(g).mod(p);
-
- BigInteger a_1 = g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p);
- BigInteger b_1 = h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p);
- BigInteger a_2 = g.modPow(w, p);
- BigInteger b_2 = h.modPow(w, p);
-
- // verifier
- BigInteger c = parameters.generateZq(random);
-
- // prover
- BigInteger d_2 = c.subtract(d_1);
- BigInteger r_2 = w.subtract(alpha.multiply(d_2));
-
- // verifier
- if (!c.equals(d_1.add(d_2).mod(p))) {
- throw new AssertionError();
- }
- if (!a_1.equals(g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p))) {
- throw new AssertionError();
- }
- if (!b_1.equals(h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p))) {
- throw new AssertionError();
- }
-
- if (!a_2.equals(g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p))) {
- throw new AssertionError();
- }
-
- if (!b_2.equals(h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p))) {
- throw new AssertionError();
- }
- }
-
-
- public static void simulateBallotZKP2(BigInteger h, ElGamalScheme
parameters, Random random) {
- final BigInteger p = parameters.getP();
- final BigInteger q = parameters.getQ();
- final BigInteger g = parameters.getG();
-
- // prover
- BigInteger alpha = parameters.generateZq(random);
- BigInteger w = parameters.generateZq(random);
- BigInteger r_2 = parameters.generateZq(random);
- BigInteger d_2 = parameters.generateZq(random);
-
- BigInteger x = g.modPow(alpha, p);
- BigInteger y = h.modPow(alpha, p).multiply(g.modInverse(p)).mod(p);
-
- BigInteger a_1 = g.modPow(w, p);
- BigInteger b_1 = h.modPow(w, p);
- BigInteger a_2 = g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p);
- BigInteger b_2 = h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p);
-
-
- // verifier
- BigInteger c = parameters.generateZq(random);
-
- // prover
- BigInteger d_1 = c.subtract(d_2);
- BigInteger r_1 = w.subtract(alpha.multiply(d_1));
-
- // verifier
- if (!c.equals(d_1.add(d_2).mod(p))) {
- throw new AssertionError();
- }
- if (!a_1.equals(g.modPow(r_1, p).multiply(x.modPow(d_1, p)).mod(p))) {
- throw new AssertionError();
- }
- if (!b_1.equals(h.modPow(r_1, p).multiply(y.multiply(g).modPow(d_1,
p)).mod(p))) {
- throw new AssertionError();
- }
-
- if (!a_2.equals(g.modPow(r_2, p).multiply(x.modPow(d_2, p)).mod(p))) {
- throw new AssertionError();
- }
-
- if (!b_2.equals(h.modPow(r_2,
p).multiply(y.multiply(g.modInverse(p)).modPow(d_2, p)).mod(p))) {
- throw new AssertionError();
- }
- }
-}
-
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-10-10
21:31:53 UTC (rev 24259)
@@ -0,0 +1,197 @@
+package org.gnunet.voting;
+
+import com.google.common.collect.Lists;
+import sun.security.x509.DistributionPoint;
+
+import java.math.BigInteger;
+import java.util.ArrayList;
+import java.util.Collections;
+
+/**
+ * ...
+ *
+ * @author Florian Dold
+ */
+public class VotingSimulation {
+ public static void main(String... args) {
+
+ final int authorityCount = 10;
+ final int authorityThreshold = 6;
+ final VotingParameters parameters =
VotingParameters.generateRandomParameters(64, 10, authorityCount,
authorityThreshold);
+
+ Authority[] authorities = new Authority[authorityCount];
+ for (int i = 0; i < authorityCount; ++i) {
+ authorities[i] = new Authority(i + 1, parameters);
+ }
+
+ FullPublicKey fullPublicKey = new FullPublicKey(authorities,
parameters);
+
+ ShareVerification[] shareVerifications = new
ShareVerification[authorityCount];
+
+ for (int i = 0; i < authorityCount; ++i) {
+ shareVerifications[i] = authorities[i].getShareVerification();
+ }
+
+ for (int i = 0; i < authorityCount; ++i) {
+ for (int j = 0; j < authorityCount; ++j) {
+ BigInteger distributionShare =
authorities[i].createShareForAuthority(j);
+ // receiving shares also verifies them
+ authorities[j].receiveShareFromAuthority(distributionShare,
shareVerifications[i]);
+ }
+ }
+
+ // each authority publishes a commitment to its received share
+ BigInteger[] sigmas = new BigInteger[authorityCount];
+ for (int i = 0; i < authorityCount; ++i) {
+ sigmas[i] = authorities[i].getSigma();
+ }
+
+ final int voterCount = 100;
+ int realTally = 0;
+ Ballot[] ballots = new Ballot[voterCount];
+ for (int i = 0; i < voterCount; ++i) {
+ boolean v = CryptoUtil.random.nextBoolean();
+ realTally += v ? 1 : -1;
+ // choice of 64 bits for voter id is totally arbitrary
+ BigInteger voterId = new BigInteger(64, CryptoUtil.random);
+ ballots[i] = new Ballot(v, voterId, fullPublicKey, parameters);
+ // to the non-interactive zero-knowledge-proof
+ ballots[i].verify(fullPublicKey);
+ }
+
+
+ Cyphertext encryptedTally = countTally(ballots, parameters);
+
+
+ SpecializedKeyShare[] specializedKeyShares = new
SpecializedKeyShare[authorityCount];
+
+ for (int i = 0; i < authorityCount; ++i) {
+ specializedKeyShares[i] =
authorities[i].generateSpecializedKeyShare(encryptedTally);
+ specializedKeyShares[i].verify(sigmas[i]);
+ }
+
+
+ int[] authorityIndices = randomSelection(authorityCount,
authorityThreshold);
+
+ System.out.println("Ai: " + authorityIndices.length);
+ System.out.println("thresh: " + parameters.authorityThreshold);
+
+
+ int decryptedTally = decryptTally(encryptedTally,
specializedKeyShares, authorityIndices, voterCount, parameters);
+
+ System.out.println("expected: " + realTally);
+ System.out.println("got: " + decryptedTally);
+
+ if (realTally != decryptedTally) {
+ throw new AssertionError();
+ }
+ }
+
+ /*
+ * Return between authorityThreshold and authorityCount indices
+ */
+ private static int[] randomSelection(int authorityCount, int
authorityThreshold) {
+ ArrayList<Integer> x = Lists.newArrayListWithCapacity(authorityCount);
+ for (int i = 0; i < authorityCount; ++i) {
+ x.add(i);
+ }
+ Collections.shuffle(x);
+ int len = CryptoUtil.random.nextInt(authorityCount -
authorityThreshold) + authorityThreshold;
+ int[] arr = new int[len];
+ for (int i = 0; i < len; ++i) {
+ arr[i] = x.get(i);
+ }
+ return arr;
+ }
+
+ private static int decryptTally(Cyphertext encryptedTally,
SpecializedKeyShare[] specializedKeyShares, int[] authorityIndices, int
voteCount, VotingParameters parameters) {
+ BigInteger resultG = decryptWithSpecializedKey(encryptedTally,
specializedKeyShares, authorityIndices, parameters);
+
+ int resultRestored = 0;
+ boolean success = false;
+
+ for (int l = -voteCount; l <= voteCount; ++l) {
+ if (resultG.equals(parameters.g.modPow(BigInteger.valueOf(l),
parameters.p))) {
+ success = true;
+ resultRestored = l;
+ break;
+ }
+ }
+
+ if (!success) {
+ throw new AssertionError();
+ }
+ return resultRestored;
+
+ }
+
+ private static BigInteger decryptWithSpecializedKey(Cyphertext cyphertext,
SpecializedKeyShare[] specializedKeyShares, int[] authorityIndices,
VotingParameters parameters) {
+ /*
+ BigInteger[] lagrangeBase = new
BigInteger[parameters.authorityThreshold];
+ for (int j = 1; j <= parameters.authorityThreshold; ++j) {
+ BigInteger n = BigInteger.ONE;
+ BigInteger d = BigInteger.ONE;
+ for (int l = 1; l <= parameters.authorityThreshold; ++l) {
+ if (l == j) {
+ continue;
+ }
+ n = n.multiply(BigInteger.valueOf(l));
+ d =
d.multiply(BigInteger.valueOf(l).subtract(BigInteger.valueOf(j)));
+ }
+ lagrangeBase[j - 1] =
n.multiply(d.modInverse(parameters.q)).mod(parameters.q);
+ }
+ */
+
+
+
+ // the coefficients for non-participating authorities are invalid
gibberish
+ BigInteger[] lagrangeBase = new BigInteger[parameters.authorityCount];
+ for (int j = 1; j <= parameters.authorityCount; j++) {
+ BigInteger n = BigInteger.ONE;
+ BigInteger d = BigInteger.ONE;
+ for (int l = 1; l <= parameters.authorityCount; ++l) {
+ boolean skip = true;
+ // only count participating authorities in
+ for (int authorityIndex : authorityIndices) {
+ if (authorityIndex == l-1) {
+ skip = false;
+ }
+ }
+ if ((l == j) || skip) {
+ continue;
+ }
+ n = n.multiply(BigInteger.valueOf(l));
+ d =
d.multiply(BigInteger.valueOf(l).subtract(BigInteger.valueOf(j)));
+ }
+ lagrangeBase[j-1] =
n.multiply(d.modInverse(parameters.q)).mod(parameters.q);
+ }
+
+ /*
+ BigInteger prod = BigInteger.ONE;
+ for (int i = 0; i < parameters.authorityThreshold; ++i) {
+ BigInteger wp =
specializedKeyShares[i].specializedShare.modPow(lagrangeBase[i], parameters.p);
+ prod = prod.multiply(wp).mod(parameters.p);
+ }
+ */
+
+ BigInteger prod = BigInteger.ONE;
+ for (int authorityIndex : authorityIndices) {
+ BigInteger wp =
specializedKeyShares[authorityIndex].specializedShare.modPow(lagrangeBase[authorityIndex],
parameters.p);
+ prod = prod.multiply(wp).mod(parameters.p);
+ }
+
+ return
cyphertext.c2.multiply(prod.modInverse(parameters.p)).mod(parameters.p);
+ }
+
+ private static Cyphertext countTally(Ballot[] ballots, VotingParameters
parameters) {
+ BigInteger votesX = BigInteger.ONE;
+ BigInteger votesY = BigInteger.ONE;
+ for (Ballot ballot : ballots) {
+ votesX = votesX.multiply(ballot.x).mod(parameters.p);
+ votesY = votesY.multiply(ballot.y).mod(parameters.p);
+ }
+
+ return new Cyphertext(votesX, votesY);
+
+ }
+}
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r24259 - in gnunet-java: . src/org/gnunet/util src/org/gnunet/voting,
gnunet <=