New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# 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.

78 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
508 views

• 113
283 views

### XOR of a secure PRF is modified weakly secure PRF

While reading A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. There was the next exercise (Ex. 4.2 (b)), let $F$ be a secure PRF over $(K,X,Y)$ where $Y := \{0,1\}^n$ and $|X|$...
• 66
202 views

### Is it necessary for a round function $F$ in a Feistel cipher to be pseudorandom?

I stumbled across this question where the questioner asked for specific requirements for the round function $F$ in a Feistel network so that the construction is secure. The answer explained that a ...
217 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 ...
• 1,625
655 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 ...
258 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 ...
122 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, ...
43 views

### Secure mapping functions

I have two secret numbers $A$ and $B$. Both are uniformly-distributed 32-bit numbers. I need a deterministic function $f(x)$ such that $f(A) = B$. $f(x)$ must not leak any information about $A$ or $B$....
• 117
51 views

• 33
1 vote
82 views

### Is there any structure similar to GGM but more efficient?

Although Goldreich-Godlwasser-Micali (GGM) construction of a pseudo-random function (PRF) from a pseudo-random number generator (PRNG) is widely in many cryptographic applications, it needs to consume ...
1 vote
I've know that a PRF Xored with its key is not a secure PRF. Then I wonder that what if the Xored (or multiplied) item is another random number. The formal expression is as belows: Let $F_k(x):\{0,1\}^... 1 vote 0 answers 352 views ### Building an Adversary for a PRF game Here is the game: How can I make an$\mathcal{O}(k^2)$-time adversary making only one query to its Fn oracle and achieving advantage$= 1 - 1/(p-1)$Here is my idea so far: query$2^{-1}$, which when ... 1 vote 0 answers 373 views ### Program to predict a 5-bit output from mersenne Twister random module from python Is there a program to predict the mersenne twister random module in python for a 5-bit integer output, provided the consecutive 3994 outputs are available? The random module is not seeded so i guess, ... 1 vote 0 answers 133 views ### Formal security arguments for 3 round feistal network using PRF There is a proof sketch in Introduction to modern cryptography that a three-round feistel network using pseudorandom round functions is a secure pseudorandom permutation PRP Πk against probabilistic ... • 11 1 vote 0 answers 111 views ### Insecure pseudo random functions Let$F$be a pseudo-random function. Show that the following constructions are insecure as message authentication codes (in each case$K \in \{0,1\}^n$is the private key):$(a)$To authenticate a ... • 41 1 vote 0 answers 85 views ### How does a pseudorandom generator produce a similar distribution to$U_{n}$? According to Wikipedia, a function${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$with${\displaystyle \ell < n}$is a pseudorandom generator against$\mathcal {A}$with bias$\epsilon$if, ... • 177 1 vote 0 answers 668 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 ... • 341 1 vote 0 answers 59 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? • 73 1 vote 0 answers 99 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 0 answers 431 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 ... 1 vote 0 answers 43 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 ... 1 vote 0 answers 149 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 (... • 11 1 vote 0 answers 561 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 ... • 11 1 vote 0 answers 57 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\...
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. ...