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.

431 questions
Filter by
Sorted by
Tagged with
2k views

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 ...
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 ...
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})$ ...
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
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 ...
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, ...
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
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 ...
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 ...
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$....
2k views

1 vote
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 ...
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 ...
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)?...
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
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
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 ...
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 ...
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
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 ...
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
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, ...
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
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 ...
76 views

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. ...
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
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
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 ...
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 ...
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} ...
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 ...
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?
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: ...
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 ...
97 views

1 vote
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$ ...
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 ...
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 ...