Efficient Zero Knowledge Proof for proving a reencryption shuffling for an arbitrary table

Zarquan

1/20/24, 9:20 PM

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).

Is there an efficient mechanism to prove a shuffle of arbitrary tables?
Also, is there a way the shufflers can work together to make one proof rather than a step-by-step proof?

0 + 7

zero-knowledge-proofs

mixnets

knaccc

1/20/24, 10:37 PM

I think this will work for you https://www.usenix.org/legacy/event/evt06/tech/full_papers/benaloh/benaloh.pdf

Zarquan

1/20/24, 10:58 PM

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.

Zarquan

1/20/24, 11:02 PM

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.

knaccc

1/20/24, 11:52 PM

What's the motivation to use a group of shufflers instead of a single shuffler?

Zarquan

1/21/24, 12:01 AM

Because no single person in the shuffle is allowed to know how it is shuffled as a whole. So, they each take turns shuffling.

poncho

1/21/24, 3:41 AM

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)

Zarquan

1/21/24, 8:34 AM

True, I hadn't considered that. My problem can (and currently does but doesn't need to) have duplicate rows. I should be able to fix that generally by not allowing for duplicate rows or by having a flag for each row and a proof that the flag is set (but I suspect this is effectively the same. To avoid duplicate rows, I could essentially add a column with a different value for each row to each table that gets discarded after the shuffle, but that would be more expensive.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Efficient Zero Knowledge Proof for proving a reencryption shuffling for an arbitrary table

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.