I have a problem where I have a table of various reencryptable/rerandomizable ciphertexts (Paillier, Elgamal, EC Additive Elgamal). Each row on a given table has the same structure, but each column potentially has its own cryptosystem. This shuffle gets executed several times on different tables with different numbers of columns.

  • I want a group of parties to execute a verified shuffle of this table.

As far as I can tell, the shuffle proofs I see, rely on there being something in common between the columns of the ciphertexts. I currently have a brute force proof that proves that each original row appears in the shuffled table, but this proof is too expensive ($O(n^2 \cdot k)$, where $n$ is the rows and $k$ is the columns).

  1. Is there an efficient mechanism to prove a shuffle of arbitrary tables?
  2. Also, is there a way the shufflers can work together to make one proof rather than a step-by-step proof?
  • 1
    $\begingroup$ I think this will work for you usenix.org/legacy/event/evt06/tech/full_papers/benaloh/… $\endgroup$
    – knaccc
    Jan 20, 2023 at 22:37
  • 1
    $\begingroup$ So he is using a cut-and-choose-like approach to shuffle the table arbitrarily. I like it. I suppose that would probably be faster with a $O(m \cdot n \cdot k)$ complexity, where m is the number of bits in the challenge. Not only that, but these should be faster than the sigma protocols I have been using, so the coefficient would likely be orders of magnitude smaller. I'll try implementing that and seeing if it is any better. $\endgroup$
    – Zarquan
    Jan 20, 2023 at 22:58
  • $\begingroup$ This can also theoretically be used to have the group of shufflers work together on the beginning and end tables that has to be shuffled publicly, but this would require the intermediate tables to be publicly available, which could have a communication size problem. I would like an approach that didn't require storing 50 copies of the table, but this is probably better than what I am currently doing. $\endgroup$
    – Zarquan
    Jan 20, 2023 at 23:02
  • $\begingroup$ What's the motivation to use a group of shufflers instead of a single shuffler? $\endgroup$
    – knaccc
    Jan 20, 2023 at 23:52
  • 1
    $\begingroup$ Actually, proving that each entry in the original also appears in the shuffle does not prove that the shuffle is a permutation of the original - consider the case where the original has entries with identical (duplicate) values - the 'shuffle' could have that entry once (and also include a completely different value as the replacement). For example, [0,0,1] shuffled is not [1,0,42]. This implies that you might need to replace your algorithm due to correctness, rather than efficiency (unless, in your problem space, duplicate entries are impossible) $\endgroup$
    – poncho
    Jan 21, 2023 at 3:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.