# Close to Optimally Secure Variants of GCM

Authors: Ping Zhang; Hong-Gang Hu; Qian Yuan
Journal: Security and Communication Networks
 (2018)

---

## Abstract

The Galois/Counter Mode of operation (GCM) is a widely used nonce-based authenticated encryption with associated data mode which provides the birthday-bound security in the nonce-respecting scenario; that is, it is secure up to about2n/2 adversarial queries if all nonces used in the encryption oracle are never repeated, where n is the block size. It is an open problem to analyze whether GCM security can be improved by using some simple operations. This paper presents a positive response for this problem. Firstly, we introduce two close to optimally secure pseudorandom functions and derive their security bound by the hybrid technique. Then, we utilize these pseudorandom functions that we design and a universal hash function to construct two improved versions of GCM, called OGCM-1 and OGCM-2. OGCM-1 and OGCM-2 are, respectively, provably secure up to approximately 2n/67(n-1)2 and 2n/67 adversarial queries in the nonce-respecting scenario if the underlying block cipher is a secure pseudorandom permutation. Finally, we discuss the properties of OGCM-1 and OGCM-2 and describe the future works.


---

## Body

## 1. Introduction

Authenticated Encryption. An authenticated encryption (AE) mode is a cryptographic scheme which guarantees privacy and authenticity of the message concurrently. So far, a large number of AE schemes have emerged. Particularly, the CAESAR competition that started in 2012 promotes enormously the development of AE schemes. AE has been widely applied to many environments. According to the application requirements classification, this includes AE with associated data (AEAD) [1, 2], parallelizable AE [3–5], online AE [6–9], tweakable AE [9–14], deterministic AE [10, 15, 16], wide block AE [17], XOR-based AE [18], and dedicated AE algorithms [19]. According to the design approaches classification, this includes generic composed AE [20], block cipher-based AE [3–6, 21], stream-cipher-based AE [18, 22], permutation-based AE [23–26], keyed-function-based AE [27, 28], tweakable block cipher-based AE [9–14], and hybrid AE [17, 19, 29].Birthday-Bound Security and Beyond-Birthday-Bound Security.Most AE modes, such as [6, 7, 9, 20, 21, 26], just offer birthday-bound security; that is, they are secure up to roughly 2n/2 adversarial queries, where n is the block size. The currently utilized block cipher is AES (the block size n=128). If AES is used in the block cipher modes of operation, 128-bit security degrades into at most about 64-bit security, which is unacceptable in some special environments. Therefore, it is vitally important to design AE modes that ensure beyond-birthday-bound (BBB) security. The so-called BBB security means that an AE mode is provably secure up to approximately 2rn/r+1 adversarial queries, where r≥2 is an integer. If an AE mode is provably secure up to roughly 2n adversarial queries, we say that it provides optimal security. In order to achieve a stronger security (BBB security or optimal security), AE modes usually compromise the efficiency of the hardware and software implementation. For example, we often utilize multiple block ciphers or their sum to construct a BBB-secure pseudorandom function. The higher the number of invoking the underlying block cipher, the greater the cost. Therefore, the efficiency of BBB-secure AE modes is generally low. In recent years, AE modes that ensure BBB security appeared endless, such as [10–12, 22–24, 30–32].Problem Statement.The Galois/Counter Mode of operation (GCM) [33] designed by McGrew and Viega is a nonce-based AEAD scheme. GCM combines the counter mode used in the encryption part and the polynomial hash function used in the authentication part and is included in the block cipher AE modes of operation recommended by NIST. Its security depends on the nonce-respecting setting that all nonces used in the encryption queries are distinct. Iwata et al. [34] pointed out that the previous claimed security was flawed and presented a new provable security, which was later improved by Niwa et al. [35]. GCM retains birthday-bound security and has better security bounds for 96-bit nonces. For the attacks of GCM, Saarinen showed weak keys of GHASH and the cycling attacks on GCM in [36]. Other researches related to GCM include [37–44]. GCM has been widely applied in the IEEE 802.1AE Ethernet security, IEEE 802.11ad, IETF IPsec standards, SSH, TLS, and so on. GCM is proven to be secure up to roughly 2n/2 adversarial queries in the nonce-respecting scenario, assuming that the underlying block cipher is a secure pseudorandom permutation. In other words, for AES-GCM, its security guarantee is lost after at most only 264 adversarial queries, which is not sufficiently secure in some special settings. Therefore, in this paper, we consider the question of whether we can design a scheme that provides better security (such as BBB security or optimal security) to improve the security guarantee of GCM.Our Contributions.This paper gives a positive response for the above question. We first introduce a basic tool: close to optimally secure pseudorandom functions (PRFs) which are, respectively, designed by the Encrypted Davies-Meyer (EDM) [45] and EDM Dual (EDMD) [46] constructions. Then we construct two improved versions of GCM, called OGCM-1 and OGCM-2, which are parallelizable nonce-based close to optimally secure AEAD modes. OGCM-1 and OGCM-2 are, respectively, provably secure up to approximately 2n/67(n-1)2 and 2n/67 adversarial queries in the nonce-respecting scenario if the underlying block cipher is a secure pseudorandom permutation (PRP). In fact, they are based on the “Encryption-then-MAC” approach, where the encryption part utilizes a multi-EDM or multi-EDMD function to set up a close to optimally secure key-stream generator and then the MAC part combines an EDM or EDMD construction and an almost-XOR-universal (AXU) hash function to generate an authentication tag.OGCM-1 and OGCM-2 balance the security and the efficiency of the software and hardware implementation. Take AES-OGCM-1 or AES-OGCM-2 as an example; that is, the underlying block cipher is instantiated with AES. First, from the point of view of security, they achieve at most about 107.9565-bit or 121.9339-bit security which is better than that of AES-GCM (at most about 64-bit security). In the nonce-respecting scenario, they can encrypt at most296 plaintexts (as the nonce length is 96 bits) and the maximum block length of each plaintext is about 232 blocks (64 GBytes). Second, from the point of view of efficiency, they invoke 2m+2 block ciphers and a+m+1 finite-field multiplications, where m is the number of the plaintext blocks and a is the number of the associated data blocks. Compared with AES-GCM, the efficiency is about half of it. Therefore, AES-OGCM-1 and AES-OGCM-2 sacrifice the efficiency of the software and hardware implementation to achieve a strong security. The comparisons among AES-GCM, AES-OGCM-1, and AES-OGCM-2 are shown in Table 1.Table 1
Comparisons among AES-GCM [34], AES-OGCM-1, and AES-OGCM-2. The nonce length is restricted to 96 bits. “n.r.” denotes nonce-respecting. “A↷B” means A can be reduced to B. Let m be the block length of the plaintext and a be the block length of associated data.
AES-GCM [34] AES-OGCM-1 AES-OGCM-2 # keys 1 3 ↷ 1 3 ↷ 1 CTR-like Yes Yes Yes Block sizen 128 128 128 Nonce scenario n.r. n.r. n.r. Assumption PRP PRP PRP Security (bits) 64 107.9565 121.9339 # block cipher calls m + 2 2 m + 2 2 m + 2 # multiplications a + m + 1 a + m + 1 a + m + 1Organizations of This Paper.Some preliminaries are presented in Section 2. A basic tool is provided in Section 3. OGCM-1 is described in Section 4. Security results of OGCM-1 are derived in Section 5. OGCM-2 and its security are shown in Section 6. Section 7 describes some discussions and future works. Finally, we end up with a conclusion in Section 8.


