Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs
15 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

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
  • 438
11 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.7k
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
4 votes
Accepted

Katz/Lindell - 2.10: Is exhaustive search over the key-space allowed in perfect indistinguishability?

This reasoning is tempting, but it is not sound: “we could have an adversary that just performs exhausting search over the key-space to determine what the cipher text decrypts to.” The problem is that ...
Chris Peikert's user avatar
4 votes
Accepted

Hybrid argument without efficient samplability

This is a very interesting question. I looked around and found a paper called Computational Indistinguishability: A Sample Hierarchy by Goldreich and Sudan. This contains a proof that it doesn't hold.
Yehuda Lindell's user avatar
4 votes
Accepted

Are there different definitions of secure two-party computation?

Defining indistinguishability is very tricky. I actually think that the definition in the book by Evans et al. is too weak, but maybe Mike Rosulek will weigh in. If you define security by saying that ...
Yehuda Lindell's user avatar
3 votes

Ideal cipher vs Ideal encryption scheme

1. Why would having just perfect secrecy/indistinguishability (and not randomness) be enough for encryption schemes but not for block ciphers? 2. On the other side, why can't perfect secrecy/...
Maarten Bodewes's user avatar
  • 92.9k
3 votes
Accepted

What is the definition of function index

A sPRG as defined there describes a family of functions, i.e. a set of many functions $f_I$. The index $I$ identifies one such function from the family and the algorithm $\mathsf{IdSamp}$ describes ...
Maeher's user avatar
  • 6,842
2 votes

Distinguishers and next bit predictors without the uniform distribution

Nice question! This seems to have been addressed in a conference paper also available here by Schrift and Shamir in 1991: A.W. Schrift, A. Shamir, On the universality of the next bit test, Conference ...
kodlu's user avatar
  • 22.6k
2 votes

what's the reason of the notational difference between statistical and computational indistinguishabilities?

You can define statistical security directly in terms of the statistical properties of different distributions. For example, you could define two distributions to be statistically close if their ...
Daniel's user avatar
  • 3,972
2 votes
Accepted

What does the syntax Pr[D = 1] mean?

$Pr[D^{O_i} = 1]$ is the probability that the distinguisher outputs 1 given the actual oracle is $O_i.$
kodlu's user avatar
  • 22.6k
2 votes

Indistinguishability versus Indifferentiability

The definitions of "indistinguishability" and "indifferentiability" were introduced in paper "Indifferentiability, Impossibility Results on Reductions, and Applications to the ...
lalalala's user avatar
2 votes

About the definition of distinguishing advantage and computational indistinguishability

A few things to mention For certain situations, the restriction to binary-output adversaries is (known to be) without loss of generality. The data-processing inequality gives that $\Delta(f(X), f(Y)) ...
Mark Schultz-Wu's user avatar
  • 13.3k
2 votes
Accepted

"randomized" indistinguishability vs "deterministic" indistinguishability

Big caveat that I'm not a probabilist, and your answer really doesn't include much cryptography, so might be better suited for asking a probabilist somewhere (say on math.se or something). As ...
Mark Schultz-Wu's user avatar
  • 13.3k
2 votes
Accepted

Privacy intuition vs formal definition

No information can leak about the input of machine $M$ from the output of machine $M$, in any game. That's because $M$ can be viewed as a probabilistic Turing machine (with no memory of earlier runs), ...
fgrieu's user avatar
  • 142k
2 votes

Definition of Polynomial-Time Indistinguishability

One can have $|X_n|\neq |Y_n|$, or even $|X_n| = f(n) \neq \infty = |Y_n|$ for some function $f(n)$. This occurs in practice, namely in lattice-based cryptography, where $X_n$ is some (ideal) discrete ...
Mark Schultz-Wu's user avatar
  • 13.3k
2 votes

Does Grover's algorithm really threaten symmetric security proofs?

The question as currently written asks whether Grover's algorithm threatens symmetric security proofs. The vacuous answer to this is "no". A proof will operate under an assumption of a ...
James_pic's user avatar
  • 372
2 votes

Showing that CPA encryption schemes cannot preserve the length of a message

I think this should work. Note that no deterministic encryption scheme can be CPA secure; a simple attack is discussed in the book. Next, note that any probabilistic encryption scheme will result in ...
cryptolearner's user avatar
2 votes
Accepted

Hybrid argument for quantum states

Assuming $\mathcal{A}$ can by itself generate copies of $\rho_0$ and $\rho_1$, then yes this is the case. \begin{align*} &\| \mathcal{A}(\rho_0^{\otimes p}) - \mathcal{A}(\rho_0^{\otimes p})\| \...
lamontap's user avatar
  • 925
1 vote

KEM security definition - IND-CCA vs IND-CCA2

Looking at the Wikipedia article, with IND-CCA you get access to the oracle only until the message c* arrives (this is a non-adaptive attack), while with IND-CCA2 you can access the oracle using ...
Eugene Styer's user avatar
  • 1,676
1 vote

Privacy intuition vs formal definition

I’m going to assume that when you say $M$ samples a random permutation, it does so uniformly so that each permutation is equally likely. If this is not the case, then there is information leakage. One ...
Daniel S's user avatar
  • 23.9k
1 vote
Accepted

Unbounded distinguishers and statistical indistinguishability

Statistical indistinguishability implies computational indistinguishability, and in fact this describes a tight upper bound on any distinguishers advantage, unbounded or not. So a distinguisher may ...
Lev's user avatar
  • 443
1 vote
Accepted

Are RSA-KEM key exchange material cyphertexts indistinguishable from random noise?

The RSA function is a permutation from x to c=(x^e)%N. Assuming the plaintext integer x is ...
Richard Thiessen's user avatar
1 vote
Accepted

Security Goal Indistinguishability

I think you are missing the idea of randomness as part of a cryptographic application. It is not possible to create CPA-IND- order CCA-IND-security with a deterministic encryption scheme. Only by ...
Titanlord's user avatar
  • 2,299
1 vote
Accepted

Can the indistinguishability obfuscator leak the password when obfuscating the password checking function?

But can't the indistinguishability obfuscator take any password checking function and return the dumb_checker as the canonical form? No, in order to do so, the obfuscator would have to be able to un-...
haael's user avatar
  • 285
1 vote

How small is the negligible advantage for DDH?

Negligible has a precise meaning in cryptography. It is really defined in terms of growth (or rather, decay), for example, with respect to the security parameter. A function $\mu$ is negligible if it ...
meshcollider's user avatar
  • 1,573
1 vote

Ideal cipher vs Ideal encryption scheme

Why would having just perfect secrecy/indistinguishability (and not randomness) be enough for encryption schemes but not for block ciphers? Block ciphers are primitives. We want them to be a Pseudo-...
kelalaka's user avatar
  • 48.7k
1 vote

What does the syntax Pr[D = 1] mean?

$\newcommand{\pr}{\mathbf{Pr}}$ Another possible intuitive interpretation would be: this means that the behavior of $D$ does not change perceptively. Suppose $D$ outputs 0 or 1. Then, the output ...
AYun's user avatar
  • 849
1 vote
Accepted

Multiple COA-security (IND-EAV-Mult security) cipher

I think that your design will pass the experiment provided that $t$ is small enough that collisions in $r$ occur with negligible probability. However, I also think that your design is KPA, CPA and CCA ...
Daniel S's user avatar
  • 23.9k

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