Is it possible for an encryption method to exist which is impossible to crack, even using quantum computers?

Question

Quantum computers are known to be able to crack in polynomial time a broad range of cryptographic algorithms which were previously thought to be solvable only by resources increasing exponentially with the bit size of the key. An example for that is Shor's algorithm.

But, as far I know, not all problems fall into this category. On Making Hard Problems for Quantum Computers, we can read

Researchers have developed a computer algorithm that doesn’t solve problems but instead creates them for the purpose of evaluating quantum computers.

Can we still expect a new cryptographic algorithm which will be hard to crack using even a quantum computer? For clarity: the question refers to specifically to the design of new algorithms.

Answer 1

The title of your question asks for techniques that are impossible to break, to which the One Time Pad (OTP) is the correct answer, as pointed out in the other answers. The OTP is information-theoretically secure, which means that an adversaries computational abilities are inapplicable when it comes to finding the message.

However, despite being perfectly secure in theory, the OTP is of limited use in modern cryptography. It is extremely difficult to use successfully in practice.

The important question really is:

Can we still expect a new cryptographic algorithm which will be hard to crack using even a quantum computer?

Asymmetric Cryptography

Asymmetric cryptography includes Public-Key Encryption (PKE), Digital Signatures, and Key Agreement schemes. These techniques are vital to solve the problems of key distribution and key management. Key distribution and key management are non-negligible problems, they are largely what prevent the OTP from being usable in practice. The internet as we know it today would not function without the ability to create a secured communications channel from an insecure communications channel, which is one of the features that asymmetric algorithms offer.

Shor's algorithm

Shor's algorithm is useful for solving the problems of integer factorization and discrete logarithms. These two problems are what provide the basis for security of widely used schemes such as RSA and Diffie-Hellman.

NIST is currently evaluating submissions for Post-Quantum algorithms - algorithms that are based on problems that are believed to be resistant to quantum computers. These problems include:

• Lattice based problems
  • Shortest vector problem (SVP)
  • Closest vector problem (CVP)
• Multivariate equations
  • Multivariate polynomial equations
• Code based schemes
  • Based on the hardness of decoding linear codes
• Supersingular Isogeny Diffie-Hellman (SIDH)

It should be noted that classical algorithms for solving the above problems may exist, it's just that the runtime/accuracy of these algorithms is prohibitive for solving large instances in practice. These problems don't appear to be solvable when given the ability to solve the problem of order finding, which is what the quantum part of Shor's algorithm does.

Symmetric Cryptography

Grover's algorithm provides a quadratic speedup when searching through an unsorted list. This is effectively the problem brute-forcing a symmetric encryption key.

Working around Grover's algorithm is relatively easy compared to working around Shor's algorithm: Simply double the size of your symmetric key. A 256-bit key offers 128-bits of resistance against brute force to an adversary that uses Grover's algorithm.

Grover's algorithm is also usable against hash functions. The solution again is simple: Double the size of your hash output (and capacity if you are using a hash based on a sponge construction).

Answer 2

I suppose there is a type of encryption that is not crackable using quantum computers: a one-time pad such as the Vigenère cipher. This is a cipher with a keypad that has at least the length of the encoded string and will be used only once. This cipher is impossible to crack even with a quantum computer.

I will explain why:

Let's assume our plaintext is ABCD. The corresponding key could be 1234. If you encode it then you get XYZW. Now you can use 1234 to get ABCD or 4678 to get EFGH what might be a valid sentence too.

So the problem is that nobody can decide whether you meant ABCD or EFGH without knowing your key.

The only reason this kind of encryption can be cracked is that the users are lazy and use a key twice. And then you can try to crack it. Other problems are, as @peterh stated that one-time-pads require a secret channel to be shared

Answer 3

Yes, there are a lot of proposals for Post-quantum cryptographical algorithms that provide the cryptographic primitives that we are used to (including asymmetric encryption with private and public keys).

Answer 4

To follow up on Ella Rose's answer: most practical encryption schemes used today (e.g. Diffie-Hellman, RSA, elliptic curve, lattice-based) are centered around the difficulty of solving the hidden subgroup problem (HSP). However, the first three are centered around the HSP for abelian groups. The HSP for abelian groups can be efficiently solved by the quantum Fourier transform, which is implemented e.g. by Shor's algorithm. They are therefore vulnerable to attack by a quantum computer. Most lattice-based methods, on the other hand, revolve around the HSP for dihedral groups, which are nonabelian. Quantum computers are not believed to be able to efficiently solve the nonabelian HSP, so these algorithms should be able to implement post-quantum cryptography.