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.

16 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
0 answers

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 ...
forest's user avatar
  • 15.3k
6 votes
0 answers

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? ...
Jjang's user avatar
  • 365
3 votes
0 answers

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}$ ...
EllipticNoob's user avatar
2 votes
0 answers

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 ...
Newbie's user avatar
  • 21
2 votes
0 answers

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 ...
KRob's user avatar
  • 121
2 votes
0 answers

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). ...
forest's user avatar
  • 15.3k
2 votes
0 answers

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) ...
Robert777's user avatar
  • 225
1 vote
0 answers

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 ...
Confused's user avatar
1 vote
0 answers

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 ...
nullUser's user avatar
  • 119
1 vote
0 answers

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 ...
VincBreaker's user avatar
  • 1,484
1 vote
0 answers

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 ...
yellowlive's user avatar
1 vote
0 answers

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) $\...
Mhy's user avatar
  • 398
1 vote
0 answers

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 ...
im_infamous's user avatar
0 votes
0 answers

Distinguishing between two DDH-like tuples

Given a group generator $g$ (in a group where DDH is hard). Let $X_1=g^{x_1}$ and $X_2=g^{x_2}$ be two public elements, where $x_1$ and $x_2$ are selected randomly and kept secret. Consider a game ...
Doron's user avatar
  • 99
0 votes
0 answers

Having trouble providing a distinguisher proving this hash function is not collision-resistant

As suggested by the title, I'm working on an exercise where I'm given a hash function $H$ that takes in an input string $x$. I'm supposed to construct a distinguisher that proves $H$ isn't collision-...
HughJass24's user avatar
0 votes
0 answers

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$ ...
Creeptographer's user avatar