We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message M, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed M, even though the verifier will not see—let alone verify—all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain.After defining compact certificates, we demonstrate an effi-cient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50–280× smaller and 300–4000 cheaper to verify than a natural baseline approach.

A distributed ledger is a tamperproof sequence of data that can be publicly accessed and augmented by everyone, without being maintained by a centralized party. Distributed ledgers stand to revolutionize the way a modern society operates. They can secure all kinds of traditional transactions, such as payments, asset transfers and titles, in the exact order in which the transactions occur; and enable totally new transactions, such as cryptocurrencies and smart contracts. They can remove intermediaries and usher in a new paradigm for trust. As currently implemented, however, distributed ledgers scale poorly and cannot achieve their enormous potential. In this paper we propose Algorand, an alternative, secure and efficient distributed ledger. Algorand is permissionless and works in a highly asynchronous environment. Unlike prior implementations of distributed ledgers based on “proof of work,” Algorand dispenses with “miners” and requires only a negligible amount of computation. Moreover, its transaction history “forks” only with negligible probability: that is, Algorand guarantees the finality of a transaction the moment the transaction enters the ledger.

We present a very simple, cryptographic, binary Byzantine-agreement protocol that, with n >= 3t+1 >= 3 players, at most t of which are malicious, halts in expected 9 rounds.

Algorand is a new cryptocurrency that confirms transactions with latency on the order of a minute while scaling to many users. Algorand ensures that users never have divergent views of confirmed transactions, even if some of the users are malicious and the network is temporarily partitioned. In contrast, existing cryptocurrencies allow for temporary forks and therefore require a long time, on the order of an hour, to confirm transactions with high confidence.

It is well accepted that, in some auctions, a player's "true utility" may depend not only on the price he pays and whether or not he wins the good, but also on various forms of externalities, such as the prices paid by his competitors, and the identity and true value of the actual winner.

We propose investigating the design and analysis of game theoretic mechanisms when the players have very unstructured initial knowledge about themselves, but can refine their own knowledge at a cost.

Mechanism design enables a social planner to obtain a desired outcome by leveraging the players' rationality and their beliefs. It is thus a fundamental, yet unproven, intuition that the higher the level of rationality of the players, the better the set of obtainable outcomes.

Cryptography and distributed computation have been very successful in advancing the study of interaction of distinct computing agents. Moreover, both fields have been very successful in conversing with each other, sharing models and techniques. Notably, they both model agents as being either 'good' (i.e., following their prescribed programs) or 'bad' (i.e., deviating from their prescribed program, by stopping, by acting maliciously, or even by coordinating their malicious strategies). I believe however, that we have been neglecting a fundamental ingredient, UTILITY, which has long been recognized and studied by another scientific field, game theory, and in particular by a beautiful subfield of it, mechanism design. Mechanism design aims at obtaining a desired outcome by engineering a game that, rationally played, yields a desired outcome. In such games, multiple players interact very much as in a cryptographic/distributed protocol. But here players are not good or malicious. Rather, every player is RATIONAL, that is, always acts so as to maximize HIS OWN utility.

We study the social welfare performance of the VCG mechanism in the well-known and challenging model of self uncertainty initially put forward by Frank H. Knight and later formalized by Truman F. Bewley. Namely, the only information that each player i has about his own true valuation consists of a set of distributions, from one of which i's valuation has been drawn.

We study revenue maximization for digital auctions, where there are infinitely many copies of a good for sale. There are n buyers, each of whom is interested in obtaining one copy of the good. The buyers' private valuations are drawn from a joint distribution vec{F}. The seller does not know this distribution. The only information that she has are the mean ui and variance σi2 of each buyer i's marginal distribution Fi. We call such auctions parametric auctions. We construct a deterministic parametric auction that, for a wide class of distributions, guarantees a constant fraction of the optimal revenue achievable when the seller precisely knows the distribution F. Furthermore, our auction is a posted price mechanism and it is maximin optimal among all such mechanisms. That is, it is the posted price mechanism that maximizes revenue in the worst case over an adversarial choice of the distribution.

Information asymmetry is a central problem in both computer science and economics. In many fundamental problems, an uninformed principal wants to obtain some knowledge from an untrusted expert. This models several real-world situations, such as a manager's relation with her employees, or the delegation of computational tasks in mechanical turk.

