Halevi, Tzipora, Saxena, Nitesh, Halevi, Shai
In this paper, we propose an HB-like protocol for privacy-preserving authentication of RFID tags, whereby a tag can remain anonymous and untraceable to an adversary during the authentication process....
Circular-Secure Encryption from Decision Diffie-Hellman (2009)
Dan Boneh, Shai Halevi, Mike Hamburg, Rafail Ostrovsky
Abstract. We describe a public-key encryption system that remains secure even encrypting messages that depend on the secret keys in use. In particular, it remains secure under a “key cycle ”...
ABSTRACT Private Approximation of NP-hard Functions [Extended Abstract] (2009)
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
Threshold RSA for Dynamic and Ad-Hoc Groups (2008)
Rosario Gennaro, Shai Halevi, Hugo Krawczyk, Tal Rabin
Abstract. We consider the use of threshold signatures in ad-hoc and dynamic groups such as MANETs (“mobile ad-hoc networks”). While the known threshold RSA signature schemes have several...
On Seed-Incompressible Functions (2008)
Shai Halevi, Steven Myers, Charles Rackoff
Abstract. We investigate a new notion of security for “cryptographic functions ” that we term seed incompressibility (SI). We argue that this notion captures some of the intuition for the alleged...
Background: Digital Signatures At Risk! (2008)
Shai Halevi, Hugo Krawczyk, Post-wang Trauma
� SHA-1 much weaker than thought � Lost confidence in SHA-1 but also in our ability to design secure collision resistant hashing (how much cryptanalysis ahead?) � Non-repudiable * digital...
Implementing the Halevi-Krawczyk Randomized Hashing Scheme (2008)
Shai Halevi, Weidong Shao, Hugo Krawczyk, Dan Boneh, Mike Mcintosh
The Halevi-Krawczyk randomized hashing scheme, also known as RMX, is designed to be used as a front-end to existing hash-then-sign signature schemes, such as RSA and DSS. RMX frees these signatures...
Universally Composable Password-Based Key (2008)
Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell
Abstract. We propose and realize a definition of security for passwordbased key exchange within the framework of universally composable (UC) security, thus providing security guarantees under...
Circular-Secure Encryption from Decision Diffie-Hellman (2008)
Dan Boneh, Shai Halevi, Mike Hamburg, Rafail Ostrovsky
Let E be a public-key encryption system and let (pk i, ski) be public/private key pairs for E for i = 0,..., n. A natural question is whether E remains secure once an adversary obtains an encryption...
Abstract. In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such...
The MARS Encryption Algorithm (2007)
Carolynn Burwick, Don Coppersmith, Edward D'Avignon, Edward D’avignon C, Rosario Gennaro, Shai Halevi, ...
This paper describes and analyzes the MARS symmetric-key encryption algorithm which is a new block cipher submitted to NIST for consideration as the Advanced Encryption Standard (AES). MARS supports...
The MARS Encryption Algorithm (2007)
Carolynn Burwick Don, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas, David Safford
This paper describes and analyzes the MARS symmetric-key encryption algorithm which is a new block cipher submitted to NIST for consideration as the Advanced Encryption Standard (AES). MARS supports...
A Stronger Notion of Proofs of Knowledge (2007)
Proofs of knowledge are central to cryptographic protocols, and many definitions for such proofs have been proposed. In this work we put forward a new definition, strictly stronger than previous...
Alain Azagury, Ran Canetti, Shai Halevi, Ealan Henis, Dalit Naor, Noam Rinetzky, ...
Storage Area Networks (SAN) are based on direct interaction between clients and storage servers exposing the storage server to network attacks. Giving the client direct access to the storage servers...
Ran Canetti, Oded Goldreich, Shai Halevi
the random-oracle methodology as applied to length-restricted signature schemes
Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai
Abstract. We study the problem of partial key exposure. Standard cryptographic de nitions and constructions do not guarantee any security even if a tiny fraction of the secret key is compromised. We...
We introduce the notion of incremental codes. Unlike a regular code of a given rate, which is an unordered set of elements with a large minimum distance, an incremental code is an ordered vector of...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
Dan Boneh, Shai Halevi, Nick Howgrave-graham
Abstract. We study a class of problems called Modular Inverse Hidden Number Problems (MIHNPs). The basic problem in this class is the following: Given many pairs x i; msbk ( + x i) 1
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
KNOWLEDGE COMPLEXITY VERSUS COMPUTATIONAL COMPLEXITY AND THE HARDNESS OF APPROXIMATIONS (2007)
Erez Petrank, Ran Canetti, Benny Chor, Eli Dichterman, Guy Even, Shai Halevi, ...
This research was carried out in the faculty of Computer Science under the
Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai
Abstract. We study the problem of partial key exposure. Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is compromised. We...
Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim
The notion of private approximation was introduced recently by Feigenbaum, Fong, Strauss and Wright. Informally, a private approximation of a function f is another function F that approximates f in...
from Lattice Reduction Problems (2007)
Public-key Cryptosystems, Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
Ran Canetti, Oded Goldreich, Shai Halevi
the random-oracle methodology as applied to length-restricted signature schemes
Shai Halevi, Yael Tauman Kalai
We present a general framework for constructing two-message oblivious transfer protocols using a modification of Cramer and Shoup’s notion of smooth projective hashing (2002). This framework is an...
This work describes a mode of operation, TET, that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. When using an n-bit block...
Security under key-dependent inputs (2007)
In this work we re-visit the question of building cryptographic primitives that remain secure even when queried on inputs that depend on the secret key. This was investigated by Black, Rogaway, and...
Chosen ciphertext secure public key threshold encryption without random oracles (2006)
Dan Boneh, Xavier Boyen, Shai Halevi
Abstract. We present a non-interactive chosen ciphertext secure threshold encryption system. The proof of security is set in the standard model and does not use random oracles. Our construction uses...
Ibm Watson Research, Ran Canetti, Shai Halevi, Michael Steiner
We address the issue of encrypting data in local storage using a key that is derived from the user's password. The typical solution in use today is to derive the key from the password using a...
Chosen ciphertext secure public key threshold encryption without random oracles (2006)
Dan Boneh, Xavier Boyen, Shai Halevi
Abstract. We present a non-interactive chosen ciphertext secure threshold encryption system. The proof of security is set in the standard model and does not use random oracles. Our construction uses...
Mitigating dictionary attacks on password-protected local storage (2006)
Ran Canetti, Shai Halevi, Michael Steiner
We address the issue of encrypting data in local storage using a key that is derived from the user’s password. The typical solution in use today is to derive the key from the password using a...
The RMX Transform and Digital Signatures ∗ (2006)
This document describes RMX, a simple message randomization scheme that when used as a front end to existing hash-then-sign signature schemes, such as RSA and DSS, frees these signatures from their...
We present a formal model and a simple architecture for robust pseudorandom generation that ensures resilience in the face of an observer with partial knowledge (or even partial control) of the...
A Sufficient Condition for Key-Privacy (2005)
The notion of key privacy for encryption schemes was defined formally by Bellare, Boldyreva, Desai and Pointcheval in Asiacrypt 2001. This notion seems useful in settings where anonymity is...
An Architecture for Robust Pseudo-Random Generation and Applications to /dev/random (2005)
We present a formal model and a simple architecture for robust pseudorandom generation that ensures resilience in the face of an observer with partial knowledge (or even partial control) of the...
Hardness amplification of weakly verifiable puzzles (2005)
Ran Canetti, Shai Halevi, Michael Steiner
Is it harder to solve many puzzles than it is to solve just one? This question has different answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by...
Enforcing Confinement in Distributed Storage and a cryptographic model for access control (2005)
Shai Halevi, Paul A. Karger, Dalit Naor
This work is concerned with the security of the standard T10 OSD protocol, a capabilitybased protocol for object stores designed by the OSD SNIA working group. The Object Store security protocol is...
Enforcing Confinement in Distributed Storage and a cryptographic model for access control (2005)
Shai Halevi, Paul A. Karger, Dalit Naor
This work is concerned with the security of the standard T10 OSD protocol, a capabilitybased protocol for object stores designed by the OSD SNIA working group. The Object Store security protocol is...
A sufficient condition for key-privacy (2005)
The notion of key privacy for encryption schemes was defined formally by Bellare, Boldyreva, Desai and Pointcheval in Asiacrypt 2001. This notion seems useful in settings where anonymity is...
Universally composable password-based key exchange (2005)
Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, Philip Mackenzie
Abstract We propose and realize a definition of security for password-based key exchange within theframework of universal composability (UC), thus providing security guarantees under arbitrary...
This paper tries to sell a potential approach to making the process of writing and verifying our cryptographic proofs less prone to errors. Specifically, I advocate creating an automated tool to help...
Universally composable password-based key exchange (2005)
Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, Philip Mackenzie
Abstract We propose and realize a definition of security for password-based key exchange within theframework of universal composability (UC), thus providing security guarantees under arbitrary...
Strengthening Digital Signatures via Randomized Hashing (2005)
We propose randomized hashing as a mode of operation for cryptographic hash functions intended for use with standard digital signatures and without necessitating of any changes in the internals of...
Strengthening Digital Signatures via Randomized Hashing (2005)
We propose randomized hashing as a mode of operation for cryptographic hash functions intended for use with standard digital signatures and without necessitating of any changes in the internals of...
Chosen-ciphertext security from identity-based encryption (2004)
Ran Canetti, Shai Halevi, Jonathan Katz
We show how to construct a CCA-secure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our conversion from an IBE scheme to a CCA-secure scheme is simple,...
A Parallelizable Enciphering Mode (2004)
We describe a block-cipher mode of operation, EME, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m 2 [1::n]. The mode is parallelizable,...
EME: extending EME to handle arbitrary-length messages with associated data (2004)
This work describes a mode of operation, EME # , that turns a regular block cipher into a length-preserving enciphering scheme for messages of (almost) arbitrary length. Specifically, the resulting...
Adaptively-Secure, Non-Interactive Public-Key Encryption (2004)
Ran Canetti, Shai Halevi, Jonathan Katz
Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of...
Hardness Amplification of Weakly Verifiable Puzzles (2004)
Ran Canetti, Shai Halevi, Michael Steiner
Is it harder to solve many puzzles than it is to solve just one? This question has di#erent answers, depending on how you define puzzles. For the case of inverting one-way functions it was shown by...
Ran Canetti, Shai Halevi, Jonathan Katz
Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of...
Chosen-ciphertext security from identity-based encryption (2004)
Dan Boneh, Ran Canetti, Shai Halevi, Jonathan Katz
We propose simple and efficient CCA-secure public-key encryption schemes (i.e., schemes secure against adaptive chosen-ciphertext attacks) based on any identity-based encryption (IBE) scheme. Our...
A Parallelizable Enciphering Mode (2004)
We describe a block-cipher mode of operation, EME, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m ∈ [1..n]. The mode is...
Chosen-ciphertext security from identity-based encryption (2004)
Ran Canetti, Shai Halevi, Jonathan Katz
We show how to construct a CCA-secure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our conversion from an IBE scheme to a CCA-secure scheme is simple,...
Adaptively-Secure, Non-Interactive Public-Key Encryption (2004)
Ran Canetti, Shai Halevi, Jonathan Katz
Abstract. Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of...
A Parallelizable Enciphering Mode (2004)
We describe a block-cipher mode of operation, EME, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m ∈ [1..n]. The mode is...
Chosen-ciphertext security from identity-based encryption (2004)
Dan Boneh, Ran Canetti, Shai Halevi, Jonathan Katz
We propose simple and efficient CCA-secure public-key encryption schemes (i.e., schemes secure against adaptive chosen-ciphertext attacks) based on any identity-based encryption (IBE) scheme. Our...
Chosen-Ciphertext Security from Identity-Based Encryption (2004)
Ran Canetti, Shai Halevi, Jonathan Katz
We propose a simple and e#cient construction of a CCAsecure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our construction requires the underlying IBE...
A forward-secure public-key encryption scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Abstract. Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage...
A forward-secure public-key encryption scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Abstract. Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an e#ort to mitigate the damage...
A Forward-Secure Public-Key Encryption Scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an e#ort to mitigate the damage caused by...
A Tweakable Enciphering Mode (2003)
We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m 2. When the underlying block cipher is...
A Tweakable Enciphering Mode (2003)
We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m 2. When the underlying block cipher is...
A Forward-Secure Public-Key Encryption Scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an e#ort to mitigate the damage caused by...
A Tweakable Enciphering Mode (2003)
We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m ≥ 2. When the underlying block...
Ran Canetti, Oded Goldreich, Shai Halevi
the random-oracle methodology as applied to length-restricted
A forward-secure public-key encryption scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious concern. Forward security allows one to mitigate the damage caused by...
A forward-secure public-key encryption scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Abstract Cryptographic computations are often carried out on insecure devices for which the threatof key exposure represents a serious and realistic concern. In an effort to mitigate the damage
A Tweakable Enciphering Mode (2003)
We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m ≥ 2. When the underlying block...
A forward-secure public-key encryption scheme (2003)
Ran Canetti, Shai Halevi, Jonathan Katz
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by...
A Tweakable Enciphering Mode (2003)
Abstract. We describe a block-cipher mode of operation, CMC, that turns an n-bit block cipher into a tweakable enciphering scheme that acts on strings of mn bits, where m ≥ 2. When the underlying...
Cryptanalysis of stream ciphers with linear masking (2002)
Abstract. We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a “non-linear...
Cryptanalysis of stream ciphers with linear masking (2002)
Abstract. We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a “non-linear...
Scream: a software-efficient stream cipher (2002)
Shai Halevi, Don Coppersmith, Charanjit Jutla
We report on the design of Scream, a new software-efficient stream cipher, which was designed to be a "more secure SEAL". Following SEAL, the design of Scream resembles in many ways a...
Cryptanalysis of stream ciphers with linear masking (2002)
We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. The ciphers to which this method applies consist of two processes: one is a \non-linear...
1.1.1 The Random Oracle Model............................ 3 (2002)
Ran Canetti, Oded Goldreich, Shai Halevi
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle...
Cryptanalysis of stream ciphers with linear masking (2002)
We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a “non-linear process ”...
Scream: A software-efficient stream cipher (2002)
We report on the design of Scream, a new software-efficient stream cipher, which was designed to be a “more secure SEAL”. Following SEAL, the design of Scream resembles in many ways a...
Cryptanalysis of stream ciphers with linear masking (2002)
Abstract We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a...
The modular inversion hidden number problem (2001)
Dan Boneh, Shai Halevi, Nick Howgrave-graham
Abstract. We study a class of problems called Modular Inverse Hidden Number Problems (MIHNPs). The basic problem in this class is the following: Given many pairs � � � � −1 xi, msbk (α +...
An observation regarding Jutla's modes of operation (2001)
Recently, Jutla suggested two new modes of operation for block ciphers. These modes build on traditional CBC and ECB modes, respectively, but add to them masking of the outputs and inputs. Jutla...
An observation regarding Jutla's modes of operation (2001)
Recently, Jutla suggested two new modes of operation for block ciphers. These modes build on traditional CBC and ECB modes, respectively, but add to them masking of the outputs and inputs. Jutla...
The modular inversion hidden number problem (2001)
Dan Boneh, Shai Halevi, Nick Howgrave-graham
Abstract. We study a class of problems called Modular Inverse Hidden Number Problems (MIHNPs). The basic problem in this class is the following: Given many pairs � � � � −1 xi, msbk (α +...
The Random Oracle Methodology, Revisited (2000)
Canetti, Ran, Goldreich, Oded, Halevi, Shai
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle...
A cryptographic solution to a game theoretic problem (2000)
Yevgeniy Dodis, Shai Halevi, Tal Rabin
Abstract. In this work we use cryptography to solve a game-theoretic problem which arises naturally in the area of two party strategic games. The standard game-theoretic solution concept for such...
Computing inverses over a shared secret modulus (2000)
Dario Catalano, Rosario Gennaro, Shai Halevi
Abstract. We discuss the following problem: Given an integer φ shared secretly among n players and a prime number e, how can the players efficiently compute a sharing of e −1 mod φ. The most...
Computing inverses over a shared secret modulus (2000)
Dario Catalano, Rosario Gennaro, Shai Halevi
Abstract. We discuss the following problem: Given an integer shared secretly among n players and a prime number e, how can the players efficiently compute a sharing of e 1 mod . The most interesting...
Clock synchronization with faults and recoveries (2000)
Boaz Barak, Shai Halevi, Amir Herzberg, Dalit Naor
We present a convergence-function based clock synchronization algorithm, which is simple, efficient and fault-tolerant. The algorithm is tolerant of failures and allows recoveries, as long as less...
Exposure-resilient functions and all-or-nothing transforms (2000)
Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai
Abstract. We study the problem of partial key exposure. Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is compromised. We...
Computing Inverses Over a Shared Secret Modulus (2000)
Dario Catalano, Rosario Gennaro, Shai Halevi
We discuss the following problem: Given an integer OE shared secretly among n players and a prime number e, how can the players efficiently compute a sharing of e \Gamma1 mod OE. The most interesting...
Exposure-Resilient Functions and All-Or-Nothing Transforms (2000)
Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai
In this work, we study the problem of partial key exposure. Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is...
Exposure-Resilient Functions and All-Or-Nothing Transforms (2000)
Ran Canetti, Yevgeniy Dodis, Shai Halevi, Eyal Kushilevitz, Amit Sahai
We study the problem of partial key exposure. Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is compromised. We show how...
Exposure-resilient functions and all-or-nothing transforms (2000)
Ran Canetti, Yevgeniy Dodisý, Shai Halevi, Eyal Kushilevitzþ, Amit Sahaiý
In this work, we study the problem of partial key exposure. Standard cryptographic definitions and constructions do not guarantee any security even if a tiny fraction of the secret key is...
Computing inverses over a shared secret modulus (2000)
Dario Catalano, Rosario Gennaro, Shai Halevi
Abstract. We discuss the following problem: Given an integer φ shared secretly among n players and a prime number e, how can the players efficiently compute a sharing of e −1 mod φ. The most...
Secure hash-and-sign signatures without the random oracle (1999)
Rosario Gennaro, Shai Halevi, Tal Rabin
Abstract. We present a new signature scheme which isexistentially unforgeable under chosen message attacks, assuming some variant of the RSA conjecture. This scheme is not based on \signature...
Secure hash-and-sign signatures without the random oracle (1999)
Rosario Gennaro, Shai Halevi, Tal Rabin
Abstract. We present a new signature scheme which is existentially unforgeable under chosen message attacks, assuming some variant of the RSA conjecture. This scheme is not based on “signature...
Secure hash-and-sign signatures without the random oracle (1999)
Rosario Gennaro, Shai Halevi, Tal Rabin
Abstract. We present a new signature scheme which is existentially unforgeable under chosen message attacks, assuming some variant of the RSA conjecture. This scheme is not based on...
Computing from partial solutions (1999)
Shai Halevi, Richard J. Lipton, Erez Petrank
We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an ffl fraction of the bits in a satisfying assignment to a 3-CNF...
Public-Key Cryptography and Password Protocols (1999)
We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses a pair of private and public keys while the client has only a weak...
Secure Hash-and-Sign Signatures without the Random Oracle (1999)
Rosario Gennaro Shai, Shai Halevi, Tal Rabin
. We present a new signature scheme which is existentially unforgeable under chosen message attacks, assuming some variant of the RSA conjecture. This scheme is not based on "signature...
Computing From Partial Solutions (1999)
Anna Al Shai, Shai Halevi, Richard J. Lipton, Erez Petrank
We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an ffl fraction of the bits in a satisfying assignment to a 3-CNF...
MARS - A Candidate Cipher for AES (1998)
Carolynn Burwick, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas, ...
We describe MARS, a shared-key (symmetric) block cipher supporting 128-bit blocks and variable key size. MARS is designed to take advantage of the powerful operations supported in today's...
The Random Oracle Methodology, Revisited (1998)
Ran Canetti, Oded Goldreich, Shai Halevi
We take a formal look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes which result from implementing the random oracle by...
Maintaining Authenticated Communication in the Presence of Break-ins (1998)
Ran Canetti, Shai Halevi, Amir Herzberg
We study the problem of maintaining authenticated communication over untrusted communication channels, in a scenario where the communicating parties may be occasionally and repeatedly broken into for...
Public-Key Cryptography and Password Protocols (1998)
We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses a pair of private and public keys while the client has only a weak...
Theory and practice of secret commitment /--by Shai Halevi. (1997)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.
Theory and practice of secret commitment (1997)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.
Theory and practice of secret commitment (1997)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.
Public-key cryptosystems from lattice reduction problems (1997)
Oded Goldreich, Sha Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997)
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Shai Halevi
Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on...
Public-Key Cryptosystems from Lattice Reduction Problems (1997)
Oded Goldreich Shafi, Public-key Cryptosystems, Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
Public-Key Cryptosystems from Lattice Reduction Problems (1997)
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997)
Ajtai-dwork Cryptosystem, Oded Goldreich, Shafi Goldwasser, Shai Halevi
. Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on...
Public-Key Cryptosystems from Lattice Reduction Problems (1997)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured...
MMH: Software Message Authentication in the Gbit/second Rates (1997)
March, 1997 Abstract We describe a construction of almost universal hash functions suitable for very fast software implementation and applicable to the hashing of variable size data and fast...
MMH: Software Message Authentication in the Gbit/second Rates (1997)
March, 1997 Abstract We describe a construction of almost universal hash functions suitable for very fast software implementation and applicable to the hashing of variable size data and fast...
Potential Function Analysis of Greedy Hot-Potato Routing (1997)
Amir Ben-Dor, Shai Halevi, Assaf Schuster
We study the problem of packet routing in synchronous networks. We put forward a notion of greedy hot-potato routing algorithms and devise techniques for analyzing such algorithms. A greedy...
Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem (1997)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
Following Ajtai's lead, Ajtai and Dwork have recently introduced a public-key encryption scheme which is secure under the assumption that a certain computational problem on lattices is hard on...
How to Maintain Authenticated Communication in the Presence of Break-ins (Extended Abstract) (1996)
Ran Canetti, Shai Halevi, Amir Herzberg
) Ran Canetti Shai Halevi y Amir Herzberg z May 8, 1996 Abstract Cryptography provides authenticated communication over untrusted channels, as long as the secret keys are not exposed. However,...
Collision-Free Hashing from Lattice Problems (1996)
Oded Goldreich Shafi, Oded Goldreich, Shafi Goldwasser, Shai Halevi
Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same...
Efficient Commitment Schemes with Bounded Sender and Unbounded Receiver (1996)
In this paper we address the problem of constructing commitment schemes where the sender is bounded to polynomial time and the receiver may be all powerful. Many known constructions for such...
Collision-Free Hashing from Lattice Problems (1996)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same...
Collision-Free Hashing from Lattice Problems (1996)
Oded Goldreich, Shafi Goldwasser, Shai Halevi
Recently Ajtai described a construction of one-way functions whose security is equivalent to the difficulty of some well known approximation problems in lattices. We show that essentially the same...
Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing (1996)
. We present a very practical string-commitment scheme which is provably secure based solely on collision-free hashing. Our scheme enables a computationally bounded party to commit strings to an...
Storing classified files (1995)
We initiate a study of a natural problem in secure systems, namely- storing classified files on-line. A system of classified files contains a set of files (or documents), a set of users, and an...
Storing Classified Files (1995)
We initiate a study of a natural problem in secure systems, namely - storing classified files on-line. A system of classified files contains a set of files (or documents), a set of users, and an...
Zero-One Permanent is #P-Complete, A Simpler Proof (1995)
In 1979, Valiant proved that computing the permanent of a 01-matrix is #PComplete. In this paper we present another proof for the same result. Our proof uses "black box" methodology, which...
Potential Function Analysis of Greedy Hot-Potato Routing (Extended Abstract) (1994)
Amir Ben-Dor, Shai Halevi, Assaf Schuster
Amir Ben-Dor Shai Halevi y Assaf Schuster z January 21, 1994 Abstract In this work we study the problem of packet routing in synchronous networks of processors, in which at most one packet can...
On the Independence of P versus NP (revised version (1991)
We investigate the possibility that the current failure to resolve basic complexity theoretic questions stems from the independence of these questions with respect to the formal theories underlying...
MARS - a candidate cipher for AES
Carolynn Burwick, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas, ...
We describe MARS, a shared-key (symmetric) block cipher supporting 128-bit blocks and variable key size. MARS is designed to take advantage of the powerful operations supported in today's...
MARS - a candidate cipher for AES
Carolynn Burwick Don, Rosario Gennaro, Shai Halevi, Charanjit Jutla, Stephen M. Matyas, ...
We describe MARS, a shared-key (symmetric) block cipher supporting 128-bit blocks and variable key size. MARS is designed to take advantage of the powerful operations supported in today's...
A Cryptographic Solution to a Game Theoretic Problem
Yevgeniy Dodis, Shai Halevi, Tal Rabin
Although Game Theory and Cryptography seem to have some similar scenarios in common, it is very rare to find instances where tools from one area are applied in the other. In this work we use...