@inbook {19631,
	title = {Can Optimally-Fair Coin Tossing Be Based on One-Way Functions?},
	booktitle = {Theory of Cryptography},
	series = {Lecture Notes in Computer Science},
	year = {2014},
	month = {2014/01/01/},
	pages = {217 - 239},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Coin tossing is a basic cryptographic task that allows two distrustful parties to obtain an unbiased random bit in a way that neither party can bias the output by deviating from the protocol or halting the execution. Cleve [STOC{\textquoteright}86] showed that in any r round coin tossing protocol one of the parties can bias the output by Ω(1/r) through a {\textquotedblleft}fail-stop{\textquotedblright} attack; namely, they simply execute the protocol honestly and halt at some chosen point. In addition, relying on an earlier work of Blum [COMPCON{\textquoteright}82], Cleve presented an r-round protocol based on one-way functions that was resilient to bias at most O(1/r√)O(1/\sqrt r) . Cleve{\textquoteright}s work left open whether {\textquotedblright}{\textquoteleft}optimally-fair{\textquoteright}{\textquotedblright} coin tossing (i.e. achieving bias O(1/r) in r rounds) is possible. Recently Moran, Naor, and Segev [TCC{\textquoteright}09] showed how to construct optimally-fair coin tossing based on oblivious transfer, however, it was left open to find the minimal assumptions necessary for optimally-fair coin tossing. The work of Dachman-Soled et al. [TCC{\textquoteright}11] took a step toward answering this question by showing that any black-box construction of optimally-fair coin tossing based on a one-way functions with n-bit input and output needs Ω(n/logn) rounds. In this work we take another step towards understanding the complexity of optimally-fair coin-tossing by showing that this task (with an arbitrary number of rounds) cannot be based on one-way functions in a black-box way, as long as the protocol is {\textquotedblright}{\textquoteleft}oblivious{\textquoteright}{\textquotedblright} to the implementation of the one-way function. Namely, we consider a natural class of black-box constructions based on one-way functions, called function oblivious, in which the output of the protocol does not depend on the specific implementation of the one-way function and only depends on the randomness of the parties. Other than being a natural notion on its own, the known coin tossing protocols of Blum and Cleve (both based on one-way functions) are indeed function oblivious. Thus, we believe our lower bound for function-oblivious constructions is a meaningful step towards resolving the fundamental open question of the complexity of optimally-fair coin tossing.},
	keywords = {Algorithm Analysis and Problem Complexity, black-box separations, Coin-Tossing, Computation by Abstract Devices, Data Encryption, Discrete Mathematics in Computer Science, One-Way Functions, Systems and Data Security},
	isbn = {978-3-642-54241-1, 978-3-642-54242-8},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-54242-8_10},
	author = {Dana Dachman-Soled and Mahmoody, Mohammad and Malkin, Tal},
	editor = {Lindell, Yehuda}
}
@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 {19613,
	title = {Streaming Authenticated Data Structures},
	booktitle = {Advances in Cryptology {\textendash} EUROCRYPT 2013},
	series = {Lecture Notes in Computer Science},
	year = {2013},
	month = {2013/01/01/},
	pages = {353 - 370},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We consider the problem of streaming verifiable computation, where both a verifier and a prover observe a stream of n elements x 1,x 2,{\textellipsis},x n and the verifier can later delegate some computation over the stream to the prover. The prover must return the output of the computation, along with a cryptographic proof to be used for verifying the correctness of the output. Due to the nature of the streaming setting, the verifier can only keep small local state (e.g., logarithmic) which must be updatable in a streaming manner and with no interaction with the prover. Such constraints make the problem particularly challenging and rule out applying existing verifiable computation schemes. We propose streaming authenticated data structures, a model that enables efficient verification of data structure queries on a stream. Compared to previous work, we achieve an exponential improvement in the prover{\textquoteright}s running time: While previous solutions have linear prover complexity (in the size of the stream), even for queries executing in sublinear time (e.g., set membership), we propose a scheme with O(logM logn)O(\log M\ log n) prover complexity, where n is the size of the stream and M is the size of the universe of elements. Our schemes support a series of expressive queries, such as (non-)membership, successor, range search and frequency queries, over an ordered universe and even in higher dimensions. The central idea of our construction is a new authentication tree, called generalized hash tree. We instantiate our generalized hash tree with a hash function based on lattices assumptions, showing that it enjoys suitable algebraic properties that traditional Merkle trees lack. We exploit such properties to achieve our results.},
	keywords = {Algorithm Analysis and Problem Complexity, Data Encryption, Discrete Mathematics in Computer Science, Systems and Data Security},
	isbn = {978-3-642-38347-2, 978-3-642-38348-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-38348-9_22},
	author = {Charalampos Papamanthou and Shi, Elaine and Tamassia, Roberto and Yi, Ke},
	editor = {Johansson, Thomas and Nguyen, Phong Q.}
}
@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 {19628,
	title = {A Canonical Form for Testing Boolean Function Properties},
	booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
	series = {Lecture Notes in Computer Science},
	year = {2011},
	month = {2011/01/01/},
	pages = {460 - 471},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {In a well-known result Goldreich and Trevisan (2003) showed that every testable graph property has a {\textquotedblleft}canonical{\textquotedblright} tester in which a set of vertices is selected at random and the edges queried are the complete graph over the selected vertices. We define a similar-in-spirit canonical form for Boolean function testing algorithms, and show that under some mild conditions property testers for Boolean functions can be transformed into this canonical form. Our first main result shows, roughly speaking, that every {\textquotedblleft}nice{\textquotedblright} family of Boolean functions that has low noise sensitivity and is testable by an {\textquotedblleft}independent tester,{\textquotedblright} has a canonical testing algorithm. Our second main result is similar but holds instead for families of Boolean functions that are closed under ID-negative minors. Taken together, these two results cover almost all of the constant-query Boolean function testing algorithms that we know of in the literature, and show that all of these testing algorithms can be automatically converted into a canonical form.},
	keywords = {Algorithm Analysis and Problem Complexity, Boolean functions, Computation by Abstract Devices, Computer Communication Networks, Computer Graphics, Data structures, Discrete Mathematics in Computer Science, property testing},
	isbn = {978-3-642-22934-3, 978-3-642-22935-0},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-22935-0_39},
	author = {Dana Dachman-Soled and Servedio, Rocco A.},
	editor = {Goldberg, Leslie Ann and Jansen, Klaus and Ravi, R. and Rolim, Jos{\'e} D. P.}
}
@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 {19604,
	title = {Optimal Authenticated Data Structures with Multilinear Forms},
	booktitle = {Pairing-Based Cryptography - Pairing 2010},
	series = {Lecture Notes in Computer Science},
	year = {2010},
	month = {2010/01/01/},
	pages = {246 - 264},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Cloud computing and cloud storage are becoming increasingly prevalent. In this paradigm, clients outsource their data and computations to third-party service providers. Data integrity in the cloud therefore becomes an important factor for the functionality of these web services.Authenticated data structures, implemented with various cryptographic primitives, have been widely studied as a means of providing efficient solutions to data integrity problems (e.g., Merkle trees). In this paper, we introduce a new authenticated dictionary data structure that employs multilinear forms, a cryptographic primitive proposed by Silverberg and Boneh in 2003 [10], the construction of which, however, remains an open problem to date. Our authenticated dictionary is optimal, that is, it does not add any extra asymptotic cost to the plain dictionary data structure, yielding proofs of constant size, i.e., asymptotically equal to the size of the answer, while maintaining other relevant complexities logarithmic. Instead, solutions based on cryptographic hashing (e.g., Merkle trees) require proofs of logarithmic size [40]. Because multilinear forms are not known to exist yet, our result can be viewed from a different angle: if one could prove that optimal authenticated dictionaries cannot exist in the computational model, irrespectively of cryptographic primitives, then our solution would imply that cryptographically interesting multilinear form generators cannot exist as well (i.e., it can be viewed as a reduction). Thus, we provide an alternative avenue towards proving the nonexistence of multilinear form generators in the context of general lower bounds for authenticated data structures [40] and for memory checking [18], a model similar to the authenticated data structures model.},
	keywords = {Algorithm Analysis and Problem Complexity, authenticated dictionary, Coding and Information Theory, Computer Communication Networks, Data Encryption, Discrete Mathematics in Computer Science, multilinear forms, Systems and Data Security},
	isbn = {978-3-642-17454-4, 978-3-642-17455-1},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-17455-1_16},
	author = {Charalampos Papamanthou and Tamassia, Roberto and Triandopoulos, Nikos},
	editor = {Joye, Marc and Miyaji, Atsuko and Otsuka, Akira}
}
@inbook {19605,
	title = {Graph Drawing for Security Visualization},
	booktitle = {Graph Drawing},
	series = {Lecture Notes in Computer Science},
	year = {2009},
	month = {2009/01/01/},
	pages = {2 - 13},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {With the number of devices connected to the internet growing rapidly and software systems being increasingly deployed on the web, security and privacy have become crucial properties for networks and applications. Due the complexity and subtlety of cryptographic methods and protocols, software architects and developers often fail to incorporate security principles in their designs and implementations. Also, most users have minimal understanding of security threats. While several tools for developers, system administrators and security analysts are available, these tools typically provide information in the form of textual logs or tables, which are cumbersome to analyze. Thus, in recent years, the field of security visualization has emerged to provide novel ways to display security-related information so that it is easier to understand. In this work, we give a preliminary survey of approaches to the visualization of computer security concepts that use graph drawing techniques.},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Graphics, Data structures, Discrete Mathematics in Computer Science},
	isbn = {978-3-642-00218-2, 978-3-642-00219-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-00219-9_2},
	author = {Tamassia, Roberto and Palazzi, Bernardo and Charalampos Papamanthou},
	editor = {Tollis, Ioannis G. and Patrignani, Maurizio}
}
@inbook {19638,
	title = {Improved Non-committing Encryption with Applications to Adaptively Secure Protocols},
	booktitle = {Advances in Cryptology {\textendash} ASIACRYPT 2009},
	series = {Lecture Notes in Computer Science},
	year = {2009},
	month = {2009/01/01/},
	pages = {287 - 302},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present a new construction of non-committing encryption schemes. Unlike the previous constructions of Canetti et al. (STOC {\textquoteright}96) and of Damg{\r a}rd and Nielsen (Crypto {\textquoteright}00), our construction achieves all of the following properties: Optimal round complexity. Our encryption scheme is a 2-round protocol, matching the round complexity of Canetti et al. and improving upon that in Damg{\r a}rd and Nielsen. Weaker assumptions. Our construction is based on trapdoor simulatable cryptosystems, a new primitive that we introduce as a relaxation of those used in previous works. We also show how to realize this primitive based on hardness of factoring. Improved efficiency. The amortized complexity of encrypting a single bit is O(1) public key operations on a constant-sized plaintext in the underlying cryptosystem. As a result, we obtain the first non-committing public-key encryption schemes under hardness of factoring and worst-case lattice assumptions; previously, such schemes were only known under the CDH and RSA assumptions. Combined with existing work on secure multi-party computation, we obtain protocols for multi-party computation secure against a malicious adversary that may adaptively corrupt an arbitrary number of parties under weaker assumptions than were previously known. Specifically, we obtain the first adaptively secure multi-party protocols based on hardness of factoring in both the stand-alone setting and the UC setting with a common reference string.},
	keywords = {adaptive corruption, Algorithm Analysis and Problem Complexity, Applications of Mathematics, Data Encryption, Data Structures, Cryptology and Information Theory, Discrete Mathematics in Computer Science, non-committing encryption, public-key encryption, secure multi-party computation, Systems and Data Security},
	isbn = {978-3-642-10365-0, 978-3-642-10366-7},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-10366-7_17},
	author = {Choi, Seung Geol and Dana Dachman-Soled and Malkin, Tal and Wee, Hoeteck},
	editor = {Matsui, Mitsuru}
}
@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 {19602,
	title = {Algorithms for Location Estimation Based on RSSI Sampling},
	booktitle = {Algorithmic Aspects of Wireless Sensor Networks},
	series = {Lecture Notes in Computer Science},
	year = {2008},
	month = {2008/01/01/},
	pages = {72 - 86},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {In this paper, we re-examine the RSSI measurement model for location estimation and provide the first detailed formulation of the probability distribution of the position of a sensor node. We also show how to use this probabilistic model to efficiently compute a good estimation of the position of the sensor node by sampling multiple readings from the beacons (where we do not merely use the mean of the samples) and then minimizing a function with an acceptable computational effort. The results of the simulation of our method in TOSSIM indicate that the location of the sensor node can be computed in a small amount of time and that the quality of the solution is competitive with previous approaches.},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Communication Networks, Data structures, Discrete Mathematics in Computer Science, Information Systems and Communication Service},
	isbn = {978-3-540-92861-4, 978-3-540-92862-1},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-92862-1_7},
	author = {Charalampos Papamanthou and Preparata, Franco P. and Tamassia, Roberto},
	editor = {Fekete, S{\'a}ndor P.}
}
@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 {19642,
	title = {Optimal Cryptographic Hardness of Learning Monotone Functions},
	booktitle = {Automata, Languages and Programming},
	series = {Lecture Notes in Computer Science},
	year = {2008},
	month = {2008/01/01/},
	pages = {36 - 47},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time algorithms have thus far been obtained almost exclusively for various classes of monotone functions, while the computational hardness results obtained to date have all been for various classes of general (nonmonotone) functions. Motivated by this disparity between known positive results (for monotone functions) and negative results (for nonmonotone functions), we establish strong computational limitations on the efficient learnability of various classes of monotone functions. We give several such hardness results which are provably almost optimal since they nearly match known positive results. Some of our results show cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/n--√1/2 + 1/\sqrt{n} ; this accuracy bound is close to optimal by known positive results (Blum et al., FOCS {\textquoteright}98). Other results show that under a plausible cryptographic hardness assumption, a class of constant-depth, sub-polynomial-size circuits computing monotone functions is hard to learn; this result is close to optimal in terms of the circuit size parameter by known positive results as well (Servedio, Information and Computation {\textquoteright}04). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O{\textquoteright}Donnell (JCSS {\textquoteright}04).},
	keywords = {Data structures, Data Structures, Cryptology and Information Theory, Discrete Mathematics in Computer Science, Numeric Computing, Software Engineering/Programming and Operating Systems, Theory of computation},
	isbn = {978-3-540-70574-1, 978-3-540-70575-8},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-70575-8_4},
	author = {Dana Dachman-Soled and Lee, Homin K. and Malkin, Tal and Servedio, Rocco A. and Wan, Andrew and Wee, Hoeteck},
	editor = {Aceto, Luca and Damg{\r a}rd, Ivan and Goldberg, Leslie Ann and Halld{\'o}rsson, Magn{\'u}s M. and Ing{\'o}lfsd{\'o}ttir, Anna and Walukiewicz, Igor}
}
@inbook {19606,
	title = {On the Cost of Persistence and Authentication in Skip Lists},
	booktitle = {Experimental Algorithms},
	series = {Lecture Notes in Computer Science},
	year = {2007},
	month = {2007/01/01/},
	pages = {94 - 107},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We present an extensive experimental study of authenticated data structures for dictionaries and maps implemented with skip lists. We consider realizations of these data structures that allow us to study the performance overhead of authentication and persistence. We explore various design decisions and analyze the impact of garbage collection and virtual memory paging, as well. Our empirical study confirms the efficiency of authenticated skip lists and offers guidelines for incorporating them in various applications.},
	keywords = {Algorithm Analysis and Problem Complexity, algorithms, Computer Graphics, Data structures, Discrete Mathematics in Computer Science, Numeric Computing},
	isbn = {978-3-540-72844-3, 978-3-540-72845-0},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-72845-0_8},
	author = {Goodrich, Michael T. and Charalampos Papamanthou and Tamassia, Roberto},
	editor = {Demetrescu, Camil}
}
@inbook {19567,
	title = {Distribution-Free Testing Lower Bounds for Basic Boolean Functions},
	booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
	series = {Lecture Notes in Computer Science},
	year = {2007},
	month = {2007/01/01/},
	pages = {494 - 508},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {In the distribution-free property testing model, the distance between functions is measured with respect to an arbitrary and unknown probability distribution \mathcal{D} over the input domain. We consider distribution-free testing of several basic Boolean function classes over {0,1} n , namely monotone conjunctions, general conjunctions, decision lists, and linear threshold functions. We prove that for each of these function classes, Ω((n/logn)1/5) oracle calls are required for any distribution-free testing algorithm. Since each of these function classes is known to be distribution-free properly learnable (and hence testable) using Θ(n) oracle calls, our lower bounds are within a polynomial factor of the best possible.},
	keywords = {Algorithm Analysis and Problem Complexity, Discrete Mathematics in Computer Science, Numeric Computing},
	isbn = {978-3-540-74207-4, 978-3-540-74208-1},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-74208-1_36},
	author = {Dana Dachman-Soled and Servedio, Rocco A.},
	editor = {Charikar, Moses and Jansen, Klaus and Reingold, Omer and Rolim, Jos{\'e} D. P.}
}
@inbook {19623,
	title = {Parameterized st-Orientations of Graphs: Algorithms and Experiments},
	booktitle = {Graph Drawing},
	series = {Lecture Notes in Computer Science},
	year = {2007},
	month = {2007/01/01/},
	pages = {220 - 233},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {st-orientations (st-numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an st-orientation of a biconnected graph. However, as indicated in [1], the computation of more than one st-orientation is very important for many applications in multiple research areas, such as this of Graph Drawing. In this paper we show how to compute such orientations with certain (parameterized) characteristics in the final st-oriented graph, such as the length of the longest path. Apart from Graph Drawing, this work applies in other areas such as Network Routing and in tackling difficult problems such as Graph Coloring and Longest Path. We present primary approaches to the problem of computing longest path parameterized st-orientations of graphs, an analytical presentation (together with proof of correctness) of a new O(mlog5 n) (O(mlogn) for planar graphs) time algorithm that computes such orientations (and which was used in [1]) and extensive computational results that reveal the robustness of the algorithm.},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Graphics, Data structures, Discrete Mathematics in Computer Science},
	isbn = {978-3-540-70903-9, 978-3-540-70904-6},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-70904-6_22},
	author = {Charalampos Papamanthou and Tollis, Ioannis G.},
	editor = {Kaufmann, Michael and Wagner, Dorothea}
}
@inbook {19624,
	title = {Applications of Parameterized st-Orientations in Graph Drawing Algorithms},
	booktitle = {Graph Drawing},
	series = {Lecture Notes in Computer Science},
	year = {2006},
	month = {2006/01/01/},
	pages = {355 - 367},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Many graph drawing algorithms use st-numberings (st-orien-tations or bipolar orientations) as a first step. An st-numbering of a biconnected undirected graph defines a directed graph with no cycles, one single source s and one single sink t. As there exist exponentially many st-numberings that correspond to a certain undirected graph G, using different st-numberings in various graph drawing algorithms can result in aesthetically different drawings with different area bounds. In this paper, we present results concerning new algorithms for parameterized st-orientations, their impact on graph drawing algorithms and especially in visibility representations.},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Graphics, Data structures, Discrete Mathematics in Computer Science},
	isbn = {978-3-540-31425-7, 978-3-540-31667-1},
	url = {http://link.springer.com/chapter/10.1007/11618058_32},
	author = {Charalampos Papamanthou and Tollis, Ioannis G.},
	editor = {Healy, Patrick and Nikolov, Nikola S.}
}
@inbook {19610,
	title = {3D Visualization of Semantic Metadata Models and Ontologies},
	booktitle = {Graph Drawing},
	series = {Lecture Notes in Computer Science},
	year = {2005},
	month = {2005/01/01/},
	pages = {377 - 388},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {We propose an algorithm for the 3D visualization of general ontology models used in many applications, such as semantic web, entity-relationship diagrams and other database models. The visualization places entities in the 3D space. Previous techniques produce drawings that are 2-dimensional, which are often complicated and hard to comprehend. Our technique uses the third dimension almost exclusively for the display of the isa relationships (links) while the property relationships (links) are placed on some layer (plane). Thus the semantic difference between isa links and property links, which should be as vertical or as horizontal as possible respectively, is emphasized. Special reference is made on a certain model, the CIDOC Conceptual Reference Model.},
	keywords = {Algorithm Analysis and Problem Complexity, Computer Graphics, Data structures, Discrete Mathematics in Computer Science},
	isbn = {978-3-540-24528-5, 978-3-540-31843-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-540-31843-9_38},
	author = {Charalampos Papamanthou and Tollis, Ioannis G. and Doerr, Martin},
	editor = {Pach, J{\'a}nos}
}
