For the context of this answer I will assume that that the author meant to say doubly enhanced TDP, since that's the only path I can currently think of. (See Definition 7)

Constructing CCA secure encryption

The relevant construction is due to Dolev, Dwork, and Naor. It is based on a CPA secure public key encryption scheme, a one-time signature scheme and a non-interactive zero knowledge argument. We'll show how those are instantiated below.

The basic idea of the encryption scheme is that we have $2\ell$ public keys $(\mathsf{pk}_1^0,\dots,\mathsf{pk}_\ell^0)$ and $(\mathsf{pk}_1^1,\dots,\mathsf{pk}_\ell^1)$ of the CPA secure PKE, where $\ell$ is the length of the verification key of the one-time signature scheme. To encrypt a message, we then encrypt the message seperately under $\ell$ public keys, where at position $i$ whether $\mathsf{pk}_\ell^0$ or $\mathsf{pk}_\ell^1$ is used, is determined by the $i$th bit of a fresh verification key of the one-time signature scheme. We then prove using the NIZK that all ciphertexts are encryptions of the same message and finally sign everything with the one-time signature scheme.

The main ideas of the security proof are:

1. Since we have many encryptions of the same message (something enforced by the soundness of the NIZK), we can reduce to CPA security, while still being able to decrypt, because we can use one of the other keys.
2. Any new ciphertext queried to the decryption oracle either uses the same verification key, in which case the adversary would need to forge a signature. Or it uses a different verification key, in which case at least one ciphertext uses a different encryption key from the challenge ciphertext and we are able to use the corresponding decryption key for decryption.

It of course remains to instantiate all those building blocks.

The building blocks.

CPA secure PKE

If a family of trapdoor permutations $\mathcal{F}$ exists then, due to the Goldreich-Levin Theorem there also exists a family of trapdoor permutations with a hardcore predicate. Given a TDP with a hardcore predicate, a simple construction of CPA secure PKE for bits exists, where a a keypair consists of a description of an $f_i\in\mathcal{F}$ for the public key and the corresponding trapdoor for the secret key. A ciphertext is then simply $(f_i(r),\mathsf{hc}_i(r)\oplus m)$ where $r$ is a uniformly chosen element from $f_i$'s domain, $\mathsf{hc}_i$ denotes the hardcore predicate of $f_i$ and $m\in\{0,1\}$.

If necessary, this encryption scheme can be used to construct CPA secure encryption for longer messages by encrypting each bit seperately. The security follows via a standard hybrid argument.

One-Time Signatures

The construction of Lamport gives us an existentially unforgeable one-time signature scheme for fixed length messages from any one-way function. In particular the construction can be therefore be instantiated from a family of trapdoor permuations.

Noninteractive Zero-Knowledge Proofs

NIZK for $\mathsf{NP}$ can be constructed from doubly-enhanced trapdoor permuations. The construction essentially works by performing an $\mathsf{NP}$-reduction to the Hamiltonian Cycle problem and constructing an NIZK for Hamiltonian Cycle. In the original construction in Goldreich's Foundations of Cryptography: Volume 1, Basic Tools it is incorrectly claimed that the construction is instantiable from any TDP, this was corrected in the paper linked above.

Solved by user975 (6,426 )
Feb 26, 2019 at 09:01