Consider a seller who seeks to provide service to a collection of interested parties, subject to feasibility constraints on which parties may be simultaneously served. Assuming that a distribution is known on the value of each party for service—arguably a strong assumption—Myerson's seminal work provides revenue optimizing auctions [12]. We show instead that, for very general feasibility constraints, only knowledge of the median of each party's value distribution, or any other quantile of these distributions, or approximations thereof, suffice for designing simple auctions that simultaneously approximate both the optimal revenue and the optimal welfare. Our results apply to all downward-closed feasibility constraints under the assumption that the underlying, unknown value distributions are monotone hazard rate, and to all matroid feasibility constraints under the weaker assumption of regularity of the underlying distributions. Our results jointly generalize the single-item results obtained by Azar and Micali [2] on parametric auctions, and Daskalakis and Pierrakos [6] for simultaneously approximately optimal and efficient auctions.

We investigate the problem of optimal mechanism design, where an auctioneer wants to sell a set of goods to buyers, in order to maximize revenue. In a Bayesian setting the buyers' valuations for the goods are drawn from a prior distribution D, which is often assumed to be known by the seller. In this work, we focus on cases where the seller has no knowledge at all, and "the buyers know each other better than the seller knows them". In our model, D is not necessarily common knowledge. Instead, each buyer individually knows a posterior distribution associated with D. Since the seller relies on the buyers' knowledge to help him set a price, we call these types of auctions crowdsourced Bayesian auctions.

We study single-good auctions when each player knows his own valuation only within a constant multiplicative factor δ ε (0, 1), known to the mechanism designer. The classical notions of implementation in dominant strategies and implementation in undominated strategies are naturally extended to this setting, but their power is vastly different.

We study a new type of proof system, where an unbounded prover and a polynomial time verifier interact, on inputs a string x and a function f, so that the Verifier may learn f(x). The novelty of our setting is that there no longer are "good" or "malicious" provers, but only rational ones. In essence, the Verifier has a budget c and gives the Prover a reward r ∈ [0,c] determined by the transcript of their interaction; the prover wishes to maximize his expected reward; and his reward is maximized only if he the verifier correctly learns f(x). Rational proof systems are as powerful as their classical counterparts for polynomially many rounds of interaction, but are much more powerful when we only allow a constant number of rounds. Indeed, we prove that if f ∈ #P, then f is computable by a one-round rational Merlin-Arthur game, where, on input x, Merlin's single message actually consists of sending just the value f(x). Further, we prove that CH, the counting hierarchy, coincides with the class of languages computable by a constant-round rational Merlin-Arthur game. Our results rely on a basic and crucial connection between rational proof systems and proper scoring rules, a tool developed to elicit truthful information from experts.

In settings of incomplete information, we put forward (1) a very conservative -- indeed, purely set-theoretic -- model of the beliefs (including totally wrong ones) that each player may have about the payoff types of his opponents, and (2) a new and robust solution concept, based on mutual belief of rationality, capable of leveraging such conservative beliefs. We exemplify the applicability of our new approach for single-good auctions, by showing that, under our solution concept, a normal-form, simple, and deterministic mechanism guarantees -- up to an arbitrarily small, additive constant -- a revenue benchmark that is always greater than or equal to the second-highest valuation, and sometimes much greater. By contrast, we also prove that the same benchmark cannot even be approximated within any positive factor, under classical solution concepts.

For adversarial but computationally bounded models of error, we construct appealingly simple and efficient cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular: 1) For binary alphabets, we construct positive-rate coding schemes that are uniquely decodable under a 1/2 - γ error rate for any constant γ > 0. 2) For large alphabets, we construct coding schemes that are uniquely decodable under a 1 - R error rate for any information rate R > 0. Our results for large alphabets are actually optimal, since the "computationally bounded but adversarial channel" can simulate the behavior of the q-ary symmetric channel, where q denotes the size of the alphabet, the capacity of which is known to be upper-bounded by 1 - R. Our results hold under minimal assumptions on the communication infrastructure, namely: 1) we allow the channel to be more powerful than the receiver and 2) we only assume that some information about the sender-a public key-is known. (In particular, we do not require any shared secret key or joint local state between sender and receivers).

