Evervault Papers

Crypto means cryptography

The most important cryptography papers spanning the past, present, and future of cryptosystems & cryptology.

Non-Malleable Cryptography

Danny Dolev, Cynthia Dwork, & Moni Naor

On the (Im)possibility of Obfuscating Programs

Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, & Ke Yang

Computer Systems Established, Maintained and Trusted by Mutually Suspicious Groups

David L. Chaum

A Digital Signature Based on a Conventional Encryption Function

Ralph C. Merkle

The Knowledge Complexity of Interactive Proof-Systems

Shafi Goldwasser, Silvio Micali, & Charles Rackoffero

Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security

Matt Blaze, Whiteld Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, & Michael Wiener

CryptDB: Protecting Confidentiality with Encrypted Query Processing

Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, & Hari Balakrishnan

Protocols for Secure Computations

Andrew C. Yao

Bitcoin: A Peer-to-Peer Electronic Cash System

Satoshi Nakamoto

A fully homomorphic encryption scheme

Craig Gentry

On Data Banks and Privacy Homomorphisms

Ronald L. Rivest, Len Adleman, & Michael L. Dertouzos

A fast quantum mechanical algorithm for database search

Lov K. Grover

A fast quantum mechanical algorithm for database search

Lov K. Grover — Published May 1996

In A fast quantum mechanical algorithm for database search, Grover provided an algorithm that is threatening to industry-standard symmetric cryptography, like the Advanced Encryption Standard (AES).

Grover’s algorithm can find the input of a black box function, given its output, to a high probability in O(√n) time. Grover’s algorithm is asymptotically optimal. That is, Grover’s algorithm helps quantum computers search possible permutations as fast as is theoretically possible.

The consequence of Grover’s algorithm on industry-standard symmetric cryptosystems is that an attack utilizing Grover’s algorithm would reduce the security of AES-256 to the equivalent security of AES-128.

The general rule of thumb for designing schemes which are resistant to attacks through Grover’s algorithm is to simply double the bit size of the scheme (i.e. use AES-256 instead of AES-128) as Grover’s algorithm can be used to crack a 256-bit scheme in 2^128 iterations rather than 2^256.

Download PDF

See all Papers