Cryptology ePrint Archive: Report 2021/658

A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem

Prastudy Fauzi and Martha Norberg Hovd and Håvard Raddum

Abstract: We present an adaptive key recovery attack on the leveled homomorphic encryption scheme suggested by Li, Galbraith and Ma (Provsec 2016), which itself is a modification of the GSW cryptosystem designed to resist key recovery attacks by using a different linear combination of secret keys for each decryption. We were able to efficiently recover the secret key for a realistic choice of parameters using a statistical attack. In particular, this means that the Li, Galbraith and Ma strategy does not prevent adaptive key recovery attacks.

Category / Keywords: public-key cryptography / Key recovery, somewhat homomorphic encryption, GSW, statistical attack

Original Publication (in the same form): PQCrypto 2021

Date: received 20 May 2021

Contact author: prastudy fauzi at gmail com, martha at simula no, haavardr at simula no

Available format(s): PDF | BibTeX Citation

Version: 20210520:203608 (All versions of this report)

Short URL: ia.cr/2021/658


[ Cryptology ePrint archive ]