Skip to main content

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.

Filter by
Sorted by
Tagged with
4 votes
0 answers
39 views

Comparing quantum computing ressources 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 ...
fgrieu's user avatar
  • 142k
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 "...
Mark S's user avatar
  • 289
0 votes
2 answers
557 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 ...
blademan9999's user avatar
2 votes
1 answer
253 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 ...
Flan1335's user avatar
  • 361
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 ...
cryptoman534345's user avatar
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 ...
Alireza's user avatar
  • 109
0 votes
1 answer
156 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?
Flan1335's user avatar
  • 361
4 votes
1 answer
136 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 ...
fgrieu's user avatar
  • 142k
0 votes
1 answer
186 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?
user avatar
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?
Flan1335's user avatar
  • 361
1 vote
1 answer
359 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 ...
Hern's user avatar
  • 159
2 votes
1 answer
146 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\...
Mark S's user avatar
  • 289
16 votes
2 answers
4k views

New paper claims quantum polylog time attack on AES

It is well known that Grover's algorithm can solve AES in $O(\sqrt{n})$ time, which is why symmetric key length needs to be double to maintain their security level in the face of a quantum adversary. ...
lamba's user avatar
  • 1,365
0 votes
1 answer
782 views

Why are quantum-proof cryptography algorithms being developed?

I noticed some new quantum cryptography algorithms are being developed. I know very little about quantum computing but my understanding is that it will just be a much more powerful computer and ...
david_adler's user avatar
4 votes
0 answers
140 views

Are Memory-Hard Functions de-facto quantum resistant?

