# zbMATH — the first resource for mathematics

Hyper-encryption and everlasting security. (English) Zbl 1054.68049
Alt, Helmut (ed.) et al., STACS 2002. 19th annual symposium on theoretical aspects of computer science. Antibes - Juan les Pins, France, March 14–16, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43283-3). Lect. Notes Comput. Sci. 2285, 1-26 (2002).
Summary: We present substantial extensions of work by Y. Aumann and the second author [Lect. Notes Comput. Sci. 1666, 65–79 (1999; Zbl 0940.94007)], by Y. Aumann and the authors [IEEE Trans. Inf. Theory 48, No. 6, 1668–1680 (2002)] and all previous works on encryption in the bounded storage model introduced by U. Maurer [Lect. Notes Comput. Sci. 1046, 387–398 (1996)]. The major new result is that the shared secret key employed by the sender Alice and the receiver Bob can be re-used to send an exponential number of messages, against strong adaptive attacks. This essential step enhances the usability of the encryption method, and also allows strong authentication and non-malleability described below.

We give an encryption scheme that is provably secure against adaptive attacks by a computationally unbounded adversary in the bounded storage model. In the model, a sender Alice and a receiver Bob have access to a public random string $$\alpha$$, and share a secret key $$s$$. Alice and Bob observe $$\alpha$$ on the fly, and by use of $$s$$ extract bits from which they create a one-time pad $$X$$ used to encrypt $$M$$ as $$C = X \oplus M$$. The size of the secret key $$s$$ is $$| s| = k\log_2{|\alpha|}$$, where $$k$$ is a security parameter. An Adversary $$\mathcal{ AD}$$ can compute and store any function $$A_1(\alpha) = \eta$$, subject to the bound on storage $$|\eta| \leq \gamma \cdot |\alpha|$$, $$\gamma < 1$$, and captures $$C$$. Even if $$\mathcal{ AD}$$ later gets the key $$s$$ and is computationally unbounded, the encryption is provably secure. Assume that the key $$s$$ is repeatedly used with successive strings $$\alpha_1, \alpha_2, \ldots$$ to produce encryptions $$C_1, C_2, \ldots$$ of messages $$M_1, M_2, \ldots$$. $$\mathcal{ AD}$$ computes $$\eta_1 = A_1(\alpha_1)$$, obtains $$C_{1}$$, and gets to see the first message $$M_{1}$$. Using these he computes and stores $$\eta_2 = A_1(\alpha_2, \eta_1, C_1, M_1)$$, and so on. When he has stored $$\eta_l$$ and captured $$C_{l}$$, he gets the key $$s$$ (but not $$M_{l})$$. The main result is that the encryption $$C_{l}$$ is provably secure against this adaptive attack, where $$l$$, the number of time the secret key $$s$$ is re-used, is exponentially large in the security parameter $$k$$. On this we base non-interactive protocols for authentication and non-malleability. Again, the shared secret key used in these protocols can be securely re-used an exponential number of times against adaptive attacks. The method of proof is stronger than the one in the previous papers [loc. cit.], and yields ergodic results of independent interest. We discuss in the Introduction the feasibility of the bounded storage model, and outline a solution. Furthermore, the existence of an encryption scheme with the provable strong security properties presented here, may prompt other implementations of the bounded storage model.
For the entire collection see [Zbl 0989.00048].

##### MSC:
 68P25 Data encryption (aspects in computer science) 94A60 Cryptography 94A62 Authentication, digital signatures and secret sharing
Full Text: