We’re rewarding the question askers & reputations are being recalculated! Read more.

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
-1
votes
0answers
36 views

Problem regarding computational indistinguishability [closed]

I've been dealing with this question for the last couple of days: Let S0 and S1 be two non-uniform PPT algorithms, and let X = {Xn}n∈N be a distribution ensemble. Assume that X,S0(X) ≈c X,S1(X) , (≈...
1
vote
0answers
19 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 ...
1
vote
2answers
66 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 ...
6
votes
2answers
396 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
1answer
69 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 ...
4
votes
0answers
61 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 ...
-1
votes
1answer
58 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
1answer
112 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
1answer
348 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
1answer
111 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 ...
4
votes
1answer
186 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
vote
0answers
71 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 ...
19
votes
1answer
1k 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
0answers
160 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
0answers
55 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
0answers
124 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 ...
2
votes
0answers
268 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}$ ...
2
votes
1answer
511 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)$ ...
5
votes
1answer
262 views

Computationaly efficient distinguisher for a PRP generator

Let $n$ be an integer (the motivating context had $n\approx2^{27}$). All other lowercase variables are non-negative integers less than $n$ (elements of $\mathbb Z_n$). All uppercase variables are ...
3
votes
1answer
88 views

Are two outputs of a PRF computationally indistinguishable when the keys are somehow related?

This question is related to my previous question “Are two outputs of a PRF computationally indistinguishable when using two different keys??”, but in this question the keys are related. Assume $c_i$ ...
2
votes
1answer
176 views

Are two outputs of a PRF computationally indistinguishable when using two different keys?

Assume we have a pseudorandom function $f(\cdot)$ that maps an input to $\mathbb{F}_p$ where $p$ is a large prime number. Assume $r_1$ and $r_2$ output of the pseudorandom function using two ...
1
vote
0answers
187 views

proving indistinguishability of joint distribution using hybrid argument

Using Hybrid Argument, I want to prove following equivalence: $$\{X,Y,Z\}\equiv \{X',Y',Z'\}$$ by proving following equivalences: $\{X,Y,Z\}\equiv \{X,Y,Z'\}$(1) $\{X,Y,Z'\}\equiv \{X,Y',Z'\}$(2) $\...
2
votes
3answers
446 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 ...
6
votes
0answers
549 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? ...
3
votes
2answers
769 views

Is this simple PRNG secure?

$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
1answer
191 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
1answer
235 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
1answer
86 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, ...
0
votes
2answers
2k 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
1answer
147 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 ...
6
votes
1answer
211 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-...
1
vote
0answers
94 views

2 round GOST_28147-89 cipher distinguisher

So, here is the scheme of how this will look graphically: The deal is to present distinguisher for this cipher. First of all here is my drafts: Way 1 Assume that distinguisher displays in constant ...
7
votes
2answers
1k 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 ...
1
vote
3answers
358 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 ...
1
vote
1answer
149 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 ...
2
votes
2answers
151 views

Distinguishing attack on stream cipher created from a block cipher in counter mode

A block cipher in counter mode creates a key stream by: $$z_i = E_K(IV || i)$$ Where $IV$ is some chosen initialisation vector (with some length $l$ less that $n$ bits) and $i$ is the binary ...
1
vote
1answer
1k 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 ...
5
votes
4answers
400 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-...
2
votes
1answer
4k views

Ciphertext indistinguishability (IND-CPA) for symmetric cryptography

My understanding are these steps are necessary for symmetric cryptography to be IND-CPA: The adversary submits two distinct $M_0$, $M_1$ plain-texts to the challenger. The challenger selects one of ...
5
votes
1answer
319 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 ...
3
votes
2answers
264 views

Reductionist proofs of decisional problems to computational

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 ...
-1
votes
1answer
824 views

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

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

Distinguishing Attack on CBC-MACs

I want to ask again about distinguishing attack on CBC MAC, based on the paper published by Ketting Jia, Xiaoyun Wang, Zheng Yuan, and Guangwu Xu: Distinguishing Attack and Second-Preimage Attack on ...
2
votes
2answers
435 views

Impact of distinguishing between random text and cipher text?

In theory, distinguishing cipher text from random text is considered insecure for any PRP algorithm. Say for example - due to Patarin's proof with about six rounds of Feistel Network - the attacker ...
4
votes
1answer
2k views

Distinguishing attack on CBC-MAC

I want to ask about distinguishing attack on CBC MAC, as in the paper published by Ketting Jia, Xiaoyun Wang, Zheng Yuan, and Guangwu Xu: Distinguishing Attack and Second-Preimage Attack on the CBC-...
4
votes
1answer
192 views

What is the impact of the Goppa code distinguisher on the CFS and McEliece?

What is the impact of the distinguisher for the high-rate Goppa codes (as published in "A Distinguisher for High Rate McEliece Cryptosystems") on the CFS signature scheme and the McEliece/Niederreiter ...
2
votes
0answers
252 views

How can I construct a distinguisher given an inverter?

Let $ PRG: \{ 0, 1\}^n \rightarrow \{ 0, 1\}^{n+s}$ be a pseudo random generator and let $A$ be an inverter that runs in polynomial time, specifically: $\large \mathbb P_{d \leftarrow PRG(U_n)}[ A(d) ...
2
votes
1answer
230 views

Distinguishing joint probability distributions

Assume that we have a probability distribution $P(X,Y)$ for the joint probability of random variables $X$ and $Y$. Let $P(Y, Z)$ be analogous distribution for $Z$ and $Y$. Based on these we can define ...
3
votes
1answer
740 views

How much does a successful Distinguishing Attack “break” the attacked stream cipher?

I started reading about the most recent cryptanalysis of RC4 and it's variants. One of the papers I just finished reading ("Two Linear Distinguishing Attacks on VMPC and RC4A and Weakness of RC4 ...
10
votes
1answer
3k 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,...