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 α, and share a secret key s. Alice and Bob observe α on the fly, andb y use of s extract bits from which they create a one-time pad X used to encrypt M as C = X⊕M. The size of the secret key s is ∣s∣ = klog₂ ∣α∣, where k is a security parameter. An Adversary AD can compute andstore any function A ₁(α) = η, subject to the bound on storage ∣η∣ ≤γ. ·∣α∣, γ < 1, and captures C. Even if 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 α₁, α₂, ... to produce encryptions C ₁, C ₂, ... of messagesM ₁,M ₂, .... AD computes η₁ = A ₁(α₁), obtains C ₁, and gets to see the first message M ₁. Using these he computes andstores η₂ = A ₁(α₂, α₁, C ₁,M ₁), and so on. When he has stored η_l andcaptured 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-usedan exponential number of times against adaptive attacks. The method of proof is stronger than the one in [1], [2], 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.