search

serai-dex / serai

Other
258 stars 47 forks source link

Review and support COPZ's cross-group DLEq #161

Closed kayabaNerve closed 3 months ago

kayabaNerve commented 1 year ago

Microsoft, UC Berkeley, and Signal just posted a cross-group DLEq proof claiming to be extremely minimal, only requiring a range proof on one curve for the key (which can be done logarithmically).

I have yet to review it and it seems overtly simple. If it holds, it'd be an immense improvement over the current proof. It'd be 1-2kb and and tens of ms, not 40-60kb and hundreds.

https://eprint.iacr.org/2022/1593

kayabaNerve commented 1 year ago

This uses non-full length keys, and integers not over a field. We'd have to grab crypto-bigint for that which would be painful. I also don't understand how they claim a 16-bit challenge can offer 128-bit security. It may be due to the lack of reduction performed? Yet this will definitely need a lot more review... It also may end up with vastly different security considerations than the current proof.

I'd note the current proof, targeting one time keys for swaps, can be run with weaker keys accordingly. Given its size, that probably is a worthy tradeoff.

kayabaNerve commented 1 year ago

Got it. The 16-bit challenge is not secure to 128-bits, and requires running the protocol multiple times to be secure. The proper solution is to use a 128-bit challenge to produce a 112-bit key (or smaller), combining with shifts as they describe.

It is notable this proof has a proving failure rate. The current proof offers a constant time API to generate a key pair. This would require a variable time API. While that wouldn't be leaky, just annoying, it's a note.

kayabaNerve commented 1 year ago

I don't believe the chunking protocol holds as-is and have reached out to the authors accordingly. If so, under the provided parameters, this would be ~7kb and only have 224 bits.

When running the protocol in parallel, I also wonder if there's crypt-analysis possible on the challenges. Given this will fail if it triggers an overflow, the challenges have to not do so (and nonces). Since running in parallel causes many challenges to be provided, I wouldn't be surprised if you could shave a few bits of security off (not that that'd be unusable). They are nonce blinded though and the paper claims ZK, so these are just a few more notes for review.

kayabaNerve commented 1 year ago

I misread the protocol and did confirm its chunking protocol is fine.

kayabaNerve commented 1 year ago

Implemented in https://github.com/kayabaNerve/full-chain-membership-proofs/tree/snarks/crypto/copz-dleq. Upstreaming it would require upstreaming the bulletproofs-plus implementation. We likely either want me to personally host BP+, or to slash and burn the BP+ to the aggregate range proof and only upstream that portion. The arithmetic circuit code is too messy to currently justify.

kayabaNerve commented 3 months ago

Out of scope and I don't want to add a BP impl as a dep to the dleq library.

If someone wants this, they should rescue the copz-dleq from that repo and probably use the BP impl within monero-serai/monero-bulletproofs.