25

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


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


17

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


16

If you are talking specifically about quantum key distribution (quantum cryptography being an umbrella term that could apply to lots of stuff), then once we have a quantum key distribution scheme, this is theoretically perfectly secure. Rather than computational security that much of current cryptography is based on, quantum key distribution is perfectly ...


14

Abel Molina, Thomas Vidick, and I proved that the correct answer is $c=3/4$ in this paper: A. Molina, T. Vidick, and J. Watrous. Optimal counterfeiting attacks and generalizations for Wiesner's quantum money. Proceedings of the 7th Conference on Theory of Quantum Computation, Communication, and Cryptography, volume 7582 of Lecture Notes in Computer ...


14

Quantum key distribution requires that you wholesale replace your entire communications infrastructure built out of 5 EUR ethernet cables and 0.50 EUR CPUs by multimillion-euro dedicated fiber links and specialized computers that actually just do classical secret-key cryptography anyway. Plus you have to authenticate the shared secret keys you negotiate ...


13

This is not a very enlightening concept, because most interesting quantum algorithms, such as Shor's algorithm, involve some classical computations as well. While you can always shoehorn a classical computation into a quantum computer, it would be at unnecessarily exorbitant cost. We don't yet know, of course, exactly what problems will be hard to solve ...


10

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


9

If it is proven that a given asymmetric encryption protocol relies on a problem which cannot be solved efficiently even by a quantum computer, then quantum cryptography becomes largely irrelevant. The point is that, as of today, no one was able to do this. Indeed, such a result would be a serious breakthrough, as it would prove the existence of $\text{NP}$ ...


9

Most attacks now on classical computers don't actually break the encryption, they trick the systems / communication protocols into using it in a weak way, or into exposing information via side channels or directly (via exploits like buffer overflows). Or they trick humans into doing something (social engineering). I.e. currently you don't attack the crypto ...


7

