Su-Jeong Choi (2006) Cryptanalysis of a Homomorphic Public-Key Cryptosystem.
Full text access: Open
The aims of this research are to give a precise description of a new homomorphic public-key encryption scheme proposed by Grigoriev and Ponomarenko [7] in 2004 and to break Grigoriev and Ponomarenko homomorphic public-key cryptosystem. Firstly, we prove some properties of linear fractional transformations. We analyze the X_n-representation algorithm which is used in the decryption scheme of Grigoriev and Ponomarenko homomorphic public-key cryptosystem and by these properties of the linear fractional transformations, we correct and modify the X_n-representation algorithm. We implement the modified X_n-representation algorithm by programming it and we prove the correctness of the modified X_n-representation algorithm. Secondly, we find an explicit formula to compute the X(n,S)-representations of elements of the group \Lambda_n. The X(n,S)-representation algorithm is used in the decryption scheme of Grigoriev and Ponomarenko homomorphic public-key cryptosystem and we modify the X(n,S)-representation algorithm. We implement the modified X(n,S)-representation algorithm by programming it and we justify the modified X(n,S)-representation algorithm. By these two modified X_n-representation algorithm and X(n,S)-representation algorithm, we make its decryption scheme more efficient. Thirdly, by using those properties of the linear fractional transformations, we design new X_1-representation algorithms I and II and we mainly use these two X_1-representation algorithms to break Grigoriev and Ponomarenko homomorphic public-key cryptosystem. We implement the algorithms by programming them and we prove the correctness of these two algorithms. Fourthly, we analyze Grigoriev and Ponomarenko homomorphic public-key cryptosystem and we give a clear description of Grigoriev and Ponomarenko scheme with a practical example. We also consider implementation issues for its practical applications. Lastly, we show several attack methods with examples and experiments according as the attack methods and so we break Grigoriev and Ponomarenko homomorphic public-key cryptosystem.
This is a Published version This version's date is: 21/09/2006 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/7f670a0b-4b00-da19-686b-70ce3eeb9d57/1/
Deposited by () on 12-Jul-2010 in Royal Holloway Research Online.Last modified on 13-Dec-2010
[1] S. Blackburn, and S. Galbraith, Cryptanalysis of two cryptosystems basedof group actions, Lecture Notes in Comput. Sci., 1716, 52–61, 1999.
[2] J.A. Buchmann, Introduction to cryptography, Springer, 2001.
[3] N. Ferguson, and B. Schneier, Practical cryptography, Wiley, 2003.
[4] J.B. Fraleigh, A first course in abstract algebra, Addison-Wesley, 1989.
[5] M.I. Gonzalez Vasco, and R. Steinwandt, A reaction attack on a public-keyencryption based on the word problem, Appl. Algebra Eng. Com. Comput.14(5), 335-340, 2004.
[6] D. Grigoriev, and I. Ponomarenko, Homomorphic public-key cryptosystemsand encrypting boolean circuits, arXiv:math.cs.CR/0301022, 2003.
[7] D. Grigoriev, and I. Ponomarenko, Homomorphic public-key cryptosystemsover groups and rings, Quaderni di Mathematica, vol. 13, 305-325, 2004.
[8] D. Grigoriev, and I. Ponomarenko, Constructions in public-key cryptographyover matrix groups, to appear in Contemporary Math. AMS.
[9] D.F. Holt, Handbook of computational group theory, Chapman &Hall/CRC, 2005.
[10] http://en.wikipedia.org.
[11] http://eprint.iacr.org/2005/070.pdf.
[12] http://mathworld.wolfram.com.
[13] http://www.ms.unimelb.edu.au/ cfm/notes/cgt-notes.pdf.308
[14] R.C. Lyndon, and P.E. Schupp, Combinatorial group theory, Springer-Verlag, 1977.
[15] R.A. Mollin, An introduction to cryptography, Chapman & Hall/CRC,2001.
[16] A.J. Menezes, P.C. van Oorschot and S.A. Vanstone, Handbook of appliedcryptography, CRC Press, 1997.
[17] M. Newman, Integeral matrices, Academic Press, 1972.
[18] B. Schneier, Applied cryptography, John Wiley & Sons, Inc, 1994.
[19] G.J. Simmons, Contemporary cryptology the science of information security,IEEE Press, 1992.
[20] R. Steinwandt, Loopholes in two public-key cryptosystems using the modular groups, Preprint Universitaet von Karlsruhe, 2000.
[21] D.R. Stinson, Cryptography theory and practice, Chapman & Hall/CRC,2006 .
[22] N. Wagner, and M. Magyarik, A public-key cryptosystem based on theword problem, Lecture Notes in Compt. Sci., 196, 19-36, 1985.
[23] A. Yamamura, Public-key cryptosystems using the modular groups, LectureNotes in Compt. Sci., 1431, 203-216, 1998.
[24] A. Yamamura, A functional cryptosystem using a group action, LectureNotes in Compt. Sci., 1587, 314-325, 1999.