A Guide to Fully Homomorphic Encryption

Today, increases in compute capabilities enabling new technology requires new architectures that match the problems. Similarly to how GPUs enabled deep learning.

Public-key schemes based on factoring and discrete logarithms are undone by Shor's algorithm (https://en.wikipedia.org/wiki/Shor%27s_algorithm), but there are asymmetric systems not known to be vulnerable to quantum algorithms. They are less mature, but researchers are working it.

There's some good high-level information at http://pqcrypto.org/ and in this paper: http://pqcrypto.eu/docs/initial-recommendations.pdf.

Given an arbitrary function f(x), and a desired output k, find the unique input z such that f(z)=k.

We can see that using classical computers, this problem is O(n), where n is the size of the domain of f. However, Grover's algorithm can solve this problem in O(sqrt(n)). It has been shown that O(sqrt(n)) is the best possible solution to this problem on a quantum computer.

This means that quantum computers effectively halve the key-size for a brute force attack (and probably most other types), but doing any better than this would require exploiting some structure of the cryptosystem you are trying to break. To my knowledge, no such structure has been demonstrated for any major symmetric encryption algorithms.

Basically, it uses the result that it should be 'hard' to learn a linear function with sufficient noise rate to create a cryptosystem.

For example, if cryptography basically consisted of taking a set of plaintext "blocks" and a key, permuting the key separately and deterministically for each block in O(1) time, expanding the key into a one-time pad again in O(1) time, and XORing each block with its respective pad—then you could use a quantum computer to quickly search the keyspace for a key that decrypts the blocks into something sensible according to some heuristic. You can make a quantum algorithm that "searches" a static keyspace, given that you can map a particular ciphertext block to particular plaintext block in O(1) time—this mapping effectively becomes a "projection" of the keyspace, and the quantum computer searches that.

The problem with this approach is that, in reality, subkeys in a "stream" aren't generated independently per-block (as happens in the much-derided "ECB mode" of block ciphers), but rather are generated serially by feeding in the previous subkey in a chained operation; and that each cipherblock is then created by "expanding" the subkey through a CSPRNG, which itself uses iterated hashing.

You can't make a quantum algorithm that searches a keyspace, given an encryption algorithm that is defined recursively or "statefully" on its input stream. There's no such thing as a "quantum for-loop" that magically makes an O(N)-step process into a single linear projection of the keyspace—and without this, there's nothing to usefully search through.

Even if there was such a machine, the number of people who could write code for it is less than or equal to ten.

Even quatom computers require superlinear time run Shor's algorithm.

"We have quantum information processing, but no computers as of yet."

And, that which we already have is so-darned-expensive; that it is less useful than classical computation unless you are building some exotic kind of sensor.