2.2.3.4 Verifiable Secret Shuffle of Homomorphic Encryptions

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.¹² 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.