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

74 questions
Filter by
Sorted by
Tagged with
95 views

39 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 ...
42 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 ...
79 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 ...
31 views

### testing for a curve25519 public key

The following suggest that it's possible to test 32 bytes mathematically to determine if they might constitute a Curve25519 public key: Bernstein, Hamburg, Krasnova and Lange 2013 https://safecurves....
124 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 ...
142 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 ...
60 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 ...
52 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 ...
122 views

545 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 ...
622 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? ...
800 views

$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_{... 1answer 243 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$... 1answer 325 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}$... 1answer 105 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, ... 2answers 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? 1answer 227 views ### PRF that can be distinguished after$k\$ queries?

In adaptive attacks, if we design poorly, adversary can modify his queries and break the given pseudo random function (that is being able to distinguish it from uniform randomness). Is there a poor ...
231 views

### Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

When designing SMPC protocols using secret-sharing, it is a common approach to compose a protocol from several sub-protocols (each proven secure under the formal definition of security w.r.t. semi-...