Emulating Witness Encryption with Threshold Cryptography and ZKPs

This short document outlines how to emulate witness encryption using threshold cryptography - and more specifically, threshold identity-based encryption (IBE). The ideas presented here are heavily inspired but the tlock construction from [GMR23].

Disclaimer: I have not done a thorough review of the existing literature, if you are aware of existing constructions that work in the same way please let me know!

Background

Witness Encryption. The witness encryption paradigm is the following: given an instance of some hard problem, one can encrypt a message using the instance such that it may only be decrypted by someone who knows the problem's solution (the witness).

Threshold IBE. Identity-based encryption (IBE) is a class of cryptographic primitives where public keys are some publicly known string (the identity) and the private key is derived to match that public key. Originally, IBE schemes relied on a trusted third party to derive the private key.

The Boneh-Franklin IBE scheme [BF01] is of particular interest because private keys are computed by the trusted third party as a BLS signature of the identity.

Because the private keys are BLS signatures, the trusted third party can be replaced by a quorum of signers that each hold a secret share of some (unknown) master secret key. To obtain the private key that corresponds to some identity, a user must request partial signatures from a threshold of the quorum signers.

Pseudo Witness Encryption from Threshold IBE

The emulation idea is the following: messages are encrypted with respect to some randomly generated identity; once a user knows a valid witness, they obtain the identity's private key from the quorum of signers (using ZKPs).

In practice, the system will look like this:

1. Register the puzzle. A puzzle will typically be an arithmetic circuit (e.g. Circom, Noir, etc) or a non-deterministic program (e.g. Cairo). Both of these can be succinctly described either by a verifier key or by a program hash. Once the succinct description is made public, it is also given a random string of characters/bits. This is the puzzle's identity, i.e. the public key!
2. Encrypt. To encrypt "under a certain puzzle", use the puzzle's "identity" and encrypt using the Boneh-Franklin IBE.
3. Obtain partial keys. If Alice has solved the puzzle (i.e. knows the witness for the circuit/program), she can present a zk proof of knowledge to one of the signers. If the proof is valid, the signer provides a partial BLS signature on the puzzle's identity to Alice. Repeat the process with enough signers to match the threshold.
4. Recover the private key and decrypt. Having obtained enough partial signatures to match the threshold, Alice can compute the full BLS signature on the puzzle's identity. This is the private key for the Boneh-Franklin IBE! She can now decrypt.

Some Challenges

• Who chooses the identity for a puzzle? How do we know that the identity-to-puzzle mapping is correctly preserved?
• For on-chain applications, some of the ZKP's public inputs might be chain data (e.g. a block header). Signers from the quorum will need a trustworthy way to access that data.

References

[BF01] Boneh, Dan, and Matt Franklin. "Identity-based encryption from the Weil pairing." Advances in Cryptology—CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001.

[GMR23] Gailly, Nicolas, Kelsey Melissaris, and Yolan Romailler. "tlock: practical timelock encryption from threshold BLS." Cryptology ePrint Archive (2023).