Questions tagged [distinguisher]
A distinguisher describes an adversary's advantage. In cryptography, an adversary's advantage is a measure of how successfully it can attack a cryptographic algorithm, by distinguishing it from an idealized version of that type of algorithm.
84
questions
0
votes
0
answers
76
views
Distinguishing between two DDH-like tuples
Given a group generator $g$ (in a group where DDH is hard). Let $X_1=g^{x_1}$ and $X_2=g^{x_2}$ be two public elements, where $x_1$ and $x_2$ are selected randomly and kept secret.
Consider a game ...
- 99
0
votes
0
answers
73
views
Having trouble providing a distinguisher proving this hash function is not collision-resistant
As suggested by the title, I'm working on an exercise where I'm given a hash function $H$ that takes in an input string $x$. I'm supposed to construct a distinguisher that proves $H$ isn't collision-...
- 19
1
vote
1
answer
99
views
Unbounded distinguishers and statistical indistinguishability
In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two ...
- 443
2
votes
1
answer
67
views
Reduction from Distinguisher to Indishtinguishability
Content and Informal Problem
Suppose a protocol $\pi$ doing an arbitrary task between two users A and B. I only know that $\pi$ relies on a IND-CPA symmetric encryption scheme $\mathcal{E} = $(KeyGen, ...
- 13k
3
votes
2
answers
175
views
Privacy intuition vs formal definition
Suppose we define privacy as a game where a machine $M$ has a coin $b$, and on input $M_0, M_1$ always replies with encrypted $M_0$ if $b=0$ and encrypted $M_1$ if $b=1$. The adversary can send as ...
- 23.9k
3
votes
2
answers
178
views
How to distinguish X25519 output from random?
Suppose that Alice has an X25519 key pair $\{S_A,P_A\}$ (secret and public key, respectively). Using randomly selected X25519 public keys $\{P_*\}$ (such that $P_A\notin \{P_*\}$), Alice calculates ...
- 257
1
vote
1
answer
88
views
Computing the advantage when checking PRF
I am reading a pdf on pseudorandom function I found here https://www.cs.utexas.edu/~dwu4/courses/sp21/static/reductions.pdf
My problem/struggle is with the computation of the distinguisher's $B$ ...
- 3,188
2
votes
1
answer
191
views
Example of not computationally indistinguishable
All the examples that I see for proving that two distributions are not computationally indistinguishable involve a pattern: choose a Distinguisher $D(\cdot)$ such that $D(x)$ is $1$ if $x$ satisfies ...
CommunityBot
- 1
2
votes
0
answers
86
views
Noise flooding with Renyi divergence
According to this question, I found papers that deal with noise flooding with Renyi divergence. However, the answer is still unclear to me on how to use Renyi divergence on the noise flooding ...
- 2,595
1
vote
1
answer
75
views
An unconditional proof of a PRP by restricting adversary run time
I am a Ph.D. student studying CS theory, I made this account for this question.
Recently, I seem to have obtained a proof of existence of a PRP (which is unconditional in the sense that it does not ...
- 13k
5
votes
4
answers
469
views
Reductionist proofs of computational problems to decisional
Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to ...
- 2,595
2
votes
1
answer
111
views
How small is the negligible advantage for DDH?
The well known Decisional Diffie Hellman assumption (DDH) assert that for any $n = \log q$ and generator $g$ of $\mathbb{Z}_q$, for uniformly i.i.d $A, B, C \sim U(\mathbb{Z}_q)$, the following are ...
- 113
12
votes
1
answer
5k
views
What is it meant by a "hybrid argument"?
Can anyone explain (or point to a reference for) what a hybrid argument is in a security proof, and when it's convenient or preferable to use it?
Among some of the places where I've seen it mentioned,...
- 111
0
votes
0
answers
48
views
PRGs from OW functions
Given a OW function $f:\{0,1\}^n\to\{0,1\}^n$ with hardcore predicate $h(x)$, you can build a PRG $G$ by setting $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$
The expansion condition for $G$ ...
- 48.5k
1
vote
0
answers
80
views
Showing that $F'(k, x) := F(F(k, 0^{n}), x)$ is a PRF [duplicate]
I wanted to do some practice on security reduction proofs, and I am stumped on this one from the Boneh-Shoup book.
If $F(k, x)$ is a secure PRF, then show that $F'(k, x) := F(F(k, 0^{n}), x)$ is a ...
- 43
4
votes
1
answer
128
views
Distinguishers and next bit predictors without the uniform distribution
Consider a probability distribution $D$ over $n$ bit strings. Denote $U$ to be the uniform distribution over $n$ bit strings and $U_{n}$ to be the uniform distribution over integers $\{1, 2, \ldots, n\...
- 22.5k
1
vote
1
answer
260
views
Proof of (in)distinguishability based on DDH/CDH/DL
I am wondering whether or not it is known that the following problem is computationally infeasible while working in a group for which the DDH (or CDH or DL) assumption holds (as usual, g is a group ...
CommunityBot
- 1
3
votes
1
answer
174
views
How many encryptions are needed before OpenPGP key privacy is violated?
According to an excellent answer describing the pitfalls of key privacy in OpenPGP:
Theoretically, an all-zero key ID can be used as a way to discourage traffic analysis, but this is not a complete ...
- 15.3k
1
vote
1
answer
2k
views
Why is DDH not hard over $\mathbb{Z}^*_p$?
Why is Diffie-Hellman key exchange not hard over $\mathbb{Z}^{*}_p$?
- 48.5k
2
votes
1
answer
42
views
In SKE, can we assume without loss that the ciphers of a fixed plaintext distribute identically?
Let $(KG,D,E)$ be a symmetric encryption scheme. Fix $sk\gets KG(\lambda)$ and an arbitrary plaintext $m$.
Generally speaking, $E_{sk}$ is not deterministic, so that $E_{sk}(m)$ is a random variable, ...
- 13.2k
2
votes
1
answer
102
views
Why the differential cryptanalysis complexity is linear with inverse of the probability while linear cryptanalysis is quadratic with the bias inverse?
I am trying to understand the analysis of the complexity of Differential Cryptanalysis versus the complexity of linear cryptanalysis.
In differential cryptanalysis the number of required texts is $\...
- 147k
1
vote
1
answer
511
views
Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0
I have 4 functions to analyze. I need to determine if they are or are not pseudorandom and give a proof/counterexample. I'm having trouble just determining if they are - let alone proving or giving ...
- 3,132
1
vote
1
answer
98
views
Given an input x, can a distinguisher D output 1/2?
Consider a PPT distinguisher $D$. Now if I give it an input (a bit string) $x$, it outputs 1 if $x$ ends with $1$ and $0$ otherwise. We know such a distinguisher exists and is often given as an ...
- 27.8k
2
votes
1
answer
124
views
why do we take computational distinguishability over ensembles
In the Cornell lecture notes, computational indistinguishability is defined as
Definition 69.4 (Computational Indistinguishability). Let $\{X_n\}_n$
and $\{Y_n\}_n$ be ensembles where $X_n$,$Y_n$ are ...
- 46k
1
vote
0
answers
178
views
Does a distinguisher for an PRF based on a hash make the hash function insecure?
I recently found a distinguisher for the PRF $f(s, i) = H(s || i)$ where $s$ is the seed and $i$ is a counter and $H$ is a cryptographic hash function, which is able to distinguish $f(s, i)$ from true ...
- 3,132
1
vote
1
answer
2k
views
Definition of a distinguisher
In Introduction to Modern Cryptography by Katz and Lindell, p. 70, they define a pseudorandom generator by:
Let $l(\cdot)$ be a polynomial and let $G$ be a deterministic
poly-time alg. s.t. for ...
- 3,132
7
votes
0
answers
207
views
Does the bias in RC4 drop asymptotically further in the keystream?
It's well-known that the RC4 keystream has significant biases that become less prominent later in the keystream. The most severe bias is in the second byte, which has a 128-1 bias towards zero. Other ...
- 15.3k
2
votes
0
answers
205
views
How does a hybrid argument work relating to PRG's?
How does a hybrid argument work relating to PRG's?
I am working on a homework assignment where the problems say to use a hybrid argument to prove/disprove that something is a secure PRG, and I can't ...
- 121
1
vote
1
answer
76
views
Simulating a joint distribution of an *almost* deterministic function
The following is in the context of secure MPC.
Suppose that there is a functionality $f(x,y)$ which outputs 'answer' with probability $1-\textrm{negl}(n)$ for some security parameter $n$, and 'other ...
- 141k
1
vote
1
answer
57
views
I want to know the hardness of computing a or b given $g^{b^{-1}}$ and ab in cyclic groups with large prime order
$G$ is a multiplicative cyclic group of a large prime order $p$ and $g$ is a generator of $G$
Theorem 1: Given $g^{b^{-1}}$ and $ab$, it's hard to compute $a$ or $b$, where $a$ and $b$ are randomly ...
- 147k
2
votes
1
answer
1k
views
Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?
If $F$ a PRF, and we construct $G$ using $F$ in the following way:
$$G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$$
where $|s|= n$.
Is $G$ then a PRG? If so how can I prove this? If not how can $G(s)$ ...
CommunityBot
- 1
4
votes
1
answer
158
views
Distinguishing between a Polynomial and a Laurent Polynomial
Let $f(x) \in \mathbb{Z}_p[x]$ (for a prime $p \gg d$) be a polynomial of degree $d$, and let $g(x)$ be a Laurent polynomial with the same degree and only the first negative exponent term ($g(x) = \...
- 269
18
votes
2
answers
5k
views
A website that identifies an RNG from its output
This happened during a discussion of RNG entropy, and the difficulty of verifying the level of entropy in a long sequence of bits (e.g. a private key.)
A colleague of mine told me about a website ...
- 92.6k
6
votes
0
answers
827
views
Is this PRG secure?
$G$ is a secure PRG in range $\{0,1\}^n\rightarrow\{0,1\}^{n+1}$.
Let us define $G'(S)=G(S\oplus G(S)_{1,...,n})$, s.t. $G(S)_{1,...,n}$ is the first n bits of $G(S)$.
Is $G'(S)$ a secure PRG?
...
- 46k
1
vote
0
answers
50
views
Computationally indistinguishably vs Perfect Indistinguishably [duplicate]
I know that perfect security means absolutely no information about the plaintext is leaked to the adversary while computational secrecy is okay with a tiny amount of leak.
But, what is the difference ...
- 111
2
votes
2
answers
400
views
Is there only one formula for the statistical difference between a pair of distribution ensembles?
Statistical closeness implies computational indistinguishability was recently posed. It revolves around a numeric value $\Delta(n)$ of the statistical difference between a pair of distribution ...
- 3,188
8
votes
2
answers
2k
views
Statistical closeness implies computational indistinguishability
This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness.
We say that two ensembles $X_n$ and $Y_n$ are statistically close, if
$$ \Delta(n) ...
- 3,188
0
votes
1
answer
302
views
CCA security of this scheme
Let $k$ be uniformly sampled from $\{0,1\}^\lambda$, $F$ be a secure PRP with block length $\lambda$ and let $Enc(k, m)$ be such that it returns $c = (F(k,r), r \oplus F(k,m))$ with $r$ uniformly ...
- 111
-1
votes
1
answer
144
views
Probability distribution of bitwise-&
Does the bitwise-& between two uniformly distributed input produce an output that seems uniformly distributed ? To be more specific, assume to take x and y uniformly from {0,1}^n and compute z = x ...
- 15.4k
1
vote
1
answer
274
views
How to define the statistical distance between two probabilistic algorithms?
Let
$$
\begin{aligned}
F_{i} \colon \{\, 0,1 \,\}^* \times \{\, 0,1 \,\}^* &\to \{\, 0,1 \,\}^* \\
(k, x) &\mapsto y \\
\end{aligned}
$$
for $i \in \{\, 1,2 \,\}$.
As we known, for every ...
CommunityBot
- 1
4
votes
1
answer
432
views
How to define the statistical distance between two functions?
The statistical difference between two families of distributions of random variables:
Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of ...
- 1,622
4
votes
1
answer
424
views
Hashing a counter to prevent distinguishers in CTR mode
Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data ...
- 141k
0
votes
1
answer
197
views
Is there distinguisher?
Are these distributions computationally indistinguishable ?
$f:\{0,1\}^n \to \{0,1\}^n $
$\{X_n\}_{n\in N}$ : uniform distribution for function which $f(0^n)=0^n$ and for other function probability ...
- 11
1
vote
0
answers
169
views
Is this a PRP? How can I create a distinguisher to show it isn't?
Consider the keyed permutation $F_k : \{0,1\}^2 \to \{0,1\}^2$ with two-bit keys defined as $F_k(x) = k\oplus x$.
Is this F a PRP? How can I create a distinguisher D and calculate the difference ...
- 17.9k
23
votes
1
answer
2k
views
Distinguishing x25519 public keys from random?
I recently read a piece of protocol that avoided sending ephemeral x25519 keys in the clear as an effort to foil deep-packet inspection.
I understand that x25519 public keys are effectively 255 bits, ...
- 12.5k
2
votes
0
answers
318
views
An XTS penguin?
I stumbled across a VPN website when looking up information about XTS, and came across their own explanation of different block modes (basically the ECB penguin, but with their company logo instead). ...
- 15.3k
1
vote
0
answers
65
views
Are there any references on using neural networks to distinguish CSPRNGs?
No feasible algorithm should be able to distinguish the outputs of two CSPRNGs. Are there any research papers that present results of actually testing this?
In particular, I'm interested in ...
- 17.9k
1
vote
0
answers
186
views
Difficulty of finding partially matching ciphertexts for a given plaintext when encrypted with two different keys
I'm trying to find a simple, practical proof-of-work scheme based purely on encryption (due to wide availability of optimized, hardware accelerated AES execution on most platforms, including modern ...
- 48.4k
15
votes
4
answers
2k
views
Are any of the major asymmetric ciphers distinguishable (EG, RSA, ECC)?
Related to "Is it possible to derive the encryption method from encrypted text?".
Given ciphertexts generated by any of the major asymmetric ciphers (RSA, ElGamal, ECC, etc..) can these ciphertexts ...
CommunityBot
- 1
3
votes
0
answers
487
views
Understanding hybrid arguments in detail
Assume we are given three distributions $H_{1}$, $H_{2}$ and $H_{3}$ and the following security games:
$Game_{1}$: Distinguish between $H_{1}$ and $H_{3}$.
$Game_{2}$: Distinguish between $H_{1}$ ...
CommunityBot
- 1