Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...

1
vote
1answer
54 views

Is this MAC correct and secure?

Let $m \in \{0, 1\}^{2n} = m_1 || m_2$. Let's also assume that $F_k$ is a PRF and $G$ is a PRG defined as $G: \{0, 1\}^n \rightarrow \{0, 1\}^n$. Now, Let's define the $MAC$ scheme as follows: $$MAC(...
2
votes
1answer
57 views

Is PRG On Concatenation of Input a PRG

This is a homework assignment, so I'm not expecting full solutions, just general guidance. Let a PRG $G:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{l\left(n\right)}$ (where $l\left(n\right)$ ...
-1
votes
0answers
24 views

Let G be a PRG of stretch l(n) = 2n

Determine the success probability of the following $D$: -Input: $y\in\{0,1\}^{l(n)}$ and $1^n$ -Generate uniformly $x' \in \{0,1\}^n$ -Compute $y' = G(x')$ -Return $1$ if $y=y'$; else return $0$ ...
0
votes
0answers
39 views

Making a PRG into a (t,Ɛ) PRG

I am trying to workout a value for $n$ that in effect turns a proposed PRG such as $G: \{0,1\}^n \rightarrow \{0,1\}^{4n}$ into a effectively a $(t, \epsilon)$ PRG where the inputs of $t$ and $\...
1
vote
0answers
34 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. ...
0
votes
0answers
50 views

What does this PRG achieve [closed]

I saw a textbook example of the following PseudoRandom Generator $G: \{0,1\}^n \rightarrow \{0,1\}^{2n}$ and was told that it was feasible in the book for compression functions. What I am trying to ...
1
vote
0answers
80 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
91 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 ...
3
votes
1answer
176 views

Stronger security definition of PRG

By the standard security definition of a Pseudo Random Generator, if $G$ is a PRG, then $G'$ such that $G'(0\mathbin\|x)=0\mathbin\|G(x)$ and $G'(1\mathbin\|x)=1\mathbin\|G(x)$ is a PRG. We can build ...
-1
votes
1answer
69 views

PRG Theory Design

PRG theory design is something of interest to me at the moment in the security of cryptography. I am interested in learning how to come with PRGs for random functions such as $\{0,1\}^{2n} \...
1
vote
1answer
117 views

Pseudorandom generator designs

When designing pseudorandom generators what should one consider? Here is an example pseudorandom generator $F^t : \{0,1\}^n \rightarrow \{0,1\}^{4n}$. I have no idea what it means, so what does it ...
0
votes
1answer
48 views

PRGs exist if computationally secret encryption schemes exist

I have understood the "equivalences" between PRP, PRF and PRG. Now, I just read an statement in my lecture notes that made me think that there has to be a conversion between PRG and computationally ...
1
vote
0answers
29 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?
2
votes
1answer
104 views

Cryptography Pseudo Random Generator example question - proof

For ii) G2 was proven to be a PRG, and it seems the solution for G5 uses G2. Can someone try and explain to me the solution that I was given? I specially do not understand how to calculate the given ...
2
votes
1answer
36 views

What's the internal state size and output range of mrg32k3a?

This is Pierre L'Ecuyer's PRNG. I know its period is $2^{191}$, but I don't know what is its internal state size. What is it?
0
votes
0answers
67 views

Oracle version of the IND-PRG game with q queries

Consider the following oracle-based game: $O_0$: Init: $1^n$; Query: output $y \stackrel{u}{\in} \{0,1\}^{l(n)}$ $O_1$: Init: $1^n$; Query: output $G(x)$ with $x \stackrel{u}{\in} \{0,1\}^{n}...
3
votes
0answers
73 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 ...
2
votes
2answers
1k views

Is this test result sufficient to steer clear from this RNG for cryptographic applications?

I'm not really interested in this PRNG. I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications. I'm taking the C PRNG as an example. ...
0
votes
2answers
84 views

Blockchain cryptography

I'm a high school student doing a project about blockchain. I'm trying to figure out why hashing algorithms are crucial for the existence of blockchain and other types of cryptography wouldn't work. ...
2
votes
2answers
166 views

Does there exist a CSPRNG that does not require generating prime numbers, but also does not depend on any other cryptographic primitives?

The following excerpt is taken from the “Cryptographically secure pseudorandom number generator” article on Wikipedia: CSPRNG designs are divided into three classes: those based on ...
2
votes
1answer
96 views

Making PRNG cryptographically secure thru shuffling?

Is it practical to make a PRNG cryptographically secure if I shuffle the randomly generated numbers (say 256-bit) several times before hashing it, even if a hacker knows when I generate the numbers? ...
2
votes
1answer
44 views

Problems understanding the applications of pseudo random number generators

I am trying to explore different methods used to generate pseudo-random numbers for my project in maths and I would be very grateful for some help or references to valuable sources as it is very hard ...
6
votes
1answer
681 views

What does “seed” mean in cryptography?

I have come across "seed" many times, and at each time, it confuses me more and more. I think it has a well-known meaning in cryptography, so what is it? They can usually use the limited number of ...
1
vote
1answer
43 views

Instead of sending a set of random values, send a key for a PRF

Some Protocols require one party to send $n$ random challenges (or random values) to another party. For communication efficiency purpose, one can pick a random key for a pseudorandom function, and ...
-1
votes
1answer
84 views

Can there be a PRG $G(x)$ where at most half the output bits are 1?

Can there exist a pseduorandom generator, $G(x)$, with input length $|x|=n$ and output length $|G(x)|=2n$, where $\leq n$ bits of $G(x)$ are equal to 1 for every possible input $x$? (I.e. no more than ...
-1
votes
1answer
123 views

If $G$ is a PRG, is $F(s)=G(S)||G(\bar{s})$ necessarily a PRG?

Let $G$ be a pseudorandom generator, and $F(s)=G(s)||G(\bar{s})$ (where $\bar{s}$ denotes the bitwise complement of $s$), is $F$ necessarily a PRG? My intuition says that it is a PRG, as clearly $G(s)...
3
votes
1answer
228 views

Attack of the Middle Square Weyl Sequence PRNG

The Middle Square Weyl Sequence PRNG was proposed as illustration of properties of CSPRNGs in this answer (now deleted). This PRNG was introduced (without claim of cryptographic security) by Bernard ...
7
votes
2answers
725 views

How fast does a pseudorandom number generator have to be in order to be competitive?

Let $\{x_n\}_{n}$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive ...
1
vote
1answer
77 views

Pseudo-random generators and pitfalls

I've read the Chapter "Randomness" from the Serious Cryptography book and it raised some questions. Namely: It is written that Mersenne Twister is proved to be cryptographically irreliable. And that ...
0
votes
1answer
87 views

Does hashing a PRNG by a cryptographically secure hashing algorithm result in a CSPRNG?

Or specifically, does ChaCha20 hashing of the xoroshiro128+ random number generator result in a cryptographically secure random number generator?
4
votes
1answer
230 views

Is a one-way function pseudorandom?

For one-way function $f$ I understand that $g(x)=0^{n}\mathbin\|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second ...
1
vote
0answers
42 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 ...
2
votes
1answer
132 views

Is the XOR of PRGs sharing the same input a PRG?

I have question in learning PRG. Given that $f$ and $f_1$ are PRGs, both $\{0,1\}^n \to \{0,1\}^{2n}$. Is $g(x) = f(x)$ xor $f_1(x)$ a PRG? Someone told me that in this case, $g(x)$ is not a PRG, ...
0
votes
1answer
78 views

Oblivious Encryption: Oblivious Transfer Based Encryption

I’m aware of a couple of OT protocols, most of which use Public Key Cryptography, Key Establishment (or similar constructs) as the base. I don’t really have specific knowledge on other OT protocols, ...
2
votes
1answer
106 views

PRNG with a truly random seed?

PRNG (Wikipedia): "The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values)." My ...
3
votes
2answers
96 views

Inversive Congruential Generator

The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$. One can choose $a,b$ in $k$ such that the orbit ...
1
vote
2answers
107 views

How is a ciphertext encrypted using random numbers decrypted using a symmetric key algorithm

We use true random number generators as a source of keys for encryption. What I can not wrap my head around is: How is this cipher text decrypted in case of symmetric key algorithm as we need the same ...
1
vote
1answer
98 views

repeatedly hashing result and using reverse sequence as RNG secure?

I want to have a source of randomness for which: no one but me can predict the next number in the sequence. I know the entire sequence in advance, but I have no way of manipulating it once the first ...
0
votes
1answer
62 views

Expected Linear Complexity of a sequence

Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)? I have no idea of the answer to this question? What ...
2
votes
1answer
86 views

period of the lfsr sequence after some manipulations

Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate: Given 3 maximum length (max period) LFSR's of lengths L1,...
1
vote
1answer
36 views

Random semantic security and bijective PRGs

I'm working through Boneh and Shoup's "Graduate Course in Applied Cryptography", and have just finished reading the chapter on stream ciphers and PRGs. The first exercise for this chapter introduces ...
4
votes
1answer
218 views

Identifying the type of algorithm for a PRNG that uses modular multiplication and addition

GNU libc uses the following pseudo-random number generator: $$(\mathit{state} \times 1,103,515,245) + 12,345 \pmod {2^{31}}$$ where state is the result of the previous call to the generator. My ...
0
votes
5answers
168 views

Pseudorandom number generator for which it is impossible to deduce the seed

I'm looking for an RNG that in the case that an attacker would get all or part (most likely part) of the pseudorandom data, there will be no way for them to deduce the original seed more efficiently ...
0
votes
1answer
84 views

Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

The Commutative Cipher Setup Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime. Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) =...
3
votes
1answer
106 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
3
votes
3answers
153 views

Usage and limitations of sponge functions for PRNG

This HRNG uses SHA3 as a sponge function (in its device driver) to inflate ots raw source output to many MByte/s. They compare this output rate to the output of other HRNG which don't use a sponge ...
1
vote
2answers
166 views

mapping a 256 bit random number to a 3 bit number

I am making a 2 player dice game that runs for n rounds. To create random dice roles im using a concept a understood from randao. each user generates n sha3 hashes recursively of a random seed : e.g. ...
1
vote
0answers
65 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
1answer
78 views

prove PRG is secure assuming DDH holds

Let $\Bbb{G}$ be a cyclic group of prime order $q$ generated by $g \in G$. Let $G$ be a PRG defined over $(\Bbb{Z}_q^2, \Bbb{G}^3)$ such that: $G(a, b) = (g^{a}, g^{b}, g^{ab})$ How can I show ...
2
votes
1answer
62 views

Unbalanced Feistel network only generates complete permutations with square lengths

I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then ...