## Crypto means cryptography

# Evervault Papers

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

#### La Cryptographie Militaire

Auguste Kerckhoffs — Published January 1883

This paper is the origin of **Kerckhoffs’ Principle** which states that the security of a cryptosystem must lie in the choice of its keys only; everything else (including the algorithm itself) should be considered public knowledge.

The corollary of Kerckhoffs’ Principle is that a developer should *only* use cryptosystems about which everything is known. This is a first principle for us at Evervault.

###### A Mathematical Theory of Cryptography

#### A Mathematical Theory of Cryptography

Claude E. Shannon — Published September 1945

In 1948, Claude E. Shannon published the paper A Mathematical Theory of Communication, which is seen as the foundation of modern information theory.

In 1949, Shannon published Communication Theory of Secrecy Systems which relates cryptography to information theory, and should be seen as the foundation of modern cryptography.

Both papers derive from a technical report, A Mathematical Theory of Cryptography, written by Shannon in 1945. In this report, Shannon defined, and mathematically proved, perfect secrecy.

###### Cramming more components onto integrated circuits

#### Cramming more components onto integrated circuits

Gordon Moore — Published April 1965

This paper is the origin of what has become known as Moore’s Law, which states that the number of transistors on integrated circuits doubles approximately every two years. Moore’s Law is directly related to other aspects of progress in computing, including processing speed, product price, and memory capacity.

Cryptographic algorithms are all vulnerable to brute force–trying every possible encryption key, systematically searching for hash-function collisions, factoring the large composite number, and so forth–and brute force gets easier with time (due to Moore’s Law).” — Bruce Schneier

Moore’s Law is directly related to cryptography or, more specifically, to cryptanalysis.

###### New Directions in Cryptography

#### New Directions in Cryptography

Whitfield Diffie & Martin E. Hellman — Published November 1976

This paper introduced the concept of public-key cryptography (i.e. asymmetric cryptography).

Simply, public-key cryptography uses one key for encryption and another for decryption, which allows two parties to engage in a secure communication over a non-secure communications channel without having to share a secret key.

###### A Method for Obtaining Digital Signatures and Public Key Cryptosystems

#### A Method for Obtaining Digital Signatures and Public Key Cryptosystems

Ronald L. Rivest, Adi Shamir, & Len Adleman — Published September 1977

In New Directions in Cryptography, Diffie & Hellman proposed a theoretical construction of public-key cryptography (PKC).

In A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Rivest, Shamir, and Adleman provided the first practical implementation of PKC — and introduced us to Alice and Bob.

Diffie would later call the RSA system the single most spectacular contribution to public-key cryptography.

###### Elliptic Curve Cryptosystems

#### Elliptic Curve Cryptosystems

Neal Koblitz — Published October 1985

This paper, along with Use of Elliptic Curves in Cryptography, independently proposed the use of elliptic curves in cryptography.

Unlike other public-key cryptosystems — like RSA, which relies on the fact that factoring large integers is slow and multiplication is fast (the Prime Factorization Problem) — elliptic curve cryptography (ECC) depends on the difficulty of the Elliptic Curve Discrete Logarithm Problem: given two points, P and Q, on an elliptic curve, find the integer n, if it exists, such that Q = nP.

ECC provides similar security guarantees compared to RSA, but with significantly reduced key sizes and more efficient computation. ECC — specifically, Elliptic Curve Diffie-Hellman (ECDH) — is now the preferred authentication mechanism for secure web browsing over SSL/TLS.

###### Use of Elliptic Curves in Cryptography

#### Use of Elliptic Curves in Cryptography

Victor Miller — Published August 1985

This paper, along with Elliptic Curve Cryptosystems, independently proposed the use of elliptic curves in cryptography.

Unlike other public-key cryptosystems — like RSA, which relies on the fact that factoring large integers is slow and multiplication is fast (the Prime Factorization Problem) — elliptic curve cryptography (ECC) depends on the difficulty of the Elliptic Curve Discrete Logarithm Problem: given two points, P and Q, on an elliptic curve, find the integer n, if it exists, such that Q = nP.

ECC provides similar security guarantees compared to RSA, but with significantly reduced key sizes and more efficient computation. ECC — specifically, Elliptic Curve Diffie-Hellman (ECDH) — is now the preferred authentication mechanism for secure web browsing over SSL/TLS.

###### Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

#### Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

Peter Shor — Published November 1994

Public-key cryptosystems have been based on the difficulty of two number theory problems: factoring integers (in the case of RSA) or finding discrete logarithms (in the case of elliptic-curve cryptosystems).

In Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter Shor shows that these problems can be solved in polynomial time on a quantum computer with a small probability of error.

If the only uses of quantum computation remain discrete logarithms and factoring, it will likely become a special-purpose technique whose only

raison d'êtreis to thwart public key cryptosystems.” — Peter Shor

The consequence of Shor’s algorithm is that industry-standard public-key cryptosystems — including RSA & ECDH which are used in TLS, the security protocol behind HTTPS — will easily be broken by quantum computers. NIST is in the process of standardizing public-key cryptography algorithms that are secure against quantum computers.

Once standardized, our aim at Evervault will be to accelerate the deployment of quantum-resistant cryptography to protect data across the web.

###### A fast quantum mechanical algorithm for database search

#### 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.

###### On Data Banks and Privacy Homomorphisms

#### On Data Banks and Privacy Homomorphisms

Ronald L. Rivest, Len Adleman, & Michael L. Dertouzos — Published October 1978

In On Data Banks and Privacy Homomorphisms, Rivest, Adleman, and Dertouzos proposed the problems of (1) modifying a hardware computer system to solve the problem of performing operations on encrypted data securely, and (2) the problem of constructing what has come to be known as a fully-homomorphic encryption (FHE) scheme.

The RSA public-key cryptosystem is a partially homomorphic encryption scheme, where the multiplication of the ciphertext *C* is reflected in the plaintext *P*:

Encrypt P to get C, multiply C by 2, and then decrypt 2C — and you get 2P. That’s a homomorphism: perform some mathematical operation to the ciphertext, and that operation is reflected in the plaintext.” — Bruce Schneier

A FHE cryptosystem is one that is homomorphic under both addition and multiplication and yet still secure. FHE makes it possible to perform arbitrary computations on encrypted data while it remains encrypted — and without needing a secret key. In short, you can process encrypted data without ever decrypting it.

It was not until 2009 when Craig Gentry published a plausible construction of a FHE scheme.

###### A fully homomorphic encryption scheme

#### A fully homomorphic encryption scheme

Craig Gentry — Published September 2009

In A fully homomorphic encryption scheme, Gentry provides a plausible candidate construction of a fully homomorphic (FHE) scheme, answering the problem posed in 1978 by Rivest, Adleman, and Dertouzos in On Data Banks and Privacy Homomorphisms.

A FHE cryptosystem is one that is homomorphic under both addition and multiplication and yet still secure. FHE makes it possible to perform arbitrary computations (mathematical operations like sum or product as well as more complicated operations) on encrypted data while it remains encrypted — and without needing a secret key.

To put everything online “in the cloud,” unencrypted, is to risk an Orwellian future.” — Craig Gentry

Although FHE is not yet practical for widespread implementation, Gentry’s breakthrough has enormous implications for making cloud computing more secure and compatible with the data privacy for individuals.

###### Bitcoin: A Peer-to-Peer Electronic Cash System

#### Bitcoin: A Peer-to-Peer Electronic Cash System

Satoshi Nakamoto — Published October 2008

Bitcoin is a peer-to-peer electronic cash system which does not require a third-party to verify transactions. Bitcoin builds on decades of research in public-key cryptography.

The Bitcoin protocol was the first practical solution to the Byzantine Generals Problem, which is about establishing trust between otherwise unrelated parties over an untrusted network:

[Imagine] a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.” — Leslie Lamport, Robert Shostak, and Marshall Pease

Bitcoin uses a chain of digital signatures to make coins, and hash-based proof-of-work to solve the double-spending problem — the risk that an individual could concurrently send a single unit of currency to two different sources — without the need for a trusted third party.

The ideas first introduced in Bitcoin have been further developed in other cryptocurrencies and cryptonetworks like Ethereum.

###### Protocols for Secure Computations

#### Protocols for Secure Computations

Andrew C. Yao — Published November 1982

In Protocols for Secure Computations, Yao was the first to introduce the idea of secure multi-party computation (MPC).

