Swarthmore College Department of Computer Science

Talk by Vadim Lyubashevsky, UC San Diego

Constructing an Efficient, Provably-Secure Digital Signature Scheme
Monday, January 28, 2008
4:00 pm in Science Center 240
Reception and refreshments from 3:45-4:00 pm

Abstract

Digital signature schemes are protocols that are used to sign electronic messages. Their security requires that messages can only be signed by someone in possession of a secret key, yet anyone should be able to verify the authenticity of a signed message. Such schemes play a vital role in securing internet communication.

In this talk I will describe a new provably-secure digital signature scheme in which the signing and verification operations have essentially linear-time complexity. The security of this scheme is based on the hardness of problems dealing with mathematical objects called lattices. Since no sub-exponential time algorithm for lattice problems is known, our construction gives a digital signature scheme with an almost optimal performance/security trade-off.