Verifiable encryption of discrete logarithms

[LLFourn]

@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:

1. MuSig-DN: https://eprint.iacr.org/2020/1057.pdf (relatively efficient but complex)
2. Cut and choose: https://link.springer.com/content/pdf/10.1007/3-540-44448-3_25.pdf (simple but inefficient -- works for verifiably encrypting the witness for relation with a sigma protocol from memory)
3. "practical" verifiable encryption of DLOG: https://eprint.iacr.org/2002/161.pdf (needs trusted setup for Paillier modulus but more efficient and elegant than (2)).
4. Castagnos and Laguillaumie verifiable encryption: https://eprint.iacr.org/2015/047.pdf, https://eprint.iacr.org/2020/084.pdf (absolute moon math what is even a "class group of an imaginary quadratic field" and no one really knows if this is secure or not).

[jonasnick]

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?

[LLFourn]

@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).

[LLFourn]

Another cut and choose approach worth noting (I've not read it yet): https://eprint.iacr.org/2020/1563.pdf

[burdges]

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?

[LLFourn]

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.

[burdges]

Afaik signature verifiers are always assumed honest because verifiers could always take action without the signature.

[LLFourn]

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.

[burdges]

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.. ;)

[LLFourn]

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!).

[LLFourn]

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).

[LLFourn]

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”.

[LLFourn]

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.

[real-or-random]

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.

[LLFourn]

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!

[real-or-random]

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.