Polynomial Intermediate Checksum for Integrity under Releasing Unverified Plaintext and Its Application to COPA

Abstract

COPA, introduced by Andreeva et al., is the first online authenticated encryption (AE) mode with nonce-misuse resistance, and it is covered in COLM, which is one of the final CAESAR portfolios. However, COPA has been proven to be insecure in the releasing unverified plaintext (RUP) setting. This paper mainly focuses on the integrity under RUP (INT-RUP) defect of COPA. Firstly, this paper revisits the INT-RUP security model for adaptive adversaries, investigates the possible factors of INT-RUP insecurity for “Encryption-Mix-Encryption”-type checksum-based AE schemes, and finds that these AE schemes with INT-RUP security vulnerabilities utilize a common poor checksum technique. Then, this paper introduces an improved checksum technique named polynomial intermediate checksum (PIC) for INT-RUP security and emphasizes that PIC is a sufficient condition for guaranteeing INT-RUP security for “Encryption-Mix-Encryption”-type checksum-based AE schemes. PIC is generated by a polynomial sum with full terms of intermediate internal states, which guarantees no information leakage. Moreover, PIC ensures the same level between the plaintext and the ciphertext, which guarantees that the adversary cannot obtain any useful information from the unverified decryption queries. Again, based on PIC, this paper proposes a modified scheme COPA-PIC to fix the INT-RUP defect of COPA. COPA-PIC is proven to be INT-RUP up to the birthday-bound security if the underlying primitive is secure. Finally, this paper discusses the properties of COPA-PIC and makes a comparison for AE modes with distinct checksum techniques. The proposed work is of good practical significance. In an interactive system where two parties communicate, the receiver can effectively determine whether the information received from the sender is valid or not, and thus perform the subsequent operation more effectively.

1. Introduction

1.1. Background

With the increasing demand for lightweight sensors in the development of space–aerial–ground–sea cooperative information networks, and the scalability, timeliness, and security of the network, lightweight cryptography has been deeply explored in academia and industry. To solve the practical application problems, authenticated encryption (AE) has been extended to lightweight AE, which provides both privacy and authenticity on resource-constrained devices. In conventional security models of AE, the decrypted plaintext must be released after integrity is successfully verified. However, in lightweight devices, there are not enough resources to store the whole decrypted plaintext. Moreover, there exist side channel attacks to obtain the properties of the plaintext indirectly. Thus, releasing the decrypted plaintext before verification (releasing unverified plaintext, RUP) is often desirable and can contribute effectively to the improvement of efficiency in lightweight devices [1,2,3,4].

Andreeva et al. introduced stronger security models in the RUP setting [1]. For privacy, they proposed a new notion called PA (Plaintext Awareness). PA, in fact, is a plaintext extractor which tries to deceive adversaries by simulating the decryption oracle. An AE scheme is PA if it is infeasible to distinguish the decryption oracle from the plaintext extractor. For authenticity, they proposed a new notion called INT-RUP (Integrity under Releasing Unverified Plaintext). INT-RUP is a stronger security metric than INT-CTXT (Integrity of Ciphertext). An AE scheme is INT-RUP if an adversary can not generate a fresh valid ciphertext–tag pair given the additional power of access to an unverified decryption oracle, after the encryption oracle. This paper is only interested in INT-RUP security of various AE schemes.

OCB [5,6,7] and COPA [8] are not INT-RUP. Andreeva et al. presented a forgery attack under the INT-RUP security model and left fixing OCB and COPA to be INT-RUP in an efficient way as an open problem [1]. Zhang et al. focused on the weakness of the checksum processing, described a new generalized checksum technique—PCC (Plaintext and Ciphertext Checksum)—and proved that all AE schemes with PCC are insecure under the INT-RUP security model [9]. To fix the weakness of PCC, they provided an intermediate checksum (IC) technique to generate the authentication tag. Based on the IC technique, they proposed a modified OCB scheme with IC, called OCB-IC, to settle the INT-RUP security of OCB [9,10]. Chakraborti et al. focused on the rate (which means the number of message blocks processed per block of cipher invocation) of block-cipher-based AE schemes to find the cause of INT-RUP insecurity [11]. They considered the weakness during the tag processing, showed a generic INT-RUP attack on a “rate-1” block-cipher-based affine AE mode, described an INT-RUP attack on CPFB (rate-3/4), and presented a variant mCPFB (rate-3/4) which supports INT-RUP security. Zhang and Wu focused on the security of online AE schemes in a RUP setting and looked for the reason of the INT-RUP insecurity of the schemes [12]. They found that if the encryption part of AE schemes has a CCJP (Control Ciphertext to Jump between two Plaintexts) property and the input of the authentication part is built by linear combinations of all plaintext blocks (i.e., the authentication tag is generated by the plaintext checksum), it is easy to make an INT-RUP forgery attack. Datta et al. investigated the integrity of the COLM structure in an RUP setting, rewrote a nonce-respecting INT-RUP forgery attack against COPA’s XOR mixing, and presented nonce-respecting and nonce-misusing INT-RUP forgery attacks for any mixing functions [13]. They demonstrated that its security highly depends on the choice of mixing function. Hirose et al. focused on the security of rate-1 AE schemes under RUP [14]. They showed that any rate-1 AE scheme cannot satisfy strong security requirements under RUP and then introduced new strictly weaker security notions of tag-PA and tag-INT by relaxing the security requirements; finally, they presented a new rate-1 AE scheme OCBt which is both tag-PA and tag-INT. They considered the efficiency by rate-1 and full parallelizability and security by robustness against decryption misuse. Chakraborti et al. considered the INT-RUP security of AE schemes under the lightweight application and proposed two lightweight AE modes: LOCUS and LOTUS with higher security and lighter primitives [15]. They utilized the intermediate checksum technique to generate the final authentication tag. In addition to the one-pass AE schemes with INT-RUP security, there exist two-pass AE modes with INT-RUP security. Andreeva et al. considered the INT-RUP security of SIV, HBS, and BTM and proved their INT-RUP security [1]. Chang et al. proposed a lightweight deterministic AE mode ANYDAE and proved that ANYDAE achieves INT-RUP security [16]. Recently, Andreeva et al. focused on the rate-1 online fork AE mode SAEF and showed that SAEF is INT-RUP secure up to the birthday bound by the H-coefficient technique [17]. Datta et al. considered SAEB and TinyJAMBU and presented their integrity security in the setting of a releasing unverified plaintext model [18].

This paper revisits the possible causes which result in INT-RUP insecurity, investigates almost all of the one-pass checksum-based AE schemes [5,6,7,8,11,13,19,20,21,22,23,24,25,26,27], and finds that these AE schemes with INT-RUP security defects utilize a common checksum technique. This paper focuses on the weakness of the checksum technique and tries to introduce an improved checksum technique to settle the INT-RUP security of COPA.

1.2. Problem Statement

For almost all of the one-pass AE schemes, their checksum is generated by the XOR-sum of all plaintext blocks, which results in INT-RUP insecurity. Andreeva et al. presented a forgery attack with a high probability by making one encryption query and two decryption queries under the INT-RUP security model, and they left fixing COPA to be INT-RUP in an efficient way as an open problem [1].

The IC technique [9,10] is a good technique for settling the INT-RUP security defect of OCB. However, the IC technique cannot be directly applied to COPA. COPA is an authenticated online cipher, which means that the i-block ciphertext just relies on the first i plaintext blocks. In other words, the intermediate checksum in this case only relates to the last ciphertext block. Even if you utilize the encrypted internal states to generate the intermediate checksum, the adversary just needs to keep the last ciphertext block the same to make a successful forgery. In addition, the intermediate parity checksum (IPC) technique [10] was utilized to try to settle the INT-RUP security defect of COPA, but it ultimately failed. The i-block plaintext can be recovered by the $(i-1)$-block ciphertext and the i-block ciphertext, which can be used by adversaries to launch forgery attacks. Therefore, it is necessary to propose a new improved intermediate checksum technique for settling the INT-RUP security defect of COPA.

1.3. Our Contributions

This paper mainly considers the INT-RUP insecurity of COPA and focuses on the weakness of the checksum processing. This paper first revisits the INT-RUP security model which allows for an adaptive adversary to make queries in any order and then introduces a new improved checksum technique: polynomial intermediate checksum (PIC), which is a generalization of IC. In the PIC technique, the intermediate internal states generated by either an encryption or a decryption algorithm are hidden from the adversaries, and PIC is generated by a polynomial sum with full terms of intermediate internal states, which guarantees no information leakage. Moreover, PIC maintains the same level between the plaintext and the ciphertext, which guarantees that the adversary cannot obtain any useful information from the unverified decryption queries. This technique is very effective in solving the INT-RUP security of checksum-based AE schemes. Finally, based on the PIC technique, a modified scheme called COPA-PIC is proposed to fix the INT-RUP security defect of COPA. COPA-PIC retains the main structure and the advantages of COPA.

From the perspective of the design idea, at the beginning, COPA-PIC is designed in terms of tweakable blockciphers (TBCs), as TBC-based AE modes have more advantages than AE modes based on other primitives; particularly, their structure is clear and their proof is simple [19,22,28,29,30,31]. In addition, TBCs can also be constructed by distinct primitives. Therefore, a TBC-based COPA-PIC is first illustrated, and then a blockcipher-based TBC and a permutation-based TBC are utilized to further instantiate COPA-PIC.

From the perspective of the security guarantee, COPA-PIC is proven INT-RUP up to the birthday bound of $n/2$-bit security if the underlying primitive (including TBC, block cipher, and permutation) is secure, where n is the block size of the underlying primitive.

From the perspective of the efficiency, the number of underlying primitive invocations of COPA-PIC is less than that of COPA. To be specific, let a be the number of blocks of the associated data and l be the number of blocks of the plaintext. Then, the encryption, decryption, and verification algorithms of COPA-PIC invoke $a+2l+2$, $a+2l+2$, and $a+l+2$ underlying primitives, respectively, while the encryption, decryption, and verification algorithms of COPA invoke $a+2l+2$ underlying primitives. In other words, the encryption and decryption costs of COPA-PIC are the same as those of COPA, but the verification cost of COPA-PIC is close to half of COPA. In practical scenarios, such as an interactive system where two parties communicate, the receiver can first effectively determine whether the information received from the sender is valid or not, and then perform the decryption operation more effectively to obtain the correct plaintext. Therefore, the efficiency of COPA-PIC is significantly improved in practical applications. The comparison between COPA and COPA-PIC is shown in

Table 1. Comparison between COPA and COPA-PIC for a-block associated data and l-block plaintext, where # Encryption, # Decryption, and # Verification, respectively, stand for the number of invoking underlying primitives in the encryption, decryption, and verification algorithms, and n is the block size.

Schemes	Checksum Technique	# Encryption	# Decryption	# Verification
COPA	PCC	$a+2l+2$	$a+2l+2$	$a+2l+2$
COPA-PIC	PIC	$a+2l+2$	$a+2l+2$	$a+l+2$
Schemes	Security	Security Bound	Rate	Reference
COPA	INT-CTXT	$O\left(2^{n/2}\right)$	1/2	[8]
COPA-PIC	INT-RUP	$O\left(2^{n/2}\right)$	1/2	This paper

.

The proposed work is of high significance to both theoretical investigations and practical applications. This work supports Zhang and Wu’s view that it is easy to make an INT-RUP forgery attack if the encryption part of the AE schemes has a CCJP property and the input of the authentication part is mainly subject to linear combinations of all plaintext blocks [12]. The PIC technique is essentially an improvement of Chakraborti et al.’s technique and covers the IC technique. The PIC technique aims to settle the problem of INT-RUP security for “Encryption-Mix-Encryption”-type checksum-based AE schemes. Moreover, the proposed work also meets the requirements of strong security and high efficiency in lightweight devices in the next-generation network. In particular, it is of good practical significance to establish the rapid feedback mechanism of third-party error authentication.

1.4. Organization of This Paper

Some preliminaries are presented in Section 2. A new polynomial intermediate checksum (PIC) technique is described in Section 3. Section 4 provides a modified scheme COPA-PIC to fix the INT-RUP security defect of COPA and derives its security proof. Finally, this paper concludes with some discussions and a mention of future works in Section 5.