We put forward a new approach to mechanism design, and exemplify it via a new mechanism guaranteeing significant revenue in unrestricted combinatorial auctions. Our mechanism (1) succeeds in a new and very adversarial collusion model; (2) works in a new, equilibrium-less, and very strong solution concept; (3) benchmarks its performance against the knowledge that the players have about each other; (4) is computationally efficient and preserves the players' privacy to an unusual extent.

We put forward a first definition of general secure computation that, without any trusted set-up, handles an arbitrary number of concurrent executions; and is implementable based on standard complexity assumptions. In contrast to previous definitions of secure computation, ours is not simulation-based

We put forward the notion of Local Zero Knowledge and provide its first implementations in a variety of settings under standard complexity assumptions.Whereas the classical notion of Zero Knowledge guarantees the secrecy only of information that is hard to compute, the new one meaningfully guarantees the secrecy of any information (in case of perfect zero-knowledge, and asymptotically in all other cases). Consequently, Local Zero Knowledge remains very meaningful even if DP = NP.

Secure computation essentially guarantees that whatever computation n players can do with the help of a trusted party, they can also do by themselves. Fundamentally, however, this notion depends on the honesty of at least some players. We put forward and implement a stronger notion, rational secure computation, that does not depend on player honesty, but solely on player rationality. The key to our implementation is showing that the ballot-box - the venerable device used throughout the world to tally secret votes securely - can actually be used to securely compute any function. Our work bridges the fields of game theory and cryptography, and has broad implications for mechanism design.

Secure protocols attempt to minimize the injuries to privacy and correctness inflicted by malicious participants who collude during run-time. They do not, however, prevent malicious parties from colluding and coordinating their actions in the first place!Eliminating such collusion of malicious parties during the execution of a protocol is an important and exciting direction for research in Cryptography. We contribute the first general result in this direction: (1) We provide a rigorous definition of what a collusion-free protocol is; and (2) We prove that, under standard physical and computational assumptions ---i.e., plain envelopes and trapdoor permutations---collusion-free protocols exist for all finite protocol tasks with publicly observable actions. (Note that such tasks are allowed to have secret global state, and thus include Poker, Bridge, and other such games.Our solution is tight in the sense that, for a collusion-free protocol to exist, each of (a) the finiteness of the game of interest, (b) the public observability of its actions, and (c) the use of some type of physically private channel is provably essential.

Secure function evaluation (SFE) enables a group of players, by themselves, to evaluate a function on private inputs as securely as if a trusted third party had done it for them. A completely fair SFE is a protocol in which, conceptually, the function values are learned atomically.We provide a completely fair SFE protocol which is secure for any number of malicious players, using a novel combination of computational and physical channel assumptions.We also show how completely fair SFE has striking applications togame theory. In particular, it enables cheap-talk protocol that(a) achieve correlated-equilibrium payoffs in any game,(b) are the first protocols which provably give no additional power to any coalition of players, and(c) are exponentially more efficient than prior counterparts.

We show how a polynomial-time prover can commit to an arbitrary finite set S of strings so that, later on, he can, for any string x, reveal with a proof whether x /spl isin/ S or x /spl notin/ S, without revealing any knowledge beyond the verity of these membership assertions. Our method is non interactive. Given a public random string, the prover commits to a set by simply posting a short and easily computable message. After that, each time it wants to prove whether a given element is in the set, it simply posts another short and easily computable proof, whose correctness can be verified by any one against the public random string. Our scheme is very efficient; no reasonable prior way to achieve our desiderata existed. Our new primitive immediately extends to providing zero-knowledge databases.

Assume each of two parties has something the other wants. Then, a fair exchange is an electronic protocol guaranteeing that either both parties get what they want, or none of them does. Protocols relying on traditional trusted parties easily guarantee such exchanges, but are inefficient (because a trusted party must be part of every execution) and expensive (because trusted parties want to be paid for each execution).In this paper we• Quickly review fair exchanges that are optimistic, that is, relying on a trusted party that (1) does not participate at all in an honest execution, and yet (2) guarantees the fairness of all executions; and• Present some older and surprisingly simple optimistic protocols for fair certified e-mail and contract signing that never appeared in the scientific literature.

Formal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.In this paper, we formalize and implement a variant of multi-signature schemes, Accountable-Subgroup Multisignatures (ASM). In essence, ASM schemes enable any subgroup, S, of a given group, G, of potential signers, to sign efficiently a message M so that the signature provably reveals the identities of the signers in S to any verifier.Specifically, we provide:The first formal model of security for multisignature schemes that explicitly includes key generation (without relying on trusted third parties);A protocol, based on Schnorr's signature scheme [33], that is both provable and efficient:Only three rounds of communication are required per signature.The signing time per signer is the same as for the single-signer Schnorr scheme, regardless of the number of signers.The verification time is only slightly greater than that for the single-signer Schnorr scheme.The signature length is the same as for the single signer Schnorr scheme, regardless of the number of signers.Our proof of security relies on random oracles and the hardness of the Discrete Log Problem.

We introduce the notion of Resettable Zero-Knowledge (rZK), a new security measure for cryptographic protocols which strengthens the classical notion of zero-knowledge.In essence, an rZK protocol is one that remains zero knowledge even if an adversary can interact with the prover many times, each time resetting the prover to its initial state and forcing it to use the same random tape.All known examples of zero-knowledge proofs and arguments are trivially breakable in this setting.Moreover, by definition, all zero-knowledge proofs of knowledge are breakable in this setting.Under general complexity assumptions, which hold for example if the Discrete Logarithm Problem is hard, we construct: • Resettable Zero-Knowledge proof-systems for NP with non-constant number of rounds.* Five-round Resettable Witness-Indistinguishable proofsystems for NP. e Four-round Resettabie Zero-Knowledge arguments for NP in the public key model: where verifiers have fixed, public keys associated with them.In addition to shedding new light on what makes zero knowledge possible (by constructing ZK protocols that use randomness in a dramatically weaker way than before), rZK has great relevance to applications.Firstly, rZK protocols are closed under parallel and concurrent execution and thus are guaranteed to be secure when implemented in fully asynchronous networks, even if an adversary schedules the arrival of every message sent so as to foil security.Secondly, rZK protocols enlarge the range of physical ways in which provers of ZK protocols can be securely implemented, including devices which cannot reliably toss coins on line, nor keep state *A subset of this work is included in patent application [21].

We define the notions of reducibility and completeness in (two-party and multiparty) private computations. Let g be an n-argument function. We say that a function f is reducible to a function g if n honest-but-curious players can compute the function fn -privately, given a black box for g (for which they secretly give inputs and get the result of operating g on these inputs). We say that g is complete (for private computations) if every function f is reducible to g. In this paper, we characterize the complete boolean functions: we show that a boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black box available). Namely, for n-argument boolean functions, the notions of completeness and n-privacy are complementary. This characterization provides a huge collection of complete functions any nonprivate boolean function!) compared to very few examples that were given (implicitly) in previous work. On the other hand, for nonboolean functions, we show that these two notions are not complementary.

