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
0
votes
0answers
22 views

Random Oracle Model for an ideal block cipher vs Ideal Cipher Model

Some security proof involving an ideal function use the Random Oracle Model (ROM). They posit a thing that given integer $b$ and bistring $M$, returns what it previously returned for that input $(b,M)$...
4
votes
1answer
88 views

Are these functions secure PRFs?

Let $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ be a secure PRF (i.e. a PRF where the key space, input space, and output space are all $\{0,1\}^n$) and say $n=128$. My assignment is to show ...
8
votes
4answers
143 views
4
votes
1answer
217 views

What is the NIST recommended maximum bias for random number generators?

What is the maximum bias recommended by NIST for random number generators? This answer says that it is $2^{-64}$. Is it same for all applications? Does NIST have a publication with more information? I ...
5
votes
3answers
240 views

How to combine $n$ 'less random' bits to generate one 'more random' bit?

Suppose we have a random number generator badrand() generating 1 with probability $0.9$ and 0...
1
vote
3answers
306 views

Is collision resistant hash enough for one-block counter mode?

Let $H:\{0,1\}^*\rightarrow \{0,1\}^\ell$ be a collision resistant hash function (CRH), and let $\Pi = (\mathsf{enc,dec})$ be an encryption scheme with the following properties: $\Pi.\mathsf{enc}: \...
1
vote
1answer
47 views

PRF proof and length-preserving

I'm studying for my crypto exam and got stuck on following example: Is $F'_k(x) = F_k(0||x)||F_k(1||x)$ with $x \in \{0,1\}^{n-1}$ a PseudoRandom Function PRF, under the assumption, that $F_k$ is a ...
2
votes
1answer
116 views

Questions on PRF

Define three hash functions: $H_1: \{0, 1\}^* \rightarrow \mathbb{G}$ mapping $x$ to the group $\mathbb{G}$ of prime order $q$ $H_2: \mathbb{G} \rightarrow \{0, 1\}^\tau$ $H_3: \{0, 1\}^* \times \...
5
votes
3answers
180 views

A question regarding next-bit predictors

Consider a probability distribution $D$ over $n$ bit strings. Consider a next bit predictor $A$ as follows. \begin{equation} \underset{X \sim D}{\text{Pr}}[A(X_1X_2.....X_{k-1})=X_k] \geq \frac{1}{2} +...
1
vote
0answers
49 views

Trying to get idea of reduction [duplicate]

Suppose $F(k,x)$ be a secure PRF over $(\mathcal{K},\mathcal{X},\mathcal{Y})$ where $\mathcal{K} = \mathcal{X} = \mathcal{Y} = \{0,1\}^n$ $$F'(k, x) = F(F(k, 0^n), x) \; $$ Trying to get the intuition ...
0
votes
1answer
38 views

Small values with non-uniform distribution encoded as large values with uniform distribution

Given a non-uniformly distributed set of 32-bit values (for example), is there a way to reversibly encode each one as a 128-bit value (for example) where they'd be approximately uniformly distributed ...
0
votes
0answers
54 views

Insecure pseudo random functions

Let $F$ be a pseudo-random function. Show that the following constructions are insecure as message authentication codes (in each case $K \in \{0,1\}^n$ is the private key): $(a)$ To authenticate a ...
3
votes
1answer
168 views

Is HMAC-SHA256 a PRF?

In the abstract of The Exact PRF-Security of NMAC and HMAC, Gazi, Pietrzak, and Rybar state: NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto’96], who proved it to be a secure ...
3
votes
4answers
179 views

If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure?

I am new to crytography. Can anybody tell me what I might be missing here?
1
vote
0answers
69 views

How does a pseudorandom generator produce a similar distribution to $U_{n}$?

According to Wikipedia, a function ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$ with ${\displaystyle \ell < n}$ is a pseudorandom generator against $\mathcal {A}$ with bias $\epsilon$ if, ...
3
votes
1answer
43 views

Correctness of signle-point Oblivious PRF

In the paper Private Set Intersection in the Internet Setting From Lightweight Oblivious PRF, Chase et al. shows that a PSI scheme can be achieved by using an oblivious PRF (OPRF). They summarized a ...
0
votes
1answer
80 views

How to define secure pseudorandom functions?

I was told that for both cases the PRF is strong/secure, but I cant find a proper way to define this. Personally i think only (b) is secure because $x$ is not as strong as $O^n$ for $Fs$. But if that ...
1
vote
1answer
101 views

Questions about using PRF to construct PRG

Let F be a secure pseudorandom function with 128-bit key and 256-bit block length. Which are the following functions G are secure pseudorandom generators? (Select all that apply.) A. $G(x)=F_x(0...0)$...
1
vote
1answer
94 views

Deterministic Counter Mode with a PRF. What does evaluate at a point mean?

This is from Dan Boneh's Lecture where he talks about operating a PRF (AES, DES) in Deterministic Counter Mode. Dan Boneh says What we could do is we could use what's called a deterministic counter ...
1
vote
1answer
64 views

Unable to understand the concept of a 1-bit PRF

In his lecture on building Block Ciphers from PRGS, Dan Boneh says this Let’s start by finding out if we can build PRF from a PRG? Let $G:\ K \to K^2$ be a secure PRG Define 1-bit PRF $F:\ K \times \{...
1
vote
1answer
44 views

PRFs / hash functions with a parameter amount of 'hot' bits?

Does there exist a cryptographically secure hash function (or keyed PRF) that can take, as a parameter, the number of 'hot bits' in the output? And if so, what is the name? The goal here is to produce ...
0
votes
0answers
114 views

Is this scheme CPA or/and EAV secure

Let F be a pseudorandom function (length preserving). We have the following scheme: To encrypt $ m \in \{0,1\}^{2n}$, parse m as $m_1||m_2$ with $|m_1|=|m_2|$, then choose $r\leftarrow\{0,1\}^n$ and ...
5
votes
2answers
251 views

Can a PRF distiguisher invoke the function's algorithm?

The definition of a function $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $\mathcal F$, and there is no P.P.T....
2
votes
2answers
342 views

Which of those functions are PRFs?

Assume that $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$ is PRF. Examine if the following functions are PRFs: $$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), ...
0
votes
0answers
79 views

Concatenation of PRFs is PRG

$F$ be a PRF, is the following $G(x)=F_{0…0}(x)||F_{1…1}(x)$ a PRG?
1
vote
0answers
111 views

Why this isn't a secure PRF?

Given that F is a secure PRF in the example $$F'(k,x)= F(k,x)\mathbin\|F(k,F(k,x))$$ I'm not sure why this isn't a secure PRF? Under what condition $F(k, F(k,x))$ when concatenated to $F(k,x)$ the ...
0
votes
0answers
43 views

Are there any universal PRG’s or PRF’s?

Leonid Levin constructed a universal one-way function, i.e. a function $f$ such that if any one-way functions exist, then $f$ is a one-way function. My question is, what universal pseudorandom ...
0
votes
1answer
75 views

PRF and deterministic polytime function implie PRG

I'm struggling while trying to resolve this exercise. I already read all questions about PRG and PRF here and some proofs around the internet but none of them helped me. let's consider a function $C$ ...
1
vote
0answers
33 views

Is there a universal construction for Davies-Meyer hash functions?

My understanding is that there exists no strong pseudorandom permutation for which the Davies-Meyer construction is known to yield a provably collision-resistant hash function. Were I mean provably ...
0
votes
0answers
73 views

How does the entropy of $r$ influence the security of the one-time pad $F_k(r) \oplus m$?

In an one-time pad scheme, $s \oplus m$ is uniformly random for any $m \in \{ 0,1 \}^\ell$ if $s$ is uniform in $\{ 0,1 \}^\ell$. By the security of PRF, it seems to be secure to replace the truly ...
6
votes
1answer
494 views

Pseudorandom Generator

In a cryptographic application, two types of (pseudo)random bit streams are needed: a stream $A= a_{1}a_{2}a_{3}\ldots$ in which $\Pr[a_{i}=0]=\Pr[a_{i}=1]= 1/2\ \forall i$ and a stream $B= b_{1}b_{2}...
4
votes
4answers
971 views

Could a fixed RSA encryption be used instead of a salt to prevent rainbow table attacks?

It's common to use a salt before hashing a password in order to prevent an attack by rainbow tables. Would it also work to encrypt the password for instance by RSA encryption - by a permanent RSA ...
1
vote
1answer
72 views

Silent Oblivious Transfer Question

Recently, Boyle et. al. proposed silent OT extension. In the paper, silent OT, it seems that a GGM based PPRF used as building blocks. However, after reading the paper, I have two questions that are ...
0
votes
1answer
59 views

Why is SKEYSEED derived using the nonce as a key?

In IKEv2, SKEYSEED, which is used to as a seed for generating the rest of the keys, is generated as SKEYSEED = prf(Ni | Nr, g^ir)...
0
votes
1answer
40 views

Is it possible to derive a constant value from different signatures of a private key?

For example perhaps deriving the same PRF from RSA signatures on different messages from a (not known) private key? Struggling to find the proof of why not.
6
votes
2answers
1k views

What is the sponge construction in simple terms?

I suggested to my client to use SHA3 instead of SHA2. I know that SHA3 is based on Keccak algorithm which won the NIST's competition. I want to explain the structure of sponge functions in very simple ...
3
votes
1answer
83 views

Good key update algorithms for key evolving schemes

In schemes like SAKE(Symmetric-key Authenticated Key Exchange) , the master keys (used to authenticate parties and generate session keys) are evolving, ie undergo transition $K=update(K)$. What is a ...
10
votes
2answers
3k views

Is 512 bits a more secure hashing than 256 bits?

I know that 512 bit hashing is more secure, but I don't really know why. I hope someone can help me to better understand it in more detail.
8
votes
2answers
2k views

(updated) Utilizing a non-computable function to create a one-way function

Why can't uncomputable functions be adapted to serve as theoretically perfect one-way functions? This has been bugging me for years, and I've never been able to track down an explanation of why it ...
0
votes
1answer
109 views

Is there a function similar to a hash function, but it's reversible?

I am currently making a Python game where the user's high score gets encrypted and stored in a log (a text file). The reason for this encryption is because I don't want the user to be able to enter ...
3
votes
1answer
98 views

Randomness extractors from Bourgain’s breakthrough- applications?

Some exciting progress to pure mathematics is due to Bourgain Springer - Multilinear Exponential Sums in Prime Fields Under Optimal Entropy Condition on the Sources with applications to randomness ...
2
votes
3answers
171 views

How to derive a passphrase from a hash?

I'd like to generate a passphrase derived from a hash fingerprint. The passphrase consists of short and human-pronounceable words from a phonetically-distinct wordlist. The derivation is a one-way ...
1
vote
0answers
45 views

Can Trivium ciphertext be decrypted by an adversary if the key is known, but the IV is not?

Suppose that the adversary is able to recover the key of Trivium cipher. But the associated IV is unknown to him. Will he be able to decrypt the ciphertexts without any complexity?
0
votes
1answer
64 views

Probability for success of exhaustive search on PRF keys

I saw this example for exhaustive search to break the security of a PRF $F_k:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ where the key space is of size $|\mathcal{K}|=2^n$. The claim is that there is ...
1
vote
1answer
49 views

Can any part of AES encrypted blocks be used as PRFed value?

Suppose we need a PRF whose output space is 255bit. Then, what I can do with AES with 128-bit security is producing 2 AES blocks that are of 256-bit. Then, I will remove the most significant bit of ...
1
vote
0answers
55 views

Implementing MAC with PRF family $f$, why do we need $f_k$ to be invertible?

As per the title, say we have $\text{MAC}(k,m) = (m,f_k(m))$ where $f$ is a PRF family and every function $f_k$ is PRP, where $f_k(m)$ and $f_k^{-1}(m)$ are efficiently computable. I proved that this ...
3
votes
1answer
168 views

Insecure MAC built on pseudorandom function

this is a question about Katz-Lindell book, introduction to modern cryptography, 2nd edition, exercise 4.7, part c. For (a) and (b) it is clear that the Macs are insecure, but for (c) I am struggling ...
2
votes
2answers
144 views

Mathematical definition of deterministic and non-deterministic random bit generators

Can anyone give the mathematical definition of deterministic and non-deterministic random bit generator? Providing a reference will also be very helpful.
3
votes
1answer
469 views

Is this a PRF? Fk(x) = G(k⊕x) where G is a PRG

This is not homework, but a random thought. Let $G(x)$ be a PRG. We define the following function: $$F_k(x) = G(k\oplus x)$$ My intuition is that it shouldn't be a PRF but I couldn't come with an ...
0
votes
1answer
83 views

Which is faster, PRF based on AES-CTR and PRF based on BLAKE{2,3}?

Recently Blake3 has been announced, which can be used as PRF. I'm wondering which PRF is faster, namely PRF based on Blake3 or the one based on AES-CTR?

1
2 3 4 5
7