# Questions tagged [pseudo-random-function]

A pseudo-random function (PRF) is a family of deterministic functions indexed by a parameter, such that a randomly selected instance is computationally indistinguishable from a uniformly random function with the same input and output spaces.

303 questions
Filter by
Sorted by
Tagged with
28 views

### Insecure MAC built on pseudorandom function

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling ...
39 views

### Mathematical definition of deterministic and non-deterministic random bit generators

Can anyone give the mathematical definition of deterministic and non-deterministic random bit generator? Providing a reference will also be very helpful.
111 views

### Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG

This is not homework, but a random thought. Let $G(x)$ be a PRG. We define the following function: $$F_k(x) = G(k\oplus x)$$ My intuition is that it shouldn't be a PRF but I couldn't come with an ...
82 views

### Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0

I have 4 functions to analyze. I need to determine if they are or are not pseudorandom and give a proof/counterexample. I'm having trouble just determining if they are - let alone proving or giving ...
18 views

### safe concating PRP and PRG

Suppose it is necessary to build a safe PRG. You have one PRP with $\epsilon = \frac{1}{2} ^ {45}$, and one PRF with $\epsilon = \frac{1}{2} ^ {55}$. There is no mathematical relationship in the PRP ...
557 views

### Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?

If $F$ a PRF, and we construct $G$ using $F$ in the following way: $$G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$$ where $|s|= n$. Is $G$ then a PRG? If so how can I prove this? If not how can $G(s)$ ...
29 views

### Which is faster, PRF based on AES-CTR and PRF based on BLAKE{2,3}?

Recently Blake3 has been announced, which can be used as PRF. I'm wondering which PRF is faster, namely PRF based on Blake3 or the one based on AES-CTR?
396 views

### Can Verifiable Random Functions be used to pick a random node from a pool?

Let's say that I have a decentralized system and I have a list of nodes published on a public log like a blockchain. I want a node A to be able to connect to ...
48 views

### Why is it not ideal to rely on interactive assumption to build PRF?

I understood the meaning of interactive assumption from What is the notion of an interactive assumption? . However, I am not sure why there exists a research field of constructing PRF from standard ...
104 views

### Sponge with PRF instead of PRP

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that ...
168 views

### Luby-Rackoff theorem for Generalized Feistel

I was reading about Luby-Rackoff theorem from various sources: , , , which says you need at least 3 rounds of a $2$-branch Feistel network to get a PRP if the underlying $f$ function is a PRF....
79 views

### Random oracle : Replay

What I understand about the random oracle game: The adversary can query the oracle polynomial many times with the same (secret but unknown) key. From the output returned by the oracle, the ...
51 views

### How can we implement a PRF with 1bit input space and 1024bit output space using AES securely?

I'm considering an implementation of PRF $F:\{0,1\} \times \mathcal{K} \rightarrow \{0,1\}^{1024}$ with a key space $\mathcal{K}$ in particular with AES-128 in counter mode. Since output space is ...
28 views

### How are implementations of PRF and PRG via AES-CTR different?

I heard that AES-CTR can be used for implementation of PRF and PRG. What is the difference between these implementations?
23k views

### What is difference between PRG, PRF, and PRP

Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then ...
65 views

### Do 'nonsequential' PRNGs exist?

It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'. How about a PRNG which allows me to retrieve ...
62 views

528 views

### NIST SP800-108 KDF modes comparison

According to NIST SP800-108, there are three modes that can build KDF from PRF: counter mode, feedback mode and double-pipeline iteration mode. Assume that the same PRF and input distribution are used,...
144 views

### Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?

Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows: Let $s \in \{0,1\}^n$ ...
511 views

### Proof that MAC and hash composition is insecure

Let $F$ be a secure PRF and $H$ a universal hash function. How can I exhibit a pair $(F,H)$ whose composition $$S'((k_1, k_2), m) = F(k_2, H(k_1,m))$$ is an insecure MAC (or an insecure PRF, since a ...
155 views

### What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

What is the difference between; pseudorandom permutation pseudorandom function block cipher? Very confused with the 3 terms and I am not good at advanced math. Can someone explain in plain word?
170 views

### on CPA & KPA security of $\boxplus$-Feistel

I am interested to identify the effect of replacing $\oplus$ with $\boxplus$ on basic balanced Feistel structure over $r$-rounds. Given; $F_\boxplus[L,R]= [S,T] = [R,L \boxplus f(R)]$ where $f$ is ...
712 views

### Simple application of verifiable random function?

I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the ...
551 views

### Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| … ||F_{1…1}(x)$ a PRG?

This exercise comes from Coursera's "Cryptography" course. Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| ... ||F_{1…1}(x)$ a PRG? $F$ is a PRF with $n$ bit key, input, and ...
90 views

### Can Trivium be used as a PRF?

The Trivium encryption algorithm has two inputs, key and IV, both of which are 80 bits long. Let's call it Trivium(key, IV) → keystream. My question is whether doing Trivium(key, input) and taking the ...
117 views

### Is F_k_1(x) \xor F_k_2(x) a pseudorandom function?

I'm trying to determine if $F_{k_1, k_2}(x) = F_{k_1}(x) \oplus F_{k_2}(x)$ ($k_1 \neq k_2$ because that would be lame) is a pseudorandom function. My hunch is that it is. My reduction proof proceeds ...
3k views

### Is there a difference between PRF and a hash function?

Is there a difference between PRF and a hash function? For example: Creation of a secret key is using PRF and creating a secret key is using hash function.
112 views

### Post-Quantum security of Pseudo-Random Functions

I am wondering what is the exact post-quantum security of a PRF. I know that for most symmetric mechanisms, it is assumed it is sufficient to double the key size, but I am looking for a more precise ...
791 views

### What is the difference between PRF and a Random Oracle?

What is the difference between Pseudo Random Functions and Random Oracles? Is the difference only about the domain of PRFs and Random Oracles, former having a fixed domain and latter can act on any ...
129 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 ...
4k views

### What is the practical impact of using System.Random which is not cryptographically random?

I recently noticed a .NET software using PBKDF to derive an encryption key from a password string. This password string was ...
101 views

### What is the most secure/reliable CSPRNG currently available? [closed]

In terms of period length, uniformity/distribution, what is the most secure/reliable CSPRNG currently available?
110 views

### Fundamental difference between the constant, key, nonce, and counter bits in Salsa20/ChaCha20 or AES-Encrypt?

The Salsa20 core function takes a 128-bit constant, 256-bit key, 64-bit counter, and 64-bit nonce and produces a 512-bit value. Or more generically, it is a mapping from 512-bit values to 512-bit ...
32 views

### Help, Feedback and Solutions to a problem on a PoC CSPRNG

Background I do not recommend trying to roll your own crypto. This is just a for-fun PoC, which won't be used in any public or private scenario. I am creating a PoC nearly-true random number ...
96 views

### Security of this PRF [closed]

Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as $F'(k,x||x') = F(k, 0||x)\oplus F(k, 1||x')$ with $x$ and $x'$ of $\lambda-1$ bits. Is $F'$ a secure PRF?
I want a function $y = f(x, len)$: $x$ is the seed. $y$ is the output. $len \in \mathbb{Z^+}$ is the length (bytes) of $y$ Select a seed string $x$ to generate a string $y$. For each same pair of $x$ ...