Theory and Application of Extractable Functions

Full textClick to download.
CitationPhD Thesis, Yale University Computer Science Department, 2009
AuthorRonny Ramzi Dakdouk


We propose a new cryptographic primitive, called extractable functions. An extractable function guarantees any machine that manages to output a point in the range of this function knows a corresponding preimage. We capture knowledge of preimage by way of algorithmic extraction. We formulate two main variants of extractability, namely noninteractive and interactive. The noninteractive variant can be regarded as a generalization from specific knowledge assumption to a notion that is formulated in general computational terms. Indeed, we show how to realize it under several different assumptions. On the other hand, interactive extraction can be realized from certain perfectly one-way (POW) functions or verifiable secret-sharing (VSS) schemes. We then initiate a more general study of extractable function aimed at understanding the concept of extractability in of itself. In particular we demonstrate that a weak notion of extraction implies a strong one, and make rigorous the intuition that extraction and obfuscation are complementary notions. We demonstrate the usefulness of the new primitive in two quite different settings. First, we show how extractable functions can be used to capture, in the standard model, the knowledge of queries property that is so useful in the Random Oracle (RO) model. Specifically, we show how to convert a class of CCA2-secure encryption schemes in the RO model to concrete ones by simply replacing the Random Oracle with an extractable function, without much change in the logic of the original proof. Second, we show how extractable functions can be used to construct 3-round ZK arguments using weaker knowledge assumptions than previous results due to Hada and Tanaka (Crypto 1998) and Lepinski (M.S. Thesis, 2004). This also opens the door for constructing 3-round ZK arguments based on other assumptions. Finally, we exploit techniques used in constructing extractable functions to obfuscate point functions with multibit output. A point function with multibit output returns a fixed string on a single input point and zero everywhere else. Obfuscation of such functions has a useful application as a strong form of symmetric encryption where security holds without any assumption on the distribution of the secret key. We provide a construction that obfuscates these functions. This construction is generic in the sense that it can use any POW function or obfuscator for point functions.

Back to publications
Back to previous page