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

385 questions
Filter by
Sorted by
Tagged with
494 views

### Probability conventions in cryptography

I am working on Victor Shoup's tutorial on game-based security proof and want to figure out some notions from the perspective of probability theory. Consider the following PRF advantage defined on ...
71 views

### Are Block Ciphers Pseudorandom functions? [duplicate]

I am reading this page on wikipedia on Key derivation function here where it states: In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys ...
59 views

60 views

### Computational indistinguishability of two LWE type samples

Consider the problem of distinguishing between polynomially many samples of either \begin{equation} (x, b, As + e) ~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) + e'\right). \end{equation} Here, $A$ ...
66 views

### Using PRF as a building block to build other primitives?

I am doing an independent research in cryptography. I have designed a post-quantum secure pseudo random function. Just constructing a PRF will not help me to publish in reputed journals. I was ...
32 views

### Enumerating values from a linear congruential generator java Random()

During my research on a java application, I discovered that the nextInt(64) function of the java.Random() class is used to ...
132 views

### Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

In Katz's Introduction to Modern Cryptography, Chapter 7 Practical Constructions of Symmetric-Key Primitives In previous chapters we have demonstrated how secure encryption schemes and message ...
78 views

### Is key rotation necessary when using HMAC as a pseudo random function?

I need to generate a deterministic identifier from some user data. One of the user data items is highly sensitive, but the other two are not. The identifier will be sent to an external party regularly,...
1 vote
45 views

### Is F' = G(F)) a secure PRF given F and G are secure? [closed]

If we have a secure PRF 𝐹(𝑘, 𝑥) and a PRG G where 𝐺 : 𝒴 → 𝒴 × 𝒴 is a secure PRG. Is the PRF F'(k, x) = = 𝐺(𝐹(𝑘, 𝑥)) also secure?
40 views

### Is this property implied by a pseudorandom function?

Given a keyed pseudorandom function $f: S \times X \rightarrow Y$, where $S$ is the space of secret keys, $X$ is the input domain, and $Y$ is the range, the pseudorandom property says that given any ...
170 views

### The different bounds of PRP/PRF switching lemma

The PRP/PRF switching lemma is usually denoted as follows: I understand the proof of this version of the bound $\frac{q(q-1)}{2^{n+1}}$ and the game-playing technique behind it. However, I came ...
101 views

### Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen

I am trying to understand the following pseudorandom function constructed by Banerjee, Peikert, and Rosen in this paper, assuming the hardness of LWE. Consider the following LWE/LWR based pseudorandom ...
1 vote
75 views

### Converting a 32-bit ARX cipher to a 64-bit one, should the rounds be increased?

I read about using 64-bit words in PRF functions. I want to convert the 32-bit ARX cipher Chacha into a 64-bit version, with key/block size of 1024-bits (512*2=1024-bits) My question is: Should I add ...
74 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 ...
63 views

### Does Enc and Dec need to be a pseudo-random function for a scheme to be CPA secure?

I am currently going through past finals' questions as exercises for my exam and there are no solutions provided. The question I am currently doing is: Let ∏ = (Enc, Dec, Gen) be a CPA-secure ...
1 vote
64 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
46 views

### Showing that $F'(k, x) := F(F(k, 0^{n}), x)$ is a PRF [duplicate]

I wanted to do some practice on security reduction proofs, and I am stumped on this one from the Boneh-Shoup book. If $F(k, x)$ is a secure PRF, then show that $F'(k, x) := F(F(k, 0^{n}), x)$ is a ...
78 views

### LWE and pseudorandom functions

Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?
59 views

### Where can I find good practice questions for proofs by reduction?

I already have the Katz-Lindell textbook, but I also want some additional practice problems for security reductions for stuff like PRFs, MACs, digital signatures, private and public key schemes, and ...
335 views

### Is there any result which states that if the output of these two functions is XOR'd, the XOR'd output is pseudorandom

Let $\mathbb{G}$ be a group of prime order $p$ with generator $g$. Suppose that I randomly pick $r_1,z_1 \leftarrow \mathbb{Z}_p$ and $r_2, z_2 \leftarrow \mathbb{Z}_p$ and $c \leftarrow \mathbb{G}$. ...
258 views

The Cryptography made simple (page 207, under Fig 11.12)(Nigel Smart) say that adversary's advantage of IND-PASS Game is $Adv1 = 2\times|Pr[b=b']-\frac{1}{2}|$. The reason for multiplying by 2 is to ...
1 vote
152 views

### How are the keys used in cryptography generated?

It seems there are keys everywhere in cryptography. From things like HMAC to encryption (both asymmetric and symmetric). The bit I do not totally understand now is how are cryptographic keys generated?...
1 vote
76 views

### What does a deterministic MAC actually mean? [closed]

Does a MAC that's deterministic mean it uses a PRF? Thanks for the help!
34 views

### How to show the PRF in 2. is secure? [duplicate]

