The Fujisaki-Okamoto transform

✍️ Written on 2020-06-19 in 1781 words.
Part of cs IT-security pqcrypto

Motivation

Let us consider asymmetric cryptography. We want to encrypt and decrypt a message with a public/secret keypair.

We have an encryption step using the public key of the communication partner and a decryption step using your own secret key. To perform a decryption step, some untrusted communication entity provides the ciphertext (i.e. encrypted message). Since that entity is untrusted, the party can modify this ciphertext and the cryptosystem needs to ensure that no secret data is leaked because faulty ciphertext might be processed. We want to be secure against chosen ciphertext attacks. IND-CCA2 is a security property ensuring this.

In particular, IND-CPA (“chosen plaintext attack”) is the weakest notion of security, we consider. IND-CCA1 (“indistinguishability against a-priori chosen-ciphertext attacks”) is stronger, because the adversary is allowed to access the decryption oracle before the challenge ciphertext is given. IND-CCA2 (“indistinguishability against a-posteriori chosen-ciphertext attacks”) allows the adversary to access the decryption oracle even after the challenge ciphertext is given (but must not use the challenge ciphertext obviously). IND-CCA2 is abbreviated as IND-CCA.

Naturally, in PQCRYPTO all schemes want to achieve IND-CAA2 security. But how? Many schemes are specified only with IND-CPA security in mind and the Fujisaki-Okamoto transform does the remaining part to reach IND-CCA2 security.

The paper

In 1999, E. Fujisaki and T. Okamoto (FO) described a transform of a weak symmetric and asymmetric encryption scheme into a hybrid scheme secure against chosen-ciphertext attacks. After the transform, they also provided a proof of the claimed security properties and implementations for two schemes. Be aware, that the paper is the original one, but we discuss the paper from 2013. It is an update, or as the authors put it:

“This is the full version of the paper by fixing bugs and providing a clean, formal proof associated with a better security bound.”

One difference is that fo99 requires the symmetric encryption scheme to be deterministic and bijective, but such restrictions have been removed in fo13. In this article I am only going to sum up the transform itself.

An IND-CCA2 secure scheme

We define a hybrid encryption scheme Πhy = (Khy, Ehy, Dhy) which will satisfy desired security properties. The scheme is built using a symmetric and an asymmetric encryption scheme.

Asymmetric encryption scheme

Let Πasym = (Kasym, Easym, Dasym) be the asymmetric encryption scheme. Let k be sufficiently large.

  • Kasym is a polynomial-time (in k), probabilistic algorithm. Given 1k, it returns (pk, sk) which is a pair of public/secret keys respectively.

  • Easym is a polynomial-time (in k), probabilistic algorithm. Given public key pk, message x and seed r, it returns ciphertext y.

  • Dasym is a polynomial-time (in k), deterministic algorithm. Given secret key sk and ciphertext y, it returns x := Dsk(y).

Properties:

  • Seed r must be uniformly distributed.

  • The correctness property must be satisfied by Πasym: ∀ k ∈ ℕ ∀ (pk, sk) of Kasym(1k) ∀ x: Dasym(sk, Easym(pk, x; r)) = x.

  • Any adversary cannot entirely decrypt the encryption of a random plaintext. Here “not entirely” means that that ω(log k) bits of the plaintext are infleasible to determine. Thus, if k increases an adversary’s advantage over guessing the decryption vanishes superpolynomial.

Symmetric encryption scheme

Let Πsym = (Ksym, Esym, Dsym) be the symmetric encryption scheme. Let k be sufficiently large.

  • Esym is a polynomial-time (in k), probabilistic algorithm. Given secret key a, message x and seed r, it returns ciphertext y.

  • Dsym is a polynomial-time (in k), deterministic algorithm. Given secret key a and ciphertext y, it returns message x.

Properties:

  • Seed r must be uniformly distributed.

  • The correctness property must be satisfied by Πsym: ∀ k ∈ ℕ ∀ a ∀ x: Dsym(a, Esym(a, x); r) = x.

The hybrid scheme

Let G and H be two hash functions. G maps a finite binary string into the key space of the symmetric scheme. H maps two finite binary strings into the space of random seeds for the asymmetric scheme. In the security proofs, G and H are considered to be random oracles.

Key Generation: KG(1k)

  1. (pk, sk) := Kasym(1k)

  2. Return (pk, sh)

Encryption: Enc(pk, m)

  1. σ samples uniformly from the asymmetric message space

  2. c := Esym(G(σ), m)

  3. e := Easym(pk, σ; H(σ, c))

  4. Return e ∥ c

