Public key cryptosystems secure against memory leakage attacks

Shi-Feng Sun, Shuai Han, Dawu Gu, Shengli Liu

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)


The authors present a new general construction of public key encryption (PKE) based on the restricted subset membership (RSM) assumption, which can achieve the bounded-memory leakage resilient security and the auxiliary-input leakage resilient security simultaneously. The construction is BHHO-type, as Brakerski et al. work, but the message space is much larger and the proof is more concise benefiting from the RSM assumption. Instantiating the construction with the QR assumption, the authors get the first QR-based auxiliary-input secure PKE with a larger message space than {0,1}. Moreover, the authors generalise the Goldreich-Levin theorem to large rings. This theorem helps to improve the construction to achieve the same security level with fewer public parameters and shorter ciphertexts compared with Brakerski et al. work. For the bounded-memory leakage resilient security, the construction can achieve leakage rate of 1-o(1) and avoid the dependence between the message length and the amount of leakage. Based on the general construction, the authors also can achieve both bounded-memory leakage resilient chosen ciphertext attack (CCA) security and the auxiliary-input leakage resilient CCA security via the well-known Naor-Yung paradigm.

Original languageEnglish
Pages (from-to)403-412
Number of pages10
JournalIET Information Security
Issue number6
Publication statusPublished - 1 Nov 2016
Externally publishedYes

Cite this