## 2. Preliminaries

Notations.Let {0,1}∗ be the set containing all finite strings (including an empty string ε). For a finite string x∈{0,1}∗,  |x| stands for its length in bits and |x|n=⌈|x|/n⌉ means the length of n-bit blocks for any integer n≥1, where ⌈·⌉ denotes the operation that rounds up from a floating-point number to an integer. The n-bit zero string is written as 0n∈{0,1}n. For two finite strings x and y, let x∥y or xy be the concatenation of them. If x and y are two equal-length strings, let x⊕y denote the XOR of them. For a finite string x∈{0,1}∗ with |x|≥n, let msbn(x) be the most significant n-bit of x. Given two positive integers n and m such that m≤2n-1, let [m]n be the n-bit binary representation of m. Let inc(·) be the function for increment which takes an n-bit input x and returns an incremented value x+1 mod 2n. For i≥1, inci(x) denotes that x is incremented i times. For a finite set X, let x←$X denote the value x randomly drawn from X and let |X| denote the number of elements in X. Let [a,b] be a set of all integers from a to b; that is, [a,b]={x∈Z:a≤x≤b}. Let AO=1 be an event that an adversary A outputs 1 after interacting with the oracle O.Block Ciphers and Keyed Functions.A block cipher is a mapping E:Ke×{0,1}n→{0,1}n, which takes a key K∈Ke and a plaintext M∈{0,1}n as input and returns a ciphertext C∈{0,1}n. For any fixed K∈Ke, EK:{0,1}n→{0,1}n is an n-bit permutation and its inverse is written as DK=EK-1. Let Perm(n) be a set of all n-bit permutations. Suppose that A is an adversary which has access to an encryption oracle. Let K←$Ke and π←$Perm(n); then the PRP-advantage of A against E is defined as (1)AdvEprpA=PrAEK·=1-PrAπ·=1, where the probabilities are taken over the random choices of K and π and also over internal coins of A, if any. If AdvEprp(A) is negligible, the underlying block cipher EK is a secure pseudorandom permutation (PRP).A keyed function is a mappingF:Kf×{0,1}m→{0,1}n, which takes a key K∈Kf and a plaintext M∈{0,1}m as input and returns a ciphertext C∈{0,1}n. For any fixed K∈Kf, FK:{0,1}m→{0,1}n is a function from {0,1}m to {0,1}n. Let Func(m,n) be a set of all functions from {0,1}m to {0,1}n. If m=n, we write Func(n). Suppose that A is an adversary which has access to an encryption oracle. Let K←$Kf and R←$Func(m,n); then the PRF-advantage of A against F is defined as (2)AdvFprfA=PrAFK·=1-PrAR·=1, where the probabilities are taken over the random choices of K and R and also over internal coins of A, if any. If AdvFprf(A) is negligible, the underlying keyed function FK is a secure pseudorandom function (PRF).If the resources owned by all adversaries are at mostS, the maximum advantage is defined as Adv(S)=maxA⁡Adv(A), where S includes the running time t, the total number of oracle queries q, the maximum block length m, and the total number of blocks in all queries (query complexity) σ.Universal Hash Functions.Let n≥1; a keyed hash function H:Kh×D→{0,1}n is a mapping which takes a key Kh∈Kh and a message x∈D as input and returns an output y∈{0,1}n. We say H is an (ϵ,δ)-almost-XOR-universal ((ϵ,δ)-AXU) hash function, if, for any x∈D and y∈{0,1}n,  Pr[Kh←$Kh:HKh(x)=y]≤δ and, for any two distinct x,x′∈D and y∈{0,1}n,  Pr[Kh←$Kh:HKh(x)⊕HKh(x′)=y]≤ϵ. If δ=2-n, H is called an ϵ uniform AXU (ϵ-AXU for short) hash function.Finite Field.Given a basis, the finite field GF(2n) can be seen as the set {0,1}n. For an n-bit string a=an-1⋯a1a0, we can define a polynomial a(x)∈Z[x] by a(x)=an-1xn-1+⋯+a1x+a0, where ai∈{0,1} for any i∈[0,n-1]. Hence, any integer between 0 and 2n-1 can also be viewed as a polynomial with binary coefficients of degree at most n-1. For example, 2 corresponds to x, 3 corresponds to x+1, and 7 corresponds to x2+x+1. The addition in the field GF(2n) is the addition of polynomials over GF(2). We denote this operation by bitwise XOR, that is, a⊕b, where a,b∈GF(2n). In order to define the multiplication operation over GF(2n), we need to introduce an irreducible polynomial f(x) of degree n over GF(2). For n=128,  f(x)=x128+x7+x2+x+1. The multiplication of two elements A∈GF(2n) and B∈GF(2n) is defined as the corresponding polynomial multiplication over GF(2) reduced modulo f(x), that is A(x)B(x) mod f(x).Authenticated Encryption.A conventional nonce-based authenticated encryption with associated data (AEAD) scheme Π consists of an encryption algorithm E:K×N×H×M→C×T and a decryption algorithm D:K×N×H×C×T→M∪{⊥}; that is, (3)C,T⟵EKN,A,M=EK,N,A,M,M⊥⟵DKN,A,C,T=DK,N,A,C,T, where K∈K is a key, N∈N is a nonce, A∈H is associated data, H⊆{0,1}∗, M∈M is a plaintext, M⊆{0,1}∗, C∈C is a ciphertext, C⊆{0,1}∗, T∈T is a tag, T⊆{0,1}∗, and ⊥ is an error symbol which indicates the failure of the decryption oracle. EK(N,A,M)=(C,T) iff DK(N,A,C,T)=M. A secure AEAD scheme returns ⊥ if it receives an error (N,A,C,T) pair. If there is no associated data, A is seen as an empty string.


## 3. Basic Tool: Close to Optimally Secure PRFs

### 3.1. Multi-Encrypted-Davies-Meyer (Multi-EDM) FunctionF1

In this section, we set up a new functionF1 which is constructed from the EDM construction [45].Assuming thatP1 and P2 are two independent and random permutations on n-bit, we define a function F1:{0,1}l→{0,1}ns as F1(x)=(y1,y2,…,ys), where yi=P2(P1(inci(x∥[0]n-l))⊕inci(x∥[0]n-l))∈{0,1}n for i∈[1,s],l≤n, and x∈{0,1}l. Note that we must ensure s≤2n-l-1.We have the following theorem for information-theoretic security of the functionF1.Theorem 1.
LetA be an adversary with access to the function F1. Let ξ≥2 be any threshold. Assuming that A makes at most q≤2n/(67ξ2) oracle queries, generating at most σ=qs blocks, then the PRF-advantage of A against F1 is upper-bounded by (4)AdvF1prfA≤σ2n+σξ+12nξ.The result of Theorem1 shows that F1 constructed by P1 and P2 achieves BBB security. If ξ=2 and q≤2n-8, then the PRF-advantage of A against F1 is upper-bounded by 1.5σ3/2/2n, which means that F1 is a provably BBB-secure PRF up to approximately 22n/3 adversarial queries. If ξ=n-1 and q≤2n/67(n-1)2, then the PRF-advantage of A against F1 is upper-bounded by σ/2n, which means that F1 is a close to optimally secure PRF up to approximately 2n/67(n-1)2 adversarial queries.The proof of Theorem1 utilizes the hybrid technique. The security of the function F1 can be reduced to the security of the EDM construction [46] which utilizes Patarin’s mirror theory.Proof.
LetR←$Func(l,ns) and r←$Func(l,n); then the PRF-advantage of A against the function F1 is shown as follows: (5)AdvF1prfA=PrAF1·=1-PrAR·=1.
Letf:{0,1}l→{0,1}n be a reduced EDM construction obtained by fixing n-l bits. Let B be an adversary which has access to the reduced EDM function f or the random function r and makes qi queries for the ith f. According to the security of the EDM construction, if q≤2n/67ξ2 and ξ≥2, we have (6)AdvfprfB=PrBf·=1-PrBr·=1≤qi2n+qiξ+12nξ.
We construct a hybrid functionHsi as follows. The first i functions are f and the rest of the functions are r, that is, Hsi=(f,…,f︸i,r,…,r︸s-i). If i=0, then Hs0=(r,…,r︸s)=R. If i=s, then Hss=(f,…,f︸s)=F1. Then the PRF-advantage of A against F1 is upper-bounded by (7)AdvF1prfA=PrAF1·=1-PrAR·=1=PrAHss=1-PrAHs0=1=∑iPrAHsi+1=1-PrAHsi=1≤∑iPrBf·=1-PrBr·=1≤∑iqi2n+qiξ+12nξ≤σ2n+σξ+12nξ,where the inequality is obtained by ∑i‍qi=σ. The proof is finished.


