Distributed Public Key Schemes Secure against Continual Leakage [Extended Abstract]

In this work we study distributed public key schemes secure against continual memory leakage. The secret key will be shared among two computing devices communicating over a public channel, and the decryption operation will be com-puted by a simple 2-party protocol between the devices. Similarly, the secret key shares will be periodically refreshed by a simple 2-party protocol executed in discrete time peri-ods throughout the lifetime of the system. The leakage ad-versary can choose pairs, one per device, of polynomial time computable length shrinking (or entropy shrinking) func-tions, and receive the value of the respective function on the internal state of the respective device (namely, on its se-cret share, internal randomness, and results of intermediate computations). We present distributed public key encryption (DPKE) and distributed identity based encryption (DIBE) schemes that are secure against continual memory leakage, under the Bi-linear Decisional Diffie-Hellman and 2-linear assumptions. Our schemes have the following properties: 1. Our DPKE and DIBE schemes tolerate leakage at all times, including during refresh. During refresh the tol-erated leakage is a (1/2 − o(1), 1)-fraction of the se-cret memory of P1, P2 respectively; and at all other times (post key generation) the tolerated leakage is a ((1 − o(1)), 1)-fraction of the secret memory of P1, P2 respectively. 2. Our DIBE scheme tolerates leakage from both themas-ter secret key and the identity based secret keys