Oded Goldreich, Silvio Micali, Avi Wigderson,
... Goldreich Technion, Haifa, Israel Technion, Haifa, IsraelView Profile , Silvio Micali Massachusetts Institute of Technology, Cambridge Massachusetts Institute of ...
Tópico(s): Logic, programming, and type systems
1991 - Association for Computing Machinery | Journal of the ACM
I suggest that the T4 lymphopenia of AIDS may be caused by antibodies raised against the human immunodeficiency virus that block the generation of T4 cells.
Tópico(s): Immune Cell Function and Interaction
1993 - National Academy of Sciences | Proceedings of the National Academy of Sciences
Yuling Chen, Juan Ma, Xianmin Wang, Xinyu Zhang, Huiyu Zhou,
... Cryptography: On the Work of Shafi Goldwasser and Silvio Micali; 2019: 307-328. 11Wang X, Ranellucci S, Katz ...
Tópico(s): Privacy-Preserving Technologies in Data
2022 - Wiley | International Journal of Intelligent Systems
Tópico(s): Formal Methods in Verification
1981 - Elsevier BV | Information Processing Letters
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 ...
Tópico(s): Computability, Logic, AI Algorithms
1984 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Shafi Goldwasser, Silvio Micali,
A new probabilistic model of data encryption is introduced. For this model, under suitable complexity assumptions, it is proved that extracting any information about the cleartext from the cyphertext is hard on the average for an adversary with polynomially bounded computational resources. The proof holds for any message space with any probability distribution. The first implementation of this model is presented. The security of this implementation is proved under the interactability assumptin of ...
Tópico(s): Cryptographic Implementations and Security
1984 - Elsevier BV | Journal of Computer and System Sciences
Michael Ben-Or, Oded Goldreich, Silvio Micali, Ronald L. Rivest,
Tópico(s): graph theory and CDMA systems
1985 - Springer Science+Business Media | Lecture notes in computer science
Manuel Blum, Paul Feldman, Silvio Micali,
Tópico(s): Chaos-based Image/Signal Encryption
1990 - Springer Science+Business Media | Lecture notes in computer science
Michael Ben-Or, Oded Goldreich, Shafi Goldwasser, Johan H̊astad, Joe Kilian, Silvio Micali, Phillip Rogaway,
Assuming the existence of a secure probabilistic encryption scheme, we show that every language that admits an interactive proof admits a (computational) zero-knowledge interactive proof. This result extends the result of Goldreich, Micali and Wigderson, that, under the same assumption, all of NP admits zero-knowledge interactive proofs. Assuming envelopes for bit commitment, we show tht every language that admits an interactive proof admits a perfect zero-knowledge interactive proof.
Tópico(s): Complexity and Algorithms in Graphs
1990 - Springer Science+Business Media | Lecture notes in computer science
To obtain security, one needs to utilize many resources. Among these are one-way functions, physically secure communication channels, and —though less well known— broadcasting.
Tópico(s): Privacy-Preserving Technologies in Data
1991 - Springer Science+Business Media | Lecture notes in computer science
Let N be a positive integer and let P ε ℤ [x] be a polynomial that is nonlinear on the set ℤ N of integers modulo N. If, by choosing x at random in an initial segment of ℤ N , P(x) (mod N) appears to be uniformly distributed in ℤ N to any polynomial-time observer, then it is possible to construct very efficient pseudorandom number generators that pass any polynomial-time statistical test. We analyse this generator from two points of view. A complexity theoretic analysis relates the perfectness of the ...
Tópico(s): Cryptography and Residue Arithmetic
1991 - Springer Science+Business Media | Journal of Cryptology
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.
Tópico(s): Cryptographic Implementations and Security
1992 - Association for Computing Machinery | Journal of the ACM
Silvio Micali, Ronald L. Rivest,
We introduce and provide the first example of a transitive digital signature scheme. Informally, this is a way to digitally sign vertices and edges of a dynamically growing, transitively closed, graph G so as to guarantee the following properties: Given the signatures of edges (u, v) and (v,w), anyone can easily derive the digital signature of the edge (u,w). It is computationaly hard for any adversary to forge the digital signature of any new vertex or other edge of G, even if he can request the legitimate ...
Tópico(s): Privacy-Preserving Technologies in Data
2002 - Springer Science+Business Media | Lecture notes in computer science
We put forward a new method of constructing Fiat-Shamir-like signature schemes that yields better "exact security" than the original Fiat-Shamir method. (We also point out, however, that such tight security does not make our modified schemes always preferable to the original ones. Indeed, there exist particularly efficient Fiat-Shamir-like schemes that, though only enjoying "loose security," by using longer keys may provably provide more security at a lower computational cost than their "tight-security" ...
Tópico(s): Cryptographic Implementations and Security
2002 - Springer Science+Business Media | Journal of Cryptology
Silvio Micali, Ronald L. Rivest,
We present new micropayment schemes that are more efficient and user friendly than previous ones. These schemes reduce bank processing costs by several orders of magnitude, while preserving a simple interface for both users and merchants. The schemes utilize a probabilistic deposit protocol that, in some of the schemes, may be entirely hidden from the users.
Tópico(s): Caching and Content Delivery
2002 - Springer Science+Business Media | Lecture notes in computer science
Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo,
We introduce a technique for traversal of Merkle trees, and propose an efficient algorithm that generates a sequence of leaves along with their associated authentication paths. For one choice of parameters, and a total of N leaves, our technique requires a worst-case computational effort of 2 logN/loglog N hash function evaluations per output, and a total storage capacity of less than 1.5 log2 N/loglogN hash values. This is a simultaneous improvement both in space and time complexity over any previously ...
Tópico(s): Advanced Steganography and Watermarking Techniques
2003 - Springer Science+Business Media | Lecture notes in computer science
Jonathan Herzog, Moses Liskov, Silvio Micali,
In this paper, we reconsider the notion of plaintext awareness. We present a new model for plaintext-aware encryption that is both natural and useful. We achieve plaintext-aware encryption without random oracles by using a third party. However, we do not need to trust the third party: even when the third party is dishonest, we still guarantee security against adaptive chosen ciphertext attacks. We show a construction that achieves this definition under general assumptions. We further motivate this ...
Tópico(s): Complexity and Algorithms in Graphs
2003 - Springer Science+Business Media | Lecture notes in computer science
Rosario Gennaro, Silvio Micali,
We define and construct Independent Zero-Knowledge Sets (ZKS) protocols. In a ZKS protocols, a Prover commits to a set S, and for any x, proves non-interactively to a Verifier if x ∈S or x ∉S without revealing any other information about S. In the independent ZKS protocols we introduce, the adversary is prevented from successfully correlate her set to the one of a honest prover. Our notion of independence in particular implies that the resulting ZKS protocol is non-malleable. On the way to this result ...
Tópico(s): Advanced Authentication Protocols Security
2006 - Springer Science+Business Media | Lecture notes in computer science
We show that collusion and wrong beliefs may cause a dramatic efficiency loss in the Vickrey mechanism for auctioning a single good in limited supply. We thus put forward a new mechanism guaranteeing efficiency in a very adversarial collusion model, where the players can partition themselves into arbitrarily many coalitions, exchange money with each other, and perfectly coordinate their actions. Our mechanism bypasses classic impossibility results (such as those of Green and Laffont, and of Schummer) ...
Tópico(s): Game Theory and Voting Systems
2012 - Elsevier BV | Journal of Economic Theory
Joe Kilian, Eyal Kushilevitz, Silvio Micali, Rafail Ostrovsky,
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 ...
Tópico(s): Internet Traffic Analysis and Secure E-voting
2000 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Mihir Bellare, Alexandra Boldyreva, Silvio Micali,
This paper addresses the security of public-key cryptosystems in a “multi-user” setting, namely in the presence of attacks involving the encryption of related messages under different public keys, as exemplified by Håstad’s classical attacks on RSA. We prove that security in the single-user setting implies security in the multi-user setting as long as the former is interpreted in the strong sense of “indistinguishability,” thereby pin-pointing many schemes guaranteed to be secure against Håstad-type ...
Tópico(s): Coding theory and cryptography
2000 - Springer Science+Business Media | Lecture notes in computer science
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 ( ...
Tópico(s): Computability, Logic, AI Algorithms
2000 - Society for Industrial and Applied Mathematics | SIAM Journal on Computing
Yevgeniy Dodis, Silvio Micali,
Secure Function Evaluation (SFE) protocols are very hard to design, and reducibility has been recognized as a highly desirable property of SFE protocols. Informally speaking, reducibility (sometimes called modular composition) is the automatic ability to break up the design of complex SFE protocols into several simpler, individually secure components. Despite much effort, only the most basic type of reducibility, sequential reducibility (where only a single sub-protocol can be run at a time), has been ...
Tópico(s): Cloud Data Security Solutions
2000 - Springer Science+Business Media | Lecture notes in computer science
Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali, Nir Shavit,
Johnson-Lindenstrauss (JL) matrices implemented by sparse random synaptic connections are thought to be a prime candidate for how convergent pathways in the brain compress information. However, to date, there is no complete mathematical support for such implementations given the constraints of real neural tissue. The fact that neurons are either excitatory or inhibitory implies that every so implementable JL matrix must be sign-consistent (i.e., all entries in a single column must be either all non- ...
Tópico(s): Neural dynamics and brain function
2014 - National Academy of Sciences | Proceedings of the National Academy of Sciences
Silvio Micali, Michael O. Rabin,
A solution to the persistent problem of preventing collusion in Vickrey auctions.
Tópico(s): Blockchain Technology Applications and Security
2014 - Association for Computing Machinery | Communications of the ACM
Shimoji and Watson (1998) prove that a strategy of an extensive game is rationalizable in the sense of Pearce if and only if it survives the maximal elimination of conditionally dominated strategies.Briefly, this process iteratively eliminates conditionally dominated strategies according to a specific order, which is also the start of an order of elimination of weakly dominated strategies.Since the final set of possible payoff profiles, or terminal nodes, surviving iterated elimination of weakly ...
Tópico(s): Experimental Behavioral Economics Studies
2013 - Econometric Society | Theoretical Economics
... 2011.05.002 Izmalkov, Sergei, Matt Lepinski, and Silvio Micali (2011), "Perfect implementation. Games and Economic Behavior, 71, ...
Tópico(s): Evolutionary Game Theory and Cooperation
2013 - Econometric Society | Theoretical Economics
We present a very simple method for generating a shared pseudo-random function from a poly-random collection of functions. We discuss the applications of our construction to key escrow.
Tópico(s): Cryptographic Implementations and Security
1995 - Springer Science+Business Media | Lecture notes in computer science
Rosario Gennaro, Silvio Micali,
Verifiable Secret Sharing is a fundamental primitive for secure cryp- tographic design. We present a stronger notion of verifiable secret sharing and exhibit a protocol implementing it. We show that our new notion is preferable to the old ones whenever verifiable secret sharing is used as a tool within larger protocols, rather than being a goal in itself. Indeed our definition, and so our protocol satisfying it, provably guarantees reducibility. Applications of this new notion in the field of secure ...
Tópico(s): Coding theory and cryptography
1995 - Springer Science+Business Media | Lecture notes in computer science
The public-key model for interactive proofs has proved to be quite effective in improving protocol efficiency [CGGM00]. We argue, however, that its soundness notion is more subtle and complex than in the classical model, and that it should be better understood to avoid designing erroneous protocols. Specifically, for the public-key model, we
Tópico(s): Cryptographic Implementations and Security
2001 - Springer Science+Business Media | Lecture notes in computer science