Next: HooghSchoenmakersSkoricVillegasVRHE, Previous: JareckiLysyanskayaEDCF, Up: Classes [Contents][Index]

Recently, Groth [Gr05, Gr10] has proposed a very efficient solution to perform a verifiable shuffle of homomorphically encrypted values. He describes an honest verifier zero-knowledge argument which shows the correctness of a shuffle. Beside other applications (e.g. verifiable mix networks, electronic voting) his protocol can be used to show (with overwhelming probability) that the secret shuffle of a deck of cards was performed correctly. The computational complexity and the produced communication traffic are superior to previously deployed techniques (e.g. Schindelhauer’s cut-and-choose method). LibTMCG provides the first known implementation of Groth’s famous protocol. However, it can only be used along with the VTMF card encoding scheme of Barnett and Smart [BS03] based on the hardness of computing discrete logarithms.

Our implementation uses a generalized variant [Gr05, Gr10] of the
statistically hiding and computationally binding homomorphic commitment scheme
due to Pedersen (see *Non-interactive and Information-theoretic Secure
Verifiable Secret Sharing*, CRYPTO ’91, LNCS 576, 1992). The binding
property relies on the hardness of computing discrete logarithms in *G*
w.r.t. random bases *g_1, \ldots, g_n* and thus a commitment is only
binding for computationally bounded provers.^{12} But this choice seems to be reasonable for the
intention of LibTMCG, because all players are supposed to be computationally
bounded. The security parameters of the commitment scheme (in particular the
group *G*) are determined by the corresponding VTMF instance.

Since version 1.2.0 of LibTMCG we use a two-party version of a distributed coin
flipping protocol by Jarecki and Lysyanskaya [JL00] to protect against
malicious verifiers attacking the zero-knowledge property. Since version 1.3.0
there is an additional method for generating the bases *g_1, \ldots, g_n*
of the Pedersen commitment scheme by distributed coin flipping and a verifiable
generation procedure similar to FIPS 186-3 A.2.3. This step is important in order
to ensure, that a malicious prover cannot compute *\log_{g_i} h* resp.
*\log_h g_i*, for some *i = 1, \ldots, n*, and thus erroneously pass
the shuffle verification. It improves our former security model which considered
only a passive adversary.

Further, to the best of our knowledge it is not known, whether Groth’s protocol retains the zero-knowledge property when it is executed in a concurrent setting. Thus the application programmer should be careful and avoid parallel invocations of the same instance.

- Class:
**GrothVSSHE** This class provides the low-level interface for Groth’s protocol. There are just a few methods that might be of general interest. All other components are only used internally by high-level operations and thus their description is omitted here.

- Constructor on GrothVSSHE:
**GrothVSSHE***(*`size_t`

n,`mpz_srcptr`

p_ENC,`mpz_srcptr`

q_ENC,`mpz_srcptr`

k_ENC,`mpz_srcptr`

g_ENC,`mpz_srcptr`

h_ENC,`unsigned long int`

ell_e`=TMCG_GROTH_L_E`

,`unsigned long int`

fieldsize`=TMCG_DDH_SIZE`

,`unsigned long int`

subgroupsize`=TMCG_DLSE_SIZE`

) This constructor creates a new instance. The low-level operations are later used to show the correctness of a shuffle of at most

`n`cards. The protocol and some parameters of the commitment scheme are initialized by the members of the corresponding VTMF instance. Consequently,`p_ENC`is the prime number*p*which determines the field*{\bf Z}/p{\bf Z}*,`q_ENC`is the order of the underlying subgroup*G*, i.e. the prime number*q*, and`k_ENC`is the integer such that*p = qk + 1*holds. Further,`g_ENC`is the generator*g*of this subgroup, and finally`h_ENC`is the common public key*h*. The positive integer`ell_e`is the security parameter which controls the soundness error probability (*2^{-\ell_e}*) of the protocol. The default value is defined by`TMCG_GROTH_L_E`

, if this argument is omitted. The`fieldsize`and the`subgroupsize`are supplied to internal classes and are only of interest, if`p_ENC`or`q_ENC`have lengths different from the default. If these arguments are omitted, they are set to`TMCG_DDH_SIZE`

