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
16
votes
1answer
4k views

Security of KDF1 and KDF2 (hash based KDF's)

It's still common to come across implementations of KDF1 and KDF2. Basically these are KDF's that simply derive multiple keys from the key seed and a counter: $K_i = \operatorname{KDF}(K_{master}, i) ...
6
votes
2answers
520 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 ...
27
votes
4answers
24k 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 ...
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.
10
votes
1answer
5k views

Luby-Rackoff theorem confusion

The Luby-Rackoff theorem states that if a round function is a secure pseudorandom function (PRF) then 3 rounds are sufficient to make the block cipher a pseudorandom permutation (PRP). PRPs are ...
10
votes
3answers
7k views

Estimating bits of entropy

I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy. What I'm having a hard time finding is any particular literature ...
13
votes
3answers
2k views

How to construct a good PRF from a block cipher?

We want to explicitly construct a good (as tentatively defined below) Pseudo-Random Function $F$ with $b$-bit input and output, from (preferably just) one Pseudo-Random Permutation $E$ of $b$-bit, as ...
5
votes
1answer
713 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 ...
4
votes
4answers
1k views

The difference between MACs vs. HMACs vs. PRFs

I have some confusion regarding the difference between MACs and HMACs and PRFs and when to use which term. If the function is computed using a hash and secret key like the following, is this a HMAC ...
10
votes
1answer
6k views

Cryptographic security of PHP mt_rand() function using Mersenne Twister algo

At stackoverflow this question has been asked. It uses additional random entropy and a hash method (among others) to try and create a cryptographically secure pseudo-random number generator for PHP. ...
2
votes
1answer
771 views

Is a keyed PRF a MAC?

I remember I read that a MAC can be considered as a PRF. Can a variable-length input keyed-PRF be considered as a MAC?
2
votes
2answers
182 views

How to contruct a pseudorandom with a specific property

How to construct a pseudorandom function $PRF$ with the following property: Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$ Does the PRF with ...
11
votes
1answer
713 views

Does IND-CPA imply PRF?

It is well-known that a pseudorandom function (PRF) can be used to build a CPA-secure symmetric cryptosystem. My question: is PRF necessary for this, i.e., can one show something like "If there exists ...
7
votes
2answers
3k views

How can I prove that a function F isn't a pseudo random function?

Let $F$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$, state whether $F'$ is a ...
4
votes
2answers
881 views

Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?

Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure. To encrypt $m \in \{...
4
votes
2answers
2k views

secure PRF or not

I am new in Cryptography and I saw this question in a note I solved it but I'm not sure about my answers. Let $F : \{0, 1\}^n × \{0, 1\}^n→ \{0, 1\}^n$ be a secure PRF (i.e. a PRF where the key ...
4
votes
1answer
566 views

Differential Privacy: why $\delta$ negligible on the row numbers?

The definition of differential privacy says that an algorithm $M$ is $(\epsilon,\delta)$-differentially private if $$P(M(x \in D) \in S)\leq e^\epsilon P(M(x \in D')\in S) + \delta$$ where $D,D'$ ...
3
votes
4answers
2k views

Difference between Pseudorandom Function vs randomly chosen function

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended ...
11
votes
1answer
340 views

Which compression functions are PRFs?

In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs. The Wikipedia article on cryptographic hash functions ...
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 ...
6
votes
1answer
399 views

Private set intersection, using a semi-trusted server

Alice has a set $S$ of words. Bob has a set $T$ of words. They want to compute the intersection $S \cap T$ of their words, with the help of a semi-trusted third party Trent. Trent runs a central ...
4
votes
2answers
195 views

Can Pseudorandom values be used as secure keys?

I want to derive $n$ keys from a master key. I pick a master key $mk$ and use pseudo-random function (PRF) to generate $n$ pseudo-random values, $v_i=PRF(mk,i)$ where $1\leq i \leq n$. Next, I use ...
2
votes
3answers
2k views

Hash function based on pseudorandom functions and security

Are there hash functions that make use of pseudorandom functions. Precisely, I'm looking for a specification of a hash function based on PRF (and based on the security of such a primitive).
2
votes
1answer
113 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 ...
1
vote
0answers
139 views

Is $F_k(x)=H_k(x \oplus H_k(x))||H_k(x)$ a PRF, where $H$ is a PRF?

Let $H_k(x)$ be known to be a PRF from the family of PRFs defined by $H_k(x): \{0,1\}^{n} \times \{0,1\}^{n} \rightarrow \{0,1\}^{n}$, and then define $F_k(x) = H_k(x \oplus H_k(x))||H_k(x)$. Here,...
1
vote
1answer
222 views

Sub exponentially hard OWF , PRF and iO

I'm currently reading the work "Obfuscation of probabilistic circuits and Applications' by Canetti Lin Tessaro and Vaikuntanathan 2015. It says sub exponentially hard OWF implies sub exponentially ...
6
votes
2answers
407 views

Why does the CBC-MAC require PRFs?

I'm stuck on exercise 4.19 from Introduction to Modern Cryptography. Let $F$ be a keyed function that is a secure (deterministic) MAC for messages of length $n$. (Note that $F$ need not be a ...
5
votes
2answers
754 views

Show that G is not a PRF

$\DeclareMathOperator{concat}{\|}$ I'm trying to do the following assignment: Let $F : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Define function family $G : \{0,1\}^k \times \{0,1\}^{n-...
4
votes
1answer
929 views

What is an oracle adversary?

I'm trying to figure out block ciphers and this is the first time I've encountered the term "oracle adversary". It appears in the context of defining a PRP and a PRF. Can someone please explain what ...
4
votes
2answers
1k views

Is pseudorandom function also a one-way function?

Can I assume this? Specifically, I want to know if the following two cases are valid. Suppose $prf_k(m)=c$ One-wayness: Only given $c$, we cannot reveal $m$. Without key $k$, even given $m$, cannot ...
2
votes
1answer
1k views

Prove that a function is PRF?

Let $F\colon K×K \rightarrow \{0,1\}^{128}$ be a $\mathit{PRF}$ function. Is $F'$ a $\mathit{PRF}$ ? \begin{equation*} F'(x) = \begin{cases} 0^{128} & \quad \text{if $x = 0$} \\ ...
2
votes
2answers
274 views

Collision-resistant Pseudorandom function

Assume we have a pseudorandom function: PRF(.) We want the following property holds with a high probability: $\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$ where $k_1$ and $k_2$ are two ...
2
votes
1answer
232 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
2answers
282 views

Creating a k bit random string

My goal is to create a random $k$ bit string. My question can be divided in two parts. If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the ...
2
votes
1answer
322 views

Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key?

Consider a case where we have a master key MS that is used in pseudo-random function to generate a set of pseudo-random values. Then we use key derivation function to derive a key from each of pseudo-...
1
vote
2answers
189 views

Can I construct a PRP by sorting results of a PRF?

I am using HMAC-SHA256 as a pseudorandom function family (PRF). I read somewhere that a pseudorandom permutation family (PRP) can be implemented by applying a PRF and sorting the output. For example,...
0
votes
0answers
121 views

Building a CPA-secure sCTR from a PRF

Let $F$ be a PRF with $n = l_{in}(n) = l_{out}(n)$. For any PPT-encoding $[\;\;]:\mathbb{Z}_{2^n} \to \{0,1\}^n$ and any polynomial $l(n)$, $G_l(x) = F_k([1])\|\ldots\|F_k([l(n)])$ is a PRG ...