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.

46 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
301 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
235 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
102 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
39 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
60 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
123 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
362 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 pubic log like a blockchain. I want a node A to be able to connect to another ...
2
votes
0answers
56 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 ...
2
votes
0answers
239 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
217 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
1answer
509 views

Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?

If $F$ a PRF, and we construct $G$ using $F$ in the following way: $$G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$$ where $|s|= n$. Is $G$ then a PRG? If so how can I prove this? If not how can $G(s)$ ...
2
votes
0answers
350 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
107 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
91 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
37 views

Wrong Proof of Secure PRF

Disclaimer, this is not homework; I found the question statement here: Security of this PRF To restate the question: Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as $F'(k,x\...
1
vote
0answers
68 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
73 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
32 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
93 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 ...
1
vote
0answers
95 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
137 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
131 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
45 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
83 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
162 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
122 views

Luby-Rackoff theorem for Generalized Feistel

I was reading about Luby-Rackoff theorem from various sources: [1], [2], [3], which says you need at least 3 rounds of a $2$-branch Feistel network to get a PRP if the underlying $f$ function is a PRF....
1
vote
0answers
165 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
64 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
101 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
56 views

When we use a PRF to pad a message, do we need to worry about the PRF's output range and/or probability of collision?

My question is related to: How to contruct a pseudorandom with a specific property Collision in pseudorandom function when two different keys are used Question: When we use a pseudorandom function ...
1
vote
0answers
64 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
586 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
190 views

PHP predicting array_rand

Given the following PHP code (assuming PHP 5.6.x): ...
1
vote
0answers
147 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
576 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
323 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
142 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
1answer
55 views

Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0

I have 4 functions to analyze. I need to determine if they are or are not pseudorandom and give a proof/counterexample. I'm having trouble just determining if they are - let alone proving or giving ...
0
votes
0answers
31 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
25 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?
0
votes
0answers
74 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
104 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 ...
0
votes
0answers
70 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 ...
0
votes
0answers
358 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
0answers
129 views

Making PRFs out of PRGs

Is it possible that we take a $PRG$ $G(k)$ of stretch $n\cdot2^n$, and read its output as the table of a $PRF$ $F(K)$ with input and output size of $n$? Intuitively it sounds possible however I read ...
-1
votes
1answer
203 views

Random number generator in a 2p2 Network

for my thesis I am trying to develop a system where nodes from a peer to peer network agree in generate a random number every tot seconds. I am stocked in this problem since almost 1 week anyone can ...