37
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Please add your research efforts in the way of trying to find an answer. It's important that the first few questions set a good example of how we want the site to be in the long term. $\endgroup$ – Sanchayan Dutta Mar 12 '18 at 17:14
  • $\begingroup$ @Blue I improved the post, and I am open to improve it further. $\endgroup$ – peterh Mar 12 '18 at 17:31
  • 2
    $\begingroup$ I can think about One-time pad $\endgroup$ – Juan González Salinas Mar 12 '18 at 18:07
  • $\begingroup$ @JuanGonzálezSalinas that's a bit of a cheap answer though, since it's proven impossible (iirc). $\endgroup$ – Riker Mar 12 '18 at 19:36
  • $\begingroup$ > "Is it possible for an encryption method to exist which is impossible to crack, ..." - What constitutes "impossible", mathematical proof that it is not possible? What if it was proven that with computers advancing at the fastest rate possible that it could be broken in 10K years; is that "impossible" enough? - In the early days most unbreakable codes fell pretty quickly, it's only in the past few decades that people have known to test more and brag less. Not a criticism of your question, just a little more research and exactness. What if every 2nd word could be decrypted, is it broke? $\endgroup$ – Rob Mar 20 '18 at 18:55
22
$\begingroup$

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:

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

$\endgroup$
  • $\begingroup$ You make reference to crypto.stackexchange.com/questions/15652/… but can't we use BB84 quantum algorithm (en.wikipedia.org/wiki/BB84) to assure that the private key is shared securely ? $\endgroup$ – JanVdA Dec 5 '18 at 18:39
  • $\begingroup$ @JanVdA Have you seen this question and answer and this one? In theory under a certain set of assumptions, "yes". In practice, it's not so simple. For example, IDQuantiques setup does not benefit from the information-theoretic guarantee because they use the key shared by QKD for AES instead of a OTP. The reason for doing so is again practicality. 1/2 $\endgroup$ – Ella Rose Dec 5 '18 at 19:16
  • $\begingroup$ 2/2 There are theoretic techniques with certain assumptions that would allow you to share OTP keys without QKD: Securely meet in person with those you wish to communicate with at regular time intervals, and exchange key material on a physical medium (and assume it is destroyed properly after use). Theoretically, it works. In practice, it won't. Practicality is vital for adoption. $\endgroup$ – Ella Rose Dec 5 '18 at 19:17
20
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As I understand, it is essentially a one-time-pad. It has a significant disadvantage, that the key length should be at least the size of the cleartext, the key is not reusable, and that sharing the key requires a hidden channel. What about exp(exp(time)) problems? $\endgroup$ – peterh Mar 12 '18 at 17:45
  • $\begingroup$ @peterh yes it is an one-time pad. The problems you described were meant to be summarized in the last paragraph. I am sorry, but I have nether heard about exp(exp(time)) problems? What is this? A short Google search can't help me. Could you please give me some keywords that will direct me to the right target and I will try to include it into my answer. $\endgroup$ – MEE the setup wizard Mar 12 '18 at 18:01
  • 1
    $\begingroup$ Nice article about One Time pad here $\endgroup$ – DIDIx13 Mar 14 '18 at 9:11
  • $\begingroup$ Of course, the problem which remains is that the integrity of the message cannot be verified. $\endgroup$ – Alex Jone Mar 31 '18 at 17:23
  • $\begingroup$ It might also be worth noting that there is a quantum analogue of the one-time pad. $\endgroup$ – Sanketh Menda Apr 10 '18 at 7:06
16
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.