

New Paradigm for Practical Cryptosystems without Random OraclesAbstractThis paper introduces a new paradigm for making various types of cryptographic primitives such as authenticated key exchange and key encapsulation without random oracles under three assumptions: the decisional DiffieHellman assumption, target collision resistant hash functions, and a class of pseudorandom functions. It describes a new twopass authenticated key exchange (AKE) protocol (based on the public key infrastructure model) that is comparable in efficiency to the most efficient of the existing protocols and secure (under these assumptions), whereas existing efficient twopass AKE protocols are secure in the random oracle model. This protocol is shown to be secure in the (currently) strongest security definition, the extended CanettiKrawczyk (eCK) security definition. This paper also describes a key encapsulation mechanism (KEM) that is secure against adaptive chosen ciphertext attacks (i.e., CCAsecure) under these assumptions and almost as efficient as the KurosawaDesmedt KEM. The schemes presented this paper are validitycheckfree, which implies that combining them with validitycheckfree symmetric encryption (data encryption mechanism) will yield validitycheckfree (e.g., free of message authentication code) CCAsecure hybrid encryption.
1. IntroductionThe concept of publickey cryptosystems was introduced by Diffie and Hellman in 1976 to solve the key agreement problem over insecure networks (like the Internet). The standard security notion of a publickey cryptosystem (encryption) is security against adaptive chosen ciphertext attacks (i.e., CCAsecurity), and there are two major methodologies for designing practical CCAsecure publickey encryption: one is based on the random oracle model and the other on the standard model. A CCAsecure scheme in the standard model provides a real security guarantee, whereas a CCAsecure scheme in the random oracle model is guaranteed to be secure under unrealistic idealization of a hash function as an ideal random function. One of the most important topics for the last ten years has been to design a truly practical publickey cryptosystems in the standard model^{*1}. The most common paradigm for designing practical publickey cryptosystems that are secure in the standard model is to combine a trapdoor function (e.g., DiffieHellman or RSA (Rivest, Shamir, Adleman) function) and target collision resistance (TCR) hash functions, where the security is proven under a trapdoor function assumption (e.g., DDH (decisional DiffieHellman) or strong RSA assumption) and the TCR hash function assumption [3]–[5]. This paper introduces a new paradigm for designing practical publickey cryptosystems, where a class of pseudorandom functions (PRFs) PRFs with pairwiseindependent random sources (πPRFs), is used in addition to a trapdoor function (DiffieHellman function) and TCR hash function. The concept of a PRF was introduced by Goldreich, Goldwasser, and Micali [6]. The PRF has been shown to exist if and only if a oneway function exists [6], [7]. Therefore, the existence of a PRF is one of the weakest assumptions, so it is one of the most fundamental primitives in cryptography^{*2}. Since a TCR hash function (and the slightly more general concept of the universal oneway hash function) has also been shown to exist if and only if a oneway function exists [9], [10], the TCR hash function and PRF are on the same level as (the most) fundamental primitives in cryptography. In practice, a welldesigned efficient hash function can be assumed to be a TCR hash function, and such a hash function with a random seed as part of the input (or a keyed hash function) can be assumed to be a PRF (and a πPRF). Authenticated key exchange (AKE) protocols have been extensively studied to enhance the security of the DiffieHellman (DH) key exchange protocol, which was proposed in 1976, because the DH protocol is not secure against the maninthemiddle attack[11]–[17]. This paper presents a twopass AKE protocol that has the following properties.
This paper also presents a CCAsecure (i.e., secure against adaptive chosen ciphertext attacks) key encapsulation mechanism (KEM) under these assumptions that is almost as efficient as the KurosawaDesmedt KEM [5]. The schemes presented in this paper are validitycheckfree, which implies validitycheckfree (e.g., free of message authentication code (MACfree)) CCAsecure hybrid encryption if they are combined with validitycheckfree CCAsecure symmetric encryption (data encryption mechanism (DEM)). Therefore, their ciphertexts can be decrypted with no validitycheck.
2. Preliminaries2.1 Notationis the set of natural numbers and is the set of real numbers. ⊥ denotes a null string. A function f : →−is negligible in k, if for every constant c > 0, there exists integer n such that f(k) < k^{−c} for all k > n. If A is a probabilistic machine or algorithm, A(x) denotes the random variable of A's output on input x. Then, yR← A(x) denotes that y is randomly selected from A(x) according to its distribution. If a is a value, A(x) → a denotes the event that A outputs a on input x. If A is a set, y U← A denotes that y is uniformly selected from A. If A is a value, y ← A denotes that y is set to A. In this paper, the underlying machines are considered to be uniform Turing machines, but the results can easily be extended to nonuniform Turing machines. 2.2 Decisional DiffieHellman (DDH) assumptionLet k be a security parameter and be a group with security parameter k, where the order of is prime p and p = k. Let {}_{k} be the set of groups with security parameter k. For all k∈, we define the sets and as follows: (k)←{(, G_{1}, G_{2}, G^{x}_{1}, G^{x}_{2})  U← {}_{k}, (G_{1}, G_{2}) U← ^{2}, x U← _{p}} (k)←{(, G_{1}, G_{2}, y_{1},y_{2})  U← {}_{k}, (G_{1}, G_{2}, y_{1}, y_{2}) U← ^{4}}. Let A be a probabilistic polynomialtime machine. For all k ∈, we define the DDH advantage of A as AdvDDHA(k) ←  Pr [A(1^{k}, ρ)→1 ρ U← (k)] − Pr [A(1^{k}, ρ) → 1ρ U← (k)] . The DDH assumption for {}_{k∈} is: For any probabilistic polynomialtime adversary A, AdvDDHA(k) is negligible in k. 2.3 Pseudorandom Function (PRF)Let k∈ be a security parameter. A PRF family F associated with {Seed_{k}}_{k∈}, {Dom_{k}}_{k∈} and {Rng_{k}}_{k∈} specifies two items: – A family of random seeds {Seek_{k}}_{k∈}. – A family of PRFs indexed by k,Σ R← Seed_{k}, σ U← Σ, D R← Dom_{k}, and R R← Rng_{k}, where each such function F^{k}_{σ}^{,Σ,D,R} maps an element of D to an element of R. There must exist a deterministic polynomialtime algorithm that on input 1^{k},σ, and ρ, outputs F^{k}_{σ}^{,Σ,D,R} (ρ). Let A^{O} be a probabilistic polynomialtime machine with oracle access to O. For all k, we define AdvPRFF, A(k) ←Pr [A^{F}(1^{k},D,R )→1] − Pr[A^{RF}(1^{k},D,R ) → 1], where Σ R← Seed_{k}, σ U← Σ, D R← Dom_{k}, R R← Rng_{k}, F ←F^{k}_{σ}^{,Σ,D,R}, and RF : D → R is a truly random function (¢Ïρ∈D RF(ρ) U←R). F is a PRF family if, for any probabilistic polynomialtime adversary A, AdvPRFF, A(k) is negligible in k. 2.4 Pseudorandom function with pairwiseindependent random sources (πPRF)Here, we introduce a specific class of PRFs, πPRFs. Let k∈ be a security parameter and F be a PRF family associated with {Seed_{k}}_{k∈}, {Dom_{k}}_{k∈}, and {Rng_{k}}_{k∈}. We then define a πPRF family for F. Let Σ R← Seed_{k}, D R← Dom_{k}, R R← Rng_{k}, and RF: D → R be a truly random function (¢Ïρ∈DRF(ρ) U← R). Let I_{Σ} be a set of indices regarding Σ such that there exists a deterministic polynomialtime algorithm, f_{Σ}: I_{Σ} → Σ, that on input i ∈_{IΣ}, outputs σ_{i} ∈Σ . Let σ_{i0}, σ_{i1}, ..., σ_{it(k)} be random variables indexed by I_{Σ}, where i_{j} ∈I_{Σ} (j = 0, 1, ..., t(k)) and t(k) is a polynomial of k. Let σ_{i0} be pairwisely independent from other variables, σ_{i1}, ..., σ_{it(k)} and each variable be uniformly distributed over Σ. That is, for any pair of (σ_{i0}, σ_{ij}) (j = 1, ..., t(k)), for any (x, y)∈Σ^{2}, Pr[σ_{i0}→ x ∧σ_{ij} → y] = Pr[σ_{i0} → x ] • Pr[σ_{ij }→ y] = 1/Σ^{2}. Let A^{F, IΣ} be a probabilistic polynomialtime machine A that queries q_{j} ∈D along with i_{j} ∈I_{Σ} to F and receives the reply F ^{k}_{σij}^{,Σ,D,R} (q_{j}) for each j = 0, 1, ..., t(k). Let A^{RF, IΣ} be the same as A^{F, IΣ} except that Fk_{σij}^{k, Σ D, R,} (q_{0}) is replaced by RF(q_{0}). For all k, we define AdvπPRFF, IΣ, A(k) ← Pr[A^{F, IΣ}(1k,D ,R ) → 1] − Pr[A^{RF, IΣ}(1^{k},D ,R ) → 1]. F is a πPRF family with index {(I_{Σ}, f_{Σ})}_{Σ∈Seedk, k∈} if for any probabilistic polynomialtime adversary A,AdvπPRFF, IΣ, A (k) is negligible in k. 2.5 Target collision resistant (TCR) hash functionLet k∈ be a security parameter. A TCR hash function family H associated with {Dom_{k}}_{k∈} and {Rng_{k}}_{k∈} specifies two items: – A family of key spaces indexed by k. Each such key space is a probability space of bit strings denoted by KH_{k}. There must exist a probabilistic polynomialtime algorithm whose output distribution on input 1^{k} is equal to KH_{k}. – A family of hash functions indexed by k, h R← KH_{k}, D R← Dom_{k}, and R R← Rng_{k}, where each such function H_{h}^{k,D,R} maps an element of D to an element of R. There must exist a deterministic polynomialtime algorithm that on input 1^{k}, h, and ρ, outputs H_{h}^{k,D,R} (ρ). Let A be a probabilistic polynomialtime machine. For all k, we define AdvTCR H, A(k)← Pr [ρ∈D ∧ρ≠ρ^{*} ∧H_{h}^{k,D,R }(ρ) =H_{h}^{k,D,R} (ρ^{*})ρ R← A(1^{k}, ρ^{*}, h, D, R)], where D R← Dom_{k}, R R← Rng_{k}, ρ^{*} U← D and h R← KH_{k}. H is a TCR hash function family if for any probabilistic polynomialtime adversary A, AdvTCR H, A(k) is negligible in k. 2.6 PKIbased authenticated key exchange (AKE) and eCK security definitionThis section outlines the eCK security definition [16] for twopass AKE protocols based on the public key infrastructure (PKI) model and follows the description in [17]. The eCK definition assumes that there are n parties, which are modeled as probabilistic polynomialtime Turing machines. We assume that these parties have agreed some common parameters (common reference strings) in the AKE protocol before the protocol is started. The parameter selection mechanism is out of the scope of the AKE protocol and the (eCK) security model. Each party has a static publicprivate key pair together with a certificate that binds the public key to that party. ˆA (or ˆB ) denotes the static public key A (or B) of party A(B) together with a certificate. The certifying authority (CA) is not assumed to require parties to prove possession of their static private keys, but the CA is required to verify that the static public key of a party belongs to the domain of public keys. Here, two parties exchange static public keys A, B and ephemeral public keys X, Y; the session key is obtained by combining A, B, X, Y and possibly session identities. A party A can be activated to execute an instance of the protocol called a session. Activation is made via an incoming message that has one of the following forms: ( ˆA, ˆB) or ˆB, ˆA, X). If A was activated with ( ˆA, ˆB), then A is called the session initiator; otherwise, it is called the session responder. Session initiator A creates ephemeral publicprivate key pair (X, x) and sends ( ˆB, ˆA, X) to session responder B. B then creates ephemeral publicprivate key pair (Y, y) and sends ( ˆA, ˆB, X, Y) to A. The session of initiator A with responder B is identified via session identifier ( ˆA, ˆB, X, Y), where A and B are said to be the owner and peer of the session, respectively. The session of responder B with initiator A is identified as ( ˆB, ˆA, Y, X), where B is the owner and A is the peer. Session ( ˆB, ˆA, Y, X) is said to be a matching session of ( ˆA, ˆB, X, Y). We say that a session is completed if its owner computes a session key. The adversary M is modeled as a probabilistic polynomialtime Turing machine and controls all communications. Parties submit outgoing messages to the adversary, who makes decisions about their delivery. The adversary presents parties with incoming messages via Send(message), thereby controlling the activation of sessions. In order to capture private information that may leak, adversary M is allowed the following queries: – EphemeralKeyReveal(sid) The adversary obtains the ephemeral private key associated with session sid. – SessionKeyReveal(sid) The adversary obtains the session key for session sid, provided that the session has a session key. – StaticKeyReveal(pid) The adversary learns the static private key of party pid. – EstabllishPatry(pid) This query makes it possible for the adversary to register a static public key on behalf of a party. In this way, the adversary completely controls that party. If a party pid is established by EstabllishPatry(pid) query issued by adversary M, then we call the party dishonest. If a party is not dishonest, we call it honest. The aim of adversary M is to distinguish a session key from a random key. Formally, the adversary is allowed to make a special query Test(sid^{*}), where sid^{*} is called the target session. The adversary is then given with equal probability either the session key K^{*}, held by sid^{*}, or a random key R^{*} U← {0, 1}^{K*}. The adversary wins the game if he correctly guesses whether the key is random or not. To define the game, we need the notion of a fresh session as follows: Definition 1. (fresh session) Let sid be the session identifier of a completed session owned by an honest party A with peer B, who is also honest. Let —sid be the session identifier of the matching session of sid, if it exists. We define session sid to be fresh if none of the following conditions hold: –M issues a SessionKeyReveal(sid) query or a SessionKeyReveal(—sid) query (if —sid exists), – —sid exists and M makes either of the following queries: both StaticKeyReveal(A) and EphemeralKeyReveal(sid) or both StaticKeyReveal(B) and EphemeralKeyReveal(—sid), – —sid does not exist and M makes either of the following queries: both StaticKeyReveal(A) and EphemeralKeyReveal(sid) or StaticKeyReveal(B). Now we are ready to present the eCK security notion. Definition 2. (eCK security) Let K^{*} be the session key of the target session sid^{*} that should be fresh, R^{*} U← {0, 1}^{K*}, and b^{*} U← {0, 1}. As a reply to Test(sid^{*}) query by M, K^{*} is given to M if b^{*} = 0; R^{*}; otherwise, R^{*} is given. Finally, M outputs b ∈{0, 1}. We define A key exchange protocol is secure if the following conditions hold: – If two honest parties complete matching sessions, then they both compute the same session key (or both output an indication of protocol failure). – For any probabilistic polynomialtime adversary M, AdvAKEM(k) is negligible in k. This security definition is stronger than the original form of CanettiKrawczyk security [11] and it simultaneously captures all the known desirable security properties for authenticated key exchange including resistance to keycompromise impersonation attacks, weak perfect forward secrecy, and resilience to the leakage of ephemeral private keys. 2.7 Key encapsulation mechanism (KEM)A KEM scheme is the triplet of algorithms, Σ= (K, E, D), where 1. K, the key generation algorithm, is a probabilistic polynomialtime algorithm that takes a security parameter k∈ (provided in unary) and returns a pair (pk, sk) of matching public and secret keys. 2. E, the key encryption algorithm, is a probabilistic polynomialtime algorithm that takes as input public key pk and outputs a key/ciphertext pair (K^{*}, C^{*}). 3. D, the decryption algorithm, is a deterministic polynomial time algorithm that takes as input secret key sk and ciphertext C^{*} and outputs key K^{*} or ⊥ (⊥ means that the ciphertext is invalid). For all (pk, sk) output by key generation algorithm K and for all (K^{*}, C^{*}) output by key encryption algorithm E(pk), D(sk, C^{*}) = K^{*} holds. Here, the length of the key K^{*} is specified by l (k), where k is the security parameter. Let A be an adversary. The attack game is defined in terms of an interactive computation between adversary A and its challenger C. The challenger C responds to the oracle queries made by A. The attack game (INDCCA2 game) used to define security against adaptive chosen ciphertext attacks (INDCCA2) is described below. 1. The challenger C generates a pair of keys (pk, sk) R← K(1^{k}) and gives pk to adversary A. 2. Repeat the following procedure q_{1}(k) times, for i = 1, . . . , q_{1}(k), where q_{1}(•) is a polynomial. A submits string C_{i} to a decryption oracle, DO (in C), and DO returns D_{sk} (C_{i}) to A. 3. A submits the encryption query to C. The encryption oracle EO in C selects b^{*} U← {0, 1} and computes (C^{*}, K^{*}) ← E(pk) and returns (C^{*}, K^{*}) to A if b^{*} = 0 and (C^{*}, K^{*}) if b^{*} = 1, where R^{*} U←{0, 1}^{K*} (C^{*} is called the target ciphertext). 4. Repeat the following procedure q_{2}(k) times, for j = q_{1}(k)+1, . . . , q_{1}(k) + q_{2}(k), where q_{2}(•) is a polynomial. A submits string C_{j} to a decryption oracle, DO (in C), subject only to the restriction that a submitted text C_{j} is not identical to C^{*}. DO returns D_{sk} (C_{j}) to A. 5. A outputs b ∈{0, 1}. We define the INDCCA2 advantage of A, AdvKEM_{A}^{INDCCA2}(k) ← Pr[b = b^{*}] − 1/2 in the above attack game. We say that a KEM scheme is INDCCA2secure (secure against adaptive chosen ciphertext attacks) if, for any probabilistic polynomialtime adversaryA, AdvKEM_{A}^{INDCCA2}(k) is negligible in k. 3. New AKE protocol
3.1 ProtocolLet k∈ be a security parameter, let U←{}_{k} be a group with security parameter k, and let (G_{1}, G_{2}) U← ^{2}, where the order of is prime p and p = k. Let H be a TCR hash function family, ˆF and ˜F be PRF families and F be a πPRF family. (, G_{1}, G_{2}), H, F, ˜F, and ˆF are the system parameters common among all users of this AKE protocol (although ˜F and ˆF can be set privately by each party). We assume that the system parameters are selected by a trusted third party. Party A's static private key is (a_{1}, a_{2}, a_{3}, a_{4}) U← (p)^{5} and A's static public key is A_{1} ← G_{1}^{a1} G_{2}^{a2}, A_{2} ← G_{1}^{a3} G_{2}^{a4}. Here, h_{A} R← KH_{k} indexes a TCR hash function H_{A}← H_{hA}^{k,DH,RH}, where D_{H} ← Π_{k} × ^{4}, R_{H} ← _{p}, and Π_{k} denotes the space of possible certificates for static public keys. Similarly, Party B's static private key is (b_{0}, b_{1}, b_{2}, b_{3}, b_{4}) U← (_{p})^{5} and B's static public key is B_{1} ← G_{1}^{b1} G_{2}^{b2}, B_{2} ← G_{1}^{b3} G_{2}^{b4}. Here, h_{B} R← KH_{k} indexes a TCR hash function H_{B} ← H_{hB}^{k, DH, RH}. A and B set πPRF and PRFs F ← F^{k,ΣF,DF,RF}, ˜F ← ˜F^{k, Σ˜F, D˜F, R˜F} and ˆF ← ˆF^{k,Σ ˆF,DˆF,RˆF}, where Σ_{F}←, D_{F}← (Π_{k})^{2} × ^{10}, R_{F}← {0, 1}^{k}, Σ_{˜F} ← _{p}, D_{˜F} ← {0, 1}^{k}, R_{˜F} ←(_{p})^{2}, Σ_{ˆF} ← {0, 1}^{k}, D_{ˆF} ← {0, 1}^{k}, and R_{ˆF} ← (_{p})^{2}. To establish a session key with party B, party A performs the following procedure. 1. Select an ephemeral private key (˜x_{1}, ˜x_{2}) U← {0, 1}^{k} × {0, 1}^{k}. 2. Compute ˜a ←Σ^{4}_{i=0} a_{i} mod p (x, x_{3}) ← ˆF_{˜x1} (1^{k}) + ˜F_{˜a} (˜x_{2}) mod p (as twodimensional vectors) and the ephemeral public key (X_{1} ← G^{x}_{1}, X_{2} ← G^{x}_{2}, X_{3} ← G_{1}^{x3}). Note that the value of (x, x_{3}) (and ˜a) is only computed in a computation process of the ephemeral public key from ephemeral and static private keys. 3. Erase (x, x_{3}) and the whole computation history of the ephemeral public key. 4. Send ( ˆB, ˆA, X_{1}, X_{2}, X_{3}) to B. Upon receiving ( ˆB, ˆA, X_{1}, X_{2}, X_{3}), party B verifies that (X_{1}, X_{2}, X_{3}) ∈^{3}. If so, perform the following procedure. 1. Select an ephemeral private key (˜y_{1}, ˜y_{2}) U←{0, 1}^{k} × {0, 1}^{k}. 2. Compute ˜b ← Σ^{4}_{i=0} b_{i} mod p (y, y_{3}) ← ˆF_{˜y1} (1^{k}) + ˜F_{˜b} (˜y_{2}) mod p (as twodimensional vectors) and the ephemeral public key (Y_{1} ← G^{y}_{1}, Y_{2} ← G^{y}_{2}, Y_{3} ← G_{1}^{y3}) 3. Erase (y, y_{3}) and the whole computation history of the ephemeral public key. 4. Send ( ˆA, ˆB, X_{1}, X_{2}, X_{3}, Y_{1}, Y_{2}, Y_{3}) to A. Upon receiving( ˆA, ˆB, X_{1}, X_{2}, X_{3}, Y_{1}, Y_{2}, Y_{3}), party A checks if he sent ( ˆB, ˆA,X_{1}, X_{2}, X_{3}) to B. If so, A verifies that (Y_{1}, Y_{2}, Y_{3}) ∈ ^{3}. To compute the session key, A computes σ_{A} ← Y_{1}^{a1+ca3}Y_{2}^{a2+ca4}Y_{3}^{x3}B_{1}^{x}B_{2}^{dx} , and B computes σ_{B} ← X_{1}^{b1+db3} X_{2}^{b2+db4}X_{3}_{y3}A_{1}^{y}A_{2}^{cy} , where c ← H_{A}( ˆA, ˆB,Y_{1}, Y_{2}, Y_{3}) and d ← H_{B}( ˆB, ˆA, X_{1}, X_{2}, X_{3}). If they are correctly computed, then σ← σ_{A} (=σ_{B}). The session key is K ← Fσ (sid), where sid ← ( ˆA, ˆB, X_{1}, X_{2}, X_{3}, Y_{1}, Y_{2}, Y_{3}). 3.2 SecurityTheorem 1. 4. New KEM scheme4.1 SchemeThis section shows a CCAsecure KEM scheme. Let k∈ be a security parameter and let U←{}_{k} be a group with security parameter k, where the order of is prime p and p = k. Let H be a TCR hash function family and F be a PRF family. Secret key: The secret key is sk←(x_{1}, x_{2}, y_{1}, y_{2}) U← _{p}^{4}. Public key: G_{1} U←,G_{2} U←, z ← G_{1}^{x1} G_{2}^{x2} , w ← G_{1}^{y1} G_{2}^{y2}, H ←H_{h}^{k,DH,RH} and F ← F^{k,ΣF,DF,RF}, where h R← KH_{k}, D_{H} ← {pk} × ^{2} (pk is a possible publickey value), R_{H} ←_{p}, Σ_{F}←, D_{F}← {pk} × ^{2} and R_{F}← {0, 1}^{k}. The public key is pk ← (, G_{1}, G_{2}, z, w, H, F). Encryption: Choose r U← _{p} and compute (C_{1}, C_{2}) is a ciphertext and K is the secret key to be shared. Decryption: Given (z, w, C_{1}, C_{2}), check whether (z, w, C_{1}, C_{2})∈^{4}. If it holds, compute K ← Fσ (pk, C_{1}, C_{2}). 4.2 CCA securityTheorem 2.The new KEM scheme is INDCCA2secure if the DDH assumption holds for {}_{k¢º}, if H is a TCR hash function family, and if F is a πPRF family with index {(I_{}, f_{})}_{∈{}k, k¢º} , where I_{} ← {(V, W, d)(V, W, d) ∈^{2} × _{p}} and f_{} : (V, W, d) → V^{r1+dr2}W with (r_{1}, r_{2}) U← _{p}^{2}. 5. Concluding remarksThis paper introduced a new paradigm for making various types of cryptographic primitives such as authenticated key exchange and key encapsulation without random oracles under the three standard assumptions: the DDH assumption, TCR hash functions, and πPRFs. These schemes are secure without random oracles and almost as efficient as the most efficient schemes secure in the random oracle model. Therefore, they are good candidates for replacing practical schemes in the random oracle model and will have many practical applications^{*3} [18]. References
