# Tagged Questions

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.

45 views

### Is this PRG secure?

$G$ is a safe 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? ...
664 views

73 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}$ ...
212 views

### Is there a formal definition of what a distinguisher is?

I've often been reading about (polynomially bounded) distinguishers in books or papers. Although by name and intuition it is somewhat clear what a distinguisher is and does, but i am asking myself ...
96 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?
2k 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,...
72 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-...
263 views

### Computation indistinguishability questions

The definition I have is: Two probability ensembles $X = \{X_n\}_{n \in \mathbf{N}}$ and $X = \{Y_n\}_{n \in \mathbf{N}}$ are computationally indistinguishable if for every probabilistic polynomial-...
88 views

### Computational indistinguishability: are function parameters known?

I would like to clarify something about the definition of computational indistinguishability and pseudorandom number generators. Suppose we wanted to show that linear congruential generators of the ...
81 views

### Distinguishing between two probabilities and the uniform probability

Say I have a polynomial adversary $A$ that can distinguish with a non-negligible adventage between $x$ generated from a probability $X$ and $y$ generated from a probability $Y$. Obviously, this ...
184 views

### Computational indistinguishability with Example

Based on computational indistinguishability definition no PPT algorithm can distinguish $X$ from $Y$, where $X=\{X_n\}_{n \in N}$ and $Y=\{Y_n\}_{n \in N}$ are ensembles of probability ...
171 views

### How to construct a next bit predictor from a distinguisher

I read the claim, without proof, that it is possible to construct a next bit predictor for any PRNG given an oracle distinguisher for that PRNG and vice versa. How do I prove that? A distinguisher ...
160 views

### Why is DDH not hard over $\mathbb{Z}^*_p$?

Why is Diffie-Hellman key exchange not hard over $\mathbb{Z}^{*}_p$?