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.
414
questions
0
votes
0answers
43 views
What if inputs of OWF and PRG is non-uniform?
If $f: \{0,1\}^n→\{0,1\}^m$ is a $(t,\epsilon)$-one-way function, meaning that no adversary of running time $t$ is able to invert $f$ (on input uniformly chosen from $\{0,1\}^n$) with probability more ...
1
vote
0answers
25 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
36 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
41 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
90 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
304 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
44 views
Question about IETF RFC6979 determinisitc (EC)DSA document section 3.6 additional data k'
In RFC6979 document
https://tools.ietf.org/html/rfc6979
page 14~15, Section 3.6 "Variants"
o. Additional data may be added to the input of HMAC, concatenated
after bits2octets(H(m)):
...
8
votes
4answers
157 views
Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?
Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $...
2
votes
2answers
260 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
224 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
73 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
250 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
57 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
50 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
42 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
31 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
160 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
184 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
95 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
74 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
71 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
62 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
157 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
116 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
63 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
123 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
70 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
187 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
52 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
63 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
94 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
62 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
304 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
51 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 ...
0
votes
0answers
84 views
0
votes
0answers
40 views
What is the advantage of guessing PRG impossible outputs?
Lets say we have a length-tripling PRG $$ G:\{0,1\}^l \to \{0,1\}^{3l}$$
What would the advantage of an adversary to guess one of the impossible outputs of G?
0
votes
0answers
47 views
Are there any universal PRG’s or PRF’s?
Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom ...
0
votes
1answer
62 views
Proving G(x)=x||[x^2 mod 2^N] is not a PRG
This was a question from my exam yesterday.
We have that $G:\{0, 1\}^n\rightarrow \{0, 1\}^{2n}$ and
$$G(x)=x\mathbin\|[x^2 \bmod 2^n]$$ with $x$ is uniform and $|x|=n$, give an efficient ...
0
votes
1answer
81 views
PRF and deterministic polytime function implie PRG
I'm struggling while trying to resolve this exercise. I already read all questions about PRG and PRF here and some proofs around the internet but none of them helped me.
let's consider a function $C$ ...
5
votes
2answers
303 views
Fast cryptographic hash function for short inputs
I am looking for a cryptographic hash function optimized for speed on short inputs, in order to implement a pseudorandom generator with expansion factor 2 (e.g. takes 16 bytes of input and outputs 32 ...
6
votes
1answer
495 views
Pseudorandom Generator
In a cryptographic application, two types of (pseudo)random bit streams are needed:
a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and
a stream $B= b_{1}b_{2}...
2
votes
0answers
116 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 ...
0
votes
0answers
19 views
Lehmer random number generator cipher scheme with moving bits
Let's consider linear congruential generator:
$X_{k+1} = a \cdot X_{k} \mod 2^{128}$
Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different ...
0
votes
1answer
71 views
Cryptographically secure PRBGs and the previous-bit test
I am reading Junod's paper about the Blum-Blum-Shub PRBG (BBS) and I am having trouble following his reasoning at on page 15, where he argues that the next-bit test can also be peformed for the ...
0
votes
1answer
76 views
Lehmer random number generator - cipher?
Let's consider linear congruential generator:
$X_{k+1} = a \cdot X_{k} \mod 2^{128}$
Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different ...
1
vote
1answer
68 views
How to calculate CPA attack complexity in bits manipulation
The following Forward Errors Correcting FEC is used in our daily devices. But I added a potential security measure.
In one of FEC systems the input is $K$ bits and the output code is $M$ bits where $M=...
1
vote
1answer
48 views
Ranking “amount of randomization” in a sequence
I'm facing the problem of implementing pseudo random bit generator (PRBG) on a very low power device. NIST.SP800-22 "Statistical test suite for Pseudo Random Generators" suggests a suite of ...
