Open LLFourn opened 3 years ago
I agree that this is an important topic with interesting applications.
Also worth mentioning Juggling which seems like the most promising approach to me so far.
"practical" verifiable encryption of DLOG
Does this work for arbitrary groups such as secp256k1?
@jonasnick Thanks. I think I recall this idea as a gradual release scheme.
Does this work for arbitrary groups such as secp256k1?
Yes it does. It falls into the greater pool of "discrete log easy subgroup in groups of unknown order" scheme. The idea is that you can encrypt the group element of the DL-easy subgroup (in this case group of order N where modulus is N^2) and so decrypting the group element allows you to decrypt the associated secret key. You can provide proof that you have encrypted the right thing via a sigma EQ composition. The proof is tricky since you are in a group of unknown order but it's doable. This is the same idea as in Castagnos and Laguillaumie (CL) verifiable encryption but with a Paillier modulus instead.
Another example of verifiable encryption is in Fast Secure Two-Party ECDSA Signing which does verifiable encryption of a prime-order group scalar within a Paillier encryption (so it can encrypt the ECDSA signing key and give it to the other party to operate on).
Another cut and choose approach worth noting (I've not read it yet): https://eprint.iacr.org/2020/1563.pdf
On https://eprint.iacr.org/2020/1563.pdf how is a verifiable timed signature different from a verifier that checks a regular signature in plaintext, but then only executes the resulting logic after a specific time?
On https://eprint.iacr.org/2020/1563.pdf how is a verifiable timed signature different from a verifier that checks a regular signature in plaintext, but then only executes the resulting logic after a specific time?
well you have to assume the verifier is honest then in that they only do the thing after the time. This prevents them from doing it before that time.
Afaik signature verifiers are always assumed honest because verifiers could always take action without the signature.
Well ok sure but if it's a blockchain signature then the person decrypting the thing is not verifying the signature but is verifying the encryption, then working to decrypt and then taking the action of broadcasting the tx with the signature. The blockchain network is then verifying the decrypted signature.
Alright, but any blockchain already has a clock, so it's more robust if the transaction rules simply demand waiting past some specified time, no?
I do realize front-running or MEV defenses provide use cases for verifiable encryption, perhaps including encrypting the signer of a signature, but verifiable timed signature just surprised me. Apologies for the derail.. ;)
No worries. Perhaps the authors are using it in settings where the blockchain doesn't have timelocks (e.g. monero). I'm not sure though. I'm only interested in the cut-and-choose VE that forms part of the scheme (which can be used independently -- or so I'm told!).
I had some time to benchmark our verifiable encryption from Cryptographic Oracle-Based Conditional Payments as a pure batch verifiable encryption algorithm. Here's some results for total running time for ristretto at the 128 bit security level (time in ms
):
n_encryptions time_per_encryption time_total
2 38.5 77
4 26.5 106
8 19.875 159
16 16 256
32 13.03125 417
64 11.21875 718
128 9.53125 1220
256 8.390625 2148
512 7.390625 3784
1024 6.8056640625 6969
2048 6.130859375 12556
Key take away is that you get diminishing returns past ~100 verifiable encryptions batched.
To get an idea about how much is borne by the prover vs verifier:
cargo run --release -- -s 128 --n-encryptions 100
Finished release [optimized] target(s) in 0.03s
Running `/home/llfourn/src/dlc-venc-adaptor/target/release/run -s 128 --n-encryptions 100`
Params s: 128 n_encryptions: 100, n_elgamal_encryptions: 2847 bucket_size: 22 proportion_closed: 0.773
End Alice 1 elapsed: 302.516165ms transmitted: 364419
End Bob 1 elapsed: 98.829µs transmitted: 7935
End Alice 2 elapsed: 430.236653ms transmitted: 372716
End Bob 2 elapsed: 258.521873ms
Total elapsed: 991 sans-preprocessing: 688 transmitted: 745070 non-interactive: 737135
so 100 verifiable encryptions takes around a second in total with around 732 ms prover time and 258ms verifier time. Note that Bob 1
would be replaced by a non-interactive call to a hash function at the 128 bit security level.
Source code to reproduce yourself https://github.com/LLFourn/dlc-verifiable-encryption-non-pairing/tree/ristretto-venc-bench
exact command I used for the above table was:
for i in 2 4 8 16 32 64 128 256 512 1024 2048; do cargo run --release -- -s 128 --n-encryptions $i 2>&1| perl -snE 's/Total elapsed: (\d+).*/$1/g && print "$i ",$_/$i, " $_"' -- -i=$i; done | column -t -N 'n_encryptions,time_per_encryption(ms),time_total(ms)'
[EDIT] I also ran the benchmarks from the "juggling" implementation here:
I just ran the "juggling" protocol implementation benchmarks from: https://github.com/ZenGo-X/centipede/blob/491836c78b73a2d5c8a898b43be1762500006015/benches/v_backup.rs#L47
I got around 138ms per verifiable encryption and i think this is only the prover time. This was on the same machine as the above benchmarks but keep in mind that this is for a non-optimal secp256k1 implementation while my benchmarks were for a fairly optimized ristretto implementation (including batch verification of DLEQ proofs for the protocol).
Another helpful hint I got via email on this topic:
Last but not least, I found another potential verifiable encryption scheme that is rarely discussed in the literature recently, but also seems viable. It also relies on Paillier encryption and may be comparable to CS03. The construction is part of the paper One Round Threshold Discrete-Log Key Generation without Private Channels and is included in Section 3.2 “A Proof of Fairness”.
There are nice ideas in Non-interactive distributed key generation and key resharing by Jens Groth. The verifiable encryption in here is similar to the juggling idea but manages to get away without doing range proofs. Would be interested to see if we can do better than the benchmarks above with this. The paper is targeting a kind of pairing based ID encryption in the target group. I wonder if the verifiable encryption of secret shares can be used independently of this.
I wonder if the verifiable encryption of secret shares can be used independently of this.
See https://twitter.com/Jens_Groth16/status/1524387476701339648, where Jens says:
The pairings are used to build encryption with forward secrecy. So depends on your goal: if forward secrecy is a non-objective you can switch to a pairing-free scheme.
Thanks! Ok this is a little ambiguous I guess. "a pairing-free scheme" i.e. that scheme proposed without pairings or there is no reason to use this scheme outside of the pairing setting. I will try and figure this out!
There's also Verifiable Encryption from MPC-in-the-Head by Akira Takahashi and Greg Zaverucha. It has an implementation on secp256k1: https://github.com/akiratk0355/verenc-mpcith.
@nkohen mentioned that efficient verifiable encryption of discrete logarithms was a real pain point in his research (mine too!). Even though I don't think this problem will ever be "closed" and the problem page could detail tricks for getting around it and the best available schemes to do it. These are: