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
46 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 ...
2
votes
0answers
51 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
64 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
103 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
118 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
80 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
87 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
55 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
101 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
95 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
83 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
31 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
89 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
76 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
161 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
68 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
90 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
81 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
126 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
43 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
253 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
63 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
76 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
97 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
100 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
106 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
135 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
149 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
32 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
93 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
139 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
616 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
59 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
101 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
98 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
139 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
184 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
151 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
106 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 ...
3
votes
0answers
248 views

Can we construct a PRF directly from a one way permutation function?

In Introduction to Modern Cryptography first a pseudo random generator (PRG) is constructed from a one way function (OWF). After that the PRG is used to to construct pseudorandom functions (PRF). Is ...
6
votes
2answers
381 views

Why does the CBC-MAC require PRFs?

I'm stuck on exercise 4.19 from Introduction to Modern Cryptography. Let $F$ be a keyed function that is a secure (deterministic) MAC for messages of length $n$. (Note that $F$ need not be a ...
2
votes
1answer
92 views

How can an unlimited adversary distinguish PRF's from Truly Random Functions (TRF)?

I'd like to know which strategy is adopted by an unlimited adversary to distinguish PRF's from Truly Random Functions
1
vote
1answer
144 views

Let F be a PRF, how to prove F3 is PRF?

Let $\operatorname{F}$ be a $\operatorname{PRF}$, how to prove $\operatorname{F^3_{k_1,k_2}}(x) = \operatorname{F_{k_1}}(x) \oplus \operatorname{F_{k_2}}(x) $ is aslo a $\operatorname{PRF}$?
1
vote
1answer
156 views

How to prove the PRF, $F(k,x) = (k \wedge x ) \oplus k$ is PRP?

I am trying to understand PRF's and PRP's. I have got a question where I have to decide whether $F(k,x) = (k \wedge x ) \oplus k$ (where $k$ and $x$ are simple $1$ bits (1 or 0)) is PRP or not. I am ...