Masked Even–Mansour (MEM) is a tweakable construction proposed at EUROCRYPT 2016 for usage in authenticated encryption schemes. This paper investigates the quantum security of MEM, highlighting the threat of quantum computing in applications, i.e., multi-user networks. In the single-key scenario, an attack on MEM using only known-plaintext classical queries is developed by exploiting the randomness inherent in tweaks. In the multi-key scenario, we explore general attacks and emphasize that it is costly to recover all keys if correlations between users cannot be established. To solve it, we draw on the giant component theorem and propose the first known-plaintext attack on MEM. The trade-offs between data per user (D), offline time (T), and the number of users (W) are <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4781_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="91" /> </InlineMediaObject> <EquationSource Format="TEX">$W\cdot D^{2}=2^{n}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>W</mi> <mo>·</mo> <msup> <mi>D</mi> <mn>2</mn> </msup> <mo>=</mo> <msup> <mn>2</mn> <mi>n</mi> </msup> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="11128_2025_4781_Article_IEq2.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="150" /> </InlineMediaObject> <EquationSource Format="TEX">$T\cdot {(D\cdot W)^{1/6}}=2^{n/2}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>·</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mo>·</mo> <mi>W</mi> <mo stretchy="false">)</mo> </mrow> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>6</mn> </mrow> </msup> <mo>=</mo> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> </mrow> </math></EquationSource> </InlineEquation>. The result holds significance as it is developed under a realistic known-plaintext setting, providing great flexibility in terms of W and T. We also provide a memory-efficient multi-key attack on MEM. As applications, various attacks on OPP and Elephant (a third-round candidate of NIST-LWC) are proposed. For the same number of users, our attacks have a lower time complexity compared to the general bound, confirming the power and value of quantum attacks presented in this paper.

(Multi-key) quantum analysis of Masked Even–Mansour with applications to offset public permutation and elephant

期刊论文
发表日期：

2025年6月9日

查看全文

Tairong Shi,
Wenling Wu,
Lin Ding,
Sengpeng Wang,
Mengyuan Zhang,
Bin Hu,
Jie Guan

摘要

Masked Even–Mansour (MEM) is a tweakable construction proposed at EUROCRYPT 2016 for usage in authenticated encryption schemes. This paper investigates the quantum security of MEM, highlighting the threat of quantum computing in applications, i.e., multi-user networks. In the single-key scenario, an attack on MEM using only known-plaintext classical queries is developed by exploiting the randomness inherent in tweaks. In the multi-key scenario, we explore general attacks and emphasize that it is costly to recover all keys if correlations between users cannot be established. To solve it, we draw on the giant component theorem and propose the first known-plaintext attack on MEM. The trade-offs between data per user (D), offline time (T), and the number of users (W) are $W\cdot D^{2}=2^{n}$ $W \cdot D^{2} = 2^{n}$ and $T\cdot {(D\cdot W)^{1/6}}=2^{n/2}$ $T \cdot {(D \cdot W)}^{1 / 6} = 2^{n / 2}$ . The result holds significance as it is developed under a realistic known-plaintext setting, providing great flexibility in terms of W and T. We also provide a memory-efficient multi-key attack on MEM. As applications, various attacks on OPP and Elephant (a third-round candidate of NIST-LWC) are proposed. For the same number of users, our attacks have a lower time complexity compared to the general bound, confirming the power and value of quantum attacks presented in this paper.