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

learn more… | top users | synonyms (1)

3
votes
1answer
100 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: ...
1
vote
1answer
54 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
77 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
64 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
47 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
94 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
72 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
532 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
166 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
97 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
99 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?
3
votes
1answer
559 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
88 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
254 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
132 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
81 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
84 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
82 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
104 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
57 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
160 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
75 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
213 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 ...
10
votes
2answers
4k 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
178 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
384 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
112 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
162 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
87 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
234 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
185 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
105 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
96 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
640 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
147 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
111 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
113 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
60 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
120 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
813 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).
2
votes
2answers
120 views

What is the impact of different modes on pseudo randomness of AES?

AES in CBC-MAC mode is proven to be good PRF . But is there any study done on other modes ? how good is ECB mode as PRF ?
2
votes
1answer
251 views

Why is this MAC based on secure PRF with ordering and randomization insecure?

Is this MAC secure: To authenticate a message $m=m_1||\ldots||m_l$ where $m_i \in \{0,1\}^{n/2}$, choose $r \leftarrow \{0,1\}^n$ at random, compute $$t:=F_k(r)\oplus F_k(\langle 1\rangle || ...
2
votes
1answer
282 views

Why is it important to generate a pseudorandom permutation from a pseudorandom function?

Most of the papers on block cipher constructions, especially the ones which discuss constructing block ciphers of arbitrary lengths or small domains, the techniques are designed based on building a ...
2
votes
2answers
842 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 ...
1
vote
2answers
243 views

Generate random number which should depend on key

i want to generate random number for example from [1..100]. The algorithm which would generates random number should work similarly like a "Linear congruential generator", like this: $X_{n+1}≡(aX_n ...
3
votes
1answer
197 views

Salsa20 in Davies-Meyer mode with a fixed key (message): is it one-way?

Say I have a function that calculates a pseudo random permutation and this function is easy to invert. For example $P(i) = AES_k(i)$ where $k$ is a publicly known key. So anyone can compute $P(i)$ ...
4
votes
2answers
688 views

Questions about Key Derivation Functions

My understanding is that a KDF is a function that takes a master secret and generates multiple keys. It is secure as long as the keys are "independent". If this is true, the following definition would ...
2
votes
1answer
147 views

The Goldreich-Goldwasser-Micali Construction with bad PRGS

I understand that if we have a secure PRG then the Goldreich-Goldwasser-Micali construction gives us a secure PRF. However, what I've not been able to find much material on is how will the GGM ...
5
votes
1answer
105 views

Is there any existing analysis for this construction to turn a tweakable blockcipher into a PRF?

I'm basically looking at this construction to turn a tweakable blockcipher $E_c(x)$ taking a key $k$, nonce $n$, counter $c$ (forming tweak $t = c||n$) and an input $x$ into a PRF on an ...