Unconditionally secure block cipher for a finite number of blocks
The PEANUT and WALNUT ciphers are an example of this (see also Vaudenay's decorrelation theory for the theory behind these ciphers). The idea is simple: take a provably secure construction, like the Luby-Rackoff scheme, and instantiate it with random functions that are identical to random up to $h$ invocations.
For example, if your block cipher works on $n=128$-bit blocks, it is easy to come up with a $64$-bit random function that is indistinguishable from random up to $h$ evaluations: a random polynomial of degree $h-1$ over $\mathbb{F}_{2^{64}}$. It takes $hn/2$ bits to represent such a polynomial. You cannot do better than this and remain information-theoretically secure.
Since with Luby-Rackoff you need $4$ rounds with an independent random function each, you need $4$ random polynomials as above to obtain a cipher that has an unconditional attack advantage bound
$$
\mathbf{Adv}^{\mathrm{sprp}}_E(q) \le \frac{q^2}{2^{64}} + \frac{q^2}{2^{128}}\,,
$$
provided the number of queries $q$ stays under the maximum $h$. Security completely breaks down after $h+1$ queries.
With some extra complications you can reduce this to a single random degree-$4h$ polynomial and $4$ Luby-Rackoff rounds.