Stack Exchange Network

Stack Exchange network consists of 175 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.

3
votes
1answer
39 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 ...
1
vote
1answer
36 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 ...
6
votes
2answers
201 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 ...
2
votes
1answer
50 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
53 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 ...
3
votes
2answers
83 views

Does a regularly reseeded PRNG provide backtracking resistance?

I'm currently discussing a security topic with some of my classmates. A cryptographic PRNG typically provides backtracking resistance if an adversary that compromises the internal PRNG state cannot ...
-2
votes
1answer
92 views

A well known hash function?

Name a well-known and standardized function $F : \{0,1\}^{256} × \{0,1\}^{128} → \{0,1\}^{128}$ that is believed to be a pseudorandom permutation. I was thinking SHA256, but I am not sure. Can ...
0
votes
0answers
24 views

Tool to find non-linearity, resiliency and algebraic degree of a boolean function?

Is there any program or software to find out cryptographic properties like non-linearity, algebraic degree, balancedness and resiliency of a large boolean function?
2
votes
1answer
91 views

Constructions of PRF (Pseudo Random Function)

I was taught only GGM based PRF construction in class. It's very inefficient. I am just curious about various PRF constructions from standard assumptions. Please provide a few PRF constructions from ...
0
votes
2answers
125 views

Which functions can be used as Pseudo Random functions? Can block Ciphers be used for this purpose with our own encryption function?

Since the cloud security algorithm I am trying to implement says that for a PRF, any secure encryption algorithm or a keyed hash function can be used. The security parameter I have chosen is 15 bits ...
1
vote
2answers
118 views

Statistical Tests for Pseudorandom Functions

Say I have an implementation of a potential Pseudo-Random function and I want to test whether my implementation does at least not contain any obvious flaws. As far as I understand, in other ...
1
vote
0answers
31 views

How to prove security of scheme constructed by Hash then PRP

Suppose there is a scheme where a message is first hashed and then sent to a PRP. If the hash is done using an $\epsilon$-bounded universal hash function and the PRP $K\times \{0,1\}^n\rightarrow\{0,1\...
1
vote
0answers
84 views

Patarin’s H-Coefficient Technique

I have come across many paper that applies Patarin’s H-Coefficient Technique in various cryptographic securities (KPA, CPA, CCA,...). I am asking kindly if someone could explain it simple with ...
0
votes
1answer
79 views

The role of IV when AES is used as $PRF$

We want to use AES as a pseudorandom function. Given a random master key, we want to derive a set of pseudorandom values/keys, e.g say $n$ keys. Then from each of those derived keys, we want to derive ...
2
votes
1answer
85 views

Formal definition PRNG

I tried to look for a book that presents cryptographic concepts(specially PRNG) in a formal way but what I find is an intuitive approach. So my question is what is the formal definition of Psuedo-...
3
votes
3answers
556 views

Truncating the output of AES-128

I'd like to use the output of a pseudorandom function (PRF) as a one time pad. I want to use AES-128 (as it's commonly used as a PRF). As we know AES-128 output 128 bits. Question: Would be secure ...
1
vote
1answer
44 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 suggest me that the same argument, perhaps with minor ...
2
votes
1answer
50 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
73 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
83 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
69 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
92 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
143 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
107 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
83 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
158 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
270 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
85 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
89 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
104 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 ...
5
votes
0answers
132 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
96 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 ...
4
votes
2answers
159 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
48 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 ...
1
vote
1answer
216 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
105 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
36 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
129 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
289 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
48 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
97 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
143 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
112 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
319 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
42 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
270 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
105 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
186 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
121 views

is XOR-hash difference-unpredictable

Let $F$ be a PRF. The $XOR\text{-hash}$ is defined as: ...
-1
votes
2answers
71 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?