Questions tagged [pseudo-random-generator]

In cryptography, a pseudo-random generator (PRG) is a deterministic procedure that maps a random seed to a longer pseudo-random string such that no statistical test can distinguish between the output of the generator and the uniform distribution. Pseudo-random generators have numerous applications in cryptography. For instance, pseudo-random generators provide an efficient analog of one-time pads.

Filter by
Sorted by
Tagged with
1
vote
1answer
47 views

Pseudo Random Generators

G is a PRG and takes in a seed s. Is G'(s) = [G(s)]' (i.e. the complement of G(s)) a PRG as well? My proof by contradiction: Suppose G' is not a PRG, then G''(s) = [[G(s)]']' = G(s) is also not a PRG ...
0
votes
0answers
53 views

Prove a function G is not a pseudo random generator

A function G(x) = x || x (where “||” denotes string concatenation). It is given that G is not s pseudo random generator. Can someone describe how can we prove this. I am getting a bit confused in the ...
0
votes
1answer
19 views

Relationship between LCGs and LFSRs

Here: https://en.wikipedia.org/wiki/Linear-feedback_shift_register they wrote: The linear feedback shift register has a strong relationship to linear congruential generators What this relationship ...
1
vote
0answers
27 views

How to reproduce seeds in Random Number Generator like WELL, KISS etc

I am curious about Padding the seeds of Random Number Generator. (I am sure that terminology, padding the seeds, is not correct. If someone knows the proper word, please let me know :) ) What is ...
1
vote
1answer
58 views

Getting the plaintext encrypting the ciphertext

