Fully Leakage-Resilient Signatures
Speaker: Elette Boyle , MIT
Date: October 1 2010
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva
Host: Shafi Goldwasser, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
A signature scheme is {\em fully leakage resilient} (Katz and
Vaikuntanathan, ASIACRYPT '09) if it is existentially unforgeable
under an adaptive chosen-message attack even in a setting where an
adversary may obtain bounded (yet arbitrary) leakage information on
{\em all intermediate values that are used throughout the lifetime of
the system}. This is a strong and meaningful notion of security that
captures a significantly wide range of side-channel attacks.
One of the main challenges in constructing fully leakage-resilient
signature schemes is dealing with leakage that may depend on the
random bits used by the signing algorithm, and constructions of such
schemes are known only in the random-oracle model. Moreover, even in
the random-oracle model, known schemes are only resilient to leakage
of less than half the length of their signing key.
In this paper we construct the first fully leakage-resilient signature
schemes without random oracles. We present a scheme that is resilient
to any leakage of length $(1-o(1))L$ bits, where $L$ is the length of
the signing key. Our approach relies on generic cryptographic
primitives, and at the same time admits rather efficient
instantiations based on specific number-theoretic assumptions. In
addition, we show that our approach extends to the continual-leakage
model, recently introduced by Dodis, Haralambiev, Lopez-Alt and Wichs
(FOCS '10), and by Brakerski, Tauman Kalai, Katz and Vaikuntanathan
(FOCS '10). In this model the signing key is allowed to be refreshed,
while its corresponding verification key remains fixed, and the amount
of leakage is assumed to be bounded only in between any two successive
key refreshes.
See other events that are part of CIS Seminars 2010/2011
See other events happening in October 2010
