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
0
votes
0answers
77 views

Why is a two-round Feistel Network not a PRF?

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
1answer
85 views

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

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
0answers
77 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 ...
2
votes
0answers
49 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 ...
0
votes
0answers
28 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
0answers
39 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, ...
0
votes
0answers
27 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 ...
0
votes
2answers
175 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 ...
2
votes
3answers
446 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 ...
0
votes
0answers
42 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 ...
0
votes
0answers
32 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 ? ...
3
votes
1answer
73 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$ ...
2
votes
0answers
88 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
0answers
34 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
0answers
88 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 ...
3
votes
1answer
176 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 ...
0
votes
0answers
53 views

Random Oracle Model for an ideal block cipher vs Ideal Cipher Model

Some security proof involving an ideal function use the Random Oracle Model (ROM). They posit a thing that given integer $b$ and bistring $M$, returns what it previously returned for that input $(b,M)$...
4
votes
1answer
118 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 ...
8
votes
4answers
168 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 $...
4
votes
1answer
228 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
3answers
273 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
3answers
329 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
1answer
94 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 ...
2
votes
1answer
141 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 \...
5
votes
3answers
193 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} +...
1
vote
0answers
49 views

Trying to get idea of reduction [duplicate]

Suppose $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$ $$F'(k, x) = F(F(k, 0^n), x) \; $$ Trying to get the intuition ...
0
votes
1answer
47 views

Small values with non-uniform distribution encoded as large values with uniform distribution

Given a non-uniformly distributed set of 32-bit values (for example), is there a way to reversibly encode each one as a 128-bit value (for example) where they'd be approximately uniformly distributed ...
0
votes
0answers
59 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 ...
4
votes
1answer
484 views

Is HMAC-SHA256 a PRF?

In the abstract of The Exact PRF-Security of NMAC and HMAC, Gazi, Pietrzak, and Rybar state: NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto’96], who proved it to be a secure ...
3
votes
4answers
250 views

If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure?

I am new to crytography. Can anybody tell me what I might be missing here?
1
vote
0answers
73 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, ...
3
votes
1answer
49 views

Correctness of signle-point Oblivious PRF

In the paper Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF, Chase et al. shows that a PSI scheme can be achieved by using an oblivious PRF (OPRF). They summarized a ...
0
votes
1answer
85 views

How to define secure pseudorandom functions?

I was told that for both cases the PRF is strong/secure, but I cant find a proper way to define this. Personally i think only (b) is secure because $x$ is not as strong as $O^n$ for $Fs$. But if that ...
1
vote
1answer
176 views

Questions about using PRF to construct PRG

Let F be a secure pseudorandom function with 128-bit key and 256-bit block length. Which are the following functions G are secure pseudorandom generators? (Select all that apply.) A. $G(x)=F_x(0...0)$...
1
vote
1answer
150 views

Deterministic Counter Mode with a PRF. What does evaluate at a point mean?

This is from Dan Boneh's Lecture where he talks about operating a PRF (AES, DES) in Deterministic Counter Mode. Dan Boneh says What we could do is we could use what's called a deterministic counter ...
1
vote
1answer
81 views

Unable to understand the concept of a 1-bit PRF

In his lecture on building Block Ciphers from PRGS, Dan Boneh says this Let’s start by finding out if we can build PRF from a PRG? Let $G:\ K \to K^2$ be a secure PRG Define 1-bit PRF $F:\ K \times \{...
1
vote
1answer
47 views

PRFs / hash functions with a parameter amount of 'hot' bits?

Does there exist a cryptographically secure hash function (or keyed PRF) that can take, as a parameter, the number of 'hot bits' in the output? And if so, what is the name? The goal here is to produce ...
0
votes
0answers
233 views

Is this scheme CPA or/and EAV secure

Let F be a pseudorandom function (length preserving). We have the following scheme: To encrypt $ m \in \{0,1\}^{2n}$, parse m as $m_1||m_2$ with $|m_1|=|m_2|$, then choose $r\leftarrow\{0,1\}^n$ and ...
5
votes
2answers
276 views

Can a PRF distiguisher invoke the function's algorithm?

The definition of a function $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $\mathcal F$, and there is no P.P.T....
2
votes
2answers
424 views

Which of those functions are PRFs?

Assume that $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$ is PRF. Examine if the following functions are PRFs: $$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), ...
0
votes
0answers
99 views

Concatenation of PRFs is PRG

$F$ be a PRF, is the following $G(x)=F_{0…0}(x)||F_{1…1}(x)$ a PRG?
1
vote
0answers
158 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 ...
0
votes
0answers
49 views

Are there any universal PRG’s or PRF’s?

Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom ...
0
votes
1answer
109 views

PRF and deterministic polytime function implie PRG

I'm struggling while trying to resolve this exercise. I already read all questions about PRG and PRF here and some proofs around the internet but none of them helped me. let's consider a function $C$ ...
1
vote
0answers
43 views

Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
0
votes
0answers
78 views

How does the entropy of $r$ influence the security of the one-time pad $F_k(r) \oplus m$?

In an one-time pad scheme, $s \oplus m$ is uniformly random for any $m \in \{ 0,1 \}^\ell$ if $s$ is uniform in $\{ 0,1 \}^\ell$. By the security of PRF, it seems to be secure to replace the truly ...
6
votes
1answer
509 views

Pseudorandom Generator

In a cryptographic application, two types of (pseudo)random bit streams are needed: a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and a stream $B= b_{1}b_{2}...
3
votes
4answers
1k views

Could a fixed RSA encryption be used instead of a salt to prevent rainbow table attacks?

It's common to use a salt before hashing a password in order to prevent an attack by rainbow tables. Would it also work to encrypt the password for instance by RSA encryption - by a permanent RSA ...
1
vote
1answer
97 views

Silent Oblivious Transfer Question

Recently, Boyle et. al. proposed silent OT extension. In the paper, silent OT, it seems that a GGM based PPRF used as building blocks. However, after reading the paper, I have two questions that are ...
0
votes
1answer
96 views

Why is SKEYSEED derived using the nonce as a key?

In IKEv2, SKEYSEED, which is used to as a seed for generating the rest of the keys, is generated as SKEYSEED = prf(Ni | Nr, g^ir)...

1
2 3 4 5
8