2. Preliminaries

The basic notations and concepts closely follow [9,10]. Some of the important symbols are described in Abbreviations.

• Block ciphers. Block cipher is an important part of symmetric-key ciphers, and its standardized algorithms, such as AES or SM4, have been widely used in practice.

Let $E:\mathcal{K}\times {\{0,1\}}^n\to {\{0,1\}}^n$ be a block cipher, where $\mathcal{K}$ is a key space and n is the block size. For any $K\in \mathcal{K}$, $E_K(·)=E(K,·)$ is an n-bit permutation. Let $\mathcal{A}$ be an adversary with access to the encryption oracle or encryption and decryption oracles; then, the pseudorandom permutation (PRP) and strong pseudorandom permutation (SPRP) advantages of $\mathcal{A}$ against E are, respectively, defined as

$$\begin{array}{cc}\hfill & Ad{v}_E^{prp}\left(\mathcal{A}\right)=|Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{E_K}\Rightarrow 1]-Pr[\pi \stackrel{\$}{\leftarrow }Perm\left(n\right):{\mathcal{A}}^{\pi }\Rightarrow 1]|,\hfill \\ \hfill & Ad{v}_E^{sprp}\left(\mathcal{A}\right)=|Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{E_K^{\pm 1}}\Rightarrow 1]-Pr[\pi \stackrel{\$}{\leftarrow }Perm\left(n\right):{\mathcal{A}}^{{\pi }^{\pm 1}}\Rightarrow 1]|.\hfill \end{array}$$

• Tweakable blockciphers (TBCs). As the generalization of block ciphers, TBCs have been widely used in the fields of disk encryption, length-preserving encryption, storage encryption, etc. Related works about TBCs include [30,32,33,34,35,36,37,38,39].

Let $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\mathcal{K}$ is a key space and $\Gamma$ is a tweak space. For any $K\in \mathcal{K}$, $t\in \Gamma$, ${\tilde{E}}_K^t(·)=\tilde{E}(K,t,·)$ is an n-bit permutation. Let $\mathcal{A}$ be an adversary with access to the tweakable encryption oracle or tweakable encryption and tweakable decryption oracles, then the tweakable PRP (TPRP) and strong TPRP (STPRP) advantages of $\mathcal{A}$ against $\tilde{E}$ are, respectively, defined as

$$\begin{array}{cc}\hfill & Ad{v}_{\tilde{E}}^{\widetilde{prp}}\left(\mathcal{A}\right)=|Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\tilde{E}}_K}\Rightarrow 1]-Pr[\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n):{\mathcal{A}}^{\tilde{\pi }}\Rightarrow 1]|,\hfill \\ \hfill & Ad{v}_{\tilde{E}}^{\widetilde{sprp}}\left(\mathcal{A}\right)=|Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\tilde{E}}_K^{\pm 1}}\Rightarrow 1]-Pr[\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n):{\mathcal{A}}^{{\tilde{\pi }}^{\pm 1}}\Rightarrow 1]|.\hfill \end{array}$$

The above adversary is just allowed to query the encryption oracle in the tweak space $\Gamma$ for TPRP, while it is allowed to query both encryption and decryption oracles in the tweak space $\Gamma$ for STPRP. However, in real life, the encryption part of some cryptographic schemes is allowed to query both encryption and decryption oracles in a subset of tweaks and the authentication part of an associated data is just allowed to query the encryption oracle in another subset of tweaks, such as COPA. Granger et al. introduced a mixed security notion to settle this problem [22]. Consider a partition ${\Gamma }_0\cup {\Gamma }_1=\Gamma$ of the tweak space into encryption-only tweaks ${\Gamma }_0$ and encryption-and-decryption tweaks ${\Gamma }_1$; then, the mixed TPRP (MTPRP) advantage of $\mathcal{A}$ against $\tilde{E}$ is defined as

$$\begin{array}{c}\hfill Ad{v}_{\tilde{E}}^{\widetilde{mprp}}\left(\mathcal{A}\right)=|Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\tilde{E}}_K,{\tilde{E}}_K^{\pm 1}}\Rightarrow 1]-Pr[\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n):{\mathcal{A}}^{\tilde{\pi },{\tilde{\pi }}^{\pm 1}}\Rightarrow 1]|.\end{array}$$

Note that, here, $\mathcal{A}$ is not allowed to query ${\tilde{E}}_K^{-1}$ or ${\tilde{\pi }}^{-1}$ for tweaks from ${\Gamma }_0$. In fact, MTPRP covers TPRP if $({\Gamma }_0,{\Gamma }_1)=(\Gamma ,\varnothing )$ and STPRP if $({\Gamma }_0,{\Gamma }_1)=(\varnothing ,\Gamma )$.

• Construction of TBCs. TBCs can be constructed from primitives that are widely used today, such as block ciphers and permutations. In these constructions, since the tweak is an important component of TBCs, it must be instantiated in advance when implementing with block ciphers and permutations. Moreover, considering the application of TBC in the actual modes of operations, the update of the tweak is as simple as possible. In practice, due to the wide application of nonce-based encryption, authentication, and authenticated encryption modes of operations, using a nonce to instantiate a tweak has become a common technical means. Here, we consider a nonce-based instantiation of a tweak space $\Gamma =\mathcal{N}\times \mathcal{I}\times \mathcal{J}$, where $\mathcal{N}$ is a nonce space, $\mathcal{I}$ is a large-integer set, and $\mathcal{J}$ is a small-integer set, and we give two general methods for constructing TBCs as follows.

Method 1: Let $E:\mathcal{K}\times {\{0,1\}}^n\to {\{0,1\}}^n$ be a block cipher. By the XEX* construction [6], a blockcipher-based TBC $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ is built as follows:

$$\begin{array}{c}\hfill {\tilde{E}}_K^{N,i,j}\left(x\right)=E_K(x\oplus \Delta )and{\tilde{E}}_K^{N,i^{\prime },j^{\prime }}\left(x\right)=E_K(x\oplus {\Delta }^{\prime })\oplus {\Delta }^{\prime },\end{array}$$

where $K\in \mathcal{K},(N,i,j)\in {\Gamma }_0,(N,i^{\prime },j^{\prime })\in {\Gamma }_1,{\Gamma }_0\cap {\Gamma }_1=⌀,{\Gamma }_0\cup {\Gamma }_1\subseteq \Gamma ,\Delta =2^i{3}^{j}L,{\Delta }^{\prime }=2^{i^{\prime }}{3}^{j^{\prime }}L$, and $L=E_K\left(N\right)$.

Method 2: Let $\pi :{\{0,1\}}^n\to {\{0,1\}}^n$ be a public n-bit permutation. By the MEM construction [22], a permutation-based TBC $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ is built as follows:

$$\begin{array}{c}\hfill {\tilde{E}}_K^{N,i,j}\left(x\right)=\pi (x\oplus \Delta )and{\tilde{E}}_K^{N,i^{\prime },j^{\prime }}\left(x\right)=\pi (x\oplus {\Delta }^{\prime })\oplus {\Delta }^{\prime },\end{array}$$

where $K\in \mathcal{K},(N,i,j)\in {\Gamma }_0,(N,i^{\prime },j^{\prime })\in {\Gamma }_1,{\Gamma }_0\cap {\Gamma }_1=⌀,{\Gamma }_0\cup {\Gamma }_1\subseteq \Gamma ,\Delta =2^i{3}^{j}L,{\Delta }^{\prime }=2^{i^{\prime }}{3}^{j^{\prime }}L$, and $L=\pi \left(N\right|\left|K\right)$.

The security of these two general methods for constructing TBCs is shown in the following lemmas.

Lemma 1

(XEX* [6]). Assume that the adversary makes q construction queries to $\tilde{E}$ and ${\tilde{E}}^{-1}$ and $2^i{3}^j\ne 1$ for all $(i,j)\in \mathcal{I}\times \mathcal{J}$. Let $\tilde{E}=XE{X}^{*}[E,2^{\mathcal{I}}{3}^{\mathcal{J}}]$; then,

$$\begin{array}{c}\hfill Ad{v}_{\tilde{E}}^{\widetilde{mprp}}\left(q\right)\le Ad{v}_E^{sprp}\left(2q\right)+9.5q^2/2^n.\end{array}$$

Lemma 2

(MEM [22]). Assume that the adversary makes q construction queries to $\tilde{E}$ and ${\tilde{E}}^{-1}$ and p primitive queries to π and ${\pi }^{-1}$ and $2^i{3}^j\ne 1$ for all $(i,j)\in \mathcal{I}\times \mathcal{J}$. Let $\tilde{E}=MEM[\pi ,2^{\mathcal{I}}{3}^{\mathcal{J}}]$; then,

$$\begin{array}{c}\hfill Ad{v}_{\tilde{E},\pi }^{\widetilde{mprp}}(q,p)\le 4.5q^2/2^n+3qp/2^n+p/2^k.\end{array}$$

• Syntax of AE. In the RUP setting, Andreeva et al. introduced a new syntax for AE modes [1]. They divided the conventional decryption algorithm into a decryption algorithm and a verification algorithm so that the decryption algorithm always releases plaintext and the verification algorithm only performs integrity verification. The new syntax of nonce-based AE schemes $\Pi =(\mathcal{E},\mathcal{D},\mathcal{V})$ consists of an encryption algorithm $\mathcal{E}:\mathcal{K}\times \mathcal{N}\times \mathcal{H}\times \mathcal{M}\to \mathcal{C}\times \mathcal{T}$, a decryption algorithm $\mathcal{D}$: $\mathcal{K}\times \mathcal{N}\times \mathcal{H}\times \mathcal{C}$$\times \mathcal{T}\to \mathcal{M}$, and a verification algorithm $\mathcal{V}:\mathcal{K}\times \mathcal{N}\times \mathcal{H}\times \mathcal{C}\times \mathcal{T}\to \top /\perp$, which is described as follows:

  $$\begin{array}{cc}\hfill & {\mathcal{E}}_K(N,A,M)=(C,T),\hfill \\ \hfill & {\mathcal{D}}_K(N,A,C,T)=M,\hfill \\ \hfill & {\mathcal{V}}_K(N,A,C,T)=\top /\perp ,\hfill \end{array}$$

  where $K\in \mathcal{K},N\in \mathcal{N},A\in \mathcal{H},M\in \mathcal{M},C\in \mathcal{C},T\in \mathcal{T}$, and the symbols ⊤ and ⊥ indicate the success and failure of integrity verification, respectively.
• INT-RUP security model of AE. Let $\Pi =(\mathcal{E},\mathcal{D},\mathcal{V})$ be a nonce-based AE scheme. Let $K\in \mathcal{K}$ and $\mathcal{A}$ be an adversary which makes at most q queries to ${\mathcal{E}}_K(·,·,·)$ and ${\mathcal{D}}_K(·,·,·,·)$, and at most $q_v$ queries to ${\mathcal{V}}_K(·,·,·,·)$. Assume that $\mathcal{A}$ is an adaptive adversary which can perform encryption and decryption oracle queries in any order. In other words, $\mathcal{A}$ can perform the interleaved queries to ${\mathcal{E}}_K(·,·,·)$ and ${\mathcal{D}}_K(·,·,·,·)$. $\mathcal{A}$ forges if at least one forgery attempt in all $q_v$ forgery attempts succeeds. Then, the INT-RUP-advantage of $\mathcal{A}$ against $\Pi =(\mathcal{E},\mathcal{D},\mathcal{V})$ is defined as

  $$\begin{array}{c}\hfill Ad{v}_{\Pi }^{int-rup}\left(\mathcal{A}\right)=Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\mathcal{E}}_K,{\mathcal{D}}_K,{\mathcal{V}}_K}forges].\end{array}$$

Let $Ad{v}_{\Pi }^{int-rup}(t,q,l,\sigma )$ be the INT-RUP-advantage of the adversary $\mathcal{A}$ against the nonce-based AE scheme $\Pi$ under the limited running time t, queries q, block length l, query complexity $\sigma$, and other resources.

3. Polynomial Intermediate Checksum (PIC) Technique

