Cryptanalysis of the GGH cryptosystem

Abstract

In this correspondence, we show that partial information of plaintext can be used to simplify the decryption problem in the case of the GGH cryptosystem. Combined with Nguyens previous attack, we solve the numerical GGH challenge of the highest dimension 400, proposed on the Internet by the authors of the cryptosystem. We also discuss how to avoid this attack. © Birkhäuser Verlag Basel/Switzerland 2009.