UTCS Colloquium: Susan Hohenberger/Johns Hopkins University: "Short Signatures from Standard Assumptions" TAY 3.128, Friday, April 17, 2009 11:00 a.m.

Contact Name: 
Jenna Whitney
Apr 17, 2009 11:00am - 12:00pm

Type of Talk:  UTCS Colloquium


on:   Susan Hohenberger/John Hopkins University


; Friday, April 17, 2009  11:00

Location:  TAY 3.128

Host:  David Zuckerman

Talk Title:  "Short Sig

natures from Standard Assumptions"

Talk Abstract:

signatures are fundamental for modern authentication.  Currently, a

lmost all ``short'''' signatures rely on the random oracle heuristic or dep

end upon strong (and relatively new) complexity assumptions.  

In this talk, we present new short signature schemes in the standard model
(i.e., without random oracles) based upon the traditional RSA and Computa

tional Diffie-Hellman assumptions.

Our construction method takes
two different approaches.   First, we show how to realize the

se signatures in a stateful setting, where the signer must store and assoc

iate each signature with an index that represents how many signatures that

signer has issued up to that point.   In this setting, we real

ize two new short signature schemes under the RSA assumption and Computatio

nal Diffie-Hellman assumption in bilinear groups.

Next, we remo

ve the need for the signer to keep state, by developing a new proof techni

que that allows the simulator to predict a prefix of the message on which t

he adversary will forge, and then use this knowledge to embed the challeng

e.   In this setting, we develop a signature secure under the

RSA assumption, which requires only one element of Zn* and one integer.&nb

sp; We also provide an entirely new security analysis for the Waters signa

tures, which are secure under the CDH assumption in bilinear groups.

Speaker Bio:

Susan Hohenberger is an Assistant Professor at Johns Ho

pkins University.    She received a Ph.D. from MIT in 200

6, where she was advised by Ronald Rivest, and a B.S. from The Ohio State
University in 2000.   Prior to joining Hopkins, she completed
a post-doc at IBM Zurich Research.   Susan''s primary research
interests are in cryptography and computer security.   She is

a recipient of a 2008 Microsoft Research New Faculty Fellowship.