Re: [freehaven-dev] POKs for mix accountability transcript

[dmolnar@belegost.mit.edu]

On Wed, 3 Jan 2001, David Hopwood wrote:

> On closer examination I don't think this really helps. We would like to
> be able to prove to any observer that:
>   1) N_j received C (this part is easy)
>   2) E_pk_j(N_{j+1}, M) = C
>   3) M was not sent to N_{j+1}
> 
> without giving away M or N_{j+1}. I'm not sure this is even possible.

1) and 2) may be possible if we have a commitment scheme which has a
protocol for proving set membership and ring operations. By this I mean

	Set membership:
	
	Given a commitment COMMIT(m1) and a set S, we can prove that
	COMMIT(m1) is a commitment to a member of S without revealing
	any information about which member it is the commitment of.

	The idea is to fix a set S of possible N_i and then commit
	to the N_{j+1}, then use set membership to show it's a valid
	N_{j+1}. Of course, the problem is that if you allow people
	to execute this protocol with different S, you could eventually
	discover what N_{j+1} is...

	What comes to mind are the "committal deniable" proofs used by
	Franklin and Sander for their receipt-free digital donation
	protocol, but I haven't checked this out in depth yet.
The link is 
http://link.springer.de/link/service/series/0558/bibs/1976/19760373.htm


	Ring operations:

	Suppose we want to show that C = (N_{j+1} || M)^e mod n,
	where || is string concatenation. 
	Suppose we have a commitment to M,  COMMIT(M)
	and a commitment COMMIT(N_{j+1})

	We want to form a commitment to their concatenation
	COMMIT(N_{j+1} || M). Then we show that C corresponds
	to that value raised to the e power mod n. 
	If we can prove that arbitrary ring operations over
	Z_N^* hold between commitments, we can do all of this.
	Such a commitment scheme was given by Cramer and Damgard
	at CRYPTO '98

	"Zero-knowledge proofs for Finite Field Arithmetic - or -
	Can Zero-Knowledge Be For Free?"
	Cramer and Damgard CRYPTO '98
	http://citeseer.nj.nec.com/201576.html


More detail on this in a bit; right now my sister needs to use the
computer.

-David