This paper puts forward a new notion of a proof based on computational complexity and explores its implications for computation at large. Computationally sound proofs provide, in a novel and meaningful framework, answers to old and new questions in complexity theory. In particular, given a random oracle or a new complexity assumption, they enable us to prove that verifying is easier than deciding for all theorems; provide a quite effective way to prove membership in computationally hard languages (such as ${\cal C}o$-$\cal N \cal P$-complete ones); and show that every computation possesses a short certificate vouching its correctness. Finally, if a special type of computationally sound proof exists, we show that Blum's notion of program checking can be meaningfully broadened so as to prove that $\cal N \cal P$-complete languages are checkable.

We efficiently combine unpredictability and verifiability by extending the Goldreich-Goldwasser-Micali (1986) construction of pseudorandom functions f/sub s/ from a secret seed s, so that knowledge of s not only enables one to evaluate f/sub s/ at any point x, but also to provide an NP-proof that the value f/sub s/(x) is indeed correct without compromising the unpredictability of f/sub s/ at any other point for which no such a proof was provided.

Broadcasting guarantees the recipient of a message that everyone else has received the same message. This guarantee no longer exists in a setting in which all communication is person-to-person and some of the people involved are untrustworthy: though he may claim to send the same message to everyone, an untrustworthy sender may send different messages to different people. In such a setting, Byzantine agreement offers the "best alternative" to broadcasting. Thus far, however, reaching Byzantine agreement has required either many rounds of communication (i.e., messages had to be sent back and forth a number of times that grew with the size of the network) or the help of some external trusted party. In this paper, for the standard communication model of synchronous networks in which each pair of processors is connected by a private communication line, we exhibit a protocol that, in probabilistic polynomial time and without relying on any external trusted party, reaches Byzantine agreement in an expected constant number of rounds and in the worst natural fault model. In fact, our protocol successfully tolerates that up to 1/3 of the processors in the network may deviate from their prescribed instructions in an arbitrary way, cooperate with each other, and perform arbitrarily long computations. Our protocol effectively demonstrates the power of randomization and zero-knowledge computation against errors. Indeed, it proves that "privacy" (a fundamental ingredient of one of our primitives), even when is not a desired goal in itself (as for the Byzantine agreement problem), can be a crucial tool for achieving correctness. Our protocol also introduces three new primitives---graded broadcast, graded verifiable secret sharing, and oblivious common coin---that are of independent interest, and may be effectively used in more practical protocols than ours.

