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
0
votes
1answer
25 views

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

I understood what 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 ...
1
vote
1answer
61 views

Do 'nonsequential' PRNGs exist?

It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'. How about a PRNG which allows me to retrieve ...
4
votes
0answers
50 views

Sponge with PRF instead of PRP

In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that ...
0
votes
0answers
33 views

Is changing-key $F_1$ a secure PRF?

Let $F(k,x):\{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}^n$ be a secure PRF. Prove or disprove whether $F_1(k,x)=F(F(k,0^n),x)$ is a secure PRF. My guess would be that it is PRF, and the part of ...
2
votes
0answers
56 views

Is there a cyclic RNG without an explicit form for $i$'th element which is guaranteed to have a sum of zero (subset of elements, $\mod P$ possible)

Let $X$ be a sequence element list of (pseudo) random values generated by a RNG and $x_i \in X$ a member of it. The period length is $k = |X|$ and it is a cyclic generator. For $i>k$ the value $x_i ...
0
votes
1answer
59 views

Random oracle : Replay

What I understand about the random oracle game: The adversary can query the oracle polynomial many times with the same (secret but unknown) key. From the output returned by the oracle, the ...
4
votes
1answer
194 views

Any speed up methods for finding the index of a random value produced by the Inversive congruential generator?

The Inversive congruential generator produces random values with: $$x_{n+1} = a\cdot x_{n}^{-1} + b \mod P$$ (special case if $x_n=0$ -> $x_{n+1}=b$) starting with an initial value $x_0$ With well ...
2
votes
1answer
72 views

Wrong Proof of Secure PRF

Disclaimer, this is not homework; I found the question statement here: Security of this PRF To restate the question: Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as $F'(k,x\...
4
votes
1answer
122 views

Necessary conditions for construction of $n$ to $p(n)$ pseudorandom generators from $n$ to $n+1$ generators?

Given a polynomial time deterministic algorithm $G_1:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$, consider the function $G:\{0,1\}^n \rightarrow \{0,1\}^{p(n)}$ constructed as follows: Let $s \in \{0,1\}^n$ ...
1
vote
2answers
122 views

What is the difference between pseudorandom permutation/pseudorandom function/block cipher?

What is the difference between; pseudorandom permutation pseudorandom function block cipher? Very confused with the 3 terms and I am not good at advanced math. Can someone explain in plain word?
5
votes
1answer
86 views

Can Trivium be used as a PRF?

The Trivium encryption algorithm has two inputs, key and IV, both of which are 80 bits long. Let's call it Trivium(key, IV) → keystream. My question is whether doing Trivium(key, input) and taking the ...
0
votes
1answer
106 views

Is F_k_1(x) \xor F_k_2(x) a pseudorandom function?

I'm trying to determine if $F_{k_1, k_2}(x) = F_{k_1}(x) \oplus F_{k_2}(x)$ ($k_1 \neq k_2$ because that would be lame) is a pseudorandom function. My hunch is that it is. My reduction proof proceeds ...
0
votes
1answer
63 views

Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0

I have 4 functions to analyze. I need to determine if they are or are not pseudorandom and give a proof/counterexample. I'm having trouble just determining if they are - let alone proving or giving ...
2
votes
1answer
102 views

Post-Quantum security of Pseudo-Random Functions

I am wondering what is the exact post-quantum security of a PRF. I know that for most symmetric mechanisms, it is assumed it is sufficient to double the key size, but I am looking for a more precise ...
0
votes
1answer
107 views

Pseudo Random Generator (PRG) not deterministic

Usually a Pseudo Random Generator is supposed to be IND-CPA secure. But apparently, it is not in some cases such as the following: A PseudoRandom Generator $G$ has expansion factor $n + 2$. Encrypt ...
1
vote
1answer
91 views

What is the most secure/reliable CSPRNG currently available? [closed]

In terms of period length, uniformity/distribution, what is the most secure/reliable CSPRNG currently available?
0
votes
0answers
32 views

Help, Feedback and Solutions to a problem on a PoC CSPRNG

Background I do not recommend trying to roll your own crypto. This is just a for-fun PoC, which won't be used in any public or private scenario. I am creating a PoC nearly-true random number ...
31
votes
6answers
4k views

What is the practical impact of using System.Random which is not cryptographically random?

I recently noticed a .NET software using PBKDF to derive an encryption key from a password string. This password string was ...
4
votes
1answer
93 views

