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
1
vote
1answer
211 views

Probability of collision in PRF

My question is related to this: Collision-resistant Pseudorandom function Assume we have a pseudorandom function as follows: $PRF: \{0,1\}^{l}\times\{0,1\}^{t}\rightarrow\{0,1\}^{m}$, where $l$ is ...
15
votes
3answers
561 views

Expected entropy in $P(x)\oplus x$ for random $x$, where $P$ is a random permutation

Let $P$ be a random permutation of $n>1$ bits. Let $F$ be the function on the same domain $\{0,1\}^n$, defined by $F(x)=P(x)\oplus x$. When $P$ is a block cipher with key a message block, that's ...
2
votes
2answers
271 views

Collision-resistant Pseudorandom function

Assume we have a pseudorandom function: PRF(.) We want the following property holds with a high probability: $\forall i, 0\leq i \leq n: PRF(k_1, i)\neq PRF(k_2,i)$ where $k_1$ and $k_2$ are two ...
3
votes
1answer
99 views

Are there order-insensitive, constant-space MAC constructions?

Are there well-studied MAC or PRF constructions that can authenticate a sequence of strings in a way that: Is sensitive to the count of each string in the sequence but not their order; Uses constant ...
0
votes
2answers
110 views

Why should keys be hidden from an eavesdropper for a pseudorandom function?

What advantage would knowing the key used for a given pseudorandom function give over having access to an oracle for that function $F_k(\cdot)$ and the actual key $k$ which will be used? Thanks very ...
1
vote
2answers
577 views

Proof by reduction clarification

If I execute a proof by reduction using a given adversary A as a subroutine to A'. How do I know that using adversary A which can solve a given hard subproblem, is the most efficient subroutine to use ...
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
630 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
1answer
751 views

Indistinguishable encryptions in the presence of an eavesdropper

I'm trying to understand how the messages $m_0$ and $m_1$ can be distinguished here. I understand the adversary game, so in short: Adv chooses $m_0$ and $m_1$, one them is encrypted and Adv is able to ...
2
votes
1answer
556 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)$ ...
1
vote
2answers
189 views

Can I construct a PRP by sorting results of a PRF?

I am using HMAC-SHA256 as a pseudorandom function family (PRF). I read somewhere that a pseudorandom permutation family (PRP) can be implemented by applying a PRF and sorting the output. For example,...
4
votes
2answers
632 views

Pseudorandom function of different keys

Could someone explain to me how they formulated the equation and how it equals to $0^{n}$ (like what F(x, x) equals to or how they cancel each other out?) on the first box and if its related to the ...
0
votes
1answer
1k views

Pseudorandom function or not?

I've read Intro to Modern Cryptography PRF section (and example 3.26) and on stackexchange(1, 2), but I still don't fully know how to prove it (with probabilities) To prove it's a PRF, I know you ...
1
vote
1answer
119 views

Number of possible functions for a PRP

In the Coursera crypto course, Dan Boneh states that if $F: K \times X \to Y$ is a PRF, if the size of the input space $X$ is $2^{128}$, and the size of the output space $Y$ is also $2^{128}$, then ...
2
votes
1answer
125 views

Correlation among Psuedo Random Sequences generated from seeds which are correlated

I want to see and mathematically verify how PN sequence generated by LFSR or maximum length codes would correlate (auto-correlation and cross correlation) for seeds of varying correlation. Say I want ...
0
votes
1answer
196 views

Secret-suffix MD5 as secure PRF (not MAC)

In standard secret-suffix fashion, assume we compute the PRF of some message $m$ as $MD5(x || k)$. Preneel and Van Oorschot showed in [1] that this secret-suffix method is unsatisfactory for ...
2
votes
1answer
159 views

Why a pseudorandom permutation is used in a simulation based proof but pseudorandom function is not?

In this paper: https://eprint.iacr.org/2011/272.pdf the authors use peudorandom permutation in the protocols and proof rather than pseudorandom function. On page 31 (last two lines) they say: "We ...
1
vote
1answer
903 views

Help with terms: hash function and a pseudorandom function

I am a little bit confused about the terms hash function and pseudorandom function. As far as I know, I can use a cryptographic strong hash function as a PRF. The hash function has a IV and is ...
2
votes
1answer
75 views

