基于Grover量子中间相遇搜索算法的ECC攻击错误bit的修正

Error Bit Correction of ECC Attack Based on Grover Quantum Intermediate Encounter Search Algorithm

在现有的针对ECC的侧信道攻击中,密钥出现错误bit难以避免,且无法快速修正。文章将Grover量子搜索算法和中间相遇攻击相结合,提出了一种新的搜索算法——Grover量子中间相遇搜索算法,并将其应用于针对ECC的侧信道攻击中。该算法可以在O(N/M)^(1/2)步修正规模为N且存在M个错误bit的密钥,与传统搜索算法的计算复杂度O(N^(M+1))相比较,计算复杂度大幅度降低。通过对算法进行分析表明,该方法能够以成功率1修正ECC攻击中出现的错误bit。

The existing error bit in the side channel attacks of ECC is difficult to avoid, and can＇t be modified quickly. In this paper, a new search algorithm based on the Grover quantum search algorithm is proposed, which combines the Grover quantum search algorithm and the meet in the middle attack, and applies it to the side channel attack for ECC. The algorithm can solve the key problem of n which has M error bit in O（√N/M） steps. Compared with classical search algorithm, the computational complexity is greatly reduced. The analysis said that the success rate of modifying ECC attack error bit is 1, and the algorithm can effectively reduce the computational complexity.