# 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]](https://eprint.iacr.org/2023/189).

*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](https://en.wikipedia.org/wiki/Identity-based_cryptography) (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]](https://link.springer.com/chapter/10.1007/3-540-44647-8_13) 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]](https://link.springer.com/chapter/10.1007/3-540-44647-8_13) 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]](https://eprint.iacr.org/2023/189) Gailly, Nicolas, Kelsey Melissaris, and Yolan Romailler. "tlock: practical timelock encryption from threshold BLS." Cryptology ePrint Archive (2023).