Sigma proofs may leak more than expected.

[pereira]

Our current approach to committing on list of neighbors is something like this:

• if A called B and C, compute c_A = g^r.h^A.h_1^B.h_2^C. If we need to prove that A called B at some point, we will prove the following statement:
• {(r, C): c_A/(h^A.h_1^B) = g^r.h_2^C}. This is good, except that it 'leaks' that, in c_A, B happens to be the power of h_1 (and not the power of h_2). Here is how this can become an issue: Suppose that we want to show the E and F are at distance 2 of A, and that they are neighbors of B (but not of C). So, c_B = g^r'.h^B.h_1^D.h_2^E. We will then prove the following statement:
• {(r, r', B, C): c_A/h^A = g^r.h_1^B.h_2^C and c_B/h_1^D.h_2^E = g^r'.h^B} The problem is that, from the first proof, the verifier already learned that the power of h_1 in c_A is B. Therefore, he can deduce that the power of h in c_B is B as well, and that D and E are connected to A through B. But this is not something that can normally be deduced from the two queries that are made.

Three possible solutions to this issue:

1. We abandon the use of multi-commitments, and commit on the list of neighbors as g_r1.h^A.h_1^B; g_r1.h^A.h_1^C (that is, one commitment per neighbor). Downsides: more computationally demanding, may require more machinery if we want to have ways of checking that Telstra does not "forget" commitments when answering queries (about the list of neighbors of A for instance).
2. We make proofs of more complex statements when we are asked to prove that A called B: we prove that B appears as a power of one of the generators, without leaking which one. Looks like an OR proof of length proportional to the number of generators in the commitment. Downside: more expensive.
3. We "ignore" the cases of second hop queries that are required to hide first hop neighbors. These look quite artificial. Question: if we rule out that type of query, are we good? Any example of natural query in which leaking about generator positioning may be an issue?

My intuition would be to go for the simple solution that leaves us with a good flexibility in what we express, that is, the first one.

[ecuvelier]

1) Could you really link the first proof to the second? When you make the proof, you will query the commitments in the Path ORAM and, when you store them back, you will modify/rerandomize them. So you won't see the same c_A twice right?

2) There may be an issue with using several commitments (edges list) to represent edges of one node. You will have edges lists of different sizes. So when you need to check the edges of a node, even if you use Path ORAM, you will need different number of queries for each node. This may reveal the degree of the nodes.

[pereira]

Hi, Edouard, With respect to 1.: yes, this is not the same c_A, but the only thing that changes is the randomness (the exponent of g). So, this is not an issue for the attack, since the answers to the two queries ("has A called B" and "are E and F withing 2-hop distance of A") both will need to show that we are talking about c_A (or its re-randomization). And the receivers knows that the only change we make is on the exponent of g. Of course, the rerandomization step could also shuffle the bases in the commitment, but then we need to prove that this shuffle happens correctly, which sounds considerably more challenging and costly to do.

[pereira]

With respect to 2: Well, we seem t.o have that problem anyway: we need to at least offer a bound on the number of generators that we use in a multi-commitment, and this will potentially leak information, right? We would solve this by choosing an upper bound on the number of generators and include dummy exponents (maybe just "0") for those we do not use. So, if we have "basic" commitments (each including a single neighbor), we will just have the same issue, which we can solve in the same way: add dummy commitments. Does that sound right?

[ecuvelier]

Hello,

I agree we have dummy commitments in both cases, but in the first one, we only have to store one group element, in the second one we need to store d group elements where d is the max degree admitted. Thus, for the path ORAM query, we will need to retrieve d.Z.log(n) blocks. I know this is just multiplying by a constant d and that it will not affect the efficiency asymptotically but still... I wonder if we compare it to the proof of shuffle of (c_A,c'_A) where the bases are re-randomized : I mean we do not need to re-randomize the base for each commitment retrieved during the Path ORAM query, but just for those on which we performed some proof.

[pereira]

Your remarks make perfect sense. It is true that we will have a relatively high cost coming from the extra ORAM accesses. We should check how to prove that generators are getting rerandomized for a Pedersen multi-commitment. Not sure of how that would work, and if we can gain anything in terms of efficiency by knowing that we just switch to randomly chosen generators. Maybe a better way to proceed would be to encode all the neighbors in a cryptographic accumulator (which has the advantage of being commutative) rather than as an ordered list in a multi-commitment.

[pereira]

Hi, One possibly good solution to this problem of neighbors that we want to keep unordered (so that the ordering does not leak information between proofs) would be based on the commitments to polynomials of Kate, Zaverucha and Goldberg http://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf. Roughly speaking, the idea would be: Given a set of neighbors {a_1, ..., a_n}, commit on the polynomial (x - a_1)...(x - a_n). Observe that this is order independent. The Kate et al. paper shows how to do this in such a way that the commitment is a single group element, and so that we can efficiently prove in ZK whether a value a is actually a root of the polynomial or not. The "or not" is particularly nice, because it makes it possible to prove that two numbers are not neighbors. I did not flesh everything out yet, so do not know whether it really works, but that looks promising to me.

[pereira]

BTW, non working solutions included:

• Many efficient accumulator schemes do not seem to offer good ways of proving membership and non membership in ZK. It typically does not seem to be a concern to hide the values in the accumulator, or to see whether a proof of (non-)membership hides the values in the accumulator.
• ZK sets seem to be what we really need. They focus on having ZK proofs of membership or non-membership. Many of them seem to have a largely theoretical flavor and/or to be based on hash functions that do not work quite nicely with what we do. One big features of these ZK sets is to hide the size of the set. That would be good for us, even though it may not be critical (we can work with upper bounds). The Kate et al. protocol leaks the set size, but gives us something that seems to work much more smoothly with the rest of our stuffs.
• Vector commitments are another recent approach for building accumulators. The construction I saw (from the original paper) would be very inefficient in our case: they require a public key that has a size quadratic in the size of the set of possible set elements. In our case, our set elements are 9 digit numbers (the phone numbers), so the public key would have size around 10^18. Not good. But there may be other better constructions.

[ecuvelier]

Hi, To my understanding, the solution of Kate, Zaverucha and Goldberg works nicely and also get us rid of the dummy commitments... so let's go for it :-)

[vteague]

Hi all,

Has anyone read this one: http://eprint.iacr.org/2015/404.pdf Looks like it has set membership and non-membership, but I have no idea whether it's efficient or not. Cheers, Vanessa.

[vteague]

Hi all, Just realised that the Kate et al paper is really good anyway, so probably no great need to look at that new one I just sent. Possibly useful for intersections etc though.

Cheers, Vanessa.