As one of the authors of the paper, and of the original theory papers on which that experimental realisation is based, perhaps I can attempt to answer. The BQC protocol used in that paper is based on a model of computations where measurements are made on a specially chosen entangled state (this is known as measurement-based quantum computation or MBQC, and ...


7

It looks like you're asking about this part of the paper: Therefore, a quantum computation is hidden as long as these measurements are successfully hidden. In order to achieve this, the BQC protocol exploits special resources called blind cluster states that must be chosen carefully to be a generic structure that reveals nothing about the underlying ...


7

"I'm looking for an explicit upper bound on the probability of successful counterfeiting ...". In "An adaptive attack on Wiesner's quantum money", by Aharon Brodutch, Daniel Nagaj, Or Sattath, and Dominique Unruh, last revised on 10 May 2016, the authors claim a success rate of: "~100%". The paper makes these claims: Main results. We show that in a ...


7

So, Bob is given the following state (also called the maximally-mixed state): $\rho = \frac{1}{2}|0\rangle\langle 0| + \frac{1}{2}|1\rangle\langle 1| = \begin{bmatrix} \frac{1}{2} & 0 \\ 0 & \frac{1}{2} \end{bmatrix}$ As you noticed, one nice feature of density matrices is they enable us to capture the uncertainty of an outcome of a measurement and ...


6

We (i.e. the current state of research) just don't know, but we can guess. We guess that there may be a problem if Post Quantum Crypto (PQC) lags behind, as Shor's algorithm can solve the factoring problem efficiently (thereby breaking RSA public key crypto) or for Grover's algorithm to force a doubling of the number of bits for all keys, as it can search ...


6

Your analysis of Eve's cheating doesn't seem quite right (although the final answer is correct). What you need to say is: Assume Alice prepares a particular state in one of the bases. You could assume that's $|0\rangle$, but you can make the argument more generally. With 50% probability, Eve measures in the same basis that Alice prepared in (the 0/1 basis ...


5

This is essentially the realm of computational complexity classes. For example, the class BQP may crudely described as the set of all problems that can be efficiently solved on a quantum computer. The difficulty with complexity classes is that it's hard to prove separations between many classes, i.e. the existence of problems which are in one class but not ...


5

Talking about bases such as $\left|0\rangle\langle0\right|$ and $\left|1\rangle\langle1\right|$ (or the equivalent vector notation $\left|0\right>$ and $\left|1\right>$, which I'll use in this answer) at the same time as 'horizontal' and 'vertical' are, to a fair extent (pardon the pun) orthogonal concepts. On a Bloch sphere, there are 3 different ...


5

Bitcoin uses elliptic-curve cryptography to sign transactions, which can easily be broken by Shor's algorithm. I didn't actually read the article because it looked kind of dumb, but I gathered that the author proposed using Grover's algorithm to speed up the mining process by looking for hashes more efficiently. If you had a functioning quantum computer, ...


5

Why can you not subdivide a quantum bitcoin? Anyone can create a Cryptocurrency, how it works is up to them, how well it is received is up to the public, generally it is decided by: Utility, Scarcity, Perceived Value. As of today a Bitcoin is worth USD 7,073.54, A Bitcoin is 10$^8$ Satoshis which are 0.00000001 Bitcoins, so a Satoshi is worth: 7,073.54 * 0....


5

Certainly! Imagine you have $K=2^k$ copies of the search oracle $U_S$ that you can use. Normally, you'd search by iterating the action $$ H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S, $$ starting from an initial state $(H|0\rangle)^{\otimes n}$. This takes time $\Theta(\sqrt{N})$. (I'm using $\mathbb{I}_n$ to denote the $2^n\...


5

So Alice sends Bob a qubit with the density matrix $$\rho = \frac{1}{2}|0\rangle\langle 0| + \frac{1}{2}|1\rangle\langle 1| = \begin{bmatrix} .5 & 0 \\ 0 & .5 \end{bmatrix}$$ as you said. (I've fixed the notation to make it a density matrix, what you wrote was in the structure of a state, but with non-normalized coeffecients. It is important to ...


5

Alice receives a quantum state $|\psi\rangle$, which is an element of some basis $\mathcal{B}$, though she does not know what $\mathcal B$ is. She then teleports this to Bob, who is told by someone else what $\mathcal B$ is. Furthermore, it seems that specifically either $\mathcal{B} = \{ \lvert 0 \rangle, \lvert 1 \rangle \}$ or $\mathcal{B} = \{ \lvert + \...


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


4

This answer assumes that you do not have a technical background in cryptography or quantum physics. Most current implementations of the blockchain rely on two math concepts: (1) Public key encryption. (2) Hash keys. Quantum computers can break the public key encryption part, through a famous method known as Shor's algorithm (For technical details: see page ...


4

My crude understanding of blockchain (derived mainly from the Wikipedia article) is that it gets its security from two sources: Individual communications are performed using a public key cryptography scheme Information is stored in a decentralised manner across many different computers, meaning that there are many different copies of the same information. ...


4

Are the current implementations of blockchain resistant to attacks using quantum computation? Quick answers: Resistant against near-term technology? Sure. Reliably secure in the long term? Probably not. Will this pose a major problem? Very likely not. Is this risk unique to blockchains? Nope. Because even if quantum computers would become a major ...


4

That’s the public discussion stage: Alice and Bob can both announce which basis they chose for each round. If they happened to pick the same basis on a given round, they know that (in a perfect world) their answers were the same, so they can translate them into a 0/1 value that nobody else knows. That translation is arbitrary, and they’ve probably agreed it ...


4

Please start by reading my answer here. I believe you've mistaken the requirements for post-quantum crypto. If you use a scheme which is QMA-hard, then that means either your problem is QMA-complete (in which case, you can decrypt the message using a quantum computer, but not with a classical computer unless NP=QMA), or not (in which case you cannot decrypt ...


Only top voted, non community-wiki answers of a minimum length are eligible