Evervault Papers

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.

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.

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.

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.

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.

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.

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.

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'être is 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.

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.

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.

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