# Tag Info

36

wondering what the largest integer is which they were able to factor with a small quantum computer Stunts Before the present answer, the largest claim for quantum-related factoring seems to have been 4088459=2017×2027, by Avinash Dash, Deepankar Sarmah, Bikash K. Behera, and Prasanta K. Panigrahi, in [DSBP2018] Exact search algorithm to factorize large ...

36

What would be the applicability of that to cryptanalysis? It wouldn't appear to have any direct applicability to cryptanalysis, for two reasons: 50 Qbits is just not enough to attack any cryptographical problem; to apply either Shor's or Grover's algorithm against any realistic problem, you'll end up needing thousands. It doesn't appear that they're ...

31

TL;DR: Not much. If the qubits were very high quality, some very tricky algorithms could use them to do some algorithm subprocesses more quickly, but we actually have more quantity than quality. So it's just research for now. A 50-qubit universal quantum computer could use Grover's algorithm to invert a 49-bit function in time $\approx7$ steps instead of $\... 28 How does it compare to classical computers, performance-wise, for cryptanalytic tasks? Not at all - IBM's quantum computer cannot perform any nontrivial cryptanalytic task. For one, 53 physical qubits far too few to do anything interesting; for example, implementing SHA-256 would take thousands of logical qubits. For another, the qubits are not even close ... 27 There is no public paper available yet, so this answer is preliminary and based on what was presented in the talk and the follow-up discussion. A full understanding cannot be reached until there is a paper to verify, evaluate, and compare to prior work and known results. However, a good understanding of the situation already seems to be emerging. The tl;dr ... 21 D-Wave's "Quantum computers" are NOT general purpose quantum computers. They can only do quantum annealing, which allows a small subset of problems to be solved. They can't run Shor's or Grover's algorithms, as these aren't quantum annealing problems. It's also still an open question whether D-Wave's machines even provide any speedup over classical simulated ... 17 can they (quantum computers) do such complicated computing (cryptanalysis)? Not currently. Current quantum computers (including the adiabatic variants specialized in quantum annealing) do not perform anything useful for cryptanalysis. In the future: we don't know. Is it possible quantum computers put the computer security in jeopardy? It is reasonable ... 15 The 20,000,000 is the number of physical qubits of a certain quality required and corresponds most closely to the number of qubits quoted by those engineering teams current developing quantum devices. However, quantum computational capability is not just dependent on the raw number of qubits available. The 20,000,000 qubits quoted need to be able to execute ... 14 I'm one of the authors of the paper. In order to make the paper more approachable, we factored each major optimizations out into its own paper. There are three of these sub-papers, and they each stand on their own mostly independent of the others. "Approximate encoded permutations and piecewise quantum adders ". We put small amounts of padding at various ... 10 If quantum computers are physically feasible, then there are some algorithmic problems that they should be able to solve faster than classical computers. It happens that brute-force search and discrete logarithms are two of those problems. Unfortunately, the security of symmetric cryptosystems depends on brute-force search being hard, and the security of ... 7 Even though the D-Wave machines can not be labelled as "general purpose", they are certainly research objects with new applications everyday. The capabilities of what they can do is only limited by our current developments, so the term general purpose is rather meaningless in the new QC realm. Contrary to the previous answer, the latest D-Wave 2X (2000 ... 7 One could give a much longer answer to this question (and I would be quite interested in seeing someone like Chris's perspective), but the following two points probably suffice for a non-specialist. Approximation Factors: The main way this attack should be seen as (potentially) threatening to lattice-based cryptography is via the possibility of future ... 6 You asked: Is it possible to crack RSA / ECC on a quantum computer if we only have ciphertext and don't have the public key used to encrypt itself? Typically not, with a few exceptions; here are the exceptions: RSA signatures with deterministic padding (eg. PKCS #1.5) and a small to moderate$e$(e.g.$e = 65537) - with two signatures (and corresponding ...

6

Here's an example where the best known quantum attack is, in a sense, just "halfway" between the best known classical attack on one side, and a complete break on the other: Inverting a cryptographic group action such as CSIDH. Let $G$ be a (finite) commutative group $G$ acting on a set $X$, i.e., we consider a map $$\ast\colon\; G\times X\to X$$ that is ...

6

Does the block size of a symmetric cipher impact the security of the cipher itself? Yes, absolutely. A small block size limits the amount of data that can be encrypted with a given key, and some block modes are more badly affected by this than others. Additionally, some cryptographic attacks against weak ciphers can be made more practical against a block ...

5

There are three main standard quantum threats to traditional cryptography: Shor's algorithm. Spend $O(\log \ell \cdot \log \log \ell)$ quantum gates and $O(\log \ell)$ additional qubits in a quantum circuit to compute the period of a function $f$ bounded by $\ell$. The number of quantum gates to compute $f$ is about the same as the number of classical ...

5

From this Thermodynamic Analysis of Classical and Quantum Search Algorithms, Sep 29, 2017; For the problem of collision finding, previous work suggested that quantum algorithms were unlikely to provide an asymptotic advantage in terms of circuit size (despite using fewer oracle queries). Our thermodynamic analysis leads to a similar conclusion. We compare ...

5

It depends on the kind of quantum computer and how many logical qubits it has. Not all quantum computer designs are capable of breaking cryptographic systems. The popular adiabatic quantum computers, while very useful for certain tasks, have no cryptanalytic utility. Designs that are capable of running, say, Shor's algorithm are currently in their infancy. ...

5

But is there also a notion of computational security in quantum cryptography (assuming a polynomial-time quantum adversary)? No, not really, or at least, none that has been explored. The goal of Quantum Cryptography is to be secure, even if the adversary has a Quantum Computer and that they are computationally unbounded; that is, the goal is to rely (as ...

5

Aaronson's notes discuss finding $p$ and $q$ if we know $\phi(N)$ by solving the quadratic equation $X^2-(N-\phi(N)+1)X+N=0$ whose roots are $p$ and $q$. This only works if $N$ is the product of two distinct primes (which is the case in most applications of interest) and if we know $\phi(N)$ exactly. What doesn't often get mentioned about RSA and ...

4

My questions are, how reasonable are these claims? Sounds fairly reasonable; they suggest an alternative factoring algorithm where they trade-off circuit depth to reduce the number of qubits required. Would this trade-off be a good thing in practice? We don't know. We don't have a large scale quantum computer in front of us, and so we don't know the ...

4

δ_0: the root Hermite factor required β: the BKZ block size d: the dimension of the lattice being reduced m: the number of LWE samples used

4

Currently, the quantum attacks work on the block cipher itself. The Grover's search algorithm reduces the complexity of 256-bit key into 128-bit since it has complexity $\mathcal{O}(\sqrt{n})$ and in the case of 256-bit $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$ Since you have started with 128-bit entropy, theoretically, the quantum attacker to ...

4

There is a superposition of states initially, and there must be enough qubits in the circuit so that after the iterations the correct period of the function $f(x)=a^x\bmod N$ where $a$ is random and $N=pq$ can be found, i.e., the convergence should take place without wraparound effects, since we are working in a cyclic group and wraparound can introduce ...

4

You are right. Indeed, Grover's algorithm has to evaluate the function that is attacked in each iteration (actually the algorithm complexity measure in which you get the square root speed-up is query complexity). And of course, if you make that function more expensive you also make an attack more expensive -- classical as well as quantum. However, here we ...

4

What happens when quantum-resistant cryptography is implemented using a quantum computer? You may want to note that "quantum-resistant" doesn't mean "the quantum computer will blow up when trying to decrypt this" nor "the quantum computer will error out when decrypting this". It means that an adversary who has access to a quantum computer has no ...

4

For symmetric cryptography, it is highly plausible that doubling the key size compared to current practice (say from 128 to 256-bit) provides more than adequate protection against hypothetical quantum computers capable of running Grover's algorithm (or similar) on large inputs. It requires $O(2^{n/2})$ effort for $n$-bit key, compared to $O(2^n)$ for brute ...

4

According to L. Zyga et al, N. Dattani and N. Bryans factored $56\,153 = 233 \cdot 241$ in November 2014, using a 4-qubit minimization (adiabatic quantum computation?) algorithm. Researchers believe that the method could be extended to factor $291\,311$. As of that time, the largest factorization achieved by Shor's algorithm was $21 = 3 \cdot 7$, and even ...

4

Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod n$, then $\gcd(a^t \pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $\gcd(a^t \pm 1, n) = p$, then you can ...

3

Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to: If $n$ is a product of more primes, say $k \ge 3$ primes, then the same speedup becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents and ($1/k$)-size moduli. Prime ...

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