Subjects: Mathematics >> Applied Mathematics submitted time 2022-10-12
Abstract:随机函数可逆性问题是密码学中一类重要的问题,例如Hash函数原像恢复,分组密码密钥恢复,离散对称问题求解等等。在这个工作中,我们将随机函数可逆性问题从一维推广到高维,并提出了一个新的广义生日碰撞原理。基于该原理,我们给出了多随机函数可逆性问题的一个求解算法。该算法可以解决1980年Hellman在分组密码TMTO攻击中只能使用一对明密文数据而不能使用多个数据的公开问题,以及Biryukov和Shamir在2000年提出的带BSW采样的TMDTO攻击中只能使用极其少量的明密文数据而不是全部数据的公开问题。
Peer Review Status:Awaiting Review
Subjects: Mathematics >> Applied Mathematics submitted time 2022-11-09
Abstract: In recent years, mixed integer linear programming (MILP, in short) is widely used to search differential characteristics and linear approximations with high probability and gradually becomes a powerful tool of automated cryptanalysis in symmetric ciphers. A key problem in the MILP method is how to fully characterize a set $S subseteq {0,1 }^n$ with as few linear integer inequalities $L$ as possible, which is called a full linear integer inequality characterization (FLIIC, in short) problem. In this work we establish a complete theory to solve the best solution of a FLIIC problem. We start from plain sets which can be characterized by exactly one linear integer inequality, and give their essential properties, including type, sparsity, degeneration, order, minimal and maximal element, norm and its bound, etc. Based on these essential properties, we further provide an efficient algorithm of solving a FLIIC problem with $S$, which can produce all minimal plain closures of $S$ and output a best FLIIC theoretically. As examples, we give their best solutions for differential properties of some common S-boxes used in block ciphers.
Peer Review Status:Awaiting Review