Issues of Provable Security
and Efficiency in
Cryptographic Constructions
Professor Rosario
Gennaro (T. J. Watson Research Center, New York) will teach a
postgraduate
course entitled Issues of Provable Security and Efficiency in
Cryptographic
Constructions. This course is supported by the Spanish Ministerio
de Educación y Ciencia
and is is a part of the Seminar on Mathematics
Applied to Cryptography.
Timetable
The course will be held from 1 to 9 July 2004. There will be eight
sessions:
- 1, 2, 5, 6, 7 ,8 ,9 July 2004, from 10 am to 12.30 pm.
- On monday 5 July 2004, from 3 pm to 6 pm, there will be a
special
session, in which the participants may present their current
research
in five minutes talks.
Location
Hall 005 in building C3 in the Campus
Nord of the Universitat
Politècnica de Catalunya
in Barcelona.
Topics
Modern Cryptography. Proofs of security by reduction. Construction of
cryptographic
algorithms from low-level mathematical objects. Black-box
constructions. One-way/trapdoor functions and permutations. Hard-core
bits.
Examples of black-box cryptographic constructions. Blum-Micali-Yao
pseudo-random number generator; Naor-Yung universal one-way
hashing; Goldwasser-Micali probabilistic encryption. Proof of security
and efficiency of these constructions.
Lower bounds on the efficiency of black-box constructions. Proof of the
optimality
of the above constructions.
How to improve efficiency. Using specific computational assumptions.
Commonly used assumptions: Discrete-log, Diffie-Hellman, Factoring,
RSA. Overview of existing schemes based on these assumptions.
Efficiency remains
close to black-box constructions. Improvements due only to more
efficient primitives (e.g. Blum-Blum-Shub generator
or Blum-Goldwasser encryption). Can we use specific assumptions to
obtain better algorithms?
Improved pseudo-random generation based on factoring and/or discrete
log
with short exponents. Improved signature schemes based on Strong RSA
Assumption. Paillier's encryption scheme (N-residuosity Assumption).
Open problems: Non-black-box constructions? New assumptions?
Back to
MAK's main page
Last Update: May 10, 2004