### 3.2. Multi-EDM-Dual (Multi-EDMD) FunctionF2

In this section, we set up another new functionF2 which is constructed from the EDMD construction [46].Assuming thatP1 and P2 are two independent and random permutations on n-bit, we define a function F2:{0,1}l→{0,1}ns as F2(x)=(y1,y2,…,ys), where yi=P2(P1(inci(x∥[0]n-l)))⊕P1(inci(x∥[0]n-l))∈{0,1}n for i∈[1,s], s≤2n-l-1,  l≤n, and x∈{0,1}l.We have the following theorem for information-theoretic security of the functionF2.Theorem 2.
LetA be an adversary with access to the function F2. Assuming that A makes at most q≤2n/67 oracle queries, generating at most σ=qs blocks, then the PRF-advantage of A against F2 is upper-bounded by (8)AdvF2prfA≤σ2n.The proof of Theorem2 is similar to that of Theorem 1. Therefore, here we omit it.The result of Theorem2 shows that F2 constructed by P1 and P2 is a provably secure PRF up to approximately 2n/67 adversarial queries; that is, F2 achieves close to optimal security. This is consistent with the views of Mennink and Neves [48].


## 3.1. Multi-Encrypted-Davies-Meyer (Multi-EDM) FunctionF1

In this section, we set up a new functionF1 which is constructed from the EDM construction [45].Assuming thatP1 and P2 are two independent and random permutations on n-bit, we define a function F1:{0,1}l→{0,1}ns as F1(x)=(y1,y2,…,ys), where yi=P2(P1(inci(x∥[0]n-l))⊕inci(x∥[0]n-l))∈{0,1}n for i∈[1,s],l≤n, and x∈{0,1}l. Note that we must ensure s≤2n-l-1.We have the following theorem for information-theoretic security of the functionF1.Theorem 1.
LetA be an adversary with access to the function F1. Let ξ≥2 be any threshold. Assuming that A makes at most q≤2n/(67ξ2) oracle queries, generating at most σ=qs blocks, then the PRF-advantage of A against F1 is upper-bounded by (4)AdvF1prfA≤σ2n+σξ+12nξ.The result of Theorem1 shows that F1 constructed by P1 and P2 achieves BBB security. If ξ=2 and q≤2n-8, then the PRF-advantage of A against F1 is upper-bounded by 1.5σ3/2/2n, which means that F1 is a provably BBB-secure PRF up to approximately 22n/3 adversarial queries. If ξ=n-1 and q≤2n/67(n-1)2, then the PRF-advantage of A against F1 is upper-bounded by σ/2n, which means that F1 is a close to optimally secure PRF up to approximately 2n/67(n-1)2 adversarial queries.The proof of Theorem1 utilizes the hybrid technique. The security of the function F1 can be reduced to the security of the EDM construction [46] which utilizes Patarin’s mirror theory.Proof.
LetR←$Func(l,ns) and r←$Func(l,n); then the PRF-advantage of A against the function F1 is shown as follows: (5)AdvF1prfA=PrAF1·=1-PrAR·=1.
Letf:{0,1}l→{0,1}n be a reduced EDM construction obtained by fixing n-l bits. Let B be an adversary which has access to the reduced EDM function f or the random function r and makes qi queries for the ith f. According to the security of the EDM construction, if q≤2n/67ξ2 and ξ≥2, we have (6)AdvfprfB=PrBf·=1-PrBr·=1≤qi2n+qiξ+12nξ.
We construct a hybrid functionHsi as follows. The first i functions are f and the rest of the functions are r, that is, Hsi=(f,…,f︸i,r,…,r︸s-i). If i=0, then Hs0=(r,…,r︸s)=R. If i=s, then Hss=(f,…,f︸s)=F1. Then the PRF-advantage of A against F1 is upper-bounded by (7)AdvF1prfA=PrAF1·=1-PrAR·=1=PrAHss=1-PrAHs0=1=∑iPrAHsi+1=1-PrAHsi=1≤∑iPrBf·=1-PrBr·=1≤∑iqi2n+qiξ+12nξ≤σ2n+σξ+12nξ,where the inequality is obtained by ∑i‍qi=σ. The proof is finished.


## 3.2. Multi-EDM-Dual (Multi-EDMD) FunctionF2

In this section, we set up another new functionF2 which is constructed from the EDMD construction [46].Assuming thatP1 and P2 are two independent and random permutations on n-bit, we define a function F2:{0,1}l→{0,1}ns as F2(x)=(y1,y2,…,ys), where yi=P2(P1(inci(x∥[0]n-l)))⊕P1(inci(x∥[0]n-l))∈{0,1}n for i∈[1,s], s≤2n-l-1,  l≤n, and x∈{0,1}l.We have the following theorem for information-theoretic security of the functionF2.Theorem 2.
LetA be an adversary with access to the function F2. Assuming that A makes at most q≤2n/67 oracle queries, generating at most σ=qs blocks, then the PRF-advantage of A against F2 is upper-bounded by (8)AdvF2prfA≤σ2n.The proof of Theorem2 is similar to that of Theorem 1. Therefore, here we omit it.The result of Theorem2 shows that F2 constructed by P1 and P2 is a provably secure PRF up to approximately 2n/67 adversarial queries; that is, F2 achieves close to optimal security. This is consistent with the views of Mennink and Neves [48].


## 4. OGCM-1: Close to Optimally Secure Variant of GCM

