|
Manuscripts
-
Leakage-Resilient Secure Computation
with Elette Boyle, Sanjam Garg, Shafi Goldwasser, Amit Sahai, Yael Tauman Kalai
Publications
-
Broad New Impossibility Results for Secure Concurrent Composition
with Shweta Agrawal, Vipul Goyal, Manoj Prabhakaran, Amit Sahai
CRYPTO 2012 -- Advances in Cryptology
-
Multiparty Computation Secure Against Continual Memory Leakage
with Elette Boyle, Shafi Goldwasser, Yael Tauman Kalai
STOC 2012 -- ACM Symposium on Theory of Computing
-
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE
with Gilad Asharov, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, Daniel Wichs
EUROCRYPT 2012
-- Advances in Cryptology
[.pdf]
(Merge of [AJW] and [LTV])
Fully homomorphic encryption (FHE) provides a simple template for secure computation between two parties (Alice and Bob) where: (I) Alice encrypts her input under her key, (II) Bob homomorphically evaluates the desired function on Alice's ciphertext and his own input, and sends the encrypted output to Alice. Extending this approach to multiple parties raises the problem of which key to encrypt under; if all parties choose a key on their own, then homomorphic evaluation on ciphertexts under different keys will not be possible, and if a single party chooses the key for everyone then corrupting this party will break privacy for all.
In this work, we explore the option of using threshold fully homomorphic encryption (TFHE), allowing many parties to cooperatively generate a common public key whose secret key is shared/distributed among them. Moreover, the parties can cooperatively decrypt a ciphertext without learning anything but the plaintext. We show how to instantiate this approach efficiently using the recent FHE schemes of Brakerski et al. (FOCS '11, ITCS '12) based on the learning with errors (LWE) assumption. Our main tool is to exploit the property that such LWE-based encryption schemes are homomorphic over their keys.
Using TFHE, we construct multiparty computation (MPC) protocols secure against fully malicious settings, tolerating any number of corruptions, and providing security in the universal composability framework. Our schemes have several benefits over prior templates for MPC. Interaction: We get protocols with only 3 rounds of interaction in the common random string model, or 2 rounds with a reusable public-key infrastructure, improving on prior known results. Communication: The communication in our protocol is only proportional to the input and output size of the function being evaluated and independent of its circuit size. Computation: The only computation that depends on the size of the circuit being computed is a homomorphic evaluation over public ciphertexts. This computation can be performed by a single party or can be outsourced to an external server. Novel Approach: Prior approaches to MPC with a dishonest majority rely in part on some combination of the techniques of Yao (FOCS '86) and/or Goldreich, Micali and Wigderson (STOC '87). Our approach is fundamentally different and relies only on the homomorphic properties of LWE-based encryption.
-
Concurrently Secure Computation in Constant Rounds
with Sanjam Garg, Vipul Goyal, Amit Sahai
EUROCRYPT 2012
-- Advances in Cryptology
[.pdf]
We study the problem of constructing concurrently secure computation protocols in the plain model, where no trust is required in any
party or setup. While the well established UC framework for concurrent security is impossible to achieve in this setting, meaningful relaxed notions of concurrent security have been achieved.
The main contribution of our work is a new technique useful for designing protocols in the concurrent setting (in the plain model). The core of our technique is a new rewinding-based extraction procedure which only requires the protocol to have a constant number of rounds. We show two main applications of our technique.
We obtain the first concurrently secure computation protocol in the plain model with super-polynomial simulation (SPS) security that uses only a constant number of rounds and requires only standard assumptions. In contrast, the only previously known result (Canetti et al., FOCS'10) achieving SPS security based on standard assumptions requires polynomial number of rounds. Our second contribution is a new definition of input indistinguishable computation (IIC) and a constant round protocols satisfying that definition. Our definition of input indistinguishable computation is a simplification and strengthening of the definition of Micali et al. (FOCS'06) in various directions. Most notably, our definition provides meaningful security guarantees even for randomized functionalities. Interestingly, we show that in fact the same protocol satisfies both the SPS and the IIC security notions.
-
Hardness Preserving Constructions of Pseudorandom Functions
with Krzysztof Pietrzak, Aris Tentes
TCC 2012
-- Theory of Cryptography Conference
[.pdf]
We show a hardness-preserving construction of a PRF from any length doubling PRG which improves upon known constructions whenever we can put a non-trivial upper bound $q$ on the number of queries to the PRF. Our construction requires only $O(\log q)$ invocations to the underlying PRG with each query. In comparison, the number of invocations by the best previous hardness-preserving construction (GGM using Levin's trick) is logarithmic in the hardness of the PRG.
For example, starting from an exponentially secure PRG that stretches $n$ bits to $2n$ bits, we get a PRF which is exponentially secure if queried at most $q=\exp(\sqrt n)$ times and where each invocation of the PRF requires $\Theta(\sqrt n)$ queries to the underlying PRG. This is much less than the $\Theta(n)$ required by known constructions.
-
Counterexamples to Hardness Amplification Beyond Negligible
with Yevgeniy Dodis, Tal Moran, Daniel Wichs
TCC 2012
-- Theory of Cryptography Conference
[.pdf]
If we have a problem that is mildly hard, can we create a problem that is significantly harder? A natural approach to hardness amplification is the ``direct product''; instead of asking an attacker to solve a single instance of a problem, we ask the attacker to solve several independently generated ones. Interestingly, proving that the direct product amplifies hardness is often highly non-trivial, and in some cases may be false. For example, it is known that the direct product (i.e. ``parallel repetition'') of general interactive games may not amplify hardness at all. On the other hand, positive results show that the direct product does amplify hardness for many basic primitives such as one-way functions/relations, weakly-verifiable puzzles, and signatures.
Even when positive direct product theorems are shown to hold for some primitive, the parameters are surprisingly weaker than what we may have expected. For example, if we start with a weak one-way function that no poly-time attacker can break with probability greater than half, then the direct product provably amplifies hardness to some negligible probability. Naturally, we would expect that we can amplify hardness exponentially, all the way to $2^{-n}$ probability, or at least to some fixed/known negligible such as $n^{-\log n}$ in the security parameter $n$, just by taking sufficiently many instances of the weak primitive. Although it is known that such parameters cannot be proven via black-box reductions, they may seem like reasonable conjectures, and, to the best of our knowledge, are widely believed to hold. In fact, a conjecture along these lines was introduced in a survey of Goldreich, Nisan and Wigderson (ECCC '95). In this work, we show that such conjectures are false by providing simple but surprising counterexamples. In particular, we construct weakly secure signatures and one-way functions, for which standard hardness amplification results are known to hold, but for which hardness does not amplify beyond just negligible. That is, for any negligible function $\eps(n)$, we instantiate these primitives so that the direct product can always be broken with probability $\eps(n)$, no matter how many copies we take.
-
Leakage-Resilient Zero Knowledge
with Sanjam Garg, Amit Sahai
CRYPTO 2011
-- Advances in Cryptology
[.pdf]
We initiate a study of zero knowledge proof systems in the presence of side-channel attacks. Specifically, we consider a setting where a cheating verifier is allowed to obtain arbitrary bounded leakage on the entire state (including the witness and the random coins) of the prover during the entire protocol execution. We formalize a meaningful definition of leakage-resilient zero knowledge (LR-ZK) proof system, that intuitively guarantees that the protocol does not yield anything beyond the validity of the statement and the leakage obtained by the verifier.
We give a construction of LR-ZK interactive proof system based on general assumptions. To the best of our knowledge, this is the first instance of a cryptographic interactive protocol where the adversary is allowed to perform leakage attacks on the entire state of honest party during the protocol execution (in contrast, prior work only considered leakage prior to the protocol execution, or very limited leakage during during the protocol execution). Next, we give an LR-NIZK argument system based on standard assumptions.
Finally, we demonstrate the usefulness of our notions by giving two concrete applications:
-- We show how to do UC secure computation in the "leaky token model" (i.e., where an adversary in possession of a token can obtain arbitrary bounded leakage on the entire state of the token) based on standard assumptions.
-- Next, we give a new construction of fully leakage-resilient signatures in the bounded leakage model (as well as the continual leakage model) based on standard assumptions. In contrast to the recent constructions of fully leakage resilient signatures, our scheme is also secure in the "noisy leakage" model.
-
Efficient Authentication from Hard Learning Problems
with Eike Kiltz, Krzysztof Pietrzak, David Cash, Daniele Venturi
EUROCRYPT 2011
-- Advances in Cryptology (best paper award)
[.pdf]
We construct efficient authentication protocols and message-authentication codes (MACs) whose security can be reduced to the learning parity with noise (LPN) problem.
Despite a large body of work -- starting with the HB protocol of Hopper and Blum in 2001 -- until now it was not even known how to construct an efficient authentication protocol from LPN which is secure against man-in-the-middle (MIM) attacks. A MAC implies such a
(two-round) protocol.
-
Parallel Repetition for Leakage Resilience Amplification, Revisited
with Krzysztof Pietrzak
TCC 2011
-- Theory of Crptography Conference
[.pdf]
If a cryptographic primitive remains secure even if $\ell$ bits about the secret key are leaked to the adversary, one would expect that at least one of $n$ independent instantiations of the scheme remains secure given $n\cdot \ell$ bits of leakage. This intuition has been proven true for schemes satisfying some special information-theoretic properties by Alwen et al. [Eurocrypt'10]. On the negative side, Lewko and Waters [FOCS'10] construct a CPA secure public-key encryption scheme for which this intuition fails.
The counterexample of Lewko and Waters leaves open the interesting possibility that for any scheme there exists a constant $c>0$, such that $n$-fold repetition remains secure against $c\cdot n\cdot \ell$ bits of leakage. Furthermore, their counterexample requires the n copies of the encryption scheme to share a common reference parameter, leaving open the possibility that the intuition is true for all schemes without common setup.
In this work we give a stronger counterexample ruling out these possibilities. We construct a signature scheme such that:
-- a single instantiation remains secure given $\ell=\log(k)$ bits of leakage where $k$ is a security parameter.
-- any polynomial number of independent instantiations can be broken (in the strongest sense of key-recovery) given $\ell'=\mathrm{poly}(k)$ bits of leakage. Note that $\ell'$ does not depend on the number of instances.
The computational assumption underlying our counterexample is that non-interactive computationally sound proofs exist. Moreover, under a stronger (non-standard) assumption about such proofs, our counterexample does not require a common reference parameter. The underlying idea of our counterexample is rather generic and can be applied to other primitives like encryption schemes.
-
Bringing People of Different Beliefs Together to do UC
with Sanjam Garg, Vipul Goyal, Amit Sahai
TCC 2011
-- Theory of Crptography Conference
[.pdf]
Known constructions of UC secure protocols are based on the premise that different parties collectively agree on some trusted setup. In this paper, we consider the following two intriguing questions: Is it possible to achieve UC if the parties do not want to put all their trust in one entity (or more generally, in one setup)? What if the parties have a difference of opinion about what they are willing to trust? The first question has been studied in only a limited way, while the second has never been considered before.
In this paper, we initiate a systematic study to answer the above questions. We consider a scenario with multiple setup instances where each party in the system has some individual belief (setup assumption in terms of the given setups). The belief of a party corresponds to what it is willing to trust and its security is guaranteed given that its belief "holds." The question considered is: "Given some setups and the (possibly) different beliefs of all the parties, when can UC security be achieved?" We present a general condition on the setups and the beliefs of all the parties under which UC security is possible. Surprisingly, we show that when parties have different beliefs, UC security can be achieved with a more limited "trust" than what is necessary in the traditional setting (where all parties have a common belief).
-
Password-Authenticated Session-Key Generation on the Internet in the Plain Model
with Vipul Goyal, Rafail Ostrovsky
CRYPTO 2010
-- Advances in Cryptology
[.pdf]
The problem of password-authenticated key exchange (PAKE) has been extensively studied for the last two decades. Despite extensive studies, no construction was known for a PAKE protocol that is secure in the plain model in the setting of concurrent self-composition, where polynomially many protocol sessions with the same password may be executed on the distributed network (such as the Internet) in an arbitrarily interleaved manner, and where the adversary may corrupt any number of participating parties.
In this paper, we resolve this long-standing open problem. In particular, we give the first construction of a PAKE protocol that is secure (with respect to the standard definition of Goldreich and Lindell) in the fully concurrent setting and without requiring any trusted setup assumptions. We stress that we allow polynomially-many concurrent sessions, where polynomial is not fixed in advance and can be determined by an adversary an an adaptive manner. Interestingly, our proof, among other things, requires important ideas from Precise Zero Knowledge theory recently developed by Micali and Pass in their STOC'06 paper.
-
On the Round Complexity of Covert Computation
with Vipul Goyal
STOC 2010
-- ACM Symposium on Theory of Computing
[.pdf]
In STOC'05, Ahn, Hopper and Langford introduced the notion of covert computation. In covert computation, a party runs a secure computation protocol over a covert (or steganographic) channel without knowing if the other parties are participating as well or not. At the end of the protocol, if all parties participated in the protocol and if the function output is "favorable" to all parties, then the output is revealed (along with the fact that everyone participated). All covert computation protocols known so far require a large polynomial number of rounds. In this work, we first study the question of the round complexity of covert computation and obtain the following results:
-- There does not exist a constant round covert computation protocol with respect to black box simulation even for the case of two parties. (In comparison, such protocols are known even for the multi-party case if there is no covertness requirement.)
-- By relying on the two slot non-black-box simulation technique of Pass (STOC'04) and techniques from cryptography in NC0 (FOCS'04), we obtain a construction of a constant round covert multi-party computation protocol.
Put together, the above adds one more example to the growing list of tasks for which non-black-box simulation techniques (introduced in the work of Barak in FOCS'01) are necessary.
Finally, we study the problem of covert multi-party computation in the setting where the parties only have point to point (covert) communication channels. We observe that our covert computation protocol for the broadcast channel inherits, from the protocol of Pass, the property of secure composition in the bounded concurrent setting. Then, as an application of this protocol, somewhat surprisingly we show the existence of covert multi-party computation with point to point channels (assuming that the number of parties is a constant).
- Bounded Ciphertext Policy Attribute Based Encryption
with Vipul Goyal, Omkant Pandey, Amit Sahai
ICALP 2008
-- International Colloquium on Automata, Languages and Programming
[.pdf]
In a ciphertext policy attribute based encryption system, a user's private key is associated with a set of attributes (describing the user) and an encrypted ciphertext will specify an access policy over attributes. A user will be able to decrypt if and only if his attributes satisfy the ciphertext's policy. In this work, we present the first construction of a ciphertext-policy attribute based encryption scheme having a security proof based on a number theoretic assumption and supporting advanced access structures. Previous CP-ABE systems could either support only very limited access structures or had a proof of security only in the generic group model. Our construction can support access structures which can be represented by a bounded size access tree with threshold gates as its nodes. The bound on the size of the access trees is chosen at the time of the system setup. Our security proof is based on the standard Decisional Bilinear Diffie-Hellman assumption.
- Packet Dropping Adversary Identification for Data Plane Security
with Xin Zhang, Adrian Perrig
CoNEXT 2008
-- ACM International Conference on emerging Networking EXperiments and Technologies
Nearly two decades ago, Perlman first studied packet dropping attacks on routing paths in the context of data-plane security. However, until recently, the design of packet dropping adversary identification protocols that are simultaneously robust to both benign packet loss and malicious behavior has proven to be surprisingly elusive. In this paper, we strive to propose a secure and practical packet-dropping adversary localization scheme that is robust (in the sense as described earlier) and simultaneously achieves high detection rate and low communication and storage overhead -- the three key performance metrics for such protocols in realistic settings. Recent work optimizes either the detection rate or the communication overhead only. We systematically explore the design space of acknowledgment based protocols to identify a packet dropping adversary on a forwarding path from a source to a destination. In particular, we investigate a set of primitive protocols where each protocol exemplifies a design dimension; and examine the underlying tradeoff between the performance metrics. For each primitive protocol, we present both upper/lower performance bounds via theoretical analysis and average-case results via simulations. We conclude that the proposed PAI-1 protocol outperforms other related schemes in terms of practicality in a realistic network setting.
|
