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

304 questions
Filter by
Sorted by
Tagged with
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: ...
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 ...
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 ...
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....
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 ...
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 ...
202 views

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= ... 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 ... 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$... 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 $$\... 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 ... 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? 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 ... 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) ... 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-... 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 ... 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 ... 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=... 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. 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 ... 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)... 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 ... 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 ... 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 ... 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): ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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{... 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'$... 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? 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. ... 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 ... 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 ... 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 :) 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. 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})$,... 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 ... 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 ... 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}...
115 views

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