In this section, we utilize the close to optimally secure PRFF1 to build an improved variant of GCM, called OGCM-1. OGCM-1 achieves close to optimal security in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP. OGCM-1 is a two-pass nonce-based AEAD scheme employing the “Encryption-then-MAC” approach, where the encryption part utilizes the close to optimally secure PRF F1 to set up a stream-cipher encryption mode and the MAC part combines an AXU hash function and the EDM construction to generate an authentication tag.Letn,k,l,τ>0 be integers. Fix a block cipher E:Ke×{0,1}n→{0,1}n and an ϵ-AXU hash function H:Kh×{0,1}∗×{0,1}∗→{0,1}n; the encryption algorithm of OGCM-1 is described as E:K×N×H×M→C×T, where K=Ke2×Kh={0,1}k is the key space, N={0,1}l is the nonce space, H⊆{0,1}∗ is the associated data space, M⊆{0,1}∗ is the plaintext space, C⊆{0,1}∗ is the ciphertext space, and T={0,1}τ is the tag space. It takes the key K=(K1,K2,Kh)∈K, the nonce N∈N, the associated data A∈H, and the plaintext M∈M as input and returns the ciphertext C∈C and the tag T∈T, where K1,K2∈Ke and Kh∈Kh. The decryption algorithm of OGCM-1 D:K×N×H×C×T→M∪⊥ is the inverse of the encryption algorithm E. It takes K=(K1,K2,Kh),N,A,C, and T as input and returns either M or a special symbol ⊥. Here ⊥ always returns a failure of the decryption oracle.The overview of OGCM-1 is depicted in Figure1. The encryption and decryption algorithms of OGCM-1 are given in Algorithms 1, 2, and 3. We recommend restricting AES-OGCM-1 to 96-bit nonces; that is, n=128 and l=96.Algorithm 1:The encryption algorithm of OGCM-1.
Input: three keys (K1,K2,Kh), a nonce N, an associated data A, and a plaintext M Output: a ciphertext C and a tag T Partition M into M1∥⋯∥Mm, M i = n for 1≤i≤m-1 and 0<Mm≤n Y 0 = N ∥ 0 n - l - 1 1 S 0 ← E K 2 E K 1 Y 0 ⊕ Y 0 for i=1 to m Y i ← i n c Y i - 1 S i ← E K 2 E K 1 Y i ⊕ Y i for i=1 to m-1 C i ← S i ⊕ M i C m ← msb | M m | ⁡ ( S m ) ⊕ M m C ← C 1 ∥ ⋯ ∥ C m S ← S 0 ⊕ H K h ( A , C ) T ← msb τ ⁡ ( S ) return C∥TAlgorithm 2:The decryption algorithm of OGCM-1.
Input: three keys (K1,K2,Kh), a nonce N, an associated data A, a ciphertext C, and a tag T Output: a plaintext M or ⊥ Y 0 = N ∥ 0 n - l - 1 1 S 0 ← E K 2 E K 1 Y 0 ⊕ Y 0 S ← S 0 ⊕ H K h A , C T ′ ← msb τ ⁡ S If T′=T, then Partition C into C1∥⋯∥Cm, | C i | = n for 1≤i≤m-1 and 0<|Cm|≤n for i=1 to m Y i ← i n c Y i - 1 S i ← E K 2 E K 1 Y i ⊕ Y i for i=1 to m-1 M i ← S i ⊕ C i M m ← msb | C m | ⁡ ( S m ) ⊕ C m M ← M 1 ∥ ⋯ ∥ M m return M else return ⊥.Algorithm 3:The hash algorithm HKh(A,C).
Input: a hash key Kh, an associated data A, and a ciphertext C Output: a hash value H X ← A ∥ 0 A n ⋅ n - | A | ∥ C ∥ 0 C n ⋅ n - | C | ∥ A n / 2 ∥ C n / 2 Partition X into X1∥⋯∥Xx, |Xi|=n for 1≤i≤x H ← 0 for i=1 to x H ← H ⊕ X i ⋅ K h returnHFigure 1
OGCM-1: a close to optimally secure variant of GCM.


## 5. Security of OGCM-1

### 5.1. Security Models of AEAD Schemes

Privacy (confidentiality) and authenticity (integrity) are two important security metrics of AEAD modes. Letk≥1 be an integer, K←${0,1}k be the key randomly drawn from {0,1}k, and Π=(EK(·,·,·),DK(·,·,·,·)) be a nonce-based AEAD scheme.Privacy.Let $(·,·,·) be a random oracle that takes (N,A,M) as input and returns a random string of length |C|+|T|. Let A be an adversary which has access to an oracle (either the encryption oracle EK(·,·,·) or the random oracle $(·,·,·)) and returns b∈{0,1}. We say that A is a nonce-respecting adversary if all nonces N1,…,Nq are always distinct for all encryption queries (N1,A1,M1),…,(Nq,Aq,Mq). Without loss of generality, we assume that A is a nonce-respecting adversary and never makes trivial queries for which their responses are obviously known. Then the PRIV-advantage of A against Π=(EK(·,·,·),DK(·,·,·,·)) is defined as (9)AdvΠprivA=PrAEK·,·,·=1-PrA$·,·,·=1.Authenticity.Let A be an adversary which has access to the encryption oracle EK(·,·,·) and the decryption oracle DK(·,·,·,·). Firstly, the adversary A queries (Ni,Ai,Mi) to EK(·,·,·) and returns (Ci,Ti)=EK(Ni,Ai,Mi), where i∈[1,q]. Then A forges a challenge query (N,A,C,T)∉{(Ni,Ai,Ci,Ti)}i=1q to DK(·,·,·,·). The forgery attempt succeeds if DK(N,A,C,T)≠⊥. Without loss of generality, we assume that A is a nonce-respecting adversary and never makes trivial queries for which their responses are obviously known. Then the AUTH-advantage of A against Π=(EK(·,·,·),DK(·,·,·,·)) is defined as (10)AdvΠauthA=PrAEK·,·,·,DK·,·,·,·forges.


### 5.2. Main Results and Security Proofs

