14 votes

Does Grover's algorithm really threaten symmetric security proofs?

Yes, but also no. Grover's algorithm is actually quadratically faster than classical algorithms. However there are a few catches. Quantum computers are slow and expensive. This means that in the near ...
Oscar Smith's user avatar
13 votes
Accepted

Impact of Ryan and Heninger's CRYPTO 2023 paper on post quantum cryptosystems

The following is mostly known to lattices people (and mentioned at the end of the Quanta article), but I also reached out to Keegan to clarify some questions I had. There are (roughly) two main types ...
Mark's user avatar
  • 12.5k
12 votes
Accepted

Does Grover's algorithm really threaten symmetric security proofs?

Despite the classical security proof, Grover's algorithm threatens symmetric key cryptography. The main reason is that classical security proof assumes that the adversary makes classical queries to ...
Hhan's user avatar
  • 428
11 votes
Accepted

Could tropical cryptography become another candidate for post-quantum cryptography?

I can think of the following reasons, and maybe further research into these systems can change this situation: When there is a proposed cryptosystem based on a different algebraic system, it is up to ...
kodlu's user avatar
  • 22.1k
10 votes

Does Grover's algorithm really threaten symmetric security proofs?

Does Grover's algorithm really threaten symmetric cryptography? Lov K. Grover's algorithm reduces the key search into $\mathcal{O}(\sqrt{2^n})$ instead of the $\mathcal{O}(2^n)$. What is generally ...
kelalaka's user avatar
  • 48.3k
9 votes

What is meant by software and hardware implementations of cryptograpic schemes? How to do it?

what is mean by software and hardware implementation? I want to know how its been done. Cryptographic Software implementation is coding the cryptographic schemes/algorithms with a programming ...
kelalaka's user avatar
  • 48.3k
8 votes

Does Grover's algorithm really threaten symmetric security proofs?

I'm going to answer the question in your headline and then go forward. No. Grover's algorithm is a canard and you ought to stop worrying about it. The major reason for this is that Grover reduces the ...
Jon Callas's user avatar
  • 2,304
7 votes
Accepted

NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f

In NTRUEncrypt we work with in the ring $\mathbb Z[X]/(X^N-1)$. it looks like for your example you have taken $N=4$. In this ring, multiplying $X$ is equivalent to rotating the coefficients so that in ...
Daniel S's user avatar
  • 23k
6 votes

Rainbow What happened to signatures in the NIST standardization process?

Rainbow was catastrophically broken, taking "a weekend on a laptop" to break.
SAI Peregrinus's user avatar
6 votes
Accepted

Is pairing-based crypto post-quantum secure?

Is pairing-based crypto post-quantum secure? No. That's because solving the Discrete Logarithm Problem in one of the pairing's source groups breaks the pairing's security, and Shor's algorithm ...
fgrieu's user avatar
  • 140k
6 votes

Could tropical cryptography become another candidate for post-quantum cryptography?

Anything can become a candidate for post-quantum cryptography if there has been sufficient cryptanalytic interest in it for long enough that practitioners believe it is plausibly hard to break for ...
Mark's user avatar
  • 12.5k
6 votes

Kyber 512 Security Level Issue

That post spawned a 1.5 month flame war on the NIST pqc google group. You can read through that for some elaboration by Dan on what he meant, but my understanding is that not everyone agrees with him, ...
Mark's user avatar
  • 12.5k
5 votes

Are there any full alternatives to RSA that are quantum-resistant

NIST is currently running a post-quantum cryptography contest for this. Note that they won't standardize one algorithm, but will split Key Encapsulation Mechanisms (KEMs) which exchange symmetric ...
SAI Peregrinus's user avatar
4 votes
Accepted

What is the post-quantum security of encryptions schemes based on transpositions?

Grover's algorithm is an unstructured search algorithm that finds the input to a black box that results in a particular value. It doesn't matter how that black box is constructed, or what operations ...
forest's user avatar
  • 15.2k
4 votes

Do we need the quantum random oracle model (QROM)?

All models are wrong, but some are useful - George Box The random oracle model (ROM) has proven the test of time insofar as it has proven an accurate/useful assessment of an adversaries capabilities ...
Daniel S's user avatar
  • 23k
4 votes
Accepted

Where does the 8 come from? Generic Search Problem with Bounded Probabilities

