[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: freehaven-dev@freehaven.net*Subject*: [freehaven-dev] POKs for mix accountability transcript*From*: Michael J Freedman <mfreed@MIT.EDU>*Date*: Mon, 25 Dec 2000 14:30:20 -0500*Delivery-Date*: Mon, 25 Dec 2000 14:30:36 -0500*Reply-To*: freehaven-dev@freehaven.net*Sender*: owner-freehaven-dev@freehaven.net

While we were discussion the mix accountability paper, I started mumbling about zero-knowledge proofs for the MIX transcripts. The idea is that Alice provides only a POK (or hopefully, even a ZKP) that some MIX foo failed. She doesn`t explicitly reveal the transcript (i.e., the destination to which the message should have gone, showing that foo indeed failed). [This is still (arguably) not universal verifiability in the voting sense, since Alice needs to get involved at a later stage, although the literative differs in their take on this...the term is not really formally defined.] The problem is a much more difficult one that I first thought. It`s not as simple as MIX voting, in which each MIX proves that it correctly applied a permutation on the set of votes. Instead, Alice needs to prove that 1. She knows the plaintext M that produced such a ciphertext C, and 2. The plaintext M \element VALID_{plaintexts} The first goal is not that hard to achieve by modifying the basic structure of the Fiat-Shamir type proof system. Given public ciphertext C and RSA encryption key e (prover doesn`t know d), modify F-S to use RSA-like one-way function, instead of the usual squaring function: C = m^e mod n, C is made public A-->B x = r^e mod n A<--B b \elt {0,1} A-->B y = rm^b mod n B verifies: if b=0, y^e = r^e mod n = x if b=1, y^e = r^e m^e mod n = xc And this process is repeated poly-many times. There are many other ways to do this as well. Now, Goal 2: the thing which (I think) is more difficult, is that Alice needs to prove that M belongs to some language defined over the domain. Namely, M = {random padding, identity_i, <rest of onion>}, such that, identity_i \element {public keys known (and fresh?) for MIXes in the MIX-net}, and <rest of onion> is well formed. Anyway, I think that`s the problem. Just thought I should define it more explicitly, if anybody else wants to also think about it. --mike ----- "Not all those who wander are lost." mfreed@mit.edu

- Prev by Date:
**Re: [freehaven-dev] urops for spring** - Next by Date:
**[freehaven-dev] List of possible UROP topics** - Prev by thread:
**[freehaven-dev] List of possible UROP topics** - Index(es):