Context: an encryption game from overthewire (the link to it: https://overthewire.org/wargames/krypton/krypton6.html, also good for more info) where given the ciphertext, one must obtain the plaintext....
0
votes
2answers
52 views

PRNG based on GF?

Are there any pseudo random number generator based on Galois fields? The source of the AES randomness lies in the GF, so GF should be capable of generating random bits. Why are there no such ...
6
votes
4answers
432 views

A source of randomness that anyone can independently, conveniently and robustly access?

Does there exist a source of randomness that anyone in the world can independently, conveniently and robustly access? For example, the 10th decimal place of the temperature in Mexico City is ...
-1
votes
0answers
44 views

Peusodrandom Generator Properites

I've learnt that a PRG is deterministic and an adversary must not be able to distinguish G(k) from a real random string. I'm asked which of the following derived generators are pseudorandom generators....
0
votes
2answers
171 views

What are the fastest algorithms that sample from the uniform distribution?

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so? I've ...
0
votes
1answer
23 views

Non-overlapping seeded numbers generator for small output range

Seen this, but it's sort of useless as it allows for trivial solutions by increasing the size of the output's space up to a point any hashing function will achieve non-collision. This question is ...
1
vote
1answer
54 views

PRNG generator which could repeats blocks

Let's use AES as stream cipher, and let's use as an input numbers $1,2,3,...$. This way we should get the random blocks and every block will be different from each other. But I have a pseudorandom ...
0
votes
0answers
28 views

How can I recover mersenne twister when only the part of the bits?

https://github.com/tna0y/Python-random-module-cracker Here, when we get 32*624 bits of outputs from Mersenne-twister we can recover Mersenne twister. My question is when we get the parts of the bits, ...
2
votes
3answers
138 views

Can we combine two true random generators to obtain a new one?

It is well known that a true random generator exploits the randomness occurs in some physical phenomena. Also, the output of a true random generators can be either biased or correlated. Therefore, de-...
0
votes
0answers
71 views

Determine if a function is a PRG when PRG concatenated with Seed?

I am a newbie in Cryptography and have trouble to solve the following question. Let $G: \{0,1 \}^n \rightarrow \{0,1 \}^{l(n)}$ be a PRG and $x \epsilon \{0,1 \}^n$. Determine if the function $Z: \{...
1
vote
0answers
27 views

composition of RLWE distributions

Assume we have the polynomial space $R_q$ defined as $R_q = Z_q/(X^n + 1)$. Additionally, we define the error distribution $\chi$ as a discrete centred Gaussian bounded by $B$. Let $s,t \in R_q$ be ...
0
votes
0answers
20 views

Construction PRG with expansion factor from a length preserving PRF [duplicate]

How can I prove that $F:\{0,1\}^n\to\{0,1\}^n$ is a length-preserving pseudorandom function, then $$G:G(s)= F_s(1)\mathbin\|F_s(2)\mathbin\|\cdots\mathbin\| F_s(l)$$ is a pseudorandom generator with ...
1
vote
1answer
39 views

How to prove the pseudorandomness of CryptoPAn

in my cryptography course, we are learning about pseudo randomness and the prefix-preserving function known as CryptoPAn invented in 2002. It is said that the scheme is highly insecure. So in that ...
0
votes
0answers
45 views

Am I applying Hybrid lemma and proof by contradiction correctly?

In the following scenario, I am trying to apply proof by contradiction. My idea is to use a Hybrid lemma. So if I am able to distinguish $G'$, this implies we are able to distinguish $G$. But we ...
0
votes
2answers
96 views

Rigorous practical pseudorandom generators

It is known that existence of pseudorandom generators (PRGs) is equivalent to the existence of one-way functions. In turn, the latter is an open problem. I am curious if someone developed kind of &...
4
votes
2answers
347 views

Is a LFSR sufficient for post-processing a biased TRNG?

I am building a TRNG on a FPGA based on ring oscillators. I found out that Linear Feedback Shift Registers (LFSRs) are commonly used for the post-processing of TRNGs. Here is my initial design: Let's ...
2
votes
1answer
66 views

Question about IETF RFC6979 determinisitc (EC)DSA document section 3.6 additional data k'

In RFC6979, on page 14, Section 3.6 "Variants": o. Additional data may be added to the input of HMAC, concatenated after bits2octets(H(m)): ...
8
votes
4answers
166 views
2
votes
2answers
266 views

Is Fibonacci-XOR-rotate one-way-ish?

Fix $n\in\mathbb{N}$ with $n > 2$ and consider the following method. Pick relatively prime seeds $x_1, x_2 \in \{0,1\}^n$ (where $x_1, x_2$ are interpreted as binary numbers. Then proceed with the ...
4
votes
1answer
226 views

What is the NIST recommended maximum bias for random number generators?

What is the maximum bias recommended by NIST for random number generators? This answer says that it is $2^{-64}$. Is it same for all applications? Does NIST have a publication with more information? I ...
1
vote
1answer
75 views

Shift-rotating random number generator

Let $\omega$ denote the set of non-negative integers. For $n\in\omega\setminus\{0\} $ define the rotation function $$\text{rot}_n:\{0,1\}^n \to \{0,1\}^n$$ by $x \mapsto x'$ where $x'_k = x_{k+1}$ ...
5
votes
3answers
263 views

How to combine $n$ 'less random' bits to generate one 'more random' bit?

Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0...
0
votes
1answer
66 views

In the reduction proof below, where OWF exists only if is a PRG. I am not able to understand the highlighted part

I am able to understand how G(x) id generated. But then what is the use of variable z. Also if the probability is >1/2 + e then the distinguisher wins! Then how is this still a OWF
1
vote
0answers
52 views

How to prove that the given encryption scheme have ciphertext indistinguishability for all PPT adversaries?

I am not sure how to prove that the given two scheme is perfectly indistinguishable for all PPT adversaries!
1
vote
0answers
45 views

Pseudorandom Generator Expansion

I have a question regarding the theoretic definition of Pseudorandom Generators. In Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62), it is defined as follows: DEFINITION 3.14. ...
2
votes
1answer
32 views

Is there a way to bound linear complexity of a sequence less than its period

Linear complexity of a sequence $s_0,s_1,\ldots$ over a finite field is the shortest length $n$ of linear recurrence of the sequence such that $s_{n+j}=\sum_{i=0}^{n-1}a_is_{i+j}$ for $j=0,1,2,\ldots$ ...
0
votes
2answers
161 views

Is it guaranteed that all possible random numbers can be produced?

As far as I know PRGs get an input (seed) and generate a larger output value than the input. Therefore is it possible that some outputs will never be generated? based on the fact that input is smaller ...
5
votes
3answers
192 views

A question regarding next-bit predictors

Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows. \begin{equation} \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} +...
1
vote
1answer
97 views

Is this a good Pseudo-Random Number Generator? [closed]

I discovered what appears to be a good quality pseudorandom number generator, but I have not subjected it to any statistical tests beyond bit frequency, bit pair frequency, and least-significant bit ...
32
votes
8answers
10k views

Why do some people believe that humans are "bad at" generating random numbers/characters like this?

I'm not even sure if they are serious, but I've heard many times that some people refuse to not only trust their computer to generate a random string (which is understandable) but also don't trust ...
0
votes
1answer
82 views

K-dimensional equidistribution - how big are periods of PCG?

I'm trying to figure out what is period of PCG generator XSL-RR-RR: https://www.pcg-random.org https://en.wikipedia.org/wiki/Permuted_congruential_generator If we use just random multiplier and ...
1
vote
1answer
48 views

Why should a distribution being pseudorandom strictly be a sequence of distributions being pseudorandom

According to Katz Lindell book, Let Dist be a distribution on l-bit strings. Informally, Dist is pseudorandom if the experiment in which a string is sampled from Dist is indistinguishable from the ...
1
vote
0answers
73 views

How does a pseudorandom generator produce a similar distribution to $U_{n}$?

According to Wikipedia, a function ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$ with ${\displaystyle \ell < n}$ is a pseudorandom generator against $\mathcal {A}$ with bias $\epsilon$ if, ...
1
vote
0answers
64 views

Nth term for Linear Congruence Generators

We can get the N+1th term for a Linear Congruence Generator like this: x[n+1] = A * x[n] (mod m) by raising the A to the exponent of n like this: ...
1
vote
1answer
195 views

Cryptographically secure linear congruential generator - is it possible?

Let's consider generator: $x_{n+1} = (a \cdot x_{n} + c) \mod m$ And let's assume we will meet three requirements known as Hull–Dobell Theorem. Also consider only $m=2^{i}$ (then $c$ has to be odd). ...
1
vote
1answer
147 views

Questions about using PRF to construct PRG

Let F be a secure pseudorandom function with 128-bit key and 256-bit block length. Which are the following functions G are secure pseudorandom generators? (Select all that apply.) A. $G(x)=F_x(0...0)$...
1
vote
1answer
69 views

Why this example about pseudorandom generators is performed like that?

Suppose Alice wishes to authenticate herself to Bob, by proving she knows a secret that they share. With pseudorandom number generators (PRNGs) they could proceed as follows. They both seed a PRNG ...
1
vote
1answer
138 views

Deterministic Counter Mode with a PRF. What does evaluate at a point mean?

This is from Dan Boneh's Lecture where he talks about operating a PRF (AES, DES) in Deterministic Counter Mode. Dan Boneh says What we could do is we could use what's called a deterministic counter ...
1
vote
1answer
72 views

Unable to understand the concept of a 1-bit PRF

In his lecture on building Block Ciphers from PRGS, Dan Boneh says this Let’s start by finding out if we can build PRF from a PRG? Let $G:\ K \to K^2$ be a secure PRG Define 1-bit PRF $F:\ K \times \{...
2
votes
1answer
197 views

Tests to distinguish between PRNG and a CSPRNG

What are the tests which a regular PRNG would fail but a CSPRNG would succeed? Is it just the next-bit test or are there multiple other tests which a PRNG which is not a CSPRNG would fail? Would a ...
0
votes
1answer
57 views

Understanding the Inner State of a RNG

Based on the BSI evaluation criteria for quality of deterministic random number generators: K4 – It should be impossible, for all practical purposes, for an attacker to calculate, or guess from an ...
1
vote
1answer
67 views

PRG exponential expansion

I am just beginning to read into pseudorandom generators and I came across this definition for a PRG: $G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial}$ Is there ...
1
vote
1answer
99 views

How to combine a PRG and a non-PRG to design a PRG?

I'm trying to solve the following exercise: Let $G_1, G_2: \{0,1\}^\lambda \to \{0,1\}^{\lambda + l}$ be two deterministic functions mapping $\lambda$ bits into $\lambda + l$ bits (for $l \ge 1$). You ...
2
votes
0answers
66 views

Proof that PRG of itself is a PRG (composition)

I have this question and I am struggling to find a formal answer to this: Given $G$ is a PRG, show that $H(s)=G(G(s))$ is also a PRG. I know that a proof for this would assume that there exists a p....
1
vote
2answers
350 views

Why is breaking the Blum Blum Shub PRNG not an undecidable problem?

The Blum Blum Schub (BBS) pseudo random number generator (PRNG) is defined inductively by $$ x_{i+1} = x_i^2 \mod N $$ to generate the bit sequence $b_0b_1b_2...$ where the bits are taken to be the ...
0
votes
0answers
52 views

Bad pseudo-random number generator -- any guesses?

I'm trying to diagnose a badly-implemented pseudo-random number generator. The two key features of the bit streams produced by this PRNG are: significant correlation of consecutive bits (approximately ...

1
2 3 4 5
9