Leaking information when a value is blinded

Assume all values are defined over a field $\mathbb{F}_p$ where $p$ is a large prime number. Given a fixed value $a,b$ we compute $v_i=a\cdot b+r_i$, where $r_i$ is picked uniformly at random from ...
2
votes
1answer
94 views

Using only pseudorandom function to drive many deterministic keys

My question is related to: Can Pseudorandom values be used as secure keys? But here I'm only using pseudorandom function. Assume we have a pseudorandom function, $PRF$. We have a truly random ...
1
vote
0answers
198 views

PHP predicting array_rand

Given the following PHP code (assuming PHP 5.6.x): ...
2
votes
1answer
234 views

Relationship between source and output entropy

True Random Number Generator (TRNG) use external physical phenomena to generate true randomness. I have a TRNG which uses two sources (oscillators) and gives an output of 256 bits. The entropy of TRNG ...
2
votes
1answer
41 views

Is there any pseudorandom function that outputs $n$ prime number of ring $Z_{N}$ where $N$ is Paillier public key

Let's assume $N$ is Paillier encryption public key, where $N=pq$ and $p,q$ are strong prime numbers. I have a set of plaintext $p_i$ whose domain is $N$. I want to deterministically generate a series ...
0
votes
1answer
650 views

Is this a secure PRG or not?

I've seen this question! from 2 years ago: Given $F$ is a $PRF$, we define $G$ for an input $x\in\{0,1\}^n$ as follows: $$G(x) = F_k(x) \oplus F_k(x \oplus 1^s)$$ The question was if $G$ is a ...
2
votes
1answer
2k views

Prove that a function is not PRF?

Let $G$ $PRG$ and $G'(s)$ equal to the first $n$-bits of $G(s)$, where $|s| = n$. Show that $F_k(x) = G'(k) ⊕ x$ is not a $PRF$. My attempt: Lets assume a $k$ and 2 messages $x_1$ and $x_2$. So, for $...
2
votes
1answer
1k views

Prove that a function is PRF?

Let $F\colon K×K \rightarrow \{0,1\}^{128}$ be a $\mathit{PRF}$ function. Is $F'$ a $\mathit{PRF}$ ? \begin{equation*} F'(x) = \begin{cases} 0^{128} & \quad \text{if $x = 0$} \\ ...
5
votes
1answer
892 views

How to prove a function is pseudorandom function?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I am using a function having $F_{k}$ = $A_{k}(B_{k}(r,m),r)$, the random number is generated using the ...
5
votes
1answer
2k views

PBKDF2 PRF: HMAC or just hash?

I understand the way $\textrm{PBKDF2}$ can be used to 'stretch' a password/passphrase that does not provide full entropy. My question: how does one choose the PRF? A common choice is any well-known ...
9
votes
1answer
310 views

State recovery of Micalli-Schnorr random number generator modulo a prime

