# Tag Info

## Hot answers tagged cryptography

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

19

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

18

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

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

17

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

15

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

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

12

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

11

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

11

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

11

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

8

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

8

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

7

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

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

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

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

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

6

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

6

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

6

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\... 6 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 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 ... 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 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 + \...

5

In principle it is possible to generate code for oracles such as the DES encryption (under fixed plaintext/ciphertext pairs, so that the search space becomes the set of all possible encryption keys). One (simple) way to do so is to apply the Bennett method to a classical, irreversible circuit and then to count the gates manually. There are better ways known ...

5

This is a purely hypothetical answer - I don't know if anybody has ever studied it, and have not attempted to find out - but think about public key cryptography. Current public key systems are based on the idea that some problems in the complexity class NP are probably hard to solve directly, but there exists a "proof" that lets you verify the solution ...

5

If one had general information-theoretically secure MQPC, one would have 1-out-of-2 oblivious transfer (OT), as this can be obtained from an MPQC protocol computing the following 2-party function: consider a function $f(a_0,a_1,b_0,b_1)$ that takes as input two private bits $a_0,a_1$ from Alice (the two different messages) and two bits $b_0,b_1$ from Bob (...

5

No. The whole point of an entangled state is that it cannot be written in the form $|\psi\rangle|\phi\rangle$. So, if you replace $|\psi\rangle$ with an entangled state, it is no longer in the state $|\psi\rangle$. In response to the updated question, the answer is still "no". There will always be a test that the sender and receiver could perform ...

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

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