A pseudo-random function is an efficiently-computable function which emulates a random oracle.

learn more… | top users | synonyms (1)

1
vote
1answer
47 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 $...
1
vote
1answer
40 views

Prove that a function is PRF

Let $F : K×K \rightarrow \{0,1\}^{128}$ be $PRF$ function. Is $F'$ $PRF$ ? $ F'(x) = \begin{cases} 0^{128} & \quad \text{if } x = 0\\ F_k(x) & \quad otherwise \end{cases} ...
5
votes
1answer
100 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 ...
4
votes
1answer
210 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
187 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\...
4
votes
1answer
55 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
74 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
0answers
38 views

TLS 1.2 PRF Cipher Suite Specification

I am upgrading our assembler SSL/TLS implementation to support TLS 1.2 and am reviewing RFC5246 specification for TLS 1.2. It states that the PRF is now part of the cipher suite specification but ...
0
votes
1answer
48 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
78 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 ...
0
votes
1answer
98 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 ...
-1
votes
1answer
55 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.
1
vote
0answers
36 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 ...
5
votes
1answer
77 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
69 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
82 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
1answer
61 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
64 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
65 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
83 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?
0
votes
0answers
30 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,...
4
votes
1answer
188 views

How to 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 ...
2
votes
1answer
154 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 ...
0
votes
0answers
87 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
50 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 ...
6
votes
1answer
100 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 ...
2
votes
2answers
95 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 ...
2
votes
2answers
177 views

Given a pseudorandom function F, is $(F_k(r) \; | \; F_k(r + 1))$ also a PRF?

Given: F is a pseudorandom function, G is a pseudorandom generator with $l(n) = n+1$. The following schemes should be classified as being insecure, IND-COA secure, IND-CPA secure. To encrypt $m \in \...
1
vote
1answer
47 views

how to prove sequence y uphold golomb's third axiom

given $\{ x_k \}$ is a m-seq of order $n$, we define $\{ y_k \}$ to be a $m$ digits number: $$ y_i=x_ix_{i+1}...x_{i+m-1} $$ for every integer $n \ge m \ge 1$ how can I show that $\{ y_k \}$ upholds ...
3
votes
1answer
98 views

Can Pseudorandom values be used as secure keys?

I want to derive $n$ keys from a master key. I pick a master key $mk$ and use pseudo-random function (PRF) to generate $n$ pseudo-random values, $v_i=PRF(mk,i)$ where $1\leq i \leq n$. Next, I use ...
2
votes
1answer
130 views

Key Derivation Function (KDF): Can a key derived from KDF be considered as a secure key?

Consider a case where we have a master key MS that is used in pseudo-random function to generate a set of pseudo-random values. Then we use key derivation function to derive a key from each of pseudo-...
3
votes
2answers
184 views

secure PRF or not

I am new in Cryptography and I saw this question in a note I solved it but I'm not sure about my answers. Let $F : \{0, 1\}^n × \{0, 1\}^n→ \{0, 1\}^n$ be a secure PRF (i.e. a PRF where the key ...
2
votes
2answers
120 views

Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG?

I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now ...
0
votes
1answer
38 views

Key derivation function in theory & practice

I am implementing a cryptographic protocol and I'd like to generate a set of seeds using a seed for a pseudo-random function. The reason is that I can pass on only one seed and it can be used to ...
1
vote
1answer
55 views

Help with pseudorandom functions

I started a new lecture this year about crypto and I've had a few problems in the first few weeks with the exercises we got. I would appreciate a "guide" on how to solve problems like the following ...
4
votes
1answer
89 views

If a PRG is constructed by iterating a PRF, is it backtracking-resistant?

Say we construct a pseudo-random generator from a pseudo-random function $f$ (using some constant key $k$ and some initial value $v_0$). We do this by feeding the output block of the PRF back into the ...
0
votes
1answer
76 views

If PRF is non invertible, why does Ctr-mode work?

I am currently taking Dan Boneh's Cryptography I course online. I have just finished the segment discussing the Cipher Block Chaining and Counter-Mode. I am having difficulty understanding why Ctr-...
1
vote
1answer
56 views

PRF that can be distinguished after $k$ queries?

In adaptive attacks, if we design poorly, adversary can modify his queries and break the given pseudo random function (that is being able to distinguish it from uniform randomness). Is there a poor ...
0
votes
0answers
41 views

Existence of a random function under constraints

Let $F_1$ and $F_2$ be two random functions taking as input $N$ bits and returning $N$ bits. Let $C_1$ and $C_2$ two constants of $N$ bits. Is there a random function $P$ taking as input $2N$ bits and ...
2
votes
0answers
118 views

Pseudorandom Functions with different input and output lengths

I am working on a problem found in my Cryptography textbook that goes as follows: Let F be a pseudorandom function such that for $k \in \{0,1\}^n$, function $F_k$ maps $l_{in}(n)$-inputs to $l_{...
2
votes
2answers
101 views

Is pseudorandom function also a one-way function?

Can I assume this? Specifically, I want to know if the following two cases are valid. Suppose $prf_k(m)=c$ One-wayness: Only given $c$, we cannot reveal $m$. Without key $k$, even given $m$, cannot ...
1
vote
1answer
37 views

Deriving a Set of Seeds from a Seed

I need a set of seeds $S=\{s_1,..., s_n\}$, for pseudo-random function where seed $s_i$ is used to generate a set of pseudo-random values. Obviously I need to be able to regenerate the sets of pseudo-...
2
votes
1answer
40 views

Data Switching and Information Leakage

Hypothesis: Let $z,a$ be uniformly random elements of a field $\mathbb{F}_p$ where $p$ is a large prime number. Also, let $(-z)$ be additive inverse of $z$. I have a fixed secret value $x$. I mask ...
2
votes
1answer
64 views

Modified version of a CPA-secure encryption scheme

The following encryption scheme: choose a random string $r \leftarrow \{0,1\}^n$ and compute the ciphertext $c= \thinspace <c_0, c_1>= \thinspace <r, F_k(r) \oplus m>$, assuming $F$ a PRF; ...
2
votes
1answer
85 views

Crypto-period for keys used in PRF

I am wondering about the crypto-period for keys used in pseudo-random functions. For example, let's say I am using HMAC-SHA256 with a secret key $K$. After how many computes do I have to update $K$?
4
votes
2answers
100 views

A periodic PRNG based on hash function?

I need a PRNG which provides 128 bytes numbers. Let's say that given a symmetric key $K$ and an internal state $s$ I use the PRF HMAC-SHA512 this way: The output is PRNG($K, s$) = HMAC-SHA512$_K$($s$...
3
votes
2answers
125 views

Does CTR mode yield a PRF?

Can the keystream generated by CTR mode be considered a pseudo-random function? I give more information. Assume $f$ is a PRF. We define a function which takes 2 inputs, the desired length, and an ...
1
vote
1answer
56 views

Random Function size

I am new to cryptography. I have question regarding the size of the set of random functions. I found the text from "Introduction to modern cryptography" by Katz and Lindell, in another thread which ...
1
vote
2answers
111 views

Let $F$ be a PRF, is the following $G(x)=F_{0…0}(x)∥F_{0…1}(x)|| … ||F_{1…1}(x)$ a PRG?

$F$ is a PRF with $n$ bit key, input, and output length. I know the answer is "NO it isn't!", but I can't understand why. Is that because on any input $x$, the keys for every $F$ in the concatenation ...
3
votes
1answer
589 views

How to prove that a function is not pseudorandom?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I'm struggling with the exercies which ask for proofs, like the following one: Let G(k) be a PRG with |k|...