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.

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
2
votes
2answers
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.
3
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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)$ ...
0
votes
0answers
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?
2
votes
0answers
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
4
votes
1answer
168 views

Luby-Rackoff theorem for Generalized Feistel

I was reading about Luby-Rackoff theorem from various sources: [1], [2], [3], 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....
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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?
27
votes
4answers
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 ...
1
vote
1answer
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 ...
2
votes
0answers
62 views

Is there a cyclic RNG without an explicit form for $i$'th element which is guaranteed to have a sum of zero (subset of elements, $\mod P$ possible)

Let $X$ be a sequence element list of (pseudo) random values generated by a RNG and $x_i \in X$ a member of it. The period length is $k = |X|$ and it is a cyclic generator. For $i>k$ the value $x_i ...
0
votes
0answers
43 views

Is changing-key $F_1$ a secure PRF?

Let $F(k,x):\{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}^n$ be a secure PRF. Prove or disprove whether $F_1(k,x)=F(F(k,0^n),x)$ is a secure PRF. My guess would be that it is PRF, and the part of ...
4
votes
1answer
203 views

Any speed up methods for finding the index of a random value produced by the Inversive congruential generator?

The Inversive congruential generator produces random values with: $$x_{n+1} = a\cdot x_{n}^{-1} + b \mod P$$ (special case if $x_n=0$ -> $x_{n+1}=b$) starting with an initial value $x_0$ With well ...
2
votes
1answer
84 views

Wrong Proof of Secure PRF

Disclaimer, this is not homework; I found the question statement here: Security of this PRF To restate the question: Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as $F'(k,x\...
2
votes
1answer
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,...
4
votes
1answer
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$ ...
6
votes
2answers
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 ...
1
vote
2answers
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?
6
votes
1answer
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 ...
5
votes
1answer
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 ...
2
votes
3answers
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 ...
5
votes
1answer
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 ...
0
votes
1answer
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 ...
10
votes
1answer
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.
2
votes
1answer
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 ...
5
votes
2answers
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 ...
0
votes
1answer
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 ...
31
votes
6answers
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 ...
1
vote
1answer
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?
4
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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?
0
votes
1answer
39 views

Output a pad (un-keyed, variable length) from an input seed (fixed value for same seed)

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$ ...
4
votes
1answer
189 views

Is $f(K, f(K, x))$ a pseudorandom function?

Given a PRF $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$, is $f(K, f(K, x))$ a PRF, too? My hunch is to construct a PRP similar to Feistel ciphers but with the property $f(K, f(K, x)) = ...
1
vote
0answers
72 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 (...
4
votes
1answer
6k views

TLS Key Block calculation - What is a PRF?

In Section 6.3 of the RFC for TLS 1.2, it is written that the key_block is derived from the following formula: ...
4
votes
1answer
98 views

A hash-based pseudorandom function

Let $H()$ be a cryptographic hash function. Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/...
2
votes
2answers
279 views

PRF from hash function?

Let $G=\langle g \rangle$ be a cyclic group of prime order $Q$. Let $H_1:\{0,1\}^*\to G$ be a hash function. Is the following a family of PRF for $s \in \mathbb{Z}_Q^*$? $$f_s(x)=(H_1(x))^s$$ Or ...
0
votes
1answer
88 views

Can you defeat AES-CTR's birthday boundary with a 2nd AES?

This follows on from How do I produce a stream of secure random numbers from AES-Counter mode? Consider then the generator:- $$ \operatorname{AES_{k1}}(n) \oplus \operatorname{AES_{k2}}(n) $$ ...
3
votes
1answer
158 views

PRP vs PRF for the F-function of a Feistel network

A Feistel network is generally defined with a PRF for its F-function, but PRPs have been used as well. What are the theoretical cryptographic implications of using a PRP instead of a PRF? Does it ...
6
votes
2answers
273 views

Do you really need a KDF when you have a PRF?

My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo ...
1
vote
1answer
47 views

PRP, PRF change at next selection?

This is probably a silly question, and similar question was asked before; but I can not figure out what actually is PRP/PRF. For example, it is commented that: A Pseudo Random Function is a ...
2
votes
1answer
81 views

How does changing input size affect The Goldreich-Goldwasser-Micali Construction?

If we want to construct a PRF that is length preserving, it is easy to show with hybrid proof that the resulting construction is a PRF. But what happens when we have longer input. Supose that the ...
1
vote
0answers
91 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 2 3 4 5 7