We define the notions of reducibility and completeness in multi-party private computations. Let g be an n-argument function. We say that a function f is reducible to g if n honest-but-curious players can compute the function f n-privately, given a black-box for g (for which they secretly give inputs and get the result of operating g on these inputs). We say that g is complete (for multi-party private computations) if every function f is reducible to g. In this paper, we characterize the complete Boolean functions: we show that a Boolean function g is complete if and only if g itself cannot be computed n-privately (when there is no black-box available). Namely, for Boolean functions, the notions of completeness and n-privacy are complementary. This characterization gives a huge collection of complete functions (any non-private Boolean function!) compared to very few examples given (implicitly) in previous work. On the other hand, for non-Boolean functions, we show that these two notions are not complementary. Our results can be viewed as a generalization (for multi-party protocols and for (n/spl ges/2)-argument functions) of the two-party case, where it was known that Oblivious Transfer protocol (and its variants) are complete.>

This paper puts forward a computationally-based notion of proof and explores its implications to computation at large. In particular, given a random oracle or a suitable cryptographic assumption, we show that every computation possesses a short certificate vouching its correctness, and that, under a cryptographic assumption, any program for a /spl Nscr//spl Pscr/-complete problem is checkable in polynomial time. In addition, our work provides the beginnings of a theory of computational complexity that is based on "individual inputs" rather than languages.>

A digital signature scheme is presented, which is based on the existence of any trapdoor permutation. The scheme is secure in the strongest possible natural sense: namely, it is secure against existential forgery under adaptive chosen message attack.

In this paper the generality and wide applicability of Zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff is demonstrated. These are probabilistic and interactive proofs that, for the members of a language, efficiently demonstrate membership in the language without conveying any additional knowledge. All previously known zero-knowledge proofs were only for number-theoretic languages in NP fl CONP. Under the assumption that secure encryption functions exist or by using "physical means for hiding information," it is shown that all languages in NP have zero-knowledge proofs. Loosely speaking, it is possible to demonstrate that a CNF formula is satisfiable without revealing any other property of the formula, in particular, without yielding neither a

This paper investigates the possibility of disposing of interaction between prover and verifier in a zero-knowledge proof if they share beforehand a short random string. Without any assumption, it is proven that noninteractive zero-knowledge proofs exist for some number-theoretic languages for which no efficient algorithm is known. If deciding quadratic residuosity (modulo composite integers whose factorization is not known) is computationally hard, it is shown that the NP-complete language of satisfiability also possesses noninteractive zero-knowledge proofs.

In a network of n players, each player i having private input zi, we show how the players can collaboratively evaluate a function f(zl, ..., zn) in a way that does not compromise the privacy of the players' inputs, and yet requires only a constant number of rounds of interaction.The underlying model of computation is a complete network of private channels, with broadcast, and a majority of the players must behave honestly.Our solution assumes the existence of a one-way function.share bi to player i.For some parameter t, t < n/2, we require that no t players get information about b from their pieces; and yet, b is recoverable, and is known to be recoverable, given the cooperation of the n -t good players--even if the t bad players try to obstruct b's recovery, or try to alter the recovered value.The value b which a player has effectively "committed to" is independent of the values that honest players may concurrently be committing to.After the sharing stage, a computation stage follows, in which each player, given his own shares of xl, ..., x,~, computes his own share of f(zt,..., z,~).To accomplish this, the function f to be evaluated is represented by a

