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
1 answer
28 views

Is it secure to do subfield VOLE over a Ring $\mathbb{Z}_{2^k}$?

In the paper "Efficient Pseudorandom Correlation Generators: Silent OT Extension and More (https://doi.org/10.1007/978-3-030-26954-8)" Boyle et. al. proposed subfield vole. For standard VOLE ...
0 votes
1 answer
49 views

Is there a way to make a pseudorandom function to generate decimal numbers in a specified range and not only producing big ones?

When I try to generate decimal numbers in the range 0-18446744073709551616 using a hash function I always get big numbers like this: ...
  • 115
0 votes
0 answers
21 views

Could Diffie-Hellman ciphertext be used as OPRF(Oblivious pseudorandom functions) input?

In my recent PSI project, I wanted to use Diffie-Hellman encryption to obtain ciphertext as OPRF input, but I could not find similar work related to it. In my opinion, Diffie-Hellman ciphertext length ...
2 votes
1 answer
62 views

When the input size in a PRF is larger than the output and many inputs will generate the same output, but why AES-256 in CTR mode is considered safe?

I know that if the input size in a pseurandom-function is larger than its output, many different inputs will generate the same output by the Pigeonhole principle (I also read an article related to ...
  • 115
2 votes
0 answers
45 views

Hybrid Argument proof

I am trying to understand what the Hybrid Argument is in cryptography and why is it useful. By the definition of the Hybrid Argument we know that to prove that if two distributions $D = D_1, D_2, ...,...
  • 93
2 votes
1 answer
88 views

Any simple, cryptographically secure AES-based DRNG?

I am looking for a DRNG/DRBG (cryptographically secure) algorithm/function (which I can program into js). I am looking to use a DRNG as a seed generator for generating multiple, identical AES keys on ...
  • 45
1 vote
2 answers
56 views

Derive related universally unique identifier (UUID) from a main UUID

Given a list of base entities (B) with each of them having a universally unique identifier (UUID) of 128 bits. I want to attach to them a list of ≤ 7 related entities (TE, UE, ..., ZE) with each of ...
  • 433
1 vote
0 answers
34 views

Construction of a SKE scheme based on a PRF family and on a MAC with UF-CMA security. Is the scheme secure?

Consider the following construction of a SKE scheme $\Pi^*=(Enc^*,Dec^*)$ based on a PRF family $F=\{F_k:\{0,1\}^n\rightarrow \{0,1\}^n\}_{k\in\{0,1\}^\lambda}$ and on a MAC $ Tag:\{0,1\}^\lambda \...
  • 33
1 vote
1 answer
62 views

Computing the advantage when checking PRF

I am reading a pdf on pseudorandom function I found here https://www.cs.utexas.edu/~dwu4/courses/sp21/static/reductions.pdf My problem/struggle is with the computation of the distinguisher's $B$ ...
3 votes
1 answer
66 views

Distribution distinguishability as a decision problem

In the definition of a pseudorandom function, we consider two distributions $D_0$ and $D_1$ over functions, where $D_0$ is the distribution of a random function and $D_1$ is the distribution of a ...
  • 295
2 votes
0 answers
117 views

Check if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom

Let F be a pseudorandom function. Check if if $F_1(k,x) = F(k,x) \oplus x$ is pseudorandom( $\oplus$ is bitwise XOR). I found this question in a book. I am not sure how to proceed : $F_1(k,x) = F(k,x) ...
2 votes
2 answers
169 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
58 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
149 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
69 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
94 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 ...
  • 373
1 vote
1 answer
84 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
55 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
64 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
129 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: $$\...
  • 33
8 votes
1 answer
600 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 ...
  • 89.3k
1 vote
2 answers
169 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
81 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
127 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.2k
1 vote
1 answer
100 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
535 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
129 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
72 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
576 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
114 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
75 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
127 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
151 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
81 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
82 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
62 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
233 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
277 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
88 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
47 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
310 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 ...
  • 125
2 votes
1 answer
122 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
116 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
140 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
152 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
224 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
61 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
129 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
65 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
349 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

1
2 3 4 5
9