This paper investigates almost all of the “Encryption-Mix-Encryption”-type checksum-based AE schemes with INT-RUP insecurity, focuses on the weakness of their checksum technique, and tries to introduce an improved checksum technique to settle the INT-RUP insecurity of COPA. This section first introduces a polynomial intermediate checksum (PIC) technique for supporting INT-RUP security and then presents the INT-RUP security of “Encryption-Mix-Encryption”-type AE modes with PIC.

3.1. PIC Technique

The checksum technique used in the previous “Encryption-Mix-Encryption”-type AE modes includes the plaintext checksum (PC), the plaintext and ciphertext checksum (PCC), intermediate checksum (IC), and intermediate parity checksum (IPC). However, these checksum techniques do not always guarantee INT-RUP security for “Encryption-Mix-Encryption”-type AE modes. To always guarantee INT-RUP security for “Encryption-Mix-Encryption”-type AE modes, here, we introduce a new polynomial intermediate checksum (PIC) technique, which is a generalization of IC. As the name suggests, PIC is a full-term polynomial XOR-sum of intermediate internal states. The intermediate internal states are generated by encrypting all of the plaintext blocks or decrypting all of the ciphertext blocks, which make them hidden from the adversaries. In other words, PIC guarantees no information leakage.

To always guarantee the INT-RUP security, PIC must satisfy the following two conditions simultaneously:

Condition 1. It is generated by all of the plaintext blocks.

Condition 2. It is generated by all of the ciphertext blocks.

The above two conditions are indispensable. Conditions 1 and 2 show that PIC is constructed by polynomials with full terms and provides the same level for the plaintext and the ciphertext to resist the releasing unverified plaintext attack. What calls for special attention is that PIC must be a polynomial function with full terms of the plaintext blocks, and it must also be a polynomial function with full terms of the ciphertext blocks. Otherwise, leaving the missing term unchanged makes it easy to make a successful forgery. Having the same level between the plaintext and the ciphertext ensures that the adversary cannot obtain any useful information from the unverified decryption queries. In other words, PIC can resist the unverified decryption queries. For “Encryption-Mix-Encryption”-type checksum-based AE schemes, PIC is a sufficient condition for guaranteeing the INT-RUP security.

3.2. INT-RUP Security of “Encryption-Mix-Encryption”-Type AE Modes with PIC

The following mathematical model is utilized to formally describe “Encryption-Mix-Encryption”-type AE modes with PIC.

Let $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\mathcal{K}$ is a key space, $\Gamma =\mathcal{N}\times \mathcal{I}\times \mathcal{J}$ is a tweak space, $\mathcal{N}$ is a nonce space, $\mathcal{I}$ is a large-integer set, and $\mathcal{J}$ is a small-integer set. Let N be a nonce, M be a plaintext, C be a ciphertext, and T be an authentication tag. The overview of “Encryption-Mix-Encryption”-type nonce-based AE modes with PIC is described in Figure 1.

Let $X_1,X_2,\cdots ,X_l$ be the encrypted internal states of the plaintext $M=(M_1,M_2,\cdots$, $M_l)$ and $Y_1,Y_2,\cdots ,Y_l$ be the decrypted internal states of the ciphertext $C=(C_1,C_2,\cdots$, $C_l)$. There exists some invertible mathematical relationship R between $X_1,X_2,\cdots ,X_l$ and $Y_1,Y_2,\cdots ,Y_l$, i.e., $(Y_1,Y_2,\cdots ,Y_l)=R(X_1,X_2,\cdots ,X_l)$ and for each $Y_i$, the following equation holds:

$$\begin{array}{cc}\hfill \begin{array}{c}{Y}_i\end{array}& =\left[\begin{array}{cccc}{A}_{i1}& A_{i2}& \cdots & A_{il}\end{array}\right]\left[\begin{array}{c}{X}_1\\ X_2\\ \cdots \\ X_l\end{array}\right]\oplus \begin{array}{c}{B}_i\end{array}\hfill \\ \hfill & =A_{i1}{X}_1\oplus A_{i2}{X}_2\oplus \cdots \oplus A_{il}{X}_l\oplus B_i\hfill \end{array}$$

where $A_{ii}\ne 0$ for $1\le i\le l$ and $B_i$ for $1\le i\le l$ are arbitrary constants.

Let $PIC=a_0\oplus a_1{X}_1\oplus \cdots \oplus a_l{X}_l=b_0\oplus b_1{Y}_1\oplus b_2{Y}_2\oplus \cdots \oplus b_l{Y}_l$ be a polynomial intermediate checksum, where $a_i,b_i\ne 0$ for $1\le i\le l$ and $a_0,b_0$ are arbitrary constants. Then,

$$\begin{array}{cc}\hfill PIC& =g(Y_1,Y_2,\cdots ,Y_l)=b_0\oplus b_1{Y}_1\oplus b_2{Y}_2\oplus \cdots \oplus b_l{Y}_l\hfill \\ \hfill & =b_0\oplus \sum _{i=1}^l{b}_i{Y}_i\hfill \\ \hfill & =b_0\oplus \sum _{i=1}^l{b}_i(A_{i1}{X}_1\oplus A_{i2}{X}_2\oplus \cdots \oplus A_{il}{X}_l\oplus B_i)\hfill \\ \hfill & =b_0\oplus \sum _{i=1}^l{b}_i{B}_i\oplus \sum _{i=1}^l{b}_i{A}_{i1}{X}_1\oplus \cdots \oplus \sum _{i=1}^l{b}_i{A}_{il}{X}_l\hfill \\ \hfill & =a_0\oplus a_1{X}_1\oplus \cdots \oplus a_l{X}_l=f(X_1,X_2,\cdots ,X_l),\hfill \end{array}$$

where $a_i$ and $b_i$ ($0\le i\le l$) satisfy the following relationship:

$$\begin{array}{c}\hfill \left(I\right)\left\{\begin{array}{ccc}{a}_0=b_0\oplus {\sum }_{j=1}^l{b}_j{B}_j,\hfill & & i=0\hfill \\ a_i=\sum _{j=1}^l{b}_j{A}_{ji},\hfill & & 1\le i\le l\hfill \end{array}\right.\end{array}$$

In particular, if $A_{ij}=0$ for any $j\ne i$, then $Y_i=A_{ii}{X}_i\oplus B_i$, where $1\le i\le l$. It follows that the relationship (I) degenerates to

$$\begin{array}{c}\hfill \left(II\right)\left\{\begin{array}{ccc}{a}_0=b_0\oplus {\sum }_{j=1}^l{b}_j{B}_j,\hfill & & i=0\hfill \\ a_i=b_i{A}_{ii},\hfill & & 1\le i\le l\hfill \end{array}\right.\end{array}$$

OCB-IC [9] is a typical example when $A_{ii}=1$ and $B_i=0$. In this case, $Y_i=X_i$ for $1\le i\le l$ and PIC degrades to IC (i.e., $PIC=f(X_1,X_2,\cdots ,X_l)=g(Y_1,Y_2,\cdots ,Y_l)=X_1\oplus X_2\oplus \cdots \oplus X_l=IC$).

If $A_{ij}=0$ for any $j>i$, then $(Y_1,Y_2,\cdots ,Y_l)=R(X_1,X_2,\cdots ,X_l)$ is an online function (i.e., $Y_i$ just depends on the first i inputs $X_1,X_2,\cdots ,X_i$, where $1\le i\le l$). It follows that, the relationship (I) degenerates to

$$\begin{array}{c}\hfill \left(III\right)\left\{\begin{array}{ccc}{a}_0=b_0\oplus {\sum }_{j=1}^l{b}_j{B}_j,\hfill & & i=0\hfill \\ a_i={\sum }_{j=i}^l{b}_j{A}_{ji},\hfill & & 1\le i\le l\hfill \end{array}\right.\end{array}$$

In this case, authenticated encryption schemes are also called authenticated online ciphers. The typical authenticated online ciphers include ELmE [25], ELmD [24], and COLM [13]. Similar checksum techniques are actually used in their design. To take it one step further, if $A_{i1}=\cdots =A_{ii}=1,B_i=c$, then $Y_i=X_1\oplus X_2\oplus \cdots \oplus X_i\oplus c$ for $1\le i\le l$, where c is an arbitrary constant. In this case, PIC must satisfy the following equation:

$$\begin{array}{cc}\hfill PIC& =f(X_1,\cdots ,X_l)=a_0\oplus a_1{X}_1\oplus \cdots \oplus a_l{X}_l\hfill \\ \hfill & =g(Y_1,\cdots ,Y_l)=b_0\oplus b_1{Y}_1\oplus \cdots \oplus b_l{Y}_l,\hfill \end{array}$$

where $a_i$ and $b_i$ ($0\le i\le l$) satisfy the following relationship:

$$\begin{array}{c}\hfill \left(IV\right)\left\{\begin{array}{ccc}{a}_0=b_0\oplus \sum _{j=1}^l{b}_{j}c,\hfill & & i=0\hfill \\ a_i=\sum _{j=i}^l{b}_j=b_i\oplus \cdots \oplus b_l,\hfill & & 1\le i\le l\hfill \end{array}\right.\end{array}$$

Theorem 1.

For “Encryption-Mix-Encryption”-type AE modes with PIC, if PIC is generated by all terms of the plaintext blocks and it can also be generated by all terms of the ciphertext blocks, then the INT-RUP security can be guaranteed.

Proof. 

Let $\Pi =({\mathcal{E}}_K,{\mathcal{D}}_K,{\mathcal{V}}_K)$ be “Encryption-Mix-Encryption”-type AE modes with PIC. Assume that the adversary $\mathcal{A}$ makes $q_e$ encryption queries ${\left\{(N^i,M^i)\right\}}_{i=1}^{q_e}$ to the encryption oracle ${\mathcal{E}}_K(·,·)$ and receives $(C^i,T^i)={\mathcal{E}}_K(N^i,M^i)$, where $1\le i\le q_e$, and makes $q_d$ decryption queries ${\left\{(N^{*j},C^{*j},T^{*j})\right\}}_{j=1}^{q_d}$ to the decryption oracle ${\mathcal{D}}_K(·,·,·)$ and obtains the unverified plaintext $M^{*j}={\mathcal{D}}_K(N^{*j},C^{*j},T^{*j})$, where $1\le j\le q_d$. Note that $(N^{*j},C^{*j},T^{*j})\ne (N^i,C^i,T^i),1\le i\le q_e,1\le j\le q_d$ and $q_e+q_d=q$. Then, $\mathcal{A}$ forges $q_v$ challenge queries $\left\{\right(N^{\prime 1},C^{\prime 1}$, $T^{\prime 1}),(N^{\prime 2},C^{\prime 2},T^{\prime 2}),\cdots$, $(N^{\prime q_v},C^{\prime q_v},T^{\prime q_v})\}\not\subset \{(N^1,C^1,T^1),\cdots ,(N^{q_e},C^{q_e},T^{q_e})\}$ to the verification oracle ${\mathcal{V}}_K(·,·,·)$, where $C^{\prime k}=C_1^{\prime k}{C}_2^{\prime k}\cdots C_{l^{\prime k}}^{\prime k},C^i=C_1^i{C}_2^i\cdots C_{l^i}^i,1\le k\le q_v,1\le i\le q_e$.

All TBCs of $\Pi$ are replaced with tweakable random permutations to obtain $\Pi \left[\tilde{\pi }\right]$, where $\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n)$ and $\Gamma$ is a tweak space. Then the INT-RUP-advantage of $\mathcal{A}$ is

$$\begin{array}{cc}\hfill Ad{v}_{\Pi }^{int-rup}\left(\mathcal{A}\right)=& Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\mathcal{E}}_K,{\mathcal{D}}_K,{\mathcal{V}}_K}forges]\hfill \\ \hfill \le & |Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\mathcal{E}}_K,{\mathcal{D}}_K,{\mathcal{V}}_K}forges]-Pr[\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n):{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}forges]|\hfill \\ \hfill & +Pr[\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n):{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}forges]\hfill \\ \hfill =& Ad{v}_{\tilde{E}}^{\widetilde{mprp}}\left(\mathcal{B}\right)+Pr[\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n):{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}forges]\hfill \\ \hfill =& Ad{v}_{\tilde{E}}^{\widetilde{mprp}}\left(\mathcal{B}\right)+Ad{v}_{\Pi \left[\tilde{\pi }\right]}^{int-rup}\left(\mathcal{A}\right),\hfill \end{array}$$

where $\mathcal{B}$ is an MTPRP adversary against $\tilde{E}$.

Let $\mathbf{F}$ be an event that at least one forgery attempt in all $q_v$ forgery attempts succeeds. Then, the INT-RUP-advantage of $\mathcal{A}$ is

$$\begin{array}{c}\hfill Ad{v}_{\Pi \left[\tilde{\pi }\right]}^{int-rup}\left(\mathcal{A}\right)=Pr\left[{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}forges\right]=Pr\left[{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}sets\mathbf{F}\right]=Pr\left[\mathbf{F}\right].\end{array}$$

Define a collision as the same output from distinct inputs. Let $\mathbf{T}$ be the event that a collision of the authentication tag occurs for the encryption queries.

With the total probability formula and the probability inequality, one has

$$\begin{array}{cc}\hfill Pr\left[\mathbf{F}\right]& =Pr[\mathbf{F}\wedge \neg \mathbf{T}]+Pr[\mathbf{F}\wedge \mathbf{T}]=Pr\left[\mathbf{F}\right|\neg \mathbf{T}\left]Pr\right[\neg \mathbf{T}]+Pr[\mathbf{F}\left|\mathbf{T}\right]Pr\left[\mathbf{T}\right]\hfill \\ \hfill & \le Pr\left[\mathbf{F}\right|\neg \mathbf{T}]+Pr[\mathbf{T}].\hfill \end{array}$$

Step 1: Bound the probability of event $\mathbf{T}$ occurring: $Pr\left[\mathbf{T}\right]\le \frac{q^2}{2^n}$.

Step 2: Evaluate the upper bound of the probability that event $\mathbf{F}$ occurs under the condition $\neg \mathbf{T}$: $Pr\left[\mathbf{F}\right|\neg \mathbf{T}]$. For simplicity, a single forgery attempt $(N^{\prime },C^{\prime },T^{\prime })\notin \{(N^1,C^1,T^1),\cdots$, $(N^{q_e},C^{q_e},T^{q_e})\}$ is first considered, where $C^{\prime }$ is divided into $l^{\prime }$ blocks and $C^i$ is divided into $l^i$ blocks for $1\le i\le q_e$. Let ${\mathcal{T}}_e=\{T^1,T^2,\cdots ,T^{q_e}\}$ be a set of the authentication tags generated by the encryption oracle (Under the condition $\neg \mathbf{T}$, $T^1,T^2,\cdots ,T^{q_e}$ are distinct from each other).

Case 1: $T^{\prime }$ is new, i.e., $T^{\prime }\notin {\mathcal{T}}_e$. In this case, the adversary $\mathcal{A}$ already knows the value of $T^i$, where $1\le i\le q_e$, and with this knowledge, the adversary tries to guess the preimage of another new tag. Therefore, the probability that the adversary $\mathcal{A}$ correctly guesses this value is at most $1/(2^n-q_e)$, which is also the probability that the adversary’s forgery attempt succeeds.

Case 2: $T^{\prime }$ is old, i.e., $T^{\prime }\in {\mathcal{T}}_e$. Let us say $T^{\prime }=T^u$, where $u\in \{1,\cdots ,q_e\}$. According to the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ of the authentication tag generation, a further analysis is discussed as follows.

Case 2-1: If $N^{\prime }\ne N^u$, the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ are new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new nonce $N^{\prime }$. The image of a single point under a tweakable random permutation is uniform, so the generated tag is an independent and uniform random value. Thus, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.

Case 2-2: If $N^{\prime }=N^u$ and $l^{\prime }\ne l^u$, the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ are new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new block-length $l^{\prime }$. The image of a single point under a tweakable random permutation is uniform, so the generated tag is an independent and uniform random value. Thus, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.

Case 2-3: If $N^{\prime }=N^u$ and $l^{\prime }=l^u$, the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ in this case are the same as those of previous query–response pairs $(N^u,M^u,C^u,T^u)$. According to $PI{C}^{\prime }=b_0\oplus b_1{Y}_1^{\prime }\oplus b_2{Y}_2^{\prime }\oplus \cdots \oplus b_l{Y}_l^{\prime }$, where $Y_i^{\prime }={\left({\tilde{\pi }}^{N^{\prime },i,2}\right)}^{-1}\left(C_i^{\prime }\right)$ for all $1\le i\le l^{\prime }$, a further discussion is shown as follows.

• $C^{\prime }$ is new and $PI{C}^{\prime }$ is new, i.e., $PI{C}^{\prime }\ne PI{C}^u$. The probability that this case occurs is about $1-1/2^n$. The adversary tries to forge an identical tag $(T^{\prime }=T^u)$ using a new checksum $PI{C}^{\prime }$. Thus, the probability that the adversary’s forgery attempt succeeds is $1/2^n$.
• $C^{\prime }$ is new and $PI{C}^{\prime }$ is old, i.e., $PI{C}^{\prime }=PI{C}^u$. According to the fact that $Pr[b_1{Y}_1^{\prime }\oplus b_2{Y}_2^{\prime }\oplus \cdots \oplus b_l{Y}_l^{\prime }=c]=1/2^n$ for any $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }}^{\prime }\in {\{0,1\}}^n$, where c is a constant from ${\{0,1\}}^n$, the probability that $PI{C}^{\prime }$ is old is at most $1/2^n$. Therefore, the probability that the adversary can guess the correct value in this case is the probability that $PI{C}^{\prime }$ is old, which is at most $1/2^n$.
• $C^{\prime }$ is old. This contradicts $(N^{\prime },C^{\prime },T^{\prime })\not\subset \{(N^1,C^1,T^1),\cdots ,(N^{q_e},C^{q_e},T^{q_e})\}$.

Summarizing all cases above, the successful probability of the single forgery attempt is upper-bounded by

$$\begin{array}{c}\hfill max\{1/(2^n-q_e),1/2^n\}\le 2/2^n.\end{array}$$

Therefore, for $q_v$ forgery attempts, it is easy to bound the probability that event $\mathbf{F}$ occurs under the condition $\neg \mathbf{T}$:

$$\begin{array}{c}\hfill Pr\left[\mathbf{F}\right|\neg \mathbf{T}]\le 2q_v/2^n.\end{array}$$

The INT-RUP advantage of $\mathcal{A}$, after q encryption and decryption queries, and $q_v$ forgery queries, is

$$\begin{array}{cc}\hfill Ad{v}_{\Pi }^{int-rup}\left(\mathcal{A}\right)& \le Ad{v}_{\tilde{E}}^{\widetilde{mprp}}\left(\mathcal{B}\right)+\frac{q^2}{2^n}+\frac{2q_v}{2^n},\hfill \end{array}$$

where $\mathcal{B}$ is an MTPRP adversary against $\tilde{E}$. If $\tilde{E}$ is a secure MTPRP, then $\Pi$ with PIC guarantees the INT-RUP security.    □

Here, PIC just focuses on the authentication of the plaintext. The authentication of the associated data should be included in the verification algorithm. This paper directly utilizes PMAC1 algorithm [6] to generate the authentication of the associated data A, i.e., $c=T_A=PMAC1\left(A\right)$. In addition, the associated data can also be treated in a similar way to messages, just saving the final output as its authentication tag.

4. COPA-PIC: COPA with Polynomial Intermediate Checksum for INT-RUP Security

To solve the INT-RUP security defect of COPA, the PIC technique is applied to COPA, and an improved variant, COPA-PIC, is proposed. In this section, the top-level design of COPA-PIC is first described from the angle of TBCs, and then blockcipher-based and permutation-based COPA-PIC instances are presented.

4.1. TBC-Based COPA-PIC: COPA-PIC[$\tilde{E}$]

At the beginning of the design, the idea was to retain as much of the COPA structure as possible. Therefore, the mainly structure of COPA-PIC is the same as that of COPA except that the plaintext checksum used in the encryption and verification algorithms is replaced with PIC. For PIC, a polynomial sum with full terms of internal intermediate states is utilized to ensure INT-RUP security. Therefore, the verification algorithm and the decryption algorithm of COPA-PIC share parts of computing resources such that the cost of the authentication tag is minimal.

Let $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\mathcal{K}$ is a key space, $\Gamma =\mathcal{N}\times \mathcal{I}\times \mathcal{J}$ is a tweak space, $\mathcal{N}$ is a nonce space, $\mathcal{I}$ is a large-integer set, and $\mathcal{J}$ is a small-integer set. We assume that COPA-PIC takes a key K, a nonce N, associated data A, and a plaintext $M=M_1\left|\right|M_2\left|\right|\cdots \left|\right|M_l$ as input and returns the corresponding ciphertext $C=C_1\left|\right|C_2\left|\right|\cdots$$\left|\right|C_l$ and an authentication tag T. Then, the checksum of COPA-PIC is $PIC=2^{l-1}{X}_1\oplus 2^{l-2}{X}_2\oplus \cdots \oplus 2X_{l-1}\oplus X_l=g(Y_1,Y_2,\cdots ,Y_l)$, where $X_i={\tilde{E}}_K^{N,i,1}\left(M_i\right)$ and $Y_i={\tilde{D}}_K^{N,i,2}\left(C_i\right)$ for all $1\le i\le l$, and g is a full-term polynomial function. It is essential to call two extra TBCs in the tag-generating process (let $N=N^{\prime }$ and $M=M^{\prime }$; then, $PIC=PI{C}^{\prime }$; for two distinct associated data $A\ne A^{\prime }$, if the final authentication tag is generated by calling once extra primitive, we can get the difference in the authentication tag of associated data and the difference in the final authentication tag, which can be easily used to obtain a forgery attack).

The overview of COPA-PIC[$\tilde{E}$] is shown in Figure 2, and its authentication component of the associated data is depicted in Figure 3. The authentication of associated data utilizes the TBC-based PMAC1 algorithm, which is shown in Algorithm 1. COPA-PIC[$\tilde{E}$] consists of an encryption algorithm $\mathcal{E}$, a decryption algorithm $\mathcal{D}$, and a verification algorithm $\mathcal{V}$, which are shown in Algorithms 2–4.

Algorithm 1 PMAC1 algorithm $PMAC{1}_K^N\left(A\right)$

Input:  Key K, nonce N, associated data A; Output:  Tag of associated data $T_A$; 1:  Partition A into $A_1\parallel \cdots \parallel A_a$, $|A_i|=n,1\le i\le a-1,0<|A_a|\le n$; 2:  for $i=1$ to $i=a-1$ do 3:     $S_i\leftarrow {\tilde{E}}_K^{N,i,5}\left(A_i\right)$; 4:  end for 5:  if  $|A_a|=n$  then 6:     $\Sigma \leftarrow S_1\oplus S_2\oplus \cdots \oplus S_{a-1}\oplus A_a$; 7:     $T_A={\tilde{E}}_K^{N,a,6}(\Sigma )$; 8:  else 9:     $\Sigma \leftarrow S_1\oplus S_2\oplus \cdots \oplus S_{a-1}\oplus A_a{10}^{*}$; 10:   $T_A={\tilde{E}}_K^{N,a,7}(\Sigma )$; 11: end if 12: return  $T_A$

Algorithm 2 Encryption algorithm $COPA-PIC.{\mathcal{E}}_K^N(A,M)$

Input:  Key K, nonce N, associated data A, and plaintext M; Output:  Ciphertext C and authentication tag T; 1:  Partition M into $M_1\parallel \cdots \parallel M_l$, $|M_i|=n,1\le i\le l$; 2:  $Y_0=T_A$; 3:  for $i=1$ to $i=l$ do 4:    $X_i\leftarrow {\tilde{E}}_K^{N,i,1}\left(M_i\right)$; 5:    $Y_i=Y_{i-1}\oplus X_i$; 6:    $C_i\leftarrow {\tilde{E}}_K^{N,i,2}\left(Y_i\right)$; 7:  end for 8:  $PIC\leftarrow 2^{l-1}{X}_1\oplus 2^{l-2}{X}_2\oplus \cdots \oplus 2X_{l-1}\oplus X_l$; 9:  $\Sigma ={\tilde{E}}_K^{N,l,3}\left(PIC\right)$; 10: $T={\tilde{E}}_K^{N,l,4}(\Sigma \oplus Y_l)$; 11: return $\left(C_1\right|\left|C_2\right||\cdots ||C_l,T)$