Let F be a PRF defined over F:{0,1}n×{0,1}n→Y. 1.We say that F is XOR-malleable if F(k,x⊕c)=F(k,x)⊕c for all k,x,c∈{0,1}n. 2.We say that F is key XOR-malleable if F(k⊕c,x)=F(k,x)⊕c for all k,x,c∈{0,1}...
105 views

### Why is a two-round Feistel Network not a PRF? [duplicate]

I am a student studying PRP and PRF in school, my prof gave us a thinking question: "Why is a two-round Feistel network not a PRF, even while the component function is a PRF?" I've seen that ...
1 vote
97 views

### How to build a lsfr based on sequence $s_i = s_{i-1} + s_{i-4}$? [closed]

How do I know where my XOR gates go? What does the F2 stand for here? Also the next task is to generate the sequence (with initialisation vector $s_0 = 1, s_1 = s_2 = s_3 = 0$) until it becomes ...
1 vote
205 views

### How to show the PRF in 4.8(b) is not secure? [closed]

Let F be a PRF defined over $F:\{0, 1\}^n \times \{0, 1\}^n \to Y$. We say that $F$ is XOR-malleable if $F(k, x \oplus c) = F(k, x) \oplus c$ for all $k, x, c \in \{0, 1\}^n$. We say that $F$ is key ...
57 views

### Types of PRFs and its applications

I was learning about iO from this paper when I noticed the different new types of PRFs. I wanted a clear understanding of the following. What are Puncturable PRF (PPRF)? Why is it defined in the way ...
42 views

### Mersenne twister word size and degree of recurrence combination

For a 32-Bit variant of Mersenne twister, if the outputs Should be a 5-Bit integer(word size) then what is the value of recurrence according to the k-distribution?
1 vote
79 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, ...
73 views

### If a Pseudorandom Function (PRF) is supplied with a key with the same size of output block, can 2 or more keys generate the same output for a input?

There a 2 examples: A block cipher with 128 bits of block size taking a plaintext and a 128 bits key (AES-128). A keyed hash function with 1024 bits of block size in its output, taking a message and a ...
218 views

### What are the fastest algorithms that sample from the uniform distribution?

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so? I've ...
483 views

### Efficient way to pick an array index by using a, say, 64 bit random number?

Say, I have uint64_t rand = <some random number>, and char array = .... My goal is to pick an element in ...
54 views

### When does a proof by reduction do not hold?

I was doing the following exercise from the Introduction of Modern Cryptography from Katz and Lindell: Let $F$ be a length preserving pseudorandom function. For the following constructions of a keyed ...
36 views

### PBKDF2 with pepper [duplicate]

The main purpose of PBKDF2 is to generate a strong key from a weak password by using an input (the weak password) and a salt (which is stored in plaintext). Is it useful to use a pepper with PBKDF2 ? ...
117 views

### Is PRF XORed with its key still a PRF? (always)

$\forall k \in \{0,1\}^n,m \in \mathbb{M},F_k(m)$ is defined as follows: $F_k(m) = F'_k(m) \oplus k$. It is known that $F'_k$ is a PRF. Note: 𝕄 is the message space and it's assumed that the key $k$ ...
138 views

### Is the following derived MAC where the output is XOR'ed with the key secure?

Hey I'm wondering if the following scheme is secure or not , I tried reductions and some tries to prove that it not must be secure but I feel completely stuck . More details: It's just any reduction ...
1 vote
66 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 ...
1 vote
102 views

### Four round Feistel network using pseudo random round function [closed]

I am solving a four-round Feistel network using pseudo-random round function is a strong pseudo-random function for security against adversaries, but I don't understand that how to solve I know 3 ...
204 views

### How to build a periodic PRF from a PRF?

This question may be related to this one, though the construction differs. Let us consider a PRF $f$. We define $g_k$ as $g_k(x)=f(x)\oplus f(x\oplus k)$. Is $g_k$ a PRF, assuming $k$ is chosen at ...
231 views

### Are these functions secure PRFs?

Let $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF (i.e. a PRF where the key space, input space, and output space are all $\{0,1\}^n$) and say $n=128$. My assignment is to show ...
184 views

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $... 4 votes 1 answer 243 views ### What is the NIST recommended maximum bias for random number generators? What is the maximum bias recommended by NIST for random number generators? This answer says that it is$2^{-64}$. Is it same for all applications? Does NIST have a publication with more information? I ... 5 votes 3 answers 292 views ### How to combine$n$'less random' bits to generate one 'more random' bit? Suppose we have a random number generator badrand() generating 1 with probability$0.9$and 0... 1 vote 3 answers 369 views ### Is collision resistant hash enough for one-block counter mode? Let$H:\{0,1\}^*\rightarrow \{0,1\}^\ell$be a collision resistant hash function (CRH), and let$\Pi = (\mathsf{enc,dec})$be an encryption scheme with the following properties:$\Pi.\mathsf{enc}: \...
1 vote
I'm studying for my crypto exam and got stuck on following example: Is $F'_k(x) = F_k(0||x)||F_k(1||x)$ with $x \in \{0,1\}^{n-1}$ a PseudoRandom Function PRF, under the assumption, that $F_k$ is a ...