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

Construct PRG from PRF with polynomial expansion factor

I want to prove that for every pseudorandom function $F: \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$ and for every polynomial $p$ such that $p(n) > 1$ for every $n$ it is possible to ...
0 votes
1 answer
34 views

Constructing a PRG from a pseudorandom function

I have recently understood how we can construct a pseudorandom function from a PRG. However, I would like to prove the reverse - how can I construct a PRG from a PRF?
4 votes
0 answers
81 views

XOR of a secure PRF is modified weakly secure PRF

While reading A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. There was the next exercise (Ex. 4.2 (b)), let $F$ be a secure PRF over $(K,X,Y)$ where $Y := \{0,1\}^n$ and $|X|$...
  • 66
0 votes
0 answers
42 views

Exchange key and input in GGM tree

In the GGM tree construction for constructing a PRF from a PRG, the secret key is used at the root of the tree and the input is used to trace a path through the tree. Consider a construction that does ...
1 vote
1 answer
93 views

"Near" Pseudorandom Function

I am searching literature on a more general notion of pseudorandom function where the range of the function is not the entire set of all binary strings of a given length, but rather a specified range ...
  • 178
1 vote
1 answer
60 views

Indistinguishability obfuscation and PRFs

Consider a family of pseudorandom functions $F$, each member $f_k$ of this family is indexed by a key $k$. It is true, due to a result by Barak et al, that black box obfuscation is not possible for a ...
0 votes
0 answers
50 views

How to share a function securely?

I was reading a paper on Function Secret Sharing, and in that the author made use of the idea of GGM-style tree to propose a scheme based on pseudorandom generator. Here I became interested in how to ...
  • 40
1 vote
1 answer
49 views

Can a cryptographic hash function that outputs a c-membered subset of the n-membered set?

Is it possible that there is a cryptographic hash function that outputs a c-membered subset of the n-membered set? In other words, can the set of the binary representation of c-membered subsets of the ...
1 vote
0 answers
121 views

Does this function yields to a PRF?

I have two PRGs: $$G: \{0,1\}^l \rightarrow \{0,1\}^{3l}$$ $$G': \{0,1\}^m \rightarrow \{0,1\}^n , n \gg m$$ I also have a PRF: $$F: \{0,1\}^{3l} \times\{0,1\}^m\rightarrow \{0,1\}^m $$ Is: $$\...
  • 23
8 votes
1 answer
576 views

Is constant-time compare really required for AEAD ciphers?

When verifying a (HMAC) authentication tag it is often indicated that a constant-time comparison is required for security. I can see how leaking information about a password hash can introduce a mild ...
  • 87.1k
1 vote
2 answers
136 views

Why is this PRF not secure? [closed]

So, I'm taking Cryptography I by Dan Boneh on Coursera and I was reviewing the definition of security for a PRF while solving exercises, and I stumbled upon this question from a homework Dan Boneh ...
  • 13
0 votes
1 answer
61 views

ChaCha Single-Use RNG with All Zero Plaintext + Nonce

I am creating an internal application that will be used to generate and manage self-signed certificates and certificate authorities. Its primary use will be for generating certificates used in SSL ...
  • 145
4 votes
1 answer
91 views

Constructing a PRF from PRG, with more parallelism

The famous result of Goldreich, Goldwasser, and Micali (GGM) constructs a PRF $F$ from a PRG $G$: ...
  • 11.1k
1 vote
1 answer
98 views

Derive independent values using block cipher

Suppose having an arbitrary $GF(2^n)$ element $x$. Its distribution is unknown. The task is to derive two $GF(2^n)$ elements $y$ and $z$, that have uniform distribution and are independent from each ...
5 votes
2 answers
467 views

Security reduction seems to wrongly show that a non-PRF is a PRF

This is a well-known exercise that has already even been posted here. I understand both arguments to prove and disprove that $F'$ and $\bar{F}$ are PRFs, as I explain below, however, it seems that the ...
  • 254
2 votes
1 answer
94 views

Show that function isn't a PRF

Let $F$ be a PRF such that $|F(k,x)|=2n$ show that $F_2$ isn't a PRF. Let's assume $F(k,x)=(y_1,...,y_{2n})$ then $F_2(k,x)=(y_1\land y_2,...,y_{2n-1}\land y_{2n})$. I want to prove $F_2$ isn't a PRF ...
  • 51
1 vote
0 answers
67 views

Is there any structure similar to GGM but more efficient?

Although Goldreich-Godlwasser-Micali (GGM) construction of a pseudo-random function (PRF) from a pseudo-random number generator (PRNG) is widely in many cryptographic applications, it needs to consume ...
7 votes
2 answers
545 views

Probability conventions in cryptography

I am working on Victor Shoup's tutorial on game-based security proof and want to figure out some notions from the perspective of probability theory. Consider the following PRF advantage defined on ...
  • 414
0 votes
2 answers
96 views

Are Block Ciphers Pseudorandom functions? [duplicate]

I am reading this page on wikipedia on Key derivation function here where it states: In cryptography, a key derivation function (KDF) is a cryptographic algorithm that derives one or more secret keys ...
0 votes
1 answer
68 views

Why is using a truly random function in a fixed length encryption scheme not efficient?

I am working through Katz and Lindell, and Theorem 3.26 in the book proves that a construction based on a PRF is CPA-secure. The thrust of the scheme is that if $F_k$ is a PRF, with $k, m, r \in \{0, ...
0 votes
1 answer
121 views

Is this pseudo random function any good and/or original? [closed]

I designed this pseudo-random function algorithm that takes a uint64 and returns a uint64. I'd like to know if it is any good ...
1 vote
0 answers
140 views

Is PRF Xored (or multiplied) with a random number still a secure PRF?

I've know that a PRF Xored with its key is not a secure PRF. Then I wonder that what if the Xored (or multiplied) item is another random number. The formal expression is as belows: Let $F_k(x):\{0,1\}^...
0 votes
1 answer
78 views

Computational indistinguishability of two LWE type samples

Consider the problem of distinguishing between polynomially many samples of either \begin{equation} (x, b, As + e) ~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) + e'\right). \end{equation} Here, $A$ ...
  • 103
0 votes
0 answers
76 views

Using PRF as a building block to build other primitives?

I am doing an independent research in cryptography. I have designed a post-quantum secure pseudo random function. Just constructing a PRF will not help me to publish in reputed journals. I was ...
0 votes
0 answers
55 views

Enumerating values from a linear congruential generator java Random()

During my research on a java application, I discovered that the nextInt(64) function of the java.Random() class is used to ...
2 votes
2 answers
177 views

Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

In Katz's Introduction to Modern Cryptography, Chapter 7 Practical Constructions of Symmetric-Key Primitives In previous chapters we have demonstrated how secure encryption schemes and message ...
  • 151
2 votes
1 answer
180 views

Is key rotation necessary when using HMAC as a pseudo random function?

I need to generate a deterministic identifier from some user data. One of the user data items is highly sensitive, but the other two are not. The identifier will be sent to an external party regularly,...
  • 135
1 vote
0 answers
79 views

Is F' = G(F)) a secure PRF given F and G are secure? [closed]

If we have a secure PRF 𝐹(𝑘, 𝑥) and a PRG G where 𝐺 : 𝒴 → 𝒴 × 𝒴 is a secure PRG. Is the PRF F'(k, x) = = 𝐺(𝐹(𝑘, 𝑥)) also secure?
  • 11
2 votes
0 answers
41 views

Is this property implied by a pseudorandom function?

Given a keyed pseudorandom function $f: S \times X \rightarrow Y$, where $S$ is the space of secret keys, $X$ is the input domain, and $Y$ is the range, the pseudorandom property says that given any ...
  • 163
4 votes
1 answer
227 views

The different bounds of PRP/PRF switching lemma

The PRP/PRF switching lemma is usually denoted as follows: I understand the proof of this version of the bound $\frac{q(q-1)}{2^{n+1}}$ and the game-playing technique behind it. However, I came ...
  • 115
2 votes
1 answer
117 views

Questions regarding the pseudorandom function construction of Banerjee, Peikert, and Rosen

I am trying to understand the following pseudorandom function constructed by Banerjee, Peikert, and Rosen in this paper, assuming the hardness of LWE. Consider the following LWE/LWR based pseudorandom ...
2 votes
1 answer
107 views

Converting a 32-bit ARX cipher to a 64-bit one, should the rounds be increased?

I read about using 64-bit words in PRF functions. I want to convert the 32-bit ARX cipher Chacha into a 64-bit version, with key/block size of 1024-bits (512*2=1024-bits) My question is: Should I add ...
3 votes
0 answers
98 views

Is it necessary for a round function $F$ in a Feistel cipher to be pseudorandom?

I stumbled across this question where the questioner asked for specific requirements for the round function $F$ in a Feistel network so that the construction is secure. The answer explained that a ...
2 votes
1 answer
114 views

Does Enc and Dec need to be a pseudo-random function for a scheme to be CPA secure?

I am currently going through past finals' questions as exercises for my exam and there are no solutions provided. The question I am currently doing is: Let ∏ = (Enc, Dec, Gen) be a CPA-secure ...
1 vote
0 answers
126 views

Building an Adversary for a PRF game

Here is the game: How can I make an $\mathcal{O}(k^2)$-time adversary making only one query to its Fn oracle and achieving advantage $= 1 - 1/(p-1)$ Here is my idea so far: query $2^{-1}$, which when ...
1 vote
0 answers
52 views

Showing that $F'(k, x) := F(F(k, 0^{n}), x)$ is a PRF [duplicate]

I wanted to do some practice on security reduction proofs, and I am stumped on this one from the Boneh-Shoup book. If $F(k, x)$ is a secure PRF, then show that $F'(k, x) := F(F(k, 0^{n}), x)$ is a ...
  • 43
2 votes
1 answer
107 views

LWE and pseudorandom functions

Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?
0 votes
1 answer
61 views

Where can I find good practice questions for proofs by reduction?

I already have the Katz-Lindell textbook, but I also want some additional practice problems for security reductions for stuff like PRFs, MACs, digital signatures, private and public key schemes, and ...
  • 43
4 votes
1 answer
345 views

Is there any result which states that if the output of these two functions is XOR'd, the XOR'd output is pseudorandom

Let $\mathbb{G}$ be a group of prime order $p$ with generator $g$. Suppose that I randomly pick $r_1,z_1 \leftarrow \mathbb{Z}_p$ and $r_2, z_2 \leftarrow \mathbb{Z}_p$ and $c \leftarrow \mathbb{G}$. ...
  • 163
2 votes
0 answers
268 views

Should I normalize adversary's advantage in IND-XXX Game?

The Cryptography made simple (page 207, under Fig 11.12)(Nigel Smart) say that adversary's advantage of IND-PASS Game is $Adv1 = 2\times|Pr[b=b']-\frac{1}{2}|$. The reason for multiplying by 2 is to ...
  • 121
2 votes
3 answers
196 views

How are the keys used in cryptography generated?

It seems there are keys everywhere in cryptography. From things like HMAC to encryption (both asymmetric and symmetric). The bit I do not totally understand now is how are cryptographic keys generated?...
1 vote
0 answers
121 views

What does a deterministic MAC actually mean? [closed]

Does a MAC that's deterministic mean it uses a PRF? Thanks for the help!
  • 43
0 votes
0 answers
54 views

How to show the PRF in 2. is secure? [duplicate]

Let F be a PRF defined over F:{0,1}n×{0,1}n→Y. 1.We say that F is XOR-malleable if F(k,x⊕c)=F(k,x)⊕c for all k,x,c∈{0,1}n. 2.We say that F is key XOR-malleable if F(k⊕c,x)=F(k,x)⊕c for all k,x,c∈{0,1}...
  • 11
1 vote
0 answers
102 views

How to build a lsfr based on sequence $s_i = s_{i-1} + s_{i-4}$? [closed]

How do I know where my XOR gates go? What does the F2 stand for here? Also the next task is to generate the sequence (with initialisation vector $s_0 = 1, s_1 = s_2 = s_3 = 0$) until it becomes ...
1 vote
0 answers
301 views

How to show the PRF in 4.8(b) is not secure? [closed]

Let F be a PRF defined over $F:\{0, 1\}^n \times \{0, 1\}^n \to Y$. We say that $F$ is XOR-malleable if $F(k, x \oplus c) = F(k, x) \oplus c$ for all $k, x, c \in \{0, 1\}^n$. We say that $F$ is key ...
  • 11
2 votes
0 answers
69 views

Types of PRFs and its applications

I was learning about iO from this paper when I noticed the different new types of PRFs. I wanted a clear understanding of the following. What are Puncturable PRF (PPRF)? Why is it defined in the way ...
1 vote
0 answers
129 views

Program to predict a 5-bit output from mersenne Twister random module from python

Is there a program to predict the mersenne twister random module in python for a 5-bit integer output, provided the consecutive 3994 outputs are available? The random module is not seeded so i guess, ...
0 votes
2 answers
259 views

What are the fastest algorithms that sample from the uniform distribution?

Lots of cryptography algorithms rely on pseudorandom number generators. Sometimes, given a plaintext, you need to generate a pseudorandom number from it. What are some fast algorithms that do so? I've ...
2 votes
3 answers
514 views

Efficient way to pick an array index by using a, say, 64 bit random number?

Say, I have uint64_t rand = <some random number>, and char array[20] = .... My goal is to pick an element in ...
  • 531
3 votes
1 answer
157 views

Is PRF XORed with its key still a PRF? (always)

$\forall k \in \{0,1\}^n,m \in \mathbb{M},F_k(m)$ is defined as follows: $F_k(m) = F'_k(m) \oplus k$. It is known that $F'_k$ is a PRF. Note: 𝕄 is the message space and it's assumed that the key $k$ ...

1
2 3 4 5
8