and`TMCG_DLSE_SIZE`

, respectively.This constructor should be instantiated only once by the session leader. All other instances can be created by the second constructor. Further, it is very important that the VTMF key generation protocol has been finished before the value of

*h*is passed to the constructors. Otherwise, the correctness verification of the shuffle will fail.Note that the generators

*g_1, \ldots, g_n*of the Pedersen commitment scheme are randomly and uniformly chosen from*{\bf Z}_q*by the session leader. However, this is not verifiable by other parties and a malicious leader can choose*g_j := h^{\xi_j} \bmod p*for some secret*\xi_j\in {\bf Z}_q*where*1 \le j \le n*. Thus it is importand to call`SetupGenerators_publiccoin`

during game initialization before any shuffle verification is performed.

- Constructor on GrothVSSHE:
**GrothVSSHE***(*`size_t`

n,`std::istream&`

in,`unsigned long int`

ell_e`=TMCG_GROTH_L_E`

,`unsigned long int`

fieldsize`=TMCG_DDH_SIZE`

,`unsigned long int`

subgroupsize`=TMCG_DLSE_SIZE`

) This constructor initializes the instance from a correctly formatted input stream

`in`. For example, such a stream can be generated by calling the method`PublishGroup`

of an already created instance. Later the instance can be used to show the correctness of a shuffle of at most`n`cards. The positive integer`ell_e`controls the soundness error probability of the protocol. The default value is defined by`TMCG_GROTH_L_E`

, if this argument is omitted.Note that the generators

*g_1, \ldots, g_n*of the Pedersen commitment scheme are randomly and uniformly chosen from*{\bf Z}_q*by the session leader. However, this is not verifiable by other parties and a malicious leader can choose*g_j := h^{\xi_j} \bmod p*for some secret*\xi_j\in {\bf Z}_q*and*1 \le j \le n*. Thus it is necessary to call the method`SetupGenerators_publiccoin`

before any shuffle verification is performed.

- Method on GrothVSSHE:
*void***SetupGenerators_publiccoin***(*`mpz_srcptr`

a) This is a simple method to setup the generators

*g_1, \ldots, g_n*of the internal Pedersen commitment scheme by using a common random value`a`for a verifiable generation procedure similar to FIPS 186-3 A.2.3. Note that the same`a`must be used by all participants and that this value should be different for each game session.

- Method on GrothVSSHE:
*bool***SetupGenerators_publiccoin***(*`size_t`

whoami,`aiounicast*`

aiou,`CachinKursawePetzoldShoupRBC*`

rbc,`JareckiLysyanskayaEDCF*`

edcf,`std::ostream&`

err) This method setup the generators

*g_1, \ldots, g_n*of the internal Pedersen commitment scheme by using a distributed coinflip protocol [JL00] and a verifiable generation procedure similar to FIPS 186-3 A.2.3. Assuming at least one honest player these values are randomly and uniformly chosen from*{\bf Z}_q*such that*\log_{g_i} h*and*\log_h g_i*are unkown, for all*i = 1, \ldots, n*. The argument`whoami`is an index of the running instance with respect to already initialized instances of asynchronous point-to-point channels`aiou`and a reliable broadcast channel`rbc`. Logging and debug messages are printed to the provided output stream`err`. The method returns`true`

, if all generators have been setup successfully.

- Method on GrothVSSHE:
*bool***CheckGroup***()* This method checks whether the initialized commitment scheme is sound. It returns

`true`

, if all tests have been passed successfully.

- Method on GrothVSSHE:
*void***PublishGroup***(*`std::ostream&`

out) This method exports the instance configuration to the output stream

`out`such that other instances can be initialized, e.g. with the second constructor.

- Destructor on GrothVSSHE:
**~GrothVSSHE***()* This destructor releases all occupied resources.

- Constructor on GrothVSSHE:

Strictly speaking, due to
this reason Groth’s protocol is a zero-knowledge *argument* instead of a
zero-knowledge *proof*. However, for convenience we will not distinguish
between these terms here.