[freehaven-dev] POKs for mix accountability transcript

[Michael J Freedman <mfreed@MIT.EDU>]

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