Decryption: Dec(sk, e ∥ c)

  1. (e, c) := e ∥ c

    1. If admissible, continue

    2. else, return ε

  2. σ' := Dasym(sk, e)

    1. If admissible, continue

    2. else, return ε

  3. a' := G(σ')

  4. h' := H(σ', c)

  5. Test whether e == Easym(pk, σ'; h')

    1. If yes, return Dsym(a', c)

    2. else, return ε

Properties:

  • Fail symbol ε must be the same in all cases

  • Ciphertext “e ∥ c” is emitted into the public and might be modified, right? Consider its manipulation.

    • Then either step 1.2, 2.2, or 5.2. is going to be triggered and thus a failure will be reported.

    • Really? Why can I not create fake “e ∥ c” values? If so, we need to ensure “e == Easym(pk, Dasym(sk, e); H(Dasym(sk, e), c))” which is obviously difficult to achieve and seemingly requires knowledge of sk.

  • The reencryption step in step 5 in the Decryption is computationally expensive in practice.

  • Theorem 6.1 in fo13 is the fundamental theorem proving IND-CCA security

  • As pointed out in section 1.3, this framework is different of the KEM structure we frequently use in post-quantum cryptography. KEMs enable the sender to create encrypted session keys independent of messages and thus generate keys ”on the fly“.

An another interesting quote:

“Any asymmetric encryption scheme can be converted to an asymmetric encryption scheme with ω(log k)-spread, and a one-time secure symmetric encryption scheme can be constructed by extending private key a to a pseudo random string with the same length of message m (via a pseudo random generator) and xoring it with m. Therefore, the above transformation provides a generic conversion from any one-way asymmetric encryption scheme to an IND-CCA asymmetric encryption scheme.”

FO transform continued

We have seen a transform to create IND-CCA2 secure schemes in the random oracle model. But what about the quantum random oracle model? For those unfamiliar with the terminology: the question is “is it secure on quantum computers?”.

The following papers are follow-ups:

  1. Targhi and Unruh [tu] gave a variant of this transform and showed IND-CCA security against a quantum adversary in the quantum random oracle

  2. Hofheinz et al. [hhk] gave a variant which does not imply perfect correctness for the public key encryption scheme. This makes it possible to apply it to LWE schemes.

  3. Jiang et al. [j18] introduced a novel proof technique and presented QROM security reductions.

The lattice-based LPR schemes NewHope, Kyber, and Saber are built on top of [hhk].

Metadata

Outline of the 1999 paper

1. Introduction
1.1. Related work
1.2. Our Results
2. Preliminary
3. Basic Conversion
4. Security Definitions
4.1. Asymmetric Encryption
4.2. Symmetric Encryption
5. Security
5.1. Basic Conversion
5.2. A Variant: Symmetric Encryption is One-Time Padding
6. Implementation
6.1. Implementation for the ElGamal Encryption Scheme
6.2. Implementation for the Okamoto-Uchiyama Scheme
7. Notes on γ-uniformity

Outline of the 2013 paper

Limited to a maximum depth of 2.

1. Introduction
1.1. Security of Encryption Schemes
1.2. Contribution
1.3. Related Work
1.4. Refinement
2. Preliminary
3. Syntax of Encryption Schemes
3.1. Asymmetric Encryption
3.2. Symmetric Encryption
4. Generic Conversion
4.1. Remarks on Decryption
5. Security Definitions
5.1. One-Way Asymmetric Encryption
5.2. Well-Spread Encryption
5.3. Random Oracle
5.4. Chosen-Ciphertext Security (IND-CCA)
5.5. One-Time Secure Symmetric Encryption
6. Security Results
7. Proof of Theorem 6.1
7.1. Outline of Proof
7.2. Details of Reduction

Definitions in the 2013 paper

All of them in section 5 (thus they have identifier “5.N” in the paper):

  1. One-Way Encryption

  2. γ-spread

  3. IND-CCA in RO (“indistinguishability in chosen-ciphertext attacks” in the “random oracle” model)

  4. OT (one-time security)

fo13

Fujisaki, E., & Okamoto, T. (2013). Secure integration of asymmetric and symmetric encryption schemes. Journal of cryptology, 26(1), 80-101.

fo99

Fujisaki, E., & Okamoto, T. (1999, August). Secure integration of asymmetric and symmetric encryption schemes. In Annual International Cryptology Conference (pp. 537-554). Springer, Berlin, Heidelberg.

hhk

Hofheinz, D., Hövelmanns, K., & Kiltz, E. (2017, November). A modular analysis of the Fujisaki-Okamoto transformation. In Theory of Cryptography Conference (pp. 341-371). Springer, Cham.

j18

Jiang, H., Zhang, Z., Chen, L., Wang, H., & Ma, Z. (2018, August). IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited. In Annual International Cryptology Conference (pp. 96-125). Springer, Cham.

tu

Targhi, E. E., & Unruh, D. (2016, November). Post-quantum security of the Fujisaki-Okamoto and OAEP transforms. In Theory of Cryptography Conference (pp. 192-216). Springer, Berlin, Heidelberg.