Searches have returned absolutely no results on this question. With that in mind, I assume the answer is either painfully obvious ('of course quantum computers get no advantage when it comes to ...
user7778287's user avatar
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 ...
cryptobeginner's user avatar
0 votes
1 answer
222 views

AES and quantum computing

I am trying to understand the AES-256 encryption algorithm as it would be implemented on a gated quantum computer (actually, a simulator), and I am having some trouble understanding the theory behind ...
Robert Singleton's user avatar
5 votes
1 answer
2k views

Factoring 2048-bit integer with quantum computer?

In this paper, there is a statement in the abstract: Our construction uses $3n + 0.002n \log(n)$ logical qubits, $0.3n^3 + 0.0005n ^3\log(n)$ Toffolis, and $500n^2 +n^2 \log(n)$ measurement depth to ...
NB_1907's user avatar
  • 640
1 vote
1 answer
119 views

Can an adversary distinguish QROM from ROM with a single query?

I acknowledge that QROM differs from ROM (which can be considered as a specific QROM which performs a measurement to the input). For example, one can find a preimage for an arbitrary value with $O(N)$ ...
Henry's user avatar
  • 55
0 votes
1 answer
96 views

QKD measuring qubit with wrong bases

I'm trying to end the research work for my master thesis about BB84 QKD (and QBC) and a basic problem of quantum mechanics is blocking me. I'm trying to do a probability calculus of the action of ...
VitoShade's user avatar
4 votes
1 answer
171 views

A question about performing quantum computations on uniform superpositions

Let us consider the following situation. Let $U_f$ be a gate computing $f$ mapping $\{0,1\}^n$ to $\{0,1\}^n$. That is, $U_f\left\vert x,0^n\right\rangle=\left\vert x,f(x)\right\rangle$. Let $\left\...
Henry's user avatar
  • 55
5 votes
1 answer
186 views

What are the misconceptions of IBM's CEO Arvind Krishna talk on the "Axios on HBO" about the quantum computing

IBM CEO Arvind made a talk in HBO's Axios program. It seems that there are misconceptions/misleading/flaws in reasoning etc. What are those! Some of the details of the speech is given as; IBM says ...
kelalaka's user avatar
  • 49k
2 votes
1 answer
623 views

What is the current situation of quantum computers?

Like other research areas of cryptography, quantum computing consists of hidden and open fractions. Apparently, we can't say certain things about governments' capabilities where academical or ...
NB_1907's user avatar
  • 640
2 votes
0 answers
70 views

What are some "must-read" papers for someone getting into Quantum Cryptography? [closed]

I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography. I'm interested in Quantum Cryptography and would ...
CSSTUDENT's user avatar
  • 121
2 votes
1 answer
146 views

Differences between Extractors and Privacy Amplification for Quantum Random Generators

We know that for the last step of QRNG: we need to separate quantum and classical noises from each other so we use extractors, after extractor we need privacy amplification step. At this point: if ...
quest's user avatar
  • 21
4 votes
1 answer
2k views

Is Mega.nz encryption vulnerable to brute force cracking by quantum computers?

I am interested in Mega.nz cloud storage. It is using end-to-end encryption. It says that it uses AES-128 to encrypt files And there are more details in their white paper But I saw that quantum ...
le menhir's user avatar
0 votes
0 answers
96 views

Using two or more encryption algorithms together, how do we compute the strength of the final encryption?

If two or more encryption algorithms are used together, how do we compute the strength of the final encryption? And how would the application perform against quantum computers? The first two tables ...
AED ER's user avatar
  • 11
1 vote
1 answer
221 views

Are MAC algorithms and digital signatures secure from quantum computers? If not, why?

I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm, and understand that symmetric encryption is somewhat quantum-resistant as long as the key-length is ...
CyberCrusader's user avatar
1 vote
0 answers
56 views

Spontaneous parametric down-conversion [closed]

we generate heralded single pho- tons via spontaneous parametric downconversion using a 5 mm long periodically-poled potassium titanyl phosphate (ppKTP) crystal pumped with a 405 nm diode laser (200 ...
Rasha rashed's user avatar
1 vote
1 answer
1k views

How Does Prime Factorization Break ECDSA?

I have heard that ECDSA will be broken in the not-to-distant future (roughly 15-25 years) by Quantum Computers running Shor's Algorithm. However, to my understanding, the only purpose of Shor's ...
Alexander Pellegrino's user avatar
2 votes
1 answer
226 views

Is there a notion of "computational security" in quantum cryptography?

In classical cryptography, security proofs are often based on the (assumed) computational hardness of some mathematical problem. Using the principles of quantum mechanics might provide means to design ...
jgerrit's user avatar
  • 51
2 votes
2 answers
215 views

Quantum Cryptography Algorithms Implementations

The Post Quantum Cryptography is a type of cryptography that lies on physics properties instead of mathematics , it has many algorithms and implementations like NTRU , McEliece , SIDH ... etc But ...
Karam Mohamed's user avatar
0 votes
2 answers
442 views

Post-Quantum cryptography usability in IoT devices

My question is very simple. Can I use Post-Quantum encryption/decryption algorithms in IoT devices such as RaspberryPi, Arduino etc, or should the hardware infrastructure obey in quantum logic?
someone's user avatar
  • 29
20 votes
1 answer
5k views

How does IBM's 53-bit quantum computer compare to classical ones for cryptanalytic tasks?

IBM just announced "a new 53-qubit quantum computer". How does it compare to classical computers, performance-wise, for cryptanalytic tasks? E.g. finding a 48- or 64-bit value whose SHA-256 has a ...
fgrieu's user avatar
  • 142k
0 votes
2 answers
333 views

How Will Quantum Computing Change Cryptography's Future? [closed]

Quantum computing is at the intersection of math, physics, and computer science. It seems so complicated that only large organizations could build such algorithms and have their own quantum computing ...
R1w's user avatar
  • 1,960
0 votes
1 answer
436 views

current state of 3-SAT problem?

In this paper, a quantum algorithm to solve the 3-SAT problem in linear time is presented. Is it true? Did the author make a mistake? What state-of-the-art algorithms exist for this problem?
OneUser's user avatar
  • 133
3 votes
2 answers
3k views

Is using quantum computing to break passwords non-sense?

I understand the concept of 'trying all possibilities at once' but can anyone explain this with respect to the fact that my PC only accepts one password at a time? There's no input field that accepts ...
Niels's user avatar
  • 133
1 vote
1 answer
414 views

What is Quantum Cryptography?

When it comes to exchanging secure information over an insecure channel, this approach is considered. It all depends on the nature of photons in which the third polarization is focused. It can easily ...
R1w's user avatar
  • 1,960
11 votes
2 answers
3k views

Can quantum computers put computer security in jeopardy?

There are many articles about quantum computers describing how powerful they are in computing and that they can solve very complicated equations in a short time. One of the biggest security measures ...
R1w's user avatar
  • 1,960
17 votes
0 answers
425 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
forest's user avatar
  • 15.3k
15 votes
3 answers
7k views

Can or can not D-Wave's quantum computers use Shor's and Grover's Algorithm to find encryption keys? Why?

I read that a company called D-Wave Systems has and is manufacturing quantum computers of 128 qubits. Can they or can they not use Shor's and Grover's algorithms for finding RSA-keys? If they can't ...
user128226's user avatar