Assuming that the underlying block cipherE is a secure PRP, OGCM-1 achieves close to optimal security in the information-theoretic setting. Detailedly speaking, the privacy and authenticity of OGCM-1 are provably secure up to q≃2n/67(n-1)2 adversarial queries in the nonce-respecting scenario if the underlying block cipher is a secure PRP. First, we present the privacy of OGCM-1 as follows.Theorem 3 (privacy of OGCM-1).
LetE:Ke×{0,1}n→{0,1}n be a block cipher and H:Kh×{0,1}∗×{0,1}∗→{0,1}n be an ϵ-AXU hash function, where Ke and Kh are two nonempty sets of keys. Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 queries with the maximum block length m and the running time t to OGCM-1. Then there exists another adversary A′ against the PRP-security of E, making at most σ=q(m+1) oracle queries and running in time at most O(t+t(σ)), such that, for any adversary A, (11)AdvOGCM-1EprivA≤2AdvEprpA′+σ2n.The proof of Theorem3 includes two steps. Firstly, we replace EK1 and EK2 with two random and independent permutations on n-bit P1 and P2, where K1 and K2 are randomly and independently drawn from Ke. Let P=(P1,P2) and let OGCM-1[P] be the new construction. By the hybrid argument, it is easy to show that there exists another adversary A′ against the PRP-security of E, making at most σ=q(m+1) oracle queries and running in time at most t′=O(t+t(σ)), such that(12)AdvOGCM-1EprivA≤2AdvEprpA′+AdvOGCM-1PprivA.Then, our goal is to upper-bound AdvOGCM-1[P]priv(A). Therefore, we introduce Lemma 4 as follows.Lemma 4.
LetP=(P1,P2) be two permutations randomly and independently chosen from Perm(n). Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 queries to OGCM-1[P], generating at most σ blocks. Then, for any adversary A,(13)AdvOGCM-1PprivA≤σ2n.Proof.
Our proof utilizes a contradiction argument. The main idea is as follows. If there exists a nonce-respecting adversaryA against OGCM-1[P] such that AdvOGCM-1[P]priv(A)>σ/2n, then we can construct a nonce-respecting adversary B against F1 such that AdvF1prf(B)>σ/2n, which derives a contradiction with Theorem 1. The details of our proof are described as follows.
LetE[P] be the encryption algorithm of OGCM-1[P] and $ be a random function that takes (N,A,M) as input and always returns a random string of length |C|+|T|. Suppose, to the contrary, that there exists a nonce-respecting adversary A against OGCM-1[P] such that (14)AdvOGCM-1PprivA=Pr⁡AEP·,·,·=1-PrA$·,·,·=1>σ2n, where A makes q queries with the block length m to OGCM-1[P], generating σ=q(m+1) blocks.
LetR∈Func(l,ns) be a random function, where s=m+1. Consider an adversary B that makes q queries to an oracle O, either F1 or R, generating σ=qs blocks, where B uses A as a subroutine (see Algorithm 4).
IfO is F1, then B provides a perfect simulation of E[P] for A. Therefore, Pr[BF1(·)=1]=Pr[AE[P](·,·,·)=1]. Similarity, if O is R, then B provides a perfect simulation of the random function $ for A. Therefore, Pr[BR(·)=1]=Pr[A$(·,·,·)=1]. It follows that (15)AdvF1prfB=PrBF1·=1-PrBR·=1=PrAEP·,·,·=1-PrA$·,·,·=1=AdvOGCM-1PprivA>σ2n, which contradicts Theorem 1. Therefore, our (contradiction) hypothesis does not hold; that is, the original proposition holds where (16)AdvOGCM-1PprivA≤σ2n. The proof of Lemma 4 is finished.Algorithm 4:Codes of PRF-adversary B against F1 using the PRIV-adversary A.
/ PRF-adversaryB against F1 / If  A  makes the ith query  (Ni,Ai,Mi): m = M i / n X i = N i ∥ 0 n - l ,   K h ← $ K h S 0 i ∥ S 1 i ∥ ⋯ ∥ S m i = O ( X i ) for j=1 to m-1:Cji=Mji⊕Sji C m i = M m i ⊕ m s b | M m i | ( S m i ) C i = C 1 i ∥ C 2 i ∥ ⋯ ∥ C m i T i = m s b τ ( S 0 i ⊕ H K h ( A i , C i ) ) return (Ci,Ti) If  A  returns  b: output bTherefore, combining (12) and (13), the result of Theorem 3 is derived. The privacy of OGCM-1 is secure up to q≃2n/67(n-1)2 adversarial queries in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP. Next, we provide the authenticity of OGCM-1.Theorem 5 (authenticity of OGCM-1).
LetE:Ke×{0,1}n→{0,1}n be a block cipher and H:Kh×{0,1}∗×{0,1}∗→{0,1}n be an ϵ-AXU hash function, where Ke and Kh are two nonempty sets of keys. Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 encryption queries and one forgery attempt to OGCM-1. The maximum block length is m and the running time is at most t. Then there exists another adversary A′ against the PRP-security of E, making at most σ=(q+1)(m+1) oracle queries and running in time at most O(t+t(σ)), such that, for any adversary A, (17)AdvOGCM-1EauthA≤2AdvEprpA′+σ2n+ϵ+n2n+12τ-q.The proof of Theorem5 includes two steps. Firstly, we replace EK1 and EK2 with two random and independent permutations P1 and P2. Let P=(P1,P2) and let OGCM-1[P] be the new construction. It is easy to show that there exists another adversary A′ against the PRP-security of E, making at most σ=(q+1)(m+1) oracle queries and running in time at most t′=O(t+t(σ)), such that(18)AdvOGCM-1EauthA≤2AdvEprpA′+AdvOGCM-1PauthA.Next, our goal is to upper-bound AdvOGCM-1[P]auth(A). Therefore, we introduce Lemma 6 as follows.Lemma 6.
Letτ>0 be an integer. Let P=(P1,P2) be two permutations randomly and independently chosen from Perm(n). Let H be an ϵ-AXU hash function. Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 encryption queries and one forgery attempt to OGCM-1[P], generating at most σ blocks. Then, for any adversary A,(19)AdvOGCM-1PauthA≤σ2n+ϵ+n2n+12τ-q.Proof.
We assume that the nonce-respecting adversaryA makes one forgery attempt after q encryption queries, generating at most σ blocks. Detailedly speaking, A firstly makes q queries (N1,A1,M1),…,(Nq,Aq,Mq) to the encryption oracle and returns (C1,T1),…,(Cq,Tq). Then A makes one forgery attempt (N′,A′,C′,T′) to the decryption oracle. Note that (N′,A′,C′,T′)∉{(Ni,Ai,Ci,Ti)}i=1q.
According to the definition of the AUTH-advantage, we have(20)AdvOGCM-1PauthA=PrAEP,DPforges(21)≤PrAEP,DPforges-PrA$1,$2forges(22)+PrA$1,$2forges, where E[P],D[P] are the encryption and decryption algorithms of OGCM-1[P], $1 is a random oracle which always returns a random string (C,T)←$C×T, and $2 is a random oracle which always returns a random string or a reject symbol; that is, M/⊥←$M∪{⊥}.
For (21), we have(23)21=AdvOGCM-1Pprivq+1,σ≤σ2n,which is shown in the privacy proof and σ=(q+1)(m+1).
For (22), we consider the forgery attempt (N′,A′,C′,T′). As A is a nonce-respecting adversary, there is at most one response (Ni,Ai,Ci,Ti) of the encryption oracle such that N′=Ni, where i∈[1,q]. Assuming that there exists a dummy key Kh, we discuss the following two cases in the single forgery attempt.
Case 1.There exist one (Ni,Ai,Ci,Ti) such that N′=Ni for some i∈[1,q]. According to the properties of the AXU hash function H, we have (24)PrmsbτHKhA′,C′⊕HKhAi,Ci=T′⊕Ti≤ϵ.
Case 2.There is no (Ni,Ai,Ci,Ti) such that N′=Ni for any i∈[1,q]; that is, N′ is new. Let l be the nonce length. We consider the following subcases in this case.
Case 2-1.There exist (Ai,Ci,Ti)=(A′,C′,T′) for multiple i∈[1,q]. In the encryption queries, there are at most n-1 collisions for q≤2n/67(n-1)2 queries; that is, the number of the same (Ai,Ci,Ti) pair is at most n-1. Then we have (25)PrP2P1Y0i⊕Y0i=P2P1Y0′⊕Y0′≤n-12n, where Y0i=Ni∥0n-l-11 and Y0′=N′∥0n-l-11.
Case 2-2.There is no (Ai,Ci,Ti)=(A′,C′,T′) for any i∈[1,q]. In this subcase, we further discuss the following two subcases.
Case 2-2-1.There exist (Ai,Ci)=(A′,C′) and Ti≠T′ for some i∈[1,q]. Then HKh(Ai,Ci)=HKh(A′,C′). Therefore, we have (26)PrmsbτS0i⊕S0′=Ti⊕T′≤12τ-q,where S0i=P2(P1(Y0i)⊕Y0i),  Y0i=Ni∥0n-l-11,  S0′=P2(P1(Y0′)⊕Y0′), and Y0′=N′∥0n-l-11.
Case 2-2-2.There is no (Ai,Ci)=(A′,C′) for any i∈[1,q]. According to the properties of the AXU hash function H, we have (27)PrmsbτS0′⊕HKhA′,C′=T′≤12n,where S0′=P2(P1Y0′⊕Y0′) and Y0′=N′∥0n-l-11.
Summarizing above all mutually exclusive cases, the success probability of the single forgery attempt is upper-bounded by(28)ϵ+n2n+12τ-q.
Combining (21), (22), (23), and (28), the AUTH-advantage of A against OGCM-1[P] is upper-bounded by (29)AdvOGCM-1PauthA≤σ2n+ϵ+n2n+12τ-q. The proof of Lemma 6 is finished.Therefore, combining (18) and (19), the result of Theorem 5 is derived. If ϵ≃2-n and τ=n, the authenticity of OGCM-1 is secure up to q≃2n/67(n-1)2 adversarial queries in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP.


