Does secure hashing imply secure symmetric encryption?

Question

I was wondering if the mere existence of a (by some definition) secure cryptographic hash function immediately implies an equally secure symmetric encryption scheme.

By my understanding, one could to the following given such a function:

Encryption: Using a shared secret key, we calculate the hash of the key concatenated with the first character of the text, the key concatenated with the first two characters of the text, etc. (every prefix), giving the same number of hashes as characters in the input. This would inflate the size somewhat, but only by a small constant factor.

Decryption: Knowing the key, we can calculate the hash of our key concatenated with every character from the alphabet, and once we find the one that matches the first hash, we can repeat the process with the next hash, until the entire text is found. This would require some more hash calculations than encryption, but only a constant factor, the size of the alphabet (this could be reduced by a bit for bit scheme instead of a character by character scheme).

As far as I know, this incremental series of slightly different inputs to a hash function should not cause the resulting hashes to be predictable, and neither should it leak information about the key.

One weakness I can see is that messages that start out the same and are using the same key will have the beginning of the hash sequence equal up to the point of divergence, but this can easily be mitigated by prefixing the message with a unique ID of some sort, perhaps just a hash of the message itself.

---

The above is the reasoning that made me think that "hash function" ⇒ "symmetric encryption".

Is there some fundamental principle or scheme that proves/disproves that this is the case?

Answer 1

The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.

A family of collision resistant compressing functions is also a family of one-way functions. By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG). The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.

Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)\oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.

Answer 2

Theoretically-speaking, yes: (collision-resistant) hash functions imply* one-way functions (OWF), and therefore they also can be used to build symmetric primitives using the chain of reductions from OWF to PRGs (pseudo-random generators) to PRFs (pseudo-random functions) and finally to PRPs (pseudo-random permutations) or block ciphers (cf. this answer).

*Refer, for example, to this paper for a proof.