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.

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
6
votes
0answers
645 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? ...
5
votes
0answers
598 views

How can we formally define a Pseudo-Random Shuffle function?

My question is related to: When we turn Random shuffle to Pseudorandom Shuffle The idea is to permute the elements in vector $\mathbf{v}$ pseudorandomly, where $|\mathbf{v}|=n$; I am aware that we ...
4
votes
0answers
238 views

is a MAC defined by a pseudo random generator secure?

Let $ G:\{0,1\}^*\rightarrow\{0,1\}^*$ be a length doubling PRG, and let $ \Pi=(Gen,Mac,Vrfy)$ be the following MAC scheme: $ Gen $ on input $ 1^n$ uniformly samples and outputs $ k\leftarrow \{0,1\...
4
votes
0answers
213 views

Feasible way to check n-dimensional equidistribution of PRNGs

I am currently gathering some test methods and test suites for random number generator qualities, and am a bit stuck at finding something feasible to test for n-dimensional equidistribution. As input ...
3
votes
0answers
481 views

Can we construct a PRF directly from a one way permutation function?

In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is ...
3
votes
0answers
207 views

Finding the cycle sets of an LCG

My LCG has the form: $$S_0 = k$$ $$S_{n+1} = S_n \times a + 1 \pmod m$$ Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this ...
3
votes
0answers
362 views

Is a PRG that reveals the first bit of the input secure

Let $G:(0,1)^n \rightarrow (0,1)^{n+1}$ be a secure PRG. Define $G'(s):=s_1 ||G(s)_{2,...,n+1} $. ($||$ is concatenation, and the subscript $ _{2,...,n+1}$ means the last $n$ bits of $G$) I claim ...
3
votes
0answers
351 views

On the Definition of a PRG and a CSPRG

I've been looking at the definition of a PRG, here. This is a broader notion than a cryptographically secure PRG ("CSPRG"), which is described here. I am realizing that I am very confused by this ...
3
votes
0answers
247 views

Integer factorization based password authentication

After looking at this security issue at DjangoProject, I started to think in a password-based authentication that places the burden of PBKDF2 (or whatever is the hashing function) on the client. So I ...
2
votes
0answers
68 views

Hash function based cryptographically secure pseudo random number generator

I once read/heard that one could generate a cryptographically secure pseudo random number generator based on two cryptographically secure hash functions. The algorithm goes this way: Let $f$ and $g$ ...
2
votes
0answers
118 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....
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 ...
2
votes
0answers
36 views

RNG and Mersenne twister learning resources for the amateur

I am a complete amateur in the area of random number generators. I would appreciate resources to begin learning. Also I would also like to learn about Mersenne twister. Resources that are easy on the ...
2
votes
1answer
445 views

Breaking a Mersenne-twister RNG with unsequential outputs

Pardon me for this newbie-ish question. I'm still a novice in cryptography . I have an application that outputs random numbers from 0 - 12 (endpoints inclusive) unsequentially (some outputs are thrown ...
2
votes
0answers
89 views

How many bits of cryptographic security do these XOR Mid-Square random numbers have?

This pseudo-random number generator uses only XOR and Mid-Square operations: Get one secret 128-bit truly random seed $R_0$ Generate a million secret $R_j$ by the recurrences (for $1\le j\le 1000000$)...
2
votes
0answers
218 views

Decentralized consent over a random number

Maybe, some of you remember having to pick one person during playing as kids. That person would than have to catch the others for example. The methods to pick given person often would either depend on ...
2
votes
0answers
305 views

Showing a generator based to pseudorandom function is also pseudorandom

First of all sorry for the bad title, this is an exercise I'm struggling with: Let $F_k$ be a pseudorandom keyed function (abbreviated to PRF) with key, input and output of length $n$. Define the ...
2
votes
0answers
72 views

Is the number still a CSPRN if we only allow an interval from a CSPRNG?

tr -dc 0-9 < /dev/urandom | fold -w 3 | awk '$0>=100 && $0<=200' What this line does: /dev/urandom (Linux) is proven to be a CSPRNG, that is ...
2
votes
0answers
100 views

Polynomial restriction for PRG

Say we have a PRG $G(l,x)$ that expands a random string $x$ to length $l$ and is pseudorandom for any $l$ polynomial in $n$ (where $n = |x|$). Is $G$ pseudorandom for any $x$ of arbitrary length? I'm ...
2
votes
0answers
308 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) ...
1
vote
0answers
48 views

Program to predict a 5-bit output from mersenne Twister random module from python

Is there a program to predict the mersenne twister random module in python for a 5-bit integer output, provided the consecutive 3994 outputs are available? The random module is not seeded so i guess, ...
1
vote
0answers
29 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
0answers
30 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 ...
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
57 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. ...
1
vote
0answers
74 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
68 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
0answers
109 views

Is $f(g)$ a PRG if $f$ is a OWF and $g$ a PRG?

If we have a PRG $g$ and a OWF $f$, can we say that $g' = f(g)$ is a PRG? And what if $g$ stretches its input by a factor of 2?
1
vote
0answers
102 views

Would the result of encrypting weak random data via AES-128 with a CSPRNG-generated key be considered strong/secure random data?

I am trying to understand the security implications of using a well known block (or stream but in this example block) cipher like AES-128 to produce pseudo-random data. My specific question is would ...
1
vote
0answers
78 views

Alternative AES key expansion for CTR based random number generator

Daniel J. Bernstein proposes an alternative to NIST AES-CTR based deterministic random number generator (AES-CTR-DRBG). Instead of a less performant complex construction, he uses an standard AES-CRT ...
1
vote
0answers
276 views

Pseudo Random Generator (PRG) not deterministic

