Public Key recovery

[NN-Binary]

Hi,

I'm having a hard time recovering public keys from a Signature in this crate. How is it done? Anyone have a proper example? Thank you.

[burdges]

If you mean like the ecrecover used by ethereum for ecdsa keys, then you need a more malleable schnorr signatures for that, but doing so makes anything like HDKD insecure, so sane schemes do not permit this. Also, if you do anything "blockchain" then your users will do HDKD whether you want them to or not, so just forget about ecrecover. In fact ecrecover is a really dumb idea anyways because it breaks batch verification.

[WildCryptoFox]

@NN-Binary Why do you want public key recovery from the signature? Are you trying to reduce the storage costs of many (public key, message, signature) triples?

@burdges What do you mean by 'more malleable' being necessary for public key recovery? Ethereum uses ECDSA over secp256k1, a prime order group - not malleable. Ed25519 is already 'more malleable' than secp256k1.

Schnorr has two variations; supporting exclusively either public key recovery or batched verification under a common signer.

Ed25519, as an official specification, forces the decision to the latter. A Ristretto255 Schnorr implementation can decide without worrying about the cofactor-malleability of Ed25519.

HDKD only blinds the keypair; where the blinding factor is public in the weak case. The issue is when cofactor-many public keys are equivalent yet indistinguishable to a human. An inconsistency between user expectation and reality, but is this a security-level issue? It is an issue with malleability in general, not the addition of HDKD, which effectively has this distinct-looking as one of its properties.

[burdges]

@james-darkfox Cofactors are irrelevant here.

You cannot do public key recovery if you define c = H(R,msg,pk) of course. You must increase malleablity by defining c = H(R,msg) if you want public key recovery.

There are niche cases where c = H(R,msg) gets used securely, like deep inside some zero knowledge proofs, and the security proofs cover that form, but..

You cannot claim security for any general pupose signature scheme that uses c = H(R,msg) because the signature scheme's security is not composable in ways everyone expects.

In HDKD there are many secret keys x and y for which x = z y for some publicly known z = H(foo)/H(bar). As a result, you can transform a signature with c = H(R,msg) for x into a signature for y. It's not only cyber-coins using HDKD since projects like GNS and Tor hidden services do so too.

If you want HDKD and ecRecover together, and you cannot ensure 100% control over the use case, then you must use ECDSA, not Schnorr.

Ristretto cannot improve the situation because cofactors have nothing whatsoever to do with the problem.

You'll find a longer write up at https://www.deadalnix.me/2017/02/17/schnorr-signatures-for-not-so-dummies/

[WildCryptoFox]

@burdges Thanks for the link and correcting me. It seems I conflated ed25519's selection for one Schnorr representation with hashed inclusion of the public key.

[burdges]

There are similar issues with using BLS for cyber-coin accounts: Yes, you can make BLS non-malleable, but then you've killed most of BLS' advantages.

As an aside, we should expect some risky, or outright insecure, combinations of the form ECDSA + ecRecover + HDKD + multisignature + adaptor-like signature + etc too, but for which pairwise nobody knows attacks.. and maybe deployed among the army of poorly designed non-private layer 2 solutions.