Are pseudorandom generators, pseudorandom permutations and hash functions all keyless?

Question

In Katz's Introduction to Modern Cryptography,

Chapter 7 Practical Constructions of Symmetric-Key Primitives

In previous chapters we have demonstrated how secure encryption schemes and message authentication codes can be constructed from cryptographic primitives such as pseudorandom generators (aka stream ciphers), pseudo-random permutations (aka block ciphers), and hash functions.

I have trouble understanding the concepts in the book.

1. Does "pseudorandom permutations (aka block ciphers)" mean that pseudorandom generators and block ciphers are the same concept? Isn't it that a block cipher is a mapping: {key}x{plaintext}->{ciphertext}? Isn't it that a pseudorandom permutation is a random function: {plaintext}->{ciphertext}?

2. Does "pseudorandom generators (aka stream ciphers)" mean that pseudorandom generators and stream ciphers are the same concepts? Why?

3. Are pseudorandom generators, pseudorandom permutations, and hash functions all keyless?

4. Are one-way functions also keyless?

5. Are one-way functions and hash functions the same concept, or very closely related concepts?

Answer 1

Abbreviations;

• PseudoRandom Permutations : PRP
• PseudoRandom Functions : PRF
• PseudoRandom Generators :PRG
• One-Way Functions: OWF

Does "pseudorandom permutations (aka block ciphers)" mean that pseudorandom generators and block ciphers are the same concepts? Isn't it that a block cipher is a mapping: {key}x{plaintext}->{ciphertext}? Isn't it that a pseudorandom permutation is a random function: {plaintext}->{ciphertext}?

PRPs and block ciphers are synonymous. Both are defined as the keyed family of permutations ( where each permutation is selected with a key or more than one key). They are designed to have a small PRP advantage to the attacker with the same syntax security target.

Determining the exact advantage is hard like nobody showed that AES is a PRP or not in more than 20 years.

There is also ideal-block cipher ( like the random oracle) that is a model for the adversaries.

?Does "pseudorandom generators (aka stream ciphers)" mean that pseudorandom generators and stream ciphers are the same concepts? Why?

Stream ciphers (for a single fixed message number) and PRGs are more or less synonymous

PRG's

• have fixed-length output
• produce output in “one shot”

If we fix the output length of stream-cipher they are more or less the same thing. In general, stream ciphers

• can be viewed as producing an “infinite” stream of pseudorandom bits, on-demand
• more flexible, more efficient

Are pseudorandom generators, pseudorandom permutations, and hash functions all keyless?

PRG and PRP are keyed. The hash function is rather a wide subject. Hash functions constructed for collision resistance like SHA-2 are keyless. HMAC, as a method of construction PRFs ( also as a MAC from hash functions like HMAC-SHA-2), is sometimes called keyed hash function.

Are one-way functions also keyless?

OWFs are not keyed.

Are one-way functions and hash functions the same concept, or very closely related concepts?

Being OWF is required of collision resistance hash functions and OWF is not synonymous with hash functions.

Answer 2

I think with the "aka" they state the example they created with the given primitive. PRG are introduced first and then they make a stream cipher using a PRG. This does not mean every PRG is a stream cipher, it only shows a possible application. The same holds for PRP. Therefore you have to distinguish between the theoretical and strict definition and the practical contextual application.

PRF, PRP, OWF and Hash-functions can be described as keyless (for simplicity), but they can also have a key. I would say that this depends on the context and the author.

OWF are in general one of the most basic concepts in cryptography. Hash functions are pretty similar to OWF, but not every OWF is also a Hash function. For a cryptographically secure Hash function, there are more properties (e.g. collision resistance), that must not be fulfilled by a OWF.