Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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
2 answers
2k views

Prove that the following private-key encryption scheme is not CPA-secure

Consider the following private-key encryption scheme: The shared key is $k \in \{0,1\}^n$. To encrypt the message $m \in \{0,1\}^n$, choose random $r \in \{0,1\}^n$ and output $(r, F_r(k)\oplus \...
3 votes
1 answer
217 views

Why is it not ideal to rely on interactive assumption to build PRF?

I understood the meaning of interactive assumption from What is the notion of an interactive assumption? . However, I am not sure why there exists a research field of constructing PRF from standard ...
3 votes
1 answer
286 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 ...
8 votes
5 answers
2k views

Is a PRF always collision resistant?

Context: We usually assume that the hash functions we use in practice are both: collision resistant and pseudorandom. I wonder what's the relation between those properties. Question: Is a pseudo ...
1 vote
0 answers
30 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?
0 votes
0 answers
62 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
50 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
87 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 ...
7 votes
2 answers
662 views

Does a hash function in chaining mode or in counter mode make a better pseudo-random number generator?

I have two pseudorandom generators: $f_1$ takes a random seed $l_0||r_0$ $\in \{0,1\}^{160}$ as input and outputs $r_1||r_2|| \dots ||r_k$, where $l_i||r_i = \operatorname{SHA-1}(l_{i-1}||r_{i-1})$ ...
11 votes
2 answers
5k views

What is the sponge construction in simple terms?

I suggested to my client to use SHA3 instead of SHA2. I know that SHA3 is based on Keccak algorithm which won the NIST's competition. I want to explain the structure of sponge functions in very simple ...
1 vote
1 answer
172 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 ...
0 votes
0 answers
77 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, ...
2 votes
1 answer
196 views

Correlation among pseudorandom sequences generated from correlated seeds

I want to see and mathematically verify how pseudonoise (PN) sequence generated by LFSR or maximum length codes would correlate (auto-correlation and cross correlation) for seeds of varying ...
1 vote
1 answer
131 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
55 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 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$....
7 votes
1 answer
2k views

Goldreich-Goldwasser-Micali Construction

The Goldreich-Goldwasser-Micali construction allows to build a (cryptographically secure) pseudo-random function from of a (cryptographically secure) pseudo-random generator. More formally, let $G: \...
4 votes
4 answers
4k views

Given PRNG $G(s)$, why is $G(s) || G(s+1)$ not a PRNG?

I have given a pseudorandom Generator $G(s)$, $|s|=n$ whose expansion $l(n)$ is $>2n$. I also know that $G^\prime(s) := G(s_1,\ldots,s_{\lfloor\frac{n}{2}\rfloor})$ is a pseudorandom generator. Now ...
1 vote
2 answers
114 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 ...
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 \...
1 vote
2 answers
180 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 ...
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 ...
0 votes
1 answer
87 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)?...
4 votes
3 answers
668 views

Can we convert a pseudorandom function (PRF) to an Oblivious PRF (OPRF) through an Oblivious Transfer (OT) protocol?

I'm a software engineer, so I generally think in building blocks. And I'm not so familiar with the Math notation in Crytography, so I'll stick with function calls and function blueprints (which I ...
1 vote
0 answers
110 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$, ...
1 vote
2 answers
141 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 ...
0 votes
0 answers
141 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
162 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 ...
1 vote
1 answer
2k views

Is this scheme CPA or/and EAV secure

Let $F$ be a pseudorandom function (length preserving). We have the following scheme: To encrypt $ m \in \{0,1\}^{2n}$, parse m as $m_1||m_2$ with $|m_1|=|m_2|$, then choose $r\leftarrow\{0,1\}^n$ and ...
0 votes
1 answer
59 views

Output a pad (un-keyed, variable length) from an input seed (fixed value for same seed)

I want a function $y = f(x, len)$: $x$ is the seed. $y$ is the output. $len \in \mathbb{Z^+}$ is the length (bytes) of $y$ Select a seed string $x$ to generate a string $y$. For each same pair of $x$ ...
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, ...
0 votes
1 answer
103 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 vote
1 answer
81 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 ...
0 votes
1 answer
76 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. ...
0 votes
0 answers
40 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
163 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 ...
1 vote
1 answer
67 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 ...
2 votes
0 answers
212 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 ...
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} ...
4 votes
1 answer
181 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 ...
3 votes
2 answers
293 views

LWE and pseudorandom functions

Consider the learning with errors problem. Assuming LWE (or a variant of LWE, like ring LWE) is hard for polynomial time algorithms, can we construct a family of pseudorandom functions from there?
0 votes
1 answer
78 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: ...
2 votes
1 answer
87 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 ...
4 votes
0 answers
97 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, ...,...
2 votes
1 answer
148 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 ...
1 vote
2 answers
263 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 ...
1 vote
0 answers
70 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 \...
1 vote
1 answer
93 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$ ...
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 ...
2 votes
2 answers
271 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 ...

1
2 3 4 5
9