One Way Function Crypto

A preliminary version of this paper appears in ASIACRYPT 2014. This is the full version appearing as

IACR ePrint Archive Report 2013/873.

Poly-Many Hardcore Bits for Any One-Way Function

and a Framework for Differing-Inputs Obfuscation

Mihir Bellare1

Igors Stepanovs2

Stefano Tessaro3

September 2014

Abstract

We show how to extract an arbitrary polynomial number of simultaneously hardcore bits from any oneway function. In the case the one-way function is injective or has polynomially-bounded pre-image size, we

assume the existence of indistinguishability obfuscation (iO). In the general case, we assume the existence

of differing-input obfuscation (diO), but of a form weaker than full auxiliary-input diO. Our construction

for injective one-way functions extends to extract hardcore bits on multiple, correlated inputs, yielding

new D-PKE schemes. Of independent interest is a definitional framework for differing-inputs obfuscation

in which security is parameterized by circuit-sampler classes.

1

Department of Computer Science & Engineering, University of California San Diego, 9500 Gilman Drive, La Jolla,

California 92093, USA. Email: mihir@eng.ucsd.edu. URL: http://cseweb.ucsd.edu/~mihir/. Supported in part by NSF

grants CNS-1116800 and CNS-1228890.

2

Department of Computer Science & Engineering, University of California San Diego, 9500 Gilman Drive, La Jolla, California

92093, USA. Email: istepano@eng.ucsd.edu. Supported in part by NSF grants CNS-1116800 and CNS-1228890.

3

Department of Computer Science, University of California Santa Barbara, Santa Barbara, California 93106, USA. Email:

tessaro@cs.ucsb.edu. URL: http://www.cs.ucsb.edu/~tessaro/. Supported in part by NSF grant CNS-1423566.

1

Contents

1 Introduction

3

2 Preliminaries

7

3 Parameterized diO framework

8

4 Poly-many hardcore bits for injective OWFs

9

5 Poly-many hardcore bits for any OWF

12

6 Hardcore functions for correlated inputs

14...