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.

55 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
332 views

What might be assumed about a PRF if the key has been chosen?

The defining feature of a PRF $f:\{0,1\}^k\times\{0,1\}^s\mapsto\{0,1\}^*$ is that, if the first parameter is selected at random, it should be indistinguishable from a function $g:\{0,1\}^s\mapsto\{0,...
3
votes
0answers
397 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 ...
3
votes
0answers
99 views

Is there any OPRF (oblibivious pseudo random random functions) between one receiver (1 input) and n senders (n inputs)? any references to read?

I am looking for some references for multi-party / distributed Oblivious pseudorandom Functions. I found two party OPRF protocols between a sender $S$ and a receiver $R$ for securely computing a ...
3
votes
0answers
105 views

Pollard's Rho - Restricting the random function to the exponents

Pollard's Rho is usually constructed using a function $f:G \rightarrow G$ which behaves 'random enough' in order to detect a collision with Floyd's cycle detection trick. It is easy enough to observe, ...
2
votes
0answers
65 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 ...
2
votes
0answers
119 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 ...
2
votes
0answers
47 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 ...
2
votes
0answers
66 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 ...
2
votes
0answers
140 views

Does there exist a highly irreversible hash function or a highly irreversible pseudo-random number generator?

In my previous question, I asked about potential symmetric cryptosystems which are designed to be computed by a reversible computer. I am now wondering if there are any cryptographic hash functions ...
2
votes
0answers
426 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 ...
2
votes
0answers
254 views

is this function pseudorandom?

$F_k$ is a PRF , $k\in\{ 0,1\}^n$ , is $H_k(x) = F_{k_1}(x)||F_{k_2}(F_{k_1}(x))$ a PRF? when $k=k_1||k_2$ , $k_1,k_2\in\{ 0,1\}^n$ and $k\in\{ 0,1\}^{2n}$ are random strings , im trying to prove ...
2
votes
0answers
264 views

Showing a generator based to pseudorandom function is also pseudorandom

First of all sorry for the bad title, this is an exercise I'm struggling with: Let $F_k$ be a pseudorandom keyed function (abbreviated to PRF) with key, input and output of length $n$. Define the ...
2
votes
0answers
472 views

Pseudorandom Function Proof

Given a set of pseudorandom functions $F=\{f_s^i\}_i$ for each $s\leftarrow\{0,1\}^n$ generated at random; moreover each $f_s^i$ uses a specific PRG $G^i:\{0,1\}^n\to\{0,1\}^{2n}$, where: $G^i(s)=x_1\...
2
votes
0answers
108 views

Special random distribution algorithm

I am implementing ring signatures as a part of an authorization system. Since the number of users could get high enough to make computation on end-user devices infeasible, I am thinking of "...
2
votes
0answers
101 views

Protocol/algorithms based on a variable-length input PRF

Are the proofs based on a PRF assumption still valid when using a variable-length input PRF ? The answer might be obvious, but I have a doubt.
1
vote
0answers
87 views

Why this isn't a secure PRF?

Given that F is a secure PRF in the example $$F'(k,x)= F(k,x)\mathbin\|F(k,F(k,x))$$ I'm not sure why this isn't a secure PRF? Under what condition $F(k, F(k,x))$ when concatenated to $F(k,x)$ the ...
1
vote
0answers
29 views

Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
1
vote
0answers
41 views

Can Trivium ciphertext be decrypted by an adversary if the key is known, but the IV is not?

Suppose that the adversary is able to recover the key of Trivium cipher. But the associated IV is unknown to him. Will he be able to decrypt the ciphertexts without any complexity?
1
vote
0answers
48 views

Implementing MAC with PRF family $f$, why do we need $f_k$ to be invertible?

As per the title, say we have $\text{MAC}(k,m) = (m,f_k(m))$ where $f$ is a PRF family and every function $f_k$ is PRP, where $f_k(m)$ and $f_k^{-1}(m)$ are efficiently computable. I proved that this ...
1
vote
0answers
82 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 (...
1
vote
0answers
134 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
vote
0answers
41 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
173 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
159 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?
1
vote
0answers
188 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
0answers
64 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-...
1
vote
0answers
126 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 ...
1
vote
0answers
188 views

Define a DEC algorithm for a problem

Given $F$ , a PRF family and $F_{n,k}$ a permutation over the set $\{0,1\}^n$. In addition, each permutation (as usual for PRF) and their inverse (not usual) has an efficient calculation. Define: ...
1
vote
0answers
308 views

Pseudo-random function where the output is inverted using XOR

I'm looking to know whether or not this PRF is secure : $$F'(k, x) = F(k, x) ⊕ 1^n$$ knowing that $F$ is already a secure PRF for $$\{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$$ with, for example, $n= ...
1
vote
0answers
83 views

Does a distinguisher for an PRF based on a hash make the hash function insecure?

I recently found a distinguisher for the PRF $f(s, i) = H(s || i)$ where $s$ is the seed and $i$ is a counter and $H$ is a cryptographic hash function, which is able to distinguish $f(s, i)$ from true ...
1
vote
0answers
111 views

Given the block cipher compute max PRF advantage

Hey all I'm having a bit of problem with this question. Not sure how to approach it. Any help will be appreciated :)
1
vote
0answers
66 views

Are there methods for finding not optimal but good linear approximations for functions?

I'm interested in finding the best, or maybe just a good linear approximation of the function $F^{(19)}: V_{56}\to V_8$, where $$ \begin{array}{l} F^{(1)}(x_1,x_2,\ldots, x_7) = P(x_2+x_6); \\ F^{(...
1
vote
0answers
768 views

how to prove by reduction correctly?

some times when see a problem like : if some G is a PRG then G' is also a PRG. we prove this by reduction in the following way: we assume there is a Distinguisher A for G' and we construct ...
1
vote
0answers
208 views

PHP predicting array_rand

Given the following PHP code (assuming PHP 5.6.x): ...
1
vote
0answers
161 views

Is $E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ PRF?

$E_{k}(x) = F_{k}(x) \oplus F_{k}( \bar x)$ and F is PRF which maps $\left \{0,1 \right \}^n \times \left \{0,1 \right \}^n $ to $\left \{0,1 \right \}^n$. Let two messages $m_{0} = 0^l $ and $m_{1} ...
1
vote
0answers
666 views

Implementing a pseudo random function in practice

Can anyone point me to a C++ crypto library with an implementation of a pseudo random function (PRF)? I don't have much background in crypto theory, but I am in the middle of a graduate course ...
1
vote
1answer
388 views

Is F' a pseudorandom function when F is composed with G, a pseudorandom generator?

If $F$ is a pseudorandom function, is $F'$ also a pseudorandom function in the following: $$ F'_k(x)=F_k(G(x)) \space \space \text, $$ where $G$ is $a$ pseudorandom generator? Also, does the other ...
1
vote
1answer
253 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}$?
0
votes
0answers
37 views

Is this scheme CPA or/and EAV secure

Let F be a pseudorandom function (length preserving). We have the following scheme: To encrypt $ m \in \{0,1\}^{2n}$, parse m as $m_1||m_2$ with $|m_1|=|m_2|$, then choose $r\leftarrow\{0,1\}^n$ and ...
0
votes
0answers
45 views

Concatenation of PRFs is PRG

$F$ be a PRF, is the following $G(x)=F_{0…0}(x)||F_{1…1}(x)$ a PRG?
0
votes
0answers
38 views

Are there any universal PRG’s or PRF’s?

Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom ...
0
votes
0answers
69 views

How does the entropy of $r$ influence the security of the one-time pad $F_k(r) \oplus m$?

In an one-time pad scheme, $s \oplus m$ is uniformly random for any $m \in \{ 0,1 \}^\ell$ if $s$ is uniform in $\{ 0,1 \}^\ell$. By the security of PRF, it seems to be secure to replace the truly ...
0
votes
0answers
38 views

Feistel Network - pseudorandomness

I want to ask about proving not pseudorandomness of Feistel network $(i=1)$ by formal definition: $$ |P[D^{F_k(\cdot)}(1^n) = 1] - P[D^{f(\cdot)}(1^n) = 1]| \le negl(n)$$ I understand how this works ...
0
votes
0answers
41 views

Any formal proof or reference that pseudorandom permutation can be used as pseudorandom function

Assume that a DRBG passes all statistical tests. We use that DRBG to shuffle(Fisher-Yates) an array that contains $\{0,1,\ldots,2^n-1\}$. Now get a pseudorandom permutation $\{0,1\}^n\rightarrow \{0,1\...
0
votes
0answers
25 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 ...
0
votes
1answer
77 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 ...
0
votes
0answers
201 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 ...
0
votes
0answers
33 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
0answers
75 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 ...
0
votes
0answers
145 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 ...