Cryptography Against Continual Memory Leakage
Yael Tauman Kalai, Jing Chen · 2011
Recall from last lecture that we have several ways to model leakage. One model is “only computation leaks ” by Micali and Reyzin [11], which assumes a form of secure memory that does not leak as long as no computation is done on the data. Another one is “memory leakage ” by Akavia, Goldwasser, and Vaikuntanathan [1], which assumes that everything can leak information. From an orthogonal dimension we can talk about bounded leakage and continual leakage, where the former assumes that leakage is just one shot, while the latter allows leakage to happen repeatedly during computation. The table below summarizes all four possible combinations of leakage models. only computation leaks memory leakage This combination is not Most previous work falls in bounded really meaningful. this model, e.g., [1, 12, 2, 9]. continual E.g., [8] E.g., [4], which we will discuss today. In last two lectures we have studied bounded memory leakage, and today we are going to study continual memory leakage. In particular, we are going to discuss signature schemes and encryption schemes that are secure against continual memory leakage —CML from now on. 2 Definition of Security Against CML Let us start by defining public-key encryption schemes that are secure against CML. Definition 1. A public-key encryption scheme E is said to be semantically secure against CML if, ∀ PPT adversary A, the advantage of A against challenger Ch in the following game is negligible (in the security parameter n): A