Arrow Research search

Author name cluster

Silvio Micali

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

39 papers
2 author rows

Possible papers

39

TCS Journal 2019 Journal Article

Algorand: A secure and efficient distributed ledger

  • Jing Chen
  • Silvio Micali

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.

Details DOI

SODA Conference 2013 Conference Paper

Optimal and Efficient Parametric Auctions

  • Pablo Daniel Azar
  • Constantinos Daskalakis
  • Silvio Micali
  • S. Matthew Weinberg

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.

Details

STOC Conference 2012 Conference Paper

Rational proofs

  • Pablo Daniel Azar
  • Silvio Micali

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.

Details

FOCS Conference 2011 Conference Paper

Mechanism Design with Set-Theoretic Beliefs

  • Jing Chen 0017
  • Silvio Micali

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.

Details

STOC Conference 2009 Conference Paper

A new approach to auctions and resilient mechanism design

  • Jing Chen 0017
  • Silvio Micali

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.

Details

FOCS Conference 2006 Conference Paper

Input-Indistinguishable Computation

  • Silvio Micali
  • Rafael Pass
  • Alon Rosen

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

Details

STOC Conference 2006 Conference Paper

Local zero knowledge

  • Silvio Micali
  • Rafael Pass

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.

Details

STOC Conference 2005 Conference Paper

Collusion-free protocols

  • Matt Lepinski
  • Silvio Micali
  • Abhi Shelat

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.

Details

FOCS Conference 2005 Conference Paper

Rational Secure Computation and Ideal Mechanism Design

  • Sergei Izmalkov
  • Silvio Micali
  • Matt Lepinski

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.

Details

FOCS Conference 2003 Conference Paper

Zero-Knowledge Sets

  • Silvio Micali
  • Michael O. Rabin
  • Joe Kilian

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.

Details

FOCS Conference 1999 Conference Paper

Verifiable Random Functions

  • Silvio Micali
  • Michael O. Rabin
  • Salil P. Vadhan

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.

Details

MFCS Conference 1998 Invited Paper

Computationally-Sound Checkers

  • Silvio Micali

Abstract We show that CS proofs have important implications for validating one-sided heuristics for NP. Namely, generalizing a prior notion of Blum's, we put forward the notion of a CS checker and show that special-type of CS proofs imply CS checkers for NP -complete languages.

Details

FOCS Conference 1994 Conference Paper

CS Proofs (Extended Abstracts)

  • Silvio Micali

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. >

Details

FOCS Conference 1994 Conference Paper

Reducibility and Completeness in Multi-Party Private Computations

  • Eyal Kushilevitz
  • Silvio Micali
  • Rafail Ostrovsky

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. >

Details

FOCS Conference 1989 Conference Paper

Minimum Resource Zero-Knowledge Proofs (Extended Abstract)

  • Joe Kilian
  • Silvio Micali
  • Rafail Ostrovsky

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/. >

Details

STOC Conference 1988 Conference Paper

Optimal Algorithms for Byzantine Agreement

  • Paul Feldman
  • Silvio Micali

We exhibit randomized Byzantine agreement (BA) algorithms achieving optimal running time and fault tolerance against all types of adversaries ever considered in the literature. Our BA algorithms do not require trusted parties, preprocessing, or non-constructive arguments.

Details

FOCS Conference 1986 Conference Paper

Dynamic deadlock resolution protocols (Extended Abstract)

  • Baruch Awerbuch
  • Silvio Micali

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.

Details

FOCS Conference 1986 Conference Paper

Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design (Extended Abstract)

  • Oded Goldreich 0001
  • Silvio Micali
  • Avi Wigderson

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.

Details

FOCS Conference 1985 Conference Paper

Byzantine Agreement in Constant Expected Time (and Trusting No One)

  • Paul Feldman
  • Silvio Micali

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.

Details

FOCS Conference 1984 Conference Paper

How to Construct Random Functions (Extended Abstract)

  • Oded Goldreich 0001
  • Shafi Goldwasser
  • Silvio Micali

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.

Details

FOCS Conference 1983 Conference Paper

How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin

  • Michael Luby
  • Silvio Micali
  • Charles Rackoff

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.

Details

FOCS Conference 1982 Conference Paper

Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs

  • Zvi Galil
  • Silvio Micali
  • Harold N. Gabow

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.

Details

STOC Conference 1982 Conference Paper

Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information

  • Shafi Goldwasser
  • Silvio Micali

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. Any implementation of a Public Key Cryptosystem, as proposed by Diffie and Hellman in [8], should possess this property. Our Encryption Scheme follows the ideas in the number theoretic implementations of a Public Key Cryptosystem due to Rivest, Shamir and Adleman [13], and Rabin [12].

Details

FOCS Conference 1982 Conference Paper

Why and How to Establish a Private Code on a Public Network (Extended Abstract)

  • Shafi Goldwasser
  • Silvio Micali
  • Po Tong

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.

Details

FOCS Conference 1980 Conference Paper

An O(sqrt(|v|) |E|) Algorithm for Finding Maximum Matching in General Graphs

  • Silvio Micali
  • Vijay V. Vazirani

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.

Details
v2026.09.13