Does an information-theoretically secure hash function exist?

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)

• Depends on what you mean by ‘hash function’. For example, the first message authentication code in history, built out of what would later be called universal hashing, provides the optimal possible ‘information-theoretic’ bound on forgery probability. But it's not a collision-resistant hash function like SHA-256, a concept which doesn't even have a mathematical formalization that could conceivably have a notion of ‘information-theoretic security’. – Squeamish Ossifrage Oct 29 '19 at 5:06
• So would Poly1305 be an information-theoretically secure "hash function", while SHA-256 is a computationally-secure function but with collision resistant? – 09182736471890 Oct 29 '19 at 5:13
• I wouldn't say that, no, and I definitely wouldn't draw specifically that contrast between different types of security for the two qualitatively different goals of bounded difference probability (Poly1305) and collision resistance (SHA-256). Poly1305 and SHA-256 are entirely different kinds of thing which both happen to fit under the wide umbrella of the vague term ‘hash function’, meaning a function that kinda scrambles its input in some way. The FNV-1 hash is also called a ‘hash function’ but it doesn't aspire to any security. – Squeamish Ossifrage Oct 29 '19 at 14:17

1 Answer

The Gilbert-MacWilliams-Sloane MAC referred to by @SqueamishOssifrage in the comments is information theoretically secure "for single use", at the cost of having hashes that have length $$2\ell$$ for fixed length messages of length $$\ell.$$

Poly1305 is not information theoretically secure.

It is much more flexible, can take essentially arbitrary length inputs, and has a low probability $$p$$ of being spoofed which depends on four factors, $$\delta,C,D,L$$ and which is essentially $$\delta$$ plus a tiny correction factor, so $$p\leq \delta+f(L,D)2^{-106}.$$ See the original paper by Bernstein (Springer LNCS vol. 3557, also available at his site https://cr.yp.to/mac/poly1305-20050329.pdf) :

• One can have up to $$C\leq 2^{64}$$ authenticated messages
• Messages are of maximum length $$L.$$
• One can attempt up to $$D$$ forgeries
• $$\delta$$ is the probability of distinguishing AES output from a random permutation

To start with, we don't know what $$\delta$$ is. AES could be replaced if it was found to be weak, but the big issue is that, there is no way of handling arbitrary input length messages with a probability distribution, which would enable one to define information theoretic security, which depends on entropy, a well defined functional of a probability distribution.

• ‘Poly1305 is not information theoretically secure.’ What is your definition of ‘information theoretically secure’ which Poly1305 fails? You proceeded to quote a paper about the composition Poly1305-AES, which uses Poly1305 as a component. – Squeamish Ossifrage Oct 29 '19 at 14:05
• ‘the big issue is that, there is no way of handling arbitrary input length messages with a probability distribution’—This is…not an issue in any of the security theorems related to Poly1305, not even Poly1305-AES or crypto_secretbox_xsalsa20poly1305. The theorems involving Poly1305 are all quantified for all messages, for uniform random keys. – Squeamish Ossifrage Oct 29 '19 at 14:07
• For a little more on the history of universal hashing one-time authenticators, their easily proven security properties, and how they fit in with other components, see crypto.stackexchange.com/a/67639. Poly1305-AES is an example of a Carter–Wegman–Shoup MAC based on Poly1305 and AES, but essentially nobody uses it today—ChaCha/Poly1305 as used in TLS 1.3 and crypto_secretbox_xsalsa20poly1305 both just derive a one-time Poly1305 authenticator key per message pseudorandomly, with no AES involved. – Squeamish Ossifrage Oct 29 '19 at 14:12
• It's unclear to me why you brought up Poly1305-AES at all. The OP wasn't asking for a MAC that's not ‘information-theoretically secure’, and wasn't asking about Poly1305, but now you seem to have misled the OP into the conclusion that there is not an ‘information-theoretic security’ theorem for Poly1305 when exactly the opposite is true. – Squeamish Ossifrage Oct 29 '19 at 17:40
• By the way, there are universal hashing MACs—not GMS, not Poly1305—that have $h$-bit outputs for $\ell$-bit messages with the smallest possible bound $1/2^h$ on forgery probability and keys much smaller than $2\ell$ bits. E.g., if a message $m$ is broken into an $n$-element sequence of $h$-bit chunks $(m_1, m_2, \dotsc, m_n)$ interpreted in $\operatorname{GF}(2^h)$, and a key is a tuple $(r_1, r_2, \dotsc, r_n, s)$ of $n + 1$ elements of $\operatorname{GF}(2^h)$, then the MAC $m_1 r_1+m_2 r_2+\dotsb+m_n r_n+s$ attains the bound $1/2^h$ on forgery probability with $\ell+h<2\ell$ key bits. – Squeamish Ossifrage Oct 29 '19 at 18:15