44
votes
Accepted
Are cryptographic hash functions quantum secure?
It is a bit dubious to claim that hash functions "are not based on any hard problem": inverting a standard hash function, or finding a collision, is itself a very hard problem.
The point of ...
44
votes
Accepted
Does Terra Quantum AG break AES and Hash Algorithms?
The onus is on the company to prove their claims, especially when they are extreme. There is also no financial motivation to not prove their claims. I can understand if they say that they want to keep ...
23
votes
Which elliptic curves are quantum resistant?
Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the ...
23
votes
Accepted
Are hash functions strong against quantum cryptanalysis and/or independent enough of mathematics?
This depends on what kind of hash function you mean and what kind of security you want.
Poly1305 is an almost-universal hash family, which, when used with a uniform random key for a single message, ...
22
votes
Why are only lattice problems used in cryptography?
What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard.
What is required for cryptography is average-case hardness --- i.e., a randomly selected ...
21
votes
Accepted
How many qubits are required to break RSA 2048 or 4096 with a universal quantum computer?
How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer?
Like the answer you linked to shows, about $\log_2(N^2) = 2 \log_2(N)$ or just $2n$ where $n$ ...
20
votes
Why NIST insists on post-quantum standardization procedure rather than post-quantum competition?
Is there any functional difference on how this process is conducted?
One likely difference is the intended end goal. The intended result of the AES process was to approve exactly one proposal, and ...
19
votes
Accepted
New quantum attack on lattices (or Shor strikes again)?
As mentioned in the comments, there is a serious flaw in the paper, and it has been withdrawn: see https://groups.google.com/forum/#!msg/cryptanalytic-algorithms/WNMuTfJuSRc/OtQMLRXgBwAJ and part (3) ...
19
votes
Accepted
Is lattice-based cryptography practical?
Yes, it is feasible. In fact, the NIST post-quantum submissions include a number of lattice-based cryptographic key exchange and signature protocols. As you can see from a summary of the different ...
17
votes
Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512
With a 1024 qubit quantum computer you cannot break any of the algorithm you mentioned.
Current estimations for an impelmentation of Grover's algorithm for AES requires much more qubits. According to ...
16
votes
New quantum attack on lattices (or Shor strikes again)?
The authors themselves point out that this doesn't break lattice-based assumptions used in crypto. To quote:
Lattice problems have received enormous attention in recent years, mainly because of ...
16
votes
New paper claims quantum polylog time attack on AES
There is an answer on the PQC mailing list by Xavier Bonnetain (https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/orySwdhmjH8/m/ScE8G_ajBgAJ) which I will copy below:
The algorithm begins but ...
15
votes
Accepted
Are post-quantum cryptographic ciphers *also* secure if the P=NP conjecture holds true?
Do the post-quantum ciphers also automag/tically address the 1st problem?
Not really, however to explore that in any detail, we need to explore what the 1st problem is.
If $P=NP$ is proven true, ...
15
votes
New quantum attack on lattices (or Shor strikes again)?
Unless I misunderstood the definitions, an algorithm for the problem in Definition 1 (i.e. their main result) is in fact enough to attack decision-LWE if the noise is small. The fact that they need a ...
15
votes
Does Terra Quantum AG break AES and Hash Algorithms?
Edit 2021-02-10: covering now their latest press release
Red flags
While the details of their work/claims are yet to be published, this article is containing a lot of conspicuous statements.
Vinokur ...
14
votes
Accepted
Why is pqRSA in the NIST PQC submissions?
[source of information: my interpretation of multiple hallway chats I've had with DJB and Tanja Lange at conferences]
The actual NIST PQC submission was for two reasons:
A joke. Evidence1: DJB ...
14
votes
Accepted
Is this variant of Diffie-Hellman viable and quantum resilient?
Is this actually a viable method of key exchange?
No. An eavesdropper can find the integer $b$ chosen by Bob from $x$ (as sent by Alice) and $b'$ (as sent by Bob), and the equation $b'\,=\,b\,x\bmod ...
13
votes
How will Cryptography be changed by Quantum Computing?
Current symmetric cryptography and hashes are actually believed to be reasonably secure against quantum computing. Quantum computers solve some problems much faster than the best known classical ...
13
votes
Which elliptic curves are quantum resistant?
What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's ...
13
votes
Accepted
Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?
No it does not.
Perfect forward secrecy implies that even if you retrieve the private key of the asymmetric key pair that you cannot read any of the past or future messages within a connection. It is ...
13
votes
Accepted
Post Quantum Symmetric Cryptography
AES-256 is still considered the strongest (and is considered secure) as related key attacks are not particular to analysis with quantum computers.
Related key attacks could happen when AES is used ...
13
votes
Accepted
Relation between Key-exchange and Public-Key encryption schemes
First, some definitions.
A public key encryption scheme (PKE) is a scheme with public and private keys, where we can encrypt a message using the public key and decrypt using the private key.
A key ...
13
votes
Current Consensus on Security of Lattice Based Cryptography?
The claimed attack does not "break" lattice-based cryptography, merely further improves known attacks.
I'll try to briefly describe the situation.
Asymptotics:
Asymptotically, our best ...
13
votes
Accepted
New paper claims quantum polylog time attack on AES
I concur with Xavier Bonnetain per lamba's answer, but can add a bit more flesh to what is going on.
Working through the proposed algorithm with an $n$-bit search space, looking for a solution $x$ to $...
13
votes
The death of isogeny-based cryptography?
It's early days to assess the full implications yet, but there is an excellent blog by Stephen Galbraith that seems to indicate that this does not currently apply to all isogeny-based schemes (in ...
12
votes
Is braid-based cryptography proven insecure when looking towards post-quantum cryptography?
I believe that the conjugacy search problem is broken by probabilistic attacks (see chapter 7). I am not sure if this completely ends braid cryptography, however, since there are other difficult ...
12
votes
Accepted
What are the characteristics of a quantum secure protocol?
Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers.
Quantum computers don'...
12
votes
Accepted
Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis)
As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography).
All the field was arguably started by ...
12
votes
Accepted
Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm
It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM.
So here is what you ...
12
votes
Accepted
Discrete Gaussian Sampling role in Lattice-Based Crypto?
A Gaussian distribution satisfies the following desirable properties:
It can be implemented coordinate-wise: If $x_1, x_2, \ldots , x_n$ are each sampled from a one-variable Gaussian distribution, ...
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
post-quantum-cryptography × 594lattice-crypto × 115
signature × 62
public-key × 58
elliptic-curves × 44
hash × 42
hash-signature × 42
encryption × 38
lwe × 37
cryptanalysis × 36
key-exchange × 36
quantum-cryptography × 32
ntru × 31
nist × 30
isogeny × 30
mceliece × 27
rsa × 23
ring-lwe × 18
quantum-cryptanalysis × 18
aes × 17
diffie-hellman × 15
kem × 15
algorithm-design × 13
homomorphic-encryption × 12
collision-resistance × 12