Isamu Teranishi

Signatures Resilient to Continual Leakage on Memory and Computation

AUTHORS: Tal Malkin and Isamu Teranishiy and Yevgeniy Vahlis and Moti Yung

 Recent breakthrough results by Brakerski et.al. and Dodis et.al.  have
shown that signature schemes can be made secure even if the adversary
 continually obtains information leakage from the secret key of the
scheme. However, the schemes currently do not allow leakage on the
secret key and randomness during signing, except in the random
oracle model. Further, the random oracle based schemes require updates to
the secret key in order to maintain security, even when no leakage
during computation is present.

We present the first signature scheme that is resilient to full continual
leakage: memory leakage as well as leakage from processing during
signing (both from the secret key and the randomness), in
key generation, and in update.
Our scheme can tolerate leakage of a 1-o(1) fraction of the secret
key between updates, and is proven secure in the standard model based
on the symmetric external DDH  (SXDH) assumption in bilinear groups.
The time periods between updates are a function of the amount of
leakage in the period (and nothing more).

Our construction makes new use of the Groth-Sahai proof systems, and in
particular avoids composing proofs, which gives improved efficiency. In
addition, we introduce a new tool: independent pre-image resistant hash
functions, which may be of independent interest.