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


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


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

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


1

There is an interesting time lock technique known as 'delay encryption'. This is based on isogenies of supersingular curves and pairings. As we know, Supersingular Isogeny curves are one of the reference post quantum ( quantum safe / resistant ) cryptography technique. This technique is related to Time-lock Puzzles and Verifiable Delay Functions. This ...


1

No, not yet. Let: "time" mean the total amount of computations, and "parallel time" mean the minimum amount of sequential computations In order to meet the practical requirements for a puzzle that will last until Shor's algorithm can be implemented, the asymptotic complexity needs to meet the following requirements: The solving time and parallel time ...


1

Currently we use slow key derivation functions. If a hypothetical quantom computer could run these as fast as a classical computer (Which is a huge If) grover's algorithm would allow searching over the equivalent of the squared root of the password space. However even a sizeable quantom computer won't be able to do that. We will be seeing Shor's algorithm ...


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