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
1answer
26 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
74 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
173 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
43 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
34 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
50 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
100 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
152 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
67 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
38 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
79 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
88 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
50 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
59 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
42 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
72 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
239 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....
1
vote
2answers
289 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
60 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
96 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
42 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
69 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
30 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
70 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
487 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
936 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
60 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
49 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
37 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
768 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
107 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
93 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
157 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
44 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
0answers
39 views

Feistel Network - pseudorandomness

I want to ask about proving not pseudorandomness of Feistel network $(i=1)$ by formal definition: $$ |P[D^{F_k(\cdot)}(1^n) = 1] - P[D^{f(\cdot)}(1^n) = 1]| \le negl(n)$$ I understand how this works ...
0
votes
1answer
61 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 ...
0
votes
0answers
44 views

Any formal proof or reference that pseudorandom permutation can be used as pseudorandom function

Assume that a DRBG passes all statistical tests. We use that DRBG to shuffle(Fisher-Yates) an array that contains $\{0,1,\ldots,2^n-1\}$. Now get a pseudorandom permutation $\{0,1\}^n\rightarrow \{0,1\...
1
vote
0answers
52 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
156 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
127 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
417 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
77 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?
0
votes
1answer
82 views

How can we implement a PRF with 1bit input space and 1024bit output space using AES securely?

I'm considering an implementation of PRF $F:\{0,1\} \times \mathcal{K} \rightarrow \{0,1\}^{1024}$ with a key space $\mathcal{K}$ in particular with AES-128 in counter mode. Since output space is ...
0
votes
1answer
78 views

Why is it not ideal to rely on interactive assumption to build PRF?

I understood the meaning of interactive assumption from What is the notion of an interactive assumption? . However, I am not sure why there exists a research field of constructing PRF from standard ...
1
vote
1answer
80 views

Do 'nonsequential' PRNGs exist?

It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'. How about a PRNG which allows me to retrieve ...
6
votes
1answer
164 views

Sponge with PRF instead of PRP

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that ...

1
2 3 4 5
7