Abstract models of computation and complexity lower bounds
Speaker: Ueli Maurer , ETH - Zurich
Date: May 1 2007
Time: 4:00PM to 5:15PM
Location: 32-G449 Patil/Kiva, Stata Ctr
Host: Madhu Sudan, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html[Note UNUSUAL TIME: 4pm. Refreshments at 3:40pm]
Computational security proofs in cryptography, without unproven
intractability assumptions, exist today only if one restricts the
computational model. For example, one can prove a lower bound on the
complexity of computing discrete logarithms in a cyclic group if one
considers only generic algorithms which can not exploit the properties
of the representation of the group elements. A simple abstract model
of computation is proposed which allows to capture such reasonable
restrictions on the power of algorithms. Several instantiations of
the model and the corresponding lower bounds are discussed, including
different flavors of generic algorithms in groups.
See other events that are part of Theory Colloquium Spring 2007
See other events happening in May 2007
