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 is private if it provides an adversary with no information with high probability. An ideal digital locker would also detect if an adversary that mauls an obfuscation on one password and key into a new program that obfuscates a related password or key. Such a primitive is achievable in the random oracle model. Komargodski and Yogev (Eurocrypt, 2018) constructed a simpler primitive - a non-malleable point function - which is a digital locker with no key. This work describes the first non-malleable digital locker. This construction is built in two main steps: 1. Constructing non-malleable digital lockers for short keys. We present one construction for a single bit key and a second for a logarithmic length keys. These constructions can be safely composed with the same input password. This composed construction is non-malleable with respect to the password. Security relies on variants of the strong and power DDH assumptions. 2. An extension to polynomial length keys that additionally provides nonmalleability over the stored key. This extension combines the digital locker for short keys, non-malleable codes, and seed- dependent condensers. The password distribution can depend on the seed of the condenser as long as it is efficiently sampleable. The seed condenser must be public and random but programmability is not required. 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 non-malleable code.

Note: Minor revision, cleaned up comparison to other nonmalleable tools