Paper 2018/149

Another Step Towards Realizing Random Oracles: Non-Malleable Point Obfuscation

Ilan Komargodski and Eylon Yogev

Abstract

The random oracle paradigm allows us to analyze the security of protocols and constructions in an idealized model, where all parties have access to a truly random function. This is one of the most popular and well-studied models in cryptography. However, being such a strong idealized model, it is known to be susceptible to various weaknesses when implemented naively in ``real-life'', as shown by Canetti, Goldreich and Halevi (J. ACM 2004). As a counter-measure, one could try to identify and implement only one or few of the properties a random oracle possesses that are needed for a specific setting. Such a systematic study was initiated by Canetti (CRYPTO 1997), who showed how to implement the property that the output of the function does not reveal anything regarding the input by constructing a point function obfucator. This property turned out to suffice in many follow-up works and applications. In this work, we tackle another natural property of random oracles and implement it in the standard model. The property we focus on is non-malleability, where it is required that the output on an input cannot be used to generate an output on any related point. We construct a point obfuscator that is both hiding (a la Canetti) and is non-malleable for a non-trivial class of mauling functions. Our construction does not use heavy cryptographic machinery (such as zero-knowledge proofs) and is comparable to that of Canetti in terms of time complexity and obfuscation size. The security of our construction relies on variants of the DDH and power-DDH assumptions. On the technical side, we introduce a new technique for proving security of a construction based on a DDH-like assumption. We call this technique ``double-exponentiation'' and believe it will be useful in the future.