@inbook {19629,
	title = {Adaptive and Concurrent Secure Computation from New Adaptive, Non-malleable Commitments},
	booktitle = {Advances in Cryptology - ASIACRYPT 2013},
	series = {Lecture Notes in Computer Science},
	year = {2013},
	month = {2013/01/01/},
	pages = {316 - 336},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present a unified approach for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Using our approach we essentially obtain all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions in known models. Additionally, we provide the first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and the non-uniform simulation model. As a corollary we also obtain the first adaptively secure multiparty computation protocol in the plain model that is secure under bounded-concurrency. Conceptually, our approach can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC {\textquoteleft}09], who considered only non-adaptive adversaries. Their main insight was that the non-malleability requirement could be decoupled from the simulation requirement to achieve UC-security. A main conceptual contribution of this work is, quite surprisingly, that it is still the case even when considering adaptive security. A key element in our construction is a commitment scheme that satisfies a strong definition of non-malleability. Our new primitive of concurrent equivocal non-malleable commitments, intuitively, guarantees that even when a man-in-the-middle adversary observes concurrent equivocal commitments and decommitments, the binding property of the commitments continues to hold for commitments made by the adversary. This definition is stronger than previous ones, and may be of independent interest. Previous constructions that satisfy our definition have been constructed in setup models, but either require existence of stronger encryption schemes such as CCA-secure encryption or require independent {\textquotedblleft}trapdoors{\textquotedblright} provided by the setup for every pair of parties to ensure non-malleability. A main technical contribution of this work is to provide a construction that eliminates these requirements and requires only a single trapdoor.},
	keywords = {Algorithm Analysis and Problem Complexity, Applications of Mathematics, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, Systems and Data Security},
	isbn = {978-3-642-42032-0, 978-3-642-42033-7},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-42033-7_17},
	author = {Dana Dachman-Soled and Malkin, Tal and Raykova, Mariana and Venkitasubramaniam, Muthuramakrishnan},
	editor = {Sako, Kazue and Sarkar, Palash}
}
@inbook {19641,
	title = {On the Centrality of Off-Line E-Cash to Concrete Partial Information Games},
	booktitle = {Security and Cryptography for Networks},
	series = {Lecture Notes in Computer Science},
	year = {2012},
	month = {2012/01/01/},
	pages = {264 - 280},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Cryptography has developed numerous protocols for solving {\textquotedblleft}partial information games{\textquotedblright} that are seemingly paradoxical. Some protocols are generic (e.g., secure multi-party computation) and others, due to the importance of the scenario they represent, are designed to solve a concrete problem directly. Designing efficient and secure protocols for (off-line) e-cash, e-voting, and e-auction are some of the most heavily researched concrete problems, representing various settings where privacy and correctness of the procedure is highly important. In this work, we initiate the exploration of the relationships among e-cash, e-voting and e-auction in the universal composability (UC) framework, by considering general variants of the three problems. In particular, we first define ideal functionalities for e-cash, e-voting, and e-auction, and then give a construction of a protocol that UC-realizes the e-voting (resp., e-auction) functionality in the e-cash hybrid model. This (black-box) reducibility demonstrates the centrality of off-line e-cash and implies that designing a solution to e-cash may bear fruits in other areas. Constructing a solution to one protocol problem based on a second protocol problem has been traditional in cryptography, but typically has concentrated on building complex protocols on simple primitives (e.g., secure multi-party computation from Oblivious Transfer, signature from one-way functions, etc.). The novelty here is reducibility among mature protocols and using the ideal functionality as a design tool in realizing other ideal functionalities. We suggest this new approach, and we only consider the very basic general properties from the various primitives to demonstrate its viability. Namely, we only consider the basic coin e-cash model, the e-voting that is correct and private and relies on trusted registration, and e-auction relying on a trusted auctioneer. Naturally, relationships among protocols with further properties (i.e., extended functionalities), using the approach advocated herein, are left as open questions.},
	keywords = {Computer Appl. in Administrative Data Processing, Computer Communication Networks, Data Encryption, Management of Computing and Information Systems, Systems and Data Security},
	isbn = {978-3-642-32927-2, 978-3-642-32928-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-32928-9_15},
	author = {Choi, Seung Geol and Dana Dachman-Soled and Yung, Moti},
	editor = {Visconti, Ivan and Prisco, Roberto De}
}
@inbook {19634,
	title = {Efficient Password Authenticated Key Exchange via Oblivious Transfer},
	booktitle = {Public Key Cryptography {\textendash} PKC 2012},
	series = {Lecture Notes in Computer Science},
	year = {2012},
	month = {2012/01/01/},
	pages = {449 - 466},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present a new framework for constructing efficient password authenticated key exchange (PAKE) protocols based on oblivious transfer (OT). Using this framework, we obtain: an efficient and simple UC-secure PAKE protocol that is secure against adaptive corruptions without erasures. efficient and simple PAKE protocols under the Computational Diffie-Hellman (CDH) assumption and the hardness of factoring. (Previous efficient constructions rely on hash proof systems, which appears to be inherently limited to decisional assumptions.) All of our constructions assume a common reference string (CRS) but do not rely on random oracles.},
	keywords = {adaptive security, Algorithm Analysis and Problem Complexity, Computer Communication Networks, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, oblivious transfer, Password Authenticated Key Exchange, search assumptions, Systems and Data Security, UC security},
	isbn = {978-3-642-30056-1, 978-3-642-30057-8},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-30057-8_27},
	author = {Canetti, Ran and Dana Dachman-Soled and Vaikuntanathan, Vinod and Wee, Hoeteck},
	editor = {Fischlin, Marc and Buchmann, Johannes and Manulis, Mark}
}
@inbook {19644,
	title = {Securing Circuits against Constant-Rate Tampering},
	booktitle = {Advances in Cryptology {\textendash} CRYPTO 2012},
	series = {Lecture Notes in Computer Science},
	year = {2012},
	month = {2012/01/01/},
	pages = {533 - 551},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present a compiler that converts any circuit into one that remains secure even if a constant fraction of its wires are tampered with. Following the seminal work of Ishai et. al. (Eurocrypt 2006), we consider adversaries who may choose an arbitrary set of wires to corrupt, and may set each such wire to 0 or to 1, or may toggle with the wire. We prove that such adversaries, who continuously tamper with the circuit, can learn at most logarithmically many bits of secret information (in addition to black-box access to the circuit). Our results are information theoretic.},
	keywords = {circuit compiler, Computer Communication Networks, computers and society, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, PCP of proximity, side-channel attacks, Systems and Data Security, tampering},
	isbn = {978-3-642-32008-8, 978-3-642-32009-5},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-32009-5_31},
	author = {Dana Dachman-Soled and Kalai, Yael Tauman},
	editor = {Safavi-Naini, Reihaneh and Canetti, Ran}
}
@inbook {19600,
	title = {Optimal Verification of Operations on Dynamic Sets},
	booktitle = {Advances in Cryptology {\textendash} CRYPTO 2011},
	series = {Lecture Notes in Computer Science},
	year = {2011},
	month = {2011/01/01/},
	pages = {91 - 110},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We study the design of protocols for set-operation verification, namely the problem of cryptographically checking the correctness of outsourced set operations performed by an untrusted server over a dynamic collection of sets that are owned (and updated) by a trusted source. We present new authenticated data structures that allow any entity to publicly verify a proof attesting the correctness of primitive set operations such as intersection, union, subset and set difference. Based on a novel extension of the security properties of bilinear-map accumulators as well as on a primitive called accumulation tree, our protocols achieve optimal verification and proof complexity (i.e., only proportional to the size of the query parameters and the answer), as well as optimal update complexity (i.e., constant), while incurring no extra asymptotic space overhead. The proof construction is also efficient, adding a logarithmic overhead to the computation of the answer of a set-operation query. In contrast, existing schemes entail high communication and verification costs or high storage costs. Applications of interest include efficient verification of keyword search and database queries. The security of our protocols is based on the bilinear q-strong Diffie-Hellman assumption.},
	keywords = {Computer Communication Networks, computers and society, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, Systems and Data Security},
	isbn = {978-3-642-22791-2, 978-3-642-22792-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-22792-9_6},
	author = {Charalampos Papamanthou and Tamassia, Roberto and Triandopoulos, Nikos},
	editor = {Rogaway, Phillip}
}
@inbook {19643,
	title = {Secure Efficient Multiparty Computing of Multivariate Polynomials and Applications},
	booktitle = {Applied Cryptography and Network Security},
	series = {Lecture Notes in Computer Science},
	year = {2011},
	month = {2011/01/01/},
	pages = {130 - 146},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present a robust secure methodology for computing functions that are represented as multivariate polynomials where parties hold different variables as private inputs. Our generic efficient protocols are fully black-box and employ threshold additive homomorphic encryption; they do not assume honest majority, yet are robust in detecting any misbehavior. We achieve solutions that take advantage of the algebraic structure of the polynomials, and are polynomial-time in all parameters (security parameter, polynomial size, polynomial degree, number of parties). We further exploit a {\textquotedblleft}round table{\textquotedblright} communication paradigm to reduce the complexity in the number of parties. A large collection of problems are naturally and efficiently represented as multivariate polynomials over a field or a ring: problems from linear algebra, statistics, logic, as well as operations on sets represented as polynomials. In particular, we present a new efficient solution to the multi-party set intersection problem, and a solution to a multi-party variant of the polynomial reconstruction problem.},
	keywords = {additive homomorphic encryption, Algorithm Analysis and Problem Complexity, Computer Communication Networks, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, multiparty set intersection, multivariate polynomial evaluation, secret sharing, secure multiparty computation, Systems and Data Security, threshold cryptosystems},
	isbn = {978-3-642-21553-7, 978-3-642-21554-4},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-21554-4_8},
	author = {Dana Dachman-Soled and Malkin, Tal and Raykova, Mariana and Yung, Moti},
	editor = {Lopez, Javier and Tsudik, Gene}
}
@inbook {19645,
	title = {Simple, Black-Box Constructions of Adaptively Secure Protocols},
	booktitle = {Theory of Cryptography},
	series = {Lecture Notes in Computer Science},
	year = {2009},
	month = {2009/01/01/},
	pages = {387 - 402},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present a compiler for transforming an oblivious transfer (OT) protocol secure against an adaptive semi-honest adversary into one that is secure against an adaptive malicious adversary. Our compiler achieves security in the universal composability framework, assuming access to an ideal commitment functionality, and improves over previous work achieving the same security guarantee in two ways: it uses black-box access to the underlying protocol and achieves a constant multiplicative overhead in the round complexity. As a corollary, we obtain the first constructions of adaptively secure protocols in the stand-alone model using black-box access to a low-level primitive.},
	keywords = {Algorithm Analysis and Problem Complexity, computers and society, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, Systems and Data Security},
	isbn = {978-3-642-00456-8, 978-3-642-00457-5},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-00457-5_23},
	author = {Choi, Seung Geol and Dana Dachman-Soled and Malkin, Tal and Wee, Hoeteck},
	editor = {Reingold, Omer}
}
@inbook {19630,
	title = {Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One},
	booktitle = {Theory of Cryptography},
	series = {Lecture Notes in Computer Science},
	year = {2008},
	month = {2008/01/01/},
	pages = {427 - 444},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We show how to transform any semantically secure encryption scheme into a non-malleable one, with a black-box construction that achieves a quasi-linear blow-up in the size of the ciphertext. This improves upon the previous non-black-box construction of Pass, Shelat and Vaikuntanathan (Crypto {\textquoteright}06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt {\textquoteright}07). Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions; instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. We exploit the fact that low-degree polynomials are simultaneously good error-correcting codes and a secret-sharing scheme.},
	keywords = {Algorithm Analysis and Problem Complexity, black-box constructions, computers and society, Data Encryption, Discrete Mathematics in Computer Science, Management of Computing and Information Systems, non-malleability, public-key encryption, semantic security, Systems and Data Security},
	isbn = {978-3-540-78523-1, 978-3-540-78524-8},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-78524-8_24},
	author = {Choi, Seung Geol and Dana Dachman-Soled and Malkin, Tal and Wee, Hoeteck},
	editor = {Canetti, Ran}
}
@inbook {19622,
	title = {Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures},
	booktitle = {Information and Communications Security},
	series = {Lecture Notes in Computer Science},
	year = {2007},
	month = {2007/01/01/},
	pages = {1 - 15},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Authentication is increasingly relevant to data management. Data is being outsourced to untrusted servers and clients want to securely update and query their data. For example, in database outsourcing, a client{\textquoteright}s database is stored and maintained by an untrusted server. Also, in simple storage systems, clients can store very large amounts of data but at the same time, they want to assure their integrity when they retrieve them. In this paper, we present a model and protocol for two-party authentication of data structures. Namely, a client outsources its data structure and verifies that the answers to the queries have not been tampered with. We provide efficient algorithms to securely outsource a skip list with logarithmic time overhead at the server and client and logarithmic communication cost, thus providing an efficient authentication primitive for outsourced data, both structured (e.g., relational databases) and semi-structured (e.g., XML documents). In our technique, the client stores only a constant amount of space, which is optimal. Our two-party authentication framework can be deployed on top of existing storage applications, thus providing an efficient authentication service. Finally, we present experimental results that demonstrate the practical efficiency and scalability of our scheme.},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Communication Networks, computers and society, Data Encryption, Management of Computing and Information Systems, Systems and Data Security},
	isbn = {978-3-540-77047-3, 978-3-540-77048-0},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-77048-0_1},
	author = {Charalampos Papamanthou and Tamassia, Roberto},
	editor = {Qing, Sihan and Imai, Hideki and Wang, Guilin}
}