Fundamental difference between the constant, key, nonce, and counter bits in Salsa20/ChaCha20 or AES-Encrypt?

The Salsa20 core function takes a 128-bit constant, 256-bit key, 64-bit counter, and 64-bit nonce and produces a 512-bit value. Or more generically, it is a mapping from 512-bit values to 512-bit ...
0
votes
1answer
87 views

Security of this PRF [closed]

Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as $F'(k,x||x') = F(k, 0||x)\oplus F(k, 1||x')$ with $x$ and $x'$ of $\lambda-1$ bits. Is $F'$ a secure PRF?
0
votes
1answer
39 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$ ...
4
votes
1answer
179 views

Is $f(K, f(K, x))$ a pseudorandom function?

Given a PRF $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}^n$, is $f(K, f(K, x))$ a PRF, too? My hunch is to construct a PRP similar to Feistel ciphers but with the property $f(K, f(K, x)) = ...
1
vote
0answers
70 views

Dependence of a Pseudorandom Function's Security on its Input/Output Spaces

Let $n$ be a security parameter and $F:\{0,1\}^{\ell_{key}(n)} \times \{0,1\}^{\ell_{in}(n)} \rightarrow \{0,1\}^{\ell_{out}(n)}$ be a keyed function which forms a family of Pseudorandom Functions (...
4
votes
1answer
94 views

A hash-based pseudorandom function

Let $H()$ be a cryptographic hash function. Question: Can we consider $c= H(r||i)$ as a pseudorandom value, where $i$ is a public value, $1\leq i\leq n$, and $r$ is a large uniformly random value/...
0
votes
1answer
82 views

Can you defeat AES-CTR's birthday boundary with a 2nd AES?

This follows on from How do I produce a stream of secure random numbers from AES-Counter mode? Consider then the generator:- $$ \operatorname{AES_{k1}}(n) \oplus \operatorname{AES_{k2}}(n) $$ ...
3
votes
1answer
135 views

PRP vs PRF for the F-function of a Feistel network

A Feistel network is generally defined with a PRF for its F-function, but PRPs have been used as well. What are the theoretical cryptographic implications of using a PRP instead of a PRF? Does it ...
1
vote
1answer
44 views

PRP, PRF change at next selection?

This is probably a silly question, and similar question was asked before; but I can not figure out what actually is PRP/PRF. For example, it is commented that: A Pseudo Random Function is a ...
6
votes
2answers
259 views

Do you really need a KDF when you have a PRF?

My understanding is that a KDF is like a PRF, except that it has a preliminary step that "extract" entropy. It is thus needed when the entropy is non-uniform (for example the output of ECDH is modulo ...
2
votes
1answer
72 views

How does changing input size affect The Goldreich-Goldwasser-Micali Construction?

If we want to construct a PRF that is length preserving, it is easy to show with hybrid proof that the resulting construction is a PRF. But what happens when we have longer input. Supose that the ...
1
vote
0answers
80 views

Construction PRF from PRG

As discussed here, a classic and secure construction of PRF from PRG is: $F_k(x_1x_2\cdots x_n) = G_{x_n}(\cdots(G_{x_2}(G_{x_1}(k)))\cdots)$ where $G$ is a secure pseudorandom generator. I was ...
3
votes
2answers
100 views

Does a regularly reseeded PRNG provide backtracking resistance?

I'm currently discussing a security topic with some of my classmates. A cryptographic PRNG typically provides backtracking resistance if an adversary that compromises the internal PRNG state cannot ...
-3
votes
1answer
102 views

A well known hash function?

Name a well-known and standardized function $F : \{0,1\}^{256} × \{0,1\}^{128} → \{0,1\}^{128}$ that is believed to be a pseudorandom permutation. I was thinking SHA256, but I am not sure. Can ...
0
votes
0answers
25 views

Tool to find non-linearity, resiliency and algebraic degree of a boolean function?

Is there any program or software to find out cryptographic properties like non-linearity, algebraic degree, balancedness and resiliency of a large boolean function?
2
votes
1answer
119 views

Constructions of PRF (Pseudo Random Function)

I was taught only GGM based PRF construction in class. It's very inefficient. I am just curious about various PRF constructions from standard assumptions. Please provide a few PRF constructions from ...
0
votes
2answers
138 views

Which functions can be used as Pseudo Random functions? Can block Ciphers be used for this purpose with our own encryption function?

Since the cloud security algorithm I am trying to implement says that for a PRF, any secure encryption algorithm or a keyed hash function can be used. The security parameter I have chosen is 15 bits ...
1
vote
2answers
153 views

Statistical Tests for Pseudorandom Functions

Say I have an implementation of a potential Pseudo-Random function and I want to test whether my implementation does at least not contain any obvious flaws. As far as I understand, in other ...
1
vote
0answers
33 views

How to prove security of scheme constructed by Hash then PRP

Suppose there is a scheme where a message is first hashed and then sent to a PRP. If the hash is done using an $\epsilon$-bounded universal hash function and the PRP $K\times \{0,1\}^n\rightarrow\{0,1\...
1
vote
0answers
95 views

Patarin’s H-Coefficient Technique

I have come across many paper that applies Patarin’s H-Coefficient Technique in various cryptographic securities (KPA, CPA, CCA,...). I am asking kindly if someone could explain it simple with ...
0
votes
1answer
144 views

The role of IV when AES is used as $PRF$

We want to use AES as a pseudorandom function. Given a random master key, we want to derive a set of pseudorandom values/keys, e.g say $n$ keys. Then from each of those derived keys, we want to derive ...
2
votes
1answer
90 views

Formal definition PRNG

I tried to look for a book that presents cryptographic concepts(specially PRNG) in a formal way but what I find is an intuitive approach. So my question is what is the formal definition of Psuedo-...
3
votes
3answers
623 views

Truncating the output of AES-128

I'd like to use the output of a pseudorandom function (PRF) as a one time pad. I want to use AES-128 (as it's commonly used as a PRF). As we know AES-128 output 128 bits. Question: Would be secure ...
1
vote
1answer
62 views

Give a distinguisher to differentiate between PRP and RPO

I have understood the proof that shows that a PRP is a PRF except for negligible probability $\frac{q(n)^2}{2^{-l(n)}}$. My computations suggest me that the same argument, perhaps with minor ...
2
votes
1answer
59 views

Amplifying PRF Advantage

I am trying to solve this question and I have no idea how to find the value for $q$. I know that I am supposed to find the probability of $q>3q/512$ in terms of the equation $q$, but not sure how? ...
0
votes
0answers
74 views

Computing a probability

Let $(w_1,\cdots,w_l) \in (\{0,1\}^\lambda)^l$, and $r_1,\cdots,r_l $ are chosed as uniformly random from $Z^*_q$ such that $r_1+\cdots+r_l=0$ and $q$ is a large prime number. Also, Let $F$is a ...
1
vote
1answer
106 views

Is this MAC correct and secure?

Let $m \in \{0, 1\}^{2n} = m_1 || m_2$. Let's also assume that $F_k$ is a PRF and $G$ is a PRG defined as $G: \{0, 1\}^n \rightarrow \{0, 1\}^n$. Now, Let's define the $MAC$ scheme as follows: $$MAC(...
1
vote
0answers
106 views

Indistinguishable encryptions and CPA-secure example

Let $ F $ be a PRF and $ G$ be a PRG with expansion factor $n \to n +1 $ For the following encryption scheme, decide whether it has indistinguishable encryptions and whether it is CPA-secure. ...
1
vote
0answers
142 views

$G_f(x) = x \|f(x)$ is not a PRG with $\operatorname{DPT}$-computable function $f$

Let $f:\{0,1\}^* \rightarrow \{0,1\}$ be any $\operatorname{DPT}$-computable function. Show that $G_f(x) = x \|f(x)$ is not a PRG. Can anyone help me on understand how to prove this?
2
votes
1answer
196 views

Cryptography Pseudo Random Generator example question - proof

For ii) G2 was proven to be a PRG, and it seems the solution for G5 uses G2. Can someone try and explain to me the solution that I was given? I specially do not understand how to calculate the given ...
3
votes
1answer
158 views

Can we use a PRF as a PRP?

Leaving aside the problem of how to compute the inverse of a PRF F, may we use it also as a PRP? The reciprocal of this statement is true, see for instance Katz and Lindell, Proposition 3.27, when ...
0
votes
0answers
108 views

Building a CPA-secure sCTR from a PRF

Let $F$ be a PRF with $n = l_{in}(n) = l_{out}(n)$. For any PPT-encoding $[\;\;]:\mathbb{Z}_{2^n} \to \{0,1\}^n$ and any polynomial $l(n)$, $G_l(x) = F_k([1])\|\ldots\|F_k([l(n)])$ is a PRG ...