MPC enables a number of independent parties with private data to operate on the aggregation of their private data, and receive the result — without the parties learning each others’ private data.

For a deeper dive into MPC, see A Pragmatic Introduction to Secure Multi-Party Computation.

###### CryptDB: Protecting Confidentiality with Encrypted Query Processing

#### CryptDB: Protecting Confidentiality with Encrypted Query Processing

Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, & Hari Balakrishnan — Published October 2011

End-to-end encrypted databases — that allow encrypted data to be processed without the decryption keys — are an intermediate design point before practical fully-homomorphic encryption (FHE).

Whether in-the-cloud or on-premise there is a shift to a model where individual applications need to protect themselves instead of relying on firewall-like techniques. That goes especially for the interaction between applications and storage engines, and between applications and databases.” — Werner Vogels, Amazon.com CTO

CryptDB is a system that provides practical and provable confidentiality for applications backed by SQL databases. It works by executing SQL queries over encrypted data using a collection of efficient SQL-aware encryption schemes.

CryptDB is the first practical system that can execute a wide range of SQL queries over encrypted data. The key insight that makes our approach practical is that most SQL queries use a small set of well-defined operators, each of which we are able to support efficiently over encrypted data.” — Ada Popa, Redfield, Zeldovich, and Balakrishnan

###### Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security

#### 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 — Published January 1996

The strength of cryptography lies in the choice and management of the encryption keys.

While mainly of historical interest, this paper, by "an ad hoc group of cryptographers and computer scientists", shows that longer keys will resist attack better than shorter keys, that the cost of very strong encryption is not significantly greater than that of weak encryption, and that it is prudent to require that encrypted data should still be secure in 20 years.

The sizes of encryption keys are measured in bits and the difficulty of trying all possible keys grows exponentially with the number of bits used. Adding one bit to the key doubles the number of possible keys, adding ten increases it by a factor of more than a thousand.”

###### The Knowledge Complexity of Interactive Proof-Systems

#### The Knowledge Complexity of Interactive Proof-Systems

Shafi Goldwasser, Silvio Micali, & Charles Rackoffero — Published February 1989

In this paper, Shafi Goldwasser, Silvio Micali, and Charles Rackoffero introduced zero-knowledge proofs (ZKPs).

ZKPs are a cryptographic technique that allows one party (a prover) to show another party (a verifier) that some computation is correct without revealing any information except the veracity of the statement. ZKPs provide the ability to prove the integrity of data — without revealing any underlying details about the data itself.

Goldwasser, Micali, and Goldwasser created an efficient interactive proof system: a process in which a prover probabilistically convinces a verifier of the correctness of a mathematical proposition.

In 2012, Goldwasser and Micali received the A.M. Turing Award “for transformative work that laid the complexity-theoretic foundations for the science of cryptography.”

A preliminary version of the paper appeared in 1986, and was published in revised form in 1989.

###### A Digital Signature Based on a Conventional Encryption Function

#### A Digital Signature Based on a Conventional Encryption Function

Ralph C. Merkle — Published August 1987

In this Paper, Ralph C. Merkle devised the concept of **Merkle trees**. Merkle trees provide an efficient way to store data, saving memory and processing power.

At the heart of Merkle trees is **hashing**. **Hash functions** are algorithms for computing a unique, fixed-length value (a **hash**) from data. A small change in the input of a hash function changes the hash value entirely; hashes are unique. Hash functions are one-way; hash values cannot be reversed to reveal the input. Merkle trees depend on hash uniqueness to organize and verify data.

A Merkle tree is a tree of hashes. Each **parent node** in the tree has two or more **child nodes**. The original child nodes in the tree store hashes of plaintext data. The hash of a set of child nodes (**sibling nodes**) creates the hash of the parent node — a hash of a hash. This process of hashing continues all the way up until the **root hash** — the final hash in the tree.

If at any point in the tree, the input of a hash is changed, this change will show in consequent hashes — including the root hash. **Merkle proofs** are used to verify that the hashes across all **branches** of the Merkle tree have not been tampered with.

Merkle trees are a core component of cryptocurrencies like Bitcoin and Ethereum.

We’ll be adding new papers each week — don’t forget to subscribe below.