17
$\begingroup$

Recent researches indicate that quantum algorithms are able to solve typical cryptology problems much faster than classic algorithms.

Have any quantum algorithms for encryption been developed?

I'm aware about BB84, but it only seems to be a partial solution for solving the networking.

$\endgroup$
11
$\begingroup$

Quantum cryptography relies on elaborate physical machinery to execute cryptographic protocols whose security rests upon axioms of quantum mechanics (theoretically, anyways).

To quote the wikipedia entry on the BB84 protocol:

The security of the protocol comes from encoding the information in non-orthogonal states. Quantum indeterminacy means that these states cannot in general be measured without disturbing the original state (see No cloning theorem).

There is a good question and answers about "What makes Quantum Cryptography secure?" on crypto.stackexchange. They are verbose, so I will refrain from copying the content here.

Differences between Quantum Cryptography and Modern Cryptography

Quantum cryptography requires specialized machinery in order to execute a run of the protocol. This is a non-negligible disadvantage compared to modern cryptography. If you want to use Quantum Cryptography, you'll need to pay one of the commercial entities that offers the service.

Modern cryptography uses mathematical algorithms implemented in software, which can be performed by any old computer with sufficient resources (which are almost all computers in this day and age). The outputs of the algorithms can be transmitted via an arbitrary communications medium.

If you see a green padlock next to the URL in your web browser, it means your connection to this very site is being secured by modern cryptography - which is effectively being done for free, as far as you were concerned.

Note

enter image description here

Quantum cryptography is often thought to be unconditionally unbreakable due to the laws of the universe. This sounds too good to be true, and it unfortunately is. There is nothing to stop someone from waiting for you to receive your message, then to threaten you until you reveal what the message was. There is also the issue of an adversaries ability to tamper with the hardware. For a rather scathing but in-depth review of these points, see the blog post at cr.yp.to.

Basically, as with all provably secure cryptographic techniques, these guarantees are only provided within the framework of assumptions that the proofs rest upon. An adversary who finds a hole in these assumptions can circumvent the theoretical guarantees that the algorithms offer. That's not to say that QC is totally worthless and overtly non-functional, but that "provable security", as always, needs to be understood to rest on certain sets of assumptions that could be violated in practice.

| improve this answer | |
$\endgroup$
3
$\begingroup$

There is a cryptographic primitive that is only realisable with quantum computation: A revocable timelock. The base idea is to set up a problem that needs a certain time to be solved on a quantum computer, but the quantum computation can be cancelled in a provable way.

| improve this answer | |
$\endgroup$
1
$\begingroup$

I think that there are many interesting answers to your question, but I would like to point out what I personally find the most mesmerizing consequence of quantum theory to cryptography.

One of the most fascinating quantum phenomena that has no classical counterpart is no cloning. This essentially means that if you don't have enough information about some quantum state, then you can't prepare more copies of it. This could be seen (informally) as a restatement of the uncertainty principle: if you could prepare two perfect copies of a system you know nothing about, then nothing prevents you from measuring each copy in a different basis, thereby obtaining knowledge of two mutually unbiased properties (e.g., if you could perfectly copy an electron, then you could measure its momentum in one copy and its position in the other).

No cloning is usually a huge pain. For example, consider e.g. the Miller-Rabin algorithm for primality testing. This is a randomized algorithm, which means that every time you run it it plays out a little differently. Given a prime number, this algorithm will always tell you that it is a prime. Given a composite number, it will still tell you some of the times that it is prime. However, one can prove that his happens with probability which is less than $1/2$. This implies that if you run the algorithm $n$ times on a composite number the probability that it will tell you that it is prime each and every time is at most $1/2^n$. This process is called amplification, and the underlying assumption is that we can always repeat the algorithm. While trivial classically, this assumption does not generally hold in the quantum realm, as the input state might be measured and thus irreversibly destroyed. It was shown by Marriot and Watrous that BQP algorithms can still be amplified this way, but the way to do so is highly non-trivial.

As you might have expected, now comes the "lemons to lemonade" stage. Because if cloning states is impossible, might we leverage that to our advantage, say, in order to design things that we don't want people to make copies of, such as money?

Amazingly, this idea predates most of quantum computation and information. As early as 1968, Steve Wiesner proposed applying no-cloning to implement money that is physically impossible to forge. More amazingly, his construction is extremely simple and only requires the ability to apply local Hadamard gates (and consequentially, the money is encoded into a completely separable state). Unfortunately, as the story goes, it seems that Wiesner was not able to publish his breakthrough for more than a decade.

The applications of no-cloning has since been extended greatly, and there is ongoing research of very natural further problems such as public quantum money (in Wiesner's scheme, only who created the money can verify it. This merits the question: is it able to make money that anyone can verify but no one could forge) (see also), quantum copy protection, uncloneable encryption, one time signature tokens, etc.. These are all fascinating primitives which are classically impossible, but might be possible using quantum computation (under some mild computational assumptions). The current state of the art is that almost all such constructions either rely on strong (or just irregular) assumptions, or on the existence of some unrealistic oracle. But keep in mind that these questions are relatively new, and the research involving them is very active!

| improve this answer | |
$\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.