Keywords

1 Introduction

Authenticated encryption (AE) is a symmetric-key cryptographic scheme that provides confidentiality and authenticity of a message simultaneously. For example, GCM [19] and CCM [20] are the current NIST standard AE modes and used in TLS [37, 40] and many other protocols. Among many criteria, the state size of AE has become an important one as well as the speed, since it is a key factor determining the size of hardware implementation. It is the memory size needed to implement the cryptosystem, in which we exclude core implementation (e.g. blockcipher) including key register. Thus we only count the memory size for the implementation of the mode of operation itself.

With the rise of lightweight cryptography, a number of small-state AE schemes have been proposed. CLOC and SILC proposed by Iwata et al. [25, 26] in 2014 have 2n-bit state using n-bit blockcipher. In 2017, Chakraborti et al. proposed COFB [16] which has 1.5n-bit state size. Finally, Naito et al. proposed SAEB [36] and achieved n-bit state size which is essentially minimum as a mode of n-bit blockcipher. In the realm of permutation-based cryptography, the sponge AE schemes are known to have small state size [13]. However, these AEs are essentially serial to achieve small state size. Ideally, we want an AE scheme to perform good on a wide range of platforms, and parallelizability is very effective particularly for software on high-end to middle-end platforms. For example, AES runs about \(4\sim 8\) times faster in parallel on CPUs with AES instructions (AESNI), and the bitslice implementation of lightweight blockciphers typically run significantly (often by a order of magnitude) faster than the single-block implementation [12, 29] on modern CPUs with SIMD instructions. This observation and the current research trend in serial AEs of small-state size suggest a natural question: can we reduce the state size of a parallel AE?

To answer the above question, we study the seminal OCB mode of operation from the state size perspective. OCB has been known to be the most efficient parallel AE. It consists of three versions, namely OCB1 [39], OCB2 [38] and OCB3 [27], and the latest OCB3 is in the final portfolio of CAESAR competition and was standardized in RFC [1]. In the submissions to the NIST Lightweight Cryptography Standardization project [2], the structure of OCB has been adopted by a number of schemes. Among the three versions of OCB, OCB2 has the smallest state size (e.g. OCB3 needs around n blocks in memory for internal mask generation). Note that OCB2 has been shown to be insecure by Inoue et al. [23]; we employed the fix of OCB2 suggested in [23] called OCB2f (for convention, we use “OCB2” to mean this fix unless otherwise stated). The original OCB2 needs 3n-bit state, consisting of the blockcipher state and the mask applied to the blockcipher, and the checksum value to create the authentication tag. The last one is essentially a sum of the n-bit plaintext blocks.

We propose a way to reduce OCB’s state size. In our method, we halve the length of checksum and we can reduce 0.5n-bit state size from the original OCB. An important feature of our method is that it does not lose efficiency (the number of blockcipher calls needed) nor the essential bit security of OCB. When our method is instantiated with n-bit blockcipher, it needs \(m+O(1)\) blockcipher calls to encrypt m-block input (this feature is called rate-1). Moreover, it has n/2-bit security despite of the trade-off relationship between the state size and security. We find that halving the checksum value does not harm the bit security of OCB2, and with a careful (though simple) handling of last block, we actually achieve 2.5n-bit state size with our proposal called \({\mathrm {OCB}\text {-}\mathrm {hc}}\) (for half-checksum).

One of the factors that increases the implementation size is the need of blockcipher inverse in its circuit. OCB needs the inverse, while Minematsu’s OTR [31] derived from OCB is inverse-free. The state size of OTR is 4n bits as its operates on 2n-bit blocks, thus larger than OCB2. However, thanks to the inverse-freeness, the total implementation size is expected to be smaller, which is also beneficial to high-throughput implementation (see the results of ATHENA benchmarkFootnote 1 and [41]). Using a similar technique as \({\mathrm {OCB}\text {-}\mathrm {hc}}\), we propose \({\mathrm {OTR}\text {-}\mathrm {hc}}\) that has 3.5n-bit state with n/2-bit security.

We remark that improving OCB in any metric without losing the essential properties is already very tough. All versions of OCB have been extensively studied from various perspective, such as the provable security perspective [7, 14] or the efficiency of mask generation scheme [22, 33], or the misuse resistance [4, 8] or the security beyond \(O(2^{n/2})\) queries [21]. However, its general structure which determines the state size profile is already considered to be optimal since the inception. To the best of our knowledge, there is no previous work to reduce the state size, and 2.5n-bit state of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) is the smallest among the known parallel AE modes. Likewise, 3.5n-bit state size of \({\mathrm {OTR}\text {-}\mathrm {hc}}\) is the smallest among the known inverse-free, parallel AE modes, to our knowledge. See Table 1.

Our technique can be applied to some variants of OCB as well, such as OPP [22] which has a much larger block size than OCB-AES and thus the gain is larger.

Table 1. Comparison of existing schemes and ours. State size excludes the key register. Rate is the number of input blocks processed in one primitive call.
Full size table

2 Preliminaries

2.1 Notation

