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.
500
questions
-1
votes
0
answers
41
views
Is every pseudorandom generator a one-way function, even if the output length has no extra restrictions? [duplicate]
Intuitively, if we can invert a PRG, then we can easily distinguish it with random distribution by checking g(inverse(y)) = y. So every PRG is a OWF?
Unlike the problem "Is every pseudorandom ...
- 9
2
votes
1
answer
85
views
Fast and secure pseudo random generator with Linux tools
The conventional and simple wisdom is to combine head with /dev/urandom to create the amount of pseudo-random data that is ...
- 121
2
votes
0
answers
50
views
Proving that a PRG is predictable
I am attending the video lectures from Prof Dan Boneh. He gives the following example.
Let $G:\mathcal K\longrightarrow \Bbb Z_2^n$ be a PRG with the property that from the last $\frac{n}{2}$ digits ...
- 121
3
votes
0
answers
54
views
Why: $G'(s) = G(s_1, \ldots, s_{\lfloor{n/2}\rfloor})$, where $s = s_1, \ldots, s_n$ is PRG?
I'm a novice reader of Introduction to Modern Cryptography, where it states:
Let $G$ be a pseudorandom generator with expansion factor $\ell(n) > 2n$.
In each of the following cases, say whether $...
- 31
0
votes
1
answer
49
views
Is there a way to make a pseudorandom function to generate decimal numbers in a specified range and not only producing big ones?
When I try to generate decimal numbers in the range 0-18446744073709551616 using a hash function I always get big numbers like this:
...
- 105
2
votes
0
answers
45
views
Hybrid Argument proof
I am trying to understand what the Hybrid Argument is in cryptography and why is it useful.
By the definition of the Hybrid Argument we know that to prove that if two distributions $D = D_1, D_2, ...,...
- 83
1
vote
0
answers
34
views
Public seed expansion for uniform reference strings
Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments).
Our goal is to publicly generate the random values of this ...
- 323
2
votes
1
answer
46
views
A random access machine with lots of random data on its tape is a stronger assumption than the existence of OWFs
Suppose we have a random access machine with $(n+1)2^n$ random bits on its tape. This assumption is weaker than assuming the existence of a random oracle, but using this assumption we can construct a ...
- 514
2
votes
1
answer
88
views
Any simple, cryptographically secure AES-based DRNG?
I am looking for a DRNG/DRBG (cryptographically secure) algorithm/function (which I can program into js). I am looking to use a DRNG as a seed generator for generating multiple, identical AES keys on ...
- 45
2
votes
1
answer
73
views
Let $G$ be a PRG. Establish whether the following PRG candidates $G^{'},G^{''}$ are secure or not
Let $G:\{0,1\}^n \leftarrow \{0,1\}^{2n}$ be a PRG. Establish whether the following PRG candidates $$G^{'},G^{''}:\{0,1\}^n \leftarrow \{0,1\}^{3n}$$ are secure or not:
$G^{'}(s)=(x⊕y,u,v)$ where $(x,...
- 33
1
vote
1
answer
62
views
Computing the advantage when checking PRF
I am reading a pdf on pseudorandom function I found here https://www.cs.utexas.edu/~dwu4/courses/sp21/static/reductions.pdf
My problem/struggle is with the computation of the distinguisher's $B$ ...
- 173
2
votes
1
answer
75
views
Cascading Streams From the Same Cipher
Does encrypting plaintext multiple times with the same stream cipher but independent keys increase security? If each key is n-bits, and the cascade uses m-streams, could this be considered mn-bit ...
- 23
0
votes
1
answer
91
views
Proof for secure stream cipher implies secure PRG
I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am not sure if my proof for the following problem in the book is correct. The problem asks to prove that if a ...
2
votes
0
answers
59
views
For the given construction not all secure PRG gives a secure PRG
Let $G:\{0, 1\}^n \to \{0, 1\}^m$ be a PRG. We define another PRG $G_0 : \{0, 1\}^n \to \{0, 1\}^m$ as follows: $G_0(s) = G(s) \oplus (0^{m−n}\mathbin\|s)$. Can there exists a secure PRG $G$ for ...
- 121
0
votes
0
answers
61
views
Double length inefficient PRG
Is there a known example of a deterministic algorithm that given an n-bit input returns 2n-bit output, and where a random output can't be efficiently distinguished from a random 2n bit string?
- 1
0
votes
2
answers
64
views
Does processing a trully random seed though a non-cryptographic PRNG will result in a unpredictable stream?
I have been studying C/C++ and I read that if one wants unpredictable random data in a program, it is needed that a random generation function be supplied with truly and unpredictable random data (as ...
- 867
2
votes
0
answers
117
views
Check if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom
Let F be a pseudorandom function. Check if if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom( $\oplus$ is bitwise XOR).
I found this question in a book. I am not sure how to proceed :
$F_1(k,x) = F(k,x) ...
- 173
1
vote
1
answer
112
views
Is the xor of a prg and a function still a prg?
I have this couple of deterministic functions $G_1$ and $G_2$. Suppose at least I of them is a PRG. Take $G^*=G_1(x)$ xor $G_2(x)$ with the same $x$. I have to show whether this is still a PRG. I ...
- 61
2
votes
2
answers
169
views
Construct PRG from PRF with polynomial expansion factor
I want to prove that for every pseudorandom function $F: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ and for every polynomial $p$ such that $p(n) > 1$ for every $n$ it is possible to ...
0
votes
1
answer
58
views
Constructing a PRG from a pseudorandom function
I have recently understood how we can construct a pseudorandom function from a PRG. However, I would like to prove the reverse - how can I construct a PRG from a PRF?
1
vote
0
answers
118
views
Is concatenation of two distinct secure PRG still secure?
I'm new to cryptography and having a hard time understanding PRGs and PRFs.
Question: $G'(x)$ and $G''(x)$ are two different secure pseudorandom generators, and $G(x)=G'(x) \mathbin\Vert G''(x)$.
Is $...
- 11
0
votes
0
answers
86
views
Post processing operations on pseudo-random generators
I am struggling to solve this proof.
The goal is to prove that $H \circ G$, which is a composite function $H(G(s))$ can be a pseudo-random generator under some conditions on $H$, given that $G$ is ...
0
votes
1
answer
63
views
Is gcc's stack canary cryptographically secured? Does stack canary in general has to be cryptographically secured?
I want to ask 2 questions:
Is GCC's stack canary cryptographically secured?
Does stack canary in general has to be cryptographically secured?
1
vote
1
answer
93
views
Where can I find a comprehensive guide to running the NIST SP800-90B_EntropyAssessment?
I am already using the 2 they suggest :
https://github.com/usnistgov/SP800-90B_EntropyAssessment https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-90B.pdf
but, here is where I run into ...
0
votes
0
answers
68
views
Exchange key and input in GGM tree
In the GGM tree construction for constructing a PRF from a PRG, the secret key is used at the root of the tree and the input is used to trace a path through the tree. Consider a construction that does ...
2
votes
1
answer
67
views
exact meaning of ntup in dieharder tests
I'm working with the dieharder package to test a PRNG, but I don't quite understand the ntup parameter.
I get that the ntuple should be a set of consecutive bits. ...
- 21
0
votes
1
answer
137
views
Secure Random number generator
I am trying to implement a random number generator (which should be cryptographically secure), I am thinking of combining multiple LFSRs, is it a good choice?
I've also heard I can create RNGs from ...
- 23
0
votes
1
answer
80
views
Seed of pseudo-random number generators
How is the seed of PRNGs generated? They can't be hardcoded I am guessing.
- 23
0
votes
0
answers
55
views
How to share a function securely?
I was reading a paper on Function Secret Sharing, and in that the author made use of the idea of GGM-style tree to propose a scheme based on pseudorandom generator.
Here I became interested in how to ...
- 40
1
vote
1
answer
2k
views
Should we really rely on "Cryptographically Secure Pseudo-Random Number Generators" (CSPRNG) alone to guarantee secure random output?
Would it be over-engineering to for example hash the random numbers a random amount of times too, for instance when using the CSPRNG in client-side JavaScript? (assuming this is not the strongest ...
- 293
1
vote
1
answer
126
views
Combiners on PRG
I was asking myself the following question but I'm not really sure if it's in this way:
I have a first $PRG$:
$$G_1: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{\lambda+1}$$
Now I want to construct a ...
- 33
1
vote
0
answers
128
views
Does this function yields to a PRF?
I have two PRGs:
$$G: \{0,1\}^l \rightarrow \{0,1\}^{3l}$$
$$G': \{0,1\}^m \rightarrow \{0,1\}^n , n \gg m$$
I also have a PRF:
$$F: \{0,1\}^{3l} \times\{0,1\}^m\rightarrow \{0,1\}^m $$
Is:
$$\...
- 33
2
votes
1
answer
204
views
Uniform rejection sampling by shifting or rotating bits from CSPRNG output, safe?
Given a CSPRNG (arc4random, using ChaCha20 keystream), one want to use rejection sampling to get random number on a smaller range avoiding modulo bias (arc4random_uniform()).
OpenBSD's ...
- 151
4
votes
1
answer
126
views
Constructing a PRF from PRG, with more parallelism
The famous result of Goldreich, Goldwasser, and Micali (GGM) constructs a PRF $F$ from a PRG $G$:
...
- 11.2k
0
votes
2
answers
141
views
CS(P)RNG uniqueness
I recently read a StackOverflow post about a CS(P)RNG generating sixteen bytes of random data. The OP wanted this data to be random and unique. One of the answers said that uniqueness and randomness ...
- 155
1
vote
1
answer
46
views
Security of the encryptions, using a PRG for the keyGen
I recently got doubtful to the usefulness of psuedorandom generators(PRG) in cryptography.
Based on Kereckhoff's principle, we always assume that the used algorithms are made public.
So, when we use a ...
- 220
1
vote
1
answer
103
views
Randomness of recursive sequence generation
How good from a randomness point of view are recursively generated sequences using good encryption algorithms?
Let us say I take AES128 which generates good random sequences of outputs for counter ...
- 141
1
vote
0
answers
53
views
Finding a specific word in a substitution cipher
Rand48 is a pseudo-random generator which produces a sequence of any given integer using the following rule:
$a_n=(25214903917 \cdot a_{n-1})\bmod 2^{48}$.
If $b_n=\lfloor a_n/2^{16} \rfloor \bmod 52$,...
0
votes
1
answer
127
views
Is this pseudo random function any good and/or original? [closed]
I designed this pseudo-random function algorithm that takes a uint64 and returns a uint64. I'd like to know if it is any good ...
- 627
2
votes
1
answer
299
views
What is an output symbol?
I'm reading Understanding Cryptography by Christof Paar and Jan Pelzl. In chapter 2 (Stream Ciphers). There is a section talking about "Bulding Key Streams from PRNGs".
They assume a PRNG ...
- 123
1
vote
1
answer
107
views
A security issue of a Bit commitment scheme constructed by Naor in 1990
In the Section 3.12 of book writen by Boneh and Shoup, a Bit commitment from secure PRGs is presented as follow:
Bob commits to bit $b_0\in_R\{0,1\}$:
Step 1: Alice chooses a random $r\in R$ and sends ...
- 316
1
vote
1
answer
66
views
Minimum cycle length for Rule 30 automaton with bit-toggle
A rule 30 cellular automaton produces chaotic output from a very simple rule and therefore can be used as a pseudo-random generator (but not a cryptographically secure one).
One of the problems is ...
0
votes
1
answer
130
views
Implementation of the chaotic map to produce (pseudo)-random number
For my project I used Henon map to generate (pseudo)-random number. I used the following code to generate the matrix of (pseudo)-random number.
...
- 101
0
votes
1
answer
53
views
Mapping number into number with big algorithmic entropy - how to do it?
I need to parameterize some PRNG, let's assume I need 32-bit numbers. But when numbers doesn't look very random it gives bad results. The creators of SplitMix had similar problem (note that from what ...
- 1,171
1
vote
1
answer
87
views
Can we apply the Pseudo Random Number (PRNG) as post processing method for True Random Number (TRNG)?
From the NIST SP 800-90B, we can use these cryptographic algorithms (HMAC, AES, Hash function) as a post-processing technique for TRNG.
Besides that, can we apply the Pseudo Random Number (PRNG) as a ...
- 83
6
votes
3
answers
196
views
Majority-based feedback shift register
Linear feedback shift registers (LFSR's) work by taking a fixed-length bit-string $b\in\{0,1\}^n$, as well as fixed "taps" (bit positions) and applying XOR to the taps, giving one output bit,...
2
votes
2
answers
233
views
Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?
In Katz's Introduction to Modern Cryptography,
Chapter 7 Practical Constructions of Symmetric-Key Primitives
In previous chapters we have demonstrated how secure encryption
schemes and message ...
- 151
1
vote
0
answers
88
views
Is F' = G(F)) a secure PRF given F and G are secure? [closed]
If we have a secure PRF 𝐹(𝑘, 𝑥) and a PRG G where 𝐺 : 𝒴 → 𝒴 × 𝒴 is a secure PRG.
Is the PRF F'(k, x) = = 𝐺(𝐹(𝑘, 𝑥)) also secure?
- 11
2
votes
0
answers
46
views
Is this property implied by a pseudorandom function?
Given a keyed pseudorandom function $f: S \times X \rightarrow Y$, where $S$ is the space of secret keys, $X$ is the input domain, and $Y$ is the range, the pseudorandom property says that given any ...
- 163
0
votes
0
answers
199
views
Does xoshiro/xoroshiro PRNGs provide uniform distribution?
It's not clear from the documentation if the sequence of integers produced by these PRNGs belongs to the uniform distribution.
Also it's look like there is a whole family of RNG algorithms called in a ...
- 101