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.

Filter by
Sorted by
Tagged with
7 votes
2 answers
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 ...
user avatar
  • 359
0 votes
2 answers
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 ...
user avatar
0 votes
1 answer
59 views

Why is using a truly random function in a fixed length encryption scheme not efficient?

I am working through Katz and Lindell, and Theorem 3.26 in the book proves that a construction based on a PRF is CPA-secure. The thrust of the scheme is that if $F_k$ is a PRF, with $k, m, r \in \{0, ...
user avatar
  • 480
0 votes
1 answer
101 views

Is this pseudo random function any good and/or original? [closed]

I designed this pseudo-random function algorithm that takes a uint64 and returns a uint64. I'd like to know if it is any good ...
user avatar
1 vote
0 answers
122 views

Is PRF Xored (or multiplied) with a random number still a secure PRF?

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\}^...
user avatar
0 votes
1 answer
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$ ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
2 votes
2 answers
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 ...
user avatar
  • 151
2 votes
1 answer
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,...
user avatar
  • 135
1 vote
0 answers
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?
user avatar
  • 11
2 votes
0 answers
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 ...
user avatar
  • 163
4 votes
1 answer
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 ...
user avatar
  • 115
2 votes
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
2 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 43
2 votes
1 answer
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?
user avatar
0 votes
1 answer
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 ...
user avatar
  • 43
4 votes
1 answer
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}$. ...
user avatar
  • 163
2 votes
0 answers
258 views

Should I normalize adversary's advantage in IND-XXX Game?

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 ...
user avatar
  • 121
1 vote
3 answers
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?...
user avatar
1 vote
0 answers
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!
user avatar
  • 43
0 votes
0 answers
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}...
user avatar
  • 11
0 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
2 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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?
user avatar
1 vote
0 answers
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, ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
2 answers
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 ...
user avatar
2 votes
3 answers
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[20] = .... My goal is to pick an element in ...
user avatar
  • 519
0 votes
0 answers
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 ...
user avatar
  • 23
0 votes
0 answers
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 ? ...
user avatar
3 votes
1 answer
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$ ...
user avatar
2 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
3 votes
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
8 votes
4 answers
184 views

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $...
user avatar
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 ...
user avatar
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...
user avatar
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}: \...
user avatar
  • 413
1 vote
1 answer
292 views

PRF proof and length-preserving

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 ...
user avatar
  • 1,492
2 votes
1 answer
202 views

Questions on PRF

Define three hash functions: $H_1: \{0, 1\}^* \rightarrow \mathbb{G}$ mapping $x$ to the group $\mathbb{G}$ of prime order $q$ $H_2: \mathbb{G} \rightarrow \{0, 1\}^\tau$ $H_3: \{0, 1\}^* \times \...
user avatar
  • 151
5 votes
3 answers
204 views

A question regarding next-bit predictors

Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows. \begin{equation} \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} +...
user avatar

1
2 3 4 5
โ€ฆ
8