Let \(\mathbb {N}\) be the set of natural numbers. For \(n\in \mathbb {N}\), we define \(\{0,1\}^n\) as the set of n-bit strings and \(\{0,1\}^*\) as the set of all binary strings, including the empty string \(\varepsilon \). For \(A, B \in \{0, 1\}^{*}\), \(A\,\Vert \,B\) denotes the concatenation of A and B. The bit length of a string A is denoted by |A|, and \(|A|_n:=\lceil |A|/n \rceil \). Dividing a string A into blocks of n bits is denoted by \(A[1]\,\Vert \,\cdots \,\Vert \,A[m]\xleftarrow {n}A\), where \(m=|A|_n\) and \(|A[i]| = n\), \(|A[m]| \le n\) for \(1 \le i \le m-1\). For \(t\in \mathbb {N}\) and \(t\le |A|\), \(\mathtt {msb}_t(A)\) denotes the first t bits of A and \(\mathtt {lsb}_t(A)\) denotes the last t bits of A. A sequence of i zeros (ones) is written as \(0^i\) (\(1^i\)). When \(|A|=n'<n\), we define \(\mathtt {ozp}(A):=A\,\Vert \,10^{n-n'-1}\), where \(10^0=1\). When \(|A|=n'=n\), \(\mathtt {ozp}(A):=A\). When the element K is uniformly and randomly chosen from the set \(\mathcal{K}\), it is denoted by \(K \xleftarrow {\$} \mathcal{K}\).

2.2 (Tweakable) Blockcipher

Let \(\mathcal{K}\) and \(\mathcal{M}\) be the set of keys and messages, respectively. Let \(\mathcal{T}\) be the set of tweaks, where a tweak is a public parameter. A tweakable blockcipher (TBC) [28] is a function \(\widetilde{E}: \mathcal{K}\times \mathcal{T}\times \mathcal{M}\rightarrow \mathcal{M}\) s.t. \(\widetilde{E}(K, T, \cdot )\) is a permutation on \(\mathcal{M}\) for \(\forall (K, T)\in \mathcal{K}\times \mathcal{T}\). It is also denoted by \(\widetilde{E}^T_K\), \(\widetilde{E}^T\) or \(\widetilde{E}\), where \(K\in \mathcal{K}\) and \(T \in \mathcal{T}\). If \(\mathcal{T}\) is singleton (and we thus omit it from the notation) it means a plain blockcipher. Namely, a blockcipher E is defined as \(E: \mathcal{K}\times \mathcal{M}\rightarrow \mathcal{M}\) s.t. \(E(K, \cdot )\) is a permutation on \(\mathcal{M}\) for \(\forall K \in \mathcal{K}\) and also denoted by \(E_K\) or E.

Let \({\mathsf {Perm}}(n)\) denote the set of all permutations on \(\{0, 1\}^n\). A tweakable permutation is a function \(\pi : \{0, 1\}^t \times \{0, 1\}^n \rightarrow \{0, 1\}^n\) s.t. for \(\forall T \in \{0, 1\}^t\), \(\pi (T, \cdot ) \in {\mathsf {Perm}}(n)\). Let \(\widetilde{{\mathsf {Perm}}}(t, n)\) denote the set of above all functions \(\pi \). Let \({\mathsf {P}}\) s.t. \({\mathsf {P}}\xleftarrow {\$}{\mathsf {Perm}}(n)\) be a uniform random permutation (URP) and \(\widetilde{{\mathsf {P}}}\) s.t. \(\widetilde{{\mathsf {P}}}\xleftarrow {\$}\widetilde{{\mathsf {Perm}}}(t, n)\) be a tweakable URP (TURP). A blockcipher E or a TBC \(\widetilde{E}\) is said to be secure if it is computationally hard to distinguish from the ideal primitive with oracle access. More precisely, let \(\mathcal{A}\) be an adversary who (possibly adaptively) queries to an oracle O and subsequently outputs a bit. We write \(\Pr [\mathcal{A}^{O}\rightarrow 1]\) to denote the probability that this bit is 1. We define the notions of advantage of \(\mathcal{A}\) as

$$\begin{aligned}&{\mathbf {Adv}}^{{\mathrm {prp}}}_{E}(\mathcal{A}) := | {\mathrm {Pr}}[\mathcal{A}^{E} \rightarrow 1] - {\mathrm {Pr}}[\mathcal{A}^{{\mathsf {P}}} \rightarrow 1] |, \\&{\mathbf {Adv}}^{{\mathrm {sprp}}}_{E}(\mathcal{A}^\pm ) := | {\mathrm {Pr}}[(\mathcal{A}^\pm )^{E,E^{-1}} \rightarrow 1] - {\mathrm {Pr}}[(\mathcal{A}^\pm )^{{\mathsf {P}},{\mathsf {P}}^{-1}} \rightarrow 1] |, \\&{\mathbf {Adv}}^{{\mathrm {tprp}}}_{\widetilde{E}}(\mathcal{A}) := | {\mathrm {Pr}}[\mathcal{A}^{\widetilde{E}} \rightarrow 1] - {\mathrm {Pr}}[\mathcal{A}^{\widetilde{{\mathsf {P}}}} \rightarrow 1] |, \\&{\mathbf {Adv}}^{{\mathrm {tsprp}}}_{\widetilde{E}}(\mathcal{A}^\pm ) := | {\mathrm {Pr}}[(\mathcal{A}^\pm )^{\widetilde{E},\widetilde{E}^{-1}} \rightarrow 1] - {\mathrm {Pr}}[(\mathcal{A}^\pm )^{\widetilde{{\mathsf {P}}},\widetilde{{\mathsf {P}}}^{-1}} \rightarrow 1] |, \end{aligned}$$

where the first and the third notions are for adversaries with encryption oracle (thus chosen-plaintext queries), and the second and the fourth are for adversaries with encryption and decryption oracles (thus chosen-ciphertext queries).

When the advantage is sufficiently low, E or \(\widetilde{E}\) is said to be secure against the underlying adversary.

2.3 Authenticated Encryption

Let \(\mathcal{K}\), \(\mathcal{M}_{ae}\) and \(\mathcal{N}_{ae}\) be the set of keys, messages and nonce, respectively. Let \(\mathcal{A}_{ae}\) be the set of associated data (AD), which is data not encrypted but authenticated, and it can be empty. For convention, by saying AE we may mean AEAD. If we want to explicitly mean AE with no AD, (i.e. \(\mathcal{A}_{ae}\) is empty) we call it plain AE. Suppose AE.\(\mathcal{E}\) and AE.\(\mathcal{D}\) as an encryption function and a decryption function of AE, respectively. We suppose that AE.\(\mathcal{E}\) and AE.\(\mathcal{D}\) share the key \(K\in \mathcal{K}\) as input. For encryption, the sender inputs a nonce \(N\in \mathcal{N}_{ae}\), an associated data \(A\in \mathcal{A}_{ae}\) and a message \(M\in \mathcal{M}_{ae}\) to AE.\(\mathcal{E}_K\). Then she gets a ciphertext \(C\in \mathcal{M}_{ae}\) and a tag \(T\in \{0,1\}^{\tau }\) as the output, where \(\tau \) is the length of tag. The sender sends the tuple (N, A, C, T), and the receiver inputs them to AE.\(\mathcal{D}_K\) for decryption. AE.\(\mathcal{D}_K\) outputs a message \(M'\) if the verification is success, otherwise outputs \(\bot \), which means that the verification failed.

The security of AE scheme can be evaluated by two criteria: privacy and authenticity. Following the existing work [11, 38, 39], we use the term privacy to mean confidentiality. For privacy, we define the privacy advantage as the probability that the adversary successfully distinguishes the encryption function of AE from the random-bit oracle, \( \$(*,*,*) \), which returns random bits of length \(|M|+|T|\) for any query (N, A, M): \({\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {AE}}}(\mathcal{A}) := | {\mathrm {Pr}}[\mathcal{A}^{{\mathrm {AE}}.\mathcal{E}} \rightarrow 1] - {\mathrm {Pr}}[\mathcal{A}^{\$} \rightarrow 1] |\). Here, we assume \(\mathcal{A}\) is nonce-respecting, that is, \(\mathcal{A}\) does not repeat nonce N in the encryption queries. For authenticity, we define the authenticity advantage as the probability that the adversary creates a successful forgery by accessing encryption and decryption functions of AE. It is defined as \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {AE}}}(\mathcal{A}) := {\mathrm {Pr}}[ \mathcal{A}^{{\mathrm {AE}}.\mathcal{E}, {\mathrm {AE}}.\mathcal{D}} \mathrm {forges}. ]\), where \(\mathcal{A}^{{\mathrm {AE}}.\mathcal{E}, {\mathrm {AE}}.\mathcal{D}}\) forges if \(\mathcal{A}\) receives \(M'\ne \bot \) from \({\mathrm {AE}}.\mathcal{D}\) by querying \((N',A',C',T')\) while \((N',A',M')\) has never been queried to \({\mathrm {AE}}.\mathcal{E}\). As well as the privacy case, \(\mathcal{A}\) is assumed to be nonce-respecting in its encryption queries, however no restriction on the nonce values in the decryption queries.

2.4 Computation on Galois Field

Let \(\mathbb {F}_{p^n}\) be a finite filed, where characteristic p is prime and extension degree \(n\in \mathbb {N}\). We focus on the case \(n=128\). Following [24, 38], we use the lexicographically-first polynomial for defining the field and thus \(\mathbb {F}_{2^{128}}:=\mathbb {F}_2[x]/(x^{128}+x^7+x^2+x+1)\) and obtain \(\mathbb {F}_{2^{128}}=\langle x\rangle \). We regard an element of \(\mathbb {F}_{2^{128}}\) as a polynomial of x. For \(\forall a \in \{0,1\}^{128}\), we also regard it as a coefficient vector of an element in \(\mathbb {F}_{2^{128}}\). Thus, the primitive root x is interpreted as 2 in the decimal representation. For \(a\in \mathbb {F}_{2^{128}}\), let 2a denote a multiplication by x and a, which is called doubling [38]. In \(\mathbb {F}_{2^{128}}\), \(2a := (a \ll 1)\) if \(\mathtt {msb}_1(a)=0\) and \(2a := (a \ll 1) \oplus (0^{120}10^{4}1^{3})\) if \(\mathtt {msb}_1(a)=1\), where \((a \ll 1)\) is the left-shift of one bit. For \(c\in \mathbb {N}\), we can calculate \(2^ca\) by repeating doubling of a for c-times, and \(3a = 2a \oplus a\).

3 Review of OCB and OTR

3.1 OCB

\({\mathrm {OCB}}\) is a blockcipher mode of operation for AE scheme proposed at [27, 38, 39]. It is parallelizable, and is a rate-1 scheme which needs one blockcipher call to process one message block. It also has provable security based on the pseudorandomness of underlying blockcipher. The security bound of \({\mathrm {OCB}}\) is \(O(\sigma ^2/2^n)\), which is called birthday-bound security, where \(\sigma \) is the number of access to n-bit blockcipher. \({\mathrm {OCB}}\) encrypts a message in a mode similar to ECB, where the blockcipher has input and output masks, and computes the sum of message blocks, called checksum. The authentication tag is an encryption of the checksum. Although \({\mathrm {OCB}}\) was initially proposed as a plain AE [39], it can be converted into AEAD by using PMAC [38] or Phash [27] for AD and taking the XOR of the output and the tag of (plain-AE) OCB. There are three versions for OCB: OCB1 [39], OCB2 [38], OCB3 [27]. Among them, OCB2 has the smallest state size of 3n bits, consisting of n-bit memory for processing of one message block, the value of the mask, and the checksum. As described before, since OCB2 has shown to be insecure by Inoue et al. [23], this paper focuses on the fix suggested by [23] called OCB2f, which has the same 3n-bit state. We simply call it OCB2 or even OCB as the version of OCB that we study, if no confusion is possible. OBC2 can be interpreted as a TBC mode for AE, which we call \(\mathrm {\Theta }\mathrm {CB}\). The TBC used in \(\mathrm {\Theta }\mathrm {CB}\) is a blockcipher mode called \({\mathrm {XEX}}^{*}\).

Let us review the specific (information-theoretic) security bound of OCB2 when it is instantiated with an n-bit URP \({\mathsf {P}}\). Throughout the paper, we use a subscript to denote the underlying component, hence \({\mathrm {OCB}}2_{\mathsf {P}}\) is the target scheme. We write \(\mathrm {\Theta }\mathrm {CB}_{\widetilde{{\mathsf {P}}}}\) to denote \(\mathrm {\Theta }\mathrm {CB}\) using TURP \(\widetilde{{\mathsf {P}}}\). For n-bit tag case, and for the privacy-adversary \(\mathcal{A}\) and the authenticity-adversary \(\mathcal{A}^\pm \), the security bounds of \({\mathrm {OCB}}2_{{\mathsf {P}}}\) (\({\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OCB}}2_{{\mathsf {P}}}}(\mathcal{A})\), \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}}2_{{\mathsf {P}}}}(\mathcal{A}^\pm )\)) are given as follows [23, 30, 38]:

$$\begin{aligned}&{\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OCB}}2_{{\mathsf {P}}}}(\mathcal{A}) \le {\mathbf {Adv}}^{{\mathrm {tprp}}}_{{\mathrm {XEX}}^{*}_{{\mathsf {P}}}}(\mathcal{B}) + {\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {CB}_{\widetilde{{\mathsf {P}}}}}(\mathcal{A}) \le \frac{4.5\sigma ^2_{{\mathrm {priv}}}}{2^n} + 0, \\&{\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}}2_{\mathsf {P}}}(\mathcal{A}^{\pm }) \le {\mathbf {Adv}}^{{\mathrm {tsprp}}}_{{\mathrm {XEX}}^{*}_{{\mathsf {P}}}}(\mathcal{B}^{\pm }) + {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {CB}_{\widetilde{{\mathsf {P}}}}}(\mathcal{A}^{\pm }) \le \frac{4.5\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{q_d}{2^{n}-1}, \end{aligned}$$

where \(\mathcal{B}\) (resp. \(\mathcal{B}^\pm \)) is the adversary performing chosen-plaintext attack (resp. chosen-ciphertext attack), \(\sigma _{{\mathrm {priv}}}\) (resp. \(\sigma _{{\mathrm {auth}}}\)) is the total number of queried blocks in privacy (resp. authenticity) game and \(q_d\) is the number of queries to verification (decryption) oracle. Since OCB3 can be also interpreted as a TBC mode, we can derive similar security bounds to OCB2 as above [27].

3.2 OTR

OTR is an AEAD blockcipher mode of operation proposed by Minematsu [31]. It is a parallelizable, rate-1 scheme. Whereas OCB needs blockcipher decryption for the entire decryption, OTR does not need it for both encryption and decryption, hence it is called inverse-free. As well as OCB, it has provable security based on the pseudorandomness of blockcipher, with security bound of \(O(\sigma ^2/2^n)\), where \(\sigma \) is the number of access to n-bit blockcipherFootnote 2. OTR encrypts a message by using two-round Feistel permutation based on a blockcipher with an input mask, and computes the checksum as a sum of even-numbered message blocks. The authentication tag is an encryption of the checksum. The state size of OTR is 4n bits. It is composed of 2n-bit memory for processing two message blocks (i.e. one Feistel chunk), and each n-bit memory for the value of the mask and the checksum. As well as OCB, OTR can be interpreted as a mode of TBC, which we call \(\mathrm {\Theta }\mathrm {TR}\) (originally \(\mathbb {OTR}\)). The TBC used in \(\mathrm {\Theta }\mathrm {TR}\) is a blockcipher mode called \({\mathrm {XE}}\) [38]. The security bound of \({\mathrm {OTR}}_{\mathsf {P}}\) can be bounded by a hybrid argument similar to \({\mathrm {OCB}}_{\mathsf {P}}\). A tweakable uniform random function (TURF) is denoted by \(\widetilde{{\mathsf {R}}}: \mathcal{T}\times \{0,1\}^n \rightarrow \{0,1\}^n\), where \(\mathcal{T}\) is the same tweak space as \({\mathrm {XE}}\). It is essentially a random function on the whole input domain.

For n-bit tag and for the privacy-adversary \(\mathcal{A}\) and the authenticity-adversary \(\mathcal{A}^\pm \), the security bounds of \({\mathrm {OTR}}_{{\mathsf {P}}}\) (\({\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OTR}}_{{\mathsf {P}}}}(\mathcal{A})\), \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OTR}}_{{\mathsf {P}}}}(\mathcal{A}^\pm )\)) are given as follows:

$$\begin{aligned}&{\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OTR}}_{{\mathsf {P}}}}(\mathcal{A}) \le {\mathbf {Adv}}^{\texttt {cpa}}_{{\mathrm {XE}}_{{\mathsf {P}}}, \widetilde{{\mathsf {R}}}}(\mathcal{B}) + {\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {TR}_{\widetilde{{\mathsf {R}}}}}(\mathcal{A}) \le \frac{6\sigma ^2_{{\mathrm {priv}}}}{2^n} + 0, \\&{\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OTR}}_{\mathsf {P}}}(\mathcal{A}^{\pm }) \le {\mathbf {Adv}}^{\texttt {cpa}}_{{\mathrm {XE}}_{{\mathsf {P}}}, \widetilde{{\mathsf {R}}}}(\mathcal{B}) + {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {TR}_{\widetilde{{\mathsf {R}}}}}(\mathcal{A}^{\pm }) \le \frac{6\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{q_d}{2^{n}}, \end{aligned}$$

where \({\mathbf {Adv}}^{\texttt {cpa}}_{{\mathrm {XE}}_{{\mathsf {P}}}, \widetilde{{\mathsf {R}}}}(\mathcal{B})\) is the probability which the adversary \(\mathcal{B}\) performing chosen-plaintext attack can distinguish \({\mathrm {XE}}_{{\mathsf {P}}}\) from \(\widetilde{{\mathsf {R}}}\). The parameter \(\sigma _{{\mathrm {priv}}}\) (resp. \(\sigma _{{\mathrm {auth}}}\)) is the total number of queried blocks in privacy (resp. authenticity) game and \(q_d\) is the number of queries to the decryption oracle.

4 Our Proposals

4.1 Overview

As we mentioned in Sect. 3, the security bounds of OCB and OTR are evaluated using the hybrid argument: the bound of OCB is a sum of the bound of \({\mathrm {XEX}}^{*}\) and that of \(\mathrm {\Theta }\mathrm {CB}\). Similarly, the bound of OTR is a sum of the bound of \({\mathrm {XE}}\) and that of \(\mathrm {\Theta }\mathrm {TR}\). One can find that \(\mathrm {\Theta }\mathrm {CB}\) and \(\mathrm {\Theta }\mathrm {TR}\) have beyond-birthday-bound security (namely perfect privacy and n-bit authenticity), however the total security of \({\mathrm {OCB}}\) and \({\mathrm {OTR}}\) are n/2 bits because of the birthday bounds of \({\mathrm {XEX}}^{*}\) and \({\mathrm {XE}}\). This gap implies a potential improvement in size, by trading the state size of \(\mathrm {\Theta }\mathrm {CB}\) and \(\mathrm {\Theta }\mathrm {TR}\) for security, while maintaining the overall n/2-bit security of \({\mathrm {OCB}}\) and \({\mathrm {OTR}}\). We found that such a trading-off is indeed possible by reducing the length of checksum by n/2 bits, which we call half-checksum method.

Actually, this gap has been exploited in the literature. For example, Naito’s XKX [34, 35] provides a beyond-birthday-bound secure implementation of TBC and he proposed it to be used within a mode similar to \(\mathrm {\Theta }\mathrm {CB}\) so that the resulting AE has beyond-birthday-bound security.

4.2 OCB-hc

We apply the half-checksum method mentioned in Sect. 4.1 to OCB. The resultant scheme is denoted by \({\mathrm {OCB}\text {-}\mathrm {hc}}\). While we first propose \({\mathrm {OCB}\text {-}\mathrm {hc}}\) as a plain AE with n/2-bit tag length, we will extend it to an AEAD in Sect. 5. In the following, we fix the tag length to be n/2 bits as it is essentially minimum to achieve n/2-bit security. In case a longer tag is required, Sect. 5 will also provide an extension to the case of the arbitrary tag length up to n bits.

Fig. 1.
figure 1

The encryption of \({\mathrm {OCB}\text {-}\mathrm {hc}}_{E_K}\), where \(E_K\) is any n-bit blockcipher. The function \(\texttt {pad}\) denotes the zero padding to n bits.

Full size image

Specification. We show \({\mathrm {OCB}\text {-}\mathrm {hc}}\) in Figs. 1 and 2. As mentioned, the tag is n/2 bits and AD is empty. Let \(E_K\) be an n-bit blockcipher. We define the encryption function of \({\mathrm {OCB}\text {-}\mathrm {hc}}_{E_K}\) as \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{E}_{E_K}: (N, M) \mapsto (C, T)\), where \((N, M) \in \{0,1\}^n \times \{0,1\}^{*}\) and \((C, T)\in \{0,1\}^{*} \times \{0,1\}^{n/2}\). We also define the decryption function as \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{D}_{E_K}: (N, C, T) \mapsto M\) or \(\bot \), where \((N, C, T) \in \{0,1\}^n \times \{0,1\}^{*} \times \{0,1\}^{n/2}\) and \(M \in \{0,1\}^{*}\). The structure of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) is generally the same as \({\mathrm {OCB}}\), except that it computes the n/2-bit checksum of message blocks (say the first n/2 bits; in fact any bits would work fine). This is also different in the last message block M[m], which may be partial. Following \({\mathrm {OCB}}\), we take an XOR of M[m] and the checksum padded to n bits, which is needed for security.

