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 prevent an adversary from mauling an obfuscation on one password and key into a new program that obfuscates a related password or key. There are no known constructions of non-malleable digital lockers (in the standard model). Komargodski and Yogev (Eurocrypt, 2018) constructed a simpler primitive: a non-malleable keyless digital locker. For this functionality, a user can only confirm if their point is correct. This primitive is known as non-malleable point obfuscation. Their construction prevents an adversary from transforming an obfuscation into an obfuscation on a related password. This work first describes two nonmalleable digital lockers for short keys, one for a single bit key and a second for a logarithmic length keys. These constructs can be safely composed with the same input password. We then show how to extend to an arbitrarily polynomial length key and provide non- malleability over the stored password and key. Our full design combines a digital locker for short keys, non-malleable codes, and seed-dependent condensers. Seed-dependent condensers inherently require the distribution of passwords to be efficient sampleable.

Note: Major revision from prior version. Removed the need for common reference string. Now use seed-dependent condensers as authentication.