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.
408
questions
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 ...
- 21
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 ...
- 11
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$ ...
- 173
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) ...
- 173
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 ...
- 337
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 ...
- 21
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 ...
- 208
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 ...
- 23
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 ...
- 484
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, ...
- 514
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 ...
- 627
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\}^...
- 11
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 ...
- 309
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 ...
- 337
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 ...
- 867
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 ...
- 31
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 ...
- 21
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 ...
- 21
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?
- 337
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