Quadratic residuosity and graph isomorphism are classic problems and the canonical examples of zero-knowledge languages.However, despite much research effort, all previous zero-knowledge proofs for them required either unproven complexity assumptions or an unbounded number of rounds of message exchange.For both (and similar) languages, we exhibit zeroknowledge proofs that require 5 rounds and no unproven assumptions.Our solution is essentially optimal, in this setting, due to a recent lower bound argument of Goldreich and Krawczyk.

Article The (true) complexity of statistical zero knowledge Share on Authors: M. Bellare MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile , S. Micali MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile , R. Ostrovsky MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, MAView Profile Authors Info & Claims STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of ComputingApril 1990 Pages 494–502https://doi.org/10.1145/100216.100285Online:01 April 1990Publication History 40citation347DownloadsMetricsTotal Citations40Total Downloads347Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Two parties, A and B, want to sign a contract C over a communication network. To do so, they must simultaneously exchange their commitments to C. Since simultaneous exchange is usually impossible in practice, protocols are needed to approximate simultaneity by exchanging partial commitments in piece-by-piece manner. During such a protocol, one party or another may have a slight advantage; a fair protocol keeps this advantage within acceptable limits. A new protocol is proposed. It is fair in the sense that, at any stage in its execution, the conditional probability that one party cannot commit both parties to the contract given that the other party can, is close to zero. This is true even if A and B have vastly different computing powers and is proved under very weak cryptographic assumptions.>

Several resources relating to zero-knowledge protocols are considered. They are the number of envelopes used in the protocol, the number of oblivious transfer protocols executed during the protocol, and the total amount of communication required by the protocol. It is shown that after a preprocessing stage consisting of O(k) executions of oblivious transfer, any polynomial number of NP-theorems of any polysize can be proved noninteractively and in zero knowledge, on the basis of the existence of any one-way function, so that the probability of accepting a false theorem is less than 1/2/sup k/.>

Usually, a proof of a theorem contains more knowledge than the mere fact that the theorem is true. For instance, to prove that a graph is Hamiltonian it suffices to exhibit a Hamiltonian tour in it; however, this seems to contain more knowledge than the single bit Hamiltonian/non-Hamiltonian. In this paper a computational complexity theory of the “knowledge” contained in a proof is developed. Zero-knowledge proofs are defined as those proofs that convey no additional knowledge other than the correctness of the proposition in question. Examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity. These are the first examples of zero-knowledge proofs for languages not known to be efficiently recognizable.

We present a digital signature scheme which combines high security with the property of being based on a very general assumption: the existence of trapdoor permutations. Previous signature schemes with comparable levels of security were based on assumptions of the computational hardness of particular algebraic problems such as factoring. Our contribution is to free this important cryptographic primitive from the fortunes of any specific algebraic problem by establishing a truly general signature scheme.

We show that interaction in any zero-knowledge proof can be replaced by sharing a common, short, random string. We use this result to construct the first public-key cryptosystem secure against chosen ciphertext attack.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1988.

We present a digital signature scheme based on the computational difficulty of integer factorization. The scheme possesses the novel property of being robust against an adaptive chosen-message attack: an adversary who receives signatures for messages of his choice (where each message may be chosen in a way that depends on the signatures of previously chosen messages) cannot later forge the signature of even a single additional message. This may be somewhat surprising, since in the folklore the properties of having forgery being equivalent to factoring and being invulnerable to an adaptive chosen-message attack were considered to be contradictory. More generally, we show how to construct a signature scheme with such properties based on the existence of a “claw-free” pair of permutations—a potentially weaker assumption than the intractibility of integer factorization. The new scheme is potentially practical: signing and verifying signatures are reasonably fast, and signatures are compact.

Three very different formal definitions of security for public-key cryptosystems have been proposed—two by Goldwasser and Micali and one by Yao. We prove all of them to be equivalent. This equivalence provides evidence that the right formalization of the notion of security has been reached.

We present a polynomial-time algorithm that, given as a input the description of a game with incomplete information and any number of players, produces a protocol for playing the game that leaks no partial information, provided the majority of the players is honest.