As the paper states, you should look directly at HRS16, Theorem 1. The proof there seems fairly straightforward, but it seems to depend on theorem 7.2 of Zhandry2012. This itself appears to depend on ...
Mark's user avatar
  • 12.5k
4 votes
Accepted

Quantum attack on CTR

why we have sum over all $x$ here? The difference here is notational. We use the + operator not to mean 'addition with some group operation', but instead that the state can be represented by a ...
poncho's user avatar
  • 146k
4 votes

The weakening of PQC as a result of lack of KEX?

I don't understand your concern. It sounds like you are assuming that public (and private) keys in lattice-based key exchange are static? I don't believe this is the case though. So if your bank (or ...
Mark's user avatar
  • 12.5k
3 votes
Accepted

KYBER.CPAPKE: IND-CCA Security of Lyubashevsky, Peikert, Regev (LPR) Encryption

. It seems like neither KYBER.CPAPKE nor its plain ring analogue are IND-CCA1/2 secure Yes, it's a true statement. You might have already noticed the CPA in the KYBER.CPAPKE name. And your ...
DannyNiu's user avatar
  • 9,080
3 votes
Accepted

What if LWE is not as secure as we think?

There are some alternatives. Mainly they fall into the categories of Coding-based crypto (LPN type things, McCliece, and rank metric codes) Isogeny-based crypto (though this has suffered devastating ...
Mark's user avatar
  • 12.5k
3 votes
Accepted

Regev's proof of quantumly approximating $\sum_{x \in L}\sqrt{{\rho_{r}(x)}}|x\rangle$

(1) I think saying $x\mod\mathcal{P}(L)$ isn't quite right, we should probably say $x\mod L$. Since $L$ is an additive subgroup of $\mathbb{R}^n$, we can take the quotient group $\mathbb{R}^n/L$, and ...
Sam Jaques's user avatar
  • 1,135
3 votes
Accepted

In dilithium (post quantum signature algorithm), how have the authors precomputed the table of zetas for NTT?

I did not try to implement the algorithm myself but those values are powers of $\zeta = 1753 \in \mathbb{Z}_q$ (as hinted by the name) in the Montgomery form where $q = 8380417$ and the elements of $\...
honzaik's user avatar
  • 392
3 votes

Quantum attack on CTR

Disclaimer: I'm one of the authors of the article. poncho's answer is great, but I'd like to just add some additional details that may help you in understanding the article. When describing the ...
Tristan Nemoz's user avatar
3 votes

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

So $R = \mathbb{Z}[x]/(x^n+1)$, where $x^n+1$ is an irreducible polynomial and n is a power of 2. So, this structure would not be a ring anymore, it would be a field. So, why is it called ring and ...
Mark's user avatar
  • 12.5k
2 votes
Accepted

Covering codes for digital signatures

This makes perfect sense in principle. However you will need some extra properties from your covering code. My understanding is that no one ever came up with a family of covering codes having all ...
LeoDucas's user avatar
  • 1,203
2 votes

LWE KEMs and message coding

In the case of lattice-based public-key encryption, the answer is mostly "no". For security reasons, we need $n\geq 512$ (roughly). If we assume the moduli $q$ is a free parameter, then we ...
Mark's user avatar
  • 12.5k
2 votes

Related to ntt implementation in crystal kyber

While not an answer to your question, a little background on DFT/FFT/NTT. If you understand these well, you can write your own implementation without too much trouble. DFT/FFT In a field $\mathbb{F}$...
yoyo's user avatar
  • 391
2 votes
Accepted

In Learning with errors, what is the relation between the size(or standard deviation) of errors and security?

This is a pretty hard topic to concisely summarize. In general, one way to answer your question is The hardness of LWE is precisely what the Lattice Estimator says it is. This is reductive, and ...
Mark's user avatar
  • 12.5k
2 votes
Accepted

Composition of ciphertexts in post quantum schemes Kyber and Frodo

Wouldn't it be sufficient to work with only one, which "hides" the message, that is in Kyber $v$ and in Frodo $C_2$? Actually, they are both taking a similar approach to El Gamal. With El ...
poncho's user avatar
  • 146k
2 votes

Can someone explain in simple terms how coding part and the algorithm itself, of dilithium pqc signature algorithm resemble here?

Conceptually what is happening with this algorithm is simple, so I will describe that first. To simplify things, I will simply write $a\bmod b$ rather than $a\bmod^+b$ or $a\bmod^{\pm}b$. I'll mention ...
Mark's user avatar
  • 12.5k

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