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
1 vote
1 answer
95 views

Proving set of functions are not a PRF family

I am trying to prove that $\{F'_{k}\}$ is not a PRF family. I'm not really sure what $x$ is but I know conditionally choosing a specific PRF function when $x$ is odd or even is the flaw. I think PRF ...
Jaxon Steinhower's user avatar
0 votes
0 answers
74 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, ...
zBION1C's user avatar
1 vote
1 answer
117 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 ...
Kristoffer Paulsson's user avatar
0 votes
1 answer
49 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 ...
Titanlord's user avatar
  • 2,214
2 votes
0 answers
42 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$....
zzazzles's user avatar
  • 117
0 votes
1 answer
39 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 \...
Riemann's user avatar
  • 221
1 vote
2 answers
101 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 ...
Riemann's user avatar
  • 221
1 vote
2 answers
165 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 ...
Suraj's user avatar
  • 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 ...
Victor Espinoza's user avatar
1 vote
0 answers
100 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$, ...
zxcvber's user avatar
  • 111
1 vote
2 answers
122 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 ...
John_cena's user avatar
0 votes
0 answers
124 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 ...
HughJass24's user avatar
0 votes
1 answer
73 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)?...
Ilan's user avatar
  • 1
0 votes
1 answer
99 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 ...
aiootp's user avatar
  • 785
1 vote
1 answer
79 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 ...
bluebird's user avatar
0 votes
1 answer
62 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. ...
LePetit's user avatar
  • 15
0 votes
0 answers
37 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 ...
Weierstrass99's user avatar
1 vote
1 answer
128 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 ...
LePetit's user avatar
  • 15
1 vote
1 answer
56 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, ...
canary's user avatar
  • 124
1 vote
1 answer
66 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 ...
Mairon's user avatar
  • 161
2 votes
0 answers
49 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} ...
Tomer Gigi's user avatar
4 votes
1 answer
178 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 ...
fgrieu's user avatar
  • 140k
0 votes
1 answer
141 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 ...
darkflamehxy's user avatar
0 votes
1 answer
71 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: ...
alpominth's user avatar
  • 391
0 votes
0 answers
69 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 ...
艾霖轩's user avatar
2 votes
1 answer
81 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 ...
alpominth's user avatar
  • 391
4 votes
0 answers
91 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, ...,...
sbluff's user avatar
  • 113
2 votes
1 answer
131 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 ...
Randusr's user avatar
  • 45
1 vote
2 answers
206 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 ...
DurandA's user avatar
  • 453
1 vote
0 answers
69 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 \...
Giusy's user avatar
  • 33
1 vote
1 answer
81 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$ ...
tonythestark's user avatar
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 ...
user50394's user avatar
  • 295
2 votes
0 answers
229 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) ...
tonythestark's user avatar
2 votes
2 answers
249 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 ...
luishernandex's user avatar
0 votes
1 answer
114 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?
Caio Nogueira's user avatar
4 votes
0 answers
255 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|$...
seanL's user avatar
  • 66
2 votes
0 answers
183 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 ...
rahul yadav's user avatar
1 vote
1 answer
104 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 ...
Lev's user avatar
  • 433
1 vote
1 answer
165 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 ...
BlackHat18's user avatar
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 ...
ali alizade's user avatar
1 vote
0 answers
133 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: $$\...
Invited's user avatar
  • 33
8 votes
1 answer
686 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 ...
Maarten Bodewes's user avatar
  • 92.3k
1 vote
2 answers
333 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 ...
Jeff24's user avatar
  • 13
0 votes
1 answer
146 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 ...
Goodies's user avatar
  • 145
4 votes
1 answer
230 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$: ...
Mikero's user avatar
  • 12.5k
1 vote
1 answer
116 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 ...
Georgy Firsov's user avatar
5 votes
2 answers
712 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 ...
Marcellus's user avatar
  • 264
2 votes
1 answer
256 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 ...
Saar's user avatar
  • 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 ...
user102777's user avatar
7 votes
2 answers
615 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 ...
X. G.'s user avatar
  • 424

1
2 3 4 5
9