Algorithm 3 Decryption algorithm $COPA-PIC.{\mathcal{D}}_K^N(A,C,T)$

Input:  Key K, nonce N, associated data A, ciphertext C, and authentication tag T; Output:  Plaintext M; 1: Partition C into $C_1\parallel \cdots \parallel C_l$, $|C_i|=n,1\le i\le l$; 2: $Y_0=T_A$; 3: for $i=1$ to $i=l$ do 4:    $Y_i\leftarrow {\tilde{D}}_K^{N,i,2}\left(C_i\right)$; 5:    $X_i=Y_{i-1}\oplus Y_i$; 6:    $M_i\leftarrow {\tilde{D}}_K^{N,i,1}\left(X_i\right)$; 7: end for 8: return  $M=M_1\left|\right|M_2\left|\right|\cdots \left|\right|M_l$

Algorithm 4 Verification algorithm $COPA-PIC.{\mathcal{V}}_K^N(A,C,T)$

Input:  Key K, nonce N, associated data A, ciphertext C, and authentication tag T; Output:  Success or failure $\top /\perp$; 1:  Partition C into $C_1\parallel \cdots \parallel C_l$, $|C_i|=n,1\le i\le l$; 2:  $Y_0=T_A$; 3:  for $i=1$ to $i=l$ do 4:      $Y_i\leftarrow {\tilde{D}}_K^{N,i,2}\left(C_i\right)$; 5:  end for 6:  $PIC=2^{l-1}{Y}_0\oplus 3·2^{l-2}{Y}_1\oplus 3·2^{l-3}{Y}_2\oplus \cdots \oplus 3Y_{l-1}\oplus Y_l$; 7:  $\Sigma ={\tilde{E}}_K^{N,l,3}\left(PIC\right)$; 8:  $T^{\prime }={\tilde{E}}_K^{N,l,4}(\Sigma \oplus Y_l)$; 9:  if $T^{\prime }=T$ then 10:     return ⊤; 11: else 12:     return ⊥; 13: end if

For COPA-PIC, we check the correctness as follows:

$$\begin{array}{cc}\hfill PIC=& f(X_1,X_2,\cdots ,X_l)=2^{l-1}{X}_1\oplus 2^{l-2}{X}_2\oplus \cdots \oplus X_l\hfill \\ \hfill =& 2^{l-1}(T_A\oplus Y_1)\oplus 2^{l-2}(Y_1\oplus Y_2)\oplus \cdots \oplus (Y_{l-1}\oplus Y_l)\hfill \\ \hfill =& 2^{l-1}{T}_A\oplus 3·2^{l-2}{Y}_1\oplus \cdots \oplus 3Y_{l-1}\oplus Y_l\hfill \\ \hfill =& g(Y_1,Y_2,\cdots ,Y_l).\hfill \end{array}$$

Thus, PIC is both a polynomial function with full terms of the plaintext blocks and a polynomial function with full terms of the ciphertext blocks, which meets Conditions 1 and 2. Therefore, according to Theorem 1, COPA-PIC[$\tilde{E}$] ensures INT-RUP security.

Next, the strict INT-RUP security of COPA-PIC[$\tilde{E}$] is given in the following theorems.

Theorem 2

(INT-RUP security of COPA-PIC based on ideal TBCs). For COPA-PIC[$\tilde{E}$], real TBCs are replaced with tweakable random permutations $\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n)$ to obtain COPA-PIC[$\tilde{\pi }$]. Let $\mathcal{A}$ be a nonce-misusing adversary with q encryption and decryption queries and $q_v$ forgery attempts. Then, one has

$$\begin{array}{c}\hfill Ad{v}_{COPA-PIC\left[\tilde{\pi }\right]}^{int-rup}\left(\mathcal{A}\right)\le \frac{q^2}{2^n}+\frac{(l+2){(q-1)}^2}{2^n}+\frac{2q_v}{2^n}.\end{array}$$

Proof. 

Similar to the proof of Theorem 1, assume that $\mathcal{A}$ makes $q_e$ encryption queries ${\left\{(N^i,A^i,M^i)\right\}}_{i=1}^{q_e}$ to $\mathcal{E}(·,·,·)$ and receives $(C^i,T^i)=\mathcal{E}(N^i,A^i,M^i)$, where $1\le i\le q_e$, and makes $q_d$ decryption queries ${\left\{(N^{*j},A^{*j},C^{*j},T^{*j})\right\}}_{j=1}^{q_d}$ to $\mathcal{D}(·,·,·,·)$ and obtains the unverified plaintext $M^{*j}=\mathcal{D}(N^{*j},A^{*j},C^{*j},T^{*j})$, where $1\le j\le q_d$. Note that $(N^{*j},A^{*j},C^{*j},T^{*j})\ne (N^i,A^i,C^i,T^i),1\le i\le q_e,1\le j\le q_d$ and $q_e+q_d=q$. Then, $\mathcal{A}$ forges $q_v$ challenge queries $\left\{\right(N^{\prime 1},A^{\prime 1},C^{\prime 1}$, $T^{\prime 1}),(N^{\prime 2},A^{\prime 2},C^{\prime 2},T^{\prime 2}),\cdots ,(N^{\prime q_v},A^{\prime q_v},C^{\prime q_v},T^{\prime q_v})\}\not\subset \{(N^1,A^1,C^1,T^1),\cdots ,(N^{q_e}$, $A^{q_e},C^{q_e},T^{q_e}\left)\right\}$ to $\mathcal{V}(·,·,·,·)$, where $C^{\prime k}=C_1^{\prime k}{C}_2^{\prime k}\cdots C_{l^{\prime k}}^{\prime k},C^i=C_1^i{C}_2^i\cdots C_{l^i}^i,1\le k\le q_v,1\le i\le q_e$.

Let $\mathbf{F}$ be an event that at least one forgery attempt in all $q_v$ forgery attempts succeeds. Then, the INT-RUP-advantage of $\mathcal{A}$ is

$$\begin{array}{c}\hfill Ad{v}_{COPA-PIC\left[\tilde{\pi }\right]}^{int-rup}\left(\mathcal{A}\right)=Pr\left[{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}forges\right]=Pr\left[{\mathcal{A}}^{\mathcal{E},\mathcal{D},\mathcal{V}}sets\mathbf{F}\right]=Pr\left[\mathbf{F}\right].\end{array}$$

(1)

Denote variables $Y_{\alpha }$ of internal state values as $Y_{\alpha }={⨁}_{i=1}^{\alpha }{\tilde{\pi }}^{N,i,1}\left(M_i\right)\oplus T_A$, which is also equal to ${\left({\tilde{\pi }}^{N,\alpha ,2}\right)}^{-1}\left(C_{\alpha }\right)$, where $1\le \alpha \le l$ and $T_A$ is the authentication of the associated data A. Define a collision as the same value $Y_{\alpha }$ from different prefixes $A{M}_1{M}_2\cdots M_{\alpha }$ and $A^{\prime }{M}_1^{\prime }{M}_2^{\prime }\cdots M_{\alpha }^{\prime }$. More precisely, $Y_{\alpha -1}\ne Y_{\alpha -1}^{\prime }$ and $Y_{\alpha }=Y_{\alpha }^{\prime }$, which means $M_{\alpha }\ne M_{\alpha }^{\prime }$. Let $\mathbf{C}$ be the event that a collision of $Y_{\alpha }$ occurs for some $\alpha$. Similarity, let $\mathbf{T}$ be the event that a collision of the tag occurs for the encryption queries. Let $\mathbf{A}$ be the event that a collision of $T_A$ occurs for two different associated data. Let $\mathbf{E}$ be the union of events $\mathbf{C}$, $\mathbf{T}$, and $\mathbf{A}$; then, $\mathbf{E}=\mathbf{A}\vee \mathbf{C}\vee \mathbf{T}$.

With the total probability formula and the probability inequality, one has

$$\begin{array}{c}\hfill Pr\left[\mathbf{F}\right]=Pr\left[\mathbf{F}\right|\neg \mathbf{E}\left]Pr\right[\neg \mathbf{E}]+Pr[\mathbf{F}\left|\mathbf{E}\right]Pr\left[\mathbf{E}\right]\le Pr\left[\mathbf{F}\right|\neg \mathbf{E}]+Pr[\mathbf{E}].\end{array}$$

(2)

Step 1: Bound the probability of event $\mathbf{E}$ occurring: $Pr\left[\mathbf{E}\right]$. As COPA-PIC and COPA have the same encryption and decryption structures, the events $\mathbf{E}$, $\mathbf{A}$, and $\mathbf{C}$ are exactly the same as those of COPA. Moreover, COPA-PIC and COPA use different methods for generating tags, but their authentication tags are all generated through the randomization of the checksum and the last ciphertext block. The only difference is whether the checksum has been randomized before. This does not make much difference in authentication processing, but it needs to be carefully considered in verification processing. Therefore, the event $\mathbf{T}$ is exactly the same as that of COPA.

According to two claims $Pr\left[\mathbf{A}\right]\le q^2/2^n$ and $Pr[\mathbf{C}\vee \mathbf{T}|\neg \mathbf{A}]\le (l+2){(q-1)}^2/2^n$ in COPA and the total probability formula, one has

$$\begin{array}{c}\hfill Pr\left[\mathbf{E}\right]=Pr[\mathbf{A}\vee \mathbf{C}\vee \mathbf{T}]\le Pr\left[\mathbf{A}\right]+Pr[\mathbf{C}\vee \mathbf{T}|\neg \mathbf{A}]\le q^2/2^n+(l+2){(q-1)}^2/2^n.\end{array}$$

(3)

Step 2: Evaluate the upper bound of the probability that event $\mathbf{F}$ occurs under the condition $\neg \mathbf{E}$: $Pr\left[\mathbf{F}\right|\neg \mathbf{E}]$. For simplicity, a single forgery attempt $(N^{\prime },A^{\prime },C^{\prime },T^{\prime })\notin \{(N^1,A^1,C^1,T^1),\cdots ,(N^{q_e},A^{q_e},C^{q_e},T^{q_e})\}$ is considered, where $C^{\prime }$ is divided into $l^{\prime }$ blocks and $C^i$ is divided into $l^i$ blocks for $1\le i\le q_e$. Let ${\mathcal{T}}_e=\{T^1,T^2,\cdots ,T^{q_e}\}$ be a set of the authentication tags generated by the encryption oracle.

Case 1: $T^{\prime }$ is new, i.e., $T^{\prime }\notin {\mathcal{T}}_e$. In this case, the adversary $\mathcal{A}$ already knows the value of $T^i$, where $1\le i\le q_e$, and with this knowledge, the adversary tries to guess the preimage of another new tag. Therefore, the probability that the adversary $\mathcal{A}$ correctly guesses this value is at most $1/(2^n-q_e)$, which is also the probability that the adversary’s forgery attempt succeeds.

Case 2: $T^{\prime }$ is old, i.e., $T^{\prime }\in {\mathcal{T}}_e$. Let us say $T^{\prime }=T^u$, where $u\in \{1,\cdots ,q_e\}$. According to the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ of generating the authentication tag, a further analysis should be discussed as follows.

Case 2-1: If $N^{\prime }\ne N^u$, the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ are new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new nonce $N^{\prime }$. The image of a single point under a tweakable random permutation is uniform, so the generated tag is an independent and uniform random value. Thus, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.

Case 2-2: If $N^{\prime }=N^u$ and $l^{\prime }\ne l^u$, the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ are new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new block length $l^{\prime }$. The image of a single point under a tweakable random permutation is uniform, so the generated tag is an independent and uniform random value. Thus, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.

