CCA-Secure Hybrid Encryption in Correlated Randomness Model and KEM Combiners
Abstract
A hybrid encryption (HE) system is an efficient public key encryption system for arbitrarily long messages. An HE system consists of a public key component called key encapsulation mechanism (KEM), and a symmetric key component called data encapsulation mechanism (DEM). The HE encryption algorithm uses a KEM generated key k to encapsulate the message using DEM, and send the ciphertext together with the encapsulaton of k, to the decryptor who decapsulates k and uses it to decapsulate the message using the corresponding KEM and DEM components. The KEM/DEM composition theorem proves that if KEM and DEM satisfy well-defined security notions, then HE will be secure with well defined security.
We introduce HE in correlated randomness model where the encryption and decryption algorithms have samples of correlated random variables that are partially leaked to the adversary. Security of the new KEM/DEM paradigm is defined against computationally unbounded or polynomially bounded adversaries. We define iKEM and cKEM with respective information theoretic computational security, and prove a composition theorem for them and a computationally secure DEM, resulting in secure HEs with proved computational security (CPA and CCA) and without any computational assumption. We construct two iKEMs that provably satisfy the required security notions of the composition theorem. The iKEMs are used to construct two efficient quantum-resistant HEs when used with an AES based DEM. We also define and construct combiners with proved security that combine the new KEM/DEM paradigm of HE with the traditional public key based paradigm of HE.
Index Terms:
Post-quantum cryptography, Hybrid encryption, Correlated randomness model, Key Encapsulation Mechanism.I Introduction
A hybrid Encryption (HE) system is a public-key encryption system with two components: a public-key key encapsulation mechanism (KEM) that generates a pair where is a secret key and is the encapsulation of under the KEM’s public-key, and an efficient symmetric key component called data encapsulation mechanism (DEM) that will use to efficiently encrypt an arbitrary long message , and generate the ciphertext . Decryption algorithm has the private key of KEM and takes as input. It decapsulates to find and uses it to decrypt , and recover . This is an attractive construction that effectively provides a computationally efficient public key encryption system for arbitrarily long messages, by using the computationally expensive public key KEM once, and encrypt long messages by employing a computationally efficient DEM that can be constructed using efficient and standardised secure symmetric key ciphers such as AES (Advanced Encryption Standard) in one of the known modes of operation such as counter mode. Cramer and Shoup [1] defined KEM/DEM paradigm, formalized security of KEM and DEM, and proved a general composition theorem that shows that if KEM is CCA (chosen ciphertext attack) secure, and DEM is a one-time symmetric key encryption with CCA security, then the resulting hybrid encryption system will be CCA secure (see section III for definitions). This level of security is known as the gold standard of security for modern encryption systems. KEM/DEM paradigm has been widely studied and more refined notions of security for KEM have been proposed and the corresponding composition theorems for HE have been proved [2, 3]. There is a large body of work on the construction of KEM [4, 5, 6, 3, 7] that are all public key based and rely on computational assumptions. KEM has been widely used for securing communication over the Internet including as part of TLS (Transport Layer Security) [8].
Quantum-resistant security of an HE system requires quantum-resistant security of KEM and DEM. Shor’s invention of efficient quantum algorithms for integer factorization and discrete logarithm problems [9] has made KEM constructions that rely on these assumptions, and constitute all existing KEMs in practice, insecure. KEM has been one of the first cryptographic primitives that has been standardized by NIST (National Institute of Standards and Technology) post-quantum cryptography standardization effort [10, 11]. DEM component of an HE system uses symmetric block cipher algorithms such as AES, for which the main known quantum attack is the speed-up for secret key search that is offered by the Grover’s algorithm [12]. This speed-up however can be compensated by doubling the length of the secret key and so the research on quantum-resistant security of KEM/DEM paradigm has primarily focused on the quantum-resistant security of KEM.
Information theoretic key agreement. Our main observation is that KEM is effectively a one-way secret key agreement (OWSKA) algorithm, a widely studied topic in information theoretic cryptography, but with a somewhat different definition of security.
Information theoretic key agreement was first introduced by Maurer [13] and Ahlswede [14] (independently) in what is known as the source model, where Alice and Bob have samples of two correlated random variables and that are distributed according to and are partially leaked to Eve through the variable . The probability distribution is public but the concrete samples , and are private to Alice, Bob and Eve, respectively. There is a long line of research on deriving fundamental results on the possibility of secret key agreement, bounds on rate and capacity of information theoretic key agreement in this model and its variations, and providing constructions for optimal (capacity achieving) systems [15, 16, 17, 18], together with the finite length analysis of the constructions [16, 19].
Information theoretic key agreement has also been considered in fuzzy extractor (FE) setting [20] where Alice and Bob, respectively, have samples and of the same randomness source, satisfying where is a distance function. FE setting can be seen as a special case of the source model where and are samples of the same source with a guaranteed upper bound on the distance between the two samples, and there is no initial information leakage to the adversary (). One of the main application areas of FE is key establishment using sources that employ biometric data as the source of randomness. Security model of FE is in part influenced by capturing attacks on biometric systems in practice [21, 22, 23, 24, 25].
A third important direction in the study of information theoretic key agreement is quantum key distribution (QKD) protocols that use quantum theoretic assumptions as the basis of security. Protocols such as BB84 QKD [26], use communication over a quantum channel to generate correlated random variables between two parties, which is later reconciled into a shared secret string that is partially leaked to Eve, and is used to extract a shared (close to) random key between the two parties.
In all above settings, there is an initial correlated randomness between Alice and Bob that is leveraged to establish an information theoretically secure shared secret key. Definitions of security in these settings range from security against a passive eavesdropping adversary [13, 14, 15, 16, 19, 20, 22, 25], to security against an active attacker with different levels of access to the system and communication channels [27, 28, 29, 24]. In all cases, security is against a computationally unbounded adversary and so the protocol remains secure against an adversary with access to a quantum computer.
Extending secure key agreement protocols with information theoretic security, to the establishment of secure message transmission channels using KEM/DEM approach, will allow the wealth of research and development in information theoretic key agreement protocols to be used in quantum-resistant cryptographic systems.
Cryptographic combiners combine cryptographic schemes with the same functionality into a single scheme with the guarantee that the combined scheme is secure if at least one of the component schemes is secure. Combiners mitigate the risk of possible design flaws, attacks and breaks of each of the component cryptographic schemes, and provide robustness for security systems. Combiners for public key KEMs have been introduced, their security properties have been formalized, and secure constructions for KEM combiners have been proposed [30, 31]. Cryptographic combination of public key KEM with KEMs with information theoretic security will seamlessly integrate the new KEMs into the existing applications of KEM and expand the range of KEMs that are available in designing cryptographic systems.
I-A Our Results
We propose KEM/DEM paradigm in correlated randomness model (which in cryptography, is also referred to as preprocessing model111This is because correlated randomness is generated in an initialization stage and before the actual algorithms start.). We define security and prove a composition theorem that relates security of the HE to the security of the KEM and DEM components.
Notation: To make distinction between traditional public key KEMs and KEMs in the new setting, we use pKEM to denote a KEM scheme in preprocessing model, and reserve iKEM and cKEM to refer to the information theoretic and computationally secure versions of pKEM.
The new paradigm allows KEM and DEM components to be defined with security against a computationally unbounded, or computationally bounded adversary. While one can define pKEM and associated DEM with security against information theoretic and computational adversaries, our focus is on the design of an efficient quantum-resistant encryption system (HE) that can be used in practice, and so we consider composition of iKEMs (KEMs with information theoretic security) and DEMs with computational security. We design two iKEMs with proved security in our proposed security models, one with security against passive adversaries, and one with security against active adversaries that tamper with the communication channel. The two iKEMs will have CEA (Chosen Encapsulation Attack) and CCA (Chosen Ciphertext Attack) security, respectively, and when used with a DEM with appropriate security will result in an HE with CPA (Chosen Plaintext Attack) and CCA security, respectively. We also define and construct cryptographic combiners that combine a public key KEM and an iKEM. More details below.
KEM/DEM in correlated randomness model. A KEM in correlated randomness model is a tuple of algorithms denoted by , where is a correlation generation algorithm that takes a distribution , generates correlated random samples , and side information for Alice, Bob, and Eve, respectively, and privately delivers the samples to the corresponding parties; is an encapsulation algorithm that uses the private sample of Alice and generates a pair , where is a random session key for DEM, and is an (encapsulation) ciphertext; is a decapsulation algorithm that uses and the private sample of Bob to recover .
Security of KEM is defined using key indistinguishability games between a challenger and an adversary (Figure 3). The adversary’s power is modelled by its query access to the encapsulation oracle and decapsulation oracle. An oracle implements its corresponding algorithm and has access to the private information of the party that legitimately uses the algorithm, and so the encapsulation and decapsulation oracles have the private random samples of Alice and Bob, respectively. The oracles correctly answer queries of the adversary as defined by the security game. We define these security games similar to the corresponding ones in public key KEMs [3, 1], with the difference that in public key KEM, the encapsulation algorithm has a public key for encapsulation and so the adversary can freely access the encapsulation algorithm, while in pKEM, the encapsulation algorithm uses the private sample of Alice, and the adversary can query the encapsulation oracle. A (chosen encapsulation attack (CEA) ) query to the encapsulation oracle results in an output . Decapsulation queries, also referred to as chosen ciphertext attack (CCA) queries, are the same as in public-key KEMs and allow the adversary to verify validity of a chosen pair against the decapsulation algorithm when using the private sample of Bob, and the response is either a key or . The two security notions of IND-CEA (indistinguishability against CEA) and IND-CCA (indistinguishability against CCA) capture indistinguishability of the final key from a uniform random string of the same length, when the attacker has access to CEA, or both CEA and CCA, queries respectively. Adversary can be computationally unbounded (information theoretic), or its computation be bounded by a polynomial function of the system’s security parameter (computational). The number of allowed queries in the two cases are different: for information theoretic adversary the number of allowed queries is a predefined constant (system parameter), while for computational adversary, it is a polynomial function of the security parameter of the system. We use iKEM to denote information theoretically secure pKEMs where the adversary is computationally unbounded, and use cKEM to refer to computationally secure pKEM, where the adversary is computationally bounded. This latter is to distinguish computationally secure pKEMs from traditional public key KEMs, both providing security against a polynomial time adversary but cKEM using an initial correlated randomness instead of a public key.
We define DEM and its security against a computationally bounded adversary, the same as DEMs in public-key setting [1]. DEM security notions are variations of IND-CPA (indistinguishability against CPA) security and IND-CCA (indistinguishability against CCA) security for encryption systems. DEM security can also be defined against a computationally unbounded adversary. Our definition of computationally secure DEM however is motivated by our goal of constructing quantum-resistant HE schemes that use a short (constant length) key to encrypt arbitrary long messages.
Composition Theorem. The following composition theorem (which is a restatement of Theorem 2) proves (computational) security of an HE system that is obtained by the composition of a pKEM (iKEM or cKEM) and a computationally secure DEM.
Theorem.
Let and be a cKEM and an iKEM, respectively, and denote a one-time symmetric key encryption scheme that is compatible with the corresponding or . Then the following composition results hold for the hybrid encryption in preprocessing model, against a computationally bounded adversary with access to the following queries for HE: encapsulation and decapsulation queries when is used, and polynomially bounded number of queries for both types of queries, when is used.
IND-OT and IND-OTCCA refer to indistinguishability security for one-time secure DEM with CPA and CCA security, respectively (see Definition 3).
In all cases, security of the hybrid encryption system is against a computationally bounded adversary. In (1) and (2), is secure against a computationally bounded adversary who has access to polynomially bounded number of encapsulation and decapsulation queries, and the final HE satisfies CPA and CCA definition of security of computationally secure encryption systems (see Definition in section IV-A). In (3) and (4) however, is secure against a computationally unbounded adversary with access to a constant number of encapsulation () and decapsulation () queries, and the final HE is bounded CPA and CCA secure, respectively [1].
Constructions of iKEM. In section V, we consider the case that the correlated randomness is obtained by repeated sampling a public distribution, and where for . We have , , respectively, with the corresponding private samples, , and .
We propose two constructions of iKEM for Satellite scenario, Construction 1 and Construction 2, that provide IND-CEA and IND-CCA security, respectively. Both constructions are based on the OWSKA in [19], where Alice sends a single message to Bob over a public authenticated channel. The message includes information that will be used for information reconciliation that enables Bob to recover Alice’s sample with some leakage, and the description of a hash function to be used for key extraction. The OWSKA construction uses two universal hash functions and for the two tasks. This construction was first proposed in [32] for an iKEM with IND-CEA security for encapsulation queries (and no decapsulation queries), and used two strongly universal hash functions, and . Construction 1 has the same security properties but uses universal hash families. The construction slightly modifies the initialization process of iKEM that improves the length of the established key without affecting security. The encapsulation ciphertext in Construction 1 is , where and are random strings that are used in (reconciliation) and (extraction) respectively. Our observation is that , the seed for that is used for reconciliation, can stay the same in all instances of the protocol and so can be generated and distributed to all parties (including to Eve) during initialization.
We prove security of this construction for any pair and of universal hash functions with appropriate parameters.
The second construction is a pKEM with IND-CCA security that removes the need for a public authenticated channel between Alice and Bob, and provides security against an adversary who can tamper with the KEM ciphertext. We define INT-CTXT (ciphertext integrity) for pKEM (Definition 6) that requires any tampering with the cipherext to be detectable by Bob. Theorem 1 proves that in preprocessing model, a KEM that is IND-CEA and INT-CTXT secure, is IND-CCA secure. Our IND-CCA secure Construction 2 requires a specific construction of (whereas in Construction 1, can be any universal hash function).
To show IND-CCA security of the Construction 2, we show that it is an IND-CEA and INT-CTXT secure KEM, and so it provides IND-CCA security. The construction is based on the OWSKA construction in [29] that provides security against an active adversary. Our iKEM construction slightly modifies the reconciliation message of the OWSKA, revises and corrects its security analysis, and obtains new parameters for the system. The encapsulation ciphertext in Construction 2 is given by which includes as part of the input to also. The hash function is designed to provide information reconciliation to allow Bob to securely recover Alice’s sample and serves as a MAC (message authentication code) to protect integrity of the encapsulation ciphertext. The decapsulation algorithm checks the validity of a received encapsulation ciphertext by computing the hash function using the candidate key that is derived for Alice and the received , and compares the result with . We bound the success probability of the adversary in forging a valid encapsulation ciphertext by bounding the guessing probability of the secret keys that are used in the encapsulation and decapsulation algorithms.
In Theorem 5, we prove integrity of the ciphertext (IND-CTXT) of the iKEM Construction 2 against an active adversary with access to one encapsulation and decapsulation queries. The construction in section V-E can be extended to provide security against queries. The final extracted key length however will be reduced (almost) linearly with higher . We note that security against encapsulation queries, is only necessary if the same sample is used in multiple instances of HE, and not required in applications such as QKD where each message transmission will use its dedicated quantum communication round (and so new values of , and ).
KEM Combiners. We define KEM combiners that securely combine a pKEM (iKEM or cKEM) and a public key KEM. In this combination, if at least one of the component KEMs is an iKEM, the resulting KEM will be an iKEM and secure against a computationally unbounded adversary (for fixed number of encapsulation/decapsulation queries) and so a quantum-resistant KEM. The resulting KEM will also be computationally secure with polynomial (in security parameter) number of encapsulation/decapsulation queries, as long as at least one of the component KEMs is computationally secure (public-key KEM or cKEM).
We give two blackbox constructions of KEM combiners for an iKEM and a public key KEM that satisfy the above security properties (information theoretic security for fixed number of queries and computational security for polynomial number of queries as long as the corresponding component KEM is secure). The constructions are based on the XOR combiner and PRF-then-XOR combiner of [30] that were proposed for public key KEMs. We extend these constructions to our setting where one of the KEMs is an iKEM. The XOR combiner XORs the output keys of the component KEMs. The construction maintains IND-CEA security of the resulting KEM (Theorem 6) but will not result in an IND-CCA KEM when the component KEMs are IND-CCA secure. The PRF-then-XOR combiner uses PRFs (Pseudorandom functions). A PRF is a family of functions indexed by a secret key, that guarantees that for a uniformly chosen key, the function output is indistinguishable from the output of a random function for an adversary who can see the evaluations of the function on an adaptive adversary chosen set of values (see Definition 8). We use two types of PRFs: with statistical indistinguishability for constant number of queries, and computational indistinguishability for polynomial number of queries (see Definition 8).
The PRF-then-XOR combiner XORs the outputs of a set of PRFs, each associated with one of the KEMs, where the PRF uses the secret key that is the output of the KEM, and computes the value of the function on an input that is the concatenation of the ciphertexts of all other KEMs (except the one). We require PRF with statistical indistinguishability for iKEMs, and with computational indistinguishability for computational KEMs. Theorems 6 and 7 respectively, prove IND-CEA, and IND-CCA security of the resulting KEMs, and relate their security to the security of the component KEMs and the PRFs.
Discussion. Security of KEM/DEM paradigm in correlated randomness model does not rely on any (unproven) computationally hard problem. Hybrid encryption system in this model is neither a public key, nor a symmetric key encryption system. Rather, it relies on the communicating parties secret inputs (that we refer to as key) that are not identical, but are correlated, and can be partially leaked. The final security of the HE is computational. The paradigm provides flexibility to consider security against computationally unbounded or bounded adversaries for each component (KEM and DEM). Our focus on iKEM and computationally bounded DEM is motivated by real-life application of HE in quantum-resistant systems.
II Related work
KEM/DEM paradigm has been widely used in public key based hybrid encryption for encrypting arbitrary length messages with proved security. The approach was first formalized by Cramer and Shoup [1] who proved that that a CCA secure KEM and one-time secure CCA symmetric key encryption system (DEM) result in a CCA secure hybrid encryption system. The relation between different security notions of KEM and DEM, and the resulting hybrid encryption system is given in [2]. There are numerous generic and specific constructions of public-key KEM including [33, 34, 35]. There are also constructions of KEM that use hardness assumptions for which there is no known quantum algorithm. This includes constructions [36, 37, 10] that use LWE (Learning with Error) and other lattice based assumptions. Quantum-resistant secure KEM has been part of NIST post-quantum competition [38] and CRYSTALS-Kyber is the standardized quantum-resistant KEM [10]. KEM combiners are studied in [30, 39, 31, 40].
All above works are in public-key setting. KEM/DEM in correlated randomness setting was introduced in [32] where authors considered passive adversaries with access to encapsulation queries, only. We extend this work in a number of ways. We consider security against active attackers and prove a general composition theorem for CCA security of HE, and construct a CCA secure iKEM that results in a CCA secure ( quantum-resistant) HE. We also construct combiners for iKEM and public-key KEM, that when used with a computationally secure DEM, result in a provably secure CCA encryption system.
Information theoretic key agreement in source model was first studied by Maurer [13], and Ahlswede and Csiszár [14], and has led to a long line of research on this topic and more specific related topics including information reconciliation [41, 42, 43, 44]. OWSKA uses a single message from Alice to Bob to establish a shared key [15, 17, 18, 19]. Key establishment in correlated randomness model with security against active adversary was studied in [45, 28, 46, 47].
Combining cryptographic primitives was first considered by Shannon who studied security of an encryption system that is obtained by combining multiple encryption systems, and suggested “weighted sum” and “product ciphers” to combine secrecy systems to achieve stronger security [48]. Combiners have been studied for numerous cryptographic primitives including encryption systems [49, 50] and hash functions [51]. Robust combiners for cryptographic systems were studied by Herzberg [52] and later extended [40] to include parallel and cascade constructions, where constructions for various primitives including OWF (One Way Functions), signatures and MACs are given. A robust combiner for a cryptographic primitive takes multiple candidate schemes that implement , and combine them into a single scheme such that the resulting scheme remains secure even if some of the schemes become insecure. In a -robust combiner [40] security is guaranteed if at least out of constructions remains secure.
Combiners for public key KEM was studied in Giacon et al. [30], and with security against quantum adversaries were considered and constructed in Bindel et al. [31].
Correlated randomness model has been used in cryptography to remove impossibility results, including key establishment in presence of computationally unbounded adversaries [13], oblivious transfer [53] and multi-party computation (MPC) protocols [54, 55, 56]. Correlated randomness for key agreement can be realized in settings such as biometric authentication, transmission over noisy (wiretapped) channels, and using communication over quantum channel.
III Preliminaries
We denote random variables (RVs) with upper-case letters, (e.g., ), and their realizations with lower-case letters (e.g., ). The probability distribution associated with a random variable is denoted by , and the conditional probability distribution associated with given is denoted by . Shannon entropy of an RV is defined by . The min-entropy of a random variable with probability distribution is . The average conditional min-entropy [21] is defined as, The statistical distance between two random variables and with the same domain is given by . For an -bit variable , we use to denote the block of bits from the th bit to the th bit in For , denotes an RV with uniform distribution over . Vectors are denoted using boldface letters, e.g. is a vector of RVs, and its realization is given by .
To define closeness of two families of distributions that are indexed by using the notion of indistinguishability (statistical and computational), we use two classes of functions called and as defined in [57]. The class of negligible functions , contains all functions where for every positive polynomial , such that , where is the set of non-negative real numbers. A set is a class of small functions if: it is closed under addition, and a function implies that all functions with are also in the set .
Universal hash functions have been used to generate close to uniform RVs from non-uniform entropy sources with sufficient min-entropy. This is proved in Leftover Hash Lemma [58]. We use a variant of Leftover Hash Lemma, called Generalized Leftover Hash Lemma [21, Lemma 2.4].
Definition 1 (Universal hash family).
A family of hash functions is called a universal hash family if , , we have , where the probability is over the uniform choices of .
Lemma 1 (Generalized Leftover Hash Lemma [21]).
Let be a universal hash family. Then for any two variables and , applying on can extract a uniform random variable whose length satisfies the following , where is chosen uniformly from .
For , the unary representation of given by , is used to specify the running time of the algorithm as a function of . For efficient algorithm, the running time is a polynomial in . We use as the security parameter of the system.
An algorithm that takes inputs , and generates the output , while having access to oracles , by .
KEM and DEM. Hybrid encryption and the notion of KEM was first introduced and formalized in [1]. Properties of KEM and DEM were formally defined in [2].
Definition 2 (KEM distinguishing advantage [2]).
Let be an adversary and be a KEM with security parameter and key space . For , the key indistinguishability (kind) advantage of is defined as
| (1) |
where the distinguishing game for is defined in Figure. 1.
Game
Oracles and
A KEM is IND-CPA (CCA1 or CCA2) secure if for all polynomial-time adversaries that corresponds to , or , the advantage function (in equation 1) is negligible in . In this paper, we only consider CCA2 security, and refer to it as CCA-security.
Data Encapsulation Mechanism (DEM) is a symmetric key encryption algorithm. We use the following definition in [2].
Definition 3 (Security of DEM: IND-OT, IND-OTCCA, IND-CPA, IND-CCA1, IND-CCA2 [2]).
Let
be a DEM scheme with security parameter and key space ,
and let be an adversary. For and ,
the indistinguishability (ind) advantage of is defined as
| (2) |
where the distinguishing game for is defined in Figure. 2.
Game
Oracles and
A DEM is for if for all polynomial-time adversaries , , where is a non-negative negligible function in .
The formalization and construction of HE in [1] uses one-time symmetric key encryption schemes with a specific security definition (adversary with access to decryption oracle only). The one-time symmetric key encryption that is defined below, is a DEM with OTCCA security.
A one-time symmetric key encryption with security parameter and the key space consists of two deterministic222Thus, for all and , . algorithms such that: i) the encryption algorithm encrypts a message under a uniformly chosen key and outputs a ciphertext , and ii) the decryption algorithm that decrypts the ciphertext using the key , and either recovers the message , or outputs a special rejection symbol .
Security of is tailored for its application in hybrid encryption systems, and matches the OTCCA security in Definition 3.
IV KEM in correlated randomness model
A KEM in correlated randomness model (also called preprocessing model) has two phases. In the initialization phase that is also called offline phase, Alice, Bob and Eve, respectively, privately receive , and , that is obtained by sampling a public joint distribution (e.g. an efficient probabilistic experiment). In the online phase Alice and Bob use their private values in the encapsulation and decapsulation algorithms, respectively, to obtain a shared key. Here represents Eve’s initial information about Alice and Bob’s samples.
Definition 4 (KEM in Preprocessing Model (pKEM)).
KEM in preprocessing model (pKEM) with security parameter , joint distribution , and
key space , is a triple of algorithms
, where is a randomized generation algorithm that produces private samples that are privately given to the corresponding parties, is the randomized encapsulation algorithm that outputs a pair of ciphertext and key for and , and is the deterministic decapsulation algorithm that outputs a key or a symbol (for an invalid ciphertext).
Correctness. A pKEM is -correct if for all and
,
, where
is a small function of , and and
the probability is over all random coins of and .
Security of pKEM. We consider three types of attacks: One-time attack (OT), Chosen Encapsulation Attack (CEA), and Chosen Ciphertext Attack (CCA), specified by access to the encapsulation and decapsulation oracles and , respectively. The corresponding security notions are denoted by IND-OT, IND-CEA and IND-CCA, respectively. An encapsulation query to is a call to generate a key and ciphertext pair and does not take any input from the adversary. For a query to , the attacker chooses a ciphertext , and receives the corresponding key , or .
Definition 5 (pKEM distinguishing advantage).
Let be a pKEM and let be a distinguisher. The preprocessing key indistinguishability advantage (pkind) is denoted by and defined as follows:
| (3) |
where the distinguishing game for a random bit , is defined in Figure. 3.
Game Oracles and
For , a pKEM is -IND-ATK secure if is bounded by for , respectively, where is a small function of . The adversary may be computationally bounded, or unbounded. We call the KEM in the former case a computational KEM (cKEM), and in the latter case an information theoretic KEM (iKEM), both in preprocessing model. For a secure cKEM, and for a secure iKEM .
Remark 1 (iKEM with bounded-query security).
The number of queries when the adversary is computationally bounded (Definition 5) is a polynomial in . We define -bounded adversaries for iKEM, where the number of queries is bounded by a known predetermined polynomial in . -bounded CCA security for public-key encryption has been considered in [59] to overcome impossibility results that hold for general CCA encryption. In iKEM, the bound on the number of queries is because of the adversary’s unlimited computation power. Indistinguishability security against a -bounded CEA adversary with access to at most encapsulation queries is denoted by IND--CEA security. Similarly, IND--CCA security is defined against an attacker that is -bounded for encapsulation queries and -bounded for decapsulaton queries, where the queries can be asked according to the distinguishing game of Figure. 3.
IV-1 Ciphertext Integrity (INT-CTXT) in preprocessing model.
Ciphertext integrity (INT-CTXT) requires that the adversary’s tampering of the ciphertext be detected by a high probability. Ciphertext integrity was defined by Bellare et al. [60] for symmetric key encryption systems and it was proved that in symmetric key encryption systems, IND-CPA security together with INT-CTXT security implies IND-CCA security ([60, Theorem 3.2]). In [61], the notion of ciphertext existential unforgeability is proposed and a composition theorem ([61, Theorem 1]) is proved that shows existential unforgeability of the ciphertext together with CPA security of the encryption system, leads to CCA security of the encryption system. In the following we define integrity for KEM in preprocessing model, and prove a composition theorem to obtain CCA security.
Definition 6 (pKEM ciphertext integrity).
A pKEM with security parameter , initial joint distribution , and the key space provides ciphertext integrity (INT-CTXT), if for all initial correlated samples (generated by ), and all adversaries with access to the encapsulation and decapsulation queries, the key integrity advantage defined as is upper bounded by , a small function of , where the integrity game is given in Figure. 4.
Game
We define INT--CTXT for an adversary with encapsulation and decapsulation queries, where the number of allowed queries depends on the adversary being computationally bounded or unbounded.
The following theorem shows that a pKEM that is IND-CEA and INT-CTXT secure is IND-CCA secure.
Theorem 1.
Let be a pKEM with security parameter and the input distribution . For an adversary in the CCA key distinguishing game , there are adversaries and for and the CEA key distinguishing game , respectively that satisfy the following:
If makes encapsulation and decapsulation queries, makes encapsulation and decapsulation queries to its decapsulation oracles, and makes queries to its encapsulation oracle, we have the following.
-
1.
For computationally bounded adversaries
-
2.
For computationally unbounded adversaries,
where .
Proof sketch. For the proof of the first part, we use a sequence of two games and played by the distinguisher , where is uniformly chosen from . The first game is the CCA distinguishing game ( in Figure 3). The second game, , is the same as except for its decapsulation oracle that always outputs , an empty string. We bound the CCA advantage of the adversary by bounding the advantage of these games. The proof of the second part uses the same sequence of games, but is against a computationally unbounded adversary. See the complete proof in Appendix A. ∎
IV-A Hybrid encryption in Preprocessing Model
We define hybrid encryption (HE) and KEM/DEM paradigm for preprocessing model, where during the offline phase, Alice, Bob and possibly Eve, receive correlated private inputs, and during the online phase, pKEM generates the key that will be used by DEM.
Definition 7 (Hybrid encryption in preprocessing model).
For
a security parameter , let
be a pKEM and be a DEM with
the same key space , for each .
A hybrid encryption in preprocessing model denoted by is defined as given in Figure 5.
| Return |
| If : | |
| Return | |
| Return | Else: |
| Return |
Security of hybrid encryption in preprocessing model. is a private input encryption system, where Alice and Bob’s private inputs are not the same but are correlated. We use indistinguishability security and consider three security notions depending on the attacker’s access to the encryption and decryption oracles (during the online phase): i) no oracle access (IND-OT), ii) access to encryption queries (IND-CPA), and iii) access to encryption and decryption queries, where access in the latter two cases will be before and after receiving the challenge ciphertext (IND-CCA). The number of queries for computationally bounded adversaries is polynomial in , and for unbounded adversary is a predetermined polynomial in . The security notions in the latter case for encryption queries, and for encryption and decryption queries are denoted by IND--CEA and IND--CCA, respectively. The security games are similar to the security games in symmetric key encryption schemes: the adversary (after making queries according to the game type) generates two equal length (in bits) messages and , and for a random , receives . It then (after making enough queries) outputs a bit . The indistinguishability advantage for a computationally bounded adversary and , and computationally unbounded adversary and , are , where , when and when . The advantage is bounded by , where for adversary and for adversary .
The following theorem is the counterpart for Theorem in [1] in preprocessing model. Theorem 7.2 in [1] considers only public key KEM. We prove the following theorem for both computational and information-theoretic KEMs (cKEM and iKEM, respectively). The theorem is proved for two types of query accesses for the adversary. One can consider similar types of results for other KEMs as defined in [2].
Theorem 2 (Hybrid encryption composition theorem).
For a security parameter , let,
– be an -correct cKEM in preprocessing model, and
– be an -correct iKEM in preprocessing model,
and let denote a one-time symmetric key encryption scheme with security parameter that is compatible with the corresponding or . Then,
Security of the hybrid encryption scheme in all above cases is with respect to a computationally bounded adversary.
Proof Sketch. We prove the theorem for the first two cases; the proofs of the last two cases will be similar. We use a sequence of three games , , and , all played by a computationally bounded adversary (distinguisher) . is identical to the distinguishing game of the hybrid encryption in preprocessing model. differs from in its decapsulation oracle response. For the challenge HE ciphertext , where is the ciphertext output of and is generated by , the response will be as follows. If the decryption query and (and ), the response will be the key that was generated by the encapsulation oracle (corresponding to ); otherwise the decryption oracle of uses to decrypt . Finally, differs from in using a uniformly sampled key instead of the key generated by the cKEM. The differences between the success probabilities of the first two, and the last two games are bounded by the failure probability of encapsulation, and the indistinguishability advantage of the of the . The complete proof is given in Appendix B.
Note that in cases (3) and (4) of the theorem above, the iKEM is secure against a computationally unbounded adversary. Therefore, as long as the symmetric encryption scheme is quantum safe, the resulting hybrid encryption scheme will be quantum-resistant.
V Instantiating iKEM
In this section, we construct two iKEMs in correlated random model and prove their security properties. In the first construction (Construction 1) the adversary can only query the encapsulation oracle. In the second construction (Construction 2) however, the adversary can query both the encapsulation and decapsulation oracles.
For both constructions we consider the probabilistic experiment that underlies the generation of correlated triplet to be times independent repetition of a probabilistic experiment, and so , and respectively, where , where , and . Alice, Bob and Eve privately receive realizations of the random variables , and , respectively.
V-A A CEA secure construction
An IND--CEA secure iKEM allows adversary to query tha encapsulation oracle, and can be used to construct an IND--CPA secure hybrid encryption where the adversary has access to encryption queries. The construction slightly modifies the IND--CEA secure iKEM construction in [32] to increase the length of the extracted key, without compromising its security.
Construction 1 (CEA secure iKEM.).
We define an iKEM , as follows:
Let be the public joint distribution as defined above, and for all .
Let and be two universal hash families. Let the ciphertext and key space be defined as and , respectively. The iKEM ’s three algorithms are described in Algorithm 1, Algorithm 2 and Algorithm 3 respectively. The parameters and depend on the security parameter and their relationship with other system parameters is given in section V-B.
In (Algorithm 3), we use a parameter to define a set . This is a decapsulation algorithm parameter that depends on , the correlation between the RVs and , and is chosen using the required correctness (and security) of the derived key. Higher correlation between the RVs and leads to smaller for the same correctness level. The details of parameter derivation for and are in [19] and are also repeated in the proof of Theorem 4 which uses the same reconciliation algorithm to obtain from . Theorem 3 derives that the length of the extracted key gives is upper bounded or , the extracted key length by constructing a protocol, improving the results in [19].
Note that , in addition to the random samples, generates a random seed of appropriate size that is distributed to the parties over public authenticated channels.
V-B Security analysis of iKEM construction 1
The protocol is based on the OWSKA in [19]. The parameters and are derived in [19, Theorem 2] such that the error probability of the protocol will be upperbounded by the correctness (reliability) parameter . The iKEM construction 1 uses the same reconciliation information in all queries. That is, in the encapsulation ciphertext , the value of that is used by Bob to recover recover (reconciliation information) will be the same in all queries. Each query however will include a new value of and so a new final key. In our construction 1, the randomness is generated during the initialization and published (or sent to Bob over a public authenticated channel). The CEA secure iKEM protocol construction in [32] however updates both parts of in each query, which results in higher information leakage from and shorter length for the final key. In appendix I we have reproduced the protocol in [32] for ease of reference.
The following lemma for conditional min-entropy is proved in [29, Lemma 2], and will be used in Theorem 3.
Lemma 2.
[29] For any independently and identically distributed according to , it holds that
, where and
Theorem 3 (IND--CEA).
The iKEM described in construction 1 establishes a secret key of length
that is -indistinguishable from random by an adversary with access to encapsulation queries, where (i.e. -IND--CEA secure).
Proof sketch. The response to an encapsulation query leaks some information about Alice’s private sample and this reduces the length of the final shared key. The response to the th encapsulation query is a key and ciphertext pair , where and is the same in all responses. Here and are RVs over and , respectively.
After seeing , the remaining min-entropy entropy of using [21, Lemma 2.2(b)], will be lowerbounded by . Since is the same in all responses, after queries, the min-entropy entropy of will be which will be used to bound the key distinguishing advantage of the adversary. The complete proof of the theorem is in Appendix E. ∎
V-C A CCA secure construction
In this section, we modify the IND--CEA secure iKEM construction 1 in Section V-A to provide stronger security. More specifically, we extend the construction to an IND--CCA secure iKEM which provides security against an adversary with access to encapsulation and decapsulation oracle queries. Access to decapsulation queries models an adversary who can tamper with the encapsulation ciphertext, and see the result of the decapsulation algorithm on its manufactured fraudulent encapsulation ciphertext.
To provide security against such adversaries we use the notion of ciphertext integrity (INT-CTXT) that requires the iKEM to satisfy definition 6 and guarantee that any tampering with will be detected by the decapsulation algorithm, with a high probability.
The iKEM construction 2 provides ciphertext integrity. According to Theorem 1, the IND--CEA security and -ciphertext integrity (INT--CTXT) of iKEM together lead to IND- -CCA security, where , which is the strongest and widely used notion of security for encryption systems. The construction is based on the construction 1 but modifies its ciphertext, and requires the hash function to be a universal hash function with additional properties.
Construction 2 (CCA secure iKEM.).
We define an iKEM, , as follows:
Let the joint distribution of the three random variables , and be described by the distribution that is obtained as product of independent copies of the distribution , where , , and for . The joint distribution is used to generate the correlated random samples of .
Let be a universal hash family, and denote a second universal hash family with extra properties as constructed in Section V-E.
Let and denote the ciphertext and key domains, respectively.
The hash function parameters and are functions of the security parameter and together with the other iKEM parameters are derived in Theorem 4 and Theorem 5 in section V-D. The parameter is defined and used the same as in Construction 1. Note that the initialization phase is only used to generate and securely distribute the private inputs of participants. The seed will be generated independently for each instance of the protocol and will be protected against the adversary’s tampering through the additional properties of .
| (4) |
V-C1 Relation with CEA secure iKEM
To provide CCA security in Construction 2, we modify Construction 1 and use the seeds of both hash functions as input to , which is randomly selected from a function family that in addition to being a universal hash function family, can be interpreted as an information theoretic MAC with partially leaked secret key , that detects tampering with the seeds and seed . More specifically, is a universal hash function family with seed that is evaluated on the input , and a MAC with key that is evaluated on the message . The construction of is given in Section V-E, and proof of CCA security of iKEM is given in Section V-E.
V-D Security analysis of iKEM construction 2
We prove security properties of the construction using two main theorems. The proofs also determine parameters that must be used to guarantee the required levels of correctness and security. Theorem 4 proves reliability and IND--CEA security of the iKEM. Theorem 5 proves ciphertext integrity of the construction, and together with Theorem 4 proves IND--CCA security of the construction.
Theorem 4 (reliability and IND--CEA).
Let and satisfy,
Then the iKEM in construction 2 establishes a secret key of length that is -correct and -indistinguishable from random by an adversary with access to encapsulation queries, where (i.e. -IND--CEA secure).
Proof sketch.
Correctness (reliability). We first determine the values of and that guarantee correctness (reliability) for the given , and then prove security. Decapsulation algorithm searches the set that is defined by and , to find a unique value that satisfies were is the received hash value. The algorithm fails if at least one of the following events occurs:
We use [62, Theorem 2] and the property of universal hash function to bound these two probabilities and prove that with appropriate choice of parameters, the sum of these two probabilities is bounded by .
Security: Key indistinguishability. The response to and encapsulation query, , leaks information about the secret key . We use [21, Lemma 2.2(b)] to estimate the remaining min-entropy entropy of as,
where and are RVs over and respectively. By bounding the total leakage of queries, we bound the key distinguishing advantage of the adversary.
The complete proof of the theorem is in Appendix F. ∎
V-E Ciphertext integrity of construction 2
To achieve ciphertext integrity, we use the construction of a universal hash function described below.
Construction of . For a vector of components denoted by , let and , where and .
We define a universal hash family with seed space
and input space , where , , for some suitable ,
and . Let .
We write as a vector of elements where each element is from , where is an even number satisfying:
. (We use padding with 1’s for and , when needed.). Let with and .
The hash function with seed and input is given by,
| (5) | |||
Lemma 3.
is a universal hash family.
Proof is in Appendix G.
Proving ciphertext integrity. In Theorem 5, we prove that the construction 2 is an iKEM that satisfies ciphertext integrity as given in Definition 6, for and . The proof of the theorem relies on Lemmas 4, 5, and 6.
Lemma 4.
Consider a joint distribution , and let denote a random variable over a set of size at most . Then,
Proof.
∎
Let denote the best success probability of the adversary in guessing a key for the encapsulation algorithm 5, such that it is considered valid by the decapsulation algorithm 6. That is, for (the unknown) decapsulation key .
Lemma 5.
The success probability of constructing a ciphertext that is accepted by the decapsulation algorithm is bounded as follows.
1.
| (6) |
2. Assuming equality in the above bound,
Proof.
1. The encapsulation algorithm uses the key , and the decapsulation algorithm uses the key , both unknown to the adversary. To be accepted by the decapsulation algorithm, a guessed value must belong to the set defined by the decapsulation algorithm 6. That is for the unknown . The adversary may use two types of guessing strategies to find a candidate : guess Alice’s key from such that it belongs to for the unknown , or guess a Bob’s key , and choose one of the that satisfy defined with respect to . The best success probabilities of these two types of guessing strategies are denoted by and , respectively.
We have
| (7) | |||||
The encapsulation and decapsulation algorithms are deterministic and probabilities are over the probability space .
To bound , we note that each will be accepted by all that satisfy .
This means that the adversary’s success probability that a ciphertext that is constructed using a guessed key be accepted by decapsulation algorithm that uses the unknown key , corresponds to the probability of the set of sample points (key pairs) where
which can be computed by the adversary (conditional distribution ). Therefore, to each we associate a weight that is the acceptance probability of the ciphertext by some . The best guess for will be by finding the element of with the highest acceptance probability,
(This also determines the value (i.e. ) that can be used to construct .) (We note that the acceptance probabilities attached to elements of do not form a probability distribution on .)
To find using , we note that each will accept all Alice’s key values s that satisfy .
This attaches an acceptance probability to each that is the total probability of ciphertexts being accepted by a when Alice’s key is not known, and is obtained by summing probabilities of the set of sample points (key instances) as follows
Thus, the best guess for Bob’s key for accepting a ciphertext when Alice’s key is unknown, is given by
| (8) |
Therefore,
| (9) |
2. Simplifying the bound: Consider the case that the expression 6 holds with equality. That is the value that results in the highest success probability for successful ciphertext forgery can be obtained by using one of the two key guessing strategies outlined above to guess a key and compute . This is true because any ciphertext that is accepted by the decapsulation algorithm must be well formed, and correspond to the evaluation of a polynomial defined by using a key that satisfies . A computationally unbounded adversary can always find the roots of such a polynomial, and so any forged ciphertext can be generated by choosing a key that satisfies the required condition, and using the encapsulation algorithm. This is somewhat similar to the notion of plaintext awareness in computational security [63, 64], where it is assumed that the adversary can create ciphertexts for which it is able to “extract” the corresponding plaintext.
Thus we have,
We then use the following approximation in terms of marginal distributions of and .
Let and be the and values that maximize the expressions,
and
, respectively, and and denote marginal distributions of and .
Since , we have
Note that
| (10) | |||
| (11) |
This is true because the RHSs of 10 and 11 are maximizing over all values of and , respectively.
Therefore,
| (12) |
∎
Note. We will use the above calculation for conditional distributions that takes into account all the adversary’s information about , in particular after one query, that is ,
| (13) |
In the following we will use and recall the following notations: is written as and , and where denotes concatenation of two vectors; and , suitably padded, is written as a sequence where , , and where and .
Lemma 6.
The lemma has two parts.
-
(i)
The number of that satisfies the following two equations (in ) for two values of and :
(14) (15) is at most .
In these equations, , , and
. -
(ii)
Let and satisfy and , respectively, where and are defined as in . Assume for some , and . Then the number of that satisfies the following equations:
(16) (17) is at most where, is a non-zero vector and
.
Proof.
From equation 14 and equation 15, we have
| (18) |
where arithmetic operations are in the corresponding binary extension finite fields.
If , then
as . Therefore, the degree of the equation 18 in is at most . The term takes on each element of the field at most times as varies. This is because the degree of the polynomial is and so there are at most values of that satisfy equation 18.
Equation 14, for fixed and , is a polynomial of degree three, and hence for each value of , will be satisfied by at most three values of , and so there are at most values of that satisfy both equations 14 and 18.
If , we use equation 18 to express as a polynomial in ,
and by substituting it in equation 14, obtain
for some polynomial of degree at most . Therefore, there are at most values of that satisfy this equation. From equation 18, for each value of , there is a unique that satisfies the equation.
Therefore, in both cases, there are at most values of that satisfy both the equation 14 and equation 18.
This is an equation in two indeterminates and of degree at most . The equation 17 is also an equation in two indeterminants and of degree at most . Since , by Bézout’s theorem [65, 66], recalled in Section H, we have that there are at most values of (i.e. ) that satisfy both equation 19 and equation 17.
∎
Theorem 5 (Ciphertext integrity (INT--CTXT)).
Proof.
The proof uses Lemma 4, 5 and 6. We first provide an outline of the main proof steps, and then expand each step.
Let denote the maximum success probability of the adversary that has access to (i.e. response to an encapsulation query) and constructs a forged ciphertext where . That is, is the highest success probability of constructing that is accepted by the decapsulation algorithm Algorithm 6. Let denote the expected value of over all query responses , and denote the expected final success probability with one encapsulation, and decapsulation query.
The upper bound on will be obtained in three steps: (1) bounding , (2) bounding by finding the expectation over the random variables corresponding to the adversary’s information, that is the received response , and finally (3) bounding that takes into account the decapsulation queries.
Step 1. Bounding .
The adversary has the key and the ciphertext pair , where is computed using Alice’s secret key and given by the equation 5 (section V-E). The ciphertext will be accepted by the decapsulation algorithm ikem.Dec() (Algorithm 6) using Bob’s key with probability at least .
A forged ciphertext that is accepted by the decapsulation algorithm must pass the test for a unique that is found by the decapsulation algorithm using Bob’s key . Thus a ciphertext that is accepted by the decapsulation algorithm must be generatable by the generation Algorithm 5 using some (guessed) key. We call ciphertexts that satisfy as well-formed.
We assume the adversary can only make a well-formed by using the encapsulation algorithm (Algorithm 5) for a guessed key. That is there is no shortcut algorithm can be used by the adversary to generate a new well-formed ciphertext from other available information. This assumption holds if the encapsulation algorithm is modelled as a random function (random oracle) for the generation of .
The encapsulation algorithm is deterministic, and so can be obtained by,
-
1.
Finding , the best guessing probability of a key that satisfies for Bob’s (unknown) . We use Lemma 5, part , that assumes the best guessing probability is by using one of the two direct guessing strategies outlined in the lemma.
-
2.
Take into account the number of that results in the same that is constructed using the key . An upper bound on this number, denoted by , is obtained in Lemma 6.
Step 2. : Expectation over the adversary’s view. For fixed , let , , , , , be random variables corresponding to , , , , and respectively, where the randomness is over . The adversary has derived from , guesses , and generates the ciphertext where .
We consider two cases: the adversary’s guess where is Alice’s key, and the adversary’s guessed key where for the unknown . Let the success probabilities of the adversary in generating a ciphertext corresponding to the above two cases be and respectively. The decapsulation algorithm searches for a unique element in and so only one of the above two cases will occur, and the success probability of the adversary in generating a will be
| (20) |
where probability is over .
Computing . The success probability of forging a ciphertext, given a key and ciphertext pair , is:
The known ciphertext and the forged ciphertext must satisfy equation 14 and equation 15, respectively, with . Note that if , then it must be that and because is a single value, and will reject, which is a contradiction. Therefore, we only need to consider the case that .
Since the adversary is given a key and ciphertext pair , from Lemma 5 part (2) and equation 13, we have that the adversary can guess with probability at most
| (21) |
where is the attacker’s initial side information. Since and , from Lemma 4, we have
| (22) |
Therefore,
| (23) | ||||
| (24) | ||||
| (25) | ||||
| (26) | ||||
| (27) |
where equation 24 is obtained from subtracting the two equations within the probability expression in equation 23; equation 25 follows from equation 21; equation 26 follows from equation 22. The expectation is taken over the distribution of .
Computing .
Let . The forged ciphertext will be,
| (28) | |||||
Let is constructed using . We can write for some (unknown) vector and . Replacing and with and , respectively in equation 5, we obtain
| (29) |
From Lemma 6 part , the number of (i.e. ) that satisfy both the equation 29 and equation 28 is at most .
Let , and denote the random variables corresponding to , and respectively.
Define .
| (30) | |||||
| (31) | |||||
| (32) |
where equation 30 follows from Lemma 5 part (2) and equation 13 since the adversary is given a key and ciphertext pair ; equation 31 follows from Lemma 4.
Therefore, from equations 20, 27 and 32, we have that after one encapsulation query, the probability that an adversary will be able to forge a ciphertext is at most
Step 3: : Including decapsulation queries. For each decapsulation query, the adversary receives either a key, if the forged ciphertext is accepted by the decapsulation algorithm, and or , otherwise. The adversary succeeds with the first query that is successful. After unsuccessful decapsulation queries, the size of the set of possible guesses will reduce by . Thus, after one encapsulation query and decapsulation queries, is bounded by
Corollary 1 (CCA security).
The iKEM construction 2 is an IND--CCA secure iKEM.
Proof.
According to Theorems 4 and 5 the iKEM construction 2 is both IND--CEA secure with encapsulation queries, and INT--CTXT secure with one encapsulation and decapsulation queries. Then according to Theorems 1, the iKEM is also IND--CCA secure with decapsulation queries and zero encapsulation query. Therefore, if the parameters , and are chosen to satisfy both Theorems 4 and 5, then the iKEM construction 2 is also IND--CCA secure. ∎
VI KEM combiners for iKEM
Cryptographic combiners provide robustness for cryptographic schemes against possible flaws or security breaks of the component schemes. Combiners for KEM were introduced by Giacon et al. [30] who defined a framework for combining two or more public-key KEMs. Our goal in this section is to extend their framework to allow pKEMs to be combined with public key KEMs. This is well-motivated because iKEMs are post-quantum secure and so a much wider set of KEMs with post-quantum security becomes available to the system designers.
In this section, we first define combiners for combining pKEMs (i.e. in correlated randomness model) with a public-key KEM, and then give constructions and prove their security. We focus on combiners for iKEM and public key KEMs because of subtleties of combining security of two tyoes of schemes: security against computationally unbounded and computationally bounded adversaries.
Combiners. Using the framework of Giacon et al. [30],
for security parameter , we define a core function for combining an iKEM
with correlation generating distribution , output key space , and ciphertext space , with
a public-key KEM with public-key space , output key space , and ciphertext space .
The combiner
is a KEM with three algorithms ; ; and for key generation, encapsulation and decapsulation, respectively, that uses a core function, , to generate a session key in the key space , using the algorithms defined in Figure. 6.
| Return | |
|---|---|
| Return |
| Return |
One can also define combiners for other combinations of component KEMs, i.e. two iKEMs , two cKEMs, an iKEM and a cKEM, and a cKEM and public key KEM, with private samples ) that generates a pair where key and ciphertext , and let KEM be a public-key with public and private key pair that generates
Construction 3 (XOR combiner.).
Let be an iKEM with with private samples , and be a public-key KEM with public and private key pair that generate keys and , respectively, and let . The combiner with an XOR core function , outputs when none of ’s for is , and outputs otherwise.
The following theorem shows that for a given , the XOR combiner retains the IND--CEA security of the component iKEM. The proof is given in Appendix C.
Theorem 6.
For security parameter , let be an IND--CEA secure iKEM that generates , and be a public-key KEM with the same security parameter that generates of the same length. Consider a combiner KEM using the XOR core function that combines and , and generates the key . For a computationally unbounded adversary , there exists a computationally unbounded adversary , such that
In the above theorem, computational security of follows [30, Lemma 1] as an iKEM can be seen as an insecure KEM for polynomial number of queries.
CCA security. The XOR combiner cannot retain the IND--CCA security of the component iKEM (with similar reasoning as [30, Lemma 2]).
We show the PRF-then-XOR core function in [30] can be used to combine an iKEM with a public-key KEM such that, in addition to resulting in a secure public-key KEM, if the PRF output is indistinguishable from uniform by a computationally unbounded and query-bounded adversary, the resulting KEM will be an IND--CCA secure iKEM.
Definition 8 (PRF and its security).
Let be a security parameter. We use as an argument for values to make dependence on as a parameter, explicit. A family of functions , where , and , respectively, are finite sets corresponding to key, input and outputs, is a secure PRF, if the advantage of an adversary in the distinguishing game of PRF, defined in Figure. 7, satisfies the following:
-
(i)
Computationally secure PRF: For any computationally bounded adversary with access to queries, where is a polynomial, the advantage of the adversary defined as, , is a negligible function of .
-
(ii)
Information theoretic PRF: For any computationally unbounded adversary with access to queries, where is a pre-defined polynomial in , the advantage of the adversary defined as,
, is a small function of i.e. .
The games (or the games ) are chosen using a uniformly random bit .
PRF distinguishing game. The PRF distinguishing game for a function family where , and , respectively, are finite sets corresponding to key, input and output, is defined in Figure 7.
Game Oracle
Construction 4 (PRF-then-XOR combiner.).
Let be the security parameter. Consider an iKEM with private samples that generates a pair where key and ciphertext , and let KEM be a public-key with public and private key pair that generates a pair where key and ciphertext . Further, let and be two PRFs with information theoretic and computational security, respectively.
The combiner with the core function PRF-then-XOR outputs when neither nor is , and outputs otherwise.
Theorem 7.
In Construction 4, let and be an IND--CCA secure iKEM and an IND-CCA secure KEM, respectively, and let and be two PRFs, with security against a computationally unbounded adversary with queries, and a computationally bounded adversary with polynomial number of queries, respectively. Then for any
(a) computationally bounded distinguisher , there exists computationally bounded adversaries and for games and , respectively, such that,
| (33) |
(b) computationally unbounded distinguisher , there exists a computationally unbounded adversaries and for games and , respectively, such that
Proof sketch. The proof for a computationally bounded adversary will follow the approach of Theorem 3 in [30], noting that the iKEM will loose its security when the number of queries exceed the design parameter of iKEM after repeated queries. The proof for a computationally unbounded adversary is given in Appendix D. ∎
Instantiating PRF for construction 4.
To construct a PRF with security against a computationally unbounded adversary with access to
-queries,
we can use a -independent hash function. An example construction using polynomials over finite fields is given in [67, Section 4.1].
The drawback of this PRF however is its large key size. We leave more efficient constructions of information-theoretic PRF for the required number of queries for future work.
Note that security of PRF in the combiner construction 4 against computationally unbounded adversaries, does not depend on the number of encapsulation queries to the combiner. Intuitively, this is because in each encapsulation query to combiner, the component iKEM generates a fresh uniform and independent key which is used as the secret key in PRF , and so the output of PRF is independent of previous encapsulation and decapsulation queries.
VI-A Composing a “combined” KEM with a DEM
Security requirements of DEM in Theorem 2 is identical to Cramer et. al’s [1, Theorem 7.2] and so the same DEM can be used for secure hybrid encryption for information theoretically secure KEM and public key KEM. The KEM combiner’s output will be used with a secure DEM (example construction is given in [1]), and depending on the security of the component KEM, will result in a secure hybrid encryption with one of the following security properties:
-
(i)
If the component KEM is a secure iKEM with IND--CEA (IND--CCA) security, the combiner’s output key will be secure against computationally unbounded attackers, and the resulting hybrid encryption provides security according to Theorem 2, cases (3) and (4).
-
(ii)
If an IND-CEA (IND-CCA) cKEM is used as a component in the preprocessing model, the combiner’s output will be secure against computationally bounded adversary, and the resulting hybrid encryption will be secure according to Theorem 2, cases (1) and (2).
-
(iii)
If the public-key KEM is secure, the resulting hybrid encryption provides security according to [1, Theorem 7.2].
VII Concluding remarks.
KEM/DEM in the preprocessing model is a natural and useful extension of KEM/DEM paradigm that does not require public keys and so computational assumptions. The paradigm is defined for information theoretic and computational security. That is each of the two components KEM and DEM, and the final HE, may be defined against a computationally unbounded or bounded adversaries. We prove a general composition theorem for KEM and DEM when security of KEM is against a computationally unbounded or bounded adversary, and security of DEM is against a computationally bounded adversary. We focused on these combinations of adversaries to obtain a key efficient HE. Defining DEM with information theoretic security will lead to HE constructions with high secret key requirement (i.e. essentially similar to one-time-pad).
We also defined and constructed combiners with provable security that combine KEMs in preprocessing model with public-key KEMs. Efficient and secure construction of core functions for combining iKEM and public key KEMs that retain CCA security of component KEMs is an interesting direction for future work.
An HE in preprocessing model is a private key encryption where the private keys are correlated random strings (not symmetric), and so security notions are defined similar to symmetric key encryption systems. Combiners for iKEM and public-key KEM widens the range of possible KEMs, and allow fuzzy data to be used for communication with provable security.
Construction of KEMs with computational security in preprocessing model for specific is an interesting direction for future work.
References
- [1] R. Cramer and V. Shoup, “Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack,” SIAM J. Comput., vol. 33, no. 1, pp. 167–226, 2003. [Online]. Available: https://doi.org/10.1137/S0097539702403773
- [2] J. Herranz, D. Hofheinz, and E. Kiltz, “Some (in)sufficient conditions for secure hybrid encryption,” Inf. and Computat., vol. 208, no. 11, pp. 1243–1257, 2010. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S089054011000132X
- [3] E. Kiltz, “Chosen-Ciphertext Security from Tag-Based Encryption,” in Theory of Cryptogr. Conf. Springer, 2006, pp. 581–600. [Online]. Available: http://link.springer.com/10.1007/11681878{_}30
- [4] K. Kurosawa and Y. Desmedt, “A new paradigm of hybrid encryption scheme,” in Annu. Int. Cryptol. Conf. Springer, 2004, pp. 426–442.
- [5] J. Herranz, D. Hofheinz, and E. Kiltz, “The kurosawa-desmedt key encapsulation is not chosen-ciphertext secure.” IACR Cryptol. ePrint Arch., vol. 2006, p. 207, 2006.
- [6] M. Abe, R. Gennaro, K. Kurosawa, and V. Shoup, “Tag-kem/dem: A new framework for hybrid encryption and a new analysis of kurosawa-desmedt kem,” in Advances in Cryptology – EUROCRYPT 2005. Springer Berlin Heidelberg, 2005, pp. 128–146.
- [7] H. Shacham, “A cramer-shoup encryption scheme from the linear assumption and from progressively weaker linear variants,” Cryptology ePrint Archive, Paper 2007/074, 2007, https://eprint.iacr.org/2007/074. [Online]. Available: https://eprint.iacr.org/2007/074
- [8] P. Schwabe, D. Stebila, and T. Wiggers, “Post-quantum tls without handshake signatures,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, ser. CCS ’20. New York, NY, USA: Association for Computing Machinery, 2020, p. 1461–1480. [Online]. Available: https://doi.org/10.1145/3372297.3423350
- [9] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124–134.
- [10] J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehle, “CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM,” in 2018 IEEE Eur. Symp. Secur. Priv. (EuroS&P), IEEE. IEEE, apr 2018, pp. 353–367. [Online]. Available: https://ieeexplore.ieee.org/document/8406610/
- [11] N. I. of Standards and T. group, “Post-quantum cryptography standardization,” https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions, 2022, national Institute of Standards and Technology.
- [12] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, ser. STOC ’96. New York, NY, USA: Association for Computing Machinery, 1996, p. 212–219. [Online]. Available: https://doi.org/10.1145/237814.237866
- [13] U. Maurer, “Secret Key Agreement by Public Discussion from Common Information,” IEEE Trans. Inf. Theory, vol. 39, no. 3, pp. 733–742, may 1993. [Online]. Available: https://ieeexplore.ieee.org/document/256484/
- [14] R. Ahlswede and I. Csiszar, “Common Randomness in Information Theory and Cryptography. I. Secret Sharing,” IEEE Trans. Inf. Theory, vol. 39, no. 4, pp. 1121–1132, 1993. [Online]. Available: http://ieeexplore.ieee.org/document/243431/
- [15] T. Holenstein and R. Renner, “One-way secret-key agreement and applications to circuit polarization and immunization of public-key encryption,” in Annu. Int. Cryptol. Conf. Springer, 2005, pp. 478–493.
- [16] T. Holenstein, “Strengthening Key Agreement using Hard-core Sets,” Ph.D. dissertation, ETH Zurich, 2006.
- [17] J. M. Renes, R. Renner, and D. Sutter, “Efficient One-Way Secret-Key Agreement and Private Channel Coding via Polarization,” in Int. Conf. Theory Appl. Cryptol. Inf. Secur., ser. LNCS, K. Sako and P. Sarkar, Eds. Springer, 2013, vol. 8269, pp. 194–213. [Online]. Available: http://link.springer.com/10.1007/978-3-642-42033-7{_}11
- [18] R. A. Chou, M. R. Bloch, and E. Abbe, “Polar Coding for Secret-Key Generation,” IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 6213–6237, nov 2015. [Online]. Available: http://ieeexplore.ieee.org/document/7217814/
- [19] S. Sharifian, A. Poostindouz, and R. Safavi-Naini, “A capacity-achieving one-way key agreement with improved finite blocklength analysis,” in Int. Symp. on Inf. Theory and Its Appl., ISITA 2020. IEEE, 2020, pp. 407–411. [Online]. Available: https://ieeexplore.ieee.org/document/9366148
- [20] Y. Dodis, L. Reyzin, and A. D. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” in Advances in Cryptol. - EUROCRYPT 2004,, ser. LNCS, C. Cachin and J. Camenisch, Eds., vol. 3027. Springer, 2004, pp. 523–540. [Online]. Available: https://doi.org/10.1007/978-3-540-24676-3_31
- [21] Y. Dodis, R. Ostrovsky, L. Reyzin, and A. D. Smith, “Fuzzy extractors: How to generate strong keys from biometrics and other noisy data,” SIAM J. Comput., vol. 38, no. 1, pp. 97–139, 2008. [Online]. Available: https://doi.org/10.1137/060651380
- [22] X. Boyen, “Reusable cryptographic fuzzy extractors,” in Proceedings of the 11th ACM Conf. on Computer and communications security, 2004, pp. 82–91.
- [23] X. Boyen, Y. Dodis, J. Katz, R. Ostrovsky, and A. Smith, “Secure remote authentication using biometric data,” in Annual Int. Conf. Theory Appl. Cryptographic Techniques. Springer, 2005, pp. 147–163.
- [24] Y. Dodis, B. Kanukurthi, J. Katz, L. Reyzin, and A. D. Smith, “Robust fuzzy extractors and authenticated key agreement from close secrets,” IEEE Trans. Inf. Theory, vol. 58, no. 9, pp. 6207–6222, 2012. [Online]. Available: https://doi.org/10.1109/TIT.2012.2200290
- [25] R. Canetti, B. Fuller, O. Paneth, L. Reyzin, and A. Smith, “Reusable fuzzy extractors for low-entropy distributions,” in Annual Int. Conf. Theory Appl. Cryptographic Techniques. Springer, 2016, pp. 117–146.
- [26] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” in Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, 1984, pp. 175–179.
- [27] U. Maurer, “Information-theoretically secure secret-key agreement by not authenticated public discussion,” in EUROCRYPT ’97, 1997, pp. 209–225.
- [28] U. Maurer and S. Wolf, “Secret-Key Agreement over Unauthenticated Public Channels-Part II: The Simulatability Condition,” IEEE Trans. Inf. Theory, vol. 49, no. 4, pp. 832–838, apr 2003. [Online]. Available: http://ieeexplore.ieee.org/document/1193794/
- [29] S. Panja, S. Jiang, and R. Safavi-Naini, “A one-way secret key agreement with security against active adversaries,” in 2023 IEEE International Symposium on Information Theory (ISIT), 2023, pp. 2314–2319.
- [30] F. Giacon, F. Heuer, and B. Poettering, “KEM Combiners,” in IACR Int. Work. Public Key Cryptogr. Springer, 2018, pp. 190–218. [Online]. Available: http://link.springer.com/10.1007/978-3-319-76578-5{_}7
- [31] N. Bindel, J. Brendel, M. Fischlin, B. Goncalves, and D. Stebila, “Hybrid key encapsulation mechanisms and authenticated key exchange,” in Int. Conf. Post-Quantum Cryptogr. Springer, 2019, pp. 206–226.
- [32] S. Sharifian and R. Safavi-Naini, “Information-theoretic key encapsulation and its application to secure communication,” in 2021 IEEE Int. Symp. on Inf. Theory (ISIT). IEEE, 2021, pp. 2393–2398.
- [33] A. W. Dent, “A Designer’s Guide to KEMs,” in IMA Int. Conf. on Cryptogr. and Coding. Springer, 2003, pp. 133–151. [Online]. Available: http://link.springer.com/10.1007/978-3-540-40974-8{_}12
- [34] K. Bentahar, P. Farshim, J. Malone-Lee, and N. P. Smart, “Generic Constructions of Identity-Based and Certificateless KEMs,” J. Cryptol., vol. 21, no. 2, pp. 178–199, apr 2008. [Online]. Available: http://link.springer.com/10.1007/s00145-007-9000-z
- [35] K. Haralambiev, T. Jager, E. Kiltz, and V. Shoup, “Simple and Efficient Public-Key Encryption from Computational Diffie-Hellman in the Standard Model,” in IACR Int. Work. Public Key Cryptogr. Springer, 2010, pp. 1–18. [Online]. Available: http://link.springer.com/10.1007/978-3-642-13013-7{_}1
- [36] J. Ding, X. Xie, and X. Lin, “A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem.” IACR Cryptol. ePrint Archive, vol. 2012, p. 688, 2012.
- [37] C. Peikert, “Lattice Cryptography for the Internet,” in Int. Work. Post-Quantum Cryptogr. Springer, 2014, pp. 197–219. [Online]. Available: http://link.springer.com/10.1007/978-3-319-11659-4{_}12
- [38] M. Albrecht, C. Cid, K. Paterson, C. Tjhai, and M. Tomlinson, “Nts-kem — round 2 submission,” https://csrc.nist.gov/CSRC/media/Presentations/nts-kem-round-2-presentation/images-media/nts-kem.pdf, 2019, national Institute of Standards and Technology.
- [39] T. Matsuda and J. C. N. Schuldt, “A New Key Encapsulation Combiner,” in 2018 Int. Symp. Inf. Theory Its Appl. (ISITA). IEEE, 2018, pp. 698–702.
- [40] D. Harnik, J. Kilian, M. Naor, O. Reingold, and A. Rosen, “On Robust Combiners for Oblivious Transfer and Other Primitives,” in Annu. Int. Conf. Theory Appl. Cryptographic Techniques. Springer, 2005, pp. 96–113. [Online]. Available: http://link.springer.com/10.1007/11426639{_}6
- [41] C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy Amplification by Public Discussion,” SIAM J. Comput., vol. 17, no. 2, pp. 210–229, apr 1988. [Online]. Available: http://epubs.siam.org/doi/10.1137/0217014
- [42] R. Renner and S. Wolf, “Smooth Renyi Entropy and Applications,” in 2004 IEEE Int. Symp. Inf. Theory (ISIT)., IEEE. IEEE, 2004, pp. 232–232. [Online]. Available: http://ieeexplore.ieee.org/document/1365269/
- [43] T. Holenstein and R. Renner, “On the Randomness of Independent Experiments,” IEEE Trans. Inf. Theory, vol. 57, no. 4, pp. 1865–1871, apr 2011. [Online]. Available: http://ieeexplore.ieee.org/document/5730579/
- [44] M. Tomamichel, J. Martinez-Mateo, C. Pacher, and D. Elkouss, “Fundamental finite key limits for information reconciliation in quantum key distribution,” in 2014 IEEE Int. Symp. on Inf. Theory, 2014, pp. 1469–1473.
- [45] U. Maurer and S. Wolf, “Secret-Key Agreement over Unauthenticated Public Channels-Part I: Definitions and a Completeness Result,” IEEE Trans. Inf. Theory, vol. 49, no. 4, pp. 822–831, apr 2003. [Online]. Available: http://ieeexplore.ieee.org/document/1193793/
- [46] R. Renner and S. Wolf, “The exact price for unconditionally secure asymmetric cryptography,” in Adv. Cryptol. - EUROCRYPT 2004, C. Cachin and J. L. Camenisch, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 109–125.
- [47] B. Kanukurthi and L. Reyzin, “Key Agreement from Close Secrets over Unsecured Channels,” in Annu. Int. Conf. Theory Appl. Cryptographic Techniques. Springer, 2009, pp. 206–223. [Online]. Available: http://link.springer.com/10.1007/978-3-642-01001-9{_}12
- [48] C. E. Shannon, “Communication Theory of Secrecy Systems*,” Bell System Technical Journal, vol. 28, no. 4, pp. 656–715, oct 1949. [Online]. Available: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=6769090
- [49] S. Even and O. Goldreich, “On the power of cascade ciphers,” in Adv. Cryptol. Boston, MA: Springer US, 1985, vol. 3, pp. 43–50. [Online]. Available: http://link.springer.com/10.1007/978-1-4684-4730-9{_}4
- [50] U. M. Maurer and J. L. Massey, “Cascade Ciphers: The Importance of Being First,” J. Cryptol., vol. 6, no. 1, pp. 55–61, mar 1993. [Online]. Available: http://link.springer.com/10.1007/BF02620231
- [51] M. Fischlin and A. Lehmann, “Security-amplifying combiners for collision-resistant hash functions,” in Advances in Cryptology - CRYPTO 2007, A. Menezes, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 224–243.
- [52] A. Herzberg, “Folklore, practice and theory of robust combiners,” Cryptology ePrint Archive, Paper 2002/135, 2002, https://eprint.iacr.org/2002/135. [Online]. Available: https://eprint.iacr.org/2002/135
- [53] D. Beaver, “Precomputing oblivious transfer,” in Annu. Int. Cryptol. Conf. Springer, 1995, pp. 97–109.
- [54] R. Bendlin, I. Damgård, C. Orlandi, and S. Zakarias, “Semi-homomorphic Encryption and Multiparty Computation,” in Annu. Int. Conf. Theory Appl. Cryptographic Techniques. Springer, 2011, pp. 169–188. [Online]. Available: http://link.springer.com/10.1007/978-3-642-20465-4{_}11
- [55] Y. Ishai, E. Kushilevitz, S. Meldgaard, C. Orlandi, and A. Paskin-Cherniavsky, “On the power of correlated randomness in secure computation,” in Theory of Cryptogr. Conf. Springer, 2013, pp. 600–620.
- [56] S. Garg, Y. Ishai, and A. Srinivasan, “Two-round mpc: information-theoretic and black-box,” in Theory of Cryptogr. Conf. Springer, 2018, pp. 123–151.
- [57] B. Pfitzmann and M. Waidner, “A model for asynchronous reactive systems and its application to secure message transmission,” in Proc. 2001 IEEE Symp. Secur. Privacy. S&P 2001. IEEE, 2000, pp. 184–200.
- [58] R. Impagliazzo, L. A. Levin, and M. Luby, “Pseudo-Random Generation from One-Way Functions,” in Proc. 21st Annu. ACM Symp. Theory Comput. -STOC ’89. New York, New York, USA: ACM Press, 1989, pp. 12–24. [Online]. Available: http://portal.acm.org/citation.cfm?doid=73007.73009
- [59] R. Cramer, G. Hanaoka, D. Hofheinz, H. Imai, E. Kiltz, R. Pass, A. Shelat, and V. Vaikuntanathan, “Bounded CCA2-Secure Encryption,” in Int. Conf. Theory Appl. Cryptol. Inf. Secur. Springer, 2007, pp. 502–518. [Online]. Available: http://link.springer.com/10.1007/978-3-540-76900-2{_}31
- [60] M. Bellare and C. Namprempre, “Authenticated encryption: Relations among notions and analysis of the generic composition paradigm,” in Int. Conf. Theory Appl. Cryptol. Inf. Secur. Springer, 2000, pp. 531–545.
- [61] J. Katz and M. Yung, “Characterization of security notions for probabilistic private-key encryption,” J. Cryptol., vol. 19, no. 1, pp. 67–95, 2006.
- [62] T. Holenstein and R. Renner, “On the randomness of independent experiments,” IEEE Trans. Inf. Theor., vol. 57, no. 4, pp. 1865–1871, 2011.
- [63] M. Bellare and P. Rogaway, “Optimal asymmetric encryption,” in Advances in Cryptology — EUROCRYPT’94, A. De Santis, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1995, pp. 92–111.
- [64] M. Bellare and A. Palacio, “Towards plaintext-aware public-key encryption without random oracles,” in Advances in Cryptology - ASIACRYPT 2004, P. J. Lee, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 48–62.
- [65] J. L. Coolidge, “A treatise on algebraic plane curves,” New York: Dover, 1959, p. 10.
- [66] E. W. Weisstein, “Bézout’s theorem,” From MathWorld–A Wolfram Web Resource, https://mathworld.wolfram.com/BezoutsTheorem.html. [Online]. Available: https://mathworld.wolfram.com/BezoutsTheorem.html
- [67] B. Barak, R. Shaltiel, and E. Tromer, “True Random Number Generators Secure in a Changing Environment,” in Int. Workshop on Cryptographic Hardware and Embedded Systems. Springer, 2003, pp. 166–180. [Online]. Available: http://link.springer.com/10.1007/978-3-540-45238-6{_}14
- [68] M. Bellare and P. Rogaway, “Introduction to modern cryptography,” 2005, https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf. [Online]. Available: https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf
Appendix A Proof of Theorem 1
To prove the first part of the theorem, we define two consecutive games: the first game is the CCA distinguishing game in Fig 3 and is the same game except for its decapsulation oracle that always outputs . We have:
| (35) | |||||
where equation 35 is simply using and in lieu of and respectively, and inequality 35 is by triangle inequality.
To bound the first and the last terms of inequality 35, let be the event that outputs 1 in game and be the event that outputs 1 in game for . These two games are identical except when the decapsulation oracle output is not in , lets call this event F. The event F is the union of events , where is the event that the output of the decapsulation oracle in the -th call is not . Let A be the adversary in game that makes queries to the decapsulation oracle. We have and therefore, from the union bound , and from Lemma of [1]:
| (36) |
To bound the second term in inequality 35, we note that in for , the decapsulation oracle always output and simulates the IND-CEA game . Therefore,
| (37) |
Finally, from inequalities 36 and 37 we have
.
The proof of the second part of the theorem uses the same sequence of games, but against a computationally unbounded adversary. We can similarly bound the CCA advantage of the adversary by bounding the advantage of these games. ∎
Appendix B Proof of Theorem 2
We first show the claim of the theorem for the second case that is, an IND-CCA secure KEM in preprocessing model and an IND-OTCCA secure DEM construct an IND-CCA secure hybrid encryption scheme in preprocessing model. The proof of the first case will follow from the proof of the second case. The proof of the third and forth cases are identical to the proof of first and second cases respectively and noting that the adversary for the iKEM is query-bounded and computationally unbounded.
We define a sequence of three games , , and that simulate adversary’s actual or modified interaction with the encryption system during the attack procedure. Each game operates on the same underlying probability space. In particular, private inputs of parties, randomness of the adversary’s algorithm, and the hidden bit b take on identical values across all games. At the end of each game, the adversary outputs a bit . For a game , where with output , denotes the event that . All games are played by a computationally bounded distinguisher D. is identical to the distinguishing game of hybrid encryption in preprocessing model explained above. only differs from in its decapsulation oracle. Suppose the challenge HE ciphertext , where is generated by and is generated by SE.Enc. Then for any decryption query , the decryption oracle of uses to decrypt the ciphertext unless (and . In this case, the key corresponding to that is generated by will be used for the decryption of . Finally, only differs from in using a uniformly sampled key instead of the key generated by cKEM for encryption and answering encryption and decryption queries. We bound using the defined games: For a given sample sam = generated by , we define , a set of bad keys k, generated by , as . According to the correctness of , for we have . The two events and are only different when the event happens. Using Lemma of [1], we have
| (38) |
We now consider the game and . The game is same as except that uses a uniformly sampled key instead of the key generated by cKEM for encryption and decryption queries. Since the KEM’s key is -IND-CCA secure, there exists an adversary such that
| (39) |
In the above case, the adversary just runs the adversary . Specifically, is playing an attack game against KEM in which is equal to in game , whereas is a uniformly sampled random value in the game .
Lastly, note that in game , a new random key is sampled for each encryption/decryption query. Thus in this game, the adversary is just executing a chosen ciphertext attack against SE. Therefore, there exists an adversary such that
| (40) |
Since , using inequalities 38, 39, 40 we have
For the proof of the first part, we note that and are identical because no decryption query is issued. Therefore, . Also since there is no decryption query and the KEM is -IND-CEA secure we have,
and since the DEM is -IND-OT secure, we have,
and finally,
∎
Appendix C Proof of Theorem 6
In the -CEA distinguishing game of , the distinguisher receives , , where is the encapsulation oracle’s output to the th encapsulation query, and the pair of challenge ciphertext and key , and is supposed to distinguish if is generated by or is sampled uniformly. uses the KEM to generate and produces . Then sends and to , where and to . Finally, outputs equal to ’s output. The advantages of and is upper bounded by because is a sample from the uniform distribution only if is a sample from the uniform distribution. Since we assumed that breaks the IND--CEA security of the combined key, then can break the IND--CEA security of the iKEM which is a contradiction.
Appendix D Proof of Theorem 7
The proof for a computationally bounded adversary will be based on the proof of Theorem 3 in [30], and noting that the iKEM will loose its security after a fixed number of repeated queries. We shall prove part of the theorem 7.
To prove the part of the Theorem 7, let denote a computationally unbounded adversary attacking the CCA security of the combiner by making at most encapsulation and ciphertext (decapsulation) queries in the CCA distinguishing game , and be uniform over {0,1}.
1:
2:
3:
4:
5:
%
6:
7:
8:
% :
9:
10:
11:
12: Return
Oracle 1:
2:
3:
4: Return
Oracle 1: If : Abort
2: If Return
3:
4: If :
5:
6:
%
%
7: else
8:
9: If : Return
10:
11:
12: If : Return
13:
14: Return
The proof uses a sequence of five games. We define five games to for a uniform over {0,1}, played by the adversary . Figure 8 depicts these games. In each game, outputs . Note that, if the adversary has already queried the oracle for the same input, the oracle returns the same output.
Adversary can call two oracles, and that correspond to the encapsulation and decapsulation algorithms of the combiner, and have access to the associated keys of the component KEMs. We use and to refer to oracle calls of before and after seeing the challenge ciphertext.
is the CCA distinguishing game of the combiner with the distinguisher making at most encapsulation and decapsulation queries. That is, . Note that according to the PRF-then-XOR construction of the combiner (figure 8), the decapsulation oracle outputs “” when the ciphertext of at least one of the components decapsulates to “”.
| (41) |
In , the iKEM key is replaced by a uniform random key (this replacement is also reflected in the decapsulation oracle Line 5 using ).
Claim 1.
There exists a computationally unbounded adversary whose advantage in the CCA distinguishing game of iKEM with at most encapsulation and decapsulation queries is such that
| (42) |
Proof.
Adversary takes as input. The adversary runs on the challenge . At the end, relays whatever outputs.
Adversary 1:
2:
3: Return
Adversary 1.
2:
3.
4:
5:
6: Return
Oracle 1:
2:
3:
4: Return
Oracle 1: If : Abort
2:
3: If :
4:
5: else
6:
7: If : Return
8:
9:
10: If : Return
11:
12: Return
.
In this construction, issues at most as many queries as . Now if is run by the game , and thus, is the actual key output of , then simulates the game . On the other hand, if is run by the game , that is, is uniformly sampled, then perfectly simulates the game . Therefore, and .
Hence,
∎
In , the output of PRF is replaced by a uniform sample from the output set of the PRF (line 8). This change is also applied to the decapsulation oracle (line 6).
Claim 2.
There exists a computationally unbounded adversary whose advantage, after making at most queries, in distinguishing the output of PRF from a uniform sample is such that
| (43) |
Proof.
(claim 2) We construct the adversary as given in figure 10. From line 1 and 2 of the decapsulation oracle, we ensure that the input to is always different.
Adversary 1:
2:
3:
4:
5:
6:
7:
8:
9:
11:
12: Return
Oracle 1:
2:
3:
4: Return
Oracle 1: If : Abort
2: If Return
3:
4: If :
5:
:: else
6:
7: If : Return
8:
9:
10: If : Return
11:
12: Return
From the construction of the adversary , we observe that is called only once by during generation of the challenge. In addition, for each query to the decapsulation oracle by , is called at most once by . Hence, queries at most times. Now when is run by the game , is the key generated by the game . Thus, emulates the game . On the other hand, when is run by the game , outputs uniformly sampled value, that is, in line 8 of algorithm (and line 5 of decapsulation Oracle queries) is uniformly generated. Hence perfectly simulates the game . Therefore,
and
Thus,
∎
In , we reverse the modifications of the decapsulation oracle that we introduced in game . Consequently, if an adversary queries its decapsulation oracle on a ciphertext whose first component is , the oracle computes by invoking the function instead of returning a uniformly random value. Then, there exists an adversary whose advantage in distinguishing the output of PRF from a uniform sample is such that,
| (44) |
and issues at most queries. We can construct such adversary by replacing line 8 of the adversary in figure 10 with uniform value (). The proof is same as claim 2. In this case, as is uniform, calls at most times.
In , we reverse the modifications added in the game by replacing the uniform key in line 5 of the game in figure 8 with an actual key output of . Then, there exists a computationally unbounded adversary whose advantage in the CCA distinguishing game of iKEM with encapsulation and decapsulation queries is such that
| (45) |
To construct such adversary , we replace line 3 of algorithm of the adversary in figure 9 with . The proof is similar to claim 1.
Finally, we note that since in , is sampled from uniform distribution, then is uniformly distributed and
| (46) |
∎
Appendix E Proof of Theorem 3
We need to prove that the construction 1 satisfies definition 5 for chosen encapsulation attack (CEA) security. In response to an encapsulation query, the oracle returns a key and a ciphertext to the adversary. Let, after queries, the adversary’s received responses be the vector , where . The remaining entropy about that can be used to extract the secret key is , where corresponds to , the attacker’s initial information. Now the -th query’s response to the adversary is , where and . For the -th response, the RVs and are distributed over and respectively. Now using [21, Lemma 2.2(b)], for RVs and , we have . Since remains the same in all responses and the challenge, after encapsulation queries, from [21, Lemma 2.2(b)], we have
| (47) |
Now since , from Lemma 1, we have
| (48) |
Appendix F Proof of Theorem 4
Correctness (reliability). We first determine the value of and , and then compute the extracted secret key length . In the decapsulation algorithm , Bob searches the set for whose hash value matches with the received hash value and checks whether a unique such is found. It declares success if a unique is found in the set with such required property. Therefore, the algorithm fails if one of these two events occurs: there is no element in the set such that its hash value matches with the received hash value i.e. is not in the set , there are more than one element in the set , whose hash values are equal to the received hash value . Hence, the probability that Bob fails to recover the correct key is upper bounded by the sum of the probabilities of these two events. These two cases corresponds to the events:
For any , choose and such that . Let
and .
Now, (from [62], Theorem 2).
To bound , note that since is a universal hash family with input space and seed space ,
for any , , and randomly chosen , we have , where probability is over the random choices from . Thus, . Equation 4 implies that the probability of each element of is lower bounded by . Therefore, using equation 4 and noting that the sum of probability of elements of is less than or equal to 1, we have . Thus, Let , then we have . Therefore, for , the probability that Bob fails to recover the correct key is less than or equal to .
Moreover, since are generated due to independent and identical experiments for all , we have .
Finally, by choosing and , we conclude that if and
, then . Thus, the construction 2 is -correct, and the reliability condition is satisfied.
Security. To prove chosen encapsulation attack (CEA) security, we need to prove that the construction 2 satisfies definition 5. In response to an encapsulation query, the encapsulation oracle returns a pair of key and ciphertext to the adversary. Let the adversary’s received responses to its encapsulation queries be the vector , where . The remaining entropy about is , where corresponds to , the attacker’s initial information. This remaining entropy about is used to extract the key. Now consider the -th query’s response , where and . For the -th response, the RVs and are distributed over and respectively. Using [21, Lemma 2.2(b)], for RVs and and noting that are randomly chosen and independent of RV , we have . Therefore, after encapsulation queries, from [21, Lemma 2.2(b)], we have
| (51) |
Appendix G Proof of Lemma 3.
Proof.
We show that satisfies Definition 1.
Let and be such
that . We need to show that
, where the probability is over the uniformly random choices of , and . Note that with and .
Since , we have .
Case 1. Let . For fixed values of and , there is a unique value of for which we have,
| (55) |
Therefore, for a random choice of , we have that is given by .
Case 2. Let .
For fixed values of and , there is a unique value of for which we have,
| (56) |
For every , there are values of , where each, for fixed , determines a single value for . Thus there are exactly values of for which the above equation 56 holds true.
Thus, for a random choice of the probability of collision in this case is, exactly .
Therefore, is a universal hash family. ∎
Appendix H Bézout’s theorem [65, 66]
Bézout’s Theorem [65, 66]. In general, two algebraic curves of degree and can intersect in points and cannot meet in more than points unless they have a common factor (i.e. the two equations have a common factor).
Moreover, polynomial equations of degrees in variables have in general common solutions.
Appendix I CEA secure iKEM protocol of Sharifian et al. [32]
Definition 9 (strongly universal hash family).
A family of hash functions is called a strongly universal hash family if for all , and any , , where the probability is over the uniform choices over .
We briefly recall the construction of CEA secure iKEM protocol due to Sharifian et al. [32]. .
Construction 5.
The iKEM ’s three algorithms are as follows: The protocol is designed for preprocessing model in which Alice, Bob and Eve have components of the source respectively according to a distribution . The protocol uses two strongly universal hash families: and . and denote the ciphertext space and key space respectively.
-
1.
. A trusted sample samples the distribution independently times and gives , and privately to Alice, Bob and Eve respectively.
-
2.
. The encapsulation algorithm takes Alice’s private input , randomly sample the seeds and for two strongly universal hash families and respectively. It generates the key and the ciphertext .
-
3.
. The decapsulation algorithm takes Bob’s private key and the ciphertext . It parses as , where is a -bit string. It defines a set , and for each vector checks whether . The decapsulation algorithm outputs the key if there is a unique that satisfies ; otherwise, it outputs .