## 5.1. Security Models of AEAD Schemes

Privacy (confidentiality) and authenticity (integrity) are two important security metrics of AEAD modes. Letk≥1 be an integer, K←${0,1}k be the key randomly drawn from {0,1}k, and Π=(EK(·,·,·),DK(·,·,·,·)) be a nonce-based AEAD scheme.Privacy.Let $(·,·,·) be a random oracle that takes (N,A,M) as input and returns a random string of length |C|+|T|. Let A be an adversary which has access to an oracle (either the encryption oracle EK(·,·,·) or the random oracle $(·,·,·)) and returns b∈{0,1}. We say that A is a nonce-respecting adversary if all nonces N1,…,Nq are always distinct for all encryption queries (N1,A1,M1),…,(Nq,Aq,Mq). Without loss of generality, we assume that A is a nonce-respecting adversary and never makes trivial queries for which their responses are obviously known. Then the PRIV-advantage of A against Π=(EK(·,·,·),DK(·,·,·,·)) is defined as (9)AdvΠprivA=PrAEK·,·,·=1-PrA$·,·,·=1.Authenticity.Let A be an adversary which has access to the encryption oracle EK(·,·,·) and the decryption oracle DK(·,·,·,·). Firstly, the adversary A queries (Ni,Ai,Mi) to EK(·,·,·) and returns (Ci,Ti)=EK(Ni,Ai,Mi), where i∈[1,q]. Then A forges a challenge query (N,A,C,T)∉{(Ni,Ai,Ci,Ti)}i=1q to DK(·,·,·,·). The forgery attempt succeeds if DK(N,A,C,T)≠⊥. Without loss of generality, we assume that A is a nonce-respecting adversary and never makes trivial queries for which their responses are obviously known. Then the AUTH-advantage of A against Π=(EK(·,·,·),DK(·,·,·,·)) is defined as (10)AdvΠauthA=PrAEK·,·,·,DK·,·,·,·forges.


## 5.2. Main Results and Security Proofs

