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

Prastudy Fauzi; Martha Norberg Hovd; Håvard Raddum

Paper 2021/658 Original: eprint.iacr.org/2021/658 ↗

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

Prastudy Fauzi

Martha Norberg Hovd

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2021-11-16: last updated; 2021-05-20: published
Short URL: https://ia.cr/2021/658
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2021/658,
      author = {Prastudy Fauzi and Martha Norberg Hovd and Håvard Raddum},
      title = {A Practical Adaptive Key Recovery Attack on the LGM (GSW-like) Cryptosystem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/658},
      year = {2021},
      url = {https://eprint.iacr.org/2021/658}
}