Case 2-3: If $N^{\prime }=N^u$ and $l^{\prime }=l^u$, the last two tweaks $(N^{\prime },l^{\prime },3)$ and $(N^{\prime },l^{\prime },4)$ in this case are the same as those of the previous query–response pair $(N^u,A^u,M^u,C^u,T^u)$. According to $PI{C}^{\prime }=2^{l^{\prime }-1}{T}_{A^{\prime }}^{\prime }\oplus 3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }\oplus Y_{l^{\prime }}^{\prime }$, where $T_{A^{\prime }}^{\prime }=PMAC1\left(A^{\prime }\right)$ and $Y_i^{\prime }={\left({\tilde{\pi }}^{N^{\prime },i,2}\right)}^{-1}\left(C_i^{\prime }\right)$ for all $1\le i\le l^{\prime }$, a further discussion should be considered as follows.

• $A^{\prime }\ne A^u$. Let $T_{A^i}=PMAC1\left(A^i\right)$, where $1\le i\le q_e$. Under the condition that $\neg \mathbf{E}$ ($\neg \mathbf{A}$), $T_{A^1},T_{A^2},\cdots ,T_{A^{q_e}}$ are distinct from each other. According to $T_{A^{\prime }}^{\prime }=PMAC1\left(A^{\prime }\right)$, we consider the following two cases.

  (a)

  $T_{A^{\prime }}^{\prime }$ is new, i.e., $T_{A^{\prime }}^{\prime }\ne T_{A^u}$. The probability that this case occurs is $1-1/2^n$.

  • $C_{l^{\prime }}^{\prime }$ is new. Then, $Y_{l^{\prime }}^{\prime }$ is new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new ciphertext block $C_{l^{\prime }}^{\prime }$. Therefore, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.
  • $C_{l^{\prime }}^{\prime }$ is old and $C^{\prime }$ is new. Then, $Y_{l^{\prime }}^{\prime }$ is old and there exists at least one more fresh value in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }\in {\{0,1\}}^n$. According to whether $PI{C}^{\prime }=2^{l^{\prime }-1}{T}_{A^{\prime }}^{\prime }\oplus 3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }\oplus Y_{l^{\prime }}^{\prime }$ is new or not, the following subcases are discussed.
    • $PI{C}^{\prime }$ is new, i.e., $PI{C}^{\prime }\ne PI{C}^u$. The probability that this case occurs is about $1-1/2^n$. The adversary tries to forge an identical tag $(T^{\prime }=T^u)$ using a new checksum $PI{C}^{\prime }$. Thus, the probability that the adversary’s forgery attempt succeeds is $(1-1/2^n)\times 1/2^n\le 1/2^n$.
    • $PI{C}^{\prime }$ is old, i.e., $PI{C}^{\prime }=PI{C}^u$. According to the fact that $Pr[2^{l^{\prime }-1}{T}_{A^{\prime }}^{\prime }$$\oplus 3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }=c]=1/2^n$ for any $T_{A^{\prime }}^{\prime },Y_1^{\prime },Y_2^{\prime },\cdots ,$$Y_{l^{\prime }-1}^{\prime }\in {\{0,1\}}^n$, where c is a constant from ${\{0,1\}}^n$, the probability that $PI{C}^{\prime }$ is old is at most $1/2^n$. As $PI{C}^{\prime }$, $Y_{l^{\prime }}^{\prime }$, and $(N^{\prime },l^{\prime })$ are old, the probability of obtaining an identical tag $(T^{\prime }=T^u)$ is 1. Therefore, the probability that the adversary can guess the correct value in this case is the probability that $PI{C}^{\prime }$ is old, which is at most $1/2^n$.
  • $C^{\prime }$ is old. Then, $Y_i^{\prime }$ is old, where $1\le i\le l^{\prime }$. According to $PI{C}^{\prime }=2^{l^{\prime }-1}{T}_{A^{\prime }}^{\prime }\oplus 3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }\oplus Y_{l^{\prime }}^{\prime }$; then, $PI{C}^{\prime }$ is a fresh random value. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using new associated data $A^{\prime }$ (or a new checksum $PI{C}^{\prime }$). Therefore, the probability that the adversary can guess the correct value is $1/2^n$.

  Summarizing the cases of (a), the probability that the adversary can guess the correct value is at most $(1-1/2^n)\times 1/2^n\le 1/2^n$.

  (b)

  $T_{A^{\prime }}^{\prime }$ is old, i.e., $T_{A^{\prime }}^{\prime }=T_{A^u}$. The probability that this case occurs is $1/2^n$.

  • $C_{l^{\prime }}^{\prime }$ is new. Then, $Y_{l^{\prime }}^{\prime }$ is new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new ciphertext block $C_{l^{\prime }}^{\prime }$. Therefore, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.
  • $C_{l^{\prime }}^{\prime }$ is old and $C^{\prime }$ is new. Then, $Y_{l^{\prime }}^{\prime }$ is old and there exists at least one more fresh value in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }\in {\{0,1\}}^n$. If there only exists one fresh value in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }\in {\{0,1\}}^n$, according to $PI{C}^{\prime }=2^{l^{\prime }-1}{T}_{A^{\prime }}^{\prime }\oplus 3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }\oplus Y_{l^{\prime }}^{\prime }$, then $PI{C}^{\prime }$ is new. Therefore, the probability that the adversary’s forgery attempt succeeds is $1/2^n$. If there exist at least two more fresh values in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }$$\in {\{0,1\}}^n$, according to whether $PI{C}^{\prime }$ is new or not, the following subcases are discussed.
    • $PI{C}^{\prime }$ is new, i.e., $PI{C}^{\prime }\ne PI{C}^u$. The probability that this case occurs is about $1-1/2^n$. The adversary tries to forge an identical tag $(T^{\prime }=T^u)$ using a new checksum $PI{C}^{\prime }$. Thus, the probability that the adversary’s forgery attempt succeeds is $(1-1/2^n)\times 1/2^n\le 1/2^n$.
    • $PI{C}^{\prime }$ is old, i.e., $PI{C}^{\prime }=PI{C}^u$. According to the fact that $Pr[3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }=c]=1/2^n$ for any $Y_1^{\prime },Y_2^{\prime },\cdots ,$$Y_{l^{\prime }-1}^{\prime }$$\in {\{0,1\}}^n$, where c is a constant from ${\{0,1\}}^n$, the probability that $PI{C}^{\prime }$ is old is at most $1/2^n$. As $PI{C}^{\prime }$, $Y_{l^{\prime }}^{\prime }$ and $(N^{\prime },l^{\prime })$ are old, the probability of obtaining an identical tag $(T^{\prime }=T^u)$ is 1. Therefore, the probability that the adversary can guess the correct value in this case is the probability that $PI{C}^{\prime }$ is old, which is at most $1/2^n$.
  • $C^{\prime }$ is old. Then, $Y_i^{\prime }$ is old, where $1\le i\le l^{\prime }$. As $PI{C}^{\prime }$, $Y_{l^{\prime }}^{\prime }$, and $(N^{\prime },l^{\prime })$ are old, the probability that the adversary can guess the correct value is 1.

  Summarizing the cases of (b), the probability that the adversary can guess the correct value is at most $1/2^n\times max\{1/2^n,1\}\le 1/2^n$.

• $A^{\prime }=A^u$; then, $T_{A^{\prime }}^{\prime }=T_{A^u}$. As $(N^{\prime },A^{\prime },C^{\prime },T^{\prime })\notin {\left\{(N^i,A^i,C^i,T^i)\right\}}_{i=1}^{q_e}$; therefore, $C^{\prime }$ must be new.

  (a)

  $C_{l^{\prime }}^{\prime }$ is new. Then, $Y_{l^{\prime }}^{\prime }$ is new. The adversary tries to forge an identical tag ($T^{\prime }=T^u$) using a new ciphertext block $C_{l^{\prime }}^{\prime }$. Therefore, the probability that the adversary correctly forges an identical tag ($T^{\prime }=T^u$) is $1/2^n$.

  (b)

  $C_{l^{\prime }}^{\prime }$ is old and $C^{\prime }$ is new. Then, $Y_{l^{\prime }}^{\prime }$ is old and there exists at least one more fresh value in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }\in {\{0,1\}}^n$.

  • If there only exists one fresh value in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }\in {\{0,1\}}^n$, according to $PI{C}^{\prime }=2^{l^{\prime }-1}{T}_{A^{\prime }}^{\prime }\oplus 3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }\oplus Y_{l^{\prime }}^{\prime }$, then $PI{C}^{\prime }$ is new. The adversary tries to forge an identical tag $(T^{\prime }=T^u)$ using a new checksum $PI{C}^{\prime }$. Therefore, the probability that the adversary’s forgery attempt succeeds is $1/2^n$.
  • If there exist at least two more fresh values in $Y_1^{\prime },Y_2^{\prime },\cdots ,Y_{l^{\prime }-1}^{\prime }$$\in {\{0,1\}}^n$, according to whether $PI{C}^{\prime }$ is new or not, the following subcases are discussed.
    • $PI{C}^{\prime }$ is new, i.e., $PI{C}^{\prime }\ne PI{C}^u$. The probability that this case occurs is about $1-1/2^n$. The adversary tries to forge an identical tag $(T^{\prime }=T^u)$ using a new checksum $PI{C}^{\prime }$. Thus, the probability that the adversary’s forgery attempt succeeds is $(1-1/2^n)\times 1/2^n\le 1/2^n$.
    • $PI{C}^{\prime }$ is old, i.e., $PI{C}^{\prime }=PI{C}^u$. According to the fact that $Pr[3·2^{l^{\prime }-2}{Y}_1^{\prime }\oplus 3·2^{l^{\prime }-3}{Y}_2^{\prime }\oplus \cdots \oplus 3Y_{l^{\prime }-1}^{\prime }=c]=1/2^n$ for any $Y_1^{\prime },Y_2^{\prime },\cdots ,$$Y_{l^{\prime }-1}^{\prime }$$\in {\{0,1\}}^n$, where c is a constant from ${\{0,1\}}^n$, the probability that $PI{C}^{\prime }$ is old is at most $1/2^n$. As $PI{C}^{\prime }$, $Y_{l^{\prime }}^{\prime }$, and $(N^{\prime },l^{\prime })$ are old, the probability of obtaining $T^{\prime }=T^u$ is 1. Therefore, the probability that the adversary can guess the correct value in this case is the probability that $PI{C}^{\prime }$ is old, which is at most $1/2^n$.

Summarizing all cases above, the successful probability of the single forgery attempt is upper-bounded by

$$\begin{array}{c}\hfill max\{1/(2^n-q_e),1/2^n\}\le 2/2^n.\end{array}$$

Therefore, for $q_v$ forgery attempts, the probability that event $\mathbf{F}$ occurs under the condition $\neg \mathbf{E}$ is

$$\begin{array}{c}\hfill Pr\left[\mathbf{F}\right|\neg \mathbf{E}]\le 2q_v/2^n.\end{array}$$

(4)

Combining Equations (1)–(4), the INT-RUP advantage of $\mathcal{A}$, after q encryption and decryption queries, and $q_v$ forgery queries, is

$$\begin{array}{cc}\hfill Ad{v}_{COPA-PIC\left[\tilde{\pi }\right]}^{int-rup}\left(\mathcal{A}\right)& \le \frac{q^2}{2^n}+\frac{(l+2){(q-1)}^2}{2^n}+\frac{2q_v}{2^n}.\hfill \end{array}$$

The proof of Theorem 2 is finished.    □

Theorem 3

(INT-RUP security of COPA-PIC based on TBCs). Let $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\Gamma =\mathcal{N}\times \mathcal{I}\times \mathcal{J}$ is a tweak space, $\mathcal{N}$ is a nonce space, $\mathcal{I}$ is a large-integer set, and $\mathcal{J}$ is a small-integer set. Let $\mathcal{A}$ be a nonce-misusing adversary with q encryption and decryption queries and $q_v$ forgery attempts. For COPA-PIC[$\tilde{E}$], one has

$$\begin{array}{c}\hfill Ad{v}_{COPA-PIC\left[\tilde{E}\right]}^{int-rup}(t,q+q_v,l,\sigma )\le Ad{v}_{\tilde{E}}^{\widetilde{mprp}}(t^{\prime },2\sigma )+\frac{q^2}{2^n}+\frac{(l+2){(q-1)}^2}{2^n}+\frac{2q_v}{2^n},\end{array}$$