Assuming that the underlying block cipherE is a secure PRP, OGCM-1 achieves close to optimal security in the information-theoretic setting. Detailedly speaking, the privacy and authenticity of OGCM-1 are provably secure up to q≃2n/67(n-1)2 adversarial queries in the nonce-respecting scenario if the underlying block cipher is a secure PRP. First, we present the privacy of OGCM-1 as follows.Theorem 3 (privacy of OGCM-1).
LetE:Ke×{0,1}n→{0,1}n be a block cipher and H:Kh×{0,1}∗×{0,1}∗→{0,1}n be an ϵ-AXU hash function, where Ke and Kh are two nonempty sets of keys. Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 queries with the maximum block length m and the running time t to OGCM-1. Then there exists another adversary A′ against the PRP-security of E, making at most σ=q(m+1) oracle queries and running in time at most O(t+t(σ)), such that, for any adversary A, (11)AdvOGCM-1EprivA≤2AdvEprpA′+σ2n.The proof of Theorem3 includes two steps. Firstly, we replace EK1 and EK2 with two random and independent permutations on n-bit P1 and P2, where K1 and K2 are randomly and independently drawn from Ke. Let P=(P1,P2) and let OGCM-1[P] be the new construction. By the hybrid argument, it is easy to show that there exists another adversary A′ against the PRP-security of E, making at most σ=q(m+1) oracle queries and running in time at most t′=O(t+t(σ)), such that(12)AdvOGCM-1EprivA≤2AdvEprpA′+AdvOGCM-1PprivA.Then, our goal is to upper-bound AdvOGCM-1[P]priv(A). Therefore, we introduce Lemma 4 as follows.Lemma 4.
LetP=(P1,P2) be two permutations randomly and independently chosen from Perm(n). Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 queries to OGCM-1[P], generating at most σ blocks. Then, for any adversary A,(13)AdvOGCM-1PprivA≤σ2n.Proof.
Our proof utilizes a contradiction argument. The main idea is as follows. If there exists a nonce-respecting adversaryA against OGCM-1[P] such that AdvOGCM-1[P]priv(A)>σ/2n, then we can construct a nonce-respecting adversary B against F1 such that AdvF1prf(B)>σ/2n, which derives a contradiction with Theorem 1. The details of our proof are described as follows.
LetE[P] be the encryption algorithm of OGCM-1[P] and $ be a random function that takes (N,A,M) as input and always returns a random string of length |C|+|T|. Suppose, to the contrary, that there exists a nonce-respecting adversary A against OGCM-1[P] such that (14)AdvOGCM-1PprivA=Pr⁡AEP·,·,·=1-PrA$·,·,·=1>σ2n, where A makes q queries with the block length m to OGCM-1[P], generating σ=q(m+1) blocks.
LetR∈Func(l,ns) be a random function, where s=m+1. Consider an adversary B that makes q queries to an oracle O, either F1 or R, generating σ=qs blocks, where B uses A as a subroutine (see Algorithm 4).
IfO is F1, then B provides a perfect simulation of E[P] for A. Therefore, Pr[BF1(·)=1]=Pr[AE[P](·,·,·)=1]. Similarity, if O is R, then B provides a perfect simulation of the random function $ for A. Therefore, Pr[BR(·)=1]=Pr[A$(·,·,·)=1]. It follows that (15)AdvF1prfB=PrBF1·=1-PrBR·=1=PrAEP·,·,·=1-PrA$·,·,·=1=AdvOGCM-1PprivA>σ2n, which contradicts Theorem 1. Therefore, our (contradiction) hypothesis does not hold; that is, the original proposition holds where (16)AdvOGCM-1PprivA≤σ2n. The proof of Lemma 4 is finished.Algorithm 4:Codes of PRF-adversary B against F1 using the PRIV-adversary A.
/ PRF-adversaryB against F1 / If  A  makes the ith query  (Ni,Ai,Mi): m = M i / n X i = N i ∥ 0 n - l ,   K h ← $ K h S 0 i ∥ S 1 i ∥ ⋯ ∥ S m i = O ( X i ) for j=1 to m-1:Cji=Mji⊕Sji C m i = M m i ⊕ m s b | M m i | ( S m i ) C i = C 1 i ∥ C 2 i ∥ ⋯ ∥ C m i T i = m s b τ ( S 0 i ⊕ H K h ( A i , C i ) ) return (Ci,Ti) If  A  returns  b: output bTherefore, combining (12) and (13), the result of Theorem 3 is derived. The privacy of OGCM-1 is secure up to q≃2n/67(n-1)2 adversarial queries in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP. Next, we provide the authenticity of OGCM-1.Theorem 5 (authenticity of OGCM-1).
LetE:Ke×{0,1}n→{0,1}n be a block cipher and H:Kh×{0,1}∗×{0,1}∗→{0,1}n be an ϵ-AXU hash function, where Ke and Kh are two nonempty sets of keys. Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 encryption queries and one forgery attempt to OGCM-1. The maximum block length is m and the running time is at most t. Then there exists another adversary A′ against the PRP-security of E, making at most σ=(q+1)(m+1) oracle queries and running in time at most O(t+t(σ)), such that, for any adversary A, (17)AdvOGCM-1EauthA≤2AdvEprpA′+σ2n+ϵ+n2n+12τ-q.The proof of Theorem5 includes two steps. Firstly, we replace EK1 and EK2 with two random and independent permutations P1 and P2. Let P=(P1,P2) and let OGCM-1[P] be the new construction. It is easy to show that there exists another adversary A′ against the PRP-security of E, making at most σ=(q+1)(m+1) oracle queries and running in time at most t′=O(t+t(σ)), such that(18)AdvOGCM-1EauthA≤2AdvEprpA′+AdvOGCM-1PauthA.Next, our goal is to upper-bound AdvOGCM-1[P]auth(A). Therefore, we introduce Lemma 6 as follows.Lemma 6.
Letτ>0 be an integer. Let P=(P1,P2) be two permutations randomly and independently chosen from Perm(n). Let H be an ϵ-AXU hash function. Let A be a nonce-respecting adversary which makes at most q≤2n/67(n-1)2 encryption queries and one forgery attempt to OGCM-1[P], generating at most σ blocks. Then, for any adversary A,(19)AdvOGCM-1PauthA≤σ2n+ϵ+n2n+12τ-q.Proof.
We assume that the nonce-respecting adversaryA makes one forgery attempt after q encryption queries, generating at most σ blocks. Detailedly speaking, A firstly makes q queries (N1,A1,M1),…,(Nq,Aq,Mq) to the encryption oracle and returns (C1,T1),…,(Cq,Tq). Then A makes one forgery attempt (N′,A′,C′,T′) to the decryption oracle. Note that (N′,A′,C′,T′)∉{(Ni,Ai,Ci,Ti)}i=1q.
According to the definition of the AUTH-advantage, we have(20)AdvOGCM-1PauthA=PrAEP,DPforges(21)≤PrAEP,DPforges-PrA$1,$2forges(22)+PrA$1,$2forges, where E[P],D[P] are the encryption and decryption algorithms of OGCM-1[P], $1 is a random oracle which always returns a random string (C,T)←$C×T, and $2 is a random oracle which always returns a random string or a reject symbol; that is, M/⊥←$M∪{⊥}.
For (21), we have(23)21=AdvOGCM-1Pprivq+1,σ≤σ2n,which is shown in the privacy proof and σ=(q+1)(m+1).
For (22), we consider the forgery attempt (N′,A′,C′,T′). As A is a nonce-respecting adversary, there is at most one response (Ni,Ai,Ci,Ti) of the encryption oracle such that N′=Ni, where i∈[1,q]. Assuming that there exists a dummy key Kh, we discuss the following two cases in the single forgery attempt.
Case 1.There exist one (Ni,Ai,Ci,Ti) such that N′=Ni for some i∈[1,q]. According to the properties of the AXU hash function H, we have (24)PrmsbτHKhA′,C′⊕HKhAi,Ci=T′⊕Ti≤ϵ.
Case 2.There is no (Ni,Ai,Ci,Ti) such that N′=Ni for any i∈[1,q]; that is, N′ is new. Let l be the nonce length. We consider the following subcases in this case.
Case 2-1.There exist (Ai,Ci,Ti)=(A′,C′,T′) for multiple i∈[1,q]. In the encryption queries, there are at most n-1 collisions for q≤2n/67(n-1)2 queries; that is, the number of the same (Ai,Ci,Ti) pair is at most n-1. Then we have (25)PrP2P1Y0i⊕Y0i=P2P1Y0′⊕Y0′≤n-12n, where Y0i=Ni∥0n-l-11 and Y0′=N′∥0n-l-11.
Case 2-2.There is no (Ai,Ci,Ti)=(A′,C′,T′) for any i∈[1,q]. In this subcase, we further discuss the following two subcases.
Case 2-2-1.There exist (Ai,Ci)=(A′,C′) and Ti≠T′ for some i∈[1,q]. Then HKh(Ai,Ci)=HKh(A′,C′). Therefore, we have (26)PrmsbτS0i⊕S0′=Ti⊕T′≤12τ-q,where S0i=P2(P1(Y0i)⊕Y0i),  Y0i=Ni∥0n-l-11,  S0′=P2(P1(Y0′)⊕Y0′), and Y0′=N′∥0n-l-11.
Case 2-2-2.There is no (Ai,Ci)=(A′,C′) for any i∈[1,q]. According to the properties of the AXU hash function H, we have (27)PrmsbτS0′⊕HKhA′,C′=T′≤12n,where S0′=P2(P1Y0′⊕Y0′) and Y0′=N′∥0n-l-11.
Summarizing above all mutually exclusive cases, the success probability of the single forgery attempt is upper-bounded by(28)ϵ+n2n+12τ-q.
Combining (21), (22), (23), and (28), the AUTH-advantage of A against OGCM-1[P] is upper-bounded by (29)AdvOGCM-1PauthA≤σ2n+ϵ+n2n+12τ-q. The proof of Lemma 6 is finished.Therefore, combining (18) and (19), the result of Theorem 5 is derived. If ϵ≃2-n and τ=n, the authenticity of OGCM-1 is secure up to q≃2n/67(n-1)2 adversarial queries in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP.


## 6. OGCM-2: A Dual Variant of OGCM-1

In this section, we utilize the close to optimally secure PRFF2 to build another improved variant of GCM, called OGCM-2. OGCM-2 achieves close to optimal security in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP. OGCM-2 is a two-pass nonce-based AEAD scheme employing the “Encryption-then-MAC” approach, where the encryption part utilizes a multi-EDMD function F2 to set up a stream-cipher encryption mode and the MAC part combines an AXU hash function and the EDMD construction to generate an authentication tag.The overview of OGCM-2 is depicted in Figure2. The encryption and decryption algorithms of OGCM-2 are given in Algorithms 5 and 6.Algorithm 5:The encryption algorithm of OGCM-2.
Input: three keys (K1,K2,Kh), a nonce N, an associated data A, and a plaintext M Output: a ciphertext C and a tag T Partition M into M1∥⋯∥Mm, | M i | = n for 1≤i≤m-1 and 0<|Mm|≤n Y 0 = N ∥ 0 n - l - 1 1 S 0 ← E K 2 ( E K 1 ( Y 0 ) ) ⊕ E K 1 ( Y 0 ) for i=1 to m Y i ← i n c ( Y i - 1 ) S i ← E K 2 ( E K 1 ( Y i ) ) ⊕ E K 1 ( Y i ) for i=1 to m-1 C i ← S i ⊕ M i C m ← m s b | M m | ( S m ) ⊕ M m C ← C 1 ∥ ⋯ ∥ C m S ← S 0 ⊕ H K h ( A , C ) T ← m s b τ ( S ) return C∥TAlgorithm 6:The decryption algorithm of OGCM-2.
Input: three keys (K1,K2,Kh), a nonce N, an associated data A, a ciphertext C, and a tag T Output: a plaintext M or ⊥ Y 0 = N ∥ 0 n - l - 1 1 S 0 ← E K 2 ( E K 1 ( Y 0 ) ) ⊕ E K 1 ( Y 0 ) S ← S 0 ⊕ H K h ( A , C ) T ′ ← m s b τ ( S ) If T′=T, then Partition C into C1∥⋯∥Cm, | C i | = n for 1≤i≤m-1 and 0<|Cm|≤n for i=1 to m Y i ← i n c ( Y i - 1 ) S i ← E K 2 ( E K 1 ( Y i ) ) ⊕ E K 1 ( Y i ) for i=1 to m-1 M i ← S i ⊕ C i M m ← m s b | C m | ( S m ) ⊕ C m M ← M 1 ∥ ⋯ ∥ M m return M else return⊥.Figure 2
OGCM-2: a dual variant of OGCM-1.The security of OGCM-2 is derived in the following theorem.Theorem 7 (security of OGCM-2).
Letτ≥1. Let A be a nonce-respecting adversary which makes at most q≤2n/67 encryption queries and one forgery attempt and runs in time at most t to OGCM-2. Then there exists another adversary A′ against the PRP-security of E, making at most σ oracle queries and running in time at most O(t+t(σ)), such that, for any adversary A, (30)AdvOGCM-2EprivA≤2AdvEprpA′+σ2n,AdvOGCM-2EauthA≤2AdvEprpA′+σ2n+ϵ+n2n+12τ-q.The proof of Theorem7 is similar to the proofs of Theorems 3 and 5. Therefore we omit it.According to Theorem7, assuming that the underlying block cipher E is a secure PRP and ϵ≃2-n and τ=n, the privacy and authenticity of OGCM-2 are provably secure up to q≃2n/67 adversarial queries in the nonce-respecting scenario.


