Lecture Notes in Computer Science Commenced Publication in 1973 Founding and Former Series Editors: Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
Editorial Board David Hutchison Lancaster University, UK Takeo Kanade Carnegie Mellon University, Pittsburgh, PA, USA Josef Kittler University of Surrey, Guildford, UK Jon M. Kleinberg Cornell University, Ithaca, NY, USA Alfred Kobsa University of California, Irvine, CA, USA Friedemann Mattern ETH Zurich, Switzerland John C. Mitchell Stanford University, CA, USA Moni Naor Weizmann Institute of Science, Rehovot, Israel Oscar Nierstrasz University of Bern, Switzerland C. Pandu Rangan Indian Institute of Technology, Madras, India Bernhard Steffen University of Dortmund, Germany Madhu Sudan Massachusetts Institute of Technology, MA, USA Demetri Terzopoulos University of California, Los Angeles, CA, USA Doug Tygar University of California, Berkeley, CA, USA Gerhard Weikum Max-Planck Institute of Computer Science, Saarbruecken, Germany
4948
Ran Canetti (Ed.)
Theory of Cryptography Fifth Theory of Cryptography Conference, TCC 2008 New York, USA, March 19-21, 2008 Proceedings
13
Volume Editor Ran Canetti IBM T.J. Watson Research Center NY, USA E-mail:
[email protected]
Library of Congress Control Number: 2008921565 CR Subject Classification (1998): E.3, F.2.1-2, C.2.0, G, D.4.6, K.4.1, K.4.3, K.6.5 LNCS Sublibrary: SL 4 – Security and Cryptology ISSN ISBN-10 ISBN-13
0302-9743 3-540-78523-X Springer Berlin Heidelberg New York 978-3-540-78523-1 Springer Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com ©International Association for Cryptologic Research 2008 Printed in Germany Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India Printed on acid-free paper SPIN: 12237708 06/3180 543210
Preface
TCC 2008, the 5th Theory of Cryptography Conference, was held in New York, New York, March 19–21, 2008, at New York University. TCC 2008 was sponsored by the International Association for Cryptologic Research (IACR) and was organized in cooperation with the Department of Computer Science at New York University and the Courant Institute for Mathematical Sciences. The General Chairs of the conference were Yevgeniy Dodis and Victor Shoup. The conference received 81 submissions, of which the Program Committee selected 34 for presentation at the conference. The authors of two papers then decided to merge their papers, resulting in a total of 33 presented papers. The Best Student Paper Award was given to Paul Valiant for his paper “Incrementally Verifiable Computation or Knowledge Implies Time/Space Efficiency.” These proceedings consist of revised versions of the presented papers. The revisions were not reviewed. The authors bear full responsibility for the contents of their papers. The conference program also included four special events: an invited talk entitled “Randomness Extractors and Their Cryptographic Applications” by Salil Vadhan; a tutorial entitled “Bridging Cryptography and Game Theory: Recent Results and Future Directions,” given by Jonathan Katz (with an accompanying tutorial in the proceedings); a panel discussion on “Game Theory and Cryptography: Towards a Joint Point of View?” with Tal Rabin as moderator and Jonathan Katz, Silvio Micali, and Moni Naor as panelists; and a Rump Session chaired by Anna Lysyanskaya. In spite of the relatively small number of submissions, many of them were of high quality. Consequently, the selection process was challenging and very competitive. Indeed, a number of good papers were not accepted due to lack of space in the program. The main considerations in selecting the program were conceptual and technical innovation, quality of presentation, and relevance to the theory of cryptography. An attempt was made to maintain the unique character of the conference as a stage for presenting innovative work on the foundations of cryptography. I would like to thank the TCC Steering Committee for entrusting me with the role of Program Committee Chair. In the few years since its inception, TCC has been tremendously successful in attracting high-quality papers and in providing a home and identity for the theory of cryptography community. I am honored to have had the opportunity to contribute to the continuation of this success. Special thanks are due to the Program Committee members, who have dedicated so much time and effort to provide a thorough and in-depth review of the submissions, with high standards of professional integrity. I also thank the many external reviewers who assisted the Program Committee in its work. Most
VI
Preface
importantly, I thank the authors of submitted papers for their contributions; these papers are, after all, the only reason for TCC to exist. I am grateful to the General Chairs, Yevgeniy Dodis and Victor Shoup, and their assistant Anna Mackay for their invaluable work in making the conference happen. Another special thanks is due to Shai Halevi for writing the software that greatly facilitated the committee work, and for his responsiveness in attending to our whims. I thank our corporate sponsors, the D. E. Shaw group, IBM, and Microsoft for their generous sponsorship of the conference, and Cynthia Dwork, Rosario Gennaro, Jonah Kolb, Christine Mathias, and Tal Rabin for their help in obtaining the sponsorships. Finally, I appreciate the assistance provided by the Springer LNCS editorial staff, including Alfred Hofmann, Frank Holzwarth, and Anna Kramer, in assembling these proceedings. January 2008
Ran Canetti TCC’ 2008 Program Chair
TCC 2008 5th Theory of Cryptography Conference New York University, New York, New York, USA March 18–21, 2008
General Chairs Yevgeniy Dodis and Victor Shoup, New York University
Sponsoring Institutions The D. E. Shaw group IBM Inc. Microsoft Inc.
Program Committee Boaz Barak Ran Canetti Yevgeniy Dodis Marc Fischlin Jens Groth Dennis Hofheinz Susan Hohenberger Russell Impagliazzo Eyal Kushilevitz Yehuda Lindell Ueli Maurer Moni Naor Tatsuaki Okamoto Adriana Palacio Christopher J. Peikert Leonid Reyzin abhi shelat Hoeteck Wee
Princeton University IBM Research (Chair) New York University Darmstadt University of Technology University College, London Centrum voor Wiskunde en Informatica (CWI) Johns Hopkins University University of California San Diego and the Institute of Advanced Study Technion Bar Ilan University ETH Z¨ urich Weizmann Institute NTT Laboratories Bowdoin College Stanford Research Institute Boston University University of Virginia University of California, Berkeley and Columbia University
VIII
Organization
TCC Steering Committee Mihir Bellare Ivan Damg˚ ard Oded Goldreich (Chair) Shafi Goldwasser Johan H˚ astad Russell Impagliazzo Ueli Maurer Silvio Micali Moni Naor Tatsuaki Okamoto
University of California, San Diego University of Aarhus Weizmann Institute of Science MIT and Weizmann Institute of Science Royal Institute of Technology University of California, San Diego ETH Z¨ urich Massachusetts Institute of Technology Weizmann Institute of Science NTT Laboratories
External Reviewers Michel Abdalla Joel Alwen Benny Applebaum Giuseppe Ateniese Zuzana Beerliova Amos Beimel Andrej Bogdanov Seung Geol Choi Sherman Chow Nenad Dedi´c Serge Fehr Matthias Fitzi Eiichiro Fujisaki Juan Garay Sharon Goldberg Robbert de Haan Iftach Haitner Kristiyan Haralambiev Danny Harnik Yuval Ishai Bhavana Kanukurthi Jonathan Katz Robert Koenig Gillat Kol
Chiu Yuen Koo Hugo Krawczyk Anja Lehmann Richard Lindner Moses Liskov Vadim Lyubashevsky Joshua Mason Alexander May Anton Mityagin Kirill Morozov Joern Mueller-Quade Gregory Neven Ryo Nishimaki Carles Padr Omkant Pandey Saurabh Panjwani Rafael Pass Krzysztof Pietrzak Manoj Prabhakaran Bartosz Przydatek Omer Reingold Renato Renner Thomas Ristenpart Guy Rothblum
Amit Sahai Louis Salvail Palash Sarkar Dominique Schroeder Gil Segev Sarah Shoup Thomas Shrimpton Adam Smith Stefano Tessaro Luca Trevisan Dominique Unruh Salil Vadhan Vinod Vaikuntanathan Bogdan Warinschi Brent Waters John Watrous Stephen A. Weis David Woodruff Juerg Wullschleger David Xiao Scott Yilek Shengyu Zhang Yunlei Zhao
Table of Contents
Technical Session 1 Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Paul Valiant
1
On Seed-Incompressible Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Shai Halevi, Steven Myers, and Charles Rackoff
19
Technical Session 2 Asymptotically Efficient Lattice-Based Digital Signatures . . . . . . . . . . . . . Vadim Lyubashevsky and Daniele Micciancio
37
Basing Weak Public-Key Cryptography on Strong One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Eli Biham, Yaron J. Goren, and Yuval Ishai
55
Technical Session 3 Which Languages Have 4-Round Zero-Knowledge Proofs? . . . . . . . . . . . . . Jonathan Katz
73
How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lior Malka
89
General Properties of Quantum Zero-Knowledge Proofs . . . . . . . . . . . . . . Hirotada Kobayashi
107
Technical Session 4 The Layered Games Framework for Specifications and Analysis of Security Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Amir Herzberg and Igal Yoffe
125
Universally Composable Multi-party Computation with an Unreliable Common Reference String . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vipul Goyal and Jonathan Katz
142
Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries . . . . . . . . . . . . . . . . . . . Carmit Hazay and Yehuda Lindell
155
X
Table of Contents
Fast Private Norm Estimation and Heavy Hitters . . . . . . . . . . . . . . . . . . . . Joe Kilian, Andr´e Madeira, Martin J. Strauss, and Xuan Zheng
176
Technical Session 5 Matroids Can Be Far from Ideal Secret Sharing . . . . . . . . . . . . . . . . . . . . . . Amos Beimel, Noam Livne, and Carles Padr´ o
194
Perfectly-Secure MPC with Linear Communication Complexity . . . . . . . Zuzana Beerliov´ a-Trub´ıniov´ a and Martin Hirt
213
MPC vs. SFE: Perfect Security in a Unified Corruption Model . . . . . . . . . Zuzana Beerliov´ a-Trub´ıniov´ a, Matthias Fitzi, Martin Hirt, Ueli Maurer, and Vassilis Zikas
231
Invited Talk Bridging Game Theory and Cryptography: Recent Results and Future Directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Jonathan Katz
251
Technical Session 6 Verifiably Secure Devices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sergei Izmalkov, Matt Lepinski, and Silvio Micali
273
Lower Bounds on Implementing Robust and Resilient Mediators . . . . . . . Ittai Abraham, Danny Dolev, and Joseph Y. Halpern
302
Cryptography and Game Theory: Designing Protocols for Exchanging Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gillat Kol and Moni Naor
320
Technical Session 7 Equivocal Blind Signatures and Adaptive UC-Security . . . . . . . . . . . . . . . Aggelos Kiayias and Hong-Sheng Zhou
340
P-signatures and Noninteractive Anonymous Credentials . . . . . . . . . . . . . . Mira Belenkiy, Melissa Chase, Markulf Kohlweiss, and Anna Lysyanskaya
356
Technical Session 8 Multi-property Preserving Combiners for Hash Functions . . . . . . . . . . . . . Marc Fischlin and Anja Lehmann
375
Table of Contents
XI
OT-Combiners Via Secure Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . Danny Harnik, Yuval Ishai, Eyal Kushilevitz, and Jesper Buus Nielsen
393
Semi-honest to Malicious Oblivious Transfer—The Black-Box Way . . . . . Iftach Haitner
412
Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee
427
Technical Session 9 A Linear Lower Bound on the Communication Complexity of Single-Server Private Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . Iftach Haitner, Jonathan J. Hoch, and Gil Segev
445
Randomness Extraction Via δ-Biased Masking in the Presence of a Quantum Attacker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Serge Fehr and Christian Schaffner
465
Technical Session 10 An Equivalence Between Zero Knowledge and Commitments . . . . . . . . . . Shien Jin Ong and Salil Vadhan Interactive and Noninteractive Zero Knowledge are Equivalent in the Help Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Andr´e Chailloux, Dragos Florin Ciocan, Iordanis Kerenidis, and Salil Vadhan
482
501
Technical Session 11 The Round-Complexity of Black-Box Zero-Knowledge: A Combinatorial Characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Daniele Micciancio and Scott Yilek
535
On Constant-Round Concurrent Zero-Knowledge . . . . . . . . . . . . . . . . . . . . Rafael Pass and Muthuramakrishnan Venkitasubramaniam
553
Technical Session 12 Concurrent Non-malleable Commitments from Any One-Way Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Huijia Lin, Rafael Pass, and Muthuramakrishnan Venkitasubramaniam
571
XII
Table of Contents
Faster and Shorter Password-Authenticated Key Exchange . . . . . . . . . . . . Rosario Gennaro
589
Technical Session 13 Saving Private Randomness in One-Way Functions and Pseudorandom Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nenad Dedi´c, Danny Harnik, and Leonid Reyzin
607
Degradation and Amplification of Computational Hardness . . . . . . . . . . . . Shai Halevi and Tal Rabin
626
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
645
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency Paul Valiant Massachusetts Institute of Technology
[email protected] Abstract. A probabilistically checkable proof (PCP) system enables proofs to be verified in time polylogarithmic in the length of a classical proof. Computationally sound (CS) proofs improve upon PCPs by additionally shortening the length of the transmitted proof to be polylogarithmic in the length of the classical proof. In this paper we explore the ultimate limits of non-interactive proof systems with respect to time and space efficiency. We present a proof system where the prover uses space polynomial in the space of a classical prover and time essentially linear in the time of a classical prover, while the verifier uses time and space that are essentially constant. Further, this proof system is composable: there is an algorithm for merging two proofs of length k into a proof of the conjunction of the original two theorems in time polynomial in k, yielding a proof of length exactly k. We deduce the existence of our proposed proof system by way of a natural new assumption about proofs of knowledge. In fact, a main contribution of our result is showing that knowledge can be “traded” for time and space efficiency in noninteractive proof systems. We motivate this result with an explicit construction of noninteractive CS proofs of knowledge in the random oracle model.
1
Introduction
Perhaps the simplest way to introduce the computational problem we address is by means of the following. Human motivation. Suppose humanity needs to conduct a very long computation which will span super-polynomially many generations. Each generation runs the computation until their deaths when they pass on the computational configuration to the next generation. This computation is so important that they also pass on a proof that the current configuration is correct, for fear that the following generations, without such a guarantee, might abandon the project. Can this be done? Computational setting. In a more computational context, this problem becomes: How can we compile a machine M into a new machine M that frequentlyoutputs R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 1–18, 2008. c International Association for Cryptologic Research 2008
2
P. Valiant
pairs (ci , πi ) where the ith output consists of the ith memory state ci of machine M , and a proof πi of its correctness, while keeping the resources of M intact?1 1.1
A New Problem
We motivate our problem by way of a few examples of how current techniques fail to achieve our goal. Suppose we are given a computation M that takes time t and space k t. A natural approach is have the compiled machine M keep a complete record of all the memory states of M it has simulated so far; every time it simulates a new state of M , it uses this record to output a proof that its simulation of M is thus far correct. However, this approach has the clear drawbacks that the compiled machine M uses space tk to store the records, and the proofs it outputs consist simply of this record of size tk; this requires the verifier of the proofs to also use time tk and space tk to verify each proof. If t is polynomial in k, then all these parameters are polynomial in k and this simple system is in fact “optimal up to polynomial factors in k.” We concern ourselves here with the much more interesting case where the running time t is much larger than k —exponentially larger, even— in which case this naive system is not at all efficient. What we need is a more efficient proof system. We note that the problems of improving the efficiency of the construction, transmission, and verification of proofs have been important themes in our field, and have fueled a long line of research. One major milestone on this path was the discovery of probabilistically checkable proofs (PCPs) (see [1,2,5,10] and the references therein). Under a PCP proof system statements with classical proofs of exponential length could now be verified in polynomial time, via randomized sampling of an encoded version of the classical proof. A PCP system still uses exponential resources to construct and transmit the proof, but verification is now polynomial time. The second milestone we note is the theory of computationally sound (CS) proofs as formalized by Kilian and Micali [12,13]. This notion improves on the PCP system by keeping verification polynomial time while shortening the length of the transmitted proof from exponential to polynomial in k. If we instruct the compiled machine M to output (noninteractive) CS proofs, then the length of the transmitted proofs, and the time and space required by the verifier are now polynomial in k, but the compiler still requires memory at least t, and a time interval of at least t between consecutive proofs.2 1
2
More generally one might consider a machine that, instead of outputting proofs πi , engages in some interactive proof protocol. A third major approach for improving the efficiency of proofs, arguably the most historically successful, is that of adding interaction between the prover and verifier[11,15,3]. Unfortunately, this approach does not help us here: our prover has only k memory so he may transfer his entire knowledge to the verifier at the start of their interaction; any further correspondence between the prover and verifier may be simulated by the verifier with no loss of efficiency.
Incrementally Verifiable Computation
1.2
3
Intuitive Idea of Our Solution
The ideal way to achieve incrementally verifiable computation consists of efficiently merging two CS proofs of equal length into a single CS proof which is as short and easy to verify as each of the original ones. Letting c0 , c1 , . . . be the sequence of configurations of machine M , and for i < j, intuitively denote t by (M : ci → cj ) the assertion that configuration cj is correctly obtained from configuration ci by running M for t steps. After running M for 1 step from the initial configuration c0 so as to reach configuration c1 one could easily produce 1 a CS proof of (M : c0 → c1 ). Running M for another step from configuration c1 , 1 one can easily produce a CS proof that (M : c1 → c2 ). At this point, if CS proofs can be easily merged as hypothesized above, one could obtain a CS proof that 2 (M : c0 → c2 ). And so on, until a final configuration cf is obtained, together t with a CS proof that (M : c0 → cf ) Unfortunately, we have no idea of how to achieve such efficient and length preserving merging of CS proofs. However, if a variant of CS proofs —which we call CS proofs of knowledge— exist, we show a sufficient approximation of this ideal strategy. The main idea is to construct recursively embedded CS proofs: to merge proofs π1 and π2 I prove that “I have seen convincing π1 and π2 .” In a nutshell, the CS proof methodology enables us to work with very short proofs, and proofs of knowledge enable the soundness of the proof system to persist across many levels of recursion. 1.3
A New Role for a New Type of Proof of Knowledge
Proofs of knowledge may be seen as a restricted form of classical proofs. While classically, proofs of a statement “There exists w such that R(x, w) = 1”3 can take a wide variety of non-constructive forms, the proof of knowledge form asserts essentially “I have seen a w such that R(x, w) = 1.” We note here that the inapplicability of classical proofs to our setting results from the combination of two circumstances: we require our proofs to be embeddable in other proofs, and we must work in merely computationally sound proof systems where deceptive proofs— while almost impossible to find— exist in abundance. We see the problem, intuitively, if we try to embed two computationally sound proof systems. The result would be a (computationally sound) proof that “There exists a computationally sound proof π of x.” The problem is that of course there exists a computationally sound proof of x, even when x is false. So a proof that there exists a computationally sound proof of x implies nothing about the truth or falsehood of x. Significantly, however, proofs of knowledge can be combined in this way: the result is a (computationally sound) proof that “Prover A has seen a computationally 3
We remind the reader that since classical proofs are verifiable in polynomial time, we may consider any classical theorem as being a statement of membership in an N P -language of the form “There exists a proof w such that the verifier R accepts the pair consisting of the theorem x and proof w.”
4
P. Valiant
sound proof that Prover B has seen a witness w of x.” Intuitively, this is the difference between saying “A is convinced that B is convinced of x” and saying “A is convinced that B could be convinced of x” —the first statement is reasonable evidence of x when both A and B are reasonable, but the second statement holds no weight since even a reasonable person could be mislead. In essence, the proof of knowledge property lets “reasonableness” be transferred down a sequence of provers. The formal statement of this assertion is that by sufficient repeated application of the knowledge extractor E associated with the proof system one can extract a valid witness w from any procedure that returns embedded proofs. Remark 1: This simple intuition unfortunately translates into neither simple definitions nor simple proofs. Because this work seeks to optimize both prover and verifier time and space as well as the overall soundness of the proofs, we need to keep track everywhere not only of who is proving who’s knowledge of what to whom, but also the time and space bounds of all involved parties, along with the security parameters. Nevertheless, it is our hope that the simple intuition underlying the constructions here will make the technical details less opaque. Remark 2: We note that embedding proof systems deprives us of another principal tool: the use of random oracles. Specifically, suppose we have an oraclebased prover-verifier system (P O , V O ) that can prove statements about the results of computation like “Machine M accepts the following string within t time steps. . . .” When we try to recursively embed this system the recursion breaks down because, even at the first level of recursion, we are no longer trying to prove statements about classical computation but rather statements of the form “M with oracle access to O accepts the following string....” Thus standard applications of random oracles do not appear to help. It remains an interesting question whether the goals of this paper may be attained in some other way using random oracles. The Noninteractive CS Knowledge Assumption. Random oracles are intricately tied to CS proofs, in that the only known constructions of noninteractive CS proofs make use of random oracles (see [13]). Nevertheless, as with most random oracle constructions, the hope is that in practice the random oracle may be replaced by a suitably strong hash function plus access to a common random string. In Section 4 we extend Micali’s construction of CS proofs to a construction of CS proofs of knowledge: there exists an efficient extractor E that, given a statement X, a CS proof π, and access to the CS prover that produced π, outputs in quasilinear time a (classical) proof Π of X. We highlight this construction as a motivation for our assumption that oracle-less CS proofs of knowledge exist. In essence, our assumption states that, in a specific construction of noninteractive CS proofs (Constructions 4 and 5), it is possible to replace the random oracle with a random string and still preserve the strength of the proofs. (That is, we do not invoke the random-oracle hypothesis in its general form. As shown by Canetti, Goldreich, and Halevi [8] and others in different contexts, we expect
Incrementally Verifiable Computation
5
that there may be other non-interactive CS proof constructions for which no way to replace the oracle exists.) We note that, while the Fiat-Shamir heuristic of replacing random oracle calls with a deterministic hash function yields feasible proposals for how to remove the oracle calls from the prover and verifier, it says nothing about how to translate the knowledge extractor into this new setting. For this reason we cannot explicitly conjecture a noninteractive CS proof of knowledge. However, in the context of this paper, the knowledge extractor component of the CS proof system serves only as a technique to argue security and is not invoked in our construction of incrementally verifiable computation. Thus we may propose the following much more explicit conjecture: our construction of incrementally verifiable computation (Theorem 1) works when using the prover-verifier pair (P, U ) from Construction 4, modified by replacing the random oracle with a suitably strong hash function plus access to a common random string. Knowledge ⇒ Time/Space Efficiency. In this work we start with an unusual and very strong assumption about (proofs of) knowledge and conclude with a proof system of unprecedented time and space efficiency. In this paragraph we wish to draw the reader’s attention not to the assumption or the conclusion, but to the nature of the relationship between them. On the left we make an assumption about knowledge in CS proofs: we take a restricted system that only deals with witnesses of length 3k and compresses them to proofs of length k, the security parameter, and assume that there is a linear-time knowledge extractor that can extract the witness given access to the prover. On the right we conclude with a proof system that compresses any proof to length poly(k), uses space polynomial in the space needed to classically accept the language, and is timeefficient in the tightest possible sense, using only poly(k) time to process each step of the classical acceptance algorithm. We note that current constructions of non-interactive CS proofs based on random oracles need time polynomial in the time to classically accept, and space of the same order as their time[13]. Our results constitute a new technique to leverage knowledge to gain time and space efficiency, and is in a sense a completeness result for CS proof systems.
2 2.1
Definitions Noninteractive Proofs and the Common Random String Model
It is a well-known aphorism in cryptography that “security requires randomness”. In many standard settings, a participant in a protocol injects randomness into his responses to protect him from some pre-prepared deviousness on the part of the other participant. In the noninteractive proof setting such an approach is inadequate: the verifier is unable to protect himself with randomized messages to the prover, since he cannot even communicate with the prover. To address these issues, the common random string (CRS) model was introduced [7,6].
6
P. Valiant
The CRS model —sometimes called the common reference string model— assumes that all parties have access to the same random string, and further that each can be confident that this string is truly random and not under the influence of the other parties. Potential examples of such a string are measurements of cosmic background radiation or, for a string that will appear in the future, tomorrow’s weather. In the analysis of the security of a CRS protocol leeway must be given for “unlucky” choices of strings, since if every choice of string worked in the protocol we would not need a random one. Thus even if a CRS protocol has a chance of failing, we still consider it secure if this chance is negligible as a function of the size of the random string. 2.2
Incremental Computation
Basic notation. We denote a Turing machine M with no inputs by M (), a Turing machine with one input by M (·), a Turing machine with two inputs by M (·, ·), etc. We assume a standard encoding, and denote by |M | the length of the description of M . For a Turing machine M running on input s, we denote by timeM (s) the time M takes on input s, and by spaceM (s) the space M takes on input s; we denote the empty input by , so that spaceM () is the space of Turing machine M when run on no input. Incremental outputs. Commonly, Turing machines make an output only once, and making this output ends the computation. Instead, we interpret Turing machines as being able to output their current memory state at certain times in their operation: explicitly, consider a Turing machine with a special state “Output” where whenever the machine is in state “Output” the entire contents of its tape are outputted. 4 This captures our intuitive notion of an “incremental computation,” namely one divided into “generations” where at the end of each generation the entire memory configuration is output so that the next generation may resume the computation from the current configuration. 2.3
Incrementally Verifiable Computation
We formally define incrementally verifiable computation here. We consider a Turing machine M () that we wish to simulate for t time steps using k memory, where k ≥ log t. We consider a fixed compiler C(·, ·) that produces from (M, k) an incrementally verifiable version of M , namely a machine C(M, k) = T (·) that takes as input the common random string, runs in time t · k O(1) , uses memory k O(1) , and every k O(1) time steps outputs its memory configuration. The jth 4
We note that this is a slightly unusual model of output, as the machine would be unable to output a string such as “Hello World” without first deleting all other memory locations on the tape. In the context of this paper, we expect machines to not delete this other information: since we consider only poly(k)-space machines, it imposes no undue burden on the prover to output this information, and no undue burden on the verifier to ignore it.
Incrementally Verifiable Computation
7
memory configuration output should be interpreted as a pair consisting of a claim about the memory configuration of M at time j, and a CS proof of its correctness. There is a fixed machine V , the verifier, that will accept all pairs of configurations and proofs generated in this way, and will reject other pairs, subject to the usual condition of the CRS model that the verifier may be fooled with negligible probability, and the computational soundness caveat that an adversary with enormous computational resources may also fool the verifier. Definition 1. An increasing sequence of integers {tj } is an α-incremental timeline if for any j, tj − tj−1 ≤ α. Definition 2. A Turing machine that makes outputs at every time on an α– incremental timeline is called an α–incremental output Turing machine. Definition 3 (Feasible Compiler). Let C(·, ·) be a polynomial time Turing machine. We say that C is a feasible compiler if there exists a constant c such that for all k > 0 and all M () such that |M | ≤ k, C(M, k) is a Turing machine T (·) taking as input the common random string, such that 1. T is a k c -incremental output Turing machine. 2. spaceT (r) = k c for all inputs r. In other words, properties 1 and 2 guarantee that each compiled machine T outputs its internal configuration “efficiently often” while working in “efficient space.” Definition 4 (Incrementally Verifiable Computation). The pair (C, V ) is an incrementally verifiable computation scheme (in the CRS model) with security K if C is a feasible compiler, V is a polynomial-time Turing machine (“the verifier”) and K(k) : Z+ → Z+ , such that the following properties hold: For any Turing machine M with |M | ≤ k let the jth output of the compiled machine C(M, k) be parsed as an ordered pair (mj , πjr ), representing a claim about the jth memory configuration of M , and its proof; and let r denote the common random string of length k 2 . We require: 1. (Correctness) The compiled machine accurately simulates M , in that mj is indeed the jth memory configuration of M () for all j, independent of r. 2. (Completeness) The verifier V accepts the proofs πjr : ∀r, V (M, j, mj , πjr , r) = 1. 3. (Computational soundness) For any constant c and for any machine P that r for any length k 2 input r outputs a triple (j, mr j , πj ) in time K, we have for large enough k that r r −c . P robr [mr j = mj ∧ V (M, j, mj , πj , r) = 1] < k
We note that for the incrementally verifiable computation scheme to be secure against polynomial-time adversaries we must have K super-polynomial.
8
P. Valiant
2.4
Noninteractive CS Proofs of Knowledge
We now specify the assumption we make: the existence of noninteractive CS proofs of knowledge. We note that proofs of knowledge are typically studied in the form of zero knowledge proofs of knowledge. In this setting, one party wants to convince another party that he possesses certain knowledge without revealing this knowledge. The reason why he does not simply transmit all his evidence to the other party is that he wishes to maintain his privacy. In our setting the reason one generation does not just transmit all its evidence to the next generation is not a privacy concern, but rather the concern that the following generation will not have the time to listen to all this evidence. In both settings, the “knowledge” that must be proven may be considered to be a witness for a member of an NP-complete language: one party proves to the other that he knows, for example, a three-coloring of a certain graph. In the zero-knowledge setting, our prover does not wish for the verifier to learn a three-coloring of the graph. In the incremental computation setting, our prover is worried that the verifier may not want to spare the resources to learn a three-coloring of the graph. Related issues were considered in a paper of Barak and Goldreich where they investigated efficient (interactive) ways of providing proofs and proofs of knowledge [4]. Our definition of a noninteractive CS proof of knowledge contains elements from their definition of a universal argument. For the sake of concreteness, we work with a specific NP-complete language, which has the property that for any k the strings in the language of length 4k have witnesses of length 3k. We will require of our CS proof system that instead of returning proofs of length 3k (for example, the witnesses) the proofs are shortened to be of length k. Definition 5. Let c be a constant. The language Lc consists of the ordered pairs (M, x) where M is a Turing machine and x is a string such that, letting k = |M | we have: 1. |x| = 3k. 2. There exists a string w of length 3k such that M when run on the concatenation (x, w) accepts within time k c . We note that the string w may be thought of as the NP witness for (M, x)’s membership in the language. Further, since M may express any polynomial-time computation (for large enough k), the language Lc is NP complete.5 Definition 6 (Noninteractive CS proof of knowledge). The pair (P, U ) is a noninteractive CS proof of knowledge (in the CRS model) with parameters K (k) : Z+ → Z+ , c, c1 , c2 if P and U are Turing machines such that for all machines M , defining k = |M |, and all strings x of length 3k the following properties hold: 5
One can easily manipulate any NP language into one whose members and witnesses have lengths in the 4:3 ratio by appropriate padding.
Incrementally Verifiable Computation
9
1. (Efficient prover) For any (CRS) string r of length k, timeP (M, x, w, r) = k O(1) 2. (Length shrinking) For any (CRS) string r of length k, |P (M, x, w, r)| = k. 3. (Efficient verification) For any (CRS) string r of length k, timeU (P (M, x, w, r), M, x, r) ≤ k c−1 4. (Completeness) For any (CRS) string r of length k, U (P (M, x, w, r), M, x, r) = 1 5. (Knowledge extraction) There exists a constant c2 such that for any Turing machine P there exists a randomized Turing machine EP , the extractor, such that for any input (M, x) of length 4k such that for all r of length k, timeP (M, x, r) ≤ K (k) and P rr [U (P (M, x, r), M, x, r) = 1] = α > 1/K we have P rob[w ← EP (M, x) : M (x, w) = 1] > 1/2 and the running time of EP (M, x) is at most k c2 /α times the expected running time (over choices of r) of P (M, x, r).
3 3.1
Constructing Incrementally Verifiable Computation Merging Proofs t
We aim here to reexpress claims of the form M : s1 → s2 as claims of membership in the language Lc . The equivalence will not be exact but instead, in light of the goals of this paper, computationally sound. We define this relation inductively, for t that are powers of 2. The base case, when t = 1, is an exact relation. Construction 1 (Base Case). Let T0 be the machine that interprets its input as a pair of length 3k strings (x, w) where x is interpreted as a triple of length k strings x = (M, s1 , s2 ), and checks that M when simulated for one step on configuration s1 ends up in configuration s2 , ignoring the auxiliary input w. We note that for strings M, s1 , s2 of length k, the pair (T0 , (M, s1 , s2 )) is in Lc 1 if and only if M : s1 → s2 . The language Lc is crucial here, because this is the language which (by assumption) we may find CS proofs for. We extend this construction, defining machines Ti such that (Ti , (M, s1 , s2 )) ∈ 2i
Lc is equivalent in a computationally sound sense to M : s1 → s2 . In particular, Ti is such that, given CS proofs of the claims (Ti, (M, s1 , s2 )) ∈ Lc and (Ti , (M, s2 , s3 )) ∈ Lc we can construct a CS proof of the claim (Ti+1 , (M, s1 , s3 )) ∈ Lc . Reexpressing 2i
these three statements, we see that given a CS proof that “(M : s1 → s2 )” and a CS 2i
2i+1
proof that “(M : s2 → s3 )” we may construct a CS proof that “(M : s1 → s3 ).” Since the lengths of each of these CS proofs is (by definition) k, this is our desired notion of merging proofs. Construction 2. Define Ti+1 as a machine that interprets its input as the pair (x, w) where x is interpreted as (M, s1 , s3 ) and w is interpreted as (p1 , p2 , s2 ), and does the following:
10
P. Valiant
Check if p1 , p2 are CS proofs of knowledge respectively that (Ti , (M, s1 , s2 )) ∈ Lc and (Ti , (M, s2 , s3 )) ∈ Lc . Given x, w, i such that w witnesses the fact that (Ti+1 , x) ∈ Lc , we can efficiently construct a CS proof of this fact as P (Ti+1 , x, w, ri+1 ) by assumption. (We note that we take the common random string ri+1 to be dependent on i.) We prove that this construction is computationally sound. In the following, we call a pair (x = (M, s1 , s2 ), p) deceptive if p proves to the verifier that (Ti , x) ∈ Lc but it is not the case that running M for 2i steps from memory state s1 reaches memory state s2 . The proof is by induction; the base case of T0 , as observed above, is trivial. Lemma 1. For α ∈ ( K1 , 1) and b ∈ (2(2i + k), K ), if T i has the property that no machine running in time b, outputs a deceptive pair ((M, s1 , s2 ), p) with probability 12 over the random strings r0 , . . . , ri , then no machine running in time α2 b/k c2 outputs a deceptive pair for the machine Ti+1 with probability α, over the random strings r0 , . . . , ri+1 . Proof. This result is a straightforward consequence of the knowledge extraction property of the proofs in Definition 6. Assume we have a machine P that outputs deceptive pairs (x = (M, s1 , s3 ), p ) for Ti+1 with probability α (over r) in time α c2 2 b/k . We apply the extractor EP , and have by definition that EP (Ti+1 , x) returns a classical witness w (relative to ri+1 ) with probability at least 1/2 in time at most b/2. The witness w is a classical witness for (Ti+1 , x) in the language L, and thus (by the definition of Ti+1 ) w may be interpreted as w = (p1 , p2 , s2 ). Further, since w is a classical witness, both the proofs p1 and p2 are accepted by the verifier. However, since p is deceptive, at least one of p1 , p2 must be deceptive (with respect to T, ri ). In time 2i + k ≤ b/2 we can classically check which one of p1 , p2 is deceptive, by simply simulating M for 2i steps on s1 comparing the current state against s2 , and reporting “p1 ” if they agree, “p2 ” if they do not. Thus using b/2 + b/2 = b time we have recovered a deceptive pair for Ti with probability at least 1/2, contradicting our assumption.
Applying Lemma 1 inductively starting from b = K , letting α = i − 1 iterations and α = for the last yields:
1 2
for the first
Lemma 2. No machine running in time 2K /(4k c2 )i outputs a deceptive pair for the machine Ti with probability , over the random strings r0 , . . . , ri . 3.2
The Main Result
Theorem 1. Given a noninteractive CS proof of knowledge (P, U, K , c, c1 , c2 ), there exists an incrementally verifiable computation scheme (C, V, K) provided Kk 2 log k+c2 log K ≤ K . Proof. Making use of the CS proof of knowledge, Construction 2 describes a recursive procedure for generating a proof for 2i steps of the computation using i levels of a binary recursion. Consider the tree that such a recursion would
Incrementally Verifiable Computation
11
induce. The leaves of the recursive tree are the memory configurations of M , and the internal nodes j levels above the leaves are proofs of knowledge of recursive depth j (by way of machine Tj ) asserting the results of simulating M for 2j steps. Each node is computable in time polynomial in k from its two children, as this requires just one application of the polynomial-time prover P . Let C(M ) be a machine that performs a depth-first traversal of the binary tree, starting at the leaf corresponding to time 0, visiting each leaf in order, and computing the value of every node it visits. At any moment in such a traversal the “stack” consists of the values of nodes on a path from a leaf to the root. Every time a leaf is visited, let C(M ) output the values of all the nodes along this path as a proof of incremental correctness. We note that processing any node takes time polynomial in k, and the depth of the recursion is less than k, and so a leaf is visited every k O(1) time. Thus this procedure uses the desired time and space. We now show that these “stack dumps” in fact constitute computationallysound proofs. Consider a subtree whose leaves consist of a range [t1 , t2 ]. (If the subtree has depth j then t1 and t2 will be consecutive multiples of 2j .) When the recursion finishes processing this subtree, it will store in the parent node parameters x = (M, s1 , s2 ) and a proof of knowledge that M when starting in configuration s1 reaches configuration s2 in time t2 − t1 . We note that when the recursion processes leaf t it must have finished processing all the leaves before t , and thus the leaves spanned by those subtrees in the “stack” must constitute all the leaves before t . Thus these proofs of knowledge, when considered together, assert the complete result of simulating M from time 0 to time t . To check such a sequence of proofs, V verifies their individual correctness, and checks that the start and end memory states for each of the corresponding “theorems” match up. We note, as above, that if such a sequence of proofs is deceptive, then we can (classically) isolate the deceptive proof using O(t) additional time by simulating M . From Lemma 2 with = k − log k , the probability that this incrementally verifiable computation scheme fools the verifier is negligible in k provided the time to execute of C(M ) plus the additional O(t) classical verification time is at most 2k − log k K /(4k c2 )log t . We note that C(M ) consists essentially of constructing t CS proofs, each of which takes time k O(1) < k log k . Thus (C, V, K) is an incrementally verifiable computation scheme for computations of length t ≤ K provided Kk log k ≤ k −(log k)−c2 log K K . Rearranging terms yields the desired result.
4
CS Proofs of Knowledge in the Random Oracle Model
To explicitly introduce CS proofs of knowledge, and support our hypothesis that there exist noninteractive CS proofs of knowledge in the common reference string model we provide details of such proofs in the random oracle model.
12
P. Valiant
Specifically, our construction will satisfy Definition 6 modified by replacing the string r everywhere with access to an oracle R. The construction of the proofs is based closely on the constructions of Kilian and Micali[12,13]. The construction of the witness extractor is inspired by a construction of Pass[14]. 4.1
Witness-Extractable PCPs
One of the Principal tools in the construction of CS proofs is the probabilistically checkable proof (PCP)[1,2]. The PCP theorem states that any witness w for a string x in a language in NP can be encoded into a probabilistically checkable witness, specifically, a witness of length n can be encoded into a PCP of length n · (log n)O(1) with an induced probabilistic scheme (based on x) for testing O(1) bits of the encoding such that: – For any proof generated from a valid witness the test succeeds. – For any x for which no witness exists the test fails with probability at least 23 . In practice, the test is run repeatedly to reduce the error probability from 13 to something negligible in n. In addition to the above properties of PCPs, we require one additional property that is part of the folklore of PCPs but rarely appears explicitly: Definition 7 (Witness Extracting PCP). A PCP is witness-extracting with radius γ if there exists a polynomial time algorithm W that, given any string s on which the PCP test succeeds with probability at least 1 − γ, extracts an NP witness w for x. We sketch briefly how this additional property can be attained. Consider the related notion of a PCP of proximity (PCPP)[5]: Definition 8 (Probabilistically checkable proof of proximity). A pair of machines (P, V ) are a PCPP for the NP relation L = {(x, w)} with proximity parameter if – When (x, w) ∈ L the verifier accepts the proof output by the prover: P rob[V (P (x, w), (x, w)) = 1] = 1. – If for some x, w is -far from any w such that (x, w ) ∈ L, then the verifier will reject any proof π with high probability: P rob[V (π, (x, w)) = 1] <
1 . 3
We note that this property is stronger than the standard PCP property since in addition to rejecting if no witness exists, the verifier also rejects if the prover tries to significantly deceive him about the witness. Ben-Sasson et al. showed the existence of PCPPs with O(1) queries and length n · (log n)O(1) [5]. We use these PCPPs to construct witness-extractable PCPs:
Incrementally Verifiable Computation
13
Construction 3. Let R be an error-correcting code of constant rate that can correct fraction of errors, with the PCPP parameter as above. Let L = {(x, w)} be the NP relation for which we wish to find a witness-extractable PCP. Modify L using the code R to obtain a relation L = {(x, R(w)) : (x, w) ∈ L}. Let P be a PCPP prover for this relation. The verifier for this proof system is just the PCPP verifier for L , which expects inputs of the form (P (x, R(w)), (x, R(w))). Let the witness extractor W for the proof system run the decoding algorithm on the portion of its input corresponding to R(w) and report the result. Claim. Construction 3 is a witness-extractable PCP with quasilinear expansion, where the verifier reads only a constant number of bits from the proof. Proof. We note that since R is a constant-rate code and P expands input lengths quasilinearly, this scheme also has quasilinear expansion. Since the PCPP system reads only O(1) bits of the proof, this new system does too. For any pair (x, w) ∈ L the proof generated will be accepted by the verifier, so this scheme satisfies the first property of PCPs. If x is such that no valid w exists for the L relation, then no valid R(w) exists under the L relation and the verifier will fail with probability at least 23 , as required by the second property of PCPs. Finally, to show the witness extractability property we note that by definition of a PCPP, if the verifier succeeds with probability greater than 13 on (π, (x, s)) then s is within relative distance from the encoding of a valid witness R(w). Since the code R can correct fraction errors, we apply the decoding algorithm to s to recover a fully correct witness w. We have thus constructed a witnessextractable PCP for γ = 23 .
4.2
CS Proof Construction
We now outline the construction of noninteractive CS proofs of knowledge, which is essentially the CS proof construction of Kilian and Micali[12,13]. We present the knowledge extraction construction in the next section. The main idea of this CS proof construction is for the prover to construct a (witness-extractable) PCP, choose random queries, simulate the verifier on this PCP and queries, and send only the results of these queries to the real verifier, along with convincing evidence that the queries were chosen randomly and independent of the chosen PCP. For security parameter k (we differentiate from the parameter k used in the non-oracle-based definitions.) the prover sends only data related to k runs of the PCP verifier, and thus the length of the proof essentially depends only on the security parameter k .
14
P. Valiant
The technical challenge in the construction is to convince the verifier that the queries to the PCP are independent of the PCP. To accomplish this we use a random oracle. Let denote the set of functions
R : {0, 1}2k → {0, 1}k . By a random oracle we mean a function R drawn uniformly at random from the set . The machines in our construction will have oracle access to such an R. We start by defining a Merkle hash:
Definition 9 (Merkle hash). Given a string s and a function R : {0, 1}2k → {0, 1}k , do the following: – Partition s into chunks of length k , padding out the last chunk with zeros. – Let each chunk be a leaf of a full binary tree of minimum depth. – Filling up from the leaves, for each pair of siblings s0 , s1 , assign to their parent the string R(s0 , s1 ). To aid in the notation we define a verification path in a tree: Definition 10 (Verification path). For any leaf in a full binary tree, its verification path consists of all the nodes on the path from this node to the root, along with each such node’s sibling. The construction of CS proofs is as follows: Construction 4. Given a security parameter k , a polynomial-time relation L = {(x, w)} with |w| < 2k and a corresponding witness-extractable PCP with prover and verifier P P, P V respectively, we construct a CS prover P and verifier U . P on input (x, w) and a function R : {0, 1}2k → {0, 1}k does the following: 1. Run the PCP prover to produce s = P P (x, w). 2. Compute the Merkle hash tree of s, letting sr denote the root. 3. Using R and sr as a seed, compute enough random bits to run the PCP verifier P V k times. 4. Run P V k times with these random strings; let the CS proof P R (x, w) consist of the k ·O(1) leaves accessed here, along with their complete verification pathways. U on input x, a purported proof π and a function R does the following: 1. Check for consistency of the verification pathways, i.e. for each pair of claimed children (s0 , s1 ) verify that R(s0 , s1 ) equals the claimed parent. 2. From the claimed root sr run the procedure in steps 3 and 4 of the construction of P , failing if the procedure asks for a leaf from the tree that does not have a verification pathway. 3. Accept if both steps succeed, otherwise reject. These are essentially the CS proofs of Killian and Micali. In the next section we exhibit the knowledge extraction property of these proofs, and thereby infer their soundness; further properties and applications may be found in the original papers.
Incrementally Verifiable Computation
4.3
15
Knowledge Extraction
We now turn to new part of this construction, the knowledge extractor from part 5 of Definition 6. We construct a black-box extractor, that is, a fixed E that takes a description of the machine P as an input argument, instead of depending arbitrarily on P . Recall that we want to construct a machine E that when given a (possibly deceptive) prover P will efficiently extract a witness w for any x on which P r[U R (P R (x), x) = 1] > 1/K . In other words, if P reliably constructs a proof for a given x, then there is a witness “hidden” inside P , and E can extract one. The general idea of our construction is to simulate P R (x) while noting each oracle call and response, construct all possible Merkle trees that P could have “in mind”, figure out based on the output of P which Merkle tree it finally chose, read off the PCP at the leaves of the tree, and use the PCP’s witness extraction property to reveal a witness. We note that this extractor is slightly unusual in that it does not “rewind” the computation at any stage, but merely examines the oracle calls P makes; such extractors have been recently brought to light in other contexts under the names straight-line extractors[14] or online extractors[9]. The principal reason we need such an extractor is that we require the extractor to run in time linear in the time of P , up to multiplicative constant k c2 , and we cannot afford the time needed to match up data from multiple runs. We show that the following extractor fails with negligible probability on the set of R where P R (x) is accepted by the verifier; to obtain an extractor that never fails, we re-run the extractor until it succeeds. Construction 5 (CS extractor). Simulate P R (x), and let q1 , ..., qt be the queries P makes to R, in the order in which they are made, duplicates omitted. Assemble {qi } and separately {R(qi )} into data structures that can be queried in time logarithmic in their sizes, log t in this case. If for some i = j R(qi ) = R(qj ), or if for some i ≤ j qi = R(qj ), then abort. Consider {qi } as the nodes of a graph, initially with no edges. For any qi whose first k bits equal some R(qj ) and whose second k bits equal some R(ql ), draw the directed edges from qi to both qj and ql . In the proof output by P R (x) find the string at the root, sr . If sr does not equal R(qr ) for some r, then abort. If the verification paths from the proof are not embedded in the tree rooted at qr , abort. Compute from x the depth of the Merkle tree one would obtain from a PCP derived from a witness for x. (Recall that for the language Lc in Definition 5, witnesses have length identical to that of x; in general we could pad witnesses to a prescribed length.) Read off from the tree rooted at qr all strings of this depth from the root; where strings are missing fill in 02k instead. Denote this string by pcp. Apply the PCP witness extractor to pcp, and output the result.
16
P. Valiant
Lemma 3. Construction 5 when given (P , x) such that P R (x) always runs in time at most 2k /4 and that convinces the verifier with probability P rR [U R (P R (x), x) = 1] = α > 2−k /8 , will return a witness w for x on all but a negligible fraction of those R on which P convinces the verifier in time O(k/α) times the expected running time of P . Proof. We show that this construction fails with negligible probability. We begin by showing that the probability of aborting is negligible. Suppose P has already made i − 1 queries to the oracle, and is just about to query R(qi ). This value is uniformly random and independent of the view of P at this point, so thus the probability that R(qi ) equals any of qj or R(qj ) for j < i is at most 2i · 2−k . The probability that this occurs for any i ≤ t is thus at most t2 2−k , which bounds the probability that the extractor aborts in the first half of the extractor. We note that since no two qi ’s hash to the same value, the trees will be constructed without collisions, and since qi = R(qj ) for i ≤ j, the graph will be acyclic and thus a valid binary tree. We may now bound the probability that some node on a verification path (including possibly the root) does not lie in the graph we have constructed. Let s0 , s1 be a pair of siblings on a verification pathway for which the concatenation (R(s0 ), R(s1 )) is not in the graph. Thus P does not ever query R(R(s0 ), R(s1 )). Since the proof P generates is accepted by the verifier, the value of R(R(s0 ), R(s1 )) must be on the verification path output by P . Thus P must have guessed this value without evaluating it, and further, the guess must have been right. This occurs with probability at most 2−k . Thus the total probability of aborting is at most (t2 + 1)2−k . We now show that if the extractor does not abort, it extracts a valid witness on all but a negligible fraction of R’s. Recall that the CS verifier makes k calls to the PCP verifier, each of which, if seeded randomly, fails with probability 23 whenever the string pcp does not encode a valid witness w. Consider for some non-aborting R and some i ≤ t the distribution ρ on R obtained by fixing those values of R that P R (x) learns in its first i oracle calls, and letting the values of R on the remaining inputs be distributed independently at random. Consider an R drawn from the distribution ρ. Construct a Merkle tree from the values {(qj , R(qj )) : j ≤ i} rooted at qi , i.e., pretending that P , when it finishes, will output R(qi ) as the root, and let pcp be the string read off from the leaves, as in the construction of the extractor. Compute from R and R(qi ) as in step 3 of the construction of the CS prover P the k sets of queries to the PCP verifier. Unless the oracle calls generated here collide with the i previous calls, the PCP queries will be independent and uniformly generated; if witness extraction fails on pcp then by definition, these PCP tests will succeed k with probability at most 13 . Adding in the at most t2 2−k chance that, under this distribution, one of the new oracle calls will collide with one of the old calls, the total probability that pcp is not witness-extractable, yet the tests succeed, is at most (t2 + 1)2−k . Consider all distributions ρ with i fixed values as above. We note that the distributions have disjoint support, since no fixed R could give rise to two different
Incrementally Verifiable Computation
17
initial sequences of oracle calls. We note also that any R either aborts or induces such a distribution ρ with i fixed values. We now vary i from 1 to t. Consider the set of non-aborting R for which there is some i such that the string pcpR i is not witness-extractable yet the PCP tests generated by R all succeed. By the above arguments and the union bound this set has density at most
t(t2 + 1)2−k . By assumption the set of R for which the verifier accepts P R (x) has density at least 2−k /8 . Thus for all but a negligible fraction of these R, the string pcp is witness-extractable, and we may recover a witness w as desired.
We note that our extractor runs logarithmic factor slower than P . Since the running time of P is subexponential in k, the extractor takes time o(k) more than P . As noted above, if P returns an acceptable proof with probability α we may have to run the extractor 1/α times (in expectation) before it returns a witness. Since by the above construction α ∼ 1, our extractor runs k times slower than P and always returns acceptable proofs, as desired.
Acknowledgements I am indebted to Silvio Micali for introducing me to the area of CS proofs and for many invaluable discussions along the way to writing this paper. I am grateful to Ran Canetti, Brendan Juba, and Rafael Pass for their many helpful comments on earlier versions of this paper. I would also like to thank the anonymous referees for their suggestions; those mistakes that remain are my own, and likely due to lack of understanding of what the referees were recommending.
References 1. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. Journal of the ACM 45(3), 501–555 (1998) 2. Arora, S., Safra, S.: Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM 45(1), 70–122 (1998) 3. Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has twoprover interactive protocols. Computational Complexity 1, 3–40 (1991) 4. Barak, B., Goldreich, O.: Universal Arguments. In: Proc. Complexity (CCC) (2002) 5. Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, shorter PCPs and applications to coding. In: STOC 2004, pp. 1–10 (2004) 6. Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive Zero-Knowledge. SIAM J. Comput. 20(6), 1084–1118 (1991) 7. Blum, M., Feldman, P., Micali, S.: Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In: STOC 1988, pp. 103–112 (1988) 8. Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited. In: STOC 1998, pp. 209–218 (1998)
18
P. Valiant
9. Fischlin, M.: Communication-efficient non-interactive proofs of knowledge with online extractors. Advances in Cryptology (2005) 10. Goldreich, O., Sudan, M.: Locally testable codes and PCPs of almost-linear length. In: FOCS 2002 (2002) 11. Goldwasser, S., Micali, S., Rackoff, C.: The Knowledge Complexity of Interactive Proof Systems. SIAM J. on Computing 18(1), 186–208 (1989) 12. Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC, pp. 723–732 (1992) 13. Micali, S.: Computationally Sound Proofs. SIAM J. Computing 30(4), 1253–1298 (2000) 14. Pass, R.: On deniability in the common reference string and random oracle model. In: Advances in Cryptology, pp. 316–337 (2003) 15. Shamir, A.: IP = PSPACE. Journal of the ACM 39(4), 869–877 (1992)
On Seed-Incompressible Functions Shai Halevi1 , Steven Myers2 , and Charles Rackoff3 1 IBM Research
[email protected] 2 Indiana University
[email protected] 3 University of Toronto
[email protected]
Abstract. We investigate a new notion of security for “cryptographic functions” that we term seed incompressibility (SI). We argue that this notion captures some of the intuition for the alleged security of constructions in the random-oracle model, and indeed we show that seed incompressibility suffices for some applications of the random oracle methodology. Very roughly, a function family fs (·) with |s| = n is seed incompressible if given (say) n/2 bits of advice (that can depend on the seed s) and an oracle access to fs (·), an adversary cannot “break fs (·)” any better than given only oracle access to fs (·) and no advice. The strength of this notion depends on what we mean by “breaking fs (·)”. We first show that for any family fs there exists an adversary that can distinguish fs (·) from a random function using n/2 bits of advice, so seed incompressible pseudo-random functions do not exist. Then we consider the weaker notion of seed-incompressible correlation intractability. We show that although the negative results can be partially extended also to this weaker notion, they cannot rule it out altogether. More importantly, the settings that we cannot rule out still suffice for many applications. In particular, we show that they suffice for constructing collision-resistant hash functions and for removing interaction from Σprotocols (3-round honest verifier zero-knowledge protocols).
1
Introduction
Identifying useful security notions of “cryptographic functions” was proposed ten years ago by Canetti [4], as a plausible way of putting random-oracle-based constructions on a firmer theoretical footing. The challenge is to find specific “random-oracle-like” properties, such that functions with these properties (a) can be realized in the standard model and (b) can be securely used in some cryptographic applications in lieu of access to a truly random function. However, very little progress along this line has been made since then, in fact the only nonobvious notion along this line that we know of is the “perfect one-way hashing” notion of Canetti [4,7]. In this work we study a very different security notion that we term seed incompressibility. On a very high level, this notion is meant to capture the intuition R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 19–36, 2008. c International Association for Cryptologic Research 2008
20
S. Halevi, S. Myers, and C. Rackoff
that a random function has no structure. At a first glance, it seems hopeless to define an efficiently computable function that has no structure, since the fact that the function is computed by a small circuit is itself some structure. However, we may still hope that this small circuit is the only interesting “small property” of the function. That is, no adversary can find a significantly smaller property that differentiates it from your average random function. Roughly, if you do not get enough bits to describe the entire function, then you get nothing. Toward formalizing this intuition, let F = {fs }s be a family of functions with n-bit seeds, and consider an adversary that works in two phases: In the first phase the adversary gets the n-bit seed s, compresses it to (say) an n/2-bit string σ, and keeps only σ in memory. Then the adversary gets an oracle access to the function fs (·), and it tries to “break it” (according to some notion of security). We call this the seed compression attack model. We say that the family F satisfies the underlying notion of security under seed-compression attack (or that it is seed incompressible with respect to the underlying notion of security), if breaking the function knowing σ is not any easier than breaking it without knowing σ.1 The choice of n/2 as the compression threshold is quite arbitrary. The results that we present in this paper remain unchanged whenever the threshold for the length of the compressed seed is anywhere from n to n − n for any fixed 0 < < 1. Below we stick to the n/2 threshold for convenience. Following the intuition from above, we would have liked a construction where it is not possible to distinguish fs from a random function, even given σ. Some care must be taken when defining this notion to avoid obvious pitfalls (such as σ being the first n/2 bits of fs (0)), but this can be handled using ideas similar to the ones of Coron et al. [9] (see details in Section 3). Unfortunately, even with these ideas we show that the resulting notion cannot be realized, namely no function family can be pseudo-random under seed-compression attacks. Roughly, the reason is that the adversary can encode in σ a CS-proof [21] for the statement that fs is computed by a small circuit. This impossibility result is somewhat disheartening, as it does not really show the existence of some property of the function that is smaller than its description; rather, it is simply a fact that convincing someone that a function has a small circuit takes much fewer bits than actually telling them what the circuit is. Further, from a security perspective the fact that the function is being computed by a small circuit is clearly information that the adversary knows. Faced with this negative result, we investigate weaker notions of security. One direction that seems promising is the notion of correlation-intractability under seed-compression attacks. The notion of correlation-intractability was defined by Canetti et al. [6] as the inability of the attacker to find any input x such that the pair (x, fs (x)) satisfies any “non-trivial relation” (cf. Section 4). Canetti et al. proved that correlation-intractability is not realizable when the adversary sees the entire seed s, but we point out that it may be realizable when the adversary is only given the “compressed seed” σ. We note that the negative 1
Of course, this is only meaningful if “breaking fs ” is hard without any knowledge of the seed s.
On Seed-Incompressible Functions
21
results from [6] do not seem to extend to this model. On the other hand, our negative results for PRFs can be partially extended also to this weaker notion. However, it seems that these negative results hit an inherent limitation for some parameter settings, and we show in Section 4 that the remaining parameter settings are still useful. For example, we show that we can use them to construct collision-resistant hash functions, and perhaps more interestingly that we can use them to remove interaction from three-move public-coin honest-verifier zeroknowledge proofs. Briefly, the primitives that can be constructed from seed-incompressible functions are those for which a “break” can be encoded with only a few bits. (For example, one can encode a collision in a hash function using only two inputs to the function.) When constructing such primitives from seed-incompressible functions, we let the seed of the function be sufficiently longer than the number of bits that are needed to encode a break, and then any adversary that breaks the resulting primitive can be converted into a “compressor” (that given the seed outputs a break), thus violating the seed-incompressibility of the underlying function. We unfortunately were not able to find a construction that provably achieves seed-incompressible correlation intractability under a better-known computational hardness assumption. Still, one can conjecture that ad-hoc constructions such as AES or HMAC-SHA1 have this property. Such a conjecture is theoretically more appealing than using the random-oracle model since, at the very least, we do not have a proof that it is false, while still providing a conjecture open to disproof. We explain below our intuition for why one might conjecture that AES and SHA type constructions satisfy our definitions. 1.1
Seed-Incompressibility and Contemporary Block-Ciphers
Here is one way to use the intuition behind DES and AES like block-cipher constructions to possibly construct seed-incompressible functions. We will use AES to denote any similar composition-of-round based block-cipher construction. Each AES function is expressed as the composition of r rounds of permutations pk1 ◦ ... ◦ pkr , where each n-bit ki is determined by the key. For this theoretical presentation, instead, we assume that all the “round keys” ki are chosen randomly and independently. Consider now using not r rounds but nr (independent) rounds. It seems unlikely that a key of this new construction can be “compressed” to only (say) n/2 bits. The intuition (at least for the case where the compressed seed consists of actual key bits), is that if the compressed seed is so short then there must be r consecutive rounds for which the key is completely undetermined, which in some intuitive sense is as strong as a standard r-round construction of an AES like construction. One issue for block-cipher like constructions is their invertibility, but by choosing a compressed seed of only n/2 bits, then it is not enough to help inverting the AES function. For example giving n/2 bits from the pre-image of zero does not appear to help when the AES permutation is mapping over an n-bit domain.
22
1.2
S. Halevi, S. Myers, and C. Rackoff
Related Work
The Random-Oracle Model. Following the Fiat-Shamir heuristic for transforming public-coin identification protocols into signature schemes [14] and several other uses of random-oracles in the literature, although sometimes used in different contexts (e.g., [18]), Bellare and Rogaway formalized the random-oracle heuristic as a “general-purpose” design methodology for cryptographic schemes [2] and emphasized the need to develop formal proofs of security within it. The methodology requires that one first design an ideal system in which all parties (including the adversary) have oracle access to a truly random function and prove the security of this ideal system. (The proof is called “a security proof in the random-oracle model.”) Next, one replaces the random oracle by a “cryptographic hash function” (such as SHA), where all parties (including the adversary) have a succinct description of this function. Thus, one obtains an implementation of the ideal system in a “real-world” where random oracles do not exist. The random-oracle methodology has been used quite extensively since then, often resulting in very efficient and seemingly secure schemes. A drawback of this methodology, however, is that it is not at all clear what security properties are needed from the cryptographic hash function in order for a specific scheme to be secure. In fact, Canetti et al. demonstrated that this methodology is not sound in general, in that there exist secure “ideal schemes” that have no secure implementation in the “real world” [6]. A similar negative result was later proved by Goldwasser and Kalai also for the original Fiat-Shamir heuristic [16]. Still, there are many cryptographic schemes whose only known security proof is in the random-oracle model, some of which withstood substantial cryptanalysis and are widely implemented and deployed. Seeking to provide some theoretical footing to the security of such schemes, we would like to be able to describe “random-oracle like” properties that are (a) well-defined, (b) realizable, and (c) sufficient for the security of some instances of the random-oracle methodology. As we mentioned above, a first step in this direction was taken a decade ago by Canetti et al. with the notion of perfect one-way hashing [4,7]. With respect to the realizability of such notion, one thing that we could have hoped for is to prove its existence based on a more standard cryptographic assumption (e.g., the hardness of factoring). We point out, however, that at least as important is that there will be some hope (or intuition) that typical cryptographic functions such as SHA or AES actually fulfill this notion (as it is these functions that are used in actual implementations of protocols proven correct in the Random Oracle model). Conditional Entropy Hash Functions. Barak et al. [1] conjectured the existence of families of hash functions hs for which no attacker can generate an input that has a predictable output. Specifically, a keyed function hs (x) is said to “ensure conditional entropy e” if for every attacker A that takes as input the key s and produces as output an input x to h, it holds that the conditional entropy H(hs (A(s))|A(s)) ≥ e. This notion appears to be very close to the notion of
On Seed-Incompressible Functions
23
correlation intractable functions of [6] (since if hs (x) has “high entropy” then it is unlikely to hit any evasive relation). Barak et al. show that such functions are sufficient to implement the Fiat-Shamir heuristic to Σ-protocols, as is done herein with seed incompressible functions. (This result from [1] casts doubt on the informal claim made in [6] that correlation intractability was insufficient for such constructions.) Yet, other than via the connection to correlation-intractability, their notion seems unrelated to seed-incompressibility. For example, we do not see a obvious way in which conditional entropy hashes imply collision-resistance, as we show seedincompressibility does in Section 5.1. Exposure-Resilient Functions. The notion that we investigate in this work can be seen as an enhancement of exposure-resilient functions (ERFs) as defined and constructed by Canetti et al. [5]. Recall that an ERF is a function whose output looks random even when some of the input bits are known. It is easy to see that if we restrict the seed compression attack to only output some of the bits of the seed, then a “seed incompressible PRF” can be constructed from an ERF and a standard PRF (by first applying the exposure-resilient function to the seed). The Bounded-Retrieval Model. Our seed-compression attack model can also be seen as an instance of the “bounded-retrieval model” that was introduced by Dziembowski and by Di Crescenzo et al. [13,11]. In this model, an adversary installs a virus on a target machine; the virus can observe all the secrets on the target machine, but only has a limited available bandwidth with which to communicate these secrets back to its “home base”. The works of Dziembowski, Di Crescenzo et al. and Cash et al. [13,11,8] investigate obtaining secure keyexchange and authentication protocols in this model. The current work can be thought of as trying to obtain primitives similar to pseudo-randomness in the same setting. (However, our focus is quite different, we view this model merely as a tool in order to establish primitives that can be used in other more standard models.) Compressibility of NP Languages. A different notion of “compressibility” with applications to cryptography was recently proposed by Harnik and Naor [17]. In their notion, we are given an NP language and a word that is potentially in that language, and we try to produce a shorter word that is in the language if and only if the original is. For example, we are given a CNF formula φ and we try to compress it to a shorter φ such that φ is satisfiable if and only if φ is.2 Harnik and Naor proved that if SAT is compressible then collision-resistant hashing can be constructed from one-way functions. Our notion of compression seems quite different from the one of Harnik and Naor: roughly the difference is that they consider compressing the instance, whereas we are interested in compression of the witness (i.e., the secret seed of the function in our case). 2
The length of φ should be poly-logarithmic in the length of φ, but can be polynomial in the number of variables of φ.
24
2
S. Halevi, S. Myers, and C. Rackoff
Notations and CS Proofs
Notations. We define some notation used throughout the paper. Given a bit b, we use b to denote the bit-string of bits b. Concatenation of bit strings is denoted with ||. Given an bit-string s = s1 , ..., s and c ≤ we denote its first c significant bits s1 , ..., sc by sc . We use a ∈R S to denote choosing uniformly at random an element a from a set S. We use negl(n) to denote some function f , such that for all c and sufficiently large n f (n) ≤ 1/nc and poly(n) denotes some polynomial function p ∈ O(nd ) for some constant d. CS Proofs. Our negative results use CS-proofs as constructed by Micali [20] (using techniques from Kilian [19]), as well as a variant of them due to Naor and Nissim [22]. Below, we briefly recall the definition. For our purposes, we view a CS-proof system as consisting of a prover, Prv, that wants to convince a verifier, Ver, of the validity of an assertion x ∈ L where L is some NP-language and Prv is in possession of a witness w for x.3 In our context, we use non-interactive CS-proofs that work in the Random Oracle Model; that is, both the prover and verifier have access to a common random oracle. The prover generates an alleged proof that is examined by the verifier. Definition 1 (Non-interactive CS proofs in the Random Oracle Model). A CS-proof system for a language L ∈ N P (with relation RL ), consists of two deterministic polynomial-time oracle machines, a prover Prv and a verifier Ver, operating as follows: – On input (1k , x, w) such that (x, w) ∈ RL and access to an oracle O, the prover computes a proof π = PrvO (1k , x, w) such that |π| ≤ poly(k, log(|x| + |w|)). – On input (1k , x, π) and access to O, the verifier decides whether to accept or reject the proof π (i.e., VerO (1k , x, π) ∈ {accept, reject}). The proof system satisfies the following conditions, where the probabilities are taken over the random choice of the oracle O: Perfect completeness: For any (x, w) ∈ RL and for any k, Pr π ← PrvO (1k , x, w), VerO (1k , x, π) = accept = 1. O
Computational soundness: For any polynomial time oracle machine Bad and any input x ∈ / L it holds that Pr π ← BadO (1k , x), VerO (1k , x, π) = accept ≤ negl(k). O
We sometimes also require a stronger soundness condition by replacing the neg. (This ligible function negl(k) with an exponentially small function poly(k+|x|) 2k stronger condition can still be proven in the random-oracle model.) 3
Micali defined CS-proofs more generally, but we do not need this extra generality for our purposes.
On Seed-Incompressible Functions
3
25
Seed-Incompressible Pseudo-random Functions
Following the intuition as presented in the introduction, we would have liked to have a construction F = {fs } such that fs looks random even when given a “compressed version of s.” Formalizing this takes some care, since this “compressed version of s” could be, for example, the first |s|/2 bits of fs (0) (which would make it easy to distinguish fs from an unrelated random function). This technicality can be solved by borrowing the technique used by Coron et al. (in the context of domain extenders for random oracles) [9]. Namely, the second phase of the adversary gets either the compressed seed σ and access to fs (·), or access to a random function f (·) and a “simulated compressed seed” that was generated by a simulator S f (where S has access to the same random f ). In the formal definition below, we fix some polynomially-bounded length functions 1 , 2 and consider function families from 1 (n) bits to 2 (n) bits with n-bit seeds. We denote by Fn the set of all functions f : {0, 1}1 (n) → {0, 1}2(n) . Definition 2 (Seed-Incompressible PRFs). Let {Fn }n∈N be a family of functions such that Fn : {0, 1}n × {0, 1}1(n) → {0, 1}2(n) can be efficiently computed, and denote fs (·) ≡ F (s, ·). The family {Fn } is pseudo-random under seed-compression attacks if for every two-phase efficient adversary Adv = (A, B) there exists an efficient simulator S and a negligible function negl such that Pr s ∈ {0, 1}n , σ ← A(s) : |σ| ≤ n/2 and B fs (σ) = 1 R ≤ negl(n) − Pr f ∈R Fn , σ ← S f (1n ) : |σ| ≤ n/2 and B f (σ) = 1 Seed-Incompressible PRFs would have been very useful, but unfortunately they do not exist, as will be shown below. While we show that SI-PRFs do not exist, a related concept will be introduced later, and therefore the discussion is useful for this later topic. Theorem 1. Seed-Incompressible PRFs as defined in Definition 2 do not exist. Proof. Let {Fn }n∈N be a family of functions as in Definition 2. We show a twophase adversary Adv = (A, B) for which no simulator exists. Fix some n and let 1 = 1 (n) and 2 = 2 (n). Let j = 2n/2 (i.e., the output of fs on 1, 2, . . . , j contains at least 2n bits). The first phase of the adversary, A, gets as input a seed s ∈ {0, 1}n. It computes yi = fs (0||i) for i = 1, 2, . . . , j, and then prepares a CS-proof π for the true NP statement “there exists a seed s such that yi = fs (0||i) for i = 1, 2, . . . , j”
()
The proof √ is prepared relative to the oracle O(·) = fs (1||·) and security parameter k = n. Then A outputs the proof π as the “compressed seed”, to be used by the second phase B. (Notice that the length of this proof is k·polylog(n) < n/2.) The second phase B, on input π, first uses its oracle f to compute yi = f (0||i) for i = 1, 2, . . . , j, thereby recovering the statement that π is supposed to be a
26
S. Halevi, S. Myers, and C. Rackoff
CS-proof for. Then B attempts to verify the proof π√relative to f (1||·) (where f is the provided oracle) and security parameter k = n. It accepts if the proof is valid and rejects otherwise. By the perfect completeness of CS-proofs, B accepts with probability one when given the proof that A generated and access to the same fs for which that proof was generated. On the other hand, the soundness of CS-proofs implies that no simulator can make B accept with non-negligible probability. Indeed, when f is a random function in Fn then y1 , . . . , yj consist of at least 2n random bits, hence the probability that the statement () from above is true is at most 2−n . And if the statement is not true, then no efficient simulator with access to a random f can generate a valid proof for it with probability better than poly(n) · 2−Θ(k) = negl(n).
4
Seed-Incompressible Correlation Intractability
Canetti et al. [6] introduced the concept of Correlation Intractability to capture the intuition that the adversary cannot “hit” any rare input-output relation. Roughly, an evasive relation R is one where it is hard to find an input x such that (x, f (x)) ∈ R for a random function f , and a function family F is correlation intractable if for any evasive relation R it is hard to find (x, f (x)) ∈ R for a random member f ∈ F . These notions can be extended to 2p-ary relations in the obvious way (see below). Canetti et al. proved that correlation-intractable function families do not exist, in that an adversary that knows the short description of f ∈ F can always find some (x, f (x)) ∈ RF for a particular relation RF that depends on F . In our case, however, we are interested in an adversary that does not see the entire description of f ∈ F but only gets a “compressed description”. We provide the formal definitions below, and then discuss the extent to which the negative results from [6] and from Section 3 do or do not extend to this new notion. Below we again fix some polynomially bounded length functions 1 , 2 , and denote by Fn the set of all functions f : {0, 1}1(n) → {0, 1}2(n) . Definition 3 (Evasive Relations). A 2p-ary relation R is evasive if for any efficient adversary A, there is a negligible function negl such that for all sufficiently large n Pr [x1 , . . . , xp ← Af (1n ) : x1 , . . . , xp , f (x1 ), . . . , f (xp ) ∈ R] ≤ negl(n).
f ∈Fn
Sometimes we are interested only in efficient relations, namely relations R for ?
which the membership problem x1 , . . . , xp , y1 , . . . , yp ∈ R can be efficiently decided (i.e., in polynomial time). Definition 4 (Seed-Incompressible Correlation Intractability) Let {Fn }n∈N be a family of functions where Fn : {0, 1}n ×{0, 1}1(n) → {0, 1}2(n) can be efficiently computed, and denote fs (·) ≡ F (s, ·).
On Seed-Incompressible Functions
27
For some polynomial p = p(n), we say that the family {Fn } is correlation intractable under seed-compression attacks with respect to 2p-ary relations if for every 2p-ary evasive relation R, and for every two-phase efficient adversary Adv = (A, B), there is a negligible function negl such that for all sufficiently large n s ∈R {0, 1}n, σ ← A(s), x1 , . . . , xp ← B fs (σ) : Pr ≤ negl(n). |σ| ≤ n/2 and x1 , . . . , xp , fs (x1 ), . . . , fs (xp ) ∈ R We also call such function families seed-incompressible correlation-intractable (with respect to 2p-ary relations), or SI-CorInt(2p), for short. In the case that we restrict the above quantification on all evasive relations to only efficient evasive relations, we say that the family {Fn } is weakly seedincompressible correlation-intractable with respect to 2p-ary relations (wSICorInt(2p)). 4.1
Do SI Correlation Intractable Functions Exist?
The first question to answer with respect to the seed-incompressible correlation intractability as defined above is whether we can extend the impossibility result from Theorem 1 (or from [6]) to show that it too cannot be realized. One first observes that for some setting of parameters, an attacker in the seed-compression model is just as powerful as an attacker that has the full uncompressed seed. Specifically, if the seed is more than 2p times the length of the input to h, then the first phase of an attacker in the seed-compression model can output the vector that breaks the correlation intractability as the “compressed seed”. However, the impossibility results from [6] do not extend to very long seeds, so this simple observation does not appear to shed new light on the existence of SI-CorInt functions. Below we show, however, that the technique from Theorem 1 can be extended for some settings of parameters: As opposed to the case of Theorem 1, here the adversary needs not only to distinguish fs from random (which can be done with CS-proofs), but also to compute some “unpredictable relation”. The idea that we exploit here is that the CS-proof itself can be thought of as an “unpredictable relation.” Roughly, we have a relation of the form ⎧ ⎫ ⎨ (1, . . . , t, v1 , . . . , vm ), (x1 , . . . , xt , y1 , . . . , ym ) : ⎬ The CS-proof (v1 , . . . , vm ) is valid for the instance (x1 = f (1), ⎩ ⎭ . . . , xt = f (t)) w.r.t. V receiving oracle answers (y1 , . . . , ym ). Tracing through the various parameters we see that to use Micali’s construction for CS-proofs with a relation such as above we need t = (n + ω(log n))/2 (n) and m = polylog(n). Hence we get an impossibility result for 2p-ary relations where p = n/2 (n) + polylog(n). Moreover, if we assume the existence of collisionresistant hashing then we can use the variant of CS-proofs with few oracle calls due to Naor and Nissim [22], and then we can get by with a relation that only depends on m = O(n/1 (n)) of the vi ’s. Hence for function families with n-bit
28
S. Halevi, S. Myers, and C. Rackoff
seeds and input/output bit lengths of size 1 (n), 2 (n) = Ω(n) we also obtain an impossibility result for 2p-ary relations where p = O(1) (we can get as low as p = 3 when 1 (n), 2 (n) > n.) Lemma 1. An efficiently computable functions family {Fn : {0, 1}n ×{0, 1}1(n) → {0, 1}2(n) } cannot be weakly correlation intractable under seed-compression attacks with respect to 2p-ary relations, for any p ≥ (n + ω(log n))/2 (n) + polylog(n)/2(n) . Moreover, if collision resistant hash function family {Hn : {0, 1}n × {0, 1}4(n) → {0, 1}5(n) } exist, for polynomials 4 (n) > 5 (n), then no family as above can be correlation intractable under seed-compression attacks with respect to 2p-ary relations where p ≥ (n + ω(log n))/2 (n) + n /2 (n) + n /1 (n) (for any > 0). A proof of this lemma will be in the full version of this paper. Smaller relations. We speculate that current techniques cannot be used to rule out relations with arity less than 6. This is because with the current technique of using CS-proofs, you would need at least one oracle call to specify the function instance, at least one oracle call for the CS-proof, and you would have to use at least one more vi to describe the CS-proof itself. Thus it is still plausible that seed-incompressible correlation intractable function families exist with respect to such low-arity relations.
5
Implications of Seed-Incompressible Correlation Intractability
We demonstrate the usefulness of seed-incompressible functions by showing how they can be used to easily construct two primitives: specifically collision-resistant hash functions and (single-theorem) NIZK systems via the Fiat-Shamir methodology. More generally, the primitives that can be constructed from seed-incompressible functions are those for which a “break” can be encoded with only a few bits. (For example, one can encode a collision in a hash function using only two inputs to the function. Similarly, for a NIZK that was derived from a 3-move Σprotocol, one can encode a false proof using only the two messages that the prover sends.) When constructing such primitives from seed-incompressible functions, we let the seed of the function be sufficiently longer than the number of bits that are needed to encode a break, and then any adversary that breaks the resulting primitive can be converted into a “compressor” (that given the seed outputs a break), thus violating the seed-incompressibility of the underlying function. 5.1
Collision Resistant Hashing
We show that seed-incompressible correlation-intractable function with respect to quaternary relations must be “essentially collision-resistant.” We view this feature as a minimal requirement for any primitive that one hopes to use in
On Seed-Incompressible Functions
29
lieu of a random-oracle, since heuristic implementations of random-oracle-based constructions always use collision-resistant hash functions such as SHA to replace the oracle. Note that it is not true that any seed-incompressible function is also collision-resistant (for example, seed-incompressible functions need not be length decreasing). Rather, we show below that any seed-incompressible function must have “embedded in it” a collision-resistant function. Specifically, given a seed-incompressible correlation-intractable function fs (·), we consider shortening the inputs and outputs of fs so that the inputs are shorter than one quarter of the seed and the outputs are shorter than the inputs. We then observe that an algorithm that finds collisions in the resulting (length-decreasing) function can be (trivially) converted to a “compressor” that breaks the seedincompressibility of fs : the “compressor” only needs to output the collision. We formally state the definition of collision-resistance for completeness and then state the theorem with proof. Definition 5 (Collision Resistant Hash Functions (CRHF)) Fix polynomially-bounded length functions 2 (n) < 1 (n). A function generator {Hn : {0, 1}n × {0, 1}1 (n) → {0, 1}2(n) }n∈N is collision resistant if for every probabilistic polynomial time adversary A there is a negligible functions negl such that for all sufficiently large n: Pr[s ← {0, 1}n, (x1 , x2 ) ← A(s) | x1 = x2 ∧ hs (x1 ) = hs (x2 )] ≤ negl(n). Theorem 2. If there exists a function family {Fn : {0, 1}n × {0, 1}1(n) → {0, 1}2(n) } with super-logarithmic length functions 1 , 2 = ω(log n), which is correlation intractable under seed-compression attacks with respect to quaternary relations, then collision resistant hash functions exist. Proof. Let 1 , 2 be super-logarithmic length functions, 1 , 2 = ω(log n), and assume that a family F = {Fn : {0, 1}n × {0, 1}1(n) → {0, 1}2 (n) }n∈N is correlation intractable under seed-compression attacks with respect to quaternary relations. Consider a modification of the family F to operate on potentially shorter inputs and outputs. Namely, let 1 = min(1 , n/4) and 2 = min(2 , 1 − 1), and consider the family H = {Hn : {0, 1}n × {0, 1}1(n) → {0, 1}2 (n) }n∈N which if defined as follows: on seed s of length n and input x of length 1 , first append zeros to x up to length of 1 bits, then apply F (s, ·) to the result, and finally take only the first 2 bits of the outcome.
H(s, x ) = F (s, x) , where x = x ||01 (|s|)−1 (|s|) . def
2
We prove that if F is SI-CorInt with respect to quaternary relations then H is collision-resistant. In particular, consider the relation R ⊂ {0, 1}1 × {0, 1}1 × {0, 1}2 × {0, 1}2 : def
R = {(x1 , x2 , y1 , y2 ) | x1 = x2 and y1 = y2 }. 2
2
30
S. Halevi, S. Myers, and C. Rackoff
This relation is clearly evasive, as every polynomial-tie adversary has probability at most poly(n) · 2−2 = negl(n) of outputting x1 , x2 for which (x1 , x2 , f (x1 ), f (x2 )) ∈ R where f is a random function (since 2 is super-logarithmic). Assume for contradiction that the family H from above is not collision resistant, and let C be a collision finding adversary that given a random s ∈ {0, 1}n outputs a pair of strings x1 , x2 ∈ {0, 1}1 such that H(s, x1 ) = H(s, x2 ) with probability at least 1/nc. Then, define the adversary Adv = (A, B) for the underlying SI-CorInt family as follows: The “compressor” A(s) simply outputs the collision (x1 , x2 ) = C(s), and note that |A(s)| = n/2. The second phase of the attack is just translate H-inputs into F -inputs by appending ze ros, namely B(x1 , x2 ) outputs (x1 , x2 ) where xi = xi ||01 −1 . By definition if H(s, x1 ) = H(s, x2 ) (which happens with non-negligible probability) then F (s, x1 ) = F (s, x2 ) , and therefore (x1 , x2 , F (s, x1 ), F (s, x2 )) ∈ R, con2 2 tradicting the security of F . 5.2
From Σ-Protocols to NIZK Arguments
One of the “signature uses” of the random-oracle heuristic is to remove interaction from zero-knowledge protocols using the Fiat-Shamir heuristic. Specifically, given a public-coin honest verifier zero-knowledge proof system (known as Σprotocols in the case where the number of rounds is three), it is possible to transform it into a non-interactive protocol by replacing the verifier’s messages with the output of a “cryptographic hash function”, applied to the transcript up to that point. It is well known that if the original protocol has negligible soundness error, then the resulting non-interactive protocol can be proven in the random-oracle model to be a non-interactive zero-knowledge argument system, and can also be used as a secure signature scheme. On the other hand, Goldwasser and Kalai proved in [16] that there exist interactive Σ-protocols with negligible soundness for which their resulting protocols are not secure signature schemes in the standard model, no matter what function family is used to replace their interaction. However, that negative result still leaves the possibility of a function family that will convert the interactive protocol into a NIZK argument system for a single theorem. Indeed, below we show that the latter is possible if seedincompressible correlation-intractable functions exist. We begin by recalling the definitions of Σ-protocols and NIZK argument systems. Below let L be an NP-language and let RL be a binary relation that defines L, namely L = {x : ∃w s.t. (x, w) ∈ RL } (where the witness w has length polynomial in |x|). Σ-Protocols. For a pair (P, V ) of interacting protocols, we denote by (P, V ) (x, w) a run in which P has input (x, w) ∈ RL , V has input x, and P attempts to convince V of the validity of the assertion x ∈ L. For a three-move protocols as above (with P going first), denote by α, β, and γ the three messages that are
On Seed-Incompressible Functions
31
exchanged in the protocol, and let P1 , and P2 be the randomized functions that the prescribed prover uses to compute its two messages, namely we have (α, state) ← P1 (x, w), and γ ← P2 (x, w, state, α, β). We also denote by V ∗ the function that the verifier employs to decide whether to accept or reject the proof, V ∗ (x, α, β, γ) ∈ {accept,reject}. Typically, the first flow α is called a commitment, the second flow β is called a challenge, and the third flow γ is called a response. Definition 6. A 3-move protocol (P, V ) as above is a Σ protocol for a language L if it satisfies the following properties: Public-coin verifier. The message β sent by V is always a sequence of t(|x|) uniformly chosen random bits (for some length function t). Perfect completeness. For every (x, w) ∈ R: Pr
(α, state) ← P1 (x, w); β ∈R {0, 1}t(|x|); γ ← P2 (x, w, state, α, β) : = 1, V ∗ (x, α,β, γ) = accept
where the probability is over the random choices of P1 , P2 and β. Soundness. There is a negligible function negl such that for every x ∈ / LR , for every pair of adversarial (computationally unlimited) prover circuits P1∗ , P2∗ :
Pr α ← P1∗ (x); β ∈R {0, 1}t(|x|); γ ← P2∗ (x, β) : V ∗ (x, α, β, γ) = acpt =
1 , 2t(|x|)
where the probability is over the random choice of β. 4 We note a property of Σ-protocols of interest to our later arguments: For every Σ-protocol, simple parallel repetition and padding arguments allow the length t(|x|) of the verifier’s challenge to be set to an arbitrary positive integer. 5 For the remainder of the paper we therefore assume that t ∈ ω(log n), and that the adversaries probability of success, as stated above, is negligible in |x|. Zero-knowledge. There exists a polynomial-time simulator S that on input x and β ∈ {0, 1}t(|x|) outputs (α , β , γ ) (we have S outputting its input β to simplify the notations somewhat). We require that for every (x, w) ∈ RL and every β ∈ {0, 1}t(|x|), the distribution on (α , β , γ ) = S(x, β ) is identical to the conditional distribution on the transcript (α, β, γ) = (P, V )(x, w), when conditioned on β = β . 4
5
Traditionally Σ-protocols are defined with a stronger soundness condition called extractability that clearly implies the current soundness definition. We refer the reader to [10] for a complete discussion on this and other properties of Σ-protocols.
32
S. Halevi, S. Myers, and C. Rackoff
NIZK Arguments. We remind the reader that the common reference string (CRS) model is one in which all participants and the adversary have access to a polynomial sized common reference string chosen by a trusted third party from a pre-specified distribution (which we denote D). Definition 7. A pair of efficient probabilistic algorithms (P, V ) are a singletheorem NIZK argument system for a language L (specified by a binary relation RL ) in the CRS model, if it satisfies: Completeness. ∀(x, w) ∈ R, Pr [σ ← P (crs, x, w) : V (crs, x, σ) = 1] = 1. crs,P,V
Computational Soundness. For every (possibly cheating) efficient probabilistic prover P ∗ there is a negligible function negl such that for all x ∈ / L: Pr [σ ← P ∗ (crs, x) : V (crs, x, σ) = 1] ≤ negl(|x|).
crs,P ∗ ,V
Zero-Knowledge. There exists an efficient simulator S such that for every (x, w) ∈ R, the output of the following two experiments are (computationally, statistically, perfectly)-indistinguishable. Exp1 (x, w) Exp2 (x) crs ← D (crs , σ ) ← S(x) σ ← P (crs, x, w) Output (crs, σ) Output (crs , σ ) The Fiat-Shamir Transformation. Fiat-and Shamir described in [14] a transformations that turns Σ-protocols into non-interactive argument systems. Specifically, instead of having the verifier choose a random challenge β, one computes β by applying a hash function to the input x and the commitment α, setting β = f (x, α). The non-interactive proof σ then consists of the elements α, γ of the Σ-protocol (i.e., the commitment and the response). Given the input x and (α, γ), the verifier computes β = f (x, α) and checks that V ∗ (x, α, β, γ) =accept. It is easy to show that when the hash function f is modeled as a random oracle then the resulting protocol is still computationally sound (since the challenge β is still a string of random bits that the adversary cannot control, other than attempting to select a polynomial number of them). Moreover, if the simulator can program the random oracle then this protocol also remains zero-knowledge. We next show that using SI-CorInt families (with respect to quaternary relations), we can construct function families for which the Fiat-Shamir transformation yields a single-theorem NIZK argument system in the CRS model. – Let (P, V ) be a Σ-protocol in which the commitment, challenge, and response are of lengths |α| = t1 (|x|), |β| = t2 (|x|), and |γ| = t3 (|x|), respectively. – Also, let {F : {0, 1}n × {0, 1}1(n) → {0, 1}2(n) }n∈N be a function family, where 1 , 2 are polynomially bounded from above and below. (That is n1/c ≤ 1 (n), 2 (n) ≤ nc for some constant c > 1 and every sufficiently large n).
On Seed-Incompressible Functions
33
For inputs of length |x| = m, we choose the security parameter n (which defined the seed-length for F ) as n = max{ 2(m + t1 (m) + t3 (m)), −1 1 (m + t1 (m)), −1 2 (t2 (m)) }. Namely, n is chosen large enough so that m + t1 (m) + t3 (m) ≤ n/2 and also 1 (n) ≥ m + t1 (m) and 2 (n) ≥ t2 (m). Note that since 1 , 2 and the ti ’s are polynomially-bounded, then n is polynomial in m. Below we view n, 1 , 2 as functions of the input length m. We then reset the input and output length to be exactly 1 = m + t1 (m) and 2 = t2 (m) by setting
F (s, x ) = F (s, x) , where x = x ||01 −1 def
2
Finally we define H : {0, 1}n+2 × {0, 1}1 → {0, 1}2 as def H(s, z , x ) = z ⊕ F (s, x ) = z ⊕ F s, x ||01 −1
2
(1)
We are now ready to describe the NIZK argument system. The CRS consists of a pair (s, z) where s ∈ {0, 1}n is a seed for the underlying function F and z is a random string of length 2 = t2 (m) (so together s, z are a seed for the function H from Eq. (1)). The NIZK argument system is obtained by applying the Fiat-Shamir transformation to the original Σ-protocol (P, V ) using the function Hs,z . Namely, on input (x, w) ∈ RL with |x| = m and crs = (s, z), the prover sets (α, state) = P1 (x, w), β = Hs,z (x, α) and γ = P2 (x, w, state, α, β). The proof is the string σ = (α, γ). Given x, crs = (s, z), and the proof σ = (α, γ), the verifier computes β = Hs,z (x, α) and checks that V ∗ (x, α, β, γ) =accept. Theorem 3. Let (P, V ) be a three round Σ-protocol for the language L, defined by the NP relation RL , and let F = {F : {0, 1}n × {0, 1}1(n) → {0, 1}2(n) }n∈N be a function family with polynomially-bounded length functions. If (P, V ) has a negligible soundness error and F is correlation intractable under seed-compression attacks with respect to quaternary relations, then applying the Fiat-Shamir transformation to (P, V ) using the function family H from Eq. (1) yields a single theorem NIZK argument system for L in the CRS model. Proof. The perfect completeness of the resulting NIZK system follows immediately from the perfect completeness of the Σ-protocol. For the zero-knowledge property, the simulator S ∗ for the NIZK system uses the simulator S given by the Σ-protocol. It first chooses a random value β ∈ {0, 1}t2(|x|) and uses S to compute S(z) = (α , β , γ ). It then chooses a random seed s ∈ {0, 1}n for the function F and computes z = β ⊕ F (s, x, α ) = β ⊕ F s, x, α ||01 −1 2
Note that by definition, we have H(s, z , x, α ) = β . The simulator S ∗ outputs the CRS s, z and proof α , γ . Clearly, the distribution on the output of S ∗ is identical to the distribution on the real pairs of CRS and proof.
34
S. Halevi, S. Myers, and C. Rackoff
It is left to prove computational soundness. Suppose for contradiction that there existed an efficient cheating prover P such that for a constant c > 0 and infinitely many x ∈ / L it holds that:
Pr σ ← P ((s, z), x) : V ((s, z), x, σ) = accept ≥ |x|−c . (2) s,z
We then show a non-uniform seed-compression adversary Adv = (A, B) that breaks the correlation-intractability of the underlying family F . For each x ∈ / L, denote by z(x) the auxiliary string z that maximizes the success probability of P . That is, z(x) = argmax Pr σ ← P ((s, z), x) : V ((s, z), x, σ) = accept . z
s
An easy averaging argument implies that whenever Eq. (2) holds:
Pr σ ← P ((s, z(x)), x) : V ((s, z(x)), x, σ) = accept ≥ |x|−c . s
On the other hand, for any x ∈ / L the relation ⎧ ⎫ ⎨ ⎬ x1 = x, α ||01 −1 and ˆ x = (x1 , x2 , y1 , y2 ) R ∗ ⎩ V x, α, z(x) ⊕ y1 , x2 = accept ⎭ 2
is evasive by the soundness of the original Σ-protocol. (Note, that z(x) is a constant in this relation, so XOR-ing it to y1 = f (x1 ) has no effect on 2 2 soundness when f is a random function.) It follows that for our evasive relations ˆ= ˆ Rx R x∈L / Rx is also an evasive relation. Since our choices of parameters imply that |x| + |α| + |γ| ≤ n/2, then we can use P to construct a seed-compression attacker Adv = (A, B). The first part A gets as advice string the values x, z(x) for some x ∈ / L for which Eq. (2) holds, as well as the seed s for F . It uses P to compute α, γ, and outputs (x, α, γ) as the “compressed seed”, and indeed the length of this “compressed seed” is at most n/2. The second part B outputs x, α and γ, and indeed we have by definition ˆ (x, α , γ, F (s, x, α), F (s, γ)) ∈ R. 5.3
Non-uniformity in the Proof of the Fiat-Shamir Transform
We comment that the proof of Theorem 3 seems inherently non-uniform. We use non-uniformity in two places: one is to select x ∈ / L for which P has good success probability, and the other to select the auxiliary z(x). The first use can be eliminated by switching to a uniform soundness condition on the underlying Σ-protocol (i.e., when a uniform cheating prover needs to output some x ∈ / L together with a convincing proof for it). The latter use of non-uniformity seems harder to eliminate, however. Maybe this can be done by switching to 6-ary relations and setting z = F (s, 0), so we get x1 = 0, x2 = x, α , x3 = γ, ˆ R = (x1 , x2 , x3 , y1 , y2 , y3 ) / L and V ∗ x, α, y1 ⊕ y2 , γ = accept x∈ 2
On Seed-Incompressible Functions
35
ˆ is evasive, but it is not clear how to translate It is not hard to see that this R the success of P in breaking the soundness (when z is chosen at random) to ˆ (when z is set as z = F (s, 0) for a random s). success against this R
6
Future Work and Open Problems
The most intriguing open question that results from this work is whether seedincompressible correlation-intractable functions can be constructed under more traditional computational assumptions. Given that their existence implies the existence of NIZK protocols without the aid of any apparent trapdoor feature, such a construction will likely need substantial insight. Alternately, and just as interesting, would be an argument showing that knowledge of small numbers of key-bits really does allow one to say something meaningful about composition based block-cipher and hash-function designs. In a slightly orthogonal direction, the impossibility results presented in this paper are derived through proving exactly the one property of the function generators that we know the adversary has direct knowledge of: the function is computed by a small circuit. Any definition along the lines of seed-incompressibility that also managed to circumvent this problem would be interesting. Finally, it would be nice if one could show that the OAEP scheme proposed by Bellare and Rogaway[3] (or a close relative of it) could be proven secure under such an assumption, as it is this random-oracle protocol that is probably used in practice on the most frequent basis (due to its inclusion in the TLS protocol [12] for secure web transactions), and thus further evidence of its security would be heartening.
References 1. Barak, B., Lindell, Y., Vadhan, S.: Lower Bounds for Non-Black-Box ZeroKnowledge. The Journal of Computer and System Sciences 72(2), 321–391 (2006) (JCSS FOCS 2003 Special Issue) 2. Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: 1st Conference on Computer and Communications Security, pp. 62–73. ACM, New York (1993) 3. Bellare, M., Rogaway, P.: Optimal asymmetric encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995) 4. Canetti, R.: Towards realizing random oracles: Hash functions that hide all partial information. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 455– 469. Springer, Heidelberg (1997) 5. Canetti, R., Dodis, Y., Halevi, S., Kushilevitz, E., Sahai, A.: Exposure-Resilient Functions and All-or-Nothing Transforms. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 453–469. Springer, Heidelberg (2000) 6. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. Journal of the ACM 51(4), 209–218 (2004) Preliminary version in STOC 1998, pp. 209–218.
36
S. Halevi, S. Myers, and C. Rackoff
7. Canetti, R., Micciancio, D., Reingold, O.: Perfectly one-way probabilistic hashing. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing, Dallas, TX, May 1998, pp. 131–140. ACM Press, New York (1998) 8. Cash, D., Ding, Y.Z., Dodis, Y., Lee, W., Lipton, R.J., Walfish, S.: IntrusionResilient Key Exchange in the Bounded Retrieval Model. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 479–498. Springer, Heidelberg (2007) 9. Coron, J., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgrd Revisited: How to Construct a Hash Function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005) 10. Damgard, I.: On Σ-Protocols. Lecture notes for Cryptologic Protocol Theory course, Aarhus University (2005), http://www.daimi.au.dk/%7Eivan/Sigma.pdf 11. DiCrescenzo, G., Lipton, R.J., Walfish, S.: Perfectly Secure Password Protocols in the Bounded Retrieval Model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 225–244. Springer, Heidelberg (2006) 12. Dierks, T., Allen, C.: RFC2246:The TLS Protocol. RFC 2246, The Internet Society, Network Working Group (1999) 13. Dziembowski, S.: Intrusion-Resilience Via the Bounded-Storage Model. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 207–224. Springer, Heidelberg (2006) 14. Fiat, A., Shamir, A.: How to prove yourself. practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–189. Springer, Heidelberg (1987) 15. Goldreich, O.: Modern Cryptography, Probabilistic Proofs and Pseudorandomness. Algorithms and Combinatorics, vol. 17. Springer, Heidelberg (1998) 16. Goldwasser, S., Kalai, Y.T.: On the (In)security of the Fiat-Shamir Paradigm. In: 44th Symposium on Foundations of Computer Science (FOCS 2003), pp. 102–115. IEEE Computer Society Press, Los Alamitos (2003) 17. Harnik, D., Naor, M.: On the Compressibility of NP Instances and Cryptographic Applications. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 719–728. IEEE Computer Society Press, Los Alamitos (2006) 18. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pp. 44–61. ACM Press, New York (1989) 19. Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, May 1992, pp. 723–732. ACM Press, New York (1992) 20. Micali, S.: CS proofs. In: 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 436–453. IEEE Computer Society Press, Los Alamitos (1994) 21. Micali, S.: Computationally Sound Proofs. SIAM Journal on Computing 30(4), 1253–1298 (2000) 22. Naor, M., Nissim, K.: Computationally sound proofs: Reducing the number of random oracle calls (manuscript, 1999)
Asymptotically Efficient Lattice-Based Digital Signatures Vadim Lyubashevsky and Daniele Micciancio University of California, San Diego La Jolla, CA 92093-0404, USA {vlyubash,daniele}@cs.ucsd.edu
Abstract. We give a direct construction of digital signatures based on the complexity of approximating the shortest vector in ideal (e.g., cyclic) lattices. The construction is provably secure based on the worst-case hardness of approximating the shortest vector in such lattices within a polynomial factor, and it is also asymptotically efficient: the time complexity of the signing and verification algorithms, as well as key and signature size is almost linear (up to poly-logarithmic factors) in the dimension n of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve lattice problems in the worst case, even when restricted to cyclic lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-off.
1
Introduction
Digital signature schemes, initially proposed in Diffie and Hellman’s seminal paper [9] and later formalized by Goldwasser, Micali and Rivest, [15], are among the most important and widely used cryptographic primitives. Still, our understanding of these intriguing objects is somehow limited. The definition of digital signatures clearly fits within the public key cryptography framework. However, efficiency considerations aside, the existence of secure digital signatures schemes can be shown to be equivalent to the existence of conventional (symmetric) cryptographic primitives like pseudorandom generators, one-way hash functions, private key encryption, or even just one-way functions [23,27]. There is a big gap, both theoretical and practical, between the efficiency of known constructions implementing public-key and private-key cryptography. In the symmetric setting, functions are often expected to run in time which is linear or almost linear in the security parameter k. However, essentially all known public key encryption schemes with a supporting proof of security are based on algebraic functions that take at least Ω(k 2 ) time to compute, where 2k is the conjectured hardness of the underlying problem. For example, all factoring based schemes must use keys of size approximately O(k 3 ) to achieve k bits of
Research supported in part by NSF grant CCF-0634909. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 37–54, 2008. c International Association for Cryptologic Research 2008
38
V. Lyubashevsky and D. Micciancio
security to counter the best known sub-exponential time factoring algorithms, and modular exponentiation raises the time complexity to over ω(k 4 ) even when restricted to small k-bit exponents and implemented with an asymptotically fast integer multiplication algorithm. When efficiency is taken into account, digital signatures seem much closer to public key encryption schemes than to symmetric encryption primitives. Most signature schemes known to date employ the same set of number theoretic techniques commonly used in the construction of public key encryption schemes, and result in similar complexity. Digital signatures based on arbitrary one-way hash functions have also been considered, due to the much higher speed of conjectured one-way functions (e.g., instantiated with common block ciphers as obtained from ad-hoc constructions) compared to the cost of modular squaring or exponentiation operations typical of number theoretic schemes. Still, the performance advantage of one-way function is often lost in the process of transforming them into digital signature schemes: constructions of signature schemes from non-algebraic one-way functions almost invariably rely on Lamport and Diffie’s [9] one-time signature scheme (and variants thereof) which requires a number of one-way function applications essentially proportional to the security parameter. So, even if the one-way function can be computed in linear time O(k), the complexity of the resulting signature scheme is again at least quadratic Ω(k 2 ). Therefore, a question of great theoretical and practical interest, is whether digital signature schemes can be realized at essentially the same cost as symmetric key cryptographic primitives. While a generic construction that transforms any one-way function into a signature scheme with similar efficiency seems unlikely, one may wonder if there are specific complexity assumptions that allow to build more efficient digital signature schemes than currently known. Ideally, are there digital signature schemes with O(k) complexity, which can be proved as hard to break as solving a computational problem which is believed to require 2Ω(k) time? 1.1
Results and Techniques
The main result in this paper is a construction of a provably secure digital signature scheme with key size and computation time almost linear (up to polylogarithmic factors) in the security parameter. In other words, we give a new digital signature scheme with complexity O(k logc k) which can be proved to be as hard to break as a problem which is conjectured to require 2Ω(k) time to solve. The problem underlying our signature scheme is that of approximating the shortest vector in a lattice with “cyclic” or “ideal” structure, as already used in [22] for the construction of efficient lattice based one-way functions, and subsequently extended to collision resistant functions in [25,18]. As in most previous work on lattices, our scheme can be proven secure based on the worst case complexity of the underlying lattice problems. Since one-way functions are known to imply the existence of many other cryptographic primitives (e.g., pseudorandom generators, digital signatures, private
Asymptotically Efficient Lattice-Based Digital Signatures
39
key encryption, etc.), the efficient lattice based one-way functions of [22] immediately yield corresponding cryptographic primitives based on the complexity of cyclic lattices. However, the known generic constructions of cryptographic primitives from one-way functions are usually very inefficient. So, it was left as an open problem in [22] to find direct constructions of other cryptographic primitives from lattice problems with performance and security guarantees similar to those of [22]. For the case of collision resistant hash functions, the problem was resolved in [25,18], which showed that various variants of the one-way function proposed in [22] are indeed collision resistant. In this paper we build on the results of [22,25,18] to build an asymptotically efficient lattice-based digital signature scheme. Theorem 1. There exists a signature scheme such that the signature of an n˜ bit message is of length O(k) and both the signing and verification algorithms ˜ ˜ take time O(n)+ O(k). The scheme is strongly unforgeable in the chosen message attack model, assuming the hardness of approximating the shortest vector problem ˜ 2 ). in all ideal lattices of dimension k to within a factor O(k Our lattice based signature scheme is based on a standard transformation from one-time signatures (i.e., signatures that allow to securely sign a single message) to general signature schemes, together with a novel construction of a lattice based one-time signature. We remark that the same transformation from onetime signatures to unrestricted signature schemes was also employed by virtually all previous constructions of digital signatures from arbitrary one-way functions (e.g., [21,23,27]). This transformation, which combines one-time signatures together with a tree structure, is relatively efficient and allows one to sign messages with only a logarithmic number of applications of a hash function and a onetime signature scheme [28]. The bottleneck in one-way function based signature schemes is the construction of one-time signatures from one-way functions. The reason for the slowdown is that the one-way function is typically used to sign a k-bit message one bit at a time, so that the entire signature requires k evaluations of the one-way function. In this paper we give a direct construction of one-time signatures, where each signature just requires two applications of the lattice based one-way function of [22,25,18]. The same lattice based hash function can then be used to efficiently transform the one-time signature into an unrestricted signature scheme with only a logarithmic loss in performance. The high level structure of our lattice based one-time signature scheme is easily explained. The construction is based on the generalized compact knapsack functions of [22,25,18]. These are keyed functions (indexed by a key (a1 , . . . , ak )) of the form h(x1 , . . . , xm ) = ai · xi , i
where a1 , . . . , am , x1 , . . . , xm are elements of some large ring R, and the result of the function is also in R. The domain of the function is restricted to xi ∈ D, where D is a subset of R of small elements. For example, if R is the ring of integers, and D = {0, 1}, then h is just the subset-sum function. Notice that if
40
V. Lyubashevsky and D. Micciancio
D is not restricted, then h is certainly not a one-way function: the function can be easily inverted over the integers using the extended Euclid algorithm for greatest common divisor computation. For efficiency reasons, here (as in [22,25,18]) we use a different ring R and a much larger subset D ⊂ R, so that a single element of D can be used to encode a k-bit message (see section 2.3). We now give very high level overviews of our one-time signature and the proof of its security. One-time signature. When the user wants to generate a key for the one-time signature scheme, he simply picks two “random” inputs x, y ∈ Dm , and computes their images under the hash function (h(x), h(y)). (The key (a1 , . . . , am ) to the hash function h can also be individually chosen by the user, or shared among all the users of the signature scheme.) The secret key is the pair (x, y) while the public key is given by their hashes (h(x), h(y)). Then, the signature of a message z is simply obtained as a “linear combination” x · z + y of the two secret vectors, with coefficient being the message z to be signed. (The multiplication x · z is defined as the ring multiplication of each coordinate of x by z.) Signatures can be easily verified using the homomorphic properties of the lattice based hash function h(x · z + y) = h(x) · z + h(y). Security proof. If the domain D m were closed under the ring addition and multiplication operations, then one could show that the public key (h(x), h(y)) and signature x · z + y do not reveal enough information to obtain the signer’s secret key (x, y), and a forgery relative to a different secret key will yield a collision to the hash function. But because the domain is restricted, there is a possibility that the signer’s secret key was the only one that could have produced h(x), h(y) and signature x · z + y, and so an adversary who sees these values might be able to deduce the secret key. This turns out to be the main difficulty in carrying out our proof. We overcome this technical problem by choosing the secret key elements x, y according to a carefully crafted (non-uniform) probability distribution, which can be intuitively thought as a “fuzzy” subset of the full domain Rm . It turns out that if the appropriate distribution is used, then we can have the domain Dm be closed under the ring operations in an approximate probabilistic sense, and still have h be a function that’s hard to invert. 1.2
Related Work
Lamport showed the first construction of a one-time signature based on the existence of one-way functions. In that scheme, the public key consists of the values f (x0 ), f (x1 ), where f is a one-way function and x0 , x1 are randomly chosen elements in its domain. The elements x0 and x1 are kept secret, and in order to sign a bit i, the signer reveals xi . This construction requires one application of the one-way function for every bit in the message. Since then, more efficient constructions have been proposed in (e.g. [20,7,6,11,4,5,16]), but there was always an inherent limitation in the number of bits that could be signed efficiently with one application of the one-way function [12]. Provably secure cryptography based on lattice problems was pioneered by Ajtai in [2], and attracted considerable attention within the complexity theory
Asymptotically Efficient Lattice-Based Digital Signatures
41
community because of a remarkable worst-case/average-case connection: it is possible to show that breaking the cryptographic function on the average is at least as hard as solving the lattice problem in the worst-case. Unfortunately, functions related to k-dimensional lattices typically involve an k-dimensional matrix/vector multiplication, and therefore require k 2 time to compute (as well as k 2 storage for keys). A fundamental step towards making lattice based cryptography more attractive in practice, was taken by Micciancio [22] who proposed a variant of Ajtai’s function which is much more efficient to compute (thanks to the use of certain lattices with a special cyclic structure) and still admits a worst-case/average-case proof of security. The performance improvement in [22] (as well as in subsequent work [25,18],) comes at a cost: the resulting function is as hard to break as solving the shortest vector problem in the worst case over lattices with a cyclic structure. Still, since the best known algorithms do not perform any better on these lattices than on general ones, it seems reasonable to conjecture that the shortest vector problem is still exponentially hard. It was later shown in [25,18] that, while the function constructed in [22] was only oneway, it is possible to construct efficient collision-resistant hash functions based on the hardness of problems in lattices with a similar algebraic structure. 1.3
Open Problems
Our work raises many interesting open problems. One such problem is constructing a one-time signature with similar efficiency, but based on a weaker hardness assumption. For instance, it would be great to provide a one-time signature with security based on the hardness of approximating the shortest vector problem ˜ (in ideal lattices) to within a factor of O(n). Also, with the recent results of Peikert and Rosen [26], showing a possible way to build cryptographic functions whose security is based √ on approximating the shortest vector in special lattices to within a factor O( log n), we believe that it is worthwhile exploring whether one-time signatures can be built based on similar assumptions. Another direction to try to build efficient signature schemes based directly on the hardness of lattice problems without going through one-time signatures and an authentication tree. The main advantage of such a scheme would be that the signer would not have to “keep a state” and remember which verification keys have already been used. Such constructions have been achieved based on problems from number theory [13,8] but they are not as efficient, in an asymptotic sense, as the signature scheme presented here. While the scheme presented here has almost optimal asymptotic efficiency, it is not yet ready to be used for practical applications (see Section 4). The main issue is that lattice reduction algorithms perform much better in practice than in theory, and thus our signature scheme may be insecure for parameters appropriate for practical schemes. Nevertheless, the recent advances in latticebased cryptography are a very encouraging sign that with some novel ideas, our construction can be modified into a serviceable signature scheme.
42
2 2.1
V. Lyubashevsky and D. Micciancio
Preliminaries Signatures
We recall the definitions of signature schemes and what it means for a signature scheme to be secure. Definition 2. A signature scheme consists of a triplet of polynomial-time (possibly probabilistic) algorithms (G, S, V ) such that for every pair of outputs (s, v) of G(1n ) and any n-bit message m, P r[V (v, m, S(s, m)) = 1] = 1 where the probability is taken over the randomness of algorithms S and V . In the above definition, G is called the key-generation algorithm, S is the signing algorithm, V is the verification algorithm, and s and v are, respectively, the signing and verification keys. A signature scheme is said to be secure if there is only a negligible probability that any adversary, after seeing signatures of messages of his choosing, can sign a message whose signature he has not already seen [15]. One-time security means that an adversary, after seeing a signature of a single message of his choosing, cannot produce a valid signature of a different message. Definition 3. A signature scheme (G, S, V ) is said to be one-time secure if for every polynomial-time (possibly randomized) adversary A, the probability that after seeing (m, S(s, m)) for any message m of its choosing, A can produce (m = m, σ ) such that V (v, m , σ ) = 1, is negligibly small. The probability is taken over the randomness of G, S, V , and A. In the standard security definition of a signature scheme, the adversary should not be able to produce a signature of a message he hasn’t already seen. A stronger notion of security, called strong unforgeability requires that in addition to the above, an adversary shouldn’t even be able to come up with a different signature for a message whose signature he has already seen. The scheme presented in this paper satisfies this stronger notion of unforgeability. Another feature of signatures that is sometimes desirable is the ability of the legitimate signer to prove that a message was not actually signed by her. Of course, it should be impossible for the signer to repudiate a message that she actually signed. Signatures schemes that have this feature are called Fail-Stop [24]. Our scheme has this property as well. 2.2
Notation
Let R = Zp [x]/f be a ring where f is an irreducible monic polynomial of degree n over Z[x] and p is some small prime. For the rest of the paper, the variables n, p, and f will always be associated with the ring R. We will denote elements in R by bold letters and elements of Rm , for some positive integer m,
Asymptotically Efficient Lattice-Based Digital Signatures
43
= (a1 , . . . , am ) ∈ Rm when all the ai ’s by a bold letter with a hat. That is, a = (a1 , . . . , am ) ∈ Rm and an element z ∈ R, we are in R. For an element a , z = (a1 z, . . . , am z). For two elements a b ∈ Rm , addition is defined as define a + a b = (a1 +b1 , . . . , am +bm ) and the dot product as a b = a1 b1 +. . .+am bm . Notice that with the operations that we defined, the set Rm is an R-module. , That is, Rm is an abelian additive group such that for all a b ∈ Rm and r, s ∈ R, we have r + 1. ( a+ b)r = a br 2. ( ar)s = a(rs) (r + s) = a r + a s 3. a We will now give a definition for the “length” of elements in R. To do so, we will first need to specify their representations in the ring. For our application, we will represent elements in R by a polynomial of degree n − 1 having coefficients p−1 in the range [− p−1 2 , 2 ], and so when we talk about reduction modulo p, we mean finding an equivalent element modulo p in the aforementioned range. For an element a = a0 + a1 x + . . . + an−1 xn−1 ∈ R, we define a ∞ = maxi (|ai |). = (a1 , . . . , am ) ∈ Rm , we define Similarly, for elements a a ∞ = maxi ( ai ∞ ). Notice that · ∞ is not exactly a norm because αa ∞ = α a ∞ for all integers α (because of the reduction modulo p), but it still holds true that a + b ∞ ≤ a ∞ + b ∞ and αa ∞ ≤ α a ∞ . While putting an upper-bound on a + b ∞ is straight-forward, it turns out that upper-bounding ab ∞ is somewhat more involved. Suppose that we are trying to determine the upper bound on ab ∞ . For a moment, let’s pretend that a and b are polynomials in Z[x]. Then, the product ab will have degree at most 2n − 2 and the absolute value of the maximum coefficient of ab will be at most n a ∞ b ∞ . Reducing ab modulo p will not increase the absolute value of the maximum coefficient, but reducing modulo the polynomial f can (and usually does). So if we want to upper bound ab ∞ , we need to account for the increase in the coefficient size when we reduce a polynomial in Z[x] of degree 2n − 2 modulo f . For any ring R, we define a constant φ(R) as, φ(R) = min {j : ∀a, b ∈ R, ab ∞ ≤ jn a ∞ b ∞ }. The constant φ(R) is intimately tied to the concept of “expansion factor” introduced in [18]. It is also somewhat related to the root discriminant of a number field as described in [26]. We will not go into many details here, other than to mention that there are many polynomials f which result in φ(R) being small and it is not too hard to upper bound the value of φ(R). For example for f = xn + 1, φ(R) = 1 and for f = xn + xn−1 + . . . + 1, φ(R) ≤ 2. In the rest of the paper, we will omit the parameter R, and just write φ. 2.3
A Hash Function Family
We now define a function family HR,m that maps Rm to R. The functions ∈ Rm . The input to the function is an h ∈ HR,m are indexed by elements a
44
V. Lyubashevsky and D. Micciancio
∈ Rm , and the output is a element z z . So the functions in HR,m map elements m from R to R. To summarize, ∈ Rm }, where ha ( z HR,m = {ha : a z) = a Throughout the paper, we will write h rather than ha with the understanding associated with the function h. Notice that we can efficiently that there is an a generate random functions from the function family HR,m by simply generating ∈ Rm . a random a It was shown in [18] that finding two “small” elements s, s ∈ Rm such that h( s) = h( s ) for randomly chosen h ∈ HR,m is at least as hard as solving the approximate shortest vector problem for all lattices of a certain type (a problem which is believed to be hard). The security of our signature scheme will be based on the hardness of this collision problem. We now define the problem formally. Definition 4. The collision problem, Cold,HR,m (h) takes as input a random s, s ∈ Rm with function h ∈ HR,m , and asks to find two distinct elements s ∞ , s ∞ ≤ d such that h( s) = h( s ). We now make some useful observations about the function family HR,m . The first observation is that the functions in HR,m are module homomorphisms. l ∈ Rm , Claim. HR,m is a set of module homomorphisms. That is, for every k, z ∈ R, and h ∈ HR,m , the following two conditions are satisfied: + l) = h(k) + h(l) 1. h(k 2. h(kz) = h(k)z Proof. By the definition of the hash function h, we have + l) = a + l) = a +a + h(l) (k k l = h(k) 1. h(k =a (k1 z, . . . , km z) = a1 k1 z + . . . + am km z 2. h(kz) = h(k)z = (a1 k1 + . . . + am km )z = ( a k)z
The next observation is that the kernel of every h ∈ HR,m contains an exponential number of “small” elements. ∈ Rm such Lemma 5. For every h ∈ HR,m , there exist at least 5mn elements y 1/m that y ∞ ≤ 5p and h( y ) = 0. Proof. Let S be the set containing all elements in Rm with coefficients between 0 and 5p1/m . Since |S| = (5p1/m + 1)mn > 5mn pn and |R| = pn , by the pigeonhole principle, there exists a t ∈ R and a subset S ⊆ S such that |S | ≥ 5mn and for all s ∈ S , h( s ) = t. If t = 0, then we’re done, otherwise let S = { s1 , s2 , . . . , sk } and consider the set Y = { s1 − s1 , s1 − s2 , . . . , s1 − sk } of size |S | . Note that for 1/m each y ∈ Y , y ∞ ≤ 5p and h( y ) = 0 because of the homomorphic property of h.
Asymptotically Efficient Lattice-Based Digital Signatures
2.4
45
Lattices
In this subsection, we explain the relationship between the collision problem from Definition 4 and finding shortest vectors in certain types of lattices. An n-dimensional integer lattice L is a subgroup of Zn . A lattice L can be represented by a set of linearly independent generating vectors, called a basis. For any lattice vector y ∈ L, the infinity norm of y, y ∞ , is the absolute value of the largest coefficient of y. The minimum distance (in the infinity norm1 ) of a lattice L, denoted by λ1 (L), is defined as: λ1 (L) =
min { y ∞ }
y∈L\{0}
Computing the λ1 (L) of a lattice was first shown to be NP-hard by van Emde Boas [29], and it was shown hard to approximate to within a factor of n1/ log log n by Dinur [10]. It is conjectured that approximating λ1 (L) to within any polynomial factor is a hard problem (though not NP-hard [14,1]) since the fastest known algorithm takes time 2O(n) to accomplish this [17,3]. Micciancio [22] defined a cyclic lattice to be a lattice L such that if the vector (a1 , . . . , an−1 , an ) ∈ L, then the vector (an , a1 , . . . , an−1 ) is also in the lattice L. Such lattices correspond to ideals in Z[x]/xn − 1. In [22], Micciancio gave a construction of an efficient family of one-way functions with security based on the worst case hardness of approximating λ1 (L) in cyclic lattices. Subsequently, it was shown in [25,18] how to modify Micciancio’s function in order to make it collision resistant. In addition, it was shown in [18] how to create efficient collision resistant hash functions with security based on approximating λ1 (L) in lattices that correspond to ideals in rings Z[x]/f for general f . A lattice corresponding to an ideal means that the vector (a0 , . . . , an−1 ) is in the lattice, if and only if the polynomial a0 + a1 x + . . . + an−1 xn−1 is in the ideal. Despite the added structure of these algebraic lattices, the best algorithms to solve the shortest vector problem are the same ones as for arbitrary lattices. The following theorem is a weaker special case of the main result of [18] that is most pertinent to this work: Theorem 6. Let f be an irreducible polynomial in Z[x] of degree n and define integers p = (φn)3 and m = log n. If there exists a polynomial-time algorithm that solves Cold,HR,m (h) for R = Zp [x]/f and d = 10φp1/m n log2 n, then there exists a polynomial-time algorithm that approximates λ1 (L) to within a factor of ˜ 5 n2 ) for every lattice L corresponding to an ideal in the ring Z[x]/f . O(φ We point out that in [18, Theorem 2] (which is the main result of [18]), it is shown that solving the Cold,HR,m (h) problem for certain parameters p, d, and m implies ˜ approximating the shortest vector to within a factor of O(n). Unfortunately, in the current paper we cannot show that breaking the one-time signature implies 1
All the results in this paper can be adapted to any p norm. For simplicity, we concentrate on the ∞ case, since it is the most convenient one in cryptographic applications.
46
V. Lyubashevsky and D. Micciancio
solving the Cold,HR,m (h) problem for such optimal parameters (mainly, we cannot get the parameter d to be too small). And so Theorem 6 is a weaker version of [18, Theorem 2] where the parameters p, m, and d are set in a way such that breaking the one-time signature implies solving Cold,HR,m (h). We also notice in the above theorem that the approximation factor heavily depends on φ. Thus it’s prudent to choose a polynomial f that results in a small φ. Choosing irreducible polynomials of the form xn + 1 or xn + xn−1 + . . . + 1 makes φ a small constant (1 and 2 respectively). We also point out that the integer p needs not be a prime for the proof of security to hold, but there are some practical advantages to setting it to a prime when implementing functions that involve multiplications of elements in Zp [x]/f [19].
3
The One-Time Signature Scheme
In this section we present our one-time signature scheme. The security of the scheme will be ultimately based on the worst-case hardness of approximating the shortest vector in all lattices corresponding to ideals in the ring Z[x]/f for any irreducible polynomial f . The approximation factor is determined by the polynomial f as in Theorem 6. The key-generation algorithm for the signature scheme allows us to specify the polynomial f that we want to use for the hardness assumption. Key-Generation Algorithm: Input: 1n , irreducible polynomial f ∈ Z[x] of degree n. 1: Set p ← (φn)3 , m ← log n, R ← Zp [x]/f 2: For all positive i, let the sets DKi and DLi be defined as: y ∈ Rm such that y ∞ ≤ 5ip1/m } DKi = { y ∈ Rm such that y ∞ ≤ 5inφp1/m } DLi = { 3: Choose uniformly random h ∈ HR,m
Pick a uniformly random string r ∈ {0, 1}log n 2 if r = 0log n then set j = log2 n else set j to the position of the first 1 in the string r end if l independently and uniformly at random from DKj and DLj rePick k, spectively l). Verification Key: (h, h(k), h(l)) 11: Signing Key: (k, 4: 5: 6: 7: 8: 9: 10:
2
Signing Algorithm: l) Input: Message z ∈ R such that z ∞ ≤ 1; signing key (k, Output: s ← kz + l
Asymptotically Efficient Lattice-Based Digital Signatures
47
Verification Algorithm: h(l)) Input: Message z; signature s; verification key (h, h(k), 2 1/m + h(l) Output: “ACCEPT”, if s ∞ ≤ 10φp n log n and h( s) = h(k)z “REJECT”, otherwise. At this point we would like to draw the reader’s attention to the particulars of l). Because how the key-generation algorithm generates the secret signing key (k, (resp. l) gets chosen of the way that the integer j is generated, the secret key k uniformly at random from the set DKj (resp. DLj ) with probability 2−j for 1 ≤ j < log2 n and with probability 2−j+1 for j = log2 n. Since DK1 ⊂ and l DK2 ⊂ . . . ⊂ DKlog2 n and DL1 ⊂ DL2 ⊂ . . . ⊂ DLlog2 n , the keys k end up being chosen from the sets DKlog2 n and DLlog2 n , but not uniformly at random. Notice that keys with smaller coefficients are more likely to be chosen, and it’s also extremely unlikely that we will ever end up with keys that are not in DKlog2 n−1 and DLlog2 n−1 . So with probability negligibly close to 1, there will always be valid secret keys that are “larger” than the ones generated by the key-generation algorithm. This will be crucial to the proof of security. We will first show that the verification algorithm will always accept the signature generated by the signing algorithm of any message z ∈ R. Note that the l are contained in sets DKlog2 n and DLlog2 n respectively. Thus signing keys k, 1/m k ∞ ≤ 5p log2 n and l ∞ ≤ 5φp1/m n log2 n. Therefore, +l ∞ ≤ kz ∞ + l ∞ ≤ φn k ∞ z ∞ + l ∞ ≤ 10φp1/m n log2 n s ∞ = kz Also, by the homomorphic property of functions h ∈ HR,m , + l) = h(k)z + h(l). h( s) = h(kz We next show that the above signature scheme is secure against forgery. More precisely, we show that forging a signature implies being able to solve the Cold,HR,m (h) problem for the parameters in Theorem 6, which in turn implies being able to approximate λ1 (L) for any lattice L that corresponds to an ideal in the ring Z[x]/f . Theorem 7. If there exists a polynomial-time adversary that, after seeing a sig l of a message z, can output a valid signature of another message nature s = kz+ z with probability 1/poly(n), then there exists a polynomial time algorithm that can solve the Cold,HR,m (h) problem for d = 10φp1/m n log2 n. Proof. Let A be an adversary who can break the one-time signature scheme. This means that after seeing a signature for any message of his choice, A can then successfully sign a different message of his choice. Before proceeding any further, we point out that an adversary who succeeds in forging a signature with non-negligible probability must succeed with nonnegligible probability in the case that j < log2 n in the key-generation step. 2 This is because j equals log2 n with probability only 2−log n+1 , and so an
48
V. Lyubashevsky and D. Micciancio
adversary must also be able to forge signatures for other values of j if he is to have a non-negligible success probability. In the remainder of the proof, we will be assuming that the j generated in the key-generation step was less than log2 n. ∈ DKlog2 n−1 and l ∈ DLlog2 n−1 . In other words, we’ll be assuming that k The algorithm below uses the message-forging adversary A to solve the Cold,HR,m (h) problem for the parameters specified in Theorem 6. Cold,HR,m (h) 1: Run the Key-Generation algorithm (but use the given h instead of generating a random one). 2: Receive message z from A. + l to A. 3: Send kz 4: Receive message z and its signature s from A + l 5: Output s and kz We now need to show that the outputs of the above algorithm are a collision for the function h with non-negligible probability. If A succeeds in forging a signature s for z (which happens with non-negligible probability), then s ∞ ≤ 2 1/m + l). So if + l, 10φp n log n and h( s ) = h(k)z + h(l) = h(kz s = kz then our algorithm outputted two distinct elements that form a collision for the function h. +l, then we do not get a collision. To complete On the other hand, if s = kz the proof of Theorem 7, we will show that it’s extremely unlikely that an adversary (even one with unlimited computational power) can produce an s and a z + l. This will be done in two steps. In the first step, we show such that s = kz that being able to produce such an s and z implies uniquely determining the l). Then in the second step we show that given the public key signing key (k, +l of message z, it is information theoretically (h, h(k), h(l)) and a signature kz l). This means that if A is able to impossible to determine the signing key (k, + l. forge a signature s for some message z , then almost certainly s = kz + l uniquely We now show that obtaining an s and a z such that s = kz l. Since we know that + l and + l, it follows that determines k, s = kz s = kz 2 1/m − z ). Since k ∞ ≤ 5p s− s = k(z log n and z − z ∞ ≤ 2, multiplying by z − z in the ring Zp [x]/f is the same as multiplying them in the ring k Z[x]/f because the coefficients never get big enough to get reduced modulo p. This is because − z ) ∞ ≤ 10φp1/m n log2 n = 80φ1+ log n n log2 n = φ1+o(1) · o(n2 ), k(z 3
but in order to get reduced modulo p, the absolute value of the coefficients would have to be at least p/2 = Θ(φ3 n3 ), which is a much larger quantity. Now, since the ring Z[x]/f is an integral domain and z − z = 0, there cannot exist such that k (z − z ) = k(z − z ). And so the key k is = k another key k s− s uniquely determined (and is equal to z−z ), and similarly the key l = s − kz is also unique.
Asymptotically Efficient Lattice-Based Digital Signatures
49
h(l), z, and kz + l, Now we move on to showing that by knowing only h, h(k), l) it is information theoretically impossible to determine the signing key (k, (and thus, information theoretically impossible to come up with s , z such that + l). The idea is to show that for every h, h(k), h(l), z, kz + l there s = kz is an exponential number of signing keys (k , l ), other than (k, l), that satisfy = h(k ), h(l) = h(l ), and kz + l = k z + l . And in addition, the total h(k) probability that one of these other keys was chosen in the key-generation step h(l), z, kz + l) is almost one. (conditioned on h, h(k), We point out that we are not proving witness-indistinguishability. It’s actually , l ), the probability that it was the key quite possible that for every other key (k that was used to sign the message is exponentially smaller than the probability l) was the key. What we will be showing is that the sum of probabilities that (k, of all other possible keys combined being the secret key is exponentially larger l) was the key. than the probability that (k, Lemma 8. Let (h, K, L) be the verification key of the signature scheme and s is the signature of some message z. Then for any signing key (k, l) such that ∈ DKlog2 n−1 , l ∈ DLlog2 n−1 , h(k) = K, h(l) = L and + l, the k s = kz probability that this was the actual signing key generated by the key-generation algorithm is negligibly small. Proof. We define the set Y to be the elements of the kernel of h that have “small lengths”. In particular, Y = { y ∈ Rm such that y ∞ ≤ 5p1/m and h( y ) = 0}. = k −y ∈ Y , consider the elements k and l = l + y z. Notice that For every y
) = h(k −y − h( ) = h(k) h(k y ) = K − 0 = K, z) = h(l) + h( h(l ) = h(l + y y )z = L + 0 = L,
−y + l = z + l = (k )z + l + y z = kz s. k happens to be in DKlog2 n and l happens to be in ∈ Y , if k Thus, for every y , l ) is another valid signing key that could have been used DLlog2 n , then (k to sign the message z. Since y ∞ ≤ 5p1/m and y z ∞ ≤ 5nφp1/m , we get the and l : following bounds on the norms of k
∞ ≤ k ∞ + ∞ + 5p1/m , k y ∞ ≤ k l ∞ ≤ l ∞ + yz ∞ ≤ l ∞ + 5nφp1/m .
For the remainder of the proof, let i be the smallest integer such that k and l are contained in DKi and DLi respectively. Then k and l are definitely
50
V. Lyubashevsky and D. Micciancio
∈ ∈ Y . And since we assumed that k contained in DKi+1 and DLi+1 for every y , l ) is a perfectly valid DKlog2 n−1 and l ∈ DLlog2 n−1 , it turns out that (k signing key. To prove the lemma, we will need to upper-bound the probability l given that the public keys are K = h(k) that the generated secret keys were k, and L = h(l) and the signature of z is s = kz + l. Let E be the event that the verification key are K and L and the signature of z is s. l)|E] = P r[key = (k, l) & E] = P r[key = (k, l)] P r[signing key = (k, P r[E] P r[E] l. This is computed We now calculate the probability that the keys were k, by noting that k, l were generated by selecting j ≥ i with probability 2−j and l from DKj and DLj . Since k and l are chosen uniformly and then selecting k, independently at random from DKj and DLj , the probability that they are both 1 chosen is |DKj |·|DL . So, j| l)] = P r[signing key = (k,
1 1 + i+1 + ... 2 |DKi+1 ||DLi+1 | i ||DLi |
2i |DK
(1)
To calculate the probability of event E, we need to figure out the probability that the keys chosen will result in public keys K and L and when given the ∈Y, message z, the signature will be s. We have shown above that for every y −y , l + y z will produce public keys K, L and signature choosing the keys k −y and l + y z are contained in DKi+1 and DLi+1 s. Since we know that k respectively, we get P r[E] >
|Y | 2i+1 |DK
i+1 ||DLi+1 |
+
|Y | 2i+2 |DK
i+2 ||DLi+2 |
+ ...
(2)
l)], then combining (1) and (2) we get If we let q = P r[signing key = (k, 1 P r[E] > |Y | q − i 2 |DKi ||DLi | and so, l)] P r[signing key = (k, q q2i |DKi ||DLi | = < P r[E] |Y |(q2i |DKi ||DLi | − 1) |Y | q − 2i |DK1i ||DLi | 1 1 1+ i = |Y | q2 |DKi ||DLi | − 1 Before proceeding, we will state the following inequality that will be used later, |DKi+1 ||DLi+1 | (2 · 5(i + 1)p1/m )mn (2 · 5(i + 1)nφp1/m )mn = |DKi ||DLi | (2 · 5ip1/m )mn (2 · 5inφp1/m )mn 2mn 1 = 1+ ≤ 22mn = 4mn i
Asymptotically Efficient Lattice-Based Digital Signatures
51
Now we use the above inequality to lower bound the quantity q2i |DKi ||DLi |. l), and Recall that q was defined to be the probability that the signing key is (k, so from Equation (1), we obtain 1 1 i i q2 |DKi ||DLi | = 2 |DKi ||DLi | + + ... 2i |DKi ||DLi | 2i+1 |DKi+1 ||DLi+1 | 1 1 + i+1 > 2i |DKi ||DLi | i 2 |DKi ||DLi | 2 |DKi+1 ||DLi+1 | 1 |DKi ||DLi | ≥1+ =1+ 2|DKi+1 ||DLi+1 | 2 · 4mn Using the above inequality, we obtain l)] 1 1 1 P r[signing key = (k, < 1+ i ≤ (1 + 2 · 4mn ) P r[E] |Y | q2 |DKi ||DLi | − 1 |Y | and since by Lemma 5 we know that |Y | ≥ 5mn , we are done.
This concludes the proof of the theorem.
3.1
Strong Unforgeability
We now show that our one-time signature scheme also satisfies a stronger notion of security, called strong unforgeability. In the previous section we showed that if an adversary can produce a signature for an unseen message, then Cold,HR,m (h) can be solved in polynomial time. Now we point out that Cold,HR,m (h) can be solved in polynomial time even if the adversary is able to produce a different signature of a message whose signature he has seen. Suppose that after seeing + l of a message z, the adversary A sends back another the signature s = kz valid signature s = s of z. Then s and s form a collision for h. This is because + h(l) = h(kz + l) = h( h( s ) = h(k)z s).
4
Practical Attacks
While our scheme is efficient and secure in an asymptotic sense, it is not yet secure for parameters that one would want to use in practical applications. In this section we demonstrate an attack against our one-time signature scheme by showing how an adversary would go about forging a signature for the message z = 0. We demonstrate the attack for this message because it is the simplest to explain, but the attack can be easily adapted to any other message. and h(l), we can forge a signature for the Knowing the public keys h(k) message z = 0 by finding an element l of length less than 10φp1/m n log2 n such that h(l ) = h(l) and outputting it as the signature s. Note that h( s) = s ∞ = l ∞ . So s will be a valid signature h(k)0+h(l) = h(l) = h(l ) and also
52
V. Lyubashevsky and D. Micciancio
of 0. The hard part is of course finding an l such that h(l ) = h(l). But while this problem is believed to be exponentially hard in n (the degree of the polynomial h(l)),for small values of n, this problem is heuristically solvable. We will now give an overview of how one would go about finding an l with small coefficients when given h(l ). The idea is to use lattice reduction and so first we will need to view multiplication in the ring Zp [x]/f as matrix-vector multiplication. Every polynomial in Zp [x]/f can be associated with an n-dimensional vector in Zp in the obvious way. Also, for any element a ∈ Zp [x]/f , define M (a) to be an n × n matrix where the ith column (for 0 ≤ i ≤ n − 1) corresponds to the vector representation of the polynomial axi . Now we can see that the multiplication of two polynomials a, b ∈ Zp [x]/f can be written as the multiplication modulo p of the matrix M (a) by the vector representation of b. By the above observation, the evaluation of the function ha (l ) can be interpreted as as a multiplication of an n × nm matrix A = (M (a1 )| . . . |M (am )) by the vector representation of l modulo p. And so when we’re given the public key h(l ), we can interpret it as a vector (call it y), and then try to find a vector b with coefficients at most 10φp1/m n log2 n such that Ab = y(modp). We will now explain how to use lattice reduction to find such a vector b. We first define a matrix A = (A|y), and then try to find a vector b such that A b = 0(modp) where the last coordinate of b is −1. Notice that this problem is equivalent to the previous one. We now observe that all the vectors b ∈ Zmn+1 that satisfy A b = 0(modp) form an additive group, and thus an integer lattice of dimension mn+1. And since we are trying to find a b with small coordinates, this is akin to finding a short vector in the aforementioned lattice. The basis of this lattice can be constructed in polynomial time (by viewing A as a linear transformation mapping Zmn+1 to Znp , and computing the kernel of this transformation). And now all we need to do is find a vector in this mn + 1 dimensional lattice such that all its coordinates are less than 10φp1/m n log2 n, and the last coordinate is −1. Suppose that n is around 512, then p = n3 = 227 , m = log n = 9, and suppose that φ = 1. Thus we need to find a vector whose coordinates are less that 80n log2 n ≈ 221 in a lattice of dimension 512 ∗ 9 + 1 = 4609. It’s important to notice that this lattice has a vector all of whose coefficients have absolute value at most 1, and all we need is a vector whose coefficients are less than 221 . Such a large vector (relative to the shortest vector) can easily be found by using standard lattice reduction algorithms that find an approximate shortest vector of the lattice. And heuristically, the algorithm can find such a short vector with the added requirement that the last coordinate is −1. At this point it is unclear exactly how large we would have to set n in order to avoid the above attack, but it is certainly above any parameter that could be useful in practical applications. Nevertheless, we believe that by using the general structure of the scheme presented in this paper as a starting point, it
Asymptotically Efficient Lattice-Based Digital Signatures
53
may be possible to construct a practical and secure signature scheme, and this could prove to be a fruitful direction for further research.
Acknowledgements We would like to thank the anonymous referees for their comments which helped improve the presentation of this paper.
References 1. Aharonov, D., Regev, O.: Lattice problems in NP ∩ coNP. Journal of the ACM 52(5), 749–765 (2005) 2. Ajtai, M.: Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica 13, 1–32 (2004) (Preliminary version in STOC 1996) 3. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601–610 (2001) 4. Bleichenbacher, D., Maurer, U.: On the efficiency of one-time digital signatures. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 145–158. Springer, Heidelberg (1996) 5. Bleichenbacher, D., Maurer, U.: Optimal tree-based one-time digital signature schemes. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 363–374. Springer, Heidelberg (1996) 6. Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13(4), 850–864 (1984) 7. Bos, J., Chaum, D.: Provably unforgeable signatures. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 1–14. Springer, Heidelberg (1999) 8. Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur. 3(3), 161–185 (2000) 9. Diffie, W., Hellman, M.: New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654 (1976) 10. Dinur, I.: Approximating SV P ∞ to within almost-polynomial factors is NP-hard. Theor. Comput. Sci. 285(1), 55–71 (2002) 11. Even, S., Goldreich, O., Micali, S.: On-line/off-line digital signatures. J. Cryptology 9(1), 35–67 (1996) 12. Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing 35(1), 217–246 (2005) 13. Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123– 139. Springer, Heidelberg (1999) 14. Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60(3) (2000) 15. Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988) 16. Hevia, A., Micciancio, D.: The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 379–396. Springer, Heidelberg (2002)
54
V. Lyubashevsky and D. Micciancio
17. Kumar, R., Sivakumar, D.: On polynomial-factor approximations to the shortest lattice vector length. SIAM J. Discrete Math. 16(3), 422–425 (2003) 18. Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006) 19. Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, R.: Provably secure FFT hashing. Technical report, 2nd NIST Cryptographic Hash Function Workshop (2006) 20. Merkle, R.: A digital signature based on a conventional encryption function. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 369–378. Springer, Heidelberg (1999) 21. Merkle, R.: A certified digital signature. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 218–238. Springer, Heidelberg (1999) 22. Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient oneway functions. Computational Complexity (2007) (Special issue on worst-case versus average-case complexity, in print. Available on-line as doi:10.1007/s00037-0070234-9. Preliminary version in FOCS 2002) 23. Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC, pp. 33–43 (1989) 24. Pedersen, T., Pfitzmann, B.: Fail-stop signatures. SIAM J. Comput. 26(2), 291–330 (1997) 25. Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, Springer, Heidelberg (2006) 26. Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: STOC (2007) 27. Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC, pp. 387–394 (1990) 28. Szydlo, M.: Merkle tree traversal in log space and time. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 541–554. Springer, Heidelberg (2004) 29. van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam (1981), http://turing.wins.uva.nl/∼ peter/
Basing Weak Public-Key Cryptography on Strong One-Way Functions Eli Biham1 , Yaron J. Goren2, , and Yuval Ishai3, 1
Technion, Israel
[email protected] 2 Rosetta Genomic, Israel
[email protected] 3 Technion, Israel and UCLA, USA
[email protected]
Abstract. In one of the pioneering papers on public-key cryptography, Ralph Merkle suggested a heuristic protocol for exchanging a secret key over an insecure channel by using an idealized private-key encryption scheme. Merkle’s protocol is presumed to remain secure as long as the gap between the running time of the adversary and that of the honest parties is at most quadratic (rather than super-polynomial). In this work, we initiate an effort to base similar forms of public-key cryptography on well-founded assumptions. We suggest a variant of Merkle’s protocol whose security can be based on the one-wayness of the underlying primitive. Specifically, using a one-way function of exponential strength, we obtain a key agreement protocol resisting adversaries whose running time is nearly quadratic in the running time of the honest parties. This protocol gives the adversary a small (but non-negligible) advantage in guessing the key. We show that the security of the protocol can be amplified by using a one-way function with a strong form of a hard-core predicate, whose existence follows from a conjectured “dream version” of Yao’s XOR lemma. On the other hand, we show that this type of hard-core predicate cannot be based on (even exponentially strong) one-wayness by using a black-box construction. In establishing the above results, we reveal interesting connections between the problem under consideration and problems from other domains. In particular, we suggest a paradigm for converting (unconditionally) secure protocols in Maurer’s bounded storage model into (computationally) secure protocols in the random oracle model, translating storage advantage into computational advantage. Our main protocol can be viewed as an instance of this paradigm. Finally, we observe that a quantum adversary can completely break the security of our protocol (as well as Merkle’s heuristic protocol) by using the quadratic speedup of Grover’s quantum search algorithm. This raises a speculation that there might be a closer relation between (classical) public-key cryptography and quantum computing than is commonly believed. Keywords: Public-key cryptography, one-way functions, Merkle’s puzzles, bounded storage model, quantum computing.
Most of this work was done while at the Department of Computer Science, Technion. Supported by ISF grant 1310/06, BSF grant 2004361, and NSF grants 0205594, 0430254, 0456717, 0627781, 0716835, 0716389.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 55–72, 2008. c International Association for Cryptologic Research 2008
56
E. Biham, Y. J. Goren, and Y. Ishai
1 Introduction The fundamental cryptographic primitives and protocols can be roughly divided into two categories: “private cryptography” which includes private key encryption, pseudorandom generators, pseudo-random functions, bit commitment and digital signatures, and “public cryptography” which includes public key encryption, key agreement, oblivious transfer, and secure function evaluation. Since the existence of these primitives implies that P=NP, given the current state of complexity theory we need to base it on unproven computational assumptions. These assumptions may turn out to be false; thus, basing primitives on the minimal possible assumptions has been put forward as one of the most important goals in cryptography. The weakest assumption that is commonly used in cryptography is the existence of one-way functions; it is weakest in the sense that if such functions do not exist, none of the above primitives exist [15]. The existence of one-way functions implies the existence of all of the private cryptography primitives (cf. [16,6] and references therein). In contrast, it is not known how to base public cryptography primitives on one-way functions. Obtaining such a construction is arguably one of the most intriguing open questions in cryptography. In addition to its fundamental importance, this question is also motivated by the big efficiency gap between the best current implementations of public primitives and the (much more efficient) implementations of private primitives. This gap is mostly due to the fact that current approaches for obtaining public primitives rely on algebraic intractability assumptions. Since the underlying algebraic objects are highly structured, there are sophisticated attacks that exploit this structure. Thus, the underlying objects must be very large in order to defeat known attacks. An additional, more recent, motivation for basing public cryptography on one-way functions is the advent of efficient quantum algorithms that break most (but not all) of the concrete algebraic intractability assumptions that currently underly public cryptography [22]. In light of the above, basing public-key cryptography on one-way functions can be viewed as a “holy grail” both from a theoretical and from a practical point of view. In fact, from the latter point of view even a heuristic construction based on a random oracle might be considered satisfactory (as the random oracle can often be replaced in practice by a sufficiently “structureless” function). However, a seminal result of Impagliazzo and Rudich [16] suggests that standard methods cannot be used to realize such constructions. Specifically, this result rules out the possibility of a black-box construction based on a one-way permutation (see also [20]). Furthermore, the result of [16] shows that a provable construction of a public-key primitive based on a random permutation oracle is unlikely to be found, as it would imply a proof that P=NP. Weak public-key cryptography. An implicit assumption in the last statements is that the gap between the resources of the honest parties and those of the adversary must be super-polynomial. It is natural to relax this assumption and consider a weaker variant of public-key cryptography, where the resource gap between the adversary and the honest parties is bounded by some fixed polynomial. Such a weaker form of public-key cryptography has a similar qualitative flavor as standard public-key cryptography, and might be relevant to practice. Indeed, even with a quadratic resource gap, the ratio between the amount of time required by the adversary and that required by honest parties
Basing Weak Public-Key Cryptography
57
grows linearly with the computing power. Thus, security gets better with technology. In this work, we study the possibility of basing such weak public-key cryptography on one-way functions and related primitives. Merkle’s puzzles. Our point of departure is the pioneering work of Merkle [19], who proposed the following protocol for secret key agreement over public channels. Merkle’s protocol involves two honest parties, Alice and Bob. It relies on the ability to efficiently create “puzzles” which encapsulate a value chosen by the puzzle creator and require a “moderate” amount of time T to be solved by another party. The protocol proceeds by letting Alice pick a large number S of random pairs (ki , idi ) and send to Bob S puzzles encapsulating these pairs. Bob picks a random puzzle r and, after spending time T solving it, obtains a pair (kr , idr ). It then sends idr to Alice. Now both parties have a common key kr . The time spent by Alice in this protocol is roughly S (assuming that a puzzle can be generated at a unit cost), and the time spent by Bob is roughly T . However, from the point of view of an external eavesdropper Eve, r remains secret. Thus, the intuition is that Eve will need to solve S/2 puzzles on average, spending Ω(ST ) time, before she can learn kr . Setting S = T , both Alice and Bob have a quadratic advantage over Eve. Merkle suggested a heuristic implementation of the puzzles using a weakened version of a private-key encryption scheme, where solving the puzzle amounts to exhaustively searching over a (moderately sized) key space. Trying to instantiate the puzzles in the above protocol using a standard (semantically secure) private-key encryption scheme is problematic for several reasons. First, an implicit assumption that underlies the security of the protocol is that there is a sharp bound T between the maximal time required by honest parties to completely solve a puzzle and the minimal time required by an adversary to gain some information about the solution. One might try to achieve this goal by requiring the encryption to have “exponential strength” in its key size. However, it is not clear how to realize such a strong primitive based on (even strong versions of) low-level primitives such as a one-way function. A second problem is that the security of the resulting protocol seems to rely on the assumption that the adversary has no better strategy for recovering the key kr than by trying to solve the puzzles one by one until finding the one that contains sr . Again, this is an unsubstantiated assumption in a complexity-based cryptography. 1.1 Our Contribution The question whether weak public key cryptography can be based on one-way functions, or some variation of them, is largely unexplored. Our goal is to understand what kinds of weak public key cryptography are possible and under what assumptions. We start by suggesting a variant of Merkle’s protocol which admits a simple proof of security in the random oracle model. In this protocol, each party (independently) evaluates a random permutation on a random set of inputs whose size is roughly the square root of the domain size, and the parties communicate the set of the outputs of these evaluations. By the birthday paradox, the two sets of outputs intersect with high probability, and the preimage of this intersection can be used to extract a common key. (The above protocol can be viewed as based on a similar protocol of Cachin and Maurer [2] in the bounded storage model – see below.)
58
E. Biham, Y. J. Goren, and Y. Ishai
We then show that the random permutation oracle in this protocol can be instantiated with an exponentially strong one-way permutation (OWP), or even an exponentially strong 1-1 OWF, yielding a key agreement protocol with a polynomial gap between the bounded parties and the adversary. Specifically, if the OWP is secure against adversaries that run in time 2(1−δ)n , the protocol is secure as long as the running time of the adversary is less than the running time of the honest parties to the power of 2 − 2δ. Thus, we approach quadratic security as δ tends to 0. Towards obtaining a similar result under any one-way function, we show a way for transforming an exponentially strong OWF into a family of exponentially strong OWFs that are “almost” 1-1. (We stress that this transformation inherently relies on the exponential strength of the underlying OWF; its analysis gives a general method for redistributing the hardness of OWFs which may be of independent interest.) Using this transformation we obtain a similar key agreement protocol based on an exponentially strong OWF. On the existence of strong one-way functions. Our protocols rely on one-way functions whose strength goes beyond the birthday paradox bound of 2n/2 . The existence of such OWFs can be regarded as a very mild assumption from a cryptanalytic point of view. For instance, an explicit attack against AES that runs in time 20.9n , where n is the key size, would be considered as indicating a major vulnerability. Exponentially strong OWFs were recently exploited in several cryptographic contexts. In the context of program obfuscation, Wee [23] uses a OWF with a form of exponential strength which is even stronger than ours in terms of the ratio between the adversary’s time bound and its success probability. OWFs with milder forms of exponential strength were recently employed for constructing pseudorandom generators [14,11,4]. It should be noted that given generic time-space tradeoffs for inverting functions [12,5], one cannot expect a fixed function (rather than a collection of functions) to be non-uniformly one-way with a very good exponential strength (say, better than 22n/3 ). Thus, in the context of this work one should either restrict adversaries to be uniform, or alternatively rely on a collection of strong one-way functions. On reducing the adversary’s advantage. The key agreement protocols described above allow the adversary to gain an inverse polynomial advantage in guessing the secret key. This type of insecurity may be viewed as reasonable in the context of weak public-key cryptography, but it is still desirable to obtain the standard notion of security with negligible advantage with respect to a weaker class of adversaries. Unfortunately, known techniques for converting weak key agreement to strong one (e.g., those of Holenstein [13]) do not seem sufficient for this purpose. We show that the security of the protocol can be boosted to allow only a negligible advantage if one assumes the underlying primitive to have a strong form of a hard-core predicate [8] which we call a multi-source hardcore predicate (MSHCP). Roughly speaking, an MSHCP applies a predicate to several inputs, such that an (exponentially strong) adversary can only predict the value of the predicate on independently chosen inputs with an advantage that is negligible in the size of the input domain. (This should be contrasted with a standard hard-core predicate in which the predicate is applied to a single input, and it is only guaranteed that the advantage is negligible in the bit-length of the input.) We show that the existence of an MSHCP follows from a conjectured “dream version” of Yao’s XOR lemma (a close variant of a conjecture appearing in [9]). On the other hand, we show
Basing Weak Public-Key Cryptography
59
that in contrast to standard hard-core predicates, the existence of an MSHCP cannot be based on (even exponentially strong) one-wayness by using a black-box construction. Our results reveal some interesting and perhaps unexpected connections between the problem under consideration and problems from other domains. Relation with the Bounded Storage Model. In Maurer’s bounded storage model (BSM) [18], it is assumed that a large random source is transmitted, out of which the adversary can only store a limited amount of information. Viewing the random source as an oracle, the transmission of the random source can be replaced by local computation. In terms of security, the resulting model is incomparable to the original BSM: the adversary here is weaker in that it can only access “physical” bits of the source by querying the oracle (rather than store an arbitrary function of the source), but it is stronger in the sense that it is allowed access to the source even after the execution of the protocol. To get around the latter problem, a natural approach is to code the source in the image of the oracle. That is, the evaluation of the oracle f at point x gives a pair (i, b) indicating that the ith bit of the source is b. When the honest parties in the BSM protocol only need to access the source at random locations, the protocol can still be efficiently implemented using the random oracle. Our main protocol can be viewed as applying this conversion paradigm to the BSM protocol from [2]. A similar transformation can be applied to the oblivious transfer protocol from [3] to yield an oblivious transfer protocol (with quadratic security) in the random oracle model. Relation with quantum computing. Finally, we observe that a quantum adversary can completely break the security of our protocol (as well as that of Merkle’s heuristic protocol) by using the quadratic speedup of Grover’s quantum search algorithm [10]. Thus, the two most prominent examples for speedup by quantum algorithms – the strong speedup of Shor’s algorithm and the weaker speedup of Grover’s algorithm – seem to be “tailored” to break the two main types of public-key cryptosystems – strong ones based on number-theoretic assumptions1 and weak ones based on Merkle’s technique. While this can be dismissed as a pure coincidence, it also raises the interesting speculation that there might be a closer relation between (classical) public-key cryptography and quantum computing than is commonly believed. This speculation may be supported by the relative scarcity of useful algorithms in the two domains. It is important to stress that the quadratic speedup that can be achieved using Grover’s algorithm is by no means universal, and applies only in scenarios that involve parallel search. An interesting problem left open by our work is that of obtaining a weak key agreement protocol, even in the random oracle model, that resists this kind of quantum attack. A natural approach for achieving this is by obtaining efficient implementations of puzzles that resist parallel search attacks. A similar problem was considered by Boneh and Naor [1] in the context of timed commitments. However, the only known implementations of this primitive rely on number-theoretic assumptions that do not resist a quantum attack. The possibility of implementing such “non-parallelizable” puzzles using a one-way function, or even a random function, remains open. 1
One should note in this context that we do have candidates for strong public-key cryptosystems that resist quantum attacks, mostly ones based on lattice problems and error-correcting codes. However, because of the strong algebraic structure of the underlying computational problems, the existence of efficient quantum algorithms for these problems does not seem unlikely.
60
E. Biham, Y. J. Goren, and Y. Ishai
Organization. The remainder of this paper is organized as follows. Following some preliminaries, in Section 3 we describe a key agreement protocol based on a random function. The protocol resists adversaries whose running time is nearly quadratic in the running time of the honest parties. In Section 4 we replace the random function with an exponentially strong one-way permutation, and in Section 5 we show how to base a variant of this protocol on an exponentially strong one-way function. Some details and proofs that were omitted from this version can be found in the full version.
2 Definitions In contrast to conventional cryptography, in this work we assume the resource gap between the honest parties and the adversary to be bounded by a fixed polynomial. This requires us to introduce an “exact” variant for some common definitions and to set a concrete model of computation which is sensitive to such gaps. We use a RAM model (e.g., a “log-cost” RAM) as our default model of computation, for both honest parties and adversaries. A T (n)-bounded algorithm is an algorithm whose running time on input of length n is bounded by T (n). Our results are stated for uniform adversaries, but are valid for non-uniform adversaries as well. In this case the bound on the running time serves also as a bound on the size of the advice string given to the adversary. Specific differences between the results for uniform and non-uniform adversaries will be discussed when relevant. Notation. We write f (n) = O(g(n)) if there exists some constant c such that f (n) = c O(g(n) log (g(n))). We say that a function (·) is negligible and denote such a function by neg(·) if for any constant c, (n) < n1c for sufficiently large n. We say that (·) is bounded away from c if (n) ≤ c − 1/p(n) for some polynomial p and all sufficiently large n. We denote by Un the uniform distribution over {0, 1}n. By IP we denote the n modular inner product function defined by IP (x, r) = i=1 (xi · ri ) mod 2. 2.1 Key Agreement Protocols An l(·)-bit key agreement protocol is an interactive protocol in which Alice and Bob receive a security parameter k, exchange messages over a public channel and each output a key in {0, 1}l(k) . Throughout the paper we deal only with 1-bit key agreement as defined below. Our protocols can be extended to l(k)-bit key agreement for any l(k) ≤ polylog(k) with similar asymptotic parameters by independent repetition. (A longer key will reduce the polynomial advantage of the honest parties.) Such an l-bit key can then be used to encrypt longer messages using a (conventional) symmetric encryption scheme. We note that the key agreement protocols presented in this paper are limited to two rounds. Hence what we achieve can be viewed as a (weak) public key encryption scheme, where the first message serves as the public key. Definition 1 (Key agreement). A protocol (Alice, Bob) is a (d, )-secure key agreement protocol if the following conditions hold: – Correctness: Alice and Bob are O(k)-bounded and they output the same bit except for a failure probability δ(k) = neg(k).
Basing Weak Public-Key Cryptography
61
– Security: For any constant d < d and any O(k d )-bounded adversary, for sufficiently large k the probability that the adversary guesses Bob’s output on a random transcript of the protocol is bounded by 12 + (k). We say that the protocol has quadratic security if it is (d, )-secure for d = 2 and some negligible (·). 2.2 Strong One-Way Functions and Hard-Core Predicates Definition 2 (One-way function). An efficiently computable function f : {0, 1}∗ → {0, 1}∗ is a (T, ) one-way function if for any T (n)-bounded adversary A and for all sufficiently large n, P rx∈Un [f (A(1n , f (x))) = f (x)] < (n). If in addition f is a permutation we say that it is a (T, ) one-way permutation. If f is (T, ) one-way with 1 (n) ≤ 16 , we say that it is a T (n) one-way function. We note that a standard one-way function is (nc , n1c ) one-way for every constant c > 1. Definition 3 (Hard-core predicate). An efficiently computable function h : {0, 1}∗ → {0, 1} is a (T, ) (randomized) hard-core predicate for f if for any T (n)-bounded adversary A, for sufficiently large n, P rx∈Un ,r∈Un [A(f (x), r) = h(x, r)] < 1/2 + (n). The following definition generalizes the concept of hard-core predicates to allow the predicate to depend on several pre-images. Definition 4 (Multi-source hard-core predicate). A polynomial time computable function H : {0, 1}∗ → {0, 1} is a (T, ) multi-source (randomized) hard-core predicate (MSHCP) for f if there exist two polynomials t(·) and s(·) such that for any T (n)-bounded adversary A and all sufficiently large n, P rx1 ...xt(n) ∈Un ,r∈Us(n) [A(1n , f (x1 ) . . . f (xt(n) ), r) = H(x1 . . . xt(n) , r)] < 1/2+(n). If H is a (T, ) MSHCP with (n) = neg(2n ) we say that it is a strong MSHCP. Note that a strong MSHCP can be guessed only with an advantage that is negligible in the size of the input domain. This is not possible with standard hard-core predicates since a single invocation of f is enough for finding a pre-image with probability which is the inverse of the input domain size. We also note that it is easy to show that a random function has a strong MSHCP; however, its security does not seem to follow from onewayness alone. A relevant black-box separation is given in the full version.
3 Key Agreement in the Random Oracle Model We describe a variant of Merkle’s key agreement protocol in which all parties have access to a random function oracle, and show that adversaries whose running time is nearly quadratic in the running time of the honest parties can only have a negligible advantage in guessing the agreed key. For simplicity of presentation we assume that
62
E. Biham, Y. J. Goren, and Y. Ishai
the function which the oracle computes is chosen uniformly from some set of functions after the adversary has been set, and in this scenario we bound the adversary’s advantage in guessing the key. This result can be extended, using a standard argument [16], to show that the protocol is secure against any uniform adversary when the oracle is set to a specific function from the set, with probability 1 over the choice of functions. Alternatively, the protocol is secure against non-uniform adversaries when the function is chosen after the adversary is set (i.e. no single non-uniform adversary can break the protocol for a significant fraction of the functions). We start with a protocol which uses an oracle to a random permutation and a random predicate and then extend the result for the case of a random function. The ROM protocol: For a security parameter k we use an oracle to a random permutation f : [k 2 ] → [k 2 ] and a random predicate h : [k 2 ] → {0, 1}. We set a minimal intersection size parameter l(k) to be l(k) = 12 log2 (k). – Alice chooses a random set A ⊂ [k 2 ] of size k · log k, queries the oracle on these inputs and sends f (A) = {f (a)|a ∈ A} to Bob. – Bob chooses a random set B ⊂ [k 2 ] of size k · log k and queries the oracle on these inputs. If |f (A) ∩ f (B)| < l(k) Bob aborts and both parties output random values. Otherwise, Bob randomly chooses l(k) common outputs c1 , . . . , cl(k) ∈ f (A) ∩ f (B) and sends them to Alice. – Alice and Bob find the common inputs s1 , . . . , sl(k) ∈ A ∩ B such that f (si ) = ci and output l(k) i=1 h(si ). In the full version we prove that the above protocol has quadratic security. We also show a similar protocol which uses a random function instead of a permutations and a predicate and prove the following theorem. Theorem 1. Given an oracle to a random function f : {0, 1}∗ → {0, 1}, there exists a key agreement protocol with quadratic security.
4 Key Agreement from One-Way Permutations In order to construct key agreement from one-way permutations we replace the random permutation and random predicate used in the ROM protocol with an exponentially strong one-way permutation and a hard-core predicate. The analysis is divided into two parts: first we show how to construct a key agreement protocol from a one-way permutation with an MSHCP and then we show how to construct an MSHCP for any one-way function. The maximal possible advantage in guessing the MSHCP determines the advantage the protocol allows adversaries in guessing the key. Using a conjectured dream XOR lemma we construct a strong MSHCP (in which the maximal advantage is negligible in the size of the input domain) and hence key agreement protocols in which the adversary’s advantage is negligible. Without this conjecture we do not know how to construct strong MSHCPs, but can get a weaker MSHCP that suffices for limiting the adversary’s advantage to 1/poly(k). In the full version we show that the limitation on the strength of the MSHCP is inherent to black-box constructions.
Basing Weak Public-Key Cryptography
63
The results in this section hold in both uniform and non-uniform settings, depending on the setting in which the permutations are assumed to be one-way. However, it follows from generic time-space tradeoffs for inverting functions [12,5] that one cannot expect a fixed function (rather than a collection of functions) to be non-uniformly one-way with a very good exponential strength. In order to achieve meaningful results in the nonuniform case, one may use a collection of one-way functions in the protocol described in Section 5.4. Finally, we note that the results of this section can be generalized to any 1-1 one-way function. 4.1 Key Agreement from a One-Way Permutation with an MSHCP We use a variant of the ROM protocol in which the random permutation is replaced by a one-way permutation and the random predicate is replaced by an MSHCP. The OWP protocol: For a security parameter k we set n = 2 · log k (i.e. k = 2n/2 ) and use a one-way permutation f : {0, 1}n → {0, 1}n for which H is a (T, ) MSHCP with T = 2n(1−δ) . We set the minimal size of the intersection to be l(k) = t(n) where t(·) is the number of inputs for H as in Definition 4. – Alice chooses a random set A ⊂ {0, 1}n of size k 2l(k), applies f to these inputs and sends f (A) = {f (a)|a ∈ A} to Bob. – Alice also sends Bob a random string r ∈ {0, 1}s(n), where s(·) is the size of the random input for H as in Definition 4. – Bob chooses a random set B ⊂ {0, 1}n of size k 2l(k) and applies f to these inputs. If |f (A) ∩ f (B)| < l(k) Bob aborts and both parties output random values. Otherwise, Bob randomly chooses l(k) common outputs c1 , . . . , cl(k) ∈ f (A) ∩ f (B) and sends them to Alice. – Alice and Bob find the common inputs s1 , . . . , sl(k) ∈ A ∩ B such that f (si ) = ci and output H(s1 , . . . , sl(k) , r). Theorem 2 (Key agreement from a one-way permutation with an MSHCP). For any constant δ < 12 , if there exists a one-way permutation with a (T, ) MSHCP such that T = 2n(1−δ) then there exists a (d, )-secure key agreement protocol with d = 2−2δ. Proof. The proof of correctness is the same as in the ROM protocol. The proof of security is by contradiction. Suppose that for some constant d < 2 − 2δ, an O(k d )1 bounded adversary A guesses the agreed bit with probability at least 2 + when given a random transcript of the protocol. We show how to use A to guess H(x1 , . . . , xl(k) , r), given f (x1 ), . . . , f (xl(k) ) and r on random x1 , . . . , xl(k) ∈ {0, 1}n and r ∈ {0, 1}s(n). We create a random transcript of the protocol using the following procedure: – Randomly choose a set A ⊂ {0, 1}n of size k 2l(k) − l(k), and apply f to these inputs. Randomly interleave f (x1 ), . . . , f (xl(k) ) within the set f (A) and use the result as the first part of Alice’s message to Bob. – Use the random string r as the second part of Alice’s message to Bob. – Use f (x1 ), . . . , f (xl(k) ) as Bob’s message to Alice. It is easy to verify that the result is indeed distributed identically to a random transcript created by Alice and Bob. We then apply A to the transcript and output the same bit as
64
E. Biham, Y. J. Goren, and Y. Ishai
A does. By our assumption A’s output is equal to H(x1 , . . . , xl(k) , r) with probability at least 12 + . The transcript can be created in time O(k) and since δ < 12 , for large enough n the total running time is bounded by k 2−2δ = 2n(1−δ) , contradicting the hardness of H. 4.2 Construction of an MSHCP for any One-Way Function We first construct a (single-source) randomized hard-core predicate defined by h(x, r) = IP (x, r) for a random r and prove its security using an exact version of the GoldreichLevin lemma. Then t we use h to construct an MSHCP defined by H((x1 , . . . , xt ), (r1 , . . . , rt )) = i=1 h(xi , ri ) and prove its security using an exact version of Yao’s XOR lemma. Lemma 1 (Goldreich-Levin). If f is a (T, ) one-way function then h(x, r) = IP (x, r) (where IP denotes inner product modulo 2) is a (T , ) randomized hard4 core predicate for f with T (n) = T (n) · n 3 and (n) = 4. The lemma follows from the alternative version of Proposition 2.5.3 in [7]. A consequence of this lemma is that every T (n) one-way function has a (T , ) (randomized) hard-core predicate with T = T (n)/poly(n) and = 1/4. Definition 5 (Hard predicate). We say that P : {0, 1}∗ → {0, 1} is a (T, ) hard predicate if for any T (n)-bounded adversary A and all sufficiently large n, P rx∈Un [A(x) = P (x)] < 1/2 + (n). Lemma 2 (Yao’s XOR lemma). If P is a (T, ) hard predicate and it is possible to efficiently sample from the distribution (Un , P (Un )), then for any μ(n) and t = poly(n), t μ2 P (t) (x1 , . . . , xt ) = i=1 P (xi ) is a (T , ) hard predicate for T = T · poly(n) − poly(n) and = (2)t + μ. The lemma can be derived by a careful analysis of Levin’s proof for Yao’s XOR lemma given in [17,9]; see full version. Combining Lemma 1 with Lemma 2 allows us to construct an MSHCP but there is an inherent limitation to the strength of the MSHCP which we may construct in this way. A (T , ) hard predicate constructed using Lemma 2 has the property that > μ and T < T · μ2 . For any (T, ) hard-core predicate for n ) since it is possible to invert an efficiently computable one-way function, T = O(2 the one-way function by an exhaustive search. For our key agreement protocol we need a (T , ) MSHCP in which T = 2(1−δ)n for some δ < 12 . Any (T , ) MSHCP constructed under the above restrictions will have > μ > T /T > 2−n/4 . The following conjecture allows us to construct a (T , ) hard predicate with = neg(2n ) while T remains close to T , and thus can be used to construct a strong MSHCP. Conjecture 1 (Dream XOR lemma). If P is a (T, ) hard predicate for some that is bounded away from 12 and it is possible to efficiently sample from the distribution (Un , P (Un )), then there exists a constant c < 1, a negligible μ(·) and some η(·) which from 1 such that for any t = poly(n), P (t) (x1 , . . . , xt ) = t is bounded away −o(n) and = 2cn · η t + μ(2n ). i=1 P (xi ) is a (T , ) hard predicate for T = T · 2
Basing Weak Public-Key Cryptography
65
A similar “dream version” of Yao’s XOR lemma was conjectured in [9] and it was observed that it can not be proved using a black-box analysis. (The variant appearing in [9] requires to be smaller but allows T to be smaller as well.) Theorem 3 states the parameters of MSHCP that can be obtained with and without the dream XOR lemma conjecture, while in the full version we show that a strong MSHCP cannot be obtained from a OWF using a black-box construction. We apply Lemma 2 and Conjecture 1 with t = poly(n) to the predicate defined in Lemma 1 to get the following result (smaller values of t suffice for the first two cases, but this does not improve the asymptotic result). Theorem 3. For any δ < 1, every 2n(1−δ) one-way function has a (T, ) MSHCP with the following T and : 1 - T = 2n(1−δ) /poly(n) = poly(n) using μ = O() n(1−δ−τ ) −τ n/2 -T =2 /poly(n) =2 using μ = O(2−τ n/2 ) n(1−δ) o(n) n /2 = neg(2 ) assuming the dream XOR lemma -T =2 It is easy to verify that Theorem 2 holds also when T = 2n(1−δ) is replaced with 2n(1−δ) /2o(n) . Combining this with Theorem 3 we get the main result regarding the construction of key agreement from one-way permutations. It relates the strength of the underlying one-way permutation to the security of the key agreement protocol that can be constructed from it. Corollary 1. For any constant δ < 12 if there exists a 2n(1−δ) one-way permutation then there exists a (d, ) secure key agreement protocol for the following d and : - d = 2 − 2δ = 1/ logc k for any constant c - d = 2 − 2δ − 2τ = k −τ for any τ < 1 − δ - d = 2 − 2δ = neg(k) assuming the dream XOR lemma
5 Key Agreement from One-Way Functions We extend the result from the previous section to obtain weak key agreement from exponentially strong one-way functions. The main technical result in this section is a construction of a collection of one-way functions which is almost 1-1 from an exponentially strong one-way function which is not necessarily 1-1. The construction applies a restriction to the domain of the one-way function such that the restricted function usually remains one-way and is almost always 1-1. The resulting collection of one-way functions is then used to construct a key agreement protocol. The results in this section hold in both uniform and non-uniform settings, depending on the setting in which the functions are assumed to be one-way. We refer to the uniform setting by default. 5.1 Definitions A collection of one-way functions is defined by a pair of functions G and F such that G(1n ) generates a key i of length l(n) which defines a function fi : {0, 1}n → {0, 1}∗ and F (i, x) computes fi (x). Definition 6 (Collection of one-way functions). Let F = Fn be a collection of functions where Fn = {fi : {0, 1}n → {0, 1}∗|i ∈ In }. We say that F is (T, ) one-way if there exist two PPT algorithms G and F such that the following holds:
66
E. Biham, Y. J. Goren, and Y. Ishai
1. Easy to compute: There exists a polynomially bounded function l(·) such that the output of G on input 1n is in the set In ⊆ {0, 1}l(n). On input i ∈ In and x ∈ {0, 1}n, F (i, x) = fi (x). 2. Hard to invert: For every T (n)-bounded adversary A, for all sufficiently large n’s, P ri∈G(1n ),x∈Un [fi (A(1n , i, fi (x))) = fi (x)] < (n). We say that F is T (n) one-way if it is (T, ) one-way with ≤ 1/32. We say that F is almost 1-1 if the probability that fi ∈ Fn is not 1-1 is bounded by 2−n . We will be using a family of injective length-increasing, pairwise independent hash functions in order to restrict the domain of a one-way function and increase the probability that it is 1-1. The function m(·) in the definition below determines the length of the output of the hash functions relative to the input length. Definition 7 (m(·) pairwise independent family of hash functions). Let H = Hn be a collection of functions where Hn = {hi : {0, 1}n → {0, 1}m(n)|i ∈ In }. We say that H is a m(·) pairwise independent family of hash functions if there exist two PPT algorithms G and H such that the following holds: 1. Easy to compute: There exists a polynomially bounded function l(·) such that the output of G on input 1n is in the set In ⊆ {0, 1}l(n). On input i ∈ In and x ∈ {0, 1}n, H(i, x) = hi (x). 2. Pairwise independent: For every x1 = x2 ∈ {0, 1}n and y1 = y2 ∈ {0, 1}m, P rh∈Hn [h(x1 ) = y1 ] = 21m and P rh∈Hn [h(x2 ) = y2 | h(x1 ) = y1 ] = 2m1−1 . Definition 7 can be instantiated with the collection of functions of the form ha,b (x) = ax + b where a, b ∈ GF(2m ), a = 0, both addition and multiplication are over GF(2m ), and every x is interpreted as a distinct element of the subfield GF(2n ). Definition 7 implies that each function from the collection must injective. Moreover, it also implies the following balance property that will be useful in our analysis: For every n and every n y ∈ {0, 1}m(n), P rh∈Hn [∃x such that y = h(x)] = 22m . 5.2 Restricted Exponentially Strong One-Way Functions are 1-1 We show that strong one-way functions do not have many collisions to begin with (Lemma 3), and that by restricting the domain of such a function we get a function which is 1-1 with high probability (Theorem 4). Definition 8 (Collision group of y relative to f ). [y]f = {y |f (y ) = f (y)} We denote the input length of the one-way function in the following lemma by m, as we will use n for the input length of the family of one-way functions that we construct. Lemma 3 (Exponentially strong one-way functions have few collisions). If f is a (T, ) one-way function then there exists a polynomial t(·) such that for sufficiently large m and for every y ∈ {0, 1}m, |[y]f | ≤ 2m · max{2(m), t(m)/T (m)}.
Basing Weak Public-Key Cryptography
67
Proof. We give the proof for the uniform setting, for the non-uniform case a stronger version of the lemma can be proved using the fact that a pre-image for y ∗ defined below can be given to the algorithm as advice. Let t(·) be the time required for evaluation of f . Assume for contradiction that the statement does not hold for y ∗ . We first show a T (m)-bounded algorithm that finds a pre-image for f (y ∗ ) with probability 12 . Randomly choose y1 , . . . , yT /t ∈ {0, 1}m and apply f to them. By the assumption |[y ∗ ]f | > 2m · t/T , hence for each i, yi ∈ [y ∗ ]f with probability at least t/T . Therefore the probability that there is no i for which xi ∈ [y ∗ ]f is at most (1 − t/T )T /t < 12 . By the assumption |[y ∗ ]f | > 2m · 2, therefore y ∈ [y ∗ ]f with probability at least 2. If indeed y ∈ [y ∗ ]f , finding a pre-image for f (y) is the same as finding a pre-image for f (y ∗ ) and the algorithm described above will find a pre-image with probability at least 12 . The conclusion is that there exists a T (m)-bounded adversary which finds a pre-image for f (x) on a random x with probability , contradicting the fact that f is a (T, ) one-way function. def
Notation. From here on we let fh (·) = f (h(·)). Theorem 4 (Restricted exponentially strong one-way functions are 1-1). If H = Hn is an m(·) pairwise independent family of functions and f is a (T, ) one-way function with T (m) ≥ 2μ·m and (m) ≤ 2−μ·m for some μ > 0, then the probability over h ∈ Hn that fh is not 1-1 is bounded by poly(m) · 22n−μm . Proof. Fix x1 = x2 ∈ {0, 1}n. We bound the probability that fh maps both inputs to the same image for a random h ∈ Hn . P rh∈Hn [fh (x1 ) = fh (x2 )] = P rh∈Hn [h(x2 ) ∈ [h(x1 )]f ] =
P rh∈Hn [h(x1 ) = y1 ] · P rh∈Hn [h(x2 ) ∈ [y1 ]f | h(x1 ) = y1 ]
y1 ∈{0,1}m
=
P rh∈Hn [h(x1 ) = y1 ] ·
y1 ∈{0,1}m
≤ 2m · 2−m · 2m · max{2, poly(m)/T } · ≤ 2−μ·m · poly(m)
P rh∈Hn [h(x2 ) = y2 | h(x1 ) = y1 ]
y2 ∈[y1 ]f
1 2m − 1
(1) (2)
where (1) follows from the pairwise independence of H and from Lemma 3, and (2) follows from the hypothesis of the theorem about and T . As there are 22n pairs of inputs in {0, 1}n, by a union bound the probability that hf maps any two inputs of length n to the same output is bounded by poly(m) · 22n · 2−μ·m . 5.3 Restricted Exponentially Strong One-Way Functions are One-Way We show that if f is a strong one-way function and H is a pairwise independent family of hash functions, then F = {fh | h ∈ H} is a collection of strong one-way functions. The idea is that if we have an algorithm that finds a pre-image for z = fh (x) given z and h for a random h and x, we can use it to find a pre-image for z = f (y) for a random
68
E. Biham, Y. J. Goren, and Y. Ishai
y in the following way. We randomly select sufficiently many functions h ∈ H so that one of them will have y in its range, and apply the inversion algorithm to z and each such h. If the algorithm succeeds, we get some x such that fh (x) = f (h(x)) = z and h(x) is a pre-image of z under f . This approach gives the following theorem. Theorem 5. Suppose f is (T, ) one-way and H is a m(·) pairwise independent family of functions. Then F = {fh | h ∈ H} is a (T , ) one-way collection of functions for any T , such that for all sufficiently large n the following conditions hold with m = m(n): 1. T (n) ≤ 12 · T (m) 2. (n) ≥ 2 · (m) n (n) (m) 3. T (n) ≤ 14 · 22m · T(m) c 4. T (n) > m(n) for every constant c Proof. Throughout the proof we view T and as functions of n and T and as functions of m (where m is itself a function of n). We omit m and n in order to simplify notation. Assume for contradiction that f is a (T, ) one-way function, but F is not a (T , ) one-way collection for T, T , , as stated in the theorem. By Definition 6 there exists a T -bounded adversary A such that for infinitely many n’s P rh∈Hn ,x∈Un [fh (A (1n , fh (x), h)) = fh (x)] ≥ . We construct a T -bounded algorithm A such that for infinitely many m’s P ry∈Um [f (A(1m , f (y))) = f (y)] ≥ , in contradiction with the assumption that f is (T, ) one-way. The algorithm A, described below, finds a pre-image for z = f (y). On input (1m , z), T A repeats the following steps t = 2T times: 1. Choose a random h ∈ Hn . 2. Compute x = A (1n , z, h) 3. If fh (x) = z stop and output h(x) Assuming z = f (y), we define the random variables Ai (y) and Bi (y) for i = 1, . . . , t as follows: Ai (y) = 1 if in the i’th iteration there exists a pre-image for y under h, and Bi (y) = 1 if in the i’th iteration fh (x) = f (y). (Probabilities in these variables are taken over the random coins of A.) The following two claims allow us to complete the proof of Theorem 5. Claim 1. P ry∈Um [∃i : Ai (y) = 1] ≥
Claim 2. For every i, P ry∈Um [Bi (y) = 1 | Ai (y) = 1] ≥ By the above claims and the definitions of Ai and Bi , we can lower bound the probability that A finds a pre-image for f (y). P ry∈Um [f (A(1m , f (y))) = f (y)] = P ry∈Um [∃i : Bi (y) = 1] ≥ P r[∃i : Ai (y) = 1] · P r[Bi (y) = 1 | Ai (y) = 1] ≥ · = A’s running time in every iteration is bounded by T + mc for some constant c. As there T T are t = 2T > mc the total running time is bounded by 2T iterations and T · (T + c m ) < T , contradicting the assumption that f is (T, ) one-way.
Basing Weak Public-Key Cryptography
69
Proof of Claim 1. We show that for any fixed y ∈ {0, 1}m, P r[∃i : Ai (y) = 1] ≥ and the claim follows. By the balance property we have P r[Ai (y) = 1] = P rh∈Hn [∃x n T such that y = h(x)] = 22m for every i = 1, . . . , t. We view A1 , . . . , At as t = 2T 2n independent experiments, each with success probability δ = 2m . The probability that 1 none of the experiments succeed can be bounded by (1 − δ)t < tδ+1 . Therefore P r[∃i : 1 tδ Ai (y) = 1] ≥ 1 − tδ+1 = tδ+1 . If tδ > 1, P r[∃i : Ai (y) = 1] ≥ 12 ≥ , otherwise, 1 2n T P r[∃i : Ai (y) = 1] ≥ t·δ 2 = 4 · 2m · T ≥ . In both cases the last inequality follows from the assumptions in the hypothesis of the theorem. Proof of Claim 2. We use the following notation: p1 P ry∈Um [Bi (y) = 1 | Ai (y) = 1] p2 P rh∈Hn ,y∈Um [fh (A (1n , f (y), h)) = f (y) | ∃x : y = h(x)] p3 P rh∈Hn ,x∈Un [fh (A (1n , fh (x), h)) = fh (x)] By the definition of Ai and Bi we have p1 = p2 for every i, and by our assumption that F is not (T , ) one-way, we have p3 ≥ . Since Claim 2 is that p1 ≥ for every i, it remains to show that p2 = p3 . We show this by proving that the pair (y, h) under the conditions in p2 is distributed identically to the pair (h(x), h) under the conditions in p3 . Fix some (y, h) such that y is in the range of h. We calculate the probability of getting this pair under both distributions. Under the conditions in p2 , y is chosen uniformly n from a set of size 2m and h is chosen uniformly from a set of size 22m |Hn |, altogether the probability is |Hn1|2n . Under the conditions in p3 , h is chosen uniformly from a set of size |Hn | and x is chosen from a set of size 2n . Since h is 1-1, the probability for getting y = h(x) is 2−n , thus the overall probability is again |Hn1|2n . The above construction allows us to ‘redistribute’ the hardness of a one-way function. For example a (T, ) one-way function which is strongly secure (small ) against weak adversaries (small T ) can be used to construct a (T , ) one-way function family F that is weakly secure against strong adversaries. The conditions in the theorem give us the boundaries of the possible redistribution. Condition 1 limits the maximal gap between T and T . Condition 2 does the same for . Both conditions are easy to satisfy when m(·) is large. Condition 3 defines the loss in the time over success ratio caused by the (n) transformation. The loss is bigger when m(·) is large. For m = c · n, if T(n) = 2n(1−δ) we will get
T (n) (n)
< 2n(1−cδ) .
Corollary 2. If there exists a (T, ) one-way function with T, −1 ≥ 2m/3 and T / ≥ 2m(1−δ) then there exists a collection of 2n(1−10δ) one-way functions which is almost 1-1. Proof. By applying Theorem 4 to the family H of m(·) pairwise independent family of hash functions with m = 9n and a one-way function f , we get a family F = {fh |h ∈ H} which is 1-1, except for probability at most 2−n . F is 2n(1−10δ) one-way if it is (T , ) one-way with T = 2n(1−10δ) and = 1/32 and it remains to verify that for sufficiently large n, the conditions of Theorem 5 are fulfilled. 1. T (n) = 2n(1−10δ) <
1 2
· 23n =
1 2
· 2m/3 ≤
1 2
· T (m)
70
E. Biham, Y. J. Goren, and Y. Ishai
2. (n) = 3.
T (n) (n)
1 32
> 2 · 2−m/3 ≥ 2 · (m) n
n
(m) = 32·2n(1−10δ) < 14 ·2n(1−9δ) = 14 ·2n−δm = 14 · 22m ·2m(1−δ) ≤ 14 · 22m · T(m)
4. T (n) = 2n(1−10δ) > (9n)c = mc
We note that in the non-uniform setting the parameters in the corollary can be improved by using a stronger version of Lemma 3. 5.4 Key Agreement from a Collection of 1-1 One-Way Functions We show a key agreement protocol which is based on a collection of one-way functions F which is almost 1-1. The protocol is similar to the one described for constructing key agreement from a one-way permutation. However, there are two obstacles which prevent us from directly applying the previous protocol to a random fi ∈ F. First, unlike one-way permutations, fi ∈ F is not always 1-1 and hence Alice and Bob may have different outputs. Second, since F is hard to invert only on average, it is possible that a specific function fi ∈ F is easy to invert. We use standard techniques for amplifying both correctness and security. Specifically, we begin by describing a basic protocol which in itself lacks in both security and in correctness. By combining several copies of the basic protocol we create an intermediate protocol which is secure but has a big error probability. By combining several copies of the intermediate protocol we get the final protocol which is both secure and correct. We note that the copies of the basic protocol can be run concurrently and hence the final protocol remains a two message protocol. The basic protocol. Let F = Fn , be a collection of 2n(1−δ) one-way functions which is almost 1-1. For a security parameter 1k , we set n = 2 · log k. In each copy of the protocol, Alice chooses a random r ∈ {0, 1}n, a random index i ∈ In which defines a function fi ∈ Fn and a random set A ⊂ {0, 1}n of size k · logk. She applies fi to the inputs in A, and sends the outputs i and r to Bob. Bob randomly chooses a similar set of inputs B, and applies fi to them. If f (A) ∩ f (B) = ∅, he aborts and both parties output random values; otherwise, he randomly chooses a common output c ∈ f (A)∩f (B) and sends c to Alice. Alice and Bob each identify a source for the common input, xA ∈ A and xB ∈ B, so that fi (xA ) = fi (xB ) = c. Their outputs are sA = IP (xA , r) and sB = IP (xB , r) respectively. The intermediate protocol. We denote Alice and Bob’s outputs in the i’th copy of the basic protocol by siA and siB . The intermediate protocol consists of l = polylog(k) l i copies of the basic protocol, where Alice and Bob’s outputs are SA = i=1 sA and l SB = i=1 siB respectively. The final protocol. We denote Alice and Bob’s outputs in the i’th copy of the intermei i diate protocol by SA and SB . The final protocol consists of l = polylog(k) copies of the intermediate protocol with the following addition to Bob’s messages. Bob chooses i a random S ∈ {0, 1} and for each copy of the intermediate protocol sends S SB to i i l Alice. Bob’s output is S and Alice’s output is M AJ{S SA SB }i=1 . A straightforward analysis of the final protocol (appearing in the full version) gives the following theorem:
Basing Weak Public-Key Cryptography
71
Theorem 6 (Key agreement from a collection of one-way functions which is almost 1-1). For any constant δ < 1/2, if there exists a collection of 2n(1−δ) one-way functions which is almost 1-1, then there exists a (d, ) secure key agreement protocol for the following d and : - d = 2 − 2δ = 1/ logc k for any constant c - d = 2 − 2δ − 2τ = k −τ for any τ < 1 − δ - d = 2 − 2δ = neg(k) assuming the dream XOR lemma Combining Theorem 6 with Corollary 2, we get our main result on weak public-key cryptography from strong one-way functions. Corollary 3 (Key agreement from one-way functions). For any constant δ < 1/10, if there exists a (T, ) one-way function with T, −1 ≥ 2m/3 and T / ≥ 2m(1−δ) then there exists a (d, ) secure key agreement protocol for the following d and : - d = 2 − 20δ = 1/ logc k for any constant c - d = 2 − 20δ − 2τ = k −τ for any τ < 1 − 10δ - d = 2 − 20δ = neg(k) assuming the dream XOR lemma
6 Conclusions and Open Problems We established the feasibility of basing weak public-key cryptography on strong, but arguably reasonable, forms of one-way functions. We leave open the possibility of basing weak public-key cryptography on standard (polynomially strong) one-way functions, as well as the possibility of amplifying the security of our protocols without relying on a conjectured dream version of Yao’s XOR Lemma. Finally, an interesting open question that was already discussed in the Introduction is the possibility of resisting quantum attacks in our setting. The discussion in Section 1.1 referred to the case where the honest parties are classical and the adversary is quantum. If the honest parties are quantum (and can therefore also exploit the quadratic speedup of Grover’s algorithm), it seems possible to retain some of the efficiency gap between the honest parties and the adversary. Setting T = S 2 in the description of Merkle’s protocol from Section 1, honest quantum parties can run in time O(T ) whereas a quantum adversary needs to run in time Ω(T 3/2 ). The optimality of this gap, as well as the possibility of basing it on (quantum) one-way functions, remain to be further studied. Acknowledgement. We thank the anonymous referees for helpful suggestions and comments.
References 1. Boneh, D., Naor, M.: Timed Commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000) 2. Cachin, C., Maurer, U.: Unconditional Security Against Memory-Bounded Adversaries. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 292–306. Springer, Heidelberg (1997)
72
E. Biham, Y. J. Goren, and Y. Ishai
3. Ding, Y., Harnik, D., Shaltiel, R., Rosen, A.: Constant-Round Oblivious Transfer in the Bounded Storage Model. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, Springer, Heidelberg (2004) 4. Dubrov, B., Ishai, Y.: On the randomness complexity of efficient sampling. In: Proceedings of STOC 2006, pp. 711–720 (2006) 5. Fiat, A., Naor, M.: Rigorous Time/Space Trade-offs for Inverting Functions. SIAM J. Comput. 29(3), 790–803 (1999) 6. Gertner, Y., Kannan, S., Malkin, T., Reingold, O., Viswanathan, M.: The Relationship between Public Key Encryption and Oblivious Transfer. In: Proc. of the 41st Annual Symposium on Foundations of Computer Science (FOCS) (2000) 7. Goldreich, O.: Foundations of Cryptography Basic Tools. Cambridge University Press, Cambridge (2001) 8. Goldreich, O., Levin, L.: A Hard-Core Predicate for all One-Way Functions. In: STOC 1989, pp. 25–32 (1989) 9. Goldreich, O., Nisan, N., Wigderson, A.: On Yao’s XOR lemma. Technical Report TR95-50, Electronic Colloquium on Computational Complexity (1995) 10. Grover, L.: A Fast Quantum Mechanical Algorithm for Database Search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, May 1996, p. 212 (1996) 11. Haitner, I., Harnik, D., Reingold, O.: Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 228–239. Springer, Heidelberg (2006) 12. Hellman, M.E.: A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory IT-26(4), 401–406 (1980) 13. Holenstein, T.: Key Agreement from Weak Bit Agreement. In: Proceedings of STOC 2005, pp. 664–673 (2005) 14. Holenstein, T.: Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 443–461. Springer, Heidelberg (2006) 15. Impagliazzo, R., Luby, M.: One-Way Functions are Essential for Complexity-Based Cryptography. In: 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 230– 235. IEEE, Los Alamitos (1989) 16. Impagliazzo, R., Rudich, S.: Limits on the Provable Consequences of One-way Permutations. In: Proceedings of the ACM Symposium on Theory of Computing, pp. 44–61 (1989) 17. Levin, L.A.: One-Way Functions and Pseudorandom Generators. Combinatorica 7(4), 357– 363 (1987) Earlier version in STOC 1985 18. Maurer, U.: Conditionally-Perfect Secrecy and a Provably Secure Randomized Cipher. Journal of Cryptology 5(1), 53–66 (1992) 19. Merkle, R.: Secure communications over insecure channels. CACM, 294–299 (April 1978) 20. Reingold, O., Trevisan, L., Vadhan, S.: Notions of Reducibility between Cryptgraphic Primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004) 21. Rudich, S.: Limits on the Provable Consequences of One-way Functions. Ph.D. thesis 22. Shor, P.W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantom Computer. SIAM J. Comp. 26(5), 1484–1509 (1997) 23. Wee, H.: On obfuscating point functions. In: STOC 2005, pp. 523–532 (2005)
Which Languages Have 4-Round Zero-Knowledge Proofs? Jonathan Katz Department of Computer Science University of Maryland
[email protected]
Abstract. We show that if a language L has a 4-round, black-box, computational zero-knowledge proof system with negligible soundness error, ¯ ∈ MA. Assuming the polynomial hierarchy does not collapse, this then L means in particular that NP-complete languages do not have 4-round zero-knowledge proofs (at least with respect to black-box simulation).
1
Introduction
A zero-knowledge proof system [23] for a language L is a protocol that enables a prover P to convince a polynomial-time verifier V that a given instance x is indeed a member of L. Roughly speaking, the guarantees provided are: Completeness: If x ∈ L then the honest prover P will convince the honest verifier V to accept, except possibly with some small probability. If P always convinces V to accept when x ∈ L then we say the proof system has perfect completeness. Soundness: If x ∈ L a cheating prover P ∗ will be unable to falsely convince the honest verifier that x is in L, except with some small probability known as the soundness error. Zero knowledge: When x ∈ L and the prover is honest, even a malicious verifier V ∗ “learns nothing” beyond the fact that x ∈ L. There are various ways of formalizing the above properties. In this paper, we are interested in the case when the soundness property holds against all-powerful provers — i.e., we focus on proofs rather than arguments [13] — and we are interested in proof systems with negligible soundness error. For the proof system to be non-trivial, the completeness error should not be too large; we will consider both the case of perfect completeness as well as the case when, for x ∈ L, the honest verifier accepts with some noticeable (i.e., inverse polynomial) probability. Finally, we focus on the case of computational zero knowledge (CZK) where, informally, the requirement is that a non-uniform polynomial-time cheating verifier learns nothing from the interaction. (Formal definitions are provided
This work was supported by NSF CAREER award #0447075 and US-Israel Binational Science Foundation grant #2004240.
R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 73–88, 2008. c International Association for Cryptologic Research 2008
74
J. Katz
in Section 2.) We let CZK denote the class of languages that admit a computational zero-knowledge proof system. In this paper we study the round complexity of CZK proof systems, where a round consists of a message sent from one party to the other and we assume that the prover and the verifier speak in alternating rounds. We briefly survey what is known in this regard: Unconditional constructions. The only languages currently known to be in CZK unconditionally are those that admit statistical zero-knowledge (SZK) proofs [23] where, informally, even an all-powerful cheating verifier learns nothing from its interaction with the prover; we denote the class of languages admitting statistical zero-knowledge proofs by SZK. While it is not known1 whether all languages in SZK have constant-round statistical zero-knowledge proof systems, such proof systems are known for specific languages. In particular, graph nonisomorphism [21] (cf. [21, Remark 12]) as well as languages related to various number-theoretic problems [23,30,34,15,31,14] have 4-round SZK proof systems, and graph isomorphism [7] has a 5-round SZK proof system. Constructions based on one-way functions/permutations. Assuming the existence of one-way functions, every language in NP has an ω(1)-round CZK proof system where the honest prover runs in polynomial time given an NPwitness for the statement being proved [21]. (Actually, this result holds for MA as well.2 ) If no computational restrictions are placed on the honest prover, then any language in AM has an ω(1)-round CZK proof system under the same assumption, and any language in IP = PSPACE has a CZK proof system with polynomially-many rounds [29,10]. Assuming the existence of one-way permutations, Feige and Shamir [17] show a 4-round computational zero-knowledge argument for any language in NP. Their techniques yield a 5-round CZK argument based on one-way functions, and this was later improved to 4 rounds by Bellare et al. [6]. Constructions based on stronger assumptions. Assuming the existence of a two-round statistically-hiding commitment scheme, there exists a 5-round CZK proof system for any language in NP [19] (or even AM if the honest prover can be unbounded. (More generally, given a constant-round statistically-hiding commitment scheme, there exists a constant-round CZK proof system for any language in AM.( Two-round statistically-hiding commitment schemes, in turn, can be constructed based on a variety of number-theoretic assumptions [12,13,24] or the existence of collision-resistant hash functions [16,28]. Although statistically-hiding commitment schemes can be constructed from any one-way function [27], constructions of constant-round statistically-hiding commitment schemes from one-way functions are unlikely to exist [26]. 1
2
The constant-round proofs in [8], based on specific number-theoretic assumptions, consider a weaker variant of SZK where the verifier is assumed to run in polynomial time during its interaction with the prover. See also [35]. The class MA is defined in Section 2. AM denotes the class of languages having constant-round Arthur-Merlin proofs.
Which Languages Have 4-Round Zero-Knowledge Proofs?
75
Lower bounds. Goldreich and Oren [22] show that 2-round CZK proofs exist only for languages in BPP. (Their result applies to auxiliary-input zero knowledge proofs, the type we will be concerned with here as well.) Extending this result, Goldreich and Krawczyk [20] show that 3-round black-box CZK proofs exist only for languages in BPP. (A definition of black-box CZK is given in Section 2.) Both these results hold for arguments as well as proofs. Pass [33] gives evidence of the difficulty of showing a black-box construction of a constant-round CZK proof for NP based on any one-way function (even if non black-box simulation is allowed). We refer to his paper for a precise statement of this result. 1.1
Our Result
We show that 4-round black-box CZK proofs, even with imperfect completeness, exist only for languages whose complement is in MA. This result is unconditional, and holds independent of any cryptographic assumptions one might make. Other than the fact that the bound holds only with respect to black-box simulation, this result is essentially the best one could hope for: – Under widely-believed number-theoretic assumptions, there exist 5-round CZK proofs for all of NP [19]. Assuming the polynomial hierarchy does not collapse [11], our result indicates that the round complexity in this case is optimal. – Our result applies only to proofs, but not arguments. Indeed, as noted earlier, there exist 4-round CZK arguments for all of NP under relatively weak assumptions [17,6]. – There exist unconditional constructions of 4-round CZK proofs for languages believed to be outside of BPP, such as graph non-isomorphism [21]. We remark also that for the case of uniform zero-knowledge (i.e., protocols which are zero knowledge for uniform polynomial-time verifiers), a 4-round protocol for all of NP is possible [19] assuming the existence of 1-round statisticallyhiding commitment schemes (that are computationally binding for uniform adversaries). Besides shedding further light on the finer structure of the class CZK, our result indicates that (black-box) 4-round CZK proofs for all of NP are impossible and so the round complexity of the Goldreich-Kahan protocol [19] is optimal. Our result also gives an “explanation” as to why the known SZK proof for graph isomorphism requires five rounds [7] even though graph non-isomorphism has a 4-round SZK proof [21]. Limitations of black-box impossibility results. We prove our result only for the case of black-box zero-knowledge protocols. The work of Barak [3], however, shows that black-box impossibility results and lower bounds need not carry over to the general case.3 Nevertheless, black-box bounds are useful insofar as they 3
Barak’s work gives a constant-round, public-coin, CZK argument for all of NP, something that was ruled out with respect to black-box simulation by Goldreich and Krawczyk [20].
76
J. Katz
rule out a particular approach for solving a problem. We remark further that many of the known (natural) zero-knowledge proofs are in fact black-box zero knowledge; in particular, the protocols of Barak [3] as well as those based on “knowledge of exponent” assumptions [25,9] are zero-knowledge arguments. On the other hand, non black-box zero-knowledge proofs using four or fewer rounds are known to exist based on various non-standard assumptions [5,32]. Our current ability to prove general (as opposed to black-box) lower bounds for zero-knowledge protocols is, unfortunately, relatively limited [22,5]. High-level overview of our technique. Our lower bound for 4-round protocols is proved by extending the Goldreich-Krawczyk lower bound [20] for 3-round protocols. (We assume familiarity with their proof in what follows.) To prove their result, Goldreich and Krawczyk consider a cheating verifier V ∗ who generates its message, in the second round of the protocol, using fresh random coins that are determined as a function of the prover’s first message. On an intuitive level this means that rewinding is useless because every time V ∗ is rewound, and a different first message is sent by the simulator, it is as if the protocol execution is being started again from scratch. We use the same basic idea, now applied to the verifier’s message sent in the third round of the protocol. A problem is that the verifier’s first-round message may “commit” the verifier, in a computational sense, to only one possible third-round message. (Roughly speaking, the verifier cannot be committed in an information-theoretic sense because then an all-powerful prover could guess the third-round message in advance based on the first-round message alone. This is one reason why our result applies only to proofs, and not arguments.) For this reason, we use some “all-powerful” entity to provide the verifier with collisions, i.e., multiple third-round messages consistent with the same first-round message. This idea was directly inspired by the recent work of Haitner et al. [26], who use such collisions to prove lower bounds on the round complexity of blackbox constructions of interactive protocols in other settings. In their work, an oracle provides collisions. Here, we do not have an oracle; instead, we have an all-powerful prover that provides collisions as part of an interactive MA-proof for some language. See Section 3 for further intuition, as well as the details of the proof. 1.2
Outline of the Paper
Standard definitions, as well as some terminology specific to this paper, are provided in Section 2. In Section 3 we prove our result for the case of CZK proof systems with perfect completeness. Technical modifications necessary to deal with the case of imperfect completeness are deferred to Section 4. We conclude with some open questions in Section 5.
2
Definitions
Given interactive algorithms P and V, we let P(x), V(y) denote the interaction of P, holding input x, with V, holding input y. We let P(x), V(y) = 1 denote
Which Languages Have 4-Round Zero-Knowledge Proofs?
77
the event that V outputs 1 in the indicated interaction, where an output of “1” is interpreted as “accept” and an output of “0” is interpreted as “reject”. We now give the standard definition of an interactive proof system [23] for a language L. Definition 1. Interactive algorithms P, V form an interactive proof system for a language L if V runs in probabilistic polynomial time and there exist non-negative functions c, s such that: – For all x ∈ L, it holds that Pr[P(x), V(x) = 1] ≥ c(|x|). (Note that we do not require P to run in polynomial time.) – For all x ∈ L and any P ∗ we have Pr[P ∗ , V(x) = 1] ≤ s(|x|). – There exists a polynomial p such that c(|x|) ≥ s(|x|) + 1/p(|x|). We call c the acceptance probability, and s the soundness error. If c(|x|) = 1 for all x, we say the proof system has perfect completeness. If s is negligible, we say the proof system has negligible soundness error. ♦ We will only consider zero-knowledge proof systems having negligible soundness error. A round of an interactive proof system consists of a message sent from one party to the other, and we assume that the prover and the verifier speak in alternating rounds. Following [2], we let MA denote the class of languages having a 1-round proof system and in this case refer to the prover as Merlin and the verifier as Arthur ; that is: Definition 2. L ∈ MA if there exists a probabilistic polynomial-time verifier V, a non-negative function s, and a polynomial p such that the following hold for all sufficiently-long x: – If x ∈ L then there exists a string w (that can be sent by Merlin) such that Pr[V(x, w) = 1] ≥ s(|x|) + 1/p(|x|). – If x ∈ L then for all w (sent by a cheating Merlin) it holds that Pr[V(x, w) = 1] ≤ s(|x|).
♦
In fact, it is known that an equivalent definition is obtained even if we require perfect completeness and negligible soundness error. 2.1
Zero Knowledge Proof Systems
A distribution ensemble {X(a)}a∈{0,1}∗ is an infinite sequence of probability distributions, where a distribution X(a) is associated with each value of a. Two distribution ensembles X and Y are computationally indistinguishable if for all polynomial-time algorithms D, there exists a negligible function μ such that for every a we have Pr[D(X(a), a) = 1] − Pr[D(Y (a), a) = 1] ≤ μ(|a|).
78
J. Katz
(We do not need to consider non-uniform distinguishers here since non-uniformity can be incorporated via the auxiliary input that we will provide to the cheating verifier, below.) Given interactive algorithms P, V ∗ , we let transV ∗ P(x), V ∗ (y) denote the transcript of the indicated interaction; for convenience, this includes both messages of the prover as well as those of the verifier. (We remark that we do not need to consider the entire view of V ∗ since we will restrict to deterministic verifiers, as justified below, and the input y of V ∗ will be provided to the distinguisher as per our definition of computational indistinguishability, above.) We now review the standard definitions for computational zero-knowledge proofs. Definition 3. An interactive proof system P, V for a language L is said to be a computational zero-knowledge proof system if for any probabilistic polynomialtime algorithm V ∗ , there exists an expected polynomial-time simulator S such that the following distribution ensembles are computationally indistinguishable: {transV ∗ P(x), V ∗ (x, z)}x∈L,z∈{0,1}∗
and
{S(x, z)}x∈L,z∈{0,1}∗ . ♦
The above definition incorporates an auxiliary input z provided to V ∗ , and we may therefore restrict our consideration to verifiers V ∗ that are deterministic. Note also that we allow simulation in expected polynomial time; this makes our results stronger. (Also, constant-round, black-box CZK proofs with strict polynomial-time simulation are already ruled out by Barak and Lindell [4].) A computational zero-knowledge proof system (P, V) is black-box zero knowledge if there exists a “universal” simulator that takes oracle access to the cheating verifier V ∗ . That is: Definition 4. A computational zero-knowledge proof system P, V is black-box zero-knowledge if there exists an expected polynomial-time oracle machine Sim (the black-box simulator) such that for any probabilistic polynomial-time algorithm V ∗ the following distribution ensembles are computationally indistinguishable: ∗ {transV ∗ P(x), V ∗ (x, z)}x∈L,z∈{0,1}∗ and SimV (x,z) (x) . ∗ x∈L,z∈{0,1}
♦ We denote by bb CZK(r) the class of languages that have r-round, black-box, computational zero-knowledge proof systems with negligible soundness error. Terminology and simplifying assumptions. We will be concerned with 4round CZK proof systems, where (without loss of generality) the verifier sends the first message and the prover sends the final message. We use α, β, γ, δ to denote the first, second, third, and fourth messages, respectively. We let Px (resp., Vx ) denote the honest prover (resp., honest verifier) algorithm when the common input is x.
Which Languages Have 4-Round Zero-Knowledge Proofs?
79
We let α = Vx (r) denote the first message sent by Vx when its random coins are fixed to r, and let γ = Vx (α, β; r) denote the third message sent by Vx in this case. Finally, Vx (α, β, γ, δ; r) is a bit denoting whether the verifier accepts (i.e., outputs 1) or rejects. We say that (α, β, γ, δ, r) is an accepting transcript for a given x if Vx (α, β, γ, δ; r) = 1. Note that we do not require the verifier’s decision to depend on the actual transcript alone, but allow its decision to also possibly depend on its random coins. Without loss of generality, we make a number of simplifying assumptions about the behavior of black-box simulator Sim. The first query of Sim to V ∗ will simply be a “prompt” query to which V ∗ responds with α. Subsequent queries by Sim are all of the form (α, β) (for some β of Sim’s choice), to which V ∗ will respond with some γ. (We can assume Sim makes no queries of the form (α, β, γ, δ) since V ∗ can simply refuse to respond to such queries.) We assume Sim makes a given query only once. Finally, if the simulator outputs the transcript (α , β, γ, δ) we assume that α = α, and that the simulator previously queried (α, β) to V ∗ and received response γ.
3
CZK Proof Systems with Perfect Completeness
We now state our main result: Theorem 1.
bb
CZK(4) ⊆ coMA.
In this section we prove this result in the easier case when the proof system in question has perfect completeness; we handle the case of imperfect completeness in the following section. As intuition for the proof, consider first the case of a malicious verifier Vˆ who acts in the following way: it sends an initial message α, and then in response to the prover’s second message β it chooses a random message γ consistent with α. (For now, we do not worry about the fact that this does not necessarily represent a feasible polynomial-time strategy.) Formally, if we let Rα denote the set of random coins consistent with α (i.e., r ∈ Rα implies Vx (r) = α), then in response to β the malicious verifier chooses a random r ∈ Rα and computes γ = Vx (α, β; r). Intuitively, it will be difficult to simulate an accepting transcript for such a verifier since each time the simulator “rewinds” Vˆ it will be given a message γ consistent with a different set of random coins. In fact, we can prove that if x ∈ L then the simulator will not be able to simulate an accepting transcript for such a verifier, since the ability to do so with nonnegligible probability could be translated into the ability to violate the soundness condition of the proof system with non-negligible probability. (A proof of this fact goes along similar lines as the proof in [20].) On the other hand, consider the case when x ∈ L. From the perspective of the honest prover, the behavior of Vˆ is identical to that of the honest verifier, and so the honest prover’s interaction with Vˆ leads to an accepting transcript with probability 1. We would like to claim that the zero-knowledge condition implies that Sim simulates an accepting transcript for such a verifier with high
80
J. Katz
probability. Unfortunately, Vˆ as described above may not run in polynomial time, whereas simulation is only guaranteed for polynomial-time verifiers. It is possible, however, to obtain a polynomial-time cheating verifier with the desired behavior by providing the verifier as auxiliary input a sequence of sufficiently-many coins r1 , . . . , rs that are all consistent with the same first message α. Specifically, consider the verifier V ∗ defined as follows: given auxiliary input r1 , . . . , rs (all consistent with the same first message α) and a poly-wise independent hash function h, send α as the first message. In response to the prover’s second message β, compute i = h(β) and use ri to compute the next message γ = Vx (α, β; ri ). Note that if r1 , . . . , rs are chosen at random (subject to the constraint that they are all mutually consistent) then the behavior of V ∗ is identical to the behavior of Vˆ as far as the honest prover is concerned. Since V ∗ runs in polynomial time, we are now able to argue that Sim simulates an accepting transcript for V ∗ with high probability when x ∈ L. Furthermore, it is still possible to show (using a slightly more complicated argument) that, with overwhelming probability, Sim fails to simulate an accepting transcript for this verifier whenever x ∈ L. ¯ Merlin sends Arthur Based on the above, we obtain an MA proof system for L: a sequence r1 , . . . , rs of random coins that are all consistent with the same first ∗ message α, and Arthur simulates an execution of SimV (x). If this does not result in an accepting transcript then Arthur accepts, while if it does lead to an accepting transcript then Arthur rejects. We now formalize the above intuition and show how to handle various technicalities that arise. Fix L ∈ bb CZK(4). This means that, for this language, there exists a prover P, a verifier V, and a black-box simulator Sim satisfying Definitions 1–4 (except that, in this section, we are assuming perfect completeness). Assume without loss of generality that the second message of the protocol always has length m(·), and let (·) denote the number of random coins used by V. Let T (·) denote an upper-bound on the expected running time of Sim. ¯ where Merlin Consider the following MA proof system for the language L, (i.e., the prover) and Arthur (i.e., the verifier) share in advance an input x of length n: Notation: Let = (n), m = m(n), and T = T (n). Set s = 50 · T 2 ; note that s is polynomial in n. Merlin’s message: Merlin sends a sequence of s coins r1 , . . . , rs ∈ {0, 1}. (For the honest Merlin, these are all consistent with the same first message α.) Arthur’s actions: Arthur proceeds as follows: 1. Set α = Vx (r1 ). Check that α = Vx (ri ) for all 1 < i ≤ s, i.e., that all the random coins are consistent with the same first message α. If not, reject; otherwise, go to the next step. 2. Choose a random 5T -wise independent hash function h : {0, 1}m → {1, . . . , s}. Construct the following deterministic verifier V ∗ : (a) Send first message α to the prover.
Which Languages Have 4-Round Zero-Knowledge Proofs?
81
(b) Upon receiving message β from the prover, compute i = h(β) and send the message γ = Vx (α, β; ri ) to the prover. ∗ 3. Run SimV (x) for at most 5T steps using uniformly-chosen random coins for Sim. If Sim does not output an accepting transcript within this time bound, output “accept”. Otherwise, output “reject”. (Formally, output “reject” iff Sim outputs (α, β, γ, δ), within the allotted time bound, such that Vx (α, β, γ, δ; rh(β) ) = 1.) ¯ thus The following claims show that the above is a valid MA-protocol for L, proving Theorem 1 for the case of protocols having perfect completeness. ¯ sufficiently long and for any message r1 , . . . , rs sent Claim 1. For any x ∈ L by Merlin, the probability that Arthur accepts is at most 2/5. Proof. Fix some r1 , . . . , rs sent by Merlin. Assume Vx (ri ) = Vx (rj ) for all 1 ≤ ¯ we have x ∈ L i, j ≤ s since, if not, Arthur rejects immediately. When x ∈ L and, by perfect completeness, the interaction of the honest prover Px with V ∗ would result in an accepting transcript with probability 1. (To see this, note that an execution of V ∗ is equivalent to an execution of the honest verifier Vx using random coins rh(β) .) The zero-knowledge condition thus implies that, for x ∗ sufficiently long, SimV (x) outputs an accepting conversation with probability at least 4/5. It follows that even the truncated version of Sim, where its execution is halted after 5T steps, outputs an accepting conversation with probability at least 3/5. Arthur thus accepts with probability at most 2/5, as claimed. ¯ sufficiently long, there exists a message r1 , . . . , rs such Claim 2. For any x ∈ L that Arthur will accept with probability at least 1/2. ¯ We show a randomized strategy that allows Merlin to convince Proof. Fix x ∈ L. Arthur with probability at least 1/2; this implies the claim. Merlin proceeds as follows: choose random r1 ∈ {0, 1} and compute α = def Vx (r1 ). Define Rα = {r | Vx (r) = α}; i.e., Rα is the set of coins for the honest verifier consistent with the first message α. Then choose r2 , . . . , rs uniformly from Rα . (These need not be distinct.) Send r1 , . . . , rs to Arthur. Let p∗ denote the probability that Arthur rejects. Note that this is exactly the probability that ∗ SimV (x) outputs an accepting transcript within the allotted time bound. We upper-bound p∗ by considering a slightly different experiment involving an all-powerful cheating prover P ∗ attempting to falsely convince the honest verifier Vx that x ∈ L. The strategy of P ∗ is defined as follows: def
1. Receive message α from the verifier. Let Rα = {r | Vx (r) = α}. 2. Run Sim using uniformly-chosen random coins, for at most 5T steps. Sim expects to be given oracle access to a (cheating) verifier, and P ∗ simulates the actions of such a verifier as follows: (a) Choose a random index q ← {1, . . . , 5T }. (b) Send α as the verifier’s first message.
82
J. Katz
(c) In response to the ith simulator message (α, βi ) for i = q, choose a random ri ← Rα , compute γi = Vx (α, βi ; ri ), and give γi to Sim. (Recall we assume that Sim never makes the same query twice.) (d) In response to the q th simulator message (α, βq ), send βq to the (external) honest verifier, and receive in return a message γq . Give γq to Sim. 3. If Sim outputs a conversation (α, β, γ, δ) with β = βq within the allotted time bound, then send δ to the (external) honest verifier. In the above experiment, each “query” βi of Sim is answered by using a random element ri ← Rα to compute the response γi = Vx (α, βi ; ri ). This is immediate for i = q, but is true also for i = q since, from the perspective of P ∗ and Sim, the coins being used by the external, honest verifier are uniformly-distributed in Rα . Let pˆ denote the probability that Sim outputs an accepting transcript in this case, within the allotted time bound. Since Sim makes at most 5T queries to its oracle in the above experiment, P ∗ convinces the honest verifier to accept with probability pˆ/5T . Since the proof system has negligible soundness error we have that, for x sufficiently long, pˆ ≤ 1/4. ∗ We return now to consideration of p∗ . When Arthur runs SimV (x), he does so by first choosing a random h and then answering the simulator’s ith query (α, βi ) by using rh(βi ) to compute the response γi = Vx (α, βi ; rh(βi ) ). Since Merlin chooses each of the ri uniformly from Rα , these responses are distributed identically to the above experiment unless there is a collision in h; that is, unless there exist some βi = βj with h(βi ) = h(βj ). Because h is chosen in a 5T -wise independent fashion and Sim is restricted to making only 5T queries, a standard birthday bound shows that the probability of such a collision is at most (5T )2 /2s = 1/4. Conditioned on a collision not occurring, the probability that ∗ SimV (x) outputs an accepting conversation is exactly pˆ ≤ 1/4. We conclude that p∗ ≤ 1/4 + 1/4 = 1/2, and so Arthur rejects with probability at most 1/2 (and accepts with probability at least 1/2).
4
Handling Imperfect Completeness
In the previous section we assumed perfect completeness, and in fact this is essential for the MA proof system given there. To see the problem, assume P, V is such that the honest verifier immediately rejects whenever its random coins are all 0. Then a cheating Merlin can send r1 = · · · = rs = 0 and this will cause ¯ Arthur to accept with probability 1 even when x ∈ L. In the modified proof system, we have Arthur “verify” that Merlin sends “representative” random coins r1 , . . . , rs by checking that SimVx (ri ) (x), for a random element ri in the set sent by Merlin, outputs an∗ accepting transcript with “high” probability. Then Arthur checks whether SimV (x;r1 ,...,rs ,h) (x) fails to output an accepting transcript, as in the previous section. Unfortunately, this may make ¯ since in this case SimVx (ri ) (x) might the honest Merlin’s job harder when x ∈ L (legitimately) never output an accepting transcript. But Arthur can easily check for this by running SimVx (r) (x) using random coins r that it chooses itself.
Which Languages Have 4-Round Zero-Knowledge Proofs?
83
We remark that if we were content to show inclusion in AM (rather than MA), the proof could be simplified somewhat. Before presenting the modified proof system, we introduce some notation. For a given randomized experiment Expt that can be run in polynomial time, we let estimateε (Prr [Expt]) denote a procedure that outputs an estimate to the given probability (taken over randomness r) to within an additive factor of ε, except with probability at most ε. That is: Pr estimateε (Prr [Expt = 1]) − Prr [Expt = 1] ≥ ε ≤ ε. This can be done in the standard way using Θ(ε−2 log 1ε ) independent executions of Expt. The important thing to note is that when ε is noticeable, this estimation can be done in polynomial time. In the experiments we will be considering, some variables will be fixed as part of the experiment and others will be chosen at random; we will always subscript those variables being chosen at random (as done above with the subscripted r). Below, we let V ∗ denote the same malicious verifier as in the previous section. Specifically, on input x and auxiliary input z = r1 , . . . , rs , h, where each ri represents coins for the honest verifier and h is a hash function, V ∗ acts as follows: 1. Send first message α = Vx (r1 ) to the prover. 2. Upon receiving message β from the prover, compute i = h(β) and send the message γ = Vx (α, β; ri ) to the prover. 3. Receive final message δ from the prover. We say an interaction of Px with V ∗ (x, z) results in an accepting transcript if (α, β, γ, δ, ri ) is an accepting transcript. Let L ∈ bb CZK(4), and assume L has a 4-round CZK proof system P, V with acceptance probability c(·) where c is noticeable (i.e., c = Ω(1/p) for some polynomial p). Let , m, and T be as in the previous section. Once again, Merlin and Arthur share in advance an input x of length n. The MA proof system for ¯ follows: the language L Notation: Let c = c(n), = (n), m = m(n), and T = T (n). Assume n is large enough so that c > 0. Set ε = c/20, and s = 4T 2 ε−3 . (Note that ε is noticeable, denote an execution of Sim for at most 2T /ε steps. and s is polynomial.) Let Sim Merlin’s message: Merlin sends a sequence of s coins r1 , . . . , rs ∈ {0, 1}. Arthur’s actions: Arthur proceeds as follows: 1. Compute
Vx (r ) p1 = estimateε Prr ,r Sim (x; r) outputs an accepting transcript . If p1 < c − 2ε then accept; otherwise, continue to the next step. 2. Set α = Vx (r1 ). Check that α = Vx (ri ) for all 1 < i ≤ s. If not, reject; otherwise, continue to the next step.
84
J. Katz V (r )
x i (x; r). If this does not 3. Choose i ← {1, . . . , s} and coins r and run Sim result in an accepting transcript, reject; otherwise, continue to the next step. 4. Let H denote a family of 2T /ε-wise independent hash functions h : {0, 1}m → {1, . . . , s}. Compute p2 =
V ∗ (x;r,h) (x; r) outputs an accepting transcript , estimateε Prh←H,r Sim
where r = (r1 , . . . , rs ). If p2 < c − 10ε accept; else reject. (It should be clear that we have not attempted to optimize any of the parameters of the above proof system.) We now prove claims analogous to those in the previous section. ¯ sufficiently long and for any message r1 , . . . , rs sent Claim 3. For any x ∈ L by Merlin, the probability that Arthur accepts is at most c − 6ε. ¯ then x ∈ L and so the interaction of Px with Vx results in an Proof. If x ∈ L accepting transcript with probability at least c. The zero-knowledge condition implies that, for x sufficiently long,
Vx (r ) (x; r) outputs an accepting transcript] ≥ c − ε. Prr ,r [Sim This means that, except with probability at most ε, the value p1 computed by Arthur satisfies p1 ≥ c−2ε; thus, Arthur accepts in the first step with probability at most ε. Fix some r = (r1 , . . . , rs ) sent by Merlin. We may assume Vx (ri ) = Vx (rj ) for all 1 ≤ i, j ≤ s since, if not, Arthur rejects in the second step. Define
V (r ) x i (x; r) outputs an accepting transcript . pˆ = Pri←{1,...,s},r Sim There are two cases to consider: Case 1: If pˆ < c − 7ε, then the probability that Arthur does not reject in step 3 is at most c − 7ε. Case 2: On the other hand, if pˆ ≥ c − 7ε then (again using the zero-knowledge property) Pri←{1,...,s},r [Px (r), Vx (ri ) = 1] ≥ c − 8ε. By definition of V ∗ it holds that Prh←H,r [Px (r), V ∗ (x, r, h) results in an accepting transcript] = Pri←{1,...,s},r [Px (r), Vx (ri ) = 1]. Thus, relying on the zero-knowledge property once again,
V ∗ (x;r1 ,...,rs ,h) (x; r) outputs an accepting transcript ≥ c − 9ε. Prh←H,r Sim
Which Languages Have 4-Round Zero-Knowledge Proofs?
85
So, except with probability at most ε, the value p2 computed by Arthur satisfies p2 ≥ c − 10ε; thus, Arthur accepts in the last step with probability at most ε. Combining the above, we see that Arthur accepts with probability at most ε + max{c − 7ε, ε}, which is at most c − 6ε. ¯ sufficiently long, there exists a message r1 , . . . , rs such Claim 4. For any x ∈ L that Arthur will accept with probability at least c − 5ε. ¯ Define Proof. Fix x ∈ L.
V (r ) x (x; r) outputs an accepting transcript . pˆ = Prr ,r Sim There are two cases to consider: Case 1: If pˆ < c − 3ε then, except with probability at most ε, the value p1 computed by Arthur satisfies p1 < c − 2ε; thus, Arthur accepts in the first step with probability at least 1 − ε ≥ c − 5ε. Case 2: On the other hand, say pˆ ≥ c − 3ε. As in the proof of Claim 2, Merlin proceeds as follows: choose random r1 ∈ {0, 1} and compute α = Vx (r1 ). Let def
Rα = {r | Vx (r) = α}, and choose r2 , . . . , rs uniformly from Rα . Send r = (r1 , . . . , rs ) to Arthur. We show that Arthur will accept with high probability. Arthur can reject in either step 3 or step 4. We upper-bound the probability that Arthur rejects in either of these steps individually, and then apply a union bound to upper-bound the total probability that Arthur rejects. Each ri , taken individually, is uniformly distributed in {0, 1}. Thus, in step 3, choosing a random i ∈ {1, . . . , s} and using coins ri is equivalent to choosing uniformly-random coins for Vx . It follows that the probability that Arthur rejects in step 3 is exactly equal to 1 − pˆ ≤ 1 − c + 3ε. We proceed to analyze step 4. As in the proof of Claim 2, say a collision occurs ∗ V (x;r1 ,...,rs ,h) (x; r) if the simulator makes two distinct in an execution of Sim queries (α, βi ) and (α, βj ) for which h(βi ) = h(βj ). Let coll denote such an event. As before, we have
V ∗ (x;r,h) Pr Sim (x; r) outputs an accepting transcript ≤ (1) r,h,r
V ∗ (x;r,h) Pr [coll] + Pr Sim (x; r) outputs an accepting transcript | coll , r,h,r
r,h,r
where r = (r1 , . . . , rs ) are chosen by Merlin as described above (and not uniformly and independently at random). The probability of a collision is indepen/ε)2 dent of r1 , . . . , rs , and is upper-bounded by Pr[coll] ≤ (2T2s = 2ε . As in the proof of Claim 2, for sufficiently-long x it holds that
V ∗ (x;r,h) Prr,h,r Sim (x; r) outputs an accepting transcript | coll ≤ ε2 /2;
86
J. Katz
this means that, except with probability at most ε, the r1 , . . . , rs chosen by Merlin satisfy
V ∗ (x;r1 ,...,rs ,h) Prh,r Sim (x; r) outputs an accepting transcript | coll ≤ ε/2. Using Equation (1), we see that except with probability at most ε, the r1 , . . . , rs chosen by Merlin satisfy
V ∗ (x;r1 ,...,rs ,h) Prh,r Sim (x; r) outputs an accepting transcript ≤ ε < c − 11ε. Assuming the above to be the case, Arthur will reject in step 4 with probability at most ε. Taken together, this means that Arthur rejects in step 4 with probability at most 2ε. Summing the probabilities of rejection in steps 3 and 4, we see that, overall, Arthur rejects with probability at most 1 − c + 5ε, or accepts with probability at least c − 5ε.
5
Future Directions
Coupled with the obvious fact that bb CZK(4) ⊆ AM, this work shows that bb CZK(4) ⊆ AM ∩ coMA. Due to the similarity with the fact that SZK ⊆ AM ∩ coAM [18,1], as well as the fact that the only languages known to be in 4CZK (under any assumption) are also in SZK, it is natural to conjecture that bb CZK(4) ⊆ SZK. Another interesting direction would be to show any broad positive results for 4 CZK: say, along the lines of proving that NP ∩ coNP ⊆ 4CZK. In a slightly different direction, suggested by Hoeteck Wee: can a tighter bound be shown for languages L having 4-round zero-knowledge proofs of knowledge (beyond the fact that L ∈ NP)? Finally, is it possible to apply the techniques from [26] to show that there are no black-box constructions of constant-round (black-box) zero-knowledge proofs for NP?
Acknowledgments I would like to thank Hoeteck Wee for many illuminating discussions regarding the round complexity of zero knowledge in general, and for helpful remarks on a previous draft of this paper. Thanks also to Dov Gordon and Arkady Yerukhimovich for reading and commenting on a preliminary version of this manuscript. The suggestions of an anonymous member of the ECCC scientific board and the TCC referees also helped to clarify the presentation.
Which Languages Have 4-Round Zero-Knowledge Proofs?
87
References 1. Aiello, W., H˚ astad, J.: Statistical zero-knowledge languages can be recognized in two rounds. J. Computer and System Sciences 42(3), 327–345 (1991) 2. Babai, L., Moran, S.: Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Computer and System Sciences 36(2), 254–276 (1988) 3. Barak, B.: How to go beyond the black-box simulation barrier. In: Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 106–115. IEEE Computer Society Press, Los Alamitos (2001) 4. Barak, B., Lindell, Y.: Strict polynomial-time in simulation and extraction. SIAM J. Computing 33(4), 738–818 (2004) 5. Barak, B., Lindell, Y., Vadhan, S.: Lower bounds for non-black-box zero knowledge. J. Computer and System Sciences 72(2), 321–391 (2006) 6. Bellare, M., Jakobsson, M., Yung, M.: Round-optimal zero-knowledge arguments based on any one-way function. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 280–305. Springer, Heidelberg (1997) 7. Bellare, M., Micali, S., Ostrovsky, R.: Perfect zero knowledge in constant rounds. In: Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 482–493. ACM, New York (1990) 8. Bellare, M., Micali, S., Ostrovsky, R.: The (true) complexity of statistical zero knowledge. In: Proc. 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 494–502. ACM, New York (1990) 9. Bellare, M., Palacio, A.: The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 273–289. Springer, Heidelberg (2004) 10. Ben-Or, M., Goldreich, O., Goldwasser, S., H˚ astad, J., Kilian, J., Micali, S., Rogaway, P.: Everyting provable is provable in zero knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37–56. Springer, Heidelberg (1990) 11. Boppana, R., H˚ astad, J., Zachos, S.: Does coNP have short interactive proofs? Information Proc. Letters 25(2), 127–132 (1987) 12. Boyar, J., Kurtz, S., Krentel, M.: Discrete logarithm implementation of perfect zero-knowledge blobs. J. Cryptology 2(2), 63–76 (1990) 13. Brassard, G., Chaum, D., Cr´epeau, C.: Minimum disclosure proofs of knowledge. J. Computer and Systems Sciences 37(2), 156–189 (1988) 14. Cramer, R., Damg˚ ard, I., MacKenzie, P.: Efficient zero-knowledge proofs of knowledge without intractability assumptions. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 354–372. Springer, Heidelberg (2000) 15. Di Crescenzo, G., Persiano, G.: Round-optimal perfect zero-knowledge proofs. Information Proc. Letters 50(2), 93–99 (1994) 16. Damg˚ ard, I., Pedersen, M., Pfitzmann, B.: On the existence of statistically-hiding bit commitment schemes and fail-stop signatures. J. Cryptology 10(3), 163–194 (1997) 17. Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526–544. Springer, Heidelberg (1990) 18. Fortnow, L.: The complexity of perfect zero knowledge. In: Micali, S. (ed.) Advances in Computing Research, vol. 5, pp. 327–343. JAC Press, Inc. (1989) 19. Goldreich, O., Kahan, A.: How to construct constant-round zero-knowledge proof systems for NP. J. Cryptology 9(3), 167–190 (1996)
88
J. Katz
20. Goldreich, O., Krawczyk, H.: On the composition of zero-knowledge proof systems. SIAM J. Computing 25(1), 169–192 (1996) 21. Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity, or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991) 22. Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptology 7(1), 1–32 (1994) 23. Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Computing 18(1), 186–208 (1989) 24. Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Computing 17(2), 281–308 (1988) 25. Hada, S., Tanaka, T.: On the existence of 3-round zero-knowledge protocols. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 408–423. Springer, Heidelberg (1998) (See also http://eprint.iacr.org/1999/009) 26. Haitner, I., Hoch, J.J., Reingold, O., Segev, G.: Finding collisions in interactive protocols — a tight bound on the round complexity of statistically-hiding commitments. In: Proc. 48th Annual Symposium on Foundations of Computer Science (FOCS), pp. 669–679. IEEE, Los Alamitos (2007), http://eprint.iacr.org/2007/145 27. Haitner, I., Reingold, O.: Statistically-hiding commitment from any one-way function. In: Proc. 39th Annual ACM Symposium on Theory of Computing (STOC), pp. 1–10. ACM Press, New York (2007) 28. Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 201–215. Springer, Heidelberg (1996) 29. Impagliazzo, R., Yung, M.: Direct minimum-knowledge computations (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 40–51. Springer, Heidelberg (1988) 30. Itoh, T., Sakurai, K.: On the complexity of constant round ZKIP of possession of knowledge. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 331–345. Springer, Heidelberg (1993) 31. Kurosawa, K., Ogata, W., Tsujii, S.: 4-move perfect ZKIP for some promise problems. IEICE Trans. on Fundamentals of Electronics, Communications, and Computer Sciences E78-A(1), 34–41 (1995) 32. Lepinski, M.: On the existence of 3-round zero-knowledge proofs. Master’s thesis, MIT (2002), Available at http://theory.lcs.mit.edu/Sim cis/cis-theses.html 33. Pass, R.: On Arthur-Merlin games and the possibility of basing cryptography on NP-hardness. In: 21st Annual IEEE Conference on Computational Complexity, pp. 88–95. IEEE Computer Society Press, Los Alamitos (2006) 34. Saito, T., Kurosawa, K., Sakurai, K.: 4-move perfect SKIP of knowledge with no assumption. In: Matsumoto, T., Imai, H., Rivest, R.L. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 320–331. Springer, Heidelberg (1993) 35. Vadhan, S.: A Study of Statistical Zero-Knowledge Proofs. PhD thesis, MIT (1999)
How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge Lior Malka Department of Computer Science University of Victoria, BC, Canada
[email protected]
Abstract. We study perfect zero-knowledge proofs (PZK). Unlike statistical zero-knowledge, where many fundamental questions have been answered, virtually nothing is known about these proofs. We consider reductions that yield hard and complete problems in the statistical setting. The issue with these reductions is that they introduce errors into the simulation, and therefore they do not yield analogous problems in the perfect setting. We overcome this issue using an error shifting technique. This technique allows us to remove the error from the simulation. Consequently, we obtain the first complete problem for the class of problems possessing non-interactive perfect zero-knowledge proofs (NIPZK), and the first hard problem for the class of problems possessing public-coin PZK proofs. We get the following applications. Using the error shifting technique, we show that the notion of zero-knowledge where the simulator is allowed to fail is equivalent to the one where it is not allowed to fail. Using our complete problem, we show that under certain restrictions NIPZK is closed under the OR operator. Using our hard problem, we show how a constant-round, perfectly hiding instance-dependent commitment may be obtained (this would collapse the round complexity of public-coin PZK proofs to a constant). Keywords: cryptography, non-interactive, perfect zero-knowledge, perfect simulation, error shifting, complete problems.
1 Introduction Zero-knowledge protocols allow one party (the prover) to prove an assertion to another party (the verifier), yet without revealing anything beyond the validity of the assertion [18,5]. These protocols protect the privacy of the prover, which makes them very useful to cryptography. Zero-knowledge protocols can guarantee three levels of privacy: perfect, statistical, and computational. This is formulated using the notion of simulation. When the simulation error is zero, the protocol is perfect zero-knowledge. This means that the verifier learns absolutely nothing from the prover. When the simulation error is negligible, the protocol is either statistical zero-knowledge or computational R. Canetti (Ed.): TCC 2008, LNCS 4948, pp. 89–106, 2008. c International Association for Cryptologic Research 2008
90
L. Malka
zero-knowledge. This means that the prover leaks a little amount of information to the verifier. In this paper we focus on perfect zero-knowledge protocols. These protocols are interesting from a cryptographic perspective because, unlike statistical or computational zero-knowledge protocols, they provide the highest level of privacy to the prover. Such protocols exist for a variety of well known languages, such as G RAPH -I SOMORPHISM, D ISCRETE -L OG, variants of Q UADRATIC -R ESIDUOUSITY, and more ([31,13,6,26,21]). The fact that the complexity of these languages is an open question also makes perfect zero-knowledge protocols interesting from a complexity theoretic perspective. Unfortunately, working with perfect zero-knowledge protocols is difficult. This is so because they do not allow any error in the simulation. In contrast, statistical zeroknowledge protocols allow a small error in the simulation. This means that in the statistical setting we can use a variety of techniques, even if they introduce a small error into the simulation. Indeed, such techniques were used to prove many fundamental results about statistical zero-knowledge proofs (SZK). These results include complete problems, equivalence between private-coin and public-coin, equivalence between honest and malicious verifier, and much more ([24,26,14,16,32,23]). These results do not apply to the perfect setting because they use techniques that introduce error into the simulation, and such techniques cannot be used in the perfect setting. Consequently, virtually nothing is known about perfect zero-knowledge proofs (PZK). 1.1 Our Results In this paper we consider reductions that yield hard and complete problems in the statistical setting. The issue with these reductions is that they introduce errors into the simulation, and therefore they do not yield analogous problems in the perfect setting. Our goal is to overcome this issue. This is important because if we understand why techniques from the statistical setting introduce error into the simulation, then we might be able to fix these techniques, and then apply them to the perfect setting. This will enable us to translate the results from statistical zero-knowledge to perfect zeroknowledge. In addition, results from the statistical setting are proved using the tool of complete and hard problems. Thus, to be able to prove these results in the perfect setting it is important that we obtain complete and hard problems for the perfect setting. We remark that we are not the first to observe the fact that reductions from the statistical setting do not apply to the perfect setting. Specifically, in the case of hard problems, [26] showed that the reduction could eliminate the error using approximation techniques. However, this solution does not yield a hard problem in the perfect setting because it only applies in certain cases (for example, when the underlying problem has perfect completeness). In this paper we modify the reductions from the statistical setting so that they yield hard and complete problems in the perfect setting. To do this we use what we call the error shifting technique. What is new about this technique is that instead of dealing with the error in the reduction itself, we shift it forward to the protocol. Intuitively, our reduction isolates the error that the underlying problem incurs, and shifts it forward to the protocol, where it is no longer a simulation error. Consequently, we obtain complete and hard problems for the perfect setting. We remark that the error shifting technique
How to Achieve Perfect Simulation
91
is also useful in other contexts (e.g., in Section 4 we use it to show that the notion of zero-knowledge where the simulator is allowed to fail is equivalent to the one where it is not allowed to fail). The error shifting technique applies to reductions in both the interactive and the noninteractive models. In the non-interactive model we apply it to the reduction of [30,15], thus obtaining the first complete problem for the class of problems possessing noninteractive perfect zero-knowledge proofs (NIPZK). Theorem 1. The problem U NIFORM (UN) is complete for NIPZK. Informally, instances of U NIFORM are circuits that have an additional output bit. Ignoring this bit, we can think of YES instances of UN as circuits that represent the uniform distribution, whereas NO instance are circuits that hit only a small fraction of their range. This problem is identical to the NISZK-complete problem S TATISTICAL D ISTANCE FROM U NIFORM (SDU) [15], except that YES instances of U NIFORM represent the uniform distribution, whereas YES instances of SDU represent a distribution that is only “close” to uniform. This difference is natural because it reflects the difference between perfect and statistical simulation. In the interactive model we obtain a similar result. That is, we apply the error shifting technique to the reduction of [26], thus obtaining a hard problem for the class of problems possessing public-coin HVPZK proofs. Instances of our hard problem are triplets of circuits. Again, ignoring one of these circuits, our problem is a variant of S TATISTICAL -D ISTANCE (SD) [26]. That is, we can think of YES instances of our problem as pairs of circuits representing the same distribution, whereas instances of the reduction of [26] are circuits representing “close” distributions. Theorem 2 (informal). Essentially, SD1/2,0 is hard for public-coin-HVPZK. To demonstrate the usefulness of our NIPZK-complete problem we prove that under certain restrictions NIPZK is closed under the OR operator. What is special about this result is that even in statistical setting, where we have more techniques to work with, it is not clear how to prove (or disprove) it.1 Also, we show how our hard problem may lead to a constant-round, perfectly hiding instance-dependent commitment-scheme. Notice that except for [21], who used the techniques of [8] to construct such a scheme for V -bit protocols, all the known instance-dependent commitment-schemes are only statistically hiding [33,23,22]. Thus, using our hard problem it might be possible to collapse the round complexity of public-coin PZK proofs to a constant. These applications can be found in Section 4. 1.2 Related Work As we mentioned, virtually nothing is known about perfect zero-knowledge proofs. The only exception is the result of [9], who showed a transformation from constant-round, public-coin HVPZK proofs to ones that are PZK. Also, a HVPZK-complete problem was given by [26], but it is unnatural, and defined in terms of the class itself. We remark 1
[30] claimed that NISZK is closed under the OR operator, but this claim has been retracted.
92
L. Malka
that perfect zero-knowledge arguments for NP languages have been constructed under various unproven assumptions (e.g., [19,7]), but we are interested in the unconditional study of perfect zero-knowledge proofs. Variants of Q UADRATIC -R ESIDUOUSITY and Q UADRATIC -N ONRESIDUOUSITY were shown to to be in NIPZK by [6,27]. Bellare and Rogaway [3] showed that a variant of G RAPH -I SOMORPHISM is in NIPZK. They also showed basic results about NIPZK, but their notion of zero-knowledge allows simulation in expected (as opposed to strict) polynomial-time. This notion is disadvantageous, especially when noninteractive protocols are executed as sub-protocols. Other aspects of NIPZK were studied in [27,28,29], but they apply to problems with special properties. 1.3 Organization We use standard definitions, to be found in Appendix A. In Section 2 we present the error shifting technique, and use it to obtain a NIPZK-complete problem. In Section 3 we apply this technique to the interactive setting, where we obtain a hard problem. In Section 4 we show some applications of these results.
2 A Complete Problem for NIPZK In this section we introduce the error shifting technique. Using this technique we modify the reduction of [15], hence obtaining a NIPZK-complete problem. Starting with some background, we give the definition of S TATISTICAL D ISTANCE FROM U NIFORM (SDU), the NISZK-complete problem of [15]. Instances of this problem are circuits. These circuits are treated as distributions, under the convention that the input to the circuit is uniformly distributed. Specifically, YES instances are circuits representing a distribution that is close to uniform, and NO instances are circuits representing a distribution that is far from uniform. Definition 2.1. Define SDU = SDUY , SDUN as def
SDUY = {X| Δ(X, Un ) < 1/n} , and SDUN = {X| Δ(X, Un ) > 1 − 1/n} , n
where X is a circuit with n output bits, and Un is the uniform distribution on {0, 1} . We informally describe the reduction of [15] to SDU. This reduction originated from the work of [30]. Given a NISZK problem Π, this reduction maps instances x of Π to circuits X of SDU. The circuit uses the simulator S from the proof of Π. Specifically, X executes S(x), and obtains a transcript. This transcript contains a simulated message of the prover, and a simulated reference string. If the verifier accepts in this transcript, then X outputs the simulated reference string. Otherwise, X outputs the all-zero string. Intuitively, this reduction works because if x is a YES instance, then the simulated reference string is almost uniformly distributed, and thus X is a YES instance of SDU. Conversely, if x is a NO instance, then the verifier rejects on most reference strings, and thus X is a NO instance of SDU.
How to Achieve Perfect Simulation
93
The issue with the reduction of [15]. When we apply the above reduction to NIPZK problems, it is natural that we should get a NIPZK-complete problem whose instances are circuits that represents the uniform distribution. This is so because the circuit X outputs the simulated reference string, and when the simulation is perfect, this string is uniformly distributed. Indeed, if we apply the above reduction to NIPZK problems that have perfect completeness, then the verifier will accept, and thus we will get a circuit X that represents the uniform distribution. However, if the underlying problem does not have perfect completeness, then the distribution represented by X will be skewed. This will cause problems later, when we try to construct a proof system and a simulator for our complete problem. Hence, this reduction does not apply to NIPZK. To overcome the above issue, instead of working only with the reduction to SDU, our idea is to modify both the reduction and the proof system for SDU at the same time. The Error Shifting Technique. In its most general form, the error shifting technique shifts into the protocol errors that would otherwise become simulation errors. This description is a very loose, but we chose it because our technique can be applied in various different contexts, and in each of these contexts it takes a different form. However, the following application will clarify our technique. The first step of the error shifting technique is to identify where the simulation error comes from, and then isolate it. In our case, the error comes from the reduction: if the verifier rejects, then the circuit X does not represent the uniform distribution. Thus, the error comes from the completeness error of the underlying problem. To separate this error, we add an extra output bit to the circuit X. That is, X executes the simulator, and it outputs the simulated reference string followed by an extra bit. This bit takes the value 1 if the verifier accepts, and 0 if the verifier rejects. The second step of the error shifting technique is to shift the error forward, to the completeness or the soundness error of the protocol. In our case, from the circuit X to the protocol of our complete problem. This step is not trivial because we cannot just use the protocol of [15] for SDU. Specifically, in this protocol the prover sends a string r, and the verifier accepts if X(r) equals the reference string. If we use this idea in our case, then we will get a simulation error. Thus, we modify this protocol by starting with the simulator, and constructing the prover based on the simulator. Informally, the simulator samples the circuit X, and the verifier accepts if the extra bit in this sample is 1. The prover simply mimics the simulator. This shows that the error was shifted from X to the completeness error (of a new protocol). The above reduction yields our NIPZK-complete problem U NIFORM. A formal description of the above reduction and our proof system is given in the next section. 2.1 A Complete Problem for NIPZK In this section we formalize the intuition given in the previous section, thus proving our first result. Theorem 2.1. U NIFORM is NIPZK-complete. We start with the definition of U NIFORM (UN). Recall that when we applied the error shifting technique we got circuits X with an extra output bit. We use the convention that n + 1 denotes the number of output bits of X. We need the following notation.
94
L. Malka
– TX is the set of outputs of X that end with a 1. Formally, TX = {x|∃r X(r) = x, and the suffix of x is 1}. As we shall see, the soundness and completeness properties will imply that the size of TX is large for YES instances of UN, and small for NO instances of UN. – X is the distribution on the first n bits that X outputs. That is, X is obtained from X by taking a random sample of X, and then outputting the first n bits. As we shall see, the zero-knowledge property will imply that if X is a YES instance of UN, then X is the uniform distribution on {0, 1}n . def
Now, letting X be a circuit with n + 1 output bit, we say that X is β-negative if |TX | ≤ β · 2n . That is, TX is small, and contains at most β · 2n strings. We say that X is α-positive if X is the uniform distribution on {0, 1}n and Prx←X [x ∈ TX ] ≥ α. This implies that TX is large, and contains at least α · 2n strings. Definition 2.2. The problem U NIFORM is defined as UN = UNY , UNN , where def
UNY = {X|X is 2/3 − positive} , and UNN = {X|X is 1/3 − negative} . To prove that UN is NIPZK-complete we first show that the reduction from the previous section reduces every NIPZK problem to UN. Lemma 2.1. UN is NIPZK-hard. Proof. Let Π = ΠY , ΠN be a NIPZK problem. Fix a non-interactive protocol P, V for Π with completeness and soundness errors 1/3. Let rI denote the common reference string in P, V , and fix i such that |rI | = |x|i for any x ∈ ΠY ∪ ΠN . Fix a simulator S for P, V . Since S is efficient, we can fix an efficient transformation t and an integer such that on input x ∈ ΠY ∪ ΠN the output of t(x) is a circuit S that executes S on inputs x and randomness rS of length |x| . That is, t(x) = S , and on input a string rS of length |x| the output of S (rS ) is the output of S(x; rS ). We show that Π Karp reduces to UN. That is, we define a polynomial-time Turing machine that on input x ∈ ΠY ∪ ΠN outputs a circuit X such that if x ∈ ΠY , then |x| |x|i +1 X ∈ UNY , and if x ∈ ΠN , then X ∈ UNN . The circuit X : {0, 1} → {0, 1} carries out the following computation. – Let rS be the |x| -bit input to X, and let S = t(x). Execute S (rS ), and obtain S(x; rS ) = x, rI , m . – If V (x, rI , m ) = accept, then output the string rI 1 (i.e., the concatenation of rI and 1). Otherwise, output rI 0. Now we analyze our reduction. Let x ∈ ΠY , and let X be the output of the above reduction on x. We show that X is 2/3-positive. Consider the distribution on the output x, rI , m of S(x). Since S(x) and P, V (x) are identically distributed, rI is uniformly distributed. Thus, X (i.e., the distribution on the first |x|i output bits of X) is uniformly distributed. It remains to show that Pr[X ∈ TX ] ≥ 2/3. This immediately follows from the perfect zero-knowledge and completeness properties of P, V . That
How to Achieve Perfect Simulation
95
is, the output of S is identically distributed to P, V (x), and V accepts in P, V with probability at least 2/3. Let x ∈ ΠN , and let X be the output of the above reduction on x. We show that X is 1/3-negative. Assume towards contradiction that X is β-negative for some β > 1/3. We define a prover P ∗ that behaves as follows on CRS rI . If rI 1 ∈ TX , then there is an input rS to X such that X(rS ) = rI 1. By the construction of X, there is randomness rS for the simulator such that S(x; rS ) = x, rI , m , and V (x, rI , m ) = 1. In this case P ∗ sends rS to V . If rI 1 ∈ / TX , then P ∗ fails. Notice that P ∗ makes V accept on any rI i such that rI 1 ∈ TX . Since |TX | > 2|x| /3, and since rI is uniformly chosen in P ∗ , V , the probability that rI 1 ∈ TX is strictly greater than 1/3. Thus, V accepts in P ∗ , V (x) with probability strictly greater than 1/3, and contradiction to the soundness error of P, V . Hence, X is 1/3-negative. To prove Theorem 2.1 it remains to give a NIPZK proof for UN. Lemma 2.2. UN has a NIPZK proof with a deterministic verifier. Proof. We start with our non-interactive proof for UN. This proof is based on our sim n+1 ulator, which we describe later. On input X : {0, 1} → {0, 1} and common refn erence string rI ∈ {0, 1} the prover P picks z according to the distribution X such that the n-bit prefix of z equals rI . Such a z exists because X (i.e., the distribution on the first n bits of X) is the uniform distribution when X ∈ UNY . The prover uniformly picks r ∈ X −1 (z), and sends r to the verifier V . The deterministic verifier accepts if X(r) = rI 1, and rejects otherwise. Our prover is based on the following simulator. Let S be a probabilistic, polynomial-time Turing machine that on input X uniformly picks r ∈ {0, 1} , and computes z = X(r ). The simulator assigns the n bit prefix of z to rI (i.e., the simulated reference string), and outputs X, rI , r . Let X ∈ ΠY . We show that S perfectly simulates P, V . Consider the distribution S(X) on simulated transcripts X, rI , r , and the distribution P, V (X) on the view X, rI , r of V . Since X is uniformly distributed over {0, 1}n , the string rI obtained by n the simulator is uniformly distributed over {0, 1} . Since rI is uniformly distributed, rI and rI are identically distributed. It remains to show that r and r are identically distributed conditioned on rI = rI . For each y ∈ {0, 1}n , we define By to be the set of all strings rˆ for which the prefix of X(ˆ r) is y. Now, for any simulated reference string rI , the randomness r chosen by the simulator is uniformly distributed in BrI . Similarly, for any reference string rI the message of the prover is a string r chosen uniformly from BrI . Hence, conditioned on rI = rI , the strings r and r are identically distributed. We conclude that S(X) and P, V (X) are identically distributed for any X ∈ ΠY . Turning our attention to the completeness property, we show that V accepts X with probability at least 2/3. By the zero-knowledge property, the output X, rI , r of S(X) is identically distributed to the view X, rI , r of V on X. Thus, it is enough to show that when choosing a transcript X, rI , r according to S(x) the probability that V (X, rI , r ) = 1 is at least 2/3. Since S uniformly chooses r , and since X is 2/3-positive, the probability that X(r) ∈ TX is at least 2/3. Thus, the probability that the suffix of X(r) is 1 is at least 2/3. Hence, V accepts X with probability at least 2/3.
96
L. Malka
The soundness property follows easily. Let X ∈ UNN . Since X is 1/3-negative, |TX | ≤ 1/3 · 2n . Since rI is uniformly distributed, the probability that rI 1 ∈ TX is at most 1/3. Hence, if X ∈ UNN , then V accepts X with probability at most 1/3.
3 A Hard Problem for Public-Coin PZK Proofs In this section we use the error shifting technique to modify the reduction of [26] for public-coin HVSZK proofs. Hence, we obtain a hard problem for the class of problems possessing public-coin HVPZK proofs (AM ∩ HVPZK). We start with motivation. The reduction of [26] originated from the works of [11,1]. Informally, given a problem Π that has a public-coin HVSZK proof, this reduction maps instances x of Π to pairs of circuits X0 , X1 . The circuits X0 and X1 are statistically close when x is a YES instance of Π, and statistically far when x is a NO instance of Π. The issue with this reduction is that it does not apply to the perfect setting. Specifically, when we apply it to YES instances of a problem that has a public-coin HVPZK proof, we get a pair of circuits X0 , X1 that are only statistically close, but not identically distributed. This is unnatural because the closeness between X0 and X1 reflects the closeness of the simulation. Thus, in the perfect setting we expect X0 and X1 to be identically distributed, as in the complement of SD1/2,0 . Definition 3.1. The problem SD1/2,0 [26] is the pair SD1/2,0 Y , SD1/2,0 N , where SD1/2,0 Y = {X0 , X1 | Δ(X0 , X1 ) = 0} , and SD1/2,0 N = {X0 , X1 | Δ(X0 , X1 ) ≥ 1/2} . Sahai and Vadhan [26] were aware of this issue, and they addressed it by directly calculating the errors of the underlying problem. However, their technique applies only in certain cases (for example, when the underlying problem has a proof with perfect completeness). In the next section we will show how to overcome this issue by using the error shifting technique. Essentially, we obtain a hard problem where YES instances are pairs of circuits representing identical distributions, and NO instances are circuits representing statistically far distributions. Formally, our hard problem is as follows. Definition 3.2. The problem I DENTICAL D ISTRIBUTIONS is ID = IDY , IDN , where def
IDY = {X0 , X1 , Z| Δ(X0 , X1 ) = 0 and Pr[Z = 1] ≥ 2/3} , and IDN = {X0 , X1 , Z| Δ(X0 , X1 ) ≥ 1/2 or Pr[Z = 1] ≤ 1/3} . 3.1 Modifying the Reductions for Public-Coin HVSZK Proofs In this section we show that ID is hard for AM ∩ HVPZK, and then we conclude that, essentially, SD1/2,0 is also hard for AM ∩ HVPZK. Starting with some background, we describe the reduction of [26].
How to Achieve Perfect Simulation
97
Notation. Let P, V be a public-coin HVPZK proof for a problem Π with a simulator def S. Given a string x we use v = v(|x|) to denote the number of rounds in the interaction between P and V on input x. That is, in round i the prover P sends mi and V replies with a random string ri , until P sends its last message mv , and V accepts or rejects. We denote the output of S(x) by x, m1 , r1 , . . . , mv . The reduction of [26] maps instances x of Π to pairs of circuits X0 , X1 . These circuits are constructed from the circuits Xi and Yi , defined as follows. The circuit Xi chooses randomness, executes S(x) using this randomness, and outputs the simulated transcript, truncated at the i-th round. That is, Xi obtains x, m1 , r1 , . . . , mv , and outputs m1 , r1 , . . . , mi , ri . The circuit Yi is defined exactly the same, except that it replaces ri with a truly random string ri . – Xi (r): execute S(x; r) to obtain x, m1 , r1 , . . . , mv . Output m1 , r1 , . . . , mi , ri . – Yi (r, ri ): execute S(x; r) to obtain x, m1 , r1 ,. . . , mv . Output m1 , r1 ,. . . , mi , ri . Notice that Xi and Yi represent the same distribution when x is a YES instance. This is so because S(x) perfectly simulates the view of the verifier, and therefore ri is uniformly distributed, just like ri . We define X = X1 ⊗ · · · ⊗ Xv . That is, X executes all the circuits Xi and outputs the concatenation of their outputs. Similarly, we define Y = Y1 ⊗ · · · ⊗ Yv . Again, X and Y are identically distributed when x is a YES instance. Now, the pair X0 , X1 is defined from X, Y as follows. The circuit X1 outputs 1 followed by the output of Y . The circuit X0 outputs the output of Z followed by the output of X, where Z is the circuit that outputs 1 if with high probability S(x) outputs accepting transcripts, and 0 otherwise. The issue with the reduction of [26]. The above reduction does not apply to the perfect setting (except for the case where P, V have perfect completeness). This is so because there is a non-zero probability that Z will output 0, in which case X0 and X1 will not represent the same distribution. To overcome this issue we use the error shifting technique in two steps, just like we did in the previous section. Our goal is to show that, essentially, SD1/2,0 is hard for AM ∩ HVPZK Our first step is to separate the error that the circuit Z incurs. Thus, instead of including Z in the circuits X0 and X1 , our reduction simply maps an instance x of Π to the t