where $t^{\prime }=t+cn\sigma$ for some absolute constant c, and l is the maximum block length.

Proof. 

For COPA-PIC[$\tilde{E}$], all TBCs are replaced with tweakable random permutations to obtain COPA-PIC[$\tilde{\pi }$], where $\tilde{\pi }\stackrel{\$}{\leftarrow }Perm(\Gamma ,n)$ and $\Gamma$ is a tweak space.

Let $\sigma$ be the total query complexity of message blocks for $(q+q_v)$ queries. According to the MTPRP advantage, COPA-PIC[$\tilde{E}$] can be replaced with COPA-PIC[$\tilde{\pi }$], which together cost at most $Ad{v}_{\tilde{E}}^{\widetilde{mprp}}(t^{\prime },2\sigma )$ (here, $2\sigma$ comes from the queries of TBCs in the upper and lower layers; in other words, $2\sigma$ is the query complexity of TBCs), i.e.,

$$\begin{array}{c}\hfill Ad{v}_{COPA-PIC\left[\tilde{E}\right]}^{int-rup}(t,q+q_v,l,\sigma )\le Ad{v}_{\tilde{E}}^{\widetilde{mprp}}(t^{\prime },2\sigma )+Ad{v}_{COPA-PIC\left[\tilde{\pi }\right]}^{int-rup}(t,q+q_v,l,\sigma ).\end{array}$$

(5)

Therefore, combining Equation (5) and Theorem 2, it is easy to obtain the bound of Theorem 3.    □

4.2. Blockcipher-Based COPA-PIC Instance: COPA-PIC[E]

Let $E:\mathcal{K}\times {\{0,1\}}^n\to {\{0,1\}}^n$ be a block cipher and $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\mathcal{K}$ is a key space and $\Gamma$ is a tweak space. This section presents a blockcipher-based instance of COPA-PIC[$\tilde{E}$] by the XEX* construction $\tilde{E}=XE{X}^{*}[E,2^{\mathcal{I}}{3}^{\mathcal{J}}]$ [6] and renames it as COPA-PIC[E].

The overviews of COPA-PIC[E] and blockcipher-based PMAC1 are depicted in Figure 4 and Figure 5, respectively. The blockcipher-based PMAC1 algorithm, and an encryption algorithm ${\mathcal{E}}_K$, a decryption algorithm ${\mathcal{D}}_K$, and a verification algorithm ${\mathcal{V}}_K$ of COPA-PIC[E] are shown in Algorithms 5, 6, 7, and 8, respectively.

Algorithm 5 Blockcipher-based PMAC1 algorithm $PMAC1{\left[E\right]}_K^N\left(A\right)$

Input:  Key K, nonce N, associated data A; Output:  Tag of associated data $T_A$; 1:  Partition A into $A_1\parallel \cdots \parallel A_a$, $|A_i|=n,1\le i\le a-1,0<|A_a|\le n$; 2:  $L=E_K\left(N\right)$; 3:  for $i=1$ to $i=a-1$ do 4:     $S_i\leftarrow E_K(A_i\oplus 2^{i-1}·3^{3}L)$; 5:  end for 6:  if  $|A_a|=n$  then 7:     $\Sigma \leftarrow S_1\oplus S_2\oplus \cdots \oplus S_{a-1}\oplus A_a$; 8:     $T_A=E_K(\Sigma \oplus 2^{a-1}·3^{4}L)$; 9:  else 10:    $\Sigma \leftarrow S_1\oplus S_2\oplus \cdots \oplus S_{a-1}\oplus A_a{10}^{*}$; 11:    $T_A=E_K(\Sigma \oplus 2^{a-1}·3^{5}L)$; 12: end if 13: return  $T_A$

Algorithm 6 Encryption algorithm $COPA-PIC\left[E\right].{\mathcal{E}}_K^N(A,M)$

Input:  Key K, nonce N, associated data A, and plaintext M; Output:  Ciphertext C and authentication tag T; 1:  Partition M into $M_1\parallel \cdots \parallel M_l$, $|M_i|=n,1\le i\le l$; 2:  $L=E_K\left(N\right)$ and $y_0=T_A\oplus L$; 3:  for $i=1$ to $i=l$ do 4:     $x_i\leftarrow E_K(M_i\oplus 2^{i-1}·3L)$ and $X_i$=$x_i\oplus 2^{i-1}·3L$; 5:     $y_i=y_{i-1}\oplus x_i$ and $Y_i=y_i\oplus 2^{i}L$; 6:     $C_i\leftarrow E_K\left(y_i\right)\oplus 2^{i}L$; 7:  end for 8:  $PIC\leftarrow 2^{l-1}{X}_1\oplus 2^{l-2}{X}_2\oplus \cdots \oplus 2X_{l-1}\oplus X_l$; 9:  $\Sigma =E_K(PIC\oplus 2^{l-1}·3^{2}L)$; 10: $T=E_K(\Sigma \oplus y_l)\oplus 2^{l-1}·7L$; 11: return $\left(C_1\right|\left|C_2\right||\cdots ||C_l,T)$

Algorithm 7 Decryption algorithm $COPA-PIC\left[E\right].{\mathcal{D}}_K^N(A,C,T)$

Input:  Key K, nonce N, associated data A, ciphertext C, and authentication tag T; Output:  Plaintext M; 1: Partition C into $C_1\parallel \cdots \parallel C_l$, $|C_i|=n,1\le i\le l$; 2: $L=E_K\left(N\right)$ and $y_0=T_A\oplus L$; 3: for $i=1$ to $i=l$ do 4:    $y_i\leftarrow D_K(C_i\oplus 2^{i}L)$; 5:    $x_i=y_{i-1}\oplus y_i$; 6:    $M_i\leftarrow D_K\left(x_i\right)\oplus 2^{i-1}·3L$; 7: end for 8: return  $M=M_1\left|\right|M_2\left|\right|\cdots \left|\right|M_l$

Theorem 4

(INT-RUP security of COPA-PIC based on block ciphers). Let $E:\mathcal{K}\times {\{0,1\}}^n\to {\{0,1\}}^n$ be a block cipher and $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\mathcal{K}$ is a key space, $\Gamma =\mathcal{N}\times \mathcal{I}\times \mathcal{J}$ is a tweak space, $\mathcal{N}$ is a nonce space, $\mathcal{I}$ is a large-integer set, and $\mathcal{J}$ is a small-integer set. Let $\tilde{E}=XE{X}^{*}[E,2^{\mathcal{I}}{3}^{\mathcal{J}}]$ and assume that $2^i{3}^j\ne 1$ for all $(i,j)\in \mathcal{I}\times \mathcal{J}$. Then, for a nonce-misusing adversary $\mathcal{A}$, one has

$$\begin{array}{c}\hfill Ad{v}_{COPA-PIC\left[E\right]}^{int-rup}\left(\mathcal{A}\right)\le Ad{v}_E^{sprp}\left(\mathcal{B}\right)+\frac{39{(\sigma +q)}^2}{2^n}+\frac{(l+2){(q-1)}^2}{2^n}+\frac{2q_v}{2^n},\end{array}$$

where a new adversary $\mathcal{B}$ has an additional running time equal to the time needed to process the queries from $\mathcal{A}$.

Proof. 

The security proof includes two steps. First, COPA-PIC[E] is converted to COPA-PIC[$\tilde{E}$]. The dummy masks $\{3L,2·3L,\cdots ,2^{l-1}·3L,2^{l-1}·3^{2}L\}$ and $\{2L,2^{2}L$, $\cdots ,2^l·L,2^{l-1}·7L\}$ are introduced to the upper and lower layers of COPA-PIC[E], respectively, in terms of the XEX* construction, where $L=E_K\left(N\right)$. Therefore, distinct TBCs ${\tilde{E}}_K^{N,i,1},{\tilde{E}}_K^{N,i,2},$${\tilde{E}}_K^{N,l,3}$, and ${\tilde{E}}_K^{N,l,4}$ are utilized to replace the block ciphers with distinct masks, where $i=1,\cdots ,l$. For the blockcipher-based PMAC1, distinct TBCs ${\tilde{E}}_K^{N,i,5},{\tilde{E}}_K^{N,a,6}$, and ${\tilde{E}}_K^{N,a,7}$ are utilized to replace the block ciphers with distinct masks, where $i=1,\cdots ,a-1$. According to Lemma 1 and the blockcipher-based PMAC1 [6], COPA-PIC[E] can be replaced with COPA-PIC[$\tilde{E}$], which together cost

$$\begin{array}{c}\hfill \frac{9.5{(2\sigma +2q)}^2}{2^n}+Ad{v}_E^{sprp}(t^{\prime },2·2(\sigma +q))+\frac{{\sigma }^2}{2^n}\end{array}$$

(6)

Then, combining Equation (6) and Theorem 3, the bound of Theorem 4 is obtained.    □

Algorithm 8 Verification algorithm $COPA-PIC\left[E\right].{\mathcal{V}}_K^N(A,C,T)$

Input:  Key K, nonce N, associated data A, ciphertext C, and authentication tag T; Output:  Success or failure $\top /\perp$; 1:  Partition C into $C_1\parallel \cdots \parallel C_l$, $|C_i|=n,1\le i\le l$; 2:  $L=E_K\left(N\right)$ and $Y_0=T_A$; 3:  for $i=1$ to $i=l$ do 4:      $y_i\leftarrow D_K(C_i\oplus 2^{i}L)$ and $Y_i=y_i\oplus 2^{i}L$; 5:  end for 6:  $PIC=2^{l-1}{Y}_0\oplus 3·2^{l-2}{Y}_1\oplus 3·2^{l-3}{Y}_2\oplus \cdots \oplus 3Y_{l-1}\oplus Y_l$; 7:  $\Sigma =E_K(PIC\oplus 2^{l-1}·3^{2}L)$; 8:  $T^{\prime }=E_K(\Sigma \oplus y_l)\oplus 2^{l-1}·7L$; 9:  if $T^{\prime }=T$ then 10:    return ⊤; 11: else 12:    return ⊥; 13: end if

4.3. Permutation-Based COPA-PIC Instance: COPA-PIC[$\pi$]

Let $\pi :{\{0,1\}}^n\to {\{0,1\}}^n$ be a public n-bit permutation, $\mathcal{K}={\{0,1\}}^k$ be a set of k-bit keys, $\mathcal{T}={\{0,1\}}^{n-k}\times \mathcal{I}\times \mathcal{J}$ be a tweak space, $\mathcal{I}$ be a set of large integers, and $\mathcal{J}$ be a set of small integers, we reload COPA-PIC[$\tilde{E}$] by $\tilde{E}=MEM[\pi ,2^{\mathcal{I}}{3}^{\mathcal{J}}]$ [22] to obtain an instance called COPA-PIC[$\pi$].

Let $K,N,A,M,C$, and T be the key, the nonce, the associated data, the plaintext, the ciphertext, and the authentication tag, respectively. The overviews of COPA-PIC[$\pi$] and PMAC1 are depicted in Figure 6 and Figure 7, respectively. The PMAC1 algorithm and an encryption algorithm ${\mathcal{E}}_K$, a decryption algorithm ${\mathcal{D}}_K$, and a verification algorithm ${\mathcal{V}}_K$ of COPA-PIC[$\pi$] are shown in Algorithms 9, 10, 11, and 12, respectively.

Algorithm 9 Permutation-based PMAC1 algorithm $PMAC1{\left[\pi \right]}_K^N\left(A\right)$

Input:  Key K, nonce N, associated data A; Output:  Tag of associated data $T_A$; 1:  Partition A into $A_1\parallel \cdots \parallel A_a$, $|A_i|=n,1\le i\le a-1,0<|A_a|\le n$; 2:  $L=\pi \left(N\right|\left|K\right)$; 3:  for $i=1$ to $i=a-1$ do 4:     $S_i\leftarrow \pi (A_i\oplus 2^{i-1}·3^{3}L)$; 5:  end for 6:  if  $|A_a|=n$  then 7:     $\Sigma \leftarrow S_1\oplus S_2\oplus \cdots \oplus S_{a-1}\oplus A_a$; 8:     $T_A=\pi (\Sigma \oplus 2^{a-1}·3^{4}L)$; 9:  else 10:    $\Sigma \leftarrow S_1\oplus S_2\oplus \cdots \oplus S_{a-1}\oplus A_a{10}^{*}$; 11:    $T_A=\pi (\Sigma \oplus 2^{a-1}·3^{5}L)$; 12: end if 13: return  $T_A$