The deadlock resolution problem can be informally stated as follows. There exists a set of actions, generated at different times, with some complex and contradictory precedence constraints between their executions. To resolve a deadlock, some of the actions need to be aborted; this enables to execute the remaining ones. This problem naturally arises in the context of distributed systems, e.g. communication networks, distributed operating systems and distributed databases, where actions are generated by many processors, and are not coordinated by a central controller. In this paper, we are concerned with efficient distributed algorithms (protocols) for resolution of dynamic deadlocks. Such resolution protocols must operate on-line without any knowledge of the future and using only local information. The main contribution of the paper is a reduction of the most general dynamic deadlock resolution problem to a conceptually simpler static problem, in which all actions are known a priori. The complexity of our reduction is O (m + n logn) in communication and O (n) in time, where n is the number of actions and m is total number of constraints. Since the static deadlock resolution requires at least Ω(m + n logn) in communication and Ω(n) in time, our reduction essentially shows that the resolution of dynamic deadlocks is not any harder than resolution of the static ones. We also show here a simple and optimal algorithm for the static problem, which, together with the above reduction, yields an optimal dynamic deadlock resolution protocol.

In this paper we demonstrate the generality and wide applicability of zero-knowledge proofs, a notion introduced by Goldwasser, Micali and Rackoff. These are probabilistic and interactive proofs that, for the members x of a language L, efficiently demonstrate membership in the language without conveying any additional knowledge. So far, zero-knowledge proofs were known only for some number theoretic languages in NP ∩ Co-NP.

A constructive theory of randomness for functions, based on computational complexity, is developed, and a pseudorandom function generator is presented. This generator is a deterministic polynomial-time algorithm that transforms pairs ( g , r ), where g is any one-way function and r is a random k -bit string, to polynomial-time computable functions ƒ r : {1, … , 2 k } → {1, … , 2 k }. These ƒ r 's cannot be distinguished from random functions by any probabilistic polynomial-time algorithm that asks and receives the value of a function at arguments of its choice. The result has applications in cryptography, random constructions, and complexity theory.

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes $O(\log n)$ time. We use these generalized priority queues to construct an $O(EV\log V)$ algorithm for finding a maximal weighted matching in general graphs.

We present a novel cryptographic algorithm for Byzantine agreement in a network with l=O(n) faulty processors and in the most adversarial setting. Our algorithm requires, once and for all, O(t) rounds of preprocessing. Afterwards it allows us to reach each individual Byzantine agreement in constant expected time. Our solution does not make use of any trusted party.

How much knowledge should be communicated fir proving a theorem T?Certainly enough to see that T is true, but usually much more.For instance, to prove that a graph is Hamiltonian it suffices to exhibit an Hamiltonian tour.This appears, however, to contain ,much additional knowledge than the single bit "HamiltonianInon-Hamiltonian".We give a computational complexity measure of knowledge and measure tic amount of additional knowlcdgc contained in proofs.

This paper develops a constructive theory of randomness for functions based on computational complexity. We present a deterministic polynomial-time algorithm that transforms pairs (g,r), where g is any one-way (in a very weak sense) function and r is a random k-bit string, to polynomial-time computable functions f/sub r/:{1,..., 2/sup k} /spl I.oarr/ {1, ..., 2/sup k/}. These f/sub r/'s cannot be distinguished from random functions by any probabilistic polynomial time algorithm that asks and receives the value of a function at arguments of its choice. The result has applications in cryptography, random constructions and complexity theory.

We present a general signature scheme which uses any pair of trap-door permutations (f0, f1) for which it is infeasible to find any x, y with f0(x) = f1(y). The scheme possesses the novel property of being robust against an adaptive chosen message attack: no adversary who first asks for and then receives sgnatures for messages of his choice (which may depend on previous signatures seen) can later forge the signature of even a singl additional message.

We give a set of conditions that allow one to generate 50–50 unpredictable bits.Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits. We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50–50 chance is easily transformable to an “equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if “head” guess “0”, if “tail” guess “1”

We present a cryptographic protocol allowing two mutually distrusting parties, A and B, each having a secret bit, to "simultaneously" exchange the values of those bits. It is assumed that initially each party presents a correct encryption of his secret bit to the other party. We develop a new tool to implement our protocol: a slightly biased symmetric coin. The key property of this coin is that from each flip A receives a piece of probabilistic information about B's secret bit which is symmetric to the piece of information B receives about A's secret bit.

