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.

48 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
304 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
271 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
62 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
40 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
64 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
124 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
384 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
63 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
221 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
522 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
359 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
93 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
71 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
86 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
33 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
98 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
107 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
142 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
137 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
51 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
84 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
166 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
183 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
67 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
104 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
594 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
195 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
595 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
326 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
155 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
26 views

How are implementations of PRF and PRG via AES-CTR different?

I heard that AES-CTR can be used for implementation of PRF and PRG. What is the difference between these implementations?
0
votes
1answer
45 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
35 views

Is changing-key $F_1$ a secure PRF?

Let $F(k,x):\{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}^n$ be a secure PRF. Prove or disprove whether $F_1(k,x)=F(F(k,0^n),x)$ is a secure PRF. My guess would be that it is PRF, and the part of ...
0
votes
1answer
63 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
32 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
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
110 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
71 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
394 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
131 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
213 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 ...