Paper 2018/957

Non-malleable Digital Lockers for Efficiently Sampleable Distributions

Peter Fenteany and Benjamin Fuller

Abstract

An obfuscated program reveals nothing about its design other than its input/output behavior. A digital locker is an obfuscated program that outputs a stored cryptographic key if and only if a user enters a previously stored password. A digital locker provides an adversary no information on either with high probability. An ideal digital locker also detects if an adversary mauls one obfuscation into a valid obfuscation of related values. Such a primitive is achievable in the random oracle model or using general purpose non-interactive zero knowledge proofs of knowledge (NIZKPoK) in the common random string (CRS) model. However, there are no known standard model constructions of nonmalleable digital lockers. Komargodski and Yogev (Eurocrypt, 2018) constructed a simpler primitive: a nonmalleable point function. Security relies on variants of the strong and power DDH assumptions. This work describes the first nonmalleable digital locker without resorting to generic NIZKPoKs. This construction is built in three steps: 1. We construct a nonmalleable digital locker for short keys from any sufficiently nonmalleable point function. 2. We introduce a new primitive called stocky lockers that augments this primitive to retain security if composed with the same password and maintain pseudorandomness. We show Komargodski and Yogev's construction suffices to build stocky lockers under the average-case variants of the same assumptions. This composed construction is nonmalleable with respect to the password. 3. We extend to polynomial length keys that additionally provides nonmalleability over the stored key. This extension combines the digital locker for short keys, nonmalleable codes, and seed-dependent condensers. The seed for the condenser must be public and not tampered. The third step can be achieved in the CRS model. The password distribution can depend on the condenser's seed as long as it is efficiently sampleable. We view this as a midpoint in removing the CRS. Prior works on nonmalleable hashes/one-way functions/extractors also assume a public random object that is not tampered by the adversary. The other steps in our construction do not require a CRS. Nonmalleability for the password is ensured for functions that can be represented as low degree polynomials. Key nonmalleability is ensured for the class of functions prevented by the nonmalleable code.

Note: Narrative changes and fixes