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.
441 questions
0
votes
0
answers
48
views
LSFR polynomial next term example
I’m struggling with the mathematical representation of an LFSR as polynomials, and I’d like to understand where I go wrong.
In my example, I use an LFSR with a 5-bit shift to the left and feedback on ...
2
votes
0
answers
45
views
How to bound the advantage of the following pair of games?
I'm reading a paper Code-Based Game-Playing Proofs and the Security of Triple Encryption, and I encounter a question in section 4.3, which designs the following games:
Lets just focus on the medium ...
- 43
0
votes
0
answers
57
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
56
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 ...
- 43
2
votes
1
answer
90
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 ...
- 697
1
vote
1
answer
123
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
217
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,122
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 $...
- 371
2
votes
0
answers
102
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
77
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
76
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,557
1
vote
0
answers
35
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
67
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
61
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
93
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
167
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
63
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,447
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
43
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
144
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
199
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
120
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
177
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
166
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
116
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
131
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,122
1
vote
1
answer
86
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
93
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
244
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
60
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, ...
- 134
1
vote
1
answer
81
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
52
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 ...
- 145k
0
votes
1
answer
205
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
82
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
97
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
111
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
181
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
334
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
82
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
116
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
78
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
294
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
307
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
214
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
320
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
239
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
118
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