Practical public key encryption with continual leakage resilience

Abstract

Public key encryption is an essential cryptographic primitive, which is usually used to confidentially convey messages under a public/insecure communication environment. Meanwhile, it is also a significant building block of various physical applications, such as storing private data over the cloud platform, performing private computations over different database, proving the transaction data over the blockchain, and so on. However, a public key encryption framework that follows the traditional and standard security definition will be broken by the side-channel attacks, because the adversary indeed could obtain some information of the internal secret state (e.g., the secret key). This thesis studies the constructions of public key encryption with continual leakage resilience under different security model.

Our first construction is about leakage-resilient signature (LR-Sig) schemes, in which the secret key can be leaked to the adversary information-theoretically. Apart from the leakage of the secret key, we also admit the leakage of the signing randomness. In particular, the public key and the ciphertext of our LR-Sig schemes remain the same as the original schemes. Thereby, our framework can be easily embedded in related applications, such as the LR-ECDSA over the blockchain. Meanwhile, our LR-Sig obtains the shortest signature-size, without involving any commitment scheme or non-zero knowledge proof. Besides, the secret key can be refreshed periodically, achieving the first LR-Sig that is resilient to the continual memory leakage with auxiliary inputs.

Our second construction is about leakage-resilient public key encryption (LR-PKE). We begin by devising a useful tool called hash proof system with auxiliary inputs $(\HPSAI)$. After that, via the $\HPSAI$, we derive the first LR-PKE with an optimal leakage ratio ($1-0(1)$) in the auxiliary input model, without using the pairing operations and composite order group. Moreover, our LR-PKE is secure against the chosen-ciphertext attack (CCA).

Our third construction is about leakage-resilient identity-based encryption (LR-IBE). The most important feature is that the security reduction is independent of the number of the challenge ciphertexts and users, deriving the first tight LR-IBE. Our CCA-secure LR-IBE not only allows the leakage of the secret key, but also the leakage of the master secret key, which is not achieved in most existing works. By updating both secret keys, we devise the first CCA-secure LR-IBE that is resilient to the continual memory leakage with the bound leakage model and the ciphertext size is a small constant. Furthermore, we obtain the first tightly CCA-secure LR-PKE with the unbounded leakage of the secret key during the life span of the public key.