Practical Yet Provably Secure Public-Key Primitives

New York University, New York NY

Investigators

Abstract

NSF Proposal 0310297 Practical yet Provably Secure Public-Key Primitives Victor Shoup This research addresses the fundamental building blocks, or primitives, of public-key cryptography, and attempts to design and analyze new primitives that improve the state of the art, either through increased efficiency or increased security. The objectives are to design new primitives suitable for publication in academic journals, as well as for submission to relevant standards bodies. The methods used include (1) the "reductionist" approach of modern cryptography, whereby the security of a scheme is formally reduced to the presumed intractability of well-studied mathematical problems (e.g., factoring), and (2) algorithmic techniques from number theory and algebra. Public-key cryptography plays an essential role in securing computers and communication networks. The two basic public-key primitives are public-key encryption and digital signatures. The first primitive allows a sender to secretly transmit a message to a receiver, where the sender only needs to know a public key (known to everyone), while only the receiver needs to know the corresponding secret key. The second primitive allows a signer, using a secret key, to generate a digital signature on a message so that the signature can later be verified by any party using a corresponding public key. Although substantial progress has been made in recent years on these problems, there is still more work to do, in terms of improving the efficiency of the schemes, reducing the strength of the intractability assumptions, improving the quality of the security reductions, and in developing practical distributed versions of these schemes so as to avoid a single point of failure. These are the specific tasks taken on by this research.