Paper 2018/846

Strong Leakage Resilient Encryption by Hiding Partial Ciphertext

Jia Xu and Jianying Zhou

Abstract

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 bounded leakage (e.g. 10000 bits) at anytime and anywhere and over anything. Our leakage threshold 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. 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.