Cross-curve public key correlation proof

avatar
Ethereum Research

For the project I mentioned in this thread I’m building a network of nodes that will communicate with each other via gRPC. I’m going to use SSL/TLS (actually mTLS) not only for encryption but most importantly for authentication, so that each node knows exactly what node it’s talking to, or rather what the public key / wallet address of the peer is. Of course a fully decentralized project cannot have any central components, so there will be no certification authorities involved and all SSL certificates will be self-signed.

Now, here’s the problem. In principle a self-signed certificate proves ownership of a private key, so I could simply use the same key pair for both the wallet and the self-signed certificate, that way the peer knows exactly what wallet it’s talking to even though the certificate is self-signed. However, I’m almost certainly going to use the Schnorr signature scheme over the Pallas curve for my wallets (feel free to ask me why), and unfortunately SSL supports neither.

Possible Solution

As you can see in the same thread, I’ve recently started learning about elliptic curve cryptography and the Schnorr scheme. And I learned that deriving keys is independent of the signature scheme, it only depends on the specific curve. So that gave me an idea: can I use the same private key scalar for both the wallet and the self-signed certificate, and then somehow prove that the two resulting public keys (the Ed25519 public key of the certificate and the Pallas public key of the wallet) are correlated and share the same private key?

It seems I can get close to that. And I’m going to have to implement a fair bit of custom cryptography, which might be a risk but still worth pursuing IMO.

In addition to the usual fields, my mTLS certificates will also contain:

  • the public Pallas key of the node’s wallet,
  • a zero-knowledge proof to convince the peer that the Ed25519 public key and the Pallas public key are correlated without revealing the private key.

The latter is basically a “dual” Schnorr-style signature calculated over both curves (25519 and Pallas). If the signature checks out on both curves with both public keys then the peer is convinced.

One aspect to take care of is that the private key scalar must be valid in the fields of both curves, so it must be strictly less than min(n_{25519}, n_{Pallas})min(n25519,nPallas) with n_CnC being the scalar field order of curve CC (not to be mixed up with the base field order). That doesn’t seem to be a problem because both curves have a scalar field order that’s in the whereabouts of 2^{25something}225something (2^{252}2252 for 25519 and 2^{255}2255 for Pallas, it seems).

Definitions

  • n_CnC = the field order of curve CC as explained above, e.g. n_{25519}n25519 and n_{Pallas}nPallas.
  • n = min(n_{25519}, n_{Pallas})n=min(n25519,nPallas). Some of the scalars we use must be valid in the scalar fields of both curves, so we’ll refer to the field F_nFn for those.
  • xx = the private key, such that x \in F_nx∈Fn.
  • G_CGC = the generator point of curve CC.
  • P_C = x \cdot G_CPC=x⋅GC = the public key over curve CC.
  • rr = a nonce in F_nFn.
  • cc = Schnorr-style challenge hash.
  • s_CsC = the signature response scalar over curve CC.

Signature

  • Generate a nonce rr such that r \in F_nr∈Fn.
  • Commit to the nonce on both curves:
\begin{aligned}R_{25519} &= r \cdot G_{25519} \\R_{Pallas} &= r \cdot G_{Pallas}\end{aligned}
R25519=r⋅G25519RPallas=r⋅GPallas
  • Compute the challenge hash and make it valid on both fields (it can be a SHA-3 modulo nn):
c = H(R_{25519} || R_{Pallas} || P_{25519} || P_{Pallas}) \mod{n}
c=H(R25519||RPallas||P25519||PPallas)modn
  • Compute the response scalar on both curves:
\begin{aligned}s_{25519} &= r + c \cdot x \mod{n_{25519}} \\s_{Pallas} &= r + c \cdot x \mod{n_{Pallas}}\end{aligned}
s25519=r+c⋅xmodn25519sPallas=r+c⋅xmodnPallas
  • The signature is the quadruple:
(R_{25519}, R_{Pallas}, s_{25519}, s_{Pallas})
(R25519,RPallas,s25519,sPallas)

Verification

  • Compute the challenge hash as above:
c = H(R_{25519} || R_{Pallas} || P_{25519} || P_{Pallas}) \mod{n}
c=H(R25519||RPallas||P25519||PPallas)modn
  • Check the equations:
\begin{aligned}s_{25519} \cdot G_{25519} &\stackrel{?}{=} R_{25519} + c \cdot P_{25519} \\s_{Pallas} \cdot G_{Pallas} &\stackrel{?}{=} R_{Pallas} + c \cdot P_{Pallas}\end{aligned}
s25519⋅G25519?=R25519+c⋅P25519sPallas⋅GPallas?=RPallas+c⋅PPallas

Incompleteness

In the signature there is unfortunately no evidence that R_{25519}R25519 and R_{Pallas}RPallas are related, and of course we cannot reveal rr or anyone would be able to recover the private key by solving the response scalar equations for xx. This means the scheme cannot definitely prove that P_{25519}P25519 and P_{Pallas}PPallas come from the same private key, but it definitely proves that the signer owns the private keys of both (whether they’re the same or different).

That’s good enough for my purpose because proving ownership of the private key of P_{Pallas}PPallas is all I care about, and allowing different private keys might actually provide the node owner with a little extra configuration flexibility. However it raises the question: is it possible to improve this scheme to fully prove that P_{25519}P25519 and P_{Pallas}PPallas derive from the same private key?

The answer to that must be yes because worst case I can make a zk-SNARK with a circuit that derives P_{25519}P25519 and P_{Pallas}PPallas from the same private key (“I know a secret key valid on both curves that results in public key P_{25519}P25519 on Curve25519 and in P_{Pallas}PPallas on curve Pallas.”). But I was hoping to find a simpler answer (in-circuit field conversions are complicated, if I used e.g. Halo2 the Pallas key derivation would be native but I’d still have to convert all Curve25519 arithmetic to the Pallas field), as well as one that doesn’t rely on bleeding-edge cryptography for the security of the private key (what if one of these zk-SNARK schemes turns out to be vulnerable and someone manages to recover the private inputs, which include the private key in this case?).

Alternatives Considered

1. Self-signed wallet key

Rather than going through this hassle, why not just embed the Pallas public key in the certificate along with a signature of itself that can be verified with itself?

Because that would open a replay attack vector leading to impersonation. Once one of these certificates becomes public, anyone can make its own self-signed SSL certificate containing someone else’s Pallas public key.

2. Double-signed wallet key

So why don’t we sign the public Pallas key twice – once with itself and once with the Ed25519 keypair?

Because that’s exactly the same as #1 above.

3. Double-signed wallet key the other way around

Sign the public Pallas key twice – first with the Ed25519 key and then with itself!

That could work and it’s probably equivalent to what we’re doing with our proposal, the only difference being that our scheme is slightly more ergonomic (no big deal anyway).

3. zk-SNARKs

Discussed above, in the “Incompleteness” section.


Sector:
Governance
DeFi
AMM
Source
Disclaimer: The content above is only the author's opinion which does not represent any position of Followin, and is not intended as, and shall not be understood or construed as, investment advice from Followin.
Like
Add to Favorites
Comments
Relevant content