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
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$....
zzazzles's user avatar
  • 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 \...
Riemann's user avatar
  • 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 ...
Riemann's user avatar
  • 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 ...
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
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$, ...
zxcvber's user avatar
  • 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 ...
John_cena's user avatar
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 ...
HughJass24's user avatar
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)?...
Ilan's user avatar
  • 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 ...
aiootp's user avatar
  • 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 ...
bluebird's user avatar
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. ...
LePetit's user avatar
  • 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 ...
Weierstrass99's user avatar
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 ...
LePetit's user avatar
  • 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, ...
canary's user avatar
  • 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 ...
Mairon's user avatar
  • 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} ...
Tomer Gigi's user avatar
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 ...
fgrieu's user avatar
  • 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 ...
darkflamehxy's user avatar
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: ...
alpominth's user avatar
  • 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 ...
艾霖轩's user avatar
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 ...
alpominth's user avatar
  • 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, ...,...
sbluff's user avatar
  • 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 ...
Randusr's user avatar
  • 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 ...
DurandA's user avatar
  • 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 \...
Giusy's user avatar
  • 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$ ...
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
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) ...
tonythestark's user avatar
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 ...
luishernandex's user avatar
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?
Caio Nogueira's user avatar
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|$...
seanL's user avatar
  • 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 ...
rahul yadav's user avatar
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 ...
Lev's user avatar
  • 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 ...
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
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: $$\...
Invited's user avatar
  • 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 ...
Maarten Bodewes's user avatar
  • 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 ...
Jeff24's user avatar
  • 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 ...
Goodies's user avatar
  • 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$: ...
Mikero's user avatar
  • 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 ...
Georgy Firsov's user avatar
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 ...
Marcellus's user avatar
  • 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 ...
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
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 ...
X. G.'s user avatar
  • 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 ...
Finlay Weber's user avatar
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, ...
user918212's user avatar
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 ...
Andrew Tomazos's user avatar
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\}^...
zhuo chen's user avatar

1
2 3 4 5
9