SPEAKER:
Shabsi Walfish
NYU

TITLE: 
Perfectly Secure Password Protocols in the Bounded Retrieval Model


ABSTRACT:
We introduce a formal model, which we call the Bounded Retrieval
Model, for the design and analysis of cryptographic protocols
remaining secure against intruders that can retrieve a limited amount
of parties' private memory. The underlying model assumption on the
intruders' behavior is supported by real-life physical and logical
considerations, such as the inherent superiority of a party's local
data bus over a remote intruder's bandwidth-limited channel, or the
detectability of voluminous resource access by any local
intruder. More specifically, we assume a fixed upper bound on the
amount of a party's storage retrieved by the adversary. Our model
could be considered a non-trivial variation of the well-studied
Bounded Storage Model, which postulates a bound on the amount of
storage available to an adversary attacking a given system.  

In this model we study perhaps the simplest among cryptographic tasks:
user authentication via a password protocol. Specifically, we study
the problem of constructing efficient password protocols that remain
secure against offline dictionary attacks even when a large (but
bounded) part of the storage of the server responsible for password
verification is retrieved by an intruder through a remote or local
connection. We show password protocols having satisfactory performance
on both efficiency (in terms of the server's running time) and
provable security (making the offline dictionary attack not
significantly stronger than the online attack). We also study the
tradeoffs between efficiency, quantitative and qualitative security in
these protocols. All our schemes achieve perfect security (security
against computationally-unbounded adversaries). Our main schemes
achieve the interesting efficiency property of the server's lookup
complexity being much smaller than the adversary's retrieval bound. 

Joint work with G. Di Crescenzo and R. Lipton