Standard Techniques

Fiat-Shamir (FS) Transform [FS86]

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). Specifically, instead of sampling a random challenge, set the challenge equal to the hash of the protocol transcript until that point. The hash is modeled as a random oracle for the security proof.

Fujisaki-Okamoto (FO) Transform [FO99]

The FO transform is a technique which "upgrades" a CPA-secure¹ PKE to CCA-security. 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.

Chernoff bound

Complexity Leveraging

Forking Lemma

Leftover Hash Lemma (LHL)

Union bound

Naor-Yung Paradigm

Another way (cf. FO transform) 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)\).