This paper presents a method for proving information-theoretic security of message authentication codes (MACs).
We choose MAC constructions that are not known to be tight: EWCDM proposed by Cogliati and Seurin (CRYPTO '16), DWCDM proposed by Datta~\textit{et al.} (CRYPTO '18) and 5 kinds of MACs including a two-permutation variant of nEHtM where the original nEHtM was proposed by Dutta {\it et al.} (EUROCRYPT '19) and 5 kinds of MACs were proposed by Chen {\it et al.} (ASIACRYPT '21).
By utilizing this method, we prove full $n$-bit security of several MACs, EWCDM, DWCDM, the variant of nEHtM, $F^{\text{EDM}}_{B_3}$, and $F^{\text{SoP}}_{B_3}$, in a nonce-respecting setting. Moreover, the variant of nEHtM and $F^{\text{SoP}}_{B_3}$ provides security when the number of queries with repeated nonces is upper bounded by $O(2^{n/8})$, improving the previous bound of $\frac{3n}{4}$-bit. To obtain those results, we generalize the Mirror theory for a wide range of $\xi_{\max}$ to apply to two-permutation-based constructions. Our approach is modular in the sense that MAC security can be obtained from PRF security, i.e., to the best of our knowledge, this is the first paper using Mirror theory but not using extended Mirror theory to prove MAC security of nonce-based MACs. Additionally, we present a matching forgery attack on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and a single verification query without using repeated nonces. As a result, we provide tightness results for all kinds of two-permutation-based MACs except $F^{\text{EDMD}}_{B_2}$.
이 논문은 메시지 인증 코드의 안전성을 증명하는 방법을 제시한다. 또한 정확한 안전성의 결과가 알려져 있지 않은 메시지 인증 코드 구조를 대상으로 안전성을 증명한다. 분석 및 증명 대상은 2016년 Cogliati와 Seurin에 의해 제안된 EWCDM, 2018년 Datta 등에 의해 제안된 DWCDM, 그리고 2021년 Chen 등이 분류한 5가지 메시지 인증 코드이다. 이 논문에서 제안한 방법론을 바탕으로 넌스가 재사용되지 않는다면, EWCDM, DWCDM, nEHtM의 변형, $F^{\text{EDM}}_{B_3}$, 그리고 $F^{\text{SoP}}_{B_3}$가 $n$ 비트 안전성을 가진다는 것을 증명하였다. 또한, nEHtM의 변형과 $F^{\text{SoP}}_{B_3}$는 넌스의 재사용 횟수가 $O(2^{n/8})$ 회를 넘지 않는다면 안전성이 이전의 증명 결과인 $\frac{3n}{4}$ 비트 안전성보다 높다는 것을 보였다. 이 안전성 결과를 얻기 위해, 넓은 범위의 $\xi_{\max}$에 대한 미러 이론을 두 치환을 사용한 구조에 적용할 수 있도록 일반화하였다. 또한 본 연구에서는 PRF 안전성을 사용하여 MAC 안전성을 증명하였다. 우리가 아는 한, 본 연구는 넌스 기반 메시지 인증 코드를 증명할때 확장된 미러 이론을 사용하지 않는 첫 번째 결과이다. 추가적으로, $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$에 대해 $O(2^{3n/4})$ 회의 MAC 질의와 한번의 검증 질의를 사용하는 공격을 제시하였다. 따라서, 이 두 구조가 $\frac{3n}{4}$ 비트의 정확한 안전성을 가진다는 것을 보였다. 결과적으로 $F^{\text{EDMD}}_{B_2}$를 제외한 두 치환을 기반으로 한 메시지 인증 코드의 정확한 안전성 결과를 제시하였다.
