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
0answers
166 views

Define a DEC algorithm for a problem

Given $F$ , a PRF family and $F_{n,k}$ a permutation over the set $\{0,1\}^n$. In addition, each permutation (as usual for PRF) and their inverse (not usual) has an efficient calculation. Define: ...
1
vote
1answer
155 views

Security of OFB mode if PRP is used instead of PRF

In the cryptography lecture at my university, we had the theorem that (randomized) OFB mode is IND-CPA secure if the used pseudorandom function (PRF) is IND-PRF secure. Afterwards, we investigated ...
2
votes
0answers
65 views

Is there any OPRF (oblibivious pseudo random random functions) between one receiver (1 input) and n senders (n inputs)? any references to read?

I am looking for some references for multi-party / distributed Oblivious pseudorandom Functions. I found two party OPRF protocols between a sender $S$ and a receiver $R$ for securely computing a ...
4
votes
1answer
168 views

Luby-Rackoff theorem for Generalized Feistel

I was reading about Luby-Rackoff theorem from various sources: [1], [2], [3], which says you need at least 3 rounds of a $2$-branch Feistel network to get a PRP if the underlying $f$ function is a PRF....
4
votes
3answers
705 views

Is a PRF always collision resistant?

Context: We usually assume that the hash functions we use in practice are both: collision resistant and pseudorandom. I wonder what's the relation between those properties. Question: Is a pseudo ...
6
votes
1answer
356 views

Homomorphic Evaluation of Pseudo Random Function

I'm looking for a special Pseudo Random Function (PRF) $F_k()$ which follows the below. For fully homomorphic encryption (FHE), $\mathit{FHE}(F_k(x)) = F_k(\mathit{FHE}(x))$. Or is there any ...
1
vote
0answers
202 views

Pseudo-random function where the output is inverted using XOR

I'm looking to know whether or not this PRF is secure : $$F'(k, x) = F(k, x) ⊕ 1^n$$ knowing that $F$ is already a secure PRF for $$\{0, 1\}^n × \{0, 1\}^n → \{0, 1\}^n$$ with, for example, $n= ...
1
vote
0answers
72 views

Does a distinguisher for an PRF based on a hash make the hash function insecure?

I recently found a distinguisher for the PRF $f(s, i) = H(s || i)$ where $s$ is the seed and $i$ is a counter and $H$ is a cryptographic hash function, which is able to distinguish $f(s, i)$ from true ...
3
votes
1answer
671 views

Existence of PRF $\implies$ existence of PRG

Let $F:\{0,1\}^n\times \{0,1\}^m \to \{0,1\}^l$ be a PRF. I want to show that $G(-)=F(-,x_0)$ is a PRG for every $x_0\in \{0,1\}^m$. Proof attempt: Let $D$ be an efficient distinguisher against $G$...
-2
votes
2answers
170 views

Is this scheme multi-message secure? [closed]

Let $G$ be a pseudorandom generator. Is the scheme with encryption $$\text{Enc}_k(m) = s \| \left( m\oplus G(k) \oplus s \right),\quad s\in\{0,1\}^n \text{ uniformly sampled},$$ and decryption $$\...
2
votes
0answers
768 views

Showing the concatenation of pseudorandom functions is a pseudorandom function [closed]

The definition of a pseudorandom function is: Let $F:\{0,1\}^*\times \{0,1\}^* \to \{0,1\}^*$ be an efficient, length-preserving, keyed function. $F$ is a pseudorandom function if for all ...
-3
votes
1answer
4k views

How to calculate entropy of a random number?

I am having a set of random numbers and I want to calculate entropy of them. I searched many entropy calculation formula, but I didn't get it. Can you elaborate a little bit?
4
votes
4answers
1k views

The difference between MACs vs. HMACs vs. PRFs

I have some confusion regarding the difference between MACs and HMACs and PRFs and when to use which term. If the function is computed using a hash and secret key like the following, is this a HMAC ...
8
votes
2answers
728 views

Why is this function pseudo random (PRF)?

First, I want to clarify this is not homework. I encountered this question (here How can I prove that a function F isn't a pseudo random function?) while studying for a test coming soon. $F'_k(x) ...
3
votes
1answer
172 views

Security proof for CBC as a prefix-free PRF

I am currently trying to fully understand Dan Boneh's/ Victor Shoup's proof in their excellent crypto book draft, that the raw CBC construction is a secure pseudo random function family for prefix-...
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
155 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
295 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
386 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
282 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
332 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
1k 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
289 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
700 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
621 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
422 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
93 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
195 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
222 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
713 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
632 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
340 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
108 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
564 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
171 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
605 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
570 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
229 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
107 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
98 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
729 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
411 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
926 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
66 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
115 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
308 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
749 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 2 3 4 5 7