Paper 2014/159

Weak-Key Leakage Resilient Cryptography

Zuoxia Yu, Qiuliang Xu, Yongbin Zhou, Chengyu Hu, Rupeng Yang, and Guangjun Fan

Abstract

In traditional cryptography, the standard way of examining the security of a scheme is to analyze it in a black-box manner, capturing no side channel attacks which exploit various forms of unintended information leakages and do threaten the practical security of the scheme. One way to protect against such attacks aforementioned is to extend the traditional models so as to capture them. Early models rely on the assumption that only computation leaks information, and are incapable of capturing memory attacks such as cold boot attacks. Thus, Akavia et al.(TCC '09) formalize the general model of key-leakage attacks to cover them. However, most key-leakage attacks in reality tend to be weak key leakage attacks which can be viewed as a nonadaptive version of the key-leakage attacks. Powerful as those may be, the existing constructions of cryptographic schemes in adaptive key-leakage attacks model still have some drawbacks such as they are quite inefficient or they can only tolerate a small amount of leakage. Therefore, we mainly consider models that cover weak key-leakage attacks and the corresponding constructions in them. We extend the transformation paradigm presented by Naor and Segev that can transform from any chosen-plaintext secure public-key encryption (PKE) scheme to a chosen-plaintext weak key-leakage secure PKE scheme. Our extensions are two-fold. Firstly, we extend the paradigm into chosen-ciphertext attack scenarios and prove that the properties of it still hold in these scenarios. We also give an instantiation based on DDH assumption in this setting. Additionally, we extend the paradigm to cover more side channel attacks under the consideration of different types of leakage functions. We further consider attacks which require the secret key still has enough min-entropy after leaking and prove the original paradigm is still applicable in this case with chosen-ciphertext attacks. Attacks that require the secret key is computationally infeasible to recover given the leakage information are taken into consideration as well. And we formalize the informal discusses by Naor and Segev in (Crypto' 09) on how to adapt the original paradigm in this new models.