-
Chapter and Conference Paper
Strictly-Black-Box Zero-Knowledge and Efficient Validation of Financial Transactions
Zero Knowledge Proofs (ZKPs) are one of the most striking innovations in theoretical computer science. In practice, the prevalent ZKP methods are, at times, too complicated to be useful for real-life applicati...
-
Chapter and Conference Paper
Cryptographic Combinatorial Clock-Proxy Auctions
We present a cryptographic protocol for conducting efficient, provably correct and secrecy-preserving combinatorial clock-proxy auctions. The “clock phase” functions as a trusted auction despite price discover...
-
Chapter and Conference Paper
DISC 20th Anniversary: Invited Talk Provably Unbreakable Hyper-Encryption Using Distributed Systems
Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Acces...
-
Chapter and Conference Paper
Provably Unbreakable Hyper-encryption Using Distributed Systems
Encryption is a fundamental building block for computer and communications technologies. Existing encryption methods depend for their security on unproven assumptions. We propose a new model, the Limited Acces...
-
Chapter and Conference Paper
Identity-Based Zero-Knowledge
We introduce and define the notion of identity-based zero-knowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a statement while ...
-
Chapter and Conference Paper
Hyper Encryption and Everlasting Secrets
A fundamental problem in cryptography is that of secure communication over an insecure channel, where a sender Alice wishes to communicate with a receiver Bob, in the presence of a powerful Adversary ...
-
Article
Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk
We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of different speeds. We consider a model in which each processor maintains an estimate of its own...
-
Chapter and Conference Paper
Hyper-Encryption and Everlasting Security
We present substantial extensions of works [1], [2], and all previous works, on encryption in the bounded storage model introduced by Maurer in [25]. The major new result is that the shared secret key employed by...
-
Chapter and Conference Paper
Information Theoretically Secure Communication in the Limited Storage Space Model
We provide a simple secret-key two-party secure communication scheme, which is provably information-theoretically secure in the limited-storage-space model. The limited-storage-space model postulates an eavesdrop...
-
Chapter and Conference Paper
Linear Consistency Testing
We extend the notion of linearity testing to the task of checking linear-consistency of multiple functions. Informally, functions are “linear” if their graphs form straight lines on the plane. Two such functio...
-
Chapter and Conference Paper
Super-Exponential Complexity of Presburger Arithmetic
Lower bounds are established on the computational complexity of the decision problem and on the inherent lengths of proofs for two classical decidable theories of logic: the first-order theory of the real numb...
-
Chapter and Conference Paper
Authentication, enhanced security and error correcting codes
In electronic communications and in access to systems, the issue of authentication of the Sender S of a message M, as well as of the message itself, is of paramount importance. Recently S. Goldwasser has raised t...
-
Chapter and Conference Paper
Correctness of programs and protocols through randomization
-
Chapter and Conference Paper
Optimal Parallel Pattern Matching Through Randomization
We present an optimal parallel pattern matching algorithm for d-dimensional patterns. Namely, for two d-dimensional arrays A and B, ∣A∣ = m d = M, ∣B∣ = n ...
-
Chapter and Conference Paper
Dependable parallel computing by randomization (Abstract)
-
Chapter and Conference Paper
The Information Dispersal Algorithm and its Applications
We present the Information Dispersal Algorithm (IDA) which breaks a file F of length L = |F| into n pieces F i , 1 ≤ i ≤ n, each of length |F i
-
Chapter and Conference Paper
Discovering Repetitions in Strings
There are many variants of problems involving string matchings. The basic problem is to determine whether a pattern string x appears as a (contiguous) substring of a text y, i.e. whether for some strings u, v,...
-
Article
The choice coordination problem
In the course of a concurrent computation, processes P1,..., Pn must reach a common choice of one out of k alternatives A 1,..., A k. They do this by protocols using k shared variables, one for each alternative. ...
-
Chapter
Solving Linear Equations by Means of Scalar Products
We shall state and solve a problem proposed by R. Brent and P. Wolfe concerning the solution of a system of linear equations by algorithms where the only operation permitted on the coefficient vectors a1, a2, ......
-
Article
Real time computation
We introduce a concept of real-time computation by a Turing machine. The relative strengths of one-tape versus two-tape machines is established by a new method of proofs of impossibility of actual computations.