Let $p$ be a public prime of $n$ bits. Define the sequence $x_i=z_{i-1}^e \bmod p$, where $z_i$ is the $k$ high-order bits of $x_i$, and $r_i$ the remaining $n-k$ bits of $x_i$ (thus $z_i=\Big\lfloor\...
5
votes
1answer
1k views

Prove that the following MAC is insecure

I am trying to prove that the following MAC is insecure, but I don't know how to exploit the properties of the pseudorandom function $F$ involved: Gen generates a uniform $k \in \{0, 1\}^n$. To ...
4
votes
1answer
273 views

Statistical tests for PRNG that generates a sequence which is not binary

Is there a pratical application to PRNG that generates a sequence which is not a binary one? A ternary, quaternary sequence, for instance. If so, how can we test this? Is there any alternative test ...
0
votes
1answer
177 views

PRNG that takes input a $n$-bit string and gives output a $2n$-bit string?

Recently, I'm reading one paper of Boneh and Zhandry. They have mentioned a pseudo random number generator that takes input a $n$-bit string and gives a $2n$-bit string as output. They just used it as ...
2
votes
1answer
285 views

How can I generate cryptographic-quality 1/f noise, aka “pink noise”?

Can anyone suggest how I'd generate cryptographic quality 1/f noise: aka 'pink noise', where the PSD follows 1/f. I'd be happy to derive the pink noise from white noise (e.g. /dev/urandom), but I ...
1
vote
1answer
592 views

Combining multiple PRGs together

Got some theoretical questions about PRGs to solve (given by lecturer for self-learning, no score involved). Tried to find on the internet but couldn't figure out how to solve them, so I will mention ...
0
votes
1answer
268 views

Collision-Resistance Hash Function PRF

I am trying to solve the following question with an example/proof. The question is from Introduction to Modern Cryptography by Katz and Lindell. Any help would be appreciated.
5
votes
1answer
712 views

Simple application of verifiable random function?

I have been reading a little bit about verifiable random functions (e.g.). In the literature, these are described as "pseudo-random functions that provide a non-interactively verifiable proof for the ...
4
votes
1answer
143 views

Best differential characteristic for this PRF

Consider the following construction of a PRF $F: \{0,1\}^{128} \times \{0,1\}^{64} \to \{0,1\}^{64}$ on 64-bit messages and 128-bit keys. Define $f:\{0,1\}^3 \to \{0,1\}$ by $$f(c,x,y) = \begin{...
2
votes
1answer
357 views

Are the following schemes based on a pseudo-random permutation secure?

I am currently working on the following task: Let F be a pseudorandom permutation. Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses ...
1
vote
1answer
2k views

Determine whether a given function is a pseudorandom generator/function

I am trying to solve the following three tasks (for exam practice, not as a homework): Define $𝐺 : \{0,1\}^* \rightarrow \{0,1\}^*$ by $G(x_1,...,x_n) = 𝑥_1 \oplus 𝑥_2,𝑥_1,⋅⋅⋅,x_n.$ Prove that ...
2
votes
2answers
304 views

Why is $Mac_k(m_1||m_2) = ⟨F_k(m_1), F_k(m_1 \oplus \overline{m_2})⟩$ not a secure MAC?

I am preparing for an exam and trying to solve the following question I found on the internet: Let $F_k$ be a pseudorandom function. Show that the following MAC for messages of length $2n$ is ...
2
votes
1answer
86 views

Distinguishing two sets of pseudorandom values when their keys differ by one

Suppose we use a pseudorandom function $PRF$ and a random key $k$ to generate a set of pseudorandom values: $\forall i, 1\leq i \leq n: w_i=PRF(k,i)$ Now, consider instead of picking a fresh key, ...
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
2answers
414 views

Is a PRF applied to a secure MAC also a secure MAC?

Suppose I apply a PRF to a secure MAC. Do I still have a secure MAC?
2
votes
1answer
528 views

NIST SP800-108 KDF modes comparison

According to NIST SP800-108, there are three modes that can build KDF from PRF: counter mode, feedback mode and double-pipeline iteration mode. Assume that the same PRF and input distribution are used,...
7
votes
2answers
3k views

How can I prove that a function F isn't a pseudo random function?

Let $F$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$, state whether $F'$ is a ...
1
vote
1answer
335 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
252 views

Proof that this is not a secure pseudorandom function?

$p$ is a large prime number. Consider the following function $F:\mathbb Z^*_p \times \mathbb D\rightarrow\mathbb Z^*_p$ where $\mathbb D=2,....,p-1$. $F_k(x)=x^k \bmod p$ Proof that it's not ...
1
vote
1answer
85 views

Is this a secure keyed hashing construction?

I need a PRF for use with PBKDF2, however, the only thing I have is the AES block cipher primitive. I'm attempting to derive a keyed hash function from the block cipher. The design is based on the ...
5
votes
1answer
239 views

Is IPsec IND-CCA secure provided the used block cipher is a pseudorandom function?

I am trying to solve the question whether "IPsec is IND-CCA secure provided the used block cipher is a pseudorandom function" (with IPsec using a variant of Encrypt-then-MAC) As a resource I am given ...
4
votes
2answers
1k views

What is the purpose of Pseudorandom Function Families (PRFs)?

I'm currently in a course in Cryptography, and was wondering why pseudorandom function families exist at all. If there existed one pseudorandom function f(x), based on its definition, could that not ...

1 2 3 4 5 7