Paper 2018/846

Strong Leakage Resilient Encryption: Enhancing Data Confidentiality by Hiding Partial Ciphertext

Jia Xu and Jianying Zhou


Leakage-resilient encryption is a powerful tool to protect data confidentiality against side channel attacks. In this work, we introduce a new and strong leakage setting to counter backdoor (or Trojan horse) plus covert channel attack, by relaxing the restrictions on leakage. We allow \emph{bounded} leakage at \emph{anytime} and \emph{anywhere} and over \emph{anything}. Our leakage threshold (e.g. 10000 bits) could be much larger than typical secret key (e.g. AES key or RSA private key) size. Under such a strong leakage setting, we propose an efficient encryption scheme which is semantic secure in standard setting (i.e. without leakage) and can tolerate strong continuous leakage. We manage to construct such a secure scheme under strong leakage setting, by hiding partial (e.g. $1\%$) ciphertext as secure as we hide the secret key using a small amount of more secure hardware resource, so that it is almost equally difficult for any adversary to steal information regarding this well-protected partial ciphertext or the secret key. We remark that, the size of such well-protected small portion of ciphertext is chosen to be much larger than the leakage threshold. We provide concrete and practical examples of such more secure hardware resource for data communication and data storage. Furthermore, we also introduce a new notion of computational entropy, as a sort of computational version of Kolmogorov complexity. Our quantitative analysis shows that, hiding partial ciphertext is a powerful countermeasure, which enables us to achieve higher security level than existing approaches in case of backdoor plus covert channel attacks. We also show the relationship between our new notion of computational entropy and existing relevant concepts, including Shannon-Entropy, Yao-Entropy, Hill-Entropy, All-or-Nothing Transform, and Exposure Resilient Function. This new computation entropy formulation may have independent interests.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. International Journal of Information Security
Leakage Resilient EncryptionSecret SharingInformation Dispersal AlgorithmInformation-theoretic securitySide Channel AttackCovert Channel AttackSubliminal channelKolmogorov complexity
Contact author(s)
jiaxu2001 @ gmail com
2020-06-08: last of 2 revisions
2018-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jia Xu and Jianying Zhou},
      title = {Strong Leakage Resilient Encryption: Enhancing Data Confidentiality by Hiding Partial Ciphertext},
      howpublished = {Cryptology ePrint Archive, Paper 2018/846},
      year = {2018},
      doi = {10.1007/s10207-020-00487-7},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.