State Size. Since the checksum is halved, it is easy to see that the state size of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) is reduced to 2.5n bits until the last message block. If \(0 < M[m] \le n/2\), the state size remains 2.5n bits since the checksum needs only n/2-bit memory. However if \(n/2 < M[m] \le n\), the state size seemingly increases to at most 3n bits, implying no gain. We can avoid this by only changing the computation procedure described above: we add M[m] (more precisely, \(\mathtt {ozp}(M[m])\)) not to the checksum, but to the mask used in the last block for the tag (See line 10, 11 in Algorithm: \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{E}\) and Algorithm: \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{D}\) in Fig. 2). This will not change the algorithm. Since the mask is consistently n bits, this will not increase the size. Therefore, \({\mathrm {OCB}\text {-}\mathrm {hc}}\) works with 2.5n-bit state for any plaintext.

Fig. 2.
figure 2

The algorithm of \({\mathrm {OCB}\text {-}\mathrm {hc}}\). \(E_K\) is any n-bit blockcipher, and \(D_K\) is the decryption of \(E_K\).

Full size image

4.3 Security of OCB-hc

Fig. 3.
figure 3

The algorithm of \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}\). \(\tilde{E}\) is any TBC which has the same arguments as \({\mathrm {XEX}}^{*}\), and \(\tilde{D}\) is the decryption of \(\tilde{E}\).

Full size image

The security bounds of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) are shown below. We assume the underlying blockcipher is an n-bit URP, \({\mathsf {P}}\). When the underlying blockcipher is a PRP, the security bounds are derived from ours using a standard technique [9], thus we omitted.

Theorem 1

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A}) \le \frac{4.5\sigma ^2_{{\mathrm {priv}}}}{2^n}, \ {\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A}^\pm ) \le \frac{4.5\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{4q_d}{2^{n/2}}, \end{aligned}$$

where \(\mathcal {A}\), \(\mathcal{A}^\pm \) are the adversaries against \({\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}\) and \(\sigma _{{\mathrm {priv}}}\), \(\sigma _{{\mathrm {auth}}}\) and \(q_d\) are the parameters for \(\mathcal{A}\) and \(\mathcal{A}^\pm \). The parameter \(\sigma _{{\mathrm {priv}}}\) (resp. \(\sigma _{{\mathrm {auth}}}\)) is the number of accesses to \({\mathsf {P}}\) in privacy (resp. authenticity) game. The parameter \(q_d\) is the number of queries to the decryption oracle in authenticity game.

Proof

Let \(i\in \mathbb {N}\), \(j\in \{0, 1, 2, 3\}\). We define two TBCs \({\mathrm {XEX}}_{E_K}\) and \({\mathrm {XE}}_{E_K}\) as follows.

$$\begin{aligned}&{\mathrm {XEX}}_{E_K}^{N,i}(M) = E_K(M \oplus 2^iE_K(N)) \oplus 2^iE_K(N), \\&{\mathrm {XE}}_{E_K}^{N,i,j}(M) = E_K(M \oplus 2^i3^jE_K(N)). \end{aligned}$$

Then we combine them to one TBC denoted by \({\mathrm {XEX}}^{*}_{E_K}\). \({{\mathrm {XEX}}^{*}}_{E_K}^{N, b, i, j}(M) = {\mathrm {XEX}}_{E_K}^{N,i}(M)\) if \(b=1\), \({{\mathrm {XEX}}^{*}}_{E_K}^{N, b, i, j}(M) = {\mathrm {XE}}_{E_K}^{N,i,j}(M)\) if \(b=0\). We also define \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{E}}\) as a TBC mode for plain AE in Fig. 3 for the security proof of \({\mathrm {OCB}\text {-}\mathrm {hc}}\). When \(\widetilde{E}\) is \({\mathrm {XEX}}^{*}_E\), \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{E}}\) is equivalent to \({\mathrm {OCB}\text {-}\mathrm {hc}}_E\). Let \(\widetilde{{\mathsf {P}}}\) denote a TURP which has the same arguments as \({\mathrm {XEX}}^{*}\). We define \({\mathbf {Adv}}^{\text {cpa-nr}}_{F, G}(\mathcal {A})\) (resp. \({\mathbf {Adv}}^{\text {cca-nr}}_{F, G}(\mathcal {A})\)) as the probability that the chosen-plaintext attack (resp. chosen-ciphertext attack) adversary \(\mathcal{A}\), who is nonce-respecting in encryption queries, can distinguish F from G. Then we obtain

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A})&\le {\mathbf {Adv}}^{\text {cpa-nr}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}, \mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal {A}) + {\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal {A})\nonumber \\&= {\mathbf {Adv}}^{\text {tprp}}_{{\mathrm {XEX}}^{*}_{{\mathsf {P}}}}(\mathcal {B}) + {\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal {A})\nonumber \\&\le \frac{4.5\sigma ^2_{{\mathrm {priv}}}}{2^n} + 0 \ \ \text {and} \end{aligned}$$
(1)
$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A}^\pm )&\le {\mathbf {Adv}}^{\text {cca-nr}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}, \mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal {A}^\pm ) + {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal {A}^\pm )\nonumber \\&= {\mathbf {Adv}}^{\text {tsprp}}_{{\mathrm {XEX}}^{*}_{{\mathsf {P}}}}(\mathcal {B}^\pm ) + {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal {A}^\pm )\nonumber \\&\le \frac{4.5\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{4q_d}{2^{n/2}}, \end{aligned}$$
(2)

where \(\mathcal{B}\) (resp. \(\mathcal{B}^\pm \)) is the adversary which can simulate \(\mathcal{A}\) (resp. \(\mathcal{A}^\pm \)). The first terms of (1), (2) are derived from [38] and [33]. The derivations of the second terms of (1), (2) are described below.

Privacy. Every TURP invoked in the privacy game has the different tweak since the adversary is nonce-respecting. Thus, we have \({\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal{A}) = 0\).

Authenticity.

Lemma 1

The authenticity advantage of \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}\) is

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal{A}^\pm ) \le \frac{4q_d}{2^{n/2}}, \end{aligned}$$

where \(q_d\) denotes the number of verification (decryption) queries.

Proof

We start with the case \(q_d=1\). Without loss of generality, the adversary performs the decryption query after all encryption queries. Suppose that she obtains the transcript \(z = \{ (N_1, M_1, C_1, T_1), \ldots , (N_q, M_q, C_q, T_q) \}\) in encryption query, and she queries \((N', C', T')\) in decryption query. Let Z be the set of all transcripts, and \(T^{*}\) be the valid tag for \((N', C')\). We define the function \(\mathrm {ifPad}: \{0, 1\}^{*} \rightarrow \{0, 1\}\) as follows.

$$\begin{aligned} \mathrm {ifPad}(M) = {\left\{ \begin{array}{ll} 0 &{} \text { if } |M| = 0 \bmod n; \\ 1 &{} \text {otherwise.} \end{array}\right. } \end{aligned}$$

Then we obtain the following equations.

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}}(\mathcal{A}^\pm )&= \Pr [T'=T^{*}]\\&=\sum _{z}\Pr [T'=T^{*}, Z=z]\\&=\sum _{z}\Pr [T'=T^{*} \mid Z=z]\Pr [Z=z]. \end{aligned}$$

We define FP\(_z:=\Pr [T'=T^{*} \mid Z=z]\) and evaluate \(\max _z\) FP\(_z\) as below.

  1. 1.

    Let \(N' \ne N_i\) for \(1 \le \forall i \le q\). Since the TURP which returns valid \(T^{*}\) takes a new tweak, the adversary has no information about \(T^{*}\). Thus FP\(_{z} \le 1/2^{n/2}\) holds.

  2. 2.

    Let \(N' = N_{\alpha }\), \(\alpha \in \{1, 2, \ldots , q\}\), \(C' \ne C_{\alpha }\). We divide the cases with the value of \(|C'|\) as follows.

    1. (a)

      Let \(|C'|_n \ne |C_{\alpha }|_n\). The tweak of the TURP which outputs \(T^{*}\) is different from that of TURPs which are invoked in encryption query. Thus FP\(_{z} \le 1/2^{n/2}\) holds.

    2. (b)

      Let \(|C'|_n = |C_{\alpha }|_n\) and \(\mathrm {ifPad}(C')\ne \mathrm {ifPad}(C_{\alpha })\). Suppose that \({\mathtt {Checksum}}^{*}\) and \(M^{*}\) are the valid checksum and message for \((N', C')\), respectively, and \({\mathtt {Checksum}}_{\alpha }\) is the value of the checksum for \((N_{\alpha }, M_{\alpha }, C_{\alpha }, T_{\alpha })\). The adversary can make \({\mathtt {Checksum}}^{*}\) equal to \({\mathtt {Checksum}}_{\alpha }\) by using padding. When \({\mathtt {Checksum}}^{*}\ne {\mathtt {Checksum}}_{\alpha }\), FP\(_{z} \le 2^{n/2}/(2^{n}-1)\) holds. When \({\mathtt {Checksum}}^{*}={\mathtt {Checksum}}_{\alpha }\), FP\(_{z} \le 1/(2^{n/2})\) holds since \(\mathrm {ifPad}(C')\ne \mathrm {ifPad}(C_{\alpha })\) and the adversary obtains no information about \(T^{*}\) from \(T_{\alpha }\).

    3. (c)

      Let \(|C'|_n = |C_{\alpha }|_n\) and \(\mathrm {ifPad}(C')=\mathrm {ifPad}(C_{\alpha })\). Suppose \(|C'|_n = |C_{\alpha }|_n=m\). We consider the following cases.

      • Case \(e_1\):    When \(C' \ne C_{\alpha }\), \({\mathtt {Checksum}}^{*} = {\mathtt {Checksum}}_{\alpha }\) holds.

      • Case \(e_2\):   When \(C' \ne C_{\alpha }\), \(T'=T^{*}\) holds.

      We first evaluate \(\Pr [e_1 \mid Z=z]=\Pr [{\mathtt {Checksum}}^{*} = {\mathtt {Checksum}}_{\alpha } \mid Z=z]\). When \(C'[m]\ne C_{\alpha }[m]\) and \(C'[i]=C_{\alpha }[i]\) for \(\forall i\in \{1,\ldots , m-1\}\), we obtain \(\Pr [e_1 \mid Z=z]=0\) since \(\mathtt {ozp}(M^{*}[m])\ne \mathtt {ozp}(M_{\alpha }[m])\) holds. Then suppose \(C'[u] \ne C_{\alpha }[u]\) for \(\exists u \{1, \ldots , m-1\}\). We obtain following evaluation.

      $$\begin{aligned}&\Pr [e_1 \mid Z=z] \\&= \Pr \left[ \left( \mathtt {msb}_{n/2}(M^{*}[u])\,\Vert \,0^{n/2} \right) \oplus \left( \mathtt {msb}_{n/2}(M_{\alpha }[u])\,\Vert \,0^{n/2} \right) = \delta \mid Z=z\right] \\&\le \frac{2^{n/2}}{2^n-1}, \end{aligned}$$

      where \(\delta \) \(=\) \(\left( \mathtt {msb}_{n/2}(M^{*}[u]) \,\Vert \,0^{n/2} \right) \) \(\oplus \) \(\left( \mathtt {msb}_{n/2}(M_{\alpha }[u])\,\Vert \,0^{n/2} \right) \) \(\oplus \) \({\mathtt {Checksum}}^{*}\) \(\oplus \) \({\mathtt {Checksum}}_{\alpha }\). Thus, \(\Pr [e_1 \mid Z=z] \le 2/2^{n/2}\) is obtained. Then we evaluate \(\Pr [e_2|\bar{e_1}, Z=z]\). In this case, the TURP outputting \(T^{*}\) and the TURP outputting \(T_{\alpha }\) take the same tweak, and \(\mathrm {ifPad}(C')=\mathrm {ifPad}(C_{\alpha })\) holds. However, \({\mathtt {Checksum}}^{*}\ne {\mathtt {Checksum}}_{\alpha }\) holds, and we obtain \(\Pr [e_2|\bar{e_1}, Z=z] \le 2^{n/2}/(2^n-1)\).

      From above, we obtain the following evaluation.

      $$\begin{aligned}&\text {FP}_{z} = {\mathrm {Pr}}[e_2 | Z = z]\\&\le {\mathrm {Pr}}[e_2 \cap \bar{e_1} | Z=z] + {\mathrm {Pr}}[e_1 | Z=z]\\&\le {\mathrm {Pr}}[e_2 | \bar{e_1}, Z=z] + {\mathrm {Pr}}[e_1 | Z=z]\\&\le \frac{2^{n/2}}{2^{n}-1} + \frac{2^{n/2}}{2^{n}-1} \le \frac{4}{2^{n/2}}. \end{aligned}$$

From the evaluations of the above cases, we obtain

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}}(\mathcal{A}^\pm ) \le \sum _{z} \max _z\text {FP}_z \cdot {\mathrm {Pr}}[Z=z] \le \frac{4}{2^{n/2}}. \\ \end{aligned}$$

For the case \(q_d>1\), we apply the generic conversion from \(q_d=1\) to \(q_d>1\) as shown by [10], which multiplies \(q_d\) to the above. This concludes the proof.

4.4 OTR-hc

We propose another plain AE scheme denoted by \({\mathrm {OTR}\text {-}\mathrm {hc}}\) which is obtained by applying half-checksum method to OTR. As well as \({\mathrm {OCB}\text {-}\mathrm {hc}}\), we first propose \({\mathrm {OTR}\text {-}\mathrm {hc}}\) as a plain AE with n/2-bit tag. The extension to AEAD with possibly longer tag is possible with a method applied to OCB-hc (See Sect. 5).

Specification. We show \({\mathrm {OTR}\text {-}\mathrm {hc}}\) in Figs. 4 and 5. Let \(E_K\) be an n-bit blockcipher. We define the encryption function of \({\mathrm {OTR}\text {-}\mathrm {hc}}_{E_K}\) as \({\mathrm {OTR}\text {-}\mathrm {hc}}.\mathcal{E}_{E_K}: (N, M) \mapsto (C, T)\), where \((N, M) \in \{0,1\}^n \times \{0,1\}^{*}\) and \((C, T)\in \{0,1\}^{*} \times \{0,1\}^{n/2}\). We also define the decryption function as \({\mathrm {OTR}\text {-}\mathrm {hc}}.\mathcal{D}_{E_K}: (N, C, T) \mapsto M\) or \(\bot \), where \((N, C, T) \in \{0,1\}^n \times \{0,1\}^{*} \times \{0,1\}^{n/2}\) and \(M \in \{0,1\}^{*}\). \({\mathrm {OTR}\text {-}\mathrm {hc}}\) encrypts message with 2-round Feistel based on \({\mathrm {XE}}\). An input to 2n-bit Feistel permutation is called a chunk. The checksum is computed by XORing the most significant n/2 bits of the right halves of the chunk (\(\textit{i}.\textit{e}.\) the even-numbered message blocks) except the last chunk. When the number of message blocks, m, is odd, we take an XOR of M[m] and the padded checksum. When m is even, we will take an XOR of \(\mathtt {msb}_{n/2}(\mathcal{Z})\) and the checksum in the last chunk so that any small difference in \(C[m-1]\) or C[m] (typically between the encryption and decryption queries sharing the nonce) will yield the n-bit difference of \(\mathcal{Z}\).

Fig. 4.
figure 4

The encryption of \({\mathrm {OTR}\text {-}\mathrm {hc}}_{E_K}\), where \(E_K\) is any n-bit blockcipher and \(\varDelta = E_K(N)\). When the number of input blocks m is an odd number, \({\mathtt {Checksum}}= ( \varSigma \,\Vert \,0^{n/2} ) \oplus \mathtt {ozp}(M[m])\), where \(\varSigma = \bigoplus _{i=1}^{(m-1)/2}\mathtt {msb}_{n/2}(M[2i])\). Otherwise, \({\mathtt {Checksum}}= \left( \bigoplus _{i=1}^{(m-2)/2}\mathtt {msb}_{n/2}(M[2i]) \oplus \mathtt {msb}_{n/2}(\mathcal{Z}) \right) \,\Vert \,0^{n/2}\).

Full size image

State Size. When m is odd, \({\mathrm {OTR}\text {-}\mathrm {hc}}\) has 3.5n-bit state size following the procedure described above because the last chunk has only one block. When m is even, it also has 3.5n-bit state size since the checksum can be computed in n/2 bits. Thus, the state size of \({\mathrm {OTR}\text {-}\mathrm {hc}}\) is 3.5n bits. Unlike \({\mathrm {OCB}\text {-}\mathrm {hc}}\), we do not have to derive an alternative procedure for the last chunk.

Fig. 5.
figure 5

The algorithm of \({\mathrm {OTR}\text {-}\mathrm {hc}}\). \(E_K\) is any n-bit blockcipher.

Full size image

4.5 Security of OTR-hc

We here show the security bounds of \({\mathrm {OTR}\text {-}\mathrm {hc}}\). As in the security proof of \({\mathrm {OCB}\text {-}\mathrm {hc}}\), we assume the underlying blockcipher is an n-bit URP, \({\mathsf {P}}\) and omit the case when the underlying blockcipher is a PRP.

Theorem 2

The security bounds of \({\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}\) are evaluated as follows:

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A}) \le \frac{5\sigma ^2_{{\mathrm {priv}}}}{2^n}, \ {\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A}^\pm ) \le \frac{5\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{2.5q_d}{2^{n/2}}, \end{aligned}$$

where \(\mathcal {A}\), \(\mathcal{A}^\pm \) are the adversaries against \({\mathrm {OTR}\text {-}\mathrm {hc}}\) and \(\sigma _{{\mathrm {priv}}}\), \(\sigma _{{\mathrm {auth}}}\), \(q_d\) are the parameters for \(\mathcal{A}\), \(\mathcal{A}^\pm \). The parameter \(\sigma _{{\mathrm {priv}}}\) (resp. \(\sigma _{{\mathrm {auth}}}\)) is the number of accesses to \({\mathsf {P}}\) in privacy game (resp. authenticity game) and \(q_d\) is the number of queries to the decryption oracle in authenticity game.

Fig. 6.
figure 6

The algorithm of \(\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}\). \(\widetilde{E}\) is any TBC which has the same arguments as \({\mathrm {XE}}\).

Full size image

Proof

To evaluate the security bound of \({\mathrm {OTR}\text {-}\mathrm {hc}}\), we define the TBC mode for plain AE, which is denoted by \(\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{E}}\) in Fig. 6. When \(\widetilde{E}\) is \({\mathrm {XE}}_E\), \(\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{E}}\) is equivalent to \({\mathrm {OTR}\text {-}\mathrm {hc}}_E\). Let \(\widetilde{{\mathsf {R}}}\) denote a TURF which has the same arguments as \({\mathrm {XE}}\). For privacy-adversary \(\mathcal{A}\) and authenticity-adversary \(\mathcal{A}^\pm \), we obtain following security bounds of \({\mathrm {OTR}\text {-}\mathrm {hc}}_{{\mathsf {P}}}\).

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A})&\le {\mathbf {Adv}}^{\text {cpa-nr}}_{{\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}, \mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal {A}) + {\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal {A})\nonumber \\&= {\mathbf {Adv}}^{\text {cpa-nr}}_{{\mathrm {XE}}_{{\mathsf {P}}}, \widetilde{{\mathsf {R}}}}(\mathcal {B}) + {\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal {A})\nonumber \\&\le \frac{5\sigma ^2_{{\mathrm {priv}}}}{2^n} + 0 \ \ \text {and} \end{aligned}$$
(3)
$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal {A}^\pm )&\le {\mathbf {Adv}}^{\text {cca-nr}}_{{\mathrm {OTR}\text {-}\mathrm {hc}}_{\mathsf {P}}, \mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal {A}^\pm ) + {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal {A}^\pm )\nonumber \\&= {\mathbf {Adv}}^{\text {cpa-nr}}_{{\mathrm {XE}}_{{\mathsf {P}}}, \widetilde{{\mathsf {R}}}}(\mathcal {B}^\pm ) + {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal {A}^\pm )\nonumber \\&\le \frac{5\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{2.5q_d}{2^{n/2}}, \end{aligned}$$
(4)

where \(\mathcal{B}\) (resp. \(\mathcal{B}^\pm \)) is the adversary which can simulate \(\mathcal{A}\) (resp. \(\mathcal{A}^\pm \)). The first terms of (3), (4) are derived from [31]. The second terms of (3), (4) are described below.

Privacy. As in the case of \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}\), every TURF invoked in the privacy game has a different tweak because the adversary is nonce-respecting. Therefore, we have \({\mathbf {Adv}}^{{\mathrm {priv}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal{A}) = 0\).

Authenticity.

Lemma 2

The authenticity advantage of \(\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}\) is

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {R}}}}}(\mathcal{A}^\pm ) \le \frac{2.5q_d}{2^{n/2}}, \end{aligned}$$

where \(q_d\) denotes the number of decryption queries.

Proof

We start with the case \(q_d=1\). Without loss of generality, we assume that the adversary performs decryption query after all encryption queries. As in the security proof of \({\mathrm {OCB}\text {-}\mathrm {hc}}\), suppose that she obtains the transcript \(z = \{ (N_1, M_1, C_1, T_1), \ldots , (N_q, M_q, C_q, T_q) \}\) in encryption query, and then she queries \((N', C', T')\) in decryption query. Let Z be the set of all transcripts, and \(T^{*}\) be the valid tag for \((N', C')\). We define FP\(_z:=\Pr [T'=T^{*} \mid Z=z]\) and evaluate \(\max _z\) FP\(_z\) as below.

  1. 1.

    Let \(N' \ne N_i\), \(1 \le \forall i \le q\). Since the TURF which returns valid \(T^{*}\) takes a new tweak, the adversary has no information about \(T^{*}\). Thus FP\(_{z} \le 1/2^{n/2}\) holds.

  2. 2.

    Let \(N' = N_{\alpha }\), \(\alpha \in \{1, 2, \ldots , q\}\), \(C' \ne C_{\alpha }\). We divide the cases with the value of \(|C'|\) as follows.

    1. (a)

      Let \(|C'|_{2n} \ne |C_{\alpha }|_{2n}\). The tweak of TURF which outputs \(T^{*}\) is different from that of TURFs which are invoked in encryption query. Thus FP\(_{z} \le 1/2^{n/2}\) holds.

    2. (b)

      Let \(|C'|_{2n} = |C_{\alpha }|_{2n}\) and \(|C'|_n \ne |C_{\alpha }|_n\). As above, the tweak of TURF which outputs \(T^{*}\) is different from that of TURFs which are invoked in encryption query. Thus FP\(_{z} \le 1/2^{n/2}\) holds.

    3. (c)

      Let \(|C'|_n = |C_{\alpha }|_n\) and \(\mathrm {ifPad}(C')\ne \mathrm {ifPad}(C_{\alpha })\). Let \(|C'|_n = |C_{\alpha }|_n = m\). We first consider the case that m is odd. Suppose that \({\mathtt {Checksum}}^{*}\) and \(M^{*}\) are the valid checksum and message for \((N', C')\), respectively, and \({\mathtt {Checksum}}_{\alpha }\) is the value of the checksum for \((N_{\alpha }, M_{\alpha }, C_{\alpha }, T_{\alpha })\). The adversary can make \({\mathtt {Checksum}}^{*}\) equal to \({\mathtt {Checksum}}_{\alpha }\) by using padding. However, we obtain FP\(_{z} \le 1/2^{n/2}\) no matter if \({\mathtt {Checksum}}^{*}\ne {\mathtt {Checksum}}_{\alpha }\) holds or not since \(\mathrm {ifPad}(C')\ne \mathrm {ifPad}(C_{\alpha })\) and the adversary obtains no information about \(T^{*}\) from \(T_{\alpha }\). Regarding to the case that m is even, we can discuss in the same way as above.

    4. (d)

      Let \(|C'|_n = |C_{\alpha }|_n\) and \(\mathrm {ifPad}(C')=\mathrm {ifPad}(C_{\alpha })\). Suppose \(|C'|_n = |C_{\alpha }|_n = m\) and \(CC[1] \,\Vert \,CC[2] \,\Vert \,\cdots \,\Vert \,CC[\ell ] \xleftarrow {2n} C\). We consider the following cases.

      • Case \(e_1\):   When \(CC'[i] \ne CC_{\alpha }[i]\) for \(\exists i\in \{1, \ldots , \ell \}\), \(M^{*}[2i-1]=M_{\alpha }[2i-1]\) holds.

      • Case \(e_2\):   When \(C' \ne C_{\alpha }\), \({\mathtt {Checksum}}^{*} = {\mathtt {Checksum}}_{\alpha }\) holds.

      • Case \(e_3\):   When \(C' \ne C_{\alpha }\), \(T'=T^{*}\) holds.

      We first evaluate \(\Pr [e_1 \mid Z=z]=\Pr [M^{*}[2i-1] = M_{\alpha }[2i-1] \mid Z=z]\). Let \(i\in \{1,\ldots , \ell -1\}\). When \(C'[2i-1] = C_{\alpha }[2i-1]\), \(C'[2i]\ne C_{\alpha }[2i]\) has to hold. Thus we obtain \(\Pr [e_1 \mid Z=z]=0\) since \(\widetilde{{\mathsf {R}}}^{N,i-1,1}(C'[2i-1]) \oplus C'[2i] \ne \widetilde{{\mathsf {R}}}^{N,i-1,1}(C_{\alpha }[2i-1]) \oplus C_{\alpha }[2i]\) always holds. Then let \(C'[2i-1] \ne C_{\alpha }[2i-1]\). \(\Pr [e_1 \mid Z=z] \le 1/2^n\) holds because \(\widetilde{{\mathsf {R}}}^{N,i-1,1}(C'[2i-1])\) is unpredictable for the adversary. When \(i = \ell \) and m is even, \(\Pr [e_1 \mid Z=z] \le 1/2^n\) holds from the almost same discussion as above. When \(i = \ell \) and m is odd, \(\Pr [e_1 \mid Z=z]=0\) holds.

      Secondly, we evaluate \({\mathrm {Pr}}[e_2 \mid \bar{e_1}, Z=z]\). Let m is odd. When \(C'[m] \ne C_{\alpha }[m]\) and \(CC'[i]=CC_{\alpha }[i]\) for \(\forall i\in \{1,\ldots , \ell -1\}\), we obtain \({\mathrm {Pr}}[e_2 \mid \bar{e_1}, Z=z]=0\) since \(\mathtt {ozp}(M^{*}[m])\ne \mathtt {ozp}(M_{\alpha }[m])\) holds. Then, suppose \(CC'[u]\ne CC_{\alpha }[u]\) for \(\exists u\in \{1,\ldots , \ell -1\}\). We obtain the following evaluation.

      $$\begin{aligned}&{\mathrm {Pr}}[e_2 \mid \bar{e_1}, Z=z]\\&= \Pr [ \mathtt {msb}_{n/2}(M^{*}[2u]) \,\Vert \,0^{n/2} \oplus \mathtt {msb}_{n/2}(M_{\alpha }[2u]) \,\Vert \,0^{n/2} = \delta \ \mid \bar{e_1}, Z=z], \end{aligned}$$

      where \(\delta = \mathtt {msb}_{n/2}(M^{*}[2u]) \,\Vert \,0^{n/2} \oplus \mathtt {msb}_{n/2}(M_{\alpha }[2u]) \,\Vert \,0^{n/2} \oplus {\mathtt {Checksum}}^{*} \oplus {\mathtt {Checksum}}_{\alpha }, \)

      $$\begin{aligned}&= \Pr [ \mathtt {msb}_{n/2}(\widetilde{{\mathsf {R}}}^{N,u-1,0}(M^{*}[2u-1]) \oplus C'[2u-1])\,\Vert \,0^{n/2} \\&\ \ \ \ \oplus \mathtt {msb}_{n/2}(\widetilde{{\mathsf {R}}}^{N,u-1,0}(M_{\alpha }[2u-1]) \oplus C_{\alpha }[2u-1])\,\Vert \,0^{n/2} = \delta \mid \bar{e_1}, Z=z]\\&\le 1/2^{n/2}. \end{aligned}$$

      The last line is derived since \(\bar{e_1}\) and \(\widetilde{{\mathsf {R}}}^{N,u-1,0}(M^{*}[2u-1])\) is unpredictable. Thus, we obtain \({\mathrm {Pr}}[e_2 \mid \bar{e_1}, Z=z] \le 1/2^{n/2}\) when m is odd. When m is even, \({\mathrm {Pr}}[e_2 \mid \bar{e_1}, Z=z] \le 1/2^{n/2}\) also holds from the almost same discussion as above. Then we evaluate \(\Pr [e_3 \mid \bar{e_2}, \bar{e_1}, Z=z]\). In this case, the TURF outputting \(T^{*}\) and the TURF outputting \(T_{\alpha }\) take the same tweak, and \(\mathrm {ifPad}(C')=\mathrm {ifPad}(C_{\alpha })\) holds. However \({\mathtt {Checksum}}^{*}\ne {\mathtt {Checksum}}_{\alpha }\) holds, and we obtain \(\Pr [e_3 \mid \bar{e_2}, \bar{e_1}, Z=z] \le 1/2^{n/2}\).

      From above, we obtain the following evaluation.

      $$\begin{aligned} \text {FP}_{z}&= {\mathrm {Pr}}[e_3 \mid Z = z]\\&\le {\mathrm {Pr}}[e_3 \cap (\overline{ e_1 \cup e_2}) \mid Z=z] + {\mathrm {Pr}}[e_2 \cap \bar{e_1} \mid Z=z] + {\mathrm {Pr}}[e_1 \mid Z=z]\\&\le {\mathrm {Pr}}[e_3 \mid \bar{e_2}, \bar{e_1}, Z=z] + {\mathrm {Pr}}[e_2 \mid \bar{e_1}, Z=z] + {\mathrm {Pr}}[e_1 \mid Z=z]\\&\le \frac{1}{2^{n/2}} + \frac{1}{2^{n/2}} + \frac{1}{2^{n}} \le \frac{2.5}{2^{n/2}} \end{aligned}$$

From the evaluations of above cases, we obtain

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {auth}}}_{\mathrm {\Theta }\mathrm {TR}\text {-}\mathrm {hc}}(\mathcal{A}^\pm ) \le \sum _{z} \max _z\text {FP}_z \cdot {\mathrm {Pr}}[Z=z] \le \frac{2.5}{2^{n/2}}. \end{aligned}$$

For the case \(q_d>1\), we use [10] again. This completes the proof.

5 Extensions

In this section, we show extensions of our proposals. First, we show how to extend the tag length of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) to up to n bits. Second, we propose an extension of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) to AEAD, denoted by \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\), which is the mode of operation for AEAD with 2.5n-bit state size. \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) is a combination of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and a variant of Phash [27] with half-checksum method. \({\mathrm {OTR}\text {-}\mathrm {hc}}\) can be extended to have arbitrary tag length up to n bits and AEAD in the same manner as \({\mathrm {OCB}\text {-}\mathrm {hc}}\), which we omit here.

5.1 Arbitrary Tag Length

When tag length \(\tau \) is less than n/2 bits, we can change line 12 and 13 of \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{E}\) in Fig. 2 as follows.

$$\begin{aligned}&\text {line 12} :\ {\mathbf {if}} \ |M[m]|=n \ {\mathbf {then}} \ T \leftarrow \mathtt {msb}_{\tau }({\mathrm {Tag}}), \\&\text {line 13} :\ {\mathbf {else}}\ T \leftarrow \mathtt {lsb}_{\tau }({\mathrm {Tag}}). \end{aligned}$$

For decryption, we can change \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{D}\) accordingly. When \(\tau > n/2\), we can change line 8 and 12–14 of \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{E}\) in Fig. 2 as follows.

$$\begin{aligned}&\text {line 8} :\ {\mathbf {if}} \ |M[m]|=n \ \mathbf {{then}} \ \varDelta \leftarrow 3\varDelta , {\mathbf {else}}\ \varDelta \leftarrow 3^2\varDelta , \\&\text {line 12--14} :\ {\mathbf {return}} (C[1] \,\Vert \,\cdots \,\Vert \,C[m], \mathtt {msb}_{\tau }({\mathrm {Tag}})). \end{aligned}$$

For decryption, we can change \({\mathrm {OCB}\text {-}\mathrm {hc}}.\mathcal{D}\) accordingly. Thus, we have to use the different masks in the encryption of the checksum, depending on whether the message is full n bits or partial, which is the same as the original OCB and OTR.

5.2 OCB-hc with AD

Our extension of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) to AEAD, denoted by \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\), is shown in Fig. 7. \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) consists of the plain-AE core \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) and the authentication core \({\mathrm {Phash}\text {-}\mathrm {hc}}\) (Fig. 8 in Appendix A). The way of combination is similar to \(\mathrm {\Theta }\mathrm {CB}3^{\dagger }\) proposed by Naito [34]. In \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\), \({\mathrm {Phash}\text {-}\mathrm {hc}}\) processes AD and then \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) processes a message using the output of \({\mathrm {Phash}\text {-}\mathrm {hc}}\) as the initial value of the checksum. Note that the initial value of the checksum was \(0^{n/2}\) in the case of \({\mathrm {OCB}\text {-}\mathrm {hc}}\). This way of combination is suitable when AD is processed first. If the message is processed before AD, one can combine \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) and \({\mathrm {Phash}\text {-}\mathrm {hc}}\) by XORing the tag of plain-AE \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) and the output of \({\mathrm {Phash}\text {-}\mathrm {hc}}\). This combination is similar to \({\mathrm {OCB}}3\) or AEM [27, 38].

Specification. We show \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) in Fig. 7. For simplicity, the tag is n/2 bits. Let \(E_K\) be an n-bit blockcipher. We define the encryption function of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}_{E_K}\) as \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}.\mathcal{E}_{E_K}: (N, A, M) \mapsto (C, T)\), where \((N, A, M) \in \{0,1\}^{\le n-1} \times \{0,1\}^{*} \times \{0,1\}^{*}\) and \((C, T)\in \{0,1\}^{*} \times \{0,1\}^{n/2}\). We also define the decryption function as \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}.\mathcal{D}_{E_K}: (N, A, C, T) \mapsto M\) or \(\bot \), where \((N, A, C, T) \in \{0,1\}^{\le n-1} \times \{0,1\}^{*} \times \{0,1\}^{*} \times \{0,1\}^{n/2}\) and \(M \in \{0,1\}^{*}\). \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) is the same algorithm as \({\mathrm {OCB}\text {-}\mathrm {hc}}\) except the length of nonce and the initial value of the checksum. We restrict the length of nonce to less than n bits because \({\mathrm {Phash}\text {-}\mathrm {hc}}\) always uses \(0^n\) as a nonce and so \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) cannot use \(0^n\) as a nonce. The initial value of the checksum of \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) is an output of \({\mathrm {Phash}\text {-}\mathrm {hc}}\). \({\mathrm {Phash}\text {-}\mathrm {hc}}\) computes the sum of the most significant n/2 bits of encrypted massage by \({\mathrm {XE}}\).

State Size. \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) has 2.5n-bit state size as \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) and \({\mathrm {OCB}\text {-}\mathrm {hc}}\) are almost the same. \({\mathrm {Phash}\text {-}\mathrm {hc}}\) also has 2.5n-bit state size, which includes n-bit memory for message block and mask, and 0.5n-bit memory for sum of encrypted message. Therefore, the state size of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) is 2.5n bits.

5.3 Security of OCB-hc-AD

We here show the security bounds of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\). For security analysis of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\), we define \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}\) as a TBC mode for AEAD in Fig. 7. We also define \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}'\) and \(\mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}\) as TBC versions of \({\mathrm {OCB}\text {-}\mathrm {hc}}'\) and \({\mathrm {Phash}\text {-}\mathrm {hc}}\), respectively in Fig. 7. When \(\widetilde{E}\) is instantiated by \({\mathrm {XE}}_{E}\), \(\mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}_{\widetilde{E}}\) is equivalent to \({\mathrm {Phash}\text {-}\mathrm {hc}}_{E}\). In this subsection, we first show the security of \(\mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}\). Then we evaluate the security bounds of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) using hybrid argument.

Lemma 3

Let \(\forall A, A' \in \{0,1\}^{*}\) and \(A \ne A'\). Suppose the underlying TBC of \(\mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}\) is a TURP denoted by \(\widetilde{{\mathsf {P}}}\), which has the same arguments as \({\mathrm {XE}}\). \(\mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}\) has a following property.

$$\begin{aligned} \max _{\forall \delta \in \{0,1\}^{n/2}}\Pr \left[ \mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}(A) \oplus \mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}_{\widetilde{{\mathsf {P}}}}(A') = \delta \right] \le \frac{2}{2^{n/2}}. \end{aligned}$$

The proof is described in Appendix A.

Then we show the security bounds of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\). As in the security proofs of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and \({\mathrm {OTR}\text {-}\mathrm {hc}}\), we assume the underlying blockcipher is an n-bit URP denoted by \({\mathsf {P}}\) and omit the case when the underlying blockcipher is a PRP.

Theorem 3

The security bounds of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}_{{\mathsf {P}}}\) are evaluated as follows:

$$\begin{aligned} {\mathbf {Adv}}^{{\mathrm {priv}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}_{\mathsf {P}}}(\mathcal {A}) \le \frac{4.5\sigma ^2_{{\mathrm {priv}}}}{2^n}, \ {\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}_{\mathsf {P}}}(\mathcal {A}^\pm ) \le \frac{4.5\sigma ^2_{{\mathrm {auth}}}}{2^n} + \frac{4q_d}{2^{n/2}}, \end{aligned}$$

where \(\mathcal{A}\), \(\mathcal{A}^{\pm }\) are the adversaries against \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) and \(\sigma _{{\mathrm {priv}}}\), \(\sigma _{{\mathrm {auth}}}\), \(q_d\) are the parameters for \(\mathcal{A}\), \(\mathcal{A}^{\pm }\). The parameter \(\sigma _{{\mathrm {priv}}}\) (resp. \(\sigma _{{\mathrm {auth}}}\)) is the number of accesses to \({\mathsf {P}}\) in privacy game (resp. authenticity game) and \(q_d\) is the number of queries to the decryption oracle in the authenticity game.

We prove Theorem 3 in Appendix B.

Fig. 7.
figure 7

The algorithms of \({\mathrm {OCB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}}\) and \(\mathrm {\Theta }\mathrm {CB}\text {-}\mathrm {hc}\text {-}\mathrm {AD}\). \(E_K\) is any blockcipher and \(D_K\) is the decryption of \(E_K\). \(\widetilde{E}\) is any TBC which has the same arguments as \({\mathrm {XEX}}^{*}\) and \(\tilde{D}\) is the decryption of \(\widetilde{E}\). Note that \(\widetilde{E}\) in Algorithm: \(\mathrm {\mathbb {P}}\mathrm {hash}\text {-}\mathrm {hc}_{\widetilde{E}}(A)\) can also be interpreted as a TBC which has the same arguments as \({\mathrm {XE}}\).

Full size image

6 Discussion on the Security Bounds of Proposals

In the preceding section, we proved \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and \({\mathrm {OTR}\text {-}\mathrm {hc}}\) keep the birthday-bound security as their originals (OCB and OTR). We here compare the security bounds of our proposals when the security parameters (e.g. the number of queries) are less than \(2^{n/2}\).

For privacy-adversary, our proposals and originals have the exactly same security bounds, respectively, thus we focus on the authenticity-adversary.

We first compare the security bound of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) to that of \({\mathrm {OCB}}\). For arbitrary tag length \(\tau \) up to n, the security bound of \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal{A}^{\pm })\) is evaluated to \(4.5\sigma ^{2}_{{\mathrm {auth}}}/2^n + 2^{n-\tau }q_d/(2^n-1) + 2^{n/2}q_d/(2^n-1)\) in the same manner as the proof in Sect. 4.3. The security bound of \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}}_{\mathsf {P}}}(\mathcal{A}^{\pm })\) is evaluated to \(4.5\sigma ^{2}_{{\mathrm {auth}}}/2^n + 2^{n-\tau }q_d/(2^n-1)\). In the case of \(\tau = n/2\), \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and \({\mathrm {OCB}}\) have the same security bounds except the constant factor. Therefore, \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal{A}^{\pm })\) and \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}}_{\mathsf {P}}}(\mathcal{A}^{\pm })\) grow with the same rate except the constant factor when \(0< \sigma _{{\mathrm {auth}}}, q_d < 2^{n/2}\). In the case of \(\tau < n/2\) and \(\sigma _{{\mathrm {auth}}} \approx q_d\), the security bounds of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and \({\mathrm {OCB}}\) are \(O(q_d/2^{\tau })\). Therefore, there is no difference in their bounds except the constant factor when \(0< \sigma _{{\mathrm {auth}}}, q_d < 2^{n/2}\) similarly to the case of \(\tau = n/2\). In the case of \(n/2 < \tau \le n\), the security bound of \({\mathrm {OCB}\text {-}\mathrm {hc}}\) still has the term \(O(q_d/2^{n/2})\), which is not included by that of \({\mathrm {OCB}}\). If we assume \(\sigma _{{\mathrm {auth}}} \approx q_d\) and \(0< \sigma _{{\mathrm {auth}}}, q_d < 2^{n/2}\), we obtain \(O(\sigma ^2/2^{n}) < O(q_d/2^{n/2})\). Therefore, \({\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}}_{\mathsf {P}}}(\mathcal{A}^{\pm }) < {\mathbf {Adv}}^{{\mathrm {auth}}}_{{\mathrm {OCB}\text {-}\mathrm {hc}}_{\mathsf {P}}}(\mathcal{A}^{\pm })\) always holds when \(0< \sigma _{{\mathrm {auth}}} \approx q_d < 2^{n/2}\). It indicates the security bound of \({\mathrm {OCB}}\) is better when \(n/2 < \tau \le n\) and \(0< \sigma _{{\mathrm {auth}}} \approx q_d < 2^{n/2}\). The comparison of \({\mathrm {OTR}\text {-}\mathrm {hc}}\) with \({\mathrm {OTR}}\) will be similar as above, thus we omit the details.

7 Conclusion

In this paper, we have proposed the half-checksum method to reduce the state size of parallel AE mode of operations having birthday-bound security. It maintains the bit security and overall efficiency. We have applied it to two representative parallel AE modes, OCB and OTR, to derive the concrete instantiations, \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and \({\mathrm {OTR}\text {-}\mathrm {hc}}\). They have almost same properties of \({\mathrm {OCB}}\) and \({\mathrm {OTR}}\) (\(\textit{e}.\textit{g}.\) parallelizability, efficiency, bit security, etc) except the reduced state size. When n is block length of the underlying blockcipher, \({\mathrm {OCB}\text {-}\mathrm {hc}}\) has 2.5n-bit state size, and \({\mathrm {OTR}\text {-}\mathrm {hc}}\) has 3.5n-bit state size. To the best of our knowledge, they achieve the smallest state size among the parallel, rate-1 AE modes of birthday security. Our method is applicable to other schemes having a similar structure as OCB or OTR, such as OPP [22]. While \({\mathrm {OCB}\text {-}\mathrm {hc}}\) and \({\mathrm {OTR}\text {-}\mathrm {hc}}\) are plain AE of fixed n/2-bit tag length, we presented the natural extensions of them to AEAD with arbitrary tag length up to n bits, without loss of security and increase of state size. It would be interesting to consider if we can apply the same method to other types of parallel AE, such as parallel online AE including COLM [3], COPA [5, 6] and ELmD [17, 18]. In addition, further study in hardware are required to evaluate actual circuit gain of our proposals. Finally, it would be natural to ask if the state size figures of our proposals are the theoretical minimum for parallel AE mode of birthday-bound security.