Rate-distorted cryptographic perfect hash functions
A theoretical analysis on space efficiency, time complexity, and entropy

Perfect hash functions have been extensively studied in the literature. Early foundational work by Dietzfelbinger et al. [4] established theoretical bounds for space-efficient hash tables with worst-case constant access time. Czech, Havas, and Majewski [3] introduced a family of perfect hashing methods that became widely influential.

More recent practical algorithms have focused on minimal perfect hash functions (MPHFs), which achieve a load factor of exactly 1. Botelho, Pagh, and Ziviani [2] presented simple and space-efficient constructions, while Belazzougui, Botelho, and Dietzfelbinger [1] developed the Compress, Hash, and Displace (CHD) algorithm, which achieves excellent space-time tradeoffs for large datasets.

Our work differs by focusing on the theoretical properties of cryptographic perfect hash functions with maximum entropy encodings, rather than minimal space or construction speed.

A set is an unordered collection of distinct elements. If we know the elements in a set, we may denote the set by these elements, e.g., $\{a,c,b\}$ denotes a set whose membes are exactly $a$, $b$, and $c$.

A finite set has a finite number of elements. For example, $\{1,3,5\}$ is a finite set with three elements. When sets $𝔸$ and $𝔹$ are isomorphic, denoted by $𝔸\cong 𝔹$, they can be put into a one-to-one correspondence (bijection), e.g., $\{b,a,c\}\cong \{1,2,3\}$. Since there exists at least one bijection between isomorphic sets, we can losslessly convert one to the other and thus, isomorphic sets are in some sense equivalent.

The cardinality of a finite set $𝔸$ is the number of elements in the set, denoted by $|A|$, e.g., $|\{1,3,5\}|=3$. A countably infinite set is isomorphic to the set of natural numbers $N=\{1,2,3,4,5,\mathrm{\dots }\}$.

Given two elements $a$ and $b$, an ordered pair of $a$ then $b$ is denoted by $(a,b)$, where $(a,b)=(c,d)$ if and only if $a=c$ and $b=d$. Ordered pairs are non-commutative and non-associative, i.e., $(a,b)\ne (b,a)$ if $a\ne b$ and $(a,(b,c))\ne (b,(a,c))$.

Related to the ordered pair is the Cartesian product.

By the non-commutative and non-associative property of ordered pairs, the Cartesian product is non-commutative and non-associative. However, they are isomorphic, i.e., $𝕏\times 𝕐\cong 𝕐\times 𝕏$.

A tuple is a generalization of order pairs which can consist of an arbitrary number of elements, e.g., $(x_1,x_2,\mathrm{\dots },x_n)$.

Note that $𝕏[1]\times 𝕏[2]\times 𝕏[3]\cong 𝕏[1]\times \left(𝕏[2]\times 𝕏[3]\right)\cong \left(𝕏[1]\times 𝕏[2]\right)\times 𝕏[3]$, thus we may implicitly convert between them without ambiguity.

If each set in the $n$-ary Cartesian product is the same, the power notation may be used, e.g., ${𝕏}^3\equiv 𝕏\times 𝕏\times 𝕏$. As special cases, the $0$-ary (nullary) Cartesian product is defined to be $\{\mathrm{\varnothing }\}$, and the $1$-ary (unary) Cartesian product is the identity, e.g., ${𝕏}^1=𝕏$.

The hash function is given by the following definition.

For a given bit string $x$ and hash function $\mathrm{hash}$, $y=\mathrm{hash}(x)$ is denoted the hash of $x$.

We are particularly interested in perfect hash functions as given by the following definition.

The load factor is given by the following definition.

Every hash function in $𝕏\mapsto 𝕐$ is a perfect hash function over some subset of $𝕏$, e.g., every hash function is trivially a perfect hash function of $\mathrm{\varnothing }$ and singleton sets.

Assuming $𝕏$ and $𝕐$ are finite, the set of hash functions of type $𝕏\mapsto 𝕐$, which may also be denoted by ${𝕐}^{𝕏}$, has a cardinality

The set of perfect hash functions over $𝔸\subseteq 𝕏$ is a subset of $𝕏\mapsto 𝕐$ with the predicate that no collisions may occur on any pair of elements in $𝔸$. The set of perfect hash functions over $𝔸$ has a cardinality

The bit set $\{0,1\}$ is denoted by $\{0,1\}$. The set of all bit strings of length $n$ is therefore ${\{0,1\}}^n$. The cardinality of ${\{0,1\}}^n$ is $2^n$. In the case of $\{0,1\}$, we denote ${\{0,1\}}^0$ by $ϵ$. The set of all bit strings of length $n$ or less is denoted by ${\{0,1\}}^{\le n}$ with a cardinality $2^{n+1}-1$, e.g., ${\{0,1\}}^{\le 2}=ϵ\cup \{0,1\}\cup {\{0,1\}}^2$. The countably infinite set of all bit strings, ${lim}_{n\to \mathrm{\infty }}{\{0,1\}}^{\le n}$, is denoted by ${\{0,1\}}^{\ast }$. A tuple $(x_1,x_2\mathrm{\dots })\in {\{0,1\}}^{\ast }$ is denoted a bit string, and we typically drop the angle brackets when specifying stings, e.g., $(x_1,x_2)\equiv x_1{x}_2$.

