Questions tagged [quantum-computing]
A computation model which relies on quantum-mechanic phenomena, such as entanglement and superposition. This generalizes the probabilistic model of computation.
43
questions
3
votes
0
answers
85
views
A highly space-efficient embedding of prime factorization problem using the Ising model
I hope this is not off-topic for this SE, as it directly relates to the RSA problem. My background is in quantum information and computation, so please excuse me if my notation doesn't match your ...
3
votes
2
answers
577
views
Why is discrete logarithm not quantum proof?
I don't understand why discrete logarithm is not quantum proof. I understand that quantum computer can quickly compute the exponent, but there is a modulo in the equation. Doesn't it mean, that there ...
4
votes
0
answers
77
views
Comparing quantum computing resources to break the DLP on elliptic curve group vs Schnorr group
Take an elliptic curve group of 256-bit prime order $n$ over a 256-bit prime field in which the Discrete Logarithm Problem is believed hard, e.g. secp256r1. Build an isomorphic Schnorr group by taking ...
11
votes
4
answers
8k
views
How will the world learn that Q-Day has arrived?
I wonder how the world will come to know that scalable, fully fault-tolerant quantum computers capable of running Shor's algorithm have arrived. The day when this happens has been referred to as "...
2
votes
2
answers
211
views
Breaking the Even-Mansour Cipher with Quantum Period Finding: Probability of unwanted collision
The paper Breaking Symmetric Cryptosystems using Quantum Period Finding shows how to break the Even-Mansour Cipher using Simon's algorithm. The Even-Mansour uses two keys $k_1, k_2$ and a random ...
0
votes
2
answers
607
views
Are there any full alternatives to RSA that are quantum-resistant
By full alternatives I mean things that can do everything RSA can, namely establish secure security without privately sharing information prior. Something which AES can't do.
In other words, I'm ...
2
votes
1
answer
267
views
Does triple ChaCha20 have 256-bit post-quantum security?
Experts suggested 3DES when AES wasn't developed yet, since meet-in-the-middle attack, they suggested triple DES. Grover's algorithm, a quantum algorithm, weakens symmetric encryptions, how about ...
6
votes
3
answers
9k
views
Can Quantum Computers crack RSA and AES?
Im trying to learn more about cryptography and ran into a post, Is AES-128 quantum safe?, which asks if AES-128 is safe. From the articles and replies it seems that AES-128 (symmetric key) is safe ...
1
vote
0
answers
54
views
Is Proof-of-Authority (PoA) protocol a post quantum consensus?
Is PoA persistent against quantum attacks? If not, How can we make it post quantum?
I mean the PoA used with blockchains that delivers comparatively fast transactions through a consensus mechanism ...
0
votes
1
answer
157
views
Do multiple keys mitigate Grover algorithm?
Grover, a quantum algorithm, weakens AES and ChaCha20. Is it possible to use multiple symmetric keys to encrypt a message multiple times to achieve 256-bit security for quantum computers?
4
votes
1
answer
139
views
Difficulty of Shor's algorithm in a Schnorr group as a function of the modulus
Consider a Schnorr group with order a prime $q$ sized for security against current computers (like $q$ of 256 bit); modulus a prime $p=q\,r+1$ large enough (e.g. 3072 to 32768-bit) that the algorithms ...
0
votes
1
answer
189
views
Solve discrete logarithm with new chinese research
Does this research also work for breaking bitcoin ECDSA? If so, how many qubit will be needed for 256-bit elliptic curve key?
6
votes
1
answer
1k
views
How many qubits can break NIST P-521 ECC?
NIST P-521 has the longest key size for standardised ECC, which has 521 bits instead of 512. If a quantum computer is available, how many qubits can break P-521?
1
vote
1
answer
372
views
Quantum computer threats to modern cryptography
I am having a university assignment that requires me to study on the threats that quantum computer poses to modern cryptography.
At the moment, I know that modern symmetric encryption will reduce ...
2
votes
1
answer
153
views
How easy is it to know how many preimages an image might have, given that there's at least one (preimage, image) pair?
I have been considering an approach to incentivize cryptocurrency miners to verify claims of quantum computational supremacy. Briefly, miners find collisions $f(x_1)=f(x_2)=y$ of some known $f:m+1\...