| 摘要: |
| 拓展的镜像理论是一种用于界定含有仿射等式和不等式方程组系统中未知数的可能解数的方法论,它在对称密码的可证明安全理论中发挥着重要的作用。论文再次聚焦拓展的镜像理论,着力解决一个关键挑战:为广泛参数范围内的仿射等式和不等式方程组系统中解数量建立鲁棒的下界估计。主要理论贡献体现在两大关键进展:首先,利用图论描述框架形式化地刻画了这些仿射系统固有的约束条件,为分析提供了直观且强大的视角。其次,基于这一图论视角,为广泛参数范围内的此类系统建立了一个全新且显著改进的解数量下界,为对称密码的普适抗生日界的严格证明奠定了理论基础。然后,应用到两类重要消息认证码——基于两个伪随机置换并联构造的方案EWCDMD和基于两个伪随机置换级联构造的方案EWCDM——的抗生日界安全性证明中,展示了增强的拓展的镜像理论的实际效力。利用拓展的镜像理论框架和广泛参数下的鲁棒下界,严格证明了EWCDMD和EWCDM均能达到抗生日界安全性。至关重要的是,推导出了一个广泛范围内均适用的普适安全界,证明了这两种构造均可提供2n/3比特普适安全性,其中n表示底层伪随机置换的比特长度。通过与以前的工作进行详细比较,凸显了该工作的独特优势和崭新贡献。最后,讨论了基于多个独立伪随机置换构造的抗生日界安全的消息认证码方案的安全性证明,并遗留了基于多变量拓展的镜像理论的图理论完善的开放性问题。 |
| 关键词: 拓展的镜像理论 消息认证码 图论 伪随机置换 抗生日界安全 |
| DOI：10.19363/J.cnki.cn10-1380/tn.2025.07.06 |
| Received:June 04, 2023Revised:September 07, 2023 |
| 基金项目:本课题得到国家自然科学基金青年基金“可调认证加密方案设计与分析”(No. 61902195)资助。 |
|
| Extended Mirror Theory and Its Applications in Message Authentication Codes |
| ZHANG Ping,QIN Jiaqi |
| School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210003, China |
| Abstract: |
| The extended mirror theory is a methodology for bounding the possible number of solutions for affine systems of equalities and non-equalities with unknowns. It plays an important role in the provable security theory of symmetric ciphers. This paper focuses on the extended mirror theory again and addresses the critical challenge of establishing robust lower bounds for the solution count of affine systems of equalities and non-equalities across a wide parameter range. Our primary theoretical contribution manifests in two key advancements: First, we formalize the inherent constraints of these affine systems using a graph-theoretic description, offering an intuitive and powerful lens for analysis. Second, leveraging this graphical perspective, we establish a new and significantly improved lower bound on the number of solutions applicable to a wide parameter range of system configurations, which lays a theoretical foundation for the strict proof of the universal beyond the birthday bound (BBB) of symmetric ciphers. Then, the robust lower bounds for the solution count of such systems across a wide parameter range are applied to the BBB-security proof of two prominent Message Authentication Code (MAC) constructions: EWCDMD based on the parallel construction of two pseudo-random permutations and EWCDM based on the cascading construction of two pseudo-random permutations, demonstrating the practical power of our enhanced extended mirror theory. Utilizing the extended mirror theory framework and robust lower bounds under a wide parameter range, we rigorously prove that both EWCDMD and EWCDM achieve BBB security. Crucially, we derive a universal security bound valid across a wide operational range, demonstrating that both constructions offer up to2n/3-bit universal security, where n is the bit length of the underlying pseudo-random permutation. Detailed comparisons with prior works highlight the distinct advantages and novel contributions of our work. Finally, the BBB-secure MACs based on multiple independent pseudorandom permutations are discussed, and an open problem improving graph-theoretic refinements based on multivariable extended mirror theory is left. |
| Key words: extended mirror theory message authentication code graph theory pseudorandom permutation beyond the birthday bound security |
