Implement B-Pop for PoPs about celo-bls-snark-rs

[kobigurk]

Interesting, I'd be happy to talk more about it to see how it applies.

…

On Mon, Sep 16, 2019, 11:55 Noah Vesely ***@***.***> wrote: In #63 <#63> support was added for the PoP from section 4.4 of https://cseweb.ucsd.edu/~syilek/pkreg.pdf. Compared to the B-Pop protocol in section 4.1, the one in section 4.4 has several weakness. First, PoP4.4 requires sampling a random challenge value, and we'll have to figure out how to do this in a distributed system. Second, PoP4.4 makes honest parties vulnerable to MitM attacks during key registration. Section 4.4 indeed explains how this attack can be carried out with a signing oracle, but by changing the hash function the problem is just moved to needing a registration oracle. In the real world you might obtain a registration oracle via a MitM on an honest party trying to register a key. Unless some sort of at-most-once-per-key registration semantics are implemented (which seems more fraught than switching to B-Pop), this attack becomes practical. B-Pop may be seen as applying Fiat-shamir to PoP4.4 and gaining non-malleability. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#68>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AA23MGGQDLQEICIX54JJV3TQJ5CYHANCNFSM4IW7PTBQ> .

[kobigurk]

Specifically, I hope to understand if it's OK to use a non-random challenge, but a known message (e.g., the Ethereum address). Or more concretely, understand how the proof relies on the public key being the string signed.

[psivesely]

Above when I said "registration oracle" I meant the algorithm in the paper they call RegP, the prover's registration algorithm. In the paper, they give the adversary oracle access to RegV, the verifier's registration algorithm, when in the registered public key model. This makes sense because my point was access to RegP would allow the adversary to succeed. The multisignature security experiment (fig. 1) reflects the real world in that in a spec we would define a non-interactive method B-Pop.RegP(sk) that only takes a local secret as input and thus cannot be used as an oracle.

In particular, B-Pop.RegP takes as input sk, computes pk, and uses sk to sign RO_p(pk). Here RO_p is different random oracle than the RO_s used to sign messages. So the message signed is in fact a random challenge; there's a unique random challenge corresponding to each pk. Signing the pk itself as in S-Pop, or using the same RO as used for signing as in BadPop, is demonstrably insecure (section 4.3).

[kobigurk]

We concluded the way we planned it is fine - use the Ethereum address as the fixed message.