Division Property: Efficient Method to Estimate Upper Bound of Algebraic Degree

We proposed the division property, which is a new method to find integral characteristics, at EUROCRYPT2015. Then, we applied this technique to analyze the full MISTY1 at CRYPTO2015. After the proposal of the two papers, many follow-up results have been researched at major conferences. In this paper, we first expound the integral and higher-order differential cryptanalyses in detail and focus the similarities and differences. As a result, we conclude that both cryptanalyses are the same in practical. Nevertheless, both cryptanalyses use the different method to find characteristics: the propagation characteristic of integral properties is evaluated in the integral cryptanalysis and the upper bound of the algebraic degree is evaluated in the higher-order differential cryptanalysis. Our first discovery is that each of the two methods has its own advantages and disadvantages. Moreover, there are some experimental characteristics that cannot be proven by either of both methods. These observation causes significant motivation that we developed the division property. We next expound some important follow-up results, e.g., the bit-based division property at FSE2016, the parity set at CRYPTO2016, the MILP-based propagation search at ASIACRYPT2016.