# 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.

77 questions
Filter by
Sorted by
Tagged with
27 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
53 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 ...
67 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 ...
41 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
46 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 ...
107 views

1 vote
50 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 ...
1 vote
59 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 ...
125 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 ...
147 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
173 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 ...
1 vote
64 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
53 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 ...
136 views

617 views

### Can an adversary distinguish a private key from a pseudo-random string of the same length?

Apologies if this is a dumb question but allow me to describe the dilemma I have: Suppose that I am protecting a private key on a device using a password & PBKDF2. The obvious attack would be an ...
682 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? ...
$G$ is a PRNG used in a stream cipher and defined in the following way: G receives $s_0$ as an input, which is a random string drawn from a uniform distribution. The output of step $i$ is $s_i = (s_{... 2 votes 1 answer 277 views ### A confusion on the proof of Yao's theorem (Yao 82) I'm reading the proof of Yao's theorem on Boaz Barak's lecture, the main part of the proof is the following claim: My question is: How can we say "without loss of generality" here? Since$H^i$... 5 votes 1 answer 353 views ### Does concatenation of two pair computational indistinguishable distributions still indistinguishable? Let$X,X',Y,Y'$be some distribution ensembles such that$X\sim X'$and$Y\sim Y'$, where$\sim$means computational indistinguishable. Define$(X,Y)$be the distribution ensemble over$\{0,1\}^{2n}$... 2 votes 1 answer 112 views ### Distinguishing two sets of pseudorandom values when their keys differ by one Suppose we use a pseudorandom function$PRF$and a random key$k$to generate a set of pseudorandom values:$\forall i, 1\leq i \leq n: w_i=PRF(k,i)$Now, consider instead of picking a fresh key, ... 2 votes 2 answers 3k views ### Understanding the distinguisher for a PRG Given the following definition of a psuedorandom generator, I'm having trouble understanding what exactly the "distinguisher" D is outputting, and when? 1 vote 1 answer 256 views ### PRF that can be distinguished after$k\$ queries? 