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.

Filter by
Sorted by
Tagged with
2
votes
0answers
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 ...
1
vote
1answer
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 ...
3
votes
1answer
275 views

Understanding pseudo-random functions (used in a Oblivious Transfer Protocol)

Given a family of pseudo-random functions $$\{F_K:\{0,1\}^m\mapsto \{0,1\}^m | K \in \{0,1\}^t \}.$$ I want to understand how the elements behave. Lets say we take some $F_{K_1}$ and evaluate at $x=...
-1
votes
1answer
375 views

Is a composition of PRGs itself a PRG?

I have this question: Given $G_1$, $G_2$ are PRG's. Is $H(s)=G_1(G_2(s))$ also a PRG? Thank you.
2
votes
2answers
276 views

Creating a k bit random string

My goal is to create a random $k$ bit string. My question can be divided in two parts. If a $n$ bit string $s$ is computationally indistinguishable from a random $n$ bit string, can we say that the ...
0
votes
2answers
301 views

Is this MAC secure?

Suppose that we have a pseudorandom function $F$. We compute a tag on message $m=m_1,m_2,...,m_l$ with $F_k(\langle 1\rangle\mathbin\Vert m_1) \oplus \dots\oplus F_k(\langle l\rangle\mathbin\Vert m_l)$...
1
vote
2answers
982 views

Is this function a secure PRF?

I have a PRF function $F(k, F(k,0)) = 0$. So that means, $k \times F(k,0) \rightarrow F(k, 0)$. I hope you can help me understand if the function $F(k, F(k,0))$ is a secure PRF or no? Thanks for ...
1
vote
1answer
260 views

security for PRF when key is changed often

Here's the situation. Suppose I have a secure PRF $F$ and use $F$ in the following way: for equal size message $m_i$ in $\{m_j\}^{q}_{j=1}$( $q=poly(n)$, $n$ is security parameter ), randomly select $...
2
votes
1answer
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 ...
3
votes
1answer
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): ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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 ...
8
votes
3answers
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 ...
11
votes
1answer
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 ...
4
votes
2answers
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 ...
11
votes
1answer
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 ...
2
votes
1answer
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{...
4
votes
1answer
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'$ ...
0
votes
1answer
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?
3
votes
1answer
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. ...
1
vote
2answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 :)
4
votes
2answers
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.
2
votes
2answers
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})$,...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
65 views

Pseudorandom function outputting a field element VS pseudorandom function outputting a string

Assume we have two pseudorandom functions $PRF$ and $PRF'$ defined as follows: $PRF: \{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \{0,1\}^{n}$ $PRF': \{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \mathtt{F}...
2
votes
1answer
108 views

Compute maximum PRF advantage

Hello all, I'm new to crypto, I'm not sure if my thought process is correct ? any assistance will be helpful. How useful is the partial info that A gets from (a), (b), and (c) ; in (c) A can ...
2
votes
1answer
297 views

Show G is insecure against adaptive adversaries

Hey crypto SE, i'm having a bit of trouble with this question. Can anyone help me to understand how to go about solving this problem? Any help is appreciated :) Show G is insecure against adaptive ...
5
votes
2answers
671 views

Show that G is not a PRF

$\DeclareMathOperator{concat}{\|}$ I'm trying to do the following assignment: Let $F : \{0,1\}^k \times \{0,1\}^n \to \{0,1\}^n$ be a PRF. Define function family $G : \{0,1\}^k \times \{0,1\}^{n-...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
15
votes
3answers
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 ...
2
votes
2answers
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 ...
3
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
2answers
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 ...
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
586 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
708 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
511 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
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,...
4
votes
2answers
604 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 ...