Usually a Pseudo Random Generator is supposed to be IND-CPA secure. But apparently, it is not in some cases such as the following: A PseudoRandom Generator $G$ has expansion factor $n + 2$. Encrypt ...
1
vote
0answers
106 views

Dependence of a Pseudorandom Function's Security on its Input/Output Spaces

Let $n$ be a security parameter and $F:\{0,1\}^{\ell_{key}(n)} \times \{0,1\}^{\ell_{in}(n)} \rightarrow \{0,1\}^{\ell_{out}(n)}$ be a keyed function which forms a family of Pseudorandom Functions (...
1
vote
0answers
190 views

Construction PRF from PRG

As discussed here, a classic and secure construction of PRF from PRG is: $F_k(x_1x_2\cdots x_n) = G_{x_n}(\cdots(G_{x_2}(G_{x_1}(k)))\cdots)$ where $G$ is a secure pseudorandom generator. I was ...
1
vote
0answers
754 views

Which 'info' and 'salt' parameters to use in HKDF for TLS 1.3?

all the following discussion is for HKDF in TLS1.3: Regarding the 'salt' parameter in - HKDF-Extract(salt, IKM) as written in RFC 5869: HKDF without having to protect the secrecy of the salt. In a ...
1
vote
0answers
462 views

show that G' is not a secure PRG even if G is

Hello I'm trying to show that the function G'(s) = G(s) || G(G(s)) is not a secure PRG even if G is. My first question is that in this case, how do I know what G ...
1
vote
1answer
155 views

A modification of the Blum-Micalli construction

Consider the following modification of the Blum-Micalli construction (denoted by BM): $G_l(x) = f^l(x) || BM^l(x)$ I am asked the following questions about it: Show it is a PRG of fixed stretch ...
1
vote
0answers
41 views

Pseudorandomness based on homomorphic multiplication property of Paillier cryptosystem

Given the instance $(n, g, \lambda)$ of Paillier cryptosystem with $\text{ord}(g) = n \lambda$ (symbols have their usual meaning), and $c = g^{na}$, is it possible to distinguish (computationally) $c' ...
1
vote
0answers
224 views

Indistinguishable encryptions and CPA-secure example

Let $ F $ be a PRF and $ G$ be a PRG with expansion factor $n \to n +1 $ For the following encryption scheme, decide whether it has indistinguishable encryptions and whether it is CPA-secure. ...
1
vote
0answers
110 views

Never design your own crypto...how to design a PRG

As a new learner of cryptography I have learnt from online tutorials and lectures not to design your own crypto. What I am trying to understand is the fundamental to designing PRGs to a given context ...
1
vote
0answers
136 views

Calculating t and epsilon for a computationally indistinguishable pseudo random generator

I have a PRG $G : \{0, 1\}^n \rightarrow \{0, 1\}^{2n}$. How would you go about calculating the optimal size of $n$ given that you have $$\epsilon = \cfrac{1}{2^{80}}$$ and, $t = 2$ years for a ...
1
vote
0answers
168 views

$G_f(x) = x \|f(x)$ is not a PRG with $\operatorname{DPT}$-computable function $f$

Let $f:\{0,1\}^* \rightarrow \{0,1\}$ be any $\operatorname{DPT}$-computable function. Show that $G_f(x) = x \|f(x)$ is not a PRG. Can anyone help me on understand how to prove this?
1
vote
0answers
134 views

Mersenne Twister's vulnerabilty with small-size distributions

C++ rookie here, trying to wrap his head around (CS)PRNGs. I (assume that I) already understand the concept of the Mersenne Twister being "broken" (i.e. not cryptographically secure) due to its ...
1
vote
0answers
166 views

How Are Linear Congruential Generator Multipliers Chosen?

There are several numbers that keep coming up when looking at certain random number generators, for example 6364136223846793005 is used in newer pcg-family algorithms and seems to draw it from ...
1
vote
0answers
425 views

Assume G(s) is a PRG, is the following also a PRG?

Let s be a n-length binary word and not_s its negation. Let G be a PRNG with expansion 2n. Prove that H1(s) = G(not_s) is also a PRG? Prove that H2(s) = G1(s)||G2(not_s) is also PRG. Given G1, G2 ...
1
vote
0answers
425 views

Pseudo-random function where the output is inverted using XOR

I'm looking to know whether or not this PRF is secure : $$F'(k, x) = F(k, x) ⊕ 1^n$$ knowing that $F$ is already a secure PRF for $$\{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$$ with, for example, $n= ...
1
vote
0answers
2k views

Assume $G$ is a PRG. Proof that $G'$ is PRG?

Let $G: \{0,1\}^s \rightarrow \{0,1\}^n$ be a pseudorandom generator (PRG). Are the following PRGs? $G'(x) = G(x)_{0,\ldots,n-2}$ ($G'(x)$ drops the last bit of $G(x)$) $G'(x) = G(x) \oplus ...
1
vote
0answers
974 views

how to prove by reduction correctly?

some times when see a problem like : if some G is a PRG then G' is also a PRG. we prove this by reduction in the following way: we assume there is a Distinguisher A for G' and we construct ...
1
vote
0answers
129 views

Does using pseudorandom generator more than once cause security loss?

Everytime we use the generator with itself there is security loss. Even if this loss is not enough to loose all cryptographic security, there is still some small loss in security. Is there any way to ...
1
vote
0answers
49 views

HMAC for provable server distributed randomness

I have an application in which a user must use a high-entropy salt to salt a message. Due to the fact that I can not rely on the user to actually provide a strong salt, the server must provide this ...
1
vote
0answers
479 views

Proving pseudorandom generators

Can anyone please help me on how to prove or disprove (by counterexample) whether the following function $G'$ is a PRG (Pseudorandom Generator) given that $G$ is a PRG. $$G'(s) = \operatorname{trunc}...