A pseudo-random function is an efficiently-computable function which emulates a random oracle.

learn more… | top users | synonyms (1)

2
votes
2answers
1k views

Estimating bits of entropy

Best ways to estimate average bits of entropy in a byte stream. I know there are different statistical tests out there (NIST, Dieharder, etc), which all do different ways of analyzing entropy. What ...
0
votes
1answer
46 views

Cryptanalysis of Marvin32

So I am curious about the security analysis of Marvin32, the randomized hash algorithm used in .NET (to prevent hash-table DoS). I found the source code here: ...
2
votes
1answer
56 views

Is it OK to substitute a PRF for a random oracle?

Random oracles don't exist, but aren't PRFs essentially indistinguishable from them? So why can't we substitute pseudorandom functions wherever we use random oracles? And if we can do this, why is ...
0
votes
1answer
69 views

What is the difference between H(M) and H3(M, s, IDA)? [closed]

What is the difference between H(M) and H3(M, s, IDA)? I am aware of Hash function with a Message and a Key, but there are three parameters in: H3(M, s, IDA). Here M is the message, s is the key, ...
0
votes
1answer
123 views

Permuted vectors

Consider we have two vectors $v_1, v_2$ of size $n$, and each vector contains $n$ elements. We permute the vectors as: $\pi (k_1,v_1), \pi (k_2,v_2)$. Where $\pi (k_i,v)$ denotes a permutation of a ...
0
votes
1answer
31 views

Swap $x$ and $k$ in GGM construction

I'm studying the Goldreich-Goldwasser-Micali construction from pseudo-random generators to pseudo-random functions. In this specific construction, assume $G:\{0,1\}^n\rightarrow \{0,1\}^{2n}$ is a ...
3
votes
1answer
169 views

Proving the existence of a pseudorandom function

I've been reading the Introduction to Modern Cryptography book by Katz and Lindell as part of my own learning and have come across this exercise which I am not sure how to approach. The exercise is: ...
0
votes
1answer
50 views

Is $f\colon x\mapsto g(x+1)$ necessarily a pseudorandom function?

Let $l\in\mathbb N$ and suppose $$g\colon\;\{0,1\}^l\to\{0,1\}^l$$ is a pseudorandom function. Is $f$, defined as below, necessarily a pseudorandom function as well? $$f(x)=g((x+1)\bmod2^l)$$
2
votes
0answers
71 views

Pseudorandom Function Proof

Given a set of pseudorandom functions $F=\{f_s^i\}_i$ for each $s\leftarrow\{0,1\}^n$ generated at random; moreover each $f_s^i$ uses a specific PRG $G^i:\{0,1\}^n\to\{0,1\}^{2n}$, where: ...
0
votes
0answers
62 views

Making PRFs out of PRGs

Is it possible that we take a $PRG$ $G(k)$ of stretch $n\cdot2^n$, and read its output as the table of a $PRF$ $F(K)$ with input and output size of $n$? Intuitively it sounds possible however I read ...
1
vote
1answer
78 views

Pseudorandom function library [closed]

I'm wondering if there is any library supporting pseudo-random function, so I can specify the key length and output domain. Is it correct that I need to use a block cipher for this purpose? Any ...
1
vote
1answer
104 views

PRF based on the GGM construction

What's the differences between the concepts “pseudorandom generator” and “pseudorandom number generator”? In fact, I want to implement a pseudorandom function based on GGM's construction at ...
0
votes
1answer
166 views

What is the difference between a hash function and a pseudorandom function? [duplicate]

Read the title. I've seen in RFCs that some MAC functions are called "pseudorandom functions". What are those? How are they different than hash functions? Why can't a hash function be used instead?
3
votes
0answers
56 views

Pollard's Rho - Restricting the random function to the exponents

Pollard's Rho is usually constructed using a function $f:G \rightarrow G$ which behaves 'random enough' in order to detect a collision with Floyd's cycle detection trick. It is easy enough to observe, ...
1
vote
4answers
127 views

Difference between Pseudorandom Function vs randomly chosen function

