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

302 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
64 views

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 ...
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 ...
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 ...
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, ...
147 views

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