### 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.

Available format(s)
Publication info
Keywords
point obfuscationnon-malleabilityvirtual black-boxDDHpower-DDH
Contact author(s)
komargodski @ cornell edu
eylon yogev @ weizmann ac il
History
2021-03-16: last of 4 revisions
See all versions
Short URL
https://ia.cr/2018/149

CC BY

BibTeX

@misc{cryptoeprint:2018/149,
author = {Ilan Komargodski and Eylon Yogev},
title = {Another Step Towards Realizing Random Oracles: Non-Malleable Point Obfuscation},
howpublished = {Cryptology ePrint Archive, Paper 2018/149},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/149}},
url = {https://eprint.iacr.org/2018/149}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.