I am currently going through a course in cryptography. In this, I stumbled upon Pseudorandom Functions. I got a little idea of Pseudorandom Generators which map an input string (key) to an extended ...
0
votes
0answers
112 views

Implementing a pseudo random function in practice

Can anyone point me to a C++ crypto library with an implementation of a pseudo random function (PRF)? I don't have much background in crypto theory, but I am in the middle of a graduate course ...
7
votes
1answer
734 views

Security of KDF1 and KDF2 (hash based KDF's)

It's still common to come across implementations of KDF1 and KDF2. Basically these are KDF's that simply derive multiple keys from the key seed and a counter: $K_i = KDF(K_{master}, i) = H(K_{master} ...
2
votes
2answers
228 views

Skein or Keccak stream cipher construction

I am wondering if using Skein or the Keccak hash algorithm in this construction (as a stream cipher) is secure: $H$ = Keccak or Skein hash with a 256 bit output $K$ = The main 256 bit random key, ...
1
vote
1answer
127 views

INT_32_BE in PBKDF2

Trying to understand PBKDF2 in detail. It is clear that the password and the salt is given to the PRF (which is HMAC-SHA-1 in the specification). But what is the role of the INT_32_BE(i)? What does it ...
4
votes
1answer
128 views

CBC-MAC based on PRF

Why is the block cipher in the CBC-MAC taken to be a pseudo random permutation (PRP) and not a pseudo random function (PRF)? We don't need the bijective property of the PRP. So why go with it?
4
votes
1answer
786 views

Luby-Rackoff theorem confusion

The Luby-Rackoff theorem states that if a round function is a secure pseudorandom function (PRF) then 3 rounds are sufficient to make the block cipher a pseudorandom permutation (PRP). PRPs are ...
2
votes
1answer
111 views

CTR mode encryption using PRG

In CTR mode encryption, the encryption block is not required to be invertible. Thus, a PRF can be used instead of a PRP. However most of the implementations of CTR mode are based on AES which is a ...
2
votes
1answer
429 views

PRF and hash functions

Is there a difference between PRF and a hash function? For example: Creation of a secret key is using PRF and creating a secret key is using hash function.
0
votes
1answer
151 views

How to implement a Cryptographic Pseudo Random Function

I need three pseudo random functions which all take a seed S (t-bits long). The functions should map from $d$ bits to $d$ bits $d$ bits to $1$ bit $d$ bits to $t$ bits $d$ is $10$ bits $t$ is ...
4
votes
1answer
99 views

Turning PRPs in PRGs with a counter

I am following the Coursera Cryptography I course and I have the following question, I am a bit perplexed by the statement, in week 2 lecture "What are block cyphers?" that a counter-mode PRF is a ...
2
votes
1answer
103 views

Is a keyed PRF a MAC?

I remember I read that a MAC can be considered as a PRF. Can a variable-length input keyed-PRF be considered as a MAC?
2
votes
0answers
85 views

how to truncate a PRF on n bits to PRF on t bits where t < n? [closed]

Dan Boneh's courersa lecture on format preserving encryption at 5.50 mins , talks about truncating a PRF on $n$ bits to PRF on $t$ bits. The approach is by appending $(n-t)$ zeros to input $t$ bits ...
3
votes
1answer
113 views

Cryptographic pseudo-random generation of address subsets

Suppose I have devices which broadcast, on an insecure channel, 32-bit addresses. I want to make these devices untraceable - one way to do so is to allocate for each device a distinct subset of ...
1
vote
0answers
61 views

Special random distribution algorithm

I am implementing ring signatures as a part of an authorization system. Since the number of users could get high enough to make computation on end-user devices infeasible, I am thinking of ...
0
votes
1answer
168 views

Pseudo-random Number generation for Passwords

I am looking for a good pseudo-random number generation algorithm for passwords. My scenario is that I have to generate 5K pseudo-random bits from a user-supplied password (6 characters). What are ...
1
vote
1answer
79 views

Exchanging Keyspace and Message space in PRF

Suppose there is a secure PRF $F: K \times X \to Y$. Then is $F': X \times K \to Y$, defined by $F'(x,k):=F(k,x)$, a secure PRF? In my opinion it should be because exchanging the keyspace with ...
2
votes
2answers
236 views

PRP, PRF and modular arithmetic

Are there any arithmetic or mathematical functions that can be used as PRPs or PRFs ? Since, Conventional block ciphers like AES are that are proven to be good PRPs are not based on mathematics but ...
11
votes
2answers
5k views

What is difference between PRG, PRF, and PRP

Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then ...
1
vote
1answer
191 views

Traitor-tracing PRF

I'm looking for a pseudorandom function (PRF) with "traitor-tracing" properties. More specifically, I'd like there to be multiple equivalent keys, so I can give different parties different keys, but ...
2
votes
1answer
666 views

TLS Key Block calculation - What is a PRF?

In Section 6.3 of the RFC for TLS 1.2, it is written that the key_block is derived from the following formula: ...
2
votes
1answer
153 views

What is the difference between PRF and a Random Oracle?

What is the difference between Pseudo Random Functions and Random Oracles? Is the difference only about the domain of PRFs and Random Oracles, former having a fixed domain and latter can act on any ...
0
votes
1answer
202 views

HKDF vs TLS PRF. Which of the one is better? [closed]

Which of the one (HKDF or TLS1.1+ PRF) is more secure and why?
3
votes
0answers
97 views

What might be assumed about a PRF if the key has been chosen?

The defining feature of a PRF $f:\{0,1\}^k\times\{0,1\}^s\mapsto\{0,1\}^*$ is that, if the first parameter is selected at random, it should be indistinguishable from a function ...
2
votes
1answer
249 views

Cryptographically strong pseudo-random seq. generators

If a pseudo-random sequence generator is built so that it uses an n-bit seed and outputs a string that is of length x. Let's say one wants to generate a bit string of length y and uses the previous ...
2
votes
2answers
196 views

Pseudorandom functions

The usual case to distinguish a pseudorandom function from a random function is to assume that the adversary can choose the plaintext blocks. Is there another case (game) in which the adversary can ...
-1
votes
1answer
109 views

Why is it said that if we know few bits of pseudo random sequence we can predict the whole of it?

I am new to this cryptography and in the source from which i study it is said that if we know the first few bits of a pseudo random sequence we can predict the whole of it.How is it possible? The ...
1
vote
1answer
101 views

Prove that two MACs with incremendal PRF application are not secure

How do I prove the following MACs are insecure?                                                        1                                                                                   2
5
votes
4answers
678 views

Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)

I have a question about Pseudo Random Functions. Let $f:\{0,1\}^m \times \{0,1\}^n → \{0,1\}^n$ be a secure PRF. Define $F(k,x) = f(k,x) - f(k, x-1 \bmod 2^{n}) \bmod 2^{n}$. Is $F$ is a secure ...
4
votes
1answer
164 views

Private set intersection, using a semi-trusted server

Alice has a set $S$ of words. Bob has a set $T$ of words. They want to compute the intersection $S \cap T$ of their words, with the help of a semi-trusted third party Trent. Trent runs a central ...
0
votes
1answer
119 views

Prime factors of non-random keys

I have been working on a challenge i found on the internet. It is as follows: You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the ...
2
votes
1answer
120 views

Is this EAX extension weakening the (provable) security of EAX?

I would like to insert a key deriving function into EAX mode, in order to hamper brute-force attacks for a key-size restricted cipher (56 bits). The modification inserts an identical multi-block ...
2
votes
0answers
62 views

Protocol/algorithms based on a variable-length input PRF

Are the proofs based on a PRF assumption still valid when using a variable-length input PRF ? The answer might be obvious, but I have a doubt.
1
vote
1answer
129 views

Security based on PRF

I've seen that there is several kinds of PRF, and sometimes people speak about strong PRFs. When proofs of a protocol or algorithm are given based on the assumption of the use of a PRF, are they ...
1
vote
3answers
891 views

Hash function based on pseudorandom functions and security

Are there hash functions that make use of pseudorandom functions. Precisely, I'm looking for a specification of a hash function based on PRF (and based on the security of such a primitive).