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.
425
questions
2
votes
0
answers
35
views
Secure mapping functions
I have two secret numbers $A$ and $B$. Both are uniformly-distributed 32-bit numbers.
I need a deterministic function $f(x)$ such that $f(A) = B$. $f(x)$ must not leak any information about $A$ or $B$....
- 117
0
votes
1
answer
36
views
Domain of index of PRF
On Wikipedia, they give the following definition of PRF:
A family of functions,
$f_s: \{0,1\}^{|x|} \rightarrow \{0,1\}^{\lambda(|x|)}$,
with $x\in \{0,1\}^*$ and
$\lambda:\mathbb N \rightarrow \...
- 221
1
vote
2
answers
94
views
Difference between PRF, Pseudorandom Function and Pseudorandom Function Family
According to Wikipedia, PRF is an abbreviation for Pseudorandom function family. But this answer says that PRF means Pseudorandom Function. Does that mean that a Pseudorandom Function is the same as a ...
- 221
1
vote
2
answers
145
views
Suppose $F_s$ is a PRF. Is $F'_s(x)=F_x(s)$ also a PRF?
Suppose $F_s$ be a family of keyed pseudorandom functions. Define $F'_s(x)=F_x(s)$. Is $F'_s$ a family of pseudorandom functions? It seems false but I am able to give a proof assuming $F$ is ...
- 11
14
votes
5
answers
9k
views
Does Grover's algorithm really threaten symmetric security proofs?
By Shannon's theorem of perfect security, if I give you a ciphertext 'LOUPL', you can do a brute-force attack and then you would find plaintexts like 'HELLO', 'APPLE', 'SPOON', but you can't ...
- 171
1
vote
0
answers
88
views
Showing that $F(k,x) \oplus F(k,x \oplus 1^n)$ is not a secure PRF
Let $X = \{0, 1\}^n$. Given a PRF $F : X \times X \rightarrow X$, define
$$H(k, x) = F(k,x) \oplus F(k,x \oplus 1^n).$$
I think this is insecure, since $H(k, x) = H(k, \bar{x})$ for all $x \in X$, ...
- 111
1
vote
2
answers
111
views
MAC from PRF secure under different restriction
Suppose, we have a secure PRF $F$. Then can there be a MAC Scheme $I=(Sign, Verify)$ using F such that $I$ is insecure, but I is secure under the restriction that all the queries for MAC challenges ...
- 31
0
votes
0
answers
109
views
How to "break" this PRF scheme?
I'm new to cryptography, and I'm working on exercises that involve "breaking" PRF schemes which involves writing a poly-time program that distinguishes between two particular programs, the ...
0
votes
1
answer
63
views
KangarooTwelve based Random-Access PRNG
Can the KangarooTwelve Keccak-p[1600,12] be used to create a CSPRNG in which there is random access to an element (or a small group of outputs) of the generated list (instead of sequential generation)?...
- 1
0
votes
1
answer
87
views
How much of SHA3's internal state can be reached?
After reading that about "37% of the 256-bit outputs" of SHA-256 are unreachable when fed only 256-bit inputs [1] I'm curious & confused. The formula from the proof here considers a ...
- 785
1
vote
1
answer
70
views
Tensor product of Pseudorandom States
I am reading the paper Pseudorandom Quantum States,where the following candidate was shown to be a Pseudorandom state, called the complex random phase state:
$\mathrm{PRF}_k:X → X$ be a keyed ...
- 61
0
votes
1
answer
55
views
Regarding: Pseudorandomness, Pseudorandomgenerators and Padding
Hey there guys and gals,
so I am right now studying topics regarding pseudorandomness.
I was wondering why, for example with CBC-MAC oder a regular CBC blockcipher, we use padding instead of a PRG. ...
- 15
0
votes
0
answers
34
views
PRFs with long outputs and short keys
Assume I have a PRF $F$, with polynomial key length $s_{F}(n)\geq n$, and output length $l(n)$.
I need to construct a PRF $F'$, with key length $s_{F'}(n)=n$ and output length $l(n)$.
I thought about ...
1
vote
1
answer
106
views
Regarding Pseudo Random Functions
I am right now studying Pseudo Random Functions. I have a couple of constructions made of a safe PRF F:{0,1}^l x {0,1}^l -> {0,1}^l.
I am unsure of wether these are safe ( in terms pseudorandomness ...
- 15
1
vote
1
answer
53
views
Can we extend the definition of PRF over uncountable infinite sets?
This question may be of no practical interest. But as a meaningful or meaningless question, can we extend the domains of the keyspace, ...
- 124
1
vote
1
answer
65
views
How to write monomials in $GF(2^n)$ as a system of equations in $GF(2)$
Let $F = GF(2^n)$ and $P(x) = x^e, P : F \rightarrow F$ be a monomial of degree $e$. How to write each bit of the output of $P$ as a function of input bits? In other words, how to write it as a system ...
- 161
2
votes
0
answers
46
views
PRF with one value changed
I'm having problem proving the following, I intuitively think this is correct but can't formally prove why.
given a PRF $F_k(x)$
proove that the following is also a PRF
$$
F'_k(x) = \begin{cases}
...
- 21
4
votes
1
answer
175
views
PRF collision search for input smaller than output
Assume a given pseudo-random function $H:\{0,1\}^a\mapsto\{0,1\}^b$ with $b\in[104,256]$ and $b/2<a<b$. We want to exhibit a collision if there is one, which has probability $>63\%$.
We are ...
- 138k
0
votes
1
answer
120
views
Is it secure to do subfield vector oblivious linear evaluation (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 ...
0
votes
1
answer
67
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:
...
- 391
0
votes
0
answers
57
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
80
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 ...
- 391
3
votes
0
answers
81
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, ...,...
- 103
2
votes
1
answer
124
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
178
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 ...
- 453
1
vote
0
answers
62
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
76
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
72
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
188
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
238
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
86
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
240
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
2
votes
0
answers
170
views
Exchanging key and input in GGM tree?
I am currently working through the exercises in A Graduate Course in Applied Cryptography by Dan Boneh. I am stuck on exercise 4.16 (page 188 in this PDF)
In the GGM tree construction for constructing ...
- 21
1
vote
1
answer
98
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 ...
- 413
1
vote
1
answer
135
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 ...
- 357
1
vote
1
answer
75
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
132
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
662
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 ...
- 91.9k
1
vote
2
answers
274
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
130
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
201
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$:
...
- 12k
1
vote
1
answer
113
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 ...
- 223
5
votes
2
answers
682
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 ...
- 264
2
votes
1
answer
236
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
81
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 ...
- 33
7
votes
2
answers
605
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
145
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
88
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, ...
- 526
0
votes
1
answer
136
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 ...
- 637
1
vote
0
answers
162
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