International Association
for Cryptologic Research

In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions $(P_1, \ldots, P_{q}) \in (\{0, 1\}^{n})^{q}$ satisfying a system of equations of the form $X_i \oplus X_j = \lambda_{i,j}$ such that $P_1, P_2, \ldots$, $P_{q}$ are pairwise distinct. This result is known as \emph{``$P_i \oplus P_j$ Theorem for any $\xi_{\max}$"} or alternatively as \emph{Mirror Theory for general $\xi_{\max}$}, which was later proved by Patarin in ICISC'05. Mirror theory for general $\xi_{\max}$ stands as a powerful tool to provide a high-security guarantee for many blockcipher-(or even ideal permutation-) based designs. Unfortunately, the proof of the result contains gaps that are non-trivial to fix. In this work, we present the first complete proof of the $P_i \oplus P_j$ theorem for a wide range of $\xi_{\max}$, typically up to order $O(2^{n/4}/\sqrt{n})$. Furthermore, our proof approach is made simpler by using a new type of equation, dubbed link-deletion equation, that roughly corresponds to half of the so-called orange equations from earlier works. As an illustration of our result, we also revisit the security proofs of two optimally secure blockcipher-based pseudorandom functions, and $n$-bit security proof for six round Feistel cipher, and provide updated security bounds.

In CRYPTO’21, Shen et al. proved that Two-Keyed-DbHtS construction is secure up to 22n/3 queries in the multi-user setting independent of the number of users. Here the underlying double-block hash function H of the construction realized as the concatenation of two independent n-bit keyed hash functions (HKh,1,HKh,2), and the security holds under the assumption that each of the n-bit keyed hash function is universal and regular. The authors have also demonstrated the applicability of their result to the key-reduced variants of DbHtS MACs, including 2K-SUM-ECBC, 2K-PMAC_Plus and 2K-LightMAC_Plus without requiring domain separation technique and proved 2n/3-bit multi-user security of these constructions in the ideal cipher model. Recently, Guo and Wang have invalidated the security claim of Shen et al.’s result by exhibiting three constructions, which are instantiations of the Two-Keyed-DbHtS framework, such that each of their n-bit keyed hash functions are O(2−n) universal and regular, while the constructions themselves are secure only up to the birthday bound. In this work, we show a sufficient condition on the underlying Double-block Hash (DbH) function, under which we prove an improved 3n/4-bit multi-user security of the Two-Keyed-DbHtS construction in the ideal-cipher model. To be more precise, we show that if each of the n-bit keyed hash function is universal, regular, and cross-collision resistant then it achieves the desired security. As an instantiation, we show that two-keyed Polyhash-based DbHtS construction is multi-user secure up to 23n/4 queries in the ideal-cipher model. Furthermore, due to the generic attack on DbHtS constructions by Leurent et al. in CRYPTO’18, our derived bound for the construction is tight.

In CRYPTO’02, Liskov et al. introduced the concept of a tweakable block cipher, a novel symmetric key primitive with promising applications. They put forth two constructions for designing such tweakable block ciphers from conventional block ciphers: LRW1 and LRW2. While subsequent efforts extended LRW2 to achieve security beyond the birthday bound (e.g., cascaded LRW2 in CRYPTO’12 by Landecker et al.), the extension of LRW1 remained unexplored until Bao et al.’s work in EUROCRYPT’20 that considered cascaded LRW1, a one-round extension of LRW1 - entailing masking the LRW1 output with the given tweak and re-encrypting it with the same block cipher. They showed that CLRW1 offers security up to 22n/3 queries. However, this result was challenged by Khairallah’s recent birthday bound distinguishing attack on cascaded LRW1, effectively refuting the security claim of Bao et al. Consequently, a pertinent research question emerges: How many rounds of cascaded LRW1 are required to obtain security beyond the birthday bound? This paper addresses this question by establishing that cascading LRW1 for four rounds suffices to ensure security beyond the birthday bound. Specifically, we demonstrate that 4 rounds of CLRW1 guarantees security for up to 23n/4 queries. Our security analysis is based from recent advancements in the mirror theory technique for tweakable random permutations, operating within the framework of the Expectation Method.

In CRYPTO 2019, Chen et al. have initiated an interesting research direction in designing PRF based on public permutations. They have proposed two beyond the birthday bound secure n-bit to n-bit PRF constructions, i.e., SoEM22 and SoKAC21, which are built on public permutations, where n is the size of the permutation. However, both of their constructions require two independent instances of public permutations. In FSE 2020, Chakraborti et al. have proposed a single public permutation based n-bit to n-bit beyond the birthday bound secure PRF, which they refer to as PDMMAC. Although the construction is minimal in the number of permutations, it requires the inverse call of its underlying permutation in their design. Coming up with a beyond the birthday bound secure public permutation based n-bit to n-bit PRF with a single permutation and two forward calls was left as an open problem in their paper. In this work, we propose pEDM, a single permutation based n-bit to n-bit PRF with two calls that do not require invertibility of the permutation. We have shown that our construction is secured against all adaptive information-theoretic distinguishers that make roughly up to 22n/3 construction and primitive queries. Moreover, we have also shown a matching attack with similar query complexity that establishes the tightness of our security bound.

In CRYPTO’16, Cogliati and Seurin proposed a block cipher based nonce based MAC, called Encrypted Wegman-Carter with Davies-Meyer (EWCDM), that gives 2n/3 bit MAC security in the nonce respecting setting and n/2 bit security in the nonce misuse setting, where n is the block size of the underlying block cipher. However, this construction requires two independent block cipher keys. In CRYPTO’18, Datta et al. came up with a single-keyed block cipher based nonce based MAC, called Decrypted Wegman-Carter with Davies-Meyer (DWCDM), that also provides 2n/3 bit MAC security in the nonce respecting setting and n/2 bit security in the nonce misuse setting. However, the drawback of DWCDM is that it takes only 2n/3 bit nonce. In fact, authors have shown that DWCDM cannot achieve beyond the birthday bound security with n bit nonces. In this paper, we prove that DWCDM with 3n/4 bit nonces provides MAC security up to O(23n/4) MAC queries against all nonce respecting adversaries. We also improve the MAC bound of EWCDM from 2n/3 bit to 3n/4 bit. The backbone of these two results is a refined treatment of extended mirror theory that systematically estimates the number of solutions to a system of bivariate affine equations and non-equations, which we apply on the security proofs of the constructions to achieve 3n/4 bit security.

Authenticated encryption schemes are usually expected to offer confidentiality and authenticity. In case of release of unverified plaintext (RUP), an adversary gets separated access to the decryption and verification functionality, and has more power in breaking the scheme. Andreeva et al. (ASIACRYPT 2014) formalized RUP security using plaintext awareness, informally meaning that the decryption functionality gives no extra power in breaking confidentiality, and INT-RUP security, covering authenticity in case of RUP. We describe a single, unified model, called AERUP security, that ties together these notions: we prove that an authenticated encryption scheme is AERUP secure if and only if it is conventionally secure, plaintext aware, and INT-RUP secure. We next present ANYDAE, a generalization of SUNDAE of Banik et al. (ToSC 2018/3). ANYDAE is a lightweight deterministic scheme that is based on a block cipher with block size n and arbitrary mixing functions that all operate on an n-bit state. It is particularly efficient for short messages, it does not rely on a nonce, and it provides maximal robustness to a lack of secure state. Whereas SUNDAE is not secure under release of unverified plaintext (a fairly simple attack can be mounted in constant time), ANYDAE is. We make handy use of the AERUP security model to prove that ANYDAE achieves both conventional security as RUP security, provided that certain modest conditions on the mixing functions are met. We describe two simple instances, called MONDAE and TUESDAE, that conform to these conditions and that are competitive with SUNDAE, in terms of efficiency and optimality.

In CRYPTO 2015, Cogliati et al. have proposed one-round tweakable Even-Mansour (\textsf{1-TEM}) cipher constructed out of a single $n$-bit public permutation $\pi$ and a uniform and almost XOR-universal hash function \textsf{H} as $(k, t, x) \mapsto \textsf{H}_k(t) \oplus \pi(\textsf{H}_k(t) \oplus x)$, where $t$ is the tweak, and $x$ is the $n$-bit message. Authors have shown that its two-round extension, which we refer to as \textsf{2-TEM}, obtained by cascading $2$-independent instances of the construction gives $2n/3$-bit security and $r$-round cascading gives $rn/r+2$-bit security. In ASIACRYPT 2015, Cogliati and Seurin have shown that four-round tweakable Even-Mansour cipher, which we refer to as \textsf{4-TEM}, constructed out of four independent $n$-bit permutations $\pi_1, \pi_2, \pi_3, \pi_4$ and two independent $n$-bit keys $k_1, k_2$, defined as $$k_1 \oplus t \oplus \pi_4(k_2 \oplus t \oplus \pi_3(k_1 \oplus t \oplus \pi_2(k_2 \oplus t \oplus \pi_1(k_1 \oplus t \oplus x)))), $$ is secure upto $2^{2n/3}$ adversarial queries. In this paper, we have shown that if we replace two independent permutations of \textsf{2-TEM} (Cogliati et al., CRYPTO 2015) with a single $n$-bit public permutation, then the resultant construction still guarrantees security upto $2^{2n/3}$ adversarial queries. Using the results derived therein, we also show that replacing the permutation $(\pi_4, \pi_3)$ with $(\pi_1, \pi_2)$ in the above equation preserves security upto $2^{2n/3}$ adversarial queries.

Encrypt-then-MAC (EtM) is a popular mode for authenticated encryption (AE). Unfortunately, almost all designs following the EtM paradigm, including the AE suites for TLS, are vulnerable against nonce misuse. A single repetition of the nonce value reveals the hash key, leading to a universal forgery attack. There are only two authenticated encryption schemes following the EtM paradigm which can resist nonce misuse attacks, the GCM-RUP (CRYPTO-17) and the $$\mathsf {GCM/2}^{+} $$ (INSCRYPT-12). However, they are secure only up to the birthday bound in the nonce respecting setting, resulting in a restriction on the data limit for a single key. In this paper we show that nEHtM, a nonce-based variant of EHtM (FSE-10) constructed using a block cipher, has a beyond birthday bound (BBB) unforgeable security that gracefully degrades under nonce misuse. We combine nEHtM with the CENC (FSE-06) mode of encryption using the EtM paradigm to realize a nonce-based AE, CWC+. CWC+ is very close (requiring only a few more xor operations) to the CWC AE scheme (FSE-04) and it not only provides BBB security but also gracefully degrading security on nonce misuse.

At CRYPTO 2016, Cogliati and Seurin have proposed a highly secure nonce-based MAC called Encrypted Wegman-Carter with Davies-Meyer ($$\textsf {EWCDM}$$EWCDM) construction, as $$\textsf {E}_{K_2}\bigl (\textsf {E}_{K_1}(N)\oplus N\oplus \textsf {H}_{K_h}(M)\bigr )$$EK2(EK1(N)⊕N⊕HKh(M)) for a nonce N and a message M. This construction achieves roughly $$2^{2n/3}$$22n/3 bit MAC security with the assumption that $$\textsf {E}$$E is a PRP secure n-bit block cipher and $$\textsf {H}$$H is an almost xor universal n-bit hash function. In this paper we propose Decrypted Wegman-Carter with Davies-Meyer ($$\textsf {DWCDM}$$DWCDM) construction, which is structurally very similar to its predecessor $$\textsf {EWCDM}$$EWCDM except that the outer encryption call is replaced by decryption. The biggest advantage of $$\textsf {DWCDM}$$DWCDM is that we can make a truly single key MAC: the two block cipher calls can use the same block cipher key $$K=K_1=K_2$$K=K1=K2. Moreover, we can derive the hash key as $$K_h=\textsf {E}_K(1)$$Kh=EK(1), as long as $$|K_h|=n$$|Kh|=n. Whether we use encryption or decryption in the outer layer makes a huge difference; using the decryption instead enables us to apply an extended version of the mirror theory by Patarin to the security analysis of the construction. $$\textsf {DWCDM}$$DWCDM is secure beyond the birthday bound, roughly up to $$2^{2n/3}$$22n/3 MAC queries and $$2^n$$2n verification queries against nonce-respecting adversaries. $$\textsf {DWCDM}$$DWCDM remains secure up to $$2^{n/2}$$2n/2 MAC queries and $$2^n$$2n verification queries against nonce-misusing adversaries.

SUM-ECBC (Yasuda, CT-RSA 2010) is the first beyond birthday bound (BBB) secure block cipher based deterministic MAC. After this work, some more BBB secure deterministic MACs have been proposed, namely PMAC_Plus (Yasuda, CRYPTO 2011), 3kf9 (Zhang et al., ASIACRYPT 2012) and LightMAC_Plus (Naito, ASIACRYPT 2017). In this paper, we have abstracted out the inherent design principle of all these BBB secure MACs and present a generic design paradigm to construct a BBB secure pseudo random function, namely Double-block Hash-then- Sum or in short (DbHtS). A DbHtS construction, as the name implies, computes a double block hash on the message and then sum the encrypted output of the two hash blocks. Our result renders that if the underlying hash function meets certain security requirements (namely cover-free and block-wise universal advantage is low), DbHtS construction provides 2n/3-bit security. We demonstrate the applicability of our result by instantiating all the existing beyond birthday secure deterministic MACs (e.g., SUM-ECBC, PMAC_Plus, 3kf9, LightMAC_Plus) as well as a simple two-keyed variant for each of them and some algebraic hash based constructions.

The security of a probabilistic Message Authentication Code (MAC) usually depends on the uniqueness of the random salt which restricts the security to birthday bound of the salt size due to the collision on random salts (e.g XMACR). To overcome the birthday bound limit, the natural approach to use (a) either a larger random salt (e.g MACRX3 uses 3n bits of random salt where n is the input and output size of the underlying non-compressing pseudorandom function or PRF) or (b) a PRF with increased domain size (e.g RWMAC or Randomized WMAC). Enhanced Hashthen- Mask (EHtM), proposed by Minematsu in FSE 2010, is the first probabilistic MAC scheme that provides beyond birthday bound security without increasing the randomness of the salt and the domain size of the non-compressing PRF. The author proved the security of EHtM as long as the number of MAC query is smaller than 22n/3 where n is the input size of the underlying non-compressing PRF. In this paper, we provide the exact security bound of EHtM and prove that this construction offers security up to 23n/4 MAC queries. The exactness is shown by demonstrating a matching attack.

At CRYPTO 2011, Yasuda proposed the PMAC_Plus message authentication code based on an n-bit block cipher. Its design principle inherits the well known PMAC parallel network with a low additional cost. PMAC_Plus is a rate-1 construction like PMAC (i.e., one block cipher call per n-bit message block) but provides security against all adversaries (under black-box model) making queries altogether consisting of roughly upto 22n/3 blocks (strings of n-bits). Even though PMAC_Plus gives higher security than the standard birthday bound security, with currently available best bound, it provides weaker security than PMAC for certain choices of adversaries. Moreover, unlike PMAC, PMAC_Plus operates with three independent block cipher keys. In this paper, we propose 1k-PMAC_Plus, the first rate-1 single keyed block cipher based BBB (Beyond Birthday Bound) secure (in standard model) deterministic MAC construction without arbitrary field multiplications. 1k-PMAC_Plus, as the name implies, is a simple one-key variant of PMAC_Plus. In addition to the key reduction, we obtain a higher security guarantee than what was proved originally for PMAC_Plus, thus an improvement in two directions.