基于代数技术的KECCAK算法分析及其相关代数问题研究

KECCAK is released as the third Secure Hash Algorithm (SHA-3) by NIST. After MD5 and SHA-1 has been attacked, SHA-3 will be the most important Hash algorithm in the next few years. The proposed project will study the preimage and collision attacks on KECCAK based on algebraic techniques. Specifically, the project will (1) study the detailed algebraic structures inside the KECCAK instances, and propose corresponding efficient algebraic algorithms for attacking these instances; (2) study some core algebraic problems, and propose hybrid methods which combine algebraic techniques and other techniques (e.g. MILP) to analysis cryptosystems; (3) achieve state-of-the-art performance on the preimage and collision attacks on KECCAK. The project is a cross-research on cryptology and mathematics. The innovations lie in that this project will study the nonlinear structures inside KECCAK and related techniques in more detail, and propose some new hybrid methods which combine algebraic techniques and other techniques, since the linear techniques cannot obtain satisfactory results at present. The project will promote the studies on KECCAK, and it will also improve and propose some new algebraic techniques, which are significant in both cryptology and mathematics.

KECCAK是NIST公布的最新Hash算法（SHA3）。在MD5与SHA1发现安全隐患后，SHA3将是未来最重要的Hash算法。本项目将基于代数技术对KECCAK的核心问题——原像和碰撞问题展开研究。包括：1）分析KECCAK不同实例的内部代数结构，研究有针对性的高效代数求解技术，降低攻击复杂度；2）研究一些关键代数问题，提出非线性代数技术与其他方法（如整数规划）相结合的新型分析方法，并应用于具体密码分析；3）在KECCAK原像与碰撞分析方面取得世界领先的成果。本项目是对信息与数学两个方向的交叉研究，创新点是在线性代数技术难有显著突破的情况下，项目将更为细致地研究KECCAK中特有的非线性代数结构及相关的求解技术，提出代数与其他方法结合的新型混合分析方法。本项目的研究不仅会显著推动对KECCAK的分析，还会改进和提出一些新型的代数求解技术，在密码学与数学两个领域都将产生重要的科学意义。

KECCAK是NIST公布的最新Hash算法（SHA3）。在MD5与SHA1发现安全隐患后，SHA3将是未来最重要的Hash算法。本项目基于代数技术对KECCAK的核心问题——原像和碰撞问题展开了研究。重点研究了：1）KECCAK不同实例的内部代数结构，研究有针对性的高效代数求解技术，降低攻击复杂度；2）一些关键代数问题，提出非线性代数技术与其他方法（如整数规划）相结合的新型分析方法，并应用于具体密码分析。本项目也取得了在KECCAK原像攻击方面世界领先的成果。本项目是对信息与数学两个方向的交叉研究，创新点是在线性代数技术难有显著突破的情况下，项目将更为细致地研究KECCAK中特有的非线性代数结构及相关的求解技术，提出代数与其他方法结合的新型混合分析方法。本项目的研究不仅会显著推动了对KECCAK的分析，还改进和提出一些新型的代数求解技术，在密码学与数学两个领域都将产生一定的科学意义。