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

1
2 3 4 5
10