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

doi:10.3969/j.issn.1671-1122.2016.06.005

Abstract

Abstract:

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.

Key words: elliptic curve cryptography(ECC), side channel attack, Grover algorithm, quantum intermediate encounter search algorithm

CLC Number:

TP309

Huihui JIA, Chao WANG, Jian GU, Zhen LU. Error Bit Correction of ECC Attack Based on Grover Quantum Intermediate Encounter Search Algorithm[J]. Netinfo Security, 2016, 16(6): 28-34.

Figures/Tables 2

References 23

[1]	MILLER V S.Use of Elliptic Curves in Cryptography[C]//International Association for Cryptologic Research (IACR). Advances in Cryptology-CRYPTO’85 Proceedings, August 18-22, 1985, Santa Barbara, California, USA. Berlin: Springer, 1986: 417-426.
[2]	DIFFIE W, HELLMAN M E.Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[J]. Computer, 1977, 10(6): 74-84.
[3]	MERKLE R, HELLMAN M E.On the Security of Multiple Encryption[J]. Communications of the Acm, 1981, 24(7): 465-467
[4]	FEYNMAN R P.Quantum Mechanical Compute[J]. Foundations of Physics, 1986, 16(6): 507-531.
[5]	DEUTSCH D.Quantum Theory: the Church. Turing Principle and Universal Quantum Computer[J].Proceedings of the Royal Society A Mathematical Physical & Engineering Sciences, 1985,400(1818): 97-117.
[6]	SHOR P W.Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. Quantum Entanglement & Quantum Information-ccast Workshop, 1999, 26(5): 1484-1509.
[7]	GROVER L K.A Fast Quantum Mechanical Algorithm for Database Search[C]//Association for Computing Machinery (ACM).The 28th ACM Symposium on Theory of Computation, May 29, 1996, Philadelphia, PA, USA. New York: ACM, 1996: 212-219.
[8]	钟普查,鲍皖苏. 三重DES的量子中间相遇搜索算法[J]. 科学通报,2009,54(19):3003-3007.
[9]	BIHAM E, BIHAM O.Grover’s Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution[J]. Physical Review A, 1999, 60(4): 2742-2745.
[10]	BIHAM E, BIHAM O.Analysis of Generalized Grover Quantum Search Algorithms Using Recursion Equations[J]. Physical Review A, 2001, 63(1): 5348-5353.
[11]	BULGER D, BAEITOMPA W P, WOOD G R.Implementing Pure Adaptive Search with Grover’s Quantum Algorithm[J]. Journal of Optimization Theory and Applications, 2003, 116(3): 517-529.
[12]	GROVER J K.Fixed-point Quantum Search[J]. Physical Review Letters, 2005, 95(15): 1-4.
[13]	YOUNES A.Fixed Phase Quantum Search Algorithm[J]. Applied Mathematics & Informationences, 2007, 7(1): 93-98.
[14]	DHAWAN S, PERKOWSKI M.Comparison of Influence of Two Data-encoding Methods for Grover Algorithm on Quantum Costs[C]//IEEE. 41st IEEE International Symposium on Multiple-Valued Logic, May 23-25, 2011, Tuusula, Finland. New Jersey: IEEE, 2011: 176-181.
[15]	LONG G L, LI Y S, ZHANG W L.Dominant Gate Imperfection in Grover’s Quantum Search Algorithm[J]. Physical Review A, 2000, 61(4): 042-305.
[16]	LONG Guilu, LI Yansong, XIAO Li, et al.Phase Matching in Quantum Searching and the Improved Grover Algorithm[J]. Nuclear Physics Review, 2004, 21(2):114-116.
[17]	HAO Liang, LIU Dan, LONG Guilu.An N/4 Fixed-point Duality Quantum Search Algorithm[J]. Science China, 2010, 53(9): 1765-1768.
[18]	仲明,贾徽徽,姜丽莹,等. 基于量子退火算法的DPA防御系统优化[J]. 信息网络安全,2016(2):28-33.
[19]	PAGE D.Theoretical use of Cache Memory as a Cryptanalytic Side-channel[J]. Journal of Arid Envrionments, 2002, 2002(10): 393-446.
[20]	KOCHER P, JAFFE J, JUN B.Differential Power Analysis[C]//International Association for Cryptologic Research (IACR) .19th Annual International Cryptology Conference Santa Barbara, August 15-19, 1999, California, USA. Heidelberg: Springer, 1999: 388-397.
[21]	石军. 电磁泄漏耦合发射的应用研究[J]. 信息网络安全,2015(9):101-105.
[22]	BRUMLEY B B, HAKALA R M.Cache-Timing Template Attacks[C]//International Association for Cryptologic Research (IACR). 15th International Conference on the Theory and Application of Cryptology and Information Security, December 6-10, 2009, Tokyo, Japan. Heidelberg: Springer, 1999: 667-684.
[23]	陈宇航,贾徽徽,姜丽莹,等. 基于Grover算法的ECC扫描式攻击[J]. 信息网络安全,2016(2):28-32.