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
0answers
36 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
0answers
36 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
1answer
102 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\...
3
votes
1answer
155 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 ...
2
votes
1answer
37 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, ...
0
votes
0answers
24 views

How does known-key-distinguisher work?

I read about sercurity section of AES in wikipedia. It wrote "In November 2009, the first known-key distinguishing attack against a reduced 8-round version of AES-128 was released as a preprint......
2
votes
1answer
60 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
1answer
47 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
1answer
46 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 ...
2
votes
1answer
106 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
0answers
133 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
1answer
158 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
1answer
61 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
1answer
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 ...
4
votes
1answer
128 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
2answers
4k 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 ...
1
vote
0answers
32 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
1answer
284 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
2answers
144 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
922 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
205 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 ...
7
votes
0answers
132 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
105 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
216 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
387 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
152 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
312 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
94 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
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
0answers
244 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
62 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
113 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
1answer
1k 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 ...
1
vote
0answers
155 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
368 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
854 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
309 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
107 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
294 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
209 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
586 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
646 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
805 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
256 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
334 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
108 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, ...
1
vote
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?
1
vote
1answer
244 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
233 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
124 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 ...