Efficient variants of the GGH-YK-M cryptosystem - Barguil, João M. M.; Lino, Renan Yuri; Barreto, Paulo S. L. M. (Anais do Simpósio Brasileiro de Cibersegurança (SBSeg); 2014: Anais do XIV Simpósio Brasileiro de Segurança da Informação e de Sistemas ComputacionaisDO - 10.5753/sbseg.2014.20124, 2014)
The Goldreich-Goldwasser-Halevi scheme was deemed broken until recently proposed variants were shown to thwart all known attacks. However, the associated key sizes and generation times are notoriously inefficient. In this paper, we improve on the most promising such variant, proposed by Barros and Schechter and called GGH-YK-M, by reducing public key sizes rom O(n 2 lg n) down to O(n lg n) bits, and making key generation over 3 orders of magnitude faster than the results in the literature.