量子コンピューターを使っても解読できない暗号化方法が存在することは可能ですか?


42

量子コンピューターは、以前は鍵のビットサイズとともに指数関数的に増加するリソースによってのみ解決可能であると考えられていた幅広い暗号アルゴリズムをin polynomial timeにクラックできることが知られています。その例はShor's algorithmです。

しかし、私の知る限り、すべての問題がこのカテゴリに分類されるわけではありません。Making Hard Problems for Quantum Computersに読むことができます

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

量子コンピューターを使用しても解読が困難な新しい暗号アルゴリズムを期待できますか?明確にするために:この質問は、特に新しいアルゴリズムの設計に関するものです

21

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


18

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


27

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


5

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.