Cryptanalysis of a Homomorphic Public-Key Cryptosystem
by Su-Jeong Choi
Abstract:
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.