An important operation that is closed over the free semigroup of $\{0,1\}$ is concatentation, $\#:{\{0,1\}}^{\ast }\times {\{0,1\}}^{\ast }\mapsto {\{0,1\}}^{\ast }$, which is defined as $a_1\mathrm{\dots }{a}_n\#b_1\mathrm{\dots }{b}_m=a_1\mathrm{\dots }{a}_n{b}_1\mathrm{\dots }{b}_m$ with special cases $x\#ϵ=ϵ\#x=x$.

Most hash functions are of the type ${\{0,1\}}^{\ast }\mapsto {\{0,1\}}^n$ where $n$ is some finite natural number.

Another useful function is the binary padding function $\mathrm{pad}:{\{0,1\}}^{\ast }\times {\mathbb{Z}}_{\ge 0}\mapsto {\{0,1\}}^{\ast }$ is defined as $\mathrm{pad}(x,k)=x\#0^{k-\mathrm{BL}(x)}$ with the special case $\mathrm{pad}(x,0)=ϵ$.

The binary truncation function $\mathrm{trunc}:{\{0,1\}}^{\ast }\times \mathbb{N}\mapsto {\{0,1\}}^{\ast }$ is defined as $\mathrm{trunc}(a_1\mathrm{\dots }{a}_k\mathrm{\dots }{a}_n,k)=a_1\mathrm{\dots }{a}_k$, with the special case $\mathrm{trunc}(x,0)=ϵ$.

The bit length function $\mathrm{BL}:{\{0,1\}}^{\ast }\mapsto \mathbb{N}$ is defined as $\mathrm{BL}(a_1\mathrm{\dots }{a}_n)=n$, e.g., if $b\in {\{0,1\}}^n$ then $\mathrm{BL}(b)=n$.

Since ${\{0,1\}}^{\ast }\cong \mathbb{N}$, they may put into one-to-one correspondence. A convenient one-to-one correspondence between them is given by the following definition.

We denote the mapping described by Definition 3.1 with the postfix function ${}_{}{}^{\prime }:{\{0,1\}}^{\ast }\mapsto \mathbb{N}$ and ${}_{}{}^{\prime }:\mathbb{N}\mapsto {\{0,1\}}^{\ast }$, which are inverse functions, i.e., $x^{\prime \prime }=x$. An important observation of this mapping is that a natural number $n$ maps to a bit string $n^{\prime }$ of length $\mathrm{BL}(n^{\prime })=\lfloor {\log }_{2}n\rfloor$.

More generally, if we have some set $𝕌$, in a physical computer there must be a way to map the elements of $𝕌$ to bit strings that repesent the values. We provide this mapping with encoder and decoder functions denoted respectively by $\mathrm{e}[𝕌]:𝕌\mapsto {\{0,1\}}^{\ast }$ and $\mathrm{d}[𝕌]:{\{0,1\}}^{\ast }\mapsto 𝕌$ such that $\mathrm{d}[𝕌]\circ e_{𝕌}={\mathrm{id}}_{𝕌}$ and $e_{𝕌}\circ d_{𝕌}={\mathrm{id}}_{{\{0,1\}}^{\ast }}$.

A special case of the encoder and decoder is given by letting any bit string represent either the sequence of bits $a_1\mathrm{\dots }{a}_n$ or as the binary coded decimal (BCD), e.g., $010⟷4$. Thus, any operation on non-negative integers may be applied to bit strings without ambiguity, e.g., $010+01=11$.

Given a function of $g:𝕏\mapsto 𝕐$, the domain of $g$ may be denoted by $\mathrm{dom}(g)=𝕏$ and the codomain may be denoted by $\mathrm{codom}(g)=𝕐$.

A random oracle as given by the following definition.

The theoretical analysis of the perfect hash function makes the following assumption.

Since $\mathrm{PH}$ is a data type that purports to model perfect hash functions, its computational basis is given by the following set of functions.

By the assumption of surjectivity (and the perfect hash function is not rated-distorted), then the load factor is given by $\frac{|𝕏|}{N}$ where $N={\arg \max }_{x\in 𝕏}{\mathrm{hash}}_{𝔸}(x)$, i.e., the maximum hash (natural ordering of integers) of ${\mathrm{hash}}_{𝔸}$.

The most important function, the perfect hash mapping, $\mathrm{perfect}\mathrm{\_}\mathrm{hash}:\mathrm{PH}\times 𝕌\mapsto \mathbb{N}$, is defined as

where

Suppose we have a function $f:𝕌\mapsto {\{0,1\}}^{\ast }$ such that ${f|}_{𝔸}$ is injective, e.g., an encoder for values of $𝔸\subseteq 𝕌$. The composition ${\mathrm{hash}}_{𝔸}={\mathrm{hash}}_{𝔹}\circ f$ where $𝔹=\{f(a)\in {\{0,1\}}^{\ast }|a\in 𝔸\}$ is a perfect hash function of type $𝕌\mapsto \mathbb{N}$ over $𝔸\subseteq 𝕌$. Thus, the rest of the material in this paper does not usually assume any particular domain of the perfect hash function since injections may always be constructed for any set.

Perfect hash functions can be composed with other functions to create new perfect hash functions with different properties. This algebraic structure provides flexibility in designing hash function families.