The notion of digital signature based on trapdoor functions has been introduced by Diffie and Hellman[3]. Rivest, Shamir and Adleman[8] gave the first number theoretic implementation of a signature scheme based on a trapdoor function. If f is a trapdoor function and m a message, f−1(m) is the signature of m. The signature can be verified by computing f(f−1(m)) = m. This approach presents the following problems even when f is hard to invert: 1) there may be special message spaces (or subsets of them) that are easy to sign without knowing the trapdoor information 2) it is possible to forge the signature of random numbers; this violates the requirements of many protocols 3) given a polynomial number of signed messages, it may be possible to sign a new one without knowing the trapdoor information. We solve the above problems by exhibiting two signature schemes for which any strategy of an adversary, who has seen all previously signed messages, that has a moderate success in forging even a single additional signature, is transformable to a fast algorithm for factoring or inverting the RSA function. This provably holds for all message spaces with all possible Probability distributions. Thus, in particular, given the signature of m, forging the signature of m+1 or 2m or 2sm is as hard as factoring. The two signature schemes

We give a set of conditions that allow one to generate 50–50 unpredictable bits.Based on those conditions, we present a general algorithmic scheme for constructing polynomial-time deterministic algorithms that stretch a short secret random input into a long sequence of unpredictable pseudo-random bits.We give an implementation of our scheme and exhibit a pseudo-random bit generator for which any efficient strategy for predicting the next output bit with better than 50–50 chance is easily transformable to an “equally efficient” algorithm for solving the discrete logarithm problem. In particular: if the discrete logarithm problem cannot be solved in probabilistic polynomial time, no probabilistic polynomial-time algorithm can guess the next output bit better than by flipping a coin: if “head” guess “0”, if “tail” guess “1”

We define two generalized types of a priority queue by allowing some forms of changing the priorities of the elements in the queue. We show that they can be implemented efficiently. Consequently, each operation takes O(log n) time. We use these generalized priority queues to construct an O(EV log V) algorithm for finding a maximal weighted matching in general graphs.

The Diffie and Hellman model of a Public Key Cryptosystem has received much attention as a way to provide secure network communication. In this paper, we show that the original Diffie and Hellman model does not guarantee security against other users in the system. It is shown how users, which are more powerful adversarys than the traditionally considered passive eavesdroppers, can decrypt other users messages, in implementations of Public Key Cryptosystem using the RSA function, the Rabin function and the Goldwasser&Micali scheme. This weakness depends on the bit security of the encryption function. For the RSA (Rabin) function we show that computing, from the cyphertext, specific bits of the cleartext, is polynomially equivalent to inverting the function (factoring). As for many message spaces, this bit can be easily found out by communicating, the system is insecure. We present a modification of the Diffie and Hellman model of a Public-Key Cryptosystem, and one concrete implementation of the modified model. For this implementation, the difficulty of extracting partial information about clear text messages from their encoding, by eavesdroppers, users or by Chosen Cyphertext Attacks is proved equivalent to the computational difficulty of factoring. Such equivalence proof holds in a very strong probabilistic sense and for any message space. No additional assumptions, such as the existence of a perfect signature scheme, or a trusted authentication center, are made.

This paper proposes an Encryption Scheme that possess the following property : An adversary, who knows the encryption algorithm and is given the cyphertext, cannot obtain any information about the clear-text.

In this paper we present an 0(√|V|·|E|) algorithm for finding a maximum matching in general graphs. This algorithm works in 'phases'. In each phase a maximal set of disjoint minimum length augmenting paths is found, and the existing matching is increased along these paths. Our contribution consists in devising a special way of handling blossoms, which enables an O(|E|) implementation of a phase. In each phase, the algorithm grows Breadth First Search trees at all unmatched vertices. When it detects the presence of a blossom, it does not 'shrink' the blossom immediately. Instead, it delays the shrinking in such a way that the first augmenting path found is of minimum length. Furthermore, it achieves the effect of shrinking a blossom by a special labeling procedure which enables it to find an augmenting path through a blossom quickly.

Abstract The notion of a minimal form is defined as an extension of the notion of a normal form inλ-β-calculus and its meaning is discussed in a computational environment. The features of the Knuth-Gross reduction strategy are used to prove that to possess a minimal form, for a generic term, is a semidecidable predicate.