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.

Filter by
Sorted by
Tagged with
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 ...
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-...
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 ...
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, ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 votes
1 answer
112 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 ...
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,...
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$ ...
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 ...
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\...
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 ...
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 ...
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$?
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, ...
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 $\...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1 vote
1 answer
58 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 ...
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)$ ...
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) = \...
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 ...
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? ...
1 vote
0 answers
51 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 ...
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 ...
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) ...
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 ...
-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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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). ...
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 ...
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 ...
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 ...
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}$ ...