Standard Techniques
- Fiat-Shamir (FS) Transform
- A technique which turns any constant-round public-coin HVZK protocol (e.g., a sigma protocol) into a non-interactive zero-knowledge proof of knowledge (NIZK PoK) in the random oracle model. Introduced in [FS86]. The technique works as follows: instead of sampling a random challenge, set the challenge equal to the hash of the protocol transcript until that point.
- Fujisaki-Okamoto (FO) Transform
- The FO transform is a technique which "upgrades" a CPA-secure1 PKE to CCA-security in the random oracle model. Introduced in [FO99]. Given the base scheme \(\Pi_E = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\) and two hash functions \(H_1, H_2\) modeled as random oracles, the FO-transformed ciphertext for a message \(m\) is \((\mathsf{Enc}(\mathsf{pk}, r; H_1(r)), H_2(r) + m)\), where \(r\) is sampled uniformly at random.
- Complexity Leveraging
- Forking Lemma
- Leftover Hash Lemma (LHL)
- Union bound
- Naor-Yung Paradigm
-
Another way to "upgrade" a CPA-secure encryption scheme \(\Pi_E = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\) to a CCA1 one using an adaptively-secure NIZK: compute \(c_1 \gets \mathsf{Enc}(pk_1, m)\) and \(c_2 \gets \mathsf{Enc}(pk_2, m)\) and use the NIZK to prove \(c_1, c_2\) encrypt the same message; the CCA-secure ciphertext is \((c_1, c_2, \pi)\).
Further Reading
"CMSC 858K — Advanced Topics in Cryptography: Lecture 7" by Jonathan Katz
-
In fact, the base scheme only needs to satisfy an even weaker security property than CPA-security. ↩