We’re rewarding the question askers & reputations are being recalculated! Read more.

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

289 questions
Filter by
Sorted by
Tagged with
239 views

### is this function pseudorandom?

$F_k$ is a PRF , $k\in\{ 0,1\}^n$ , is $H_k(x) = F_{k_1}(x)||F_{k_2}(F_{k_1}(x))$ a PRF? when $k=k_1||k_2$ , $k_1,k_2\in\{ 0,1\}^n$ and $k\in\{ 0,1\}^{2n}$ are random strings , im trying to prove ...
149 views

### does SHA* collide more or less than a random function?

There were several questions here regarding how surjective SHA-1/2 is, how many values don't have a pre-image from a fixed size input. I and others answered when modelling the relevant hash function ...
275 views

633 views

### Pseudo-random permutation of a range

I have this set: {0,1,2,3,...,15}. I would like to create a pseudo-random permutation from elements of this set, for example ...
542 views

### How Pairwise Transient Key is derived or generated?

I recently study WPA/WPA2 security and I want to know how PTK is derived. I found these parameters in the IEEE 802.11 standard (2012): ...
388 views

### Generating 64 bit random values using AES-CTR

I need to generate 64 bit random values using AES-CTR. Using fixed 64 bit plain text and sequential nonces can I assume the higher order 64 bit output values of the AES-CTR to be random with a ...
90 views

### Count the functions that have an entry with a specific structure

Consider the function $f: \{0,1\}^n\rightarrow \{0,1\}^{2n}$ I want to count all the functions that have one entry where its first n bits are equal with the last n bits. Assume we target entry ...
85 views

### Number of functions included in a keyed PRF

I was reading Introduction to Modern Cryptography by Katz and Lindell and i found this: Coming back to our discussion of pseudorandom functions, recall that a pseudorandom function is a keyed ...
177 views

### Are there any authenticated stream ciphers that use the same PRF for MAC and cipher?

A PRF can be used both to generate a key stream for use in a stream cipher, and to construct a MAC to authenticate. The two can then be combined e.g. in a generic encrypt-then-MAC construction to ...
1k views

### TLS 1.2 PRF with HMAC-SHA256

I am implementing support for TLS 1.2 for the IBM mainframe operating system z/VSE in Assembler language, but am having difficultly getting the PRF to work. I am validating with the values described ...
210 views

### Sub exponentially hard OWF , PRF and iO

I'm currently reading the work "Obfuscation of probabilistic circuits and Applications' by Canetti Lin Tessaro and Vaikuntanathan 2015. It says sub exponentially hard OWF implies sub exponentially ...
2k views

### Is a secure deterministic MAC always a PRF?

Given a secure MAC scheme $\Pi=(Gen, Mac, Vrfy)$, wheres $Gen$ produces uniformly distributed keys, and the algorithm $Mac$ is deterministic, is $Mac$ necessarily a pseudorandom function? I ...
614 views

### Does IND-CPA imply PRF?

It is well-known that a pseudorandom function (PRF) can be used to build a CPA-secure symmetric cryptosystem. My question: is PRF necessary for this, i.e., can one show something like "If there exists ...
597 views

### Is a function defind by PRF with given key is a PRG

Let $G(s)=F_{0^n}(s)$ ($0^n$ is a fixed key given to the PRF F) for any $n∈\mathbb{N}$ and $s∈\{0,1\}^n$. Is G, defined via PRF as above, necessarily a pseudorandom generator? I presume that it is ...
327 views

### Which compression functions are PRFs?

In a 2006 paper Bellare showed that HMAC remains secure even if collision resistance for MD5/SHA-1 is broken as long they are still PRFs. The Wikipedia article on cryptographic hash functions ...
107 views

### What might be the intuition for this scheme to be AEAD and what is the problem with this?

There is a plaintext message $M$, and a key $K \:\stackrel{{\scriptscriptstyle \hspace{0.2em}\$}} {\leftarrow}\ \{0,1\}^{128}$which we will use for AES, we can extract a ciphertext$C \gets \mathrm{...
469 views

### Differential Privacy: why $\delta$ negligible on the row numbers?

The definition of differential privacy says that an algorithm $M$ is $(\epsilon,\delta)$-differentially private if $$P(M(x \in D) \in S)\leq e^\epsilon P(M(x \in D')\in S) + \delta$$ where $D,D'$ ...
164 views

### Is $f(x) = -1.5$ a negligible function? [closed]

Is $f(x) = -1.5$ a negligible function? Since it satisfies the condition for a negligible function?
519 views

### Are these functions pseudo random? Why or why not?

So I am stuck on this problem and have absolutely no intuition as to what the right answer is or how to prove it. Any help would be appreciated. Let $F$ be a length-preserving pseudorandom function. ...
508 views

### Pseudorandom Permutation equals to PRF?

I stuck on the same problem in a cryptography, as stated in this question I found following statement in famous textbook by J. Katz (main wiki PRP article refers to this textbook) PROPOSITION 3.27 ...
217 views

### Showing a generator based to pseudorandom function is also pseudorandom

First of all sorry for the bad title, this is an exercise I'm struggling with: Let $F_k$ be a pseudorandom keyed function (abbreviated to PRF) with key, input and output of length $n$. Define the ...
101 views

### Given the block cipher compute max PRF advantage

Hey all I'm having a bit of problem with this question. Not sure how to approach it. Any help will be appreciated :)
94 views

### Are there any industry standards for PRFs?

I mean something like a NIST, ISO, FIPS or similar standard which defines a constructions for a PRF.
656 views

### Prove that the following private-key encryption scheme is not CPA-secure

Consider the following private-key encryption scheme : The shared key is k $\in$ {0,1}n. To encrypt the message m $\in$ {0,1}n, choose random r $\in$ {0,1}n and output $(r, F_r(k)\oplus \overline{m})$,...
377 views

### How can I change the length of PRF output?

Say if I have a Pseudo Random Function PRF E: {0,1}^k x {0,1}^l -> {0,1}^l. Hence it takes a key of length k and outputs ...
850 views

### How can I encrypt a plain text of length l to a ciphertext of a different length

I'm trying to encrypt a plain text (of length l) and output a ciphertext of length t, where t does not equal to l. How do i get a ciphertext that is shorter than the plaintext input? How about if I ...
65 views

56 views

### When we use a PRF to pad a message, do we need to worry about the PRF's output range and/or probability of collision?

My question is related to: How to contruct a pseudorandom with a specific property Collision in pseudorandom function when two different keys are used Question: When we use a pseudorandom function ...
180 views

### How to contruct a pseudorandom with a specific property

How to construct a pseudorandom function $PRF$ with the following property: Probability that $PRF(k_1,i)=PRF(k_2,i)$ is negligible, for all keys $k_1,k_2$ such that $k_1\neq k_2$ Does the PRF with ...
203 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 ...
550 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 ...
256 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 ...
98 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 ...
103 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 ...
453 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 ...
64 views

179 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,...
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 ...