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

```

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.

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 -