NI-PoKE2 uses group generator, rather than `H_𝔾(u,w)`

[HarryR]

In https://github.com/cambrian/accumulator/blob/c1450aac7cc45011af40b48db02354c6a27a8a76/src/proof/poke2.rs#L19

And https://github.com/cambrian/accumulator/blob/c1450aac7cc45011af40b48db02354c6a27a8a76/src/proof/poke2.rs#L32

The NI-PoKE2 implementation uses the group generator, however the BBF'18 paper denotes that g ← H_𝔾(u,w) in the non-interactive context. (see pg42, appendix D)

I think this is significant, in the non-interactive context, because it ensures the whole equation is parameterised by u and w, whereas without the 'hash to group' function being used for the generator of g^x you potentially weaken the proof.

I can't see a 'hash to group' function in the source code.

What are your thoughts?

[plra]

You are correct in pointing out this difference between our implementation and BBF. However, for security we only need g to be a fixed generator (w.r.t. u and w) and its roots hard to compute. These criteria suffice for z = g^x to be a binding commitment to the logarithm x.

In the Rsa2048 case, you'll see that g is 2. This is certainly fixed, and since discrete logarithms are hard in the RSA group computing its roots is no easier than computing the roots of an arbitrary H_G(u, w).

For more detail see sections 3.2-3.3 of BBF (in particular, sections An attack and Non-interactive proofs).

[HarryR]

That makes sense.

I think we can close this issue for now.

I did some rough notepadding of the problem, and came to the conclusion that it is computationally binding regardless of which generator is used for g, specifically because of the l=hash2prime(..) and alpha=hash2int(..), where you'd end up in a loop that every time you try to negate alpha by setting u=modinv(alpha), or making the right-hand-side match Q^l (by setting r=1 etc.) then finding values of w and z means whenever you choose another value all of the parameters change.

But the security parameter seems to depend on alpha=hash2int(...), and as long as that's like 256 bits then everything is good.

Thanks though, cool project :D