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
31 views

Give a distinguisher to differentiate between PRP and RPO

I have understood the proof that shows that a PRP is a PRF except for negligible probability $\frac{q(n)^2}{2^{-l(n)}}$. My computations show me that the same argument, perhaps with minor mathematical ...
2
votes
1answer
40 views

Amplifying PRF Advantage

I am trying to solve this question and I have no idea how to find the value for $q$. I know that I am supposed to find the probability of $q>3q/512$ in terms of the equation $q$, but not sure how? ...
0
votes
0answers
71 views

Computing a probability

Let $(w_1,\cdots,w_l) \in (\{0,1\}^\lambda)^l$, and $r_1,\cdots,r_l $ are chosed as uniformly random from $Z^*_q$ such that $r_1+\cdots+r_l=0$ and $q$ is a large prime number. Also, Let $F$is a ...
1
vote
1answer
65 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(...
1
vote
0answers
49 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
31 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
115 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
77 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 ...
0
votes
0answers
60 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
90 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
187 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
80 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
75 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
80 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
112 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
74 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
131 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
46 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
102 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
90 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
28 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
109 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
252 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
46 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
87 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
117 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
91 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
213 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
35 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
258 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
89 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
139 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
95 views

is XOR-hash difference-unpredictable

Let $F$ be a PRF. The $XOR\text{-hash}$ is defined as: ...
-1
votes
2answers
67 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
66 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
232 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
266 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
41 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
52 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
56 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
163 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
105 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
150 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
129 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
91 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 ...
1
vote
1answer
115 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
297 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
51 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
68 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))\...