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

29

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

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

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

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

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

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

3

The query complexity, i.e. the number of times the machine evaluates the function as a black box, may be $O(2^{n/3})$, but that's not the only cost of an algorithm: the size of the machine and how long you have to run it figure in too. So far, there are no implications of quantum algorithms for security parameters of collision-resistant hash functions. ...

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

3

Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in this Wikipedia article which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer ...

2

A similar construct to a time-lock puzzle is a verifiable delay function. They have a similar notion of "inherent sequentially". They have an unrelated "public verifiability" property which you do not care about. Boneh et al. build verifiable delay function from a construct called Incrementally Verifiable Computation'', which they can instantiate from ...

2

The short answer is: Of course! Why not! It is pretty easy to build an artificial secret key encryption scheme that is based on RSA and breaks if the adversary has a quantum computer*. Of course no one would want to build a symmetric primitive out of number theoretic assumptions as that would defeat the main purpose of being far more efficient than ...

2

In the $(\gamma, \eta, \rho)$-AGCD problem, all the samples are of the form $$x_i := pq_i + r_i$$ for $q_i$ uniform from $[0, 2^\gamma / p [ ~ \cap \mathbb Z$; $r_i$ uniform from $]-2^\rho, 2^\rho [ ~ \cap \mathbb Z$; and $p$ a fixed random prime of $\eta$ bits. This problem is believed to be quantum secure. See, for instance, this paper published in PKC ...

2

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

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