Next: , Previous: , Up: Operations on Stacks   [Contents][Index]

3.5.2 Shuffling the Deck

Every player must perform a shuffle of the deck, because only such a procedure guarantees that no coalition has influence on the outcome. Thus we build a shuffle chain (e.g. using the strict total order P_i < P_j, if and only if i < j) such that each player shuffles the deck once.

First the regular stack s is initialized with open cards from deck. Then each player shuffles the stack (see SchindelhauerTMCG, i.e, TMCG_MixStack) using randomness (see TMCG_CreateStackSecret) and proves the correctness of this operation (see TMCG_ProveStackEquality). Consequently, every player should verify these proofs (see TMCG_VerifyStackEquality) and complain deviations immediately. Finally, the stack s contains the shuffled result. Consider the following code fragment for the player P_j.

for (size_t i = 0; i < 5; i++)
  TMCG_Stack<VTMF_Card> s2;
  if (i == j)
    TMCG_StackSecret<VTMF_CardSecret> ss;
    tmcg->TMCG_CreateStackSecret(ss, false, s.size(), vtmf);
    tmcg->TMCG_MixStack(s, s2, ss, vtmf);
    for (size_t i2 = 0; i2 < 5; i2++)
      if (i2 == j)
      out_stream[i2] << s2 << std::endl;
      tmcg->TMCG_ProveStackEquality(s, s2, ss, false, vtmf,
        in_stream[i2], out_stream[i2]);
    in_stream[i] >> s2;
    if (!in_stream[i].good())
      std::cerr << "Read or parse error!" << std::endl;
    if (!tmcg->TMCG_VerifyStackEquality(s, s2, false, vtmf,
      in_stream[i], out_stream[i]))
        std::cerr << "Verification failed!" << std::endl;
  s = s2;

If you want to use the more efficient shuffle verification protocol of Groth, then you have to replace TMCG_ProveStackEquality and TMCG_VerifyStackEquality by TMCG_ProveStackEquality_Groth and TMCG_VerifyStackEquality_Groth, respectively.16



The non-interactive version of Groth’s protocol (see TMCG_ProveStackEquality_Groth_noninteractive and TMCG_VerifyStackEquality_Groth_noninteractive) provides an even more efficient implementation, because the prover has to compute the argument of correctness only once. Additionallly, it protects agains malicious verifiers and reduces the communication complexity, i.e. instead of O(n^2) the prover must perform only O(n) steps. Thus this approach is strongly recommended. However, the security then relies on the random oracle assumption. Please have a look at the included source code tests/ to get a clue.