## 7. Discussions and Future Works

Compared with GCM, both OGCM-1 and OGCM-2 achieve a balance between the security and the efficiency.From the perspective of security, they enjoy close to optimal security in the nonce-respecting scenario assuming that the underlying block cipher is a secure PRP. They can encrypt at most2l plaintexts in the nonce-respecting scenario and the maximum block length of the plaintext is 2n-l-1, where l is the nonce length and n is the block size. The privacy of OGCM-1 (resp., OGCM-2) is upper-bounded by σ/2n and the authenticity of OGCM-1 (resp., OGCM-2) is upper-bounded by σ/2n+ϵ+n/2n+2/2τ, for q≃2n/67(n-1)2 (resp., q≃2n/67) adversarial queries and one forgery attempt, where q is the number of the encryption queries, σ is the query complexity, and τ is the bit length of the authentication tag. In other words, the privacy and authenticity of OGCM-1 ensure at most about (n-log⁡67-2log⁡(n-1))-bit security, while the privacy and authenticity of OGCM-2 ensure at most about (n-log⁡67)-bit security, where log⁡x denotes the log (base 2) of x. Let n=128,  l=96,  ϵ=2-n, and τ=128. AES-OGCM-1 and AES-OGCM-2 can encrypt at most 296 plaintexts in the nonce-respecting scenario, the maximum length of the plaintext is about 232 blocks (64 GBytes), and the privacy and authenticity achieve roughly 107.9565-bit or 121.9339-bit security which is better than those of AES-GCM (about 64-bit security). Alike GCM, OGCM-1 and OGCM-2 are based on polynomial AXU hash functions which may introduce some attacks, such as [36, 37, 42, 43].From the perspective of efficiency, they invoke two block ciphers for encrypting each plaintext block (that is to say, their rate is 1/2) and inherit most of the advantages of GCM (such as parallelizable, stream-cipher encryption, and high speed implementation). Specifically, they utilize three keys, call the underlying block cipher2m+2 times, and use a+m+1 finite-field multiplications, while GCM is based on one key, calls the underlying block cipher m+2 times, and utilizes a+m+1 finite-field multiplications, where m (resp., a) is the block length of the plaintext (resp., associated data). Compared with GCM, the efficiency is about half of it. Therefore, OGCM-1 and OGCM-2 compromise the efficiency of the software and hardware implementation to enhance the security.Compared with some existing BBB-secure AE schemes, OGCM-1 and OGCM-2 are block cipher-based nonce-respecting AE modes that ensure close to optimal security and provide good efficiency. Details are shown in Table2. Note that RWCTRN [47] is based on the PRF assumption. Therefore, its block size n is at least 256.Table 2
Comparison of AE schemes that provide BBB security. “A↷B” means A can be reduced to B. “n.r.” denotes nonce-respecting and “n.m.” denotes nonce-misuse. “PRP” stands for pseudorandom permutation, “TPRP” stands for tweakable PRP, and “PRF” stands for pseudorandom function. Let m be the block length of the plaintext and a be the block length of associated data. Let r,ω≥2 be two integers. Let ≃ stand for approximately equal to. For example, ≃128 means that it is approximately equal to 128.
CHM GCM-SIVr OGCM-1 OGCM-2 SCT SIVx RWCTRN # keys 1 r 2 + 2 r ↷ 3 r 3 ↷ 1 3 ↷ 1 1 1 2 ↷ 1 Nonce scenario n.r. n.m. n.r. n.r. n.m. n.m. n.r. Assumption PRP PRP PRP PRP TPRP TPRP PRF Block sizen 128 128 128 128 128 128 256 Security (bits) 85.3333 128 r / r + 1 107.9565 121.9339 ≃128 ≃128 248 # primitive Calls m + m / ω + 2 r ( m + r ) 2 m + 2 2 m + 2 a + 2 m + 3 a + 2 m + 2 m + 2 # multiplications a + m r ( a + m + 1 ) a + m + 1 a + m + 1 0 0 a + m + 1 Reference [30] [32] This paper This paper [12] [11] [47]OGCM-1 and OGCM-2 utilize three keys, which increase the cost of key management. Therefore, we introduce a key deriving method which converts a key to multiple keys. Here, the hash-function keyKh and the block cipher keys (K1,K2) can be derived from a secret key K by encrypting three distinct constants. Thus, we can obtain reduced single-key OGCM-1 and OGCM-2 schemes.This paper focuses on the strong security of GCM in the nonce-respecting scenario. A natural direction for future work is how we can design an improved mode that provides strong security in the nonce-misuse and even other misuse scenarios (e.g., the releasing of unverified plaintext and decryption misuse scenarios).


## 8. Conclusions

This paper focuses on the strong security of GCM and presents two close to optimally secure variants OGCM-1 and OGCM-2. They are based on the “Encryption-then-MAC” approach, where the encryption part utilizes multiple EDM or EDMD constructions to set up a close to optimally secure key-stream generator and then the MAC part combines an AXU hash function and one EDM or EDMD construction to generate an authentication tag. OGCM-1 and OGCM-2 achieve a balance between the security and the efficiency. In terms of security, OGCM-1 guarantees at most roughly(n-log⁡67-2log⁡(n-1))-bit security and OGCM-2 guarantees at most roughly (n-log⁡67)-bit security, where n is the block size. In terms of efficiency, their rate is 1/2; that is, they invoke two block ciphers for encrypting each plaintext block. Compared with GCM [33] and CHM [30], OGCM-1 and OGCM-2 guarantee stronger security but achieve lower efficiency. Compared with GCM-SIVr [32], OGCM-1 and OGCM-2 guarantee close to optimal security and achieve higher efficiency.GCM is a NIST recommended block cipher mode of operation and has wide applications, but it only ensures the birthday-bound security. OGCM-1 and OGCM-2 that provide close to optimal security are the extensions of GCM, which is of great significance in practice.



---

*Source: 9715947-2018-03-06.xml*