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].

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