A Wu‘s Method Based Parallelization Design and Implementation for Algebraic Cryptanalysis

Abstract:

Wus method is one of the effective methods for solving large-scale polynomial equation systems in algebraic cryptanalysis. But it will take a lot of time to solve polynomial equations with a serial algorithm of Wu’s method. In order to eliminate the bottleneck of computing time overheads, we proposes an efficient data parallelization scheme based on Wu‘s method. And a load balance mechanism applied to our scheme, which greatly improves computing-performance of Wu’s method and enhances its ability to meet challenges of algebraic cryptanalysis.

• Periodical: Applied Mechanics and Materials (Volumes 530-531)
• Pages: 641-645
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.530-531.641
• Online since: February 2014
• Authors: Huai Zhe Zhou, Hai He Ba, Jiang Chun Ren*, Tao Xie, Min Zhu, Song Zhu Mei
• Keywords: Algebraic Cryptanalysis, Load Balance, Parallel Computing, Wu’s Method

References

[1] XS Gao, ZY Huang. Efficient Characteristic Set Algorithms for Equation Solving in Finite Fields and Application in Analysis of Stream Ciphers[J]. IACR Cryptology ePrint Archive, 2009, 2009: 637.

[2] PWang. Parallel polynomial operations on SMPs: An overview. Journal of Symbolic Computation, 2001, 11(1): 377-396.

[3] Rayes M, PWang. Parallel GCD for sparse multivariate polynomials on shared memory multiple processors. In: Proc. of thePASCO'96. Washington: IEEE Press, 1996. 326-335.

[4] Ajwa I, PWang. Applying parallel/distributed computing to advanced algebraic computations. In: Proc. of the 1997 IEEE NationalAerospace and Electronics Conf. Washington: IEEE Press, 1997. 156-164.

DOI: 10.1109/naecon.1997.617775

[5] DM Wang. On the Parallelization of Characteristic - Set - BasedAlgorithms［C］. Proceedings of the First International ACPC Conferencem, LNCS 591, Springer -Verlag, Berlin Heidelberg, 1991: 338 - 349.

[6] YWWu, GWYang, Lin DD. On the parallel computation for characteristic set method[J]. Journal of Electronics, 2004, 18(3): 383-388, In Chinese.

[7] YWWu, GWYang, HYang. A Distributed Computing Model for Wu's Method[J]. Journal of Software, 2005, 16(3): 384-391, In Chinese.

[8] Gregory V. Bard, Algebraic Cryptanalysis, Springer, (2009).

[9] Courtois N T, Meier W. Algebraic attacks on stream ciphers with linear feedback[A]. Biham E. Advances in Cryptology- Eurocrypt 2003[C]. Berlin: IACR2003, 2003. 345-359.

DOI: 10.1007/3-540-39200-9_21

[10] Ritt, J.F. Differential algebra, Amer. Math. Soc. Colloquium(1950).

[11] W T Wu. A Mechanization Method of Geometry and Its Applications [J]. I . Distances, Areas, and Volumes, J. Sys. Sci. & Math. Scis., 6 , 1986: 204 － 216.