Algorithm 10 Encryption algorithm $COPA-PIC\left[\pi \right].{\mathcal{E}}_K^N(A,M)$

Input:  Key K, nonce N, associated data A, and plaintext M; Output:  Ciphertext C and authentication tag T; 1:  Partition M into $M_1\parallel \cdots \parallel M_l$, $|M_i|=n,1\le i\le l$; 2:  $L=\pi \left(N\right|\left|K\right)$ and $y_0=T_A\oplus L$; 3:  for $i=1$ to $i=l$ do 4:     $x_i\leftarrow \pi (M_i\oplus 2^{i-1}·3L)$ and $X_i$=$x_i\oplus 2^{i-1}·3L$; 5:     $y_i=y_{i-1}\oplus x_i$ and $Y_i=y_i\oplus 2^{i}L$; 6:     $C_i\leftarrow \pi \left(y_i\right)\oplus 2^{i}L$; 7:  end for 8:  $PIC\leftarrow 2^{l-1}{X}_1\oplus 2^{l-2}{X}_2\oplus \cdots \oplus 2X_{l-1}\oplus X_l$; 9:  $\Sigma =\pi (PIC\oplus 2^{l-1}·3^{2}L)$; 10: $T=\pi (\Sigma \oplus y_l)\oplus 2^{l-1}·7L$; 11: return $\left(C_1\right|\left|C_2\right||\cdots ||C_l,T)$

Algorithm 11 Decryption algorithm $COPA-PIC\left[\pi \right].{\mathcal{D}}_K^N(A,C,T)$

Input:  Key K, nonce N, associated data A, ciphertext C, and authentication tag T; Output:  Plaintext M; 1: Partition C into $C_1\parallel \cdots \parallel C_l$, $|C_i|=n,1\le i\le l$; 2: $L=\pi \left(N\right|\left|K\right)$ and $y_0=T_A\oplus L$; 3: for $i=1$ to $i=l$ do 4:    $y_i\leftarrow {\pi }^{-1}(C_i\oplus 2^{i}L)$; 5:    $x_i=y_{i-1}\oplus y_i$; 6:    $M_i\leftarrow {\pi }^{-1}\left(x_i\right)\oplus 2^{i-1}·3L$; 7: end for 8: return  $M=M_1\left|\right|M_2\left|\right|\cdots \left|\right|M_l$

Algorithm 12 Verification algorithm $COPA-PIC\left[\pi \right].{\mathcal{V}}_K^N(A,C,T)$

Input:  Key K, nonce N, associated data A, ciphertext C, and authentication tag T; Output:  Success or failure $\top /\perp$; 1:  Partition C into $C_1\parallel \cdots \parallel C_l$, $|C_i|=n,1\le i\le l$; 2:  $L=\pi \left(N\right|\left|K\right)$ and $Y_0=T_A$; 3:  for $i=1$ to $i=l$ do 4:      $y_i\leftarrow {\pi }^{-1}(C_i\oplus 2^{i}L)$ and $Y_i=y_i\oplus 2^{i}L$; 5:  end for 6:  $PIC=2^{l-1}{Y}_0\oplus 3·2^{l-2}{Y}_1\oplus 3·2^{l-3}{Y}_2\oplus \cdots \oplus 3Y_{l-1}\oplus Y_l$; 7:  $\Sigma =\pi (PIC\oplus 2^{l-1}·3^{2}L)$; 8:  $T^{\prime }=\pi (\Sigma \oplus y_l)\oplus 2^{l-1}·7L$; 9:  if $T^{\prime }=T$ then 10:    return ⊤; 11: else 12:    return ⊥; 13: end if

For an INT-RUP security model with a permutation, the adversary is allowed to make ${\pi }^{\pm 1}$ queries in addition to the previous oracle queries; then, the INT-RUP-advantage of $\mathcal{A}$ against $\Pi =(\mathcal{E},\mathcal{D},\mathcal{V})$ is defined as

$$\begin{array}{c}\hfill Ad{v}_{\Pi }^{int-rup}\left(\mathcal{A}\right)=Pr[K\stackrel{\$}{\leftarrow }\mathcal{K}:{\mathcal{A}}^{{\mathcal{E}}_K,{\mathcal{D}}_K,{\mathcal{V}}_K;{\pi }^{\pm 1}}forges].\end{array}$$

Theorem 5

(INT-RUP security of COPA-PIC based on permutations). Let $\pi :{\{0,1\}}^n\to {\{0,1\}}^n$ be a public n-bit permutation and $\tilde{E}:\mathcal{K}\times \Gamma \times {\{0,1\}}^n\to {\{0,1\}}^n$ be a TBC, where $\mathcal{K}={\{0,1\}}^k$ is a key space, $\Gamma =\mathcal{N}\times \mathcal{I}\times \mathcal{J}$ is a tweak space, $\mathcal{N}={\{0,1\}}^{n-k}$ is a nonce space, $\mathcal{I}$ is a large-integer set, and $\mathcal{J}$ is a small-integer set. Assume that $2^i{3}^j\ne 1$ for all $(i,j)\in \mathcal{I}\times \mathcal{J}$. Let $\tilde{E}=MEM[\pi ,2^{\mathcal{I}}{3}^{\mathcal{J}}]$. For a nonce-misusing adversary $\mathcal{A}$, one has

$$\begin{array}{c}\hfill Ad{v}_{COPA-PIC\left[\pi \right]}^{int-rup}\left(\mathcal{A}\right)\le \frac{19{(\sigma +q)}^2}{2^n}+\frac{6(\sigma +q)p}{2^n}+\frac{p}{2^k}+\frac{(l+2){(q-1)}^2}{2^n}+\frac{2q_v}{2^n}.\end{array}$$

Proof. 

Similar to the proof of Theorem 4, the security proof includes two steps. First, COPA-PIC[$\pi$] is converted to COPA-PIC[$\tilde{E}$]. The dummy masks $\{3L,2·3L,\cdots ,2^{l-1}·3L,2^{l-1}·3^{2}L\}$ and $\{2L,2^{2}L,\cdots ,2^l·L,2^{l-1}·7L\}$ are introduced to the upper and lower layers of COPA-PIC[$\pi$], respectively, in terms of the MEM construction, where $L=\pi \left(N\right|\left|K\right)$. Therefore, distinct TBCs ${\tilde{E}}_K^{N,i,1},{\tilde{E}}_K^{N,i,2},{\tilde{E}}_K^{N,l,3}$, and ${\tilde{E}}_K^{N,l,4}$ are utilized to replace permutations with distinct masks, where $i=1,\cdots ,l$. For the permutation-based PMAC1, distinct TBCs ${\tilde{E}}_K^{N,i,5},{\tilde{E}}_K^{N,a,6}$, and ${\tilde{E}}_K^{N,a,7}$ are utilized to replace permutations with distinct masks, where $i=1,\cdots ,a-1$. According to Lemma 2 and the permutation-based PMAC1 [6], COPA-PIC[$\pi$] can be replaced with COPA-PIC[$\tilde{E}$], which together cost

$$\begin{array}{c}\hfill \frac{4.5{(2\sigma +2q)}^2}{2^n}+\frac{3(2\sigma +2q)p}{2^n}+\frac{p}{2^k}+\frac{{\sigma }^2}{2^n}=\frac{18{(\sigma +q)}^2}{2^n}+\frac{6(\sigma +q)p}{2^n}+\frac{p}{2^k}+\frac{{\sigma }^2}{2^n}.\end{array}$$

(7)

Then, combining Equation (7) and Theorem 3, the bound of Theorem 5 is obtained. □

5. Discussions and Future Works

COPA-PIC is a secure “rate-1/2” parallelizable delayed authenticated online cipher with nonce-misuse resistance. The structure of COPA-PIC is the same as that of COPA except that the authentication checksum is replaced with PIC. Therefore, COPA-PIC inherits all the advantages of COPA and calculates the authentication tag ahead of time in the verification oracle. It can be viewed as an instance of the generic B1 scheme introduced by Namprempre et al. [40]. At the beginning of the design, TBCs are used to improve COPA from the perspective of a top-level design, and the updating of the tweaks is as simple as possible. Then, by using the XEX* construction [6] and the MEM construction [22], provably secure block-cipher-based and permutation-based instances are presented. For the update of tweaks, a simple and efficient technique—point doubling is used to update tweaks. This technique follows the framework of the XEX* and MEM constructions, which makes proposed instances and proofs very simple. This paper considers the message whose length is a positive multiple of the block size n. In fact, for any length message, it also works.

There have been many studies on COPA in recent years [1,13,41,42]. Among them, the INT-RUP security is one of the most important research contents. COPA-PIC enjoys INT-RUP security up to the birthday bound in the nonce-misuse setting if the underlying primitive (including TBC, block cipher, and permutation) is secure. Of course, COPA-PIC just settles the problem of INT-RUP in the nonce-misuse setting, while the problem of privacy in the RUP setting still exists. It is left as an open problem to settle the privacy of COPA-PIC in the RUP setting.

COPA-PIC utilizes a new checksum technique—polynomial intermediate checksum (PIC)—to fix the INT-RUP security. PIC is a very vital technique which guarantees no information leakage and the same level between the plaintext and the ciphertext. In the AE schemes with PIC, the adversary cannot obtain any useful information to make a successful forgery even if given the additional power of access to an unverified decryption oracle. mCPFB with INT-RUP security combines a distance 4 error correcting code and delayed dislocation technique which is essentially a similar PIC technique. LOCUS and LOTUS are based on OCB and OTR, and their final checksum utilizes IC, which is a degenerated version of PIC.

Table 2. Comparison of AE modes with distinct checksum techniques.

Scheme	Security	Checksum Technique	Rate	Reference
OCB	INT-CTXT	PCC	1	[5,6,7]
CPFB	INT-CTXT	PCC	3/4	[11]
COPA	INT-CTXT	PCC	1/2	[8]
OCBt	tag-INT	PCC	1	[14]
OCB-IC	INT-RUP	IC	1/2	[9]
mCPFB	INT-RUP	similar PIC	3/4	[11]
COLM	INT-RUP	PIC	1/2	[13]
LOCUS	INT-RUP	IC	1/2	[15]
LOTUS	INT-RUP	IC	1/2	[15]
COPA-PIC	INT-RUP	PIC	1/2	This paper

shows the comparison of AE modes with distinct checksum techniques. Our work finds a new technique, PIC, and we believe that PIC can settle the INT-RUP security defects of any “rate < 1” and “Encryption-Mix-Encryption”-type checksum-based AE schemes. In addition, the mixing function of COLM (ELmE/ELmD) essentially provides an implementation of PIC for the authentication part, but COLM (ELmE/ELmD) also utilizes PCC in the authentication part. In fact, COLM (ELmE/ELmD) could have been designed entirely using PIC.

The proposed work is of high practical significance to establish a rapid feedback mechanism for third-party error authentication. The computational costs of COPA-PIC’s encryption and decryption algorithms are about the same as those of COPA, but the verification cost is close to one half of COPA (see Table 1). Thus, in practical applications, the receiver first verifies whether the received message is valid or not, and then determines whether to perform the next action (decrypt and obtain the correct plaintext or reject and return an error symbol). The proposed work supports Chakraborti et al.’s works and Zhang and Wu’s views, introduces a new intermediate checksum technique, PIC, and gives a possible direction for settling the security of all one-pass checksum-based AE schemes in the RUP setting. Recently, Andreeva et al. focused on SAEF which is a rate-1 online AE mode using a forkcipher as a building block, and they showed that SAEF is INT-RUP-secure up to the birthday bound by the H-coefficient technique [17]. Therefore, forkcipher is a hot future research direction. Additionally, there have been some achievements in RUP security for two-pass AE schemes in recent years, such as GCM-RUP [43] and its variant [44]. This is also a direction to watch in the future.