Paper Info
Title
An Enhanced Binary Characteristic Set Algorithm and Its Applications to Algebraic Cryptanalysis.
Abstract
Efficient methods to solve boolean polynomial systems underly the effectiveness of algebraic attacks on cryptographic ciphers and the security of multi-variate cryptosystems. Amongst various polynomial solving algorithms, the binary characteristic set algorithm was recently proposed to solve boolean polynomial systems including those arising from ciphers. In this paper, we propose some novel techniques to enhance the existing characteristic set solver. Specifically, we incorporate the ElimLin procedure and apply basic statistical learning techniques to improve the performance of the characteristic set algorithm. Our experiments show that our enhanced solver EBCSA performs better than existing algebraic methods on some ciphers, including CANFIL and PRESENT ciphers. We also perform the first algebraic cryptanalysis on the PRINCE cipher and an algebraic attack on Toyocrypt in a more practical/realistic setting as compared to previous attacks.
Year
Venue
Field
2017
ACNS
Wu's method of characteristic set,Cipher,Higher-order differential cryptanalysis,Polynomial,Piling-up lemma,Cryptography,Computer science,Algorithm,Theoretical computer science,Linear cryptanalysis,Solver
DocType
Citations 
PageRank 
Conference
0
0.34
References 
Authors
20
4
Name
Order
Citations
PageRank
Sze Ling Yeo1408.76
Zhen Li220917.82
Khoongming Khoo325023.29
Yu Bin Low400.34