Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
1answer
56 views

Is this MAC correct and secure?

Let $m \in \{0, 1\}^{2n} = m_1 || m_2$. Let's also assume that $F_k$ is a PRF and $G$ is a PRG defined as $G: \{0, 1\}^n \rightarrow \{0, 1\}^n$. Now, Let's define the $MAC$ scheme as follows: $$MAC(...
0
votes
0answers
40 views

Prove that $F(x)=f(h(x))$ is a secure PRF if $f$ is a secure PRF and $h$ is a CRHF

From my lecture notes, it says that if we have some PRF $f = \{f_k: \{0,1\}^{n} \rightarrow \{0,1\}^{n}\}$ and CRHF $h = \{h_t: \{0,1\}^{2n} \rightarrow \{0,1\}^{n}\}$, then $F = \{F_{k,t} = f_k(h_t())...
-1
votes
0answers
24 views

Let G be a PRG of stretch l(n) = 2n

Determine the success probability of the following $D$: -Input: $y\in\{0,1\}^{l(n)}$ and $1^n$ -Generate uniformly $x' \in \{0,1\}^n$ -Compute $y' = G(x')$ -Return $1$ if $y=y'$; else return $0$ ...
1
vote
0answers
35 views

Indistinguishable encryptions and CPA-secure example

Let $ F $ be a PRF and $ G$ be a PRG with expansion factor $n \to n +1 $ For the following encryption scheme, decide whether it has indistinguishable encryptions and whether it is CPA-secure. ...
1
vote
0answers
29 views

$G_f(x) = x \|f(x)$ is not a PRG with $\operatorname{DPT}$-computable function $f$

Let $f:\{0,1\}^* \rightarrow \{0,1\}$ be any $\operatorname{DPT}$-computable function. Show that $G_f(x) = x \|f(x)$ is not a PRG. Can anyone help me on understand how to prove this?
2
votes
1answer
105 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
1answer
55 views

Can we use a PRF as a PRP?

Leaving aside the problem of how to compute the inverse of a PRF F, may we use it also as a PRP? The reciprocal of this statement is true, see for instance Katz and Lindell, Proposition 3.27, when ...
-1
votes
0answers
56 views

Questions about PRF construction

How can we construct a PRF{$f_k$} mapping $n$ bits to $\ell$ bits such that there exists an efficient algorithm $\text{A}$ such that $A(k)=x$ such that $f_k(x)=0^\ell$? Constructing a PRF{$f_k$} (...
0
votes
0answers
48 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 ...
3
votes
0answers
73 views

Can we construct a PRF directly from a one way permutation function?

In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is ...
5
votes
2answers
162 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 ...
2
votes
1answer
70 views

How can an unlimited adversary distinguish PRF's from Truly Random Functions (TRF)?

I'd like to know which strategy is adopted by an unlimited adversary to distinguish PRF's from Truly Random Functions
1
vote
1answer
67 views

Let F be a PRF, how to prove F3 is PRF?

Let $\operatorname{F}$ be a $\operatorname{PRF}$, how to prove $\operatorname{F^3_{k_1,k_2}}(x) = \operatorname{F_{k_1}}(x) \oplus \operatorname{F_{k_2}}(x) $ is aslo a $\operatorname{PRF}$?
1
vote
1answer
59 views

How to prove the PRF, $F(k,x) = (k \wedge x ) \oplus k$ is PRP?

I am trying to understand PRF's and PRP's. I have got a question where I have to decide whether $F(k,x) = (k \wedge x ) \oplus k$ (where $k$ and $x$ are simple $1$ bits (1 or 0)) is PRP or not. I am ...
4
votes
0answers
105 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 ...
3
votes
2answers
65 views

Construct PRF with longer output from existing PRF

Assume we have a secure PRF $F$ which takes a key of length $k$, a message of length $l$, and outputs an output of length $o$. The task it to construct a secure PRF $G$ which takes the same input ...
3
votes
2answers
128 views

Is $F(x) =Ax+b$ a pseudorandom function or not?

Consider the following keyed function $F$: For security parameter $n,$ the key is an $n\times n$ boolean matrix $A$ and an $n-$bit boolean vector $b$. Define $F_{A,b} : \{0, 1\}^n->\{0, 1\}^n$ by $...
1
vote
1answer
43 views

Instead of sending a set of random values, send a key for a PRF

Some Protocols require one party to send $n$ random challenges (or random values) to another party. For communication efficiency purpose, one can pick a random key for a pseudorandom function, and ...
0
votes
1answer
60 views

How is a PRP different from PRF? Both can be inverted to get the same input

PRP is said to be a bijective function which means that there is a one-to-one mapping with the output. And hence the output can be inverted using the decryption algorithm to get the same input. ...
1
vote
0answers
84 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,...
2
votes
0answers
20 views

Use derived keying material as key for stream cipher

Section 7.3 of SP 800-108: To comply with this Recommendation, the derived keying material shall not be used as a key stream for a stream cipher. Footnote: The level of security provided by ...
3
votes
1answer
95 views

Key derivation: Does it make sense to use KDF and PRF consecutively?

I'm in a project, where the output of a Key Agreement algorithm (uses ECC) is used as input for a KDF, and the output of the KDF (X9.63 KDF) is consecutively used as input for a PRF (CMAC) to ...
1
vote
1answer
234 views

Given a secure PRF $f(k, x)$, is $f(x, k)$ also a secure PRF?

Let $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF. Define $F(k, x) = f(x, k)$. Is $F(k, x)$ also a secure PRF?
2
votes
1answer
42 views

Unsure of syntax used in Searchable Encryption

This image is taken from Algorithm 1 from "Σoφoς – Forward Secure Searchable Encryption, CCS '16". On line 4 there seems to be a new variable, M, that is never defined throughout the rest of the ...
0
votes
1answer
84 views

Can we use Pohlig-Hellman Exponentiation Cipher with a PRG to achieve an oblivious PRF

The Commutative Cipher Setup Alice and Bob agree on a 2048-bit safe-prime $p$, where $(p-1)/2$ is also a prime. Both parties have an encryption exponent $e$ in the range $(1, p-1)$ with $gcd(e, p-1) =...
3
votes
1answer
107 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
2
votes
2answers
82 views

Does PBKDF2 reveal any knowledge about the salt?

DK = PBKDF2(PRF, Password, Salt, c, dkLen) When PBKDF2 is used for key derivation (not password hashing), is it possible for an adversary who doesn't know ...
1
vote
2answers
166 views

Relationship between PRF/KDF/MAC?

It seems that not every MAC is a KDF. But would any PRF also work as both KDF and MAC? Could someone explain the relationship between these 3 definitions?
1
vote
0answers
31 views

Question on inputs of PRFs and HKDF KDF

I've read a lot of information about PRNGs, PRFs and KDFs. As far as I know: PRNG: The seed for the PRNG must be a uniform string. It transforms a short real uniform string into some bits of pseudo-...
8
votes
1answer
252 views

Is $F'_k(x) = F_k(x) \oplus k$ a pseudo random function?

Let $F_k$ be a pseudo random function. Is $F'_k(x) = F_k(x) \oplus k$ necessarily a pseudo random function? I think that it is a PRF, but I just can't find a reduction that works with it.
1
vote
1answer
82 views

When will a function $f$ be a truly random function?

I'm familiar with a definition of a truly random function: $f$ is a truly random function if it was selected uniformly from the set of all the functions $f(x):\{0,1\}^{n} \to \{0,1\}^{n}$ But I'm ...
2
votes
2answers
114 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
91 views

is XOR-hash difference-unpredictable

Let $F$ be a PRF. The $XOR\text{-hash}$ is defined as: ...
-1
votes
2answers
65 views

Why isn't exponentiation in a prime order group a random function?

Give a prime order group $\mathbb Z_p$, let's take a generator $g$ and raise it to $x$, now, is $g^x$ a random number and indistinguishable from any other element in the group? What am I missing?
1
vote
0answers
61 views

Are all commitment schemes pseudo-random functions?

I am interested in understanding whether or not we can use commitment schemes that are both hiding and binding as pseudorandom functions. My reasoning is that if a commitment is hiding, then an ...
5
votes
2answers
216 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
1answer
207 views

How to prove a function is negligible?

My question essentially concerns how to prove if a function is negligible. As a matter of fact, though this question might seem very basic, it seems that most of the "proofs" of negligible concern ...
0
votes
0answers
38 views

proof that 3-round Luby-Rackoff construction is not strong if adversary can do forward and backward queries

I wrote this definition for 3-round Luby-Rackoff construction, which I think is right: $F(L,R) = (A,B)$, where $A = R \oplus f_{k_2}(L \oplus f_{k_1}(R))$ and $B = (L \oplus f_{k_1}(R)) \oplus f_{...
0
votes
0answers
50 views

why isnt E a secure block cipher

Let $\pi : \{0,1\}^n \rightarrow \{0,1\}^n$ be a permutation. Let $E(k, x) = \pi(x \oplus k)$ where $x,k \in \{0,1\}^n$. Why isn't $E$ a secure block cipher? My idea: Suppose $E$ is a secure block ...
1
vote
2answers
173 views

Are the following functions pseudorandom?

Given a PRF $F $, such that for each $k \in \{0,1\} \ ^ n$ , $F_k:\{0,1\} \ ^ n \to \{0,1\} \ ^ n$ , is the function defined by $W_{k_1,k_2}(x) = F_{F_{k_1(0 \ ^n )}}(x) || F_{k_2}(x)$ also a PRF? I'...
3
votes
0answers
55 views

Did “The Catena Password-Scrambling Framework” make an error in the reduction of its pseudorandomness?

I was reviewing the most recent version of the Catena paper and they made some claims that I find questionable in their reduction of the pseudorandomness of the output of Catena (p. 32). First I will ...
1
vote
1answer
143 views

Why do we use (pseudo) random permutations and not (pseudo) random functions for en- and decryption?

Why do we use pseudo random permutations and not pseudo random functions for encryption an decryption?
2
votes
2answers
88 views

Building adversary to show a PRF is not secure

Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$. Let $F'(k, x) = F(F(k, 0^n), x) \; \Vert \; F(k, x)$. $a \; \...
0
votes
0answers
120 views

secure PRFs and XOR

Let $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$. Why is the function $F_1(k, (x_1, x_2)) = F(k, x_1) \oplus F(k, ...
0
votes
1answer
94 views

Relationship between CCA/CPA-security and PRFs

I'm a bit confused about the relationship between CCA/CPA-security and PRFs and particularly when do we think of encryption and decryption as a PRF. Assume we have an encryption scheme $\Pi = (Enc, ...
-2
votes
2answers
87 views

why isn't G a secure Pseudo-Random Function?

let $F(k,x)$ be a secure Pseudo-Random Function defined over $\{0,1\}^n$, that means: $F: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ define a $G(k,x) = F(k,x) \; \Vert \; 0$ how can one ...
0
votes
1answer
94 views

Interpolation in the Exponent (Shamir Shared PRF)

Trying to implement the Diffie-Hellman distributed PRF mentioned by Cachin : https://cachin.com/cc/papers/abba.pdf. It makes sense to me... just use the same Lagrange coefficient I'm using to combine ...
4
votes
1answer
175 views

Can someone explain how OPRF (Oblivious pseudo-Random Function) is based on OT (Oblivious Transfer)?

Can someone explain to me how OPRF is based on OT extensions? I'm currently reading papers about private set intersection problem that uses efficient OT-based protocols based on OPRF, the link of the ...
1
vote
1answer
50 views

Is there a property comparable to IND-CPA for hash functions taking a random value?

I would like to have a function $F(x, rnd)$, where $rnd$ is a fresh random value, such that it is hard, given $x_0$ and $x_1$, to distinguish $F(x_0, rnd)$ from $F(x_1, rnd)$, EDIT: but the values ...
0
votes
0answers
67 views

Secure Pseudo-random functions

Let $F_1$ and $F_2:\{0,1\}^k\times\{0,1\}^k\to\{0,1\}^k$ be any two secure pseudo-random functions. Consider $F_3:\{0,1\}^k\times\{0,1\}^{2k}\to\{0,1\}^k$ defined by: $F_3:(k,(x_1\mathbin\|x_2))\...