Cryptology ePrint Archive: Report 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.

Category / Keywords: point obfuscation, non-malleability, virtual black-box, DDH, power-DDH

Original Publication (in the same form): IACR-EUROCRYPT-2018

Date: received 7 Feb 2018, last revised 26 Feb 2019

Contact author: komargodski at cornell edu,eylon yogev@weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20190226:074205 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]