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.
439
questions
0
votes
0
answers
44
views
Is this a secure PRF?
Let $F:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ be a secure PRF. Consider a construction of a new PRF $F':\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ as follows $F'_{k}(x)=F_{F_{k}(x)}(x)$. Is $F'$ secure?
...
0
votes
1
answer
49
views
How to understand the counterexample constructed in the PRP/PRF switching lemma towards the standard proof?
I'm reading a paper Code-Based Game-Playing Proofs and the Security of Triple Encryption , which indicates an error on the standard proof of the PRP/PRF switching lemma using the conditional ...
- 3
2
votes
1
answer
78
views
Verifiable OPRF from general ZKP?
We know how to build a signature scheme from ZKP and hashing: For signing, the signer creates a ZK-PoK $Sig$ that it knows $k$ such that $\text{H}(k) = \text{id}$, and includes the message $m$ in the ...
- 687
1
vote
1
answer
74
views
How to proof that G is a PRG? [closed]
I followed a lesson this year about Introduction to Cryptography and Anonymous Communication and I am going to retake the exam of this lesson.
I was doing exercises to practice but we don't have the ...
- 11
3
votes
1
answer
200
views
Why does using keyed-$PRF$-derived inputs in a (non-committing) $\texttt{nc-AEAD}$ not provide commitment?
A definition for committing security in authenticated encryption can be described in relation to a security parameter $\lambda_{com}$, where the per-guess probability of finding distinct input tuples
$...
- 1,116
0
votes
0
answers
19
views
Universal circuit with PRF: how does a encoded PRF looks like?
I would like to ask or find materials on what an encoded string of PRF that can be fed into a universal circuit looks like.
To illustrate, I would like to have an encoding of $f_{k}()$, denoted as $...
- 361
2
votes
0
answers
72
views
What is exactly Randstorm vulnerability?
I've read the article from Unciphered about it, multiple times, and still fail to understand it
It basically says that wallets generated by BitcoinJs front end library from 2011 to 2015 are vulnerable ...
- 49
0
votes
0
answers
76
views
prove there exists a non-adaptive PRF that is not an (adaptive) PRF
A function family is a non-adaptive PRF, if it is a PRF s,but
its security should only holds against non-adaptive distinguishers
(non-adaptive distinguishers make all there queries at
once)prf
- 33
2
votes
1
answer
72
views
PRF with a one truly random evaluation
A pseudorandom function $f_k: \{0,1\}^n \rightarrow \{0,1\}^m$ has the property that for any probabilistic polynomial time adversary $\mathcal{A}$,
$$|Pr_{k}[\mathcal{A}^{f_k(\cdot)}(1^{\lambda}) = 1] ...
- 1,094
1
vote
0
answers
32
views
Adaptive and Non Adaptive PRF
Is it possible to construct a PRF that is secure under non-adaptive queries but not secure under adaptive queries?
- 11
0
votes
0
answers
63
views
Is it possible to prove this function is computationally intistinguishable from PRF？
Background
I have constructed a function $F':X × K → Y$, which has a characteristic that the quantity of $x\in X$ mapping to a single $y\in Y$ follows a binomial distribution $B(\frac{1}{2}, 2\frac{|X|...
0
votes
1
answer
55
views
Can f(S) also be replaced by PRP(S) in a Sponge consruction?
I have difficulties understanding the PRP in the absorb phase of a sponge construction: a block is XORed to the r part of the state memory,and then the entire state sent through a blockcipher-like ...
0
votes
3
answers
90
views
Is it possible to construct a (pseudo-)continuous PRF or MAC?
Is it possible to construct an efficient-to-compute function $F: X \rightarrow Y$ such that
Given samples $(x_1, F(x_1))...(x_n, F(x_n))$, any efficient adversary ($F$ itself is kept secret) can't ...
- 41
0
votes
0
answers
79
views
Possible MAC design
The problem
Let the following be a family of PRF functions with key length $2\lambda$
$$\mathbb{F} = \{F_k:\{0,1\}^n\rightarrow\{0,1\}^n\}_{k\in\{0,1\}^{2\lambda}}$$
Assuming one way functions exists, ...
- 1
1
vote
1
answer
151
views
My new PRNG (PaulssonSponge) with dieharder tests
I run an open source project implementing some RipeMD and SHA hashes, one day I got nerdy and threw together my own Sponge function. I have now tested it with the dieharder 3.31.1 test suite. Is it ...
0
votes
1
answer
59
views
Is a PRF pairwise independently and uniformly distributed
The notation of a strongly universal function was introduced by Wegman and Carter here and it states, that such a function has to be pairwise independently and uniformly distributed. I would like to ...
- 2,357
2
votes
0
answers
43
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
42
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
128
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
186
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
10k
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
114
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
149
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
151
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 ...
- 19
0
votes
1
answer
108
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
115
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 ...
- 1,116
1
vote
1
answer
84
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
79
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
1
vote
1
answer
180
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
59
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
72
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
51
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
183
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 ...
- 144k
0
votes
1
answer
190
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
81
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:
...
- 393
2
votes
1
answer
89
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 ...
- 393
5
votes
0
answers
104
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, ...,...
- 123
2
votes
1
answer
170
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
302
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
76
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
99
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
75
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
258
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
282
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
160
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?
5
votes
0
answers
296
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|$...
- 76
3
votes
0
answers
221
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 ...
- 31
1
vote
1
answer
107
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 ...
- 467
1
vote
1
answer
202
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 ...
- 387
1
vote
1
answer
76
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 ...
- 31