%0 Book Section %B Theory of Cryptography %D 2014 %T Can Optimally-Fair Coin Tossing Be Based on One-Way Functions? %A Dana Dachman-Soled %A Mahmoody, Mohammad %A Malkin, Tal %E Lindell, Yehuda %K Algorithm Analysis and Problem Complexity %K black-box separations %K Coin-Tossing %K Computation by Abstract Devices %K Data Encryption %K Discrete Mathematics in Computer Science %K One-Way Functions %K Systems and Data Security %X Coin tossing is a basic cryptographic task that allows two distrustful parties to obtain an unbiased random bit in a way that neither party can bias the output by deviating from the protocol or halting the execution. Cleve [STOC’86] showed that in any r round coin tossing protocol one of the parties can bias the output by Ω(1/r) through a “fail-stop” attack; namely, they simply execute the protocol honestly and halt at some chosen point. In addition, relying on an earlier work of Blum [COMPCON’82], Cleve presented an r-round protocol based on one-way functions that was resilient to bias at most O(1/r√)O(1/\sqrt r) . Cleve’s work left open whether ”‘optimally-fair’” coin tossing (i.e. achieving bias O(1/r) in r rounds) is possible. Recently Moran, Naor, and Segev [TCC’09] showed how to construct optimally-fair coin tossing based on oblivious transfer, however, it was left open to find the minimal assumptions necessary for optimally-fair coin tossing. The work of Dachman-Soled et al. [TCC’11] took a step toward answering this question by showing that any black-box construction of optimally-fair coin tossing based on a one-way functions with n-bit input and output needs Ω(n/logn) rounds. In this work we take another step towards understanding the complexity of optimally-fair coin-tossing by showing that this task (with an arbitrary number of rounds) cannot be based on one-way functions in a black-box way, as long as the protocol is ”‘oblivious’” to the implementation of the one-way function. Namely, we consider a natural class of black-box constructions based on one-way functions, called function oblivious, in which the output of the protocol does not depend on the specific implementation of the one-way function and only depends on the randomness of the parties. Other than being a natural notion on its own, the known coin tossing protocols of Blum and Cleve (both based on one-way functions) are indeed function oblivious. Thus, we believe our lower bound for function-oblivious constructions is a meaningful step towards resolving the fundamental open question of the complexity of optimally-fair coin tossing. %B Theory of Cryptography %S Lecture Notes in Computer Science %I Springer Berlin Heidelberg %P 217 - 239 %8 2014/01/01/ %@ 978-3-642-54241-1, 978-3-642-54242-8 %G eng %U http://link.springer.com/chapter/10.1007/978-3-642-54242-8_10 %0 Book Section %B Theory of Cryptography %D 2013 %T Signatures of Correct Computation %A Charalampos Papamanthou %A Shi, Elaine %A Tamassia, Roberto %E Sahai, Amit %K Algorithm Analysis and Problem Complexity %K Computation by Abstract Devices %K Data Encryption %K Systems and Data Security %X We introduce Signatures of Correct Computation (SCC), a new model for verifying dynamic computations in cloud settings. In the SCC model, a trusted source outsources a function f to an untrusted server, along with a public key for that function (to be used during verification). The server can then produce a succinct signature σ vouching for the correctness of the computation of f, i.e., that some result v is indeed the correct outcome of the function f evaluated on some point a. There are two crucial performance properties that we want to guarantee in an SCC construction: (1) verifying the signature should take asymptotically less time than evaluating the function f; and (2) the public key should be efficiently updated whenever the function changes. We construct SCC schemes (satisfying the above two properties) supporting expressive manipulations over multivariate polynomials, such as polynomial evaluation and differentiation. Our constructions are adaptively secure in the random oracle model and achieve optimal updates, i.e., the function’s public key can be updated in time proportional to the number of updated coefficients, without performing a linear-time computation (in the size of the polynomial). We also show that signatures of correct computation imply Publicly Verifiable Computation (PVC), a model recently introduced in several concurrent and independent works. Roughly speaking, in the SCC model, any client can verify the signature σ and be convinced of some computation result, whereas in the PVC model only the client that issued a query (or anyone who trusts this client) can verify that the server returned a valid signature (proof) for the answer to the query. Our techniques can be readily adapted to construct PVC schemes with adaptive security, efficient updates and without the random oracle model. %B Theory of Cryptography %S Lecture Notes in Computer Science %I Springer Berlin Heidelberg %P 222 - 242 %8 2013/01/01/ %@ 978-3-642-36593-5, 978-3-642-36594-2 %G eng %U http://link.springer.com/chapter/10.1007/978-3-642-36594-2_13 %0 Book Section %B Theory of Cryptography %D 2013 %T Why “Fiat-Shamir for Proofs” Lacks a Proof %A Bitansky, Nir %A Dana Dachman-Soled %A Garg, Sanjam %A Jain, Abhishek %A Kalai, Yael Tauman %A López-Alt, Adriana %A Wichs, Daniel %E Sahai, Amit %K Algorithm Analysis and Problem Complexity %K Computation by Abstract Devices %K Data Encryption %K Systems and Data Security %X The Fiat-Shamir heuristic [CRYPTO ’86] is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover’s first message to select the verifier’s challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai [FOCS ’03] shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps we can securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if we must fail for some computationally sound arguments. Indeed, this has been conjectured to be the case by Barak, Lindell and Vadhan [FOCS ’03], but we do not have any provably secure instantiation under any “standard assumption”. In this work, we give a broad black-box separation result showing that the security of the Fiat-Shamir heuristic for statistically sound proofs cannot be proved under virtually any standard assumption via a black-box reduction. More precisely: –If we want to have a “universal” instantiation of the Fiat-Shamir heuristic that works for all 3-message public-coin proofs, then we cannot prove its security via a black-box reduction from any assumption that has the format of a “cryptographic game”. –For many concrete proof systems, if we want to have a “specific” instantiation of the Fiat-Shamir heuristic for that proof system, then we cannot prove its security via a black box reduction from any “falsifiable assumption” that has the format of a cryptographic game with an efficient challenger. %B Theory of Cryptography %S Lecture Notes in Computer Science %I Springer Berlin Heidelberg %P 182 - 201 %8 2013/01/01/ %@ 978-3-642-36593-5, 978-3-642-36594-2 %G eng %U http://link.springer.com/chapter/10.1007/978-3-642-36594-2_11 %0 Book Section %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %D 2011 %T A Canonical Form for Testing Boolean Function Properties %A Dana Dachman-Soled %A Servedio, Rocco A. %E Goldberg, Leslie Ann %E Jansen, Klaus %E Ravi, R. %E Rolim, José D. P. %K Algorithm Analysis and Problem Complexity %K Boolean functions %K Computation by Abstract Devices %K Computer Communication Networks %K Computer Graphics %K Data structures %K Discrete Mathematics in Computer Science %K property testing %X In a well-known result Goldreich and Trevisan (2003) showed that every testable graph property has a “canonical” tester in which a set of vertices is selected at random and the edges queried are the complete graph over the selected vertices. We define a similar-in-spirit canonical form for Boolean function testing algorithms, and show that under some mild conditions property testers for Boolean functions can be transformed into this canonical form. Our first main result shows, roughly speaking, that every “nice” family of Boolean functions that has low noise sensitivity and is testable by an “independent tester,” has a canonical testing algorithm. Our second main result is similar but holds instead for families of Boolean functions that are closed under ID-negative minors. Taken together, these two results cover almost all of the constant-query Boolean function testing algorithms that we know of in the literature, and show that all of these testing algorithms can be automatically converted into a canonical form. %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %S Lecture Notes in Computer Science %I Springer Berlin Heidelberg %P 460 - 471 %8 2011/01/01/ %@ 978-3-642-22934-3, 978-3-642-22935-0 %G eng %U http://link.springer.com/chapter/10.1007/978-3-642-22935-0_39