@inbook {19639,
	title = {On Minimal Assumptions for Sender-Deniable Public Key Encryption},
	booktitle = {Public-Key Cryptography {\textendash} PKC 2014},
	series = {Lecture Notes in Computer Science},
	year = {2014},
	month = {2014/01/01/},
	pages = {574 - 591},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {The primitive of deniable encryption was introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is an encryption scheme with the added feature that after transmitting a message m, both sender and receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message m' in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain adaptively-secure multiparty computation (MPC) protocols and is secure under selective-opening attacks. Different flavors such as sender-deniable and receiver-deniable encryption, where only the sender or receiver produce fake random coins, have been considered. Recently, over 15 years after the primitive was first introduced, Sahai and Waters (IACR Cryptology ePrint Archive, 2013), gave the first construction of sender-deniable encryption schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. Their construction is based on the construction of an indistinguishability obfuscator for general programs recently introduced in a breakthrough result of Garg et al. (FOCS, 2013). Although feasibility has now been demonstrated, the question of determining the minimal assumptions necessary for sender-deniable encryption with super-polynomial security remains open. The primitive of simulatable public key encryption (PKE), introduced by Damg{\r a}rd and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and ciphertexts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O{\textquoteright}Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011). Moreover, the original construction of sender-deniable encryption with polynomial security given by Canetti et al. can be instantiated with simulatable PKE. Thus, a natural question to ask is whether it is possible to construct sender-deniable encryption with super-polynomial security from simulatable PKE. In this work, we investigate the possibility of constructing sender-deniable public key encryption from simulatable PKE in a black-box manner. We show that there is no black-box construction of sender-deniable public key encryption with super-polynomial security from simulatable PKE. This indicates that improving on the original construction of Canetti et al. requires the use of non-black-box techniques, stronger assumptions, or interaction, thus giving some evidence that strong assumptions such as those used by Sahai and Waters are necessary.},
	keywords = {Algorithm Analysis and Problem Complexity, black-box separation, Coding and Information Theory, Data Encryption, sender-deniable encryption, simulatable PKE, Systems and Data Security},
	isbn = {978-3-642-54630-3, 978-3-642-54631-0},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-54631-0_33},
	author = {Dana Dachman-Soled},
	editor = {Krawczyk, Hugo}
}
@inbook {19632,
	title = {Computational Extractors and Pseudorandomness},
	booktitle = {Theory of Cryptography},
	series = {Lecture Notes in Computer Science},
	year = {2012},
	month = {2012/01/01/},
	pages = {383 - 403},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Computational extractors are efficient procedures that map a source of sufficiently high min-entropy to an output that is computationally indistinguishable from uniform. By relaxing the statistical closeness property of traditional randomness extractors one hopes to improve the efficiency and entropy parameters of these extractors, while keeping their utility for cryptographic applications. In this work we investigate computational extractors and consider questions of existence and inherent complexity from the theoretical and practical angles, with particular focus on the relationship to pseudorandomness. An obvious way to build a computational extractor is via the {\textquotedblleft}extract-then-prg{\textquotedblright} method: apply a statistical extractor and use its output to seed a PRG. This approach carries with it the entropy cost inherent to implementing statistical extractors, namely, the source entropy needs to be substantially higher than the PRG{\textquoteright}s seed length. It also requires a PRG and thus relies on one-way functions. We study the necessity of one-way functions in the construction of computational extractors and determine matching lower and upper bounds on the {\textquotedblleft}black-box efficiency{\textquotedblright} of generic constructions of computational extractors that use a one-way permutation as an oracle. Under this efficiency measure we prove a direct correspondence between the complexity of computational extractors and that of pseudorandom generators, showing the optimality of the extract-then-prg approach for generic constructions of computational extractors and confirming the intuition that to build a computational extractor via a PRG one needs to make up for the entropy gap intrinsic to statistical extractors. On the other hand, we show that with stronger cryptographic primitives one can have more entropy- and computationally-efficient constructions. In particular, we show a construction of a very practical computational extractor from any weak PRF without resorting to statistical extractors.},
	keywords = {Algorithm Analysis and Problem Complexity, Coding and Information Theory, Computer Communication Networks, Data Encryption, Math Applications in Computer Science, Systems and Data Security},
	isbn = {978-3-642-28913-2, 978-3-642-28914-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-28914-9_22},
	author = {Dana Dachman-Soled and Gennaro, Rosario and Krawczyk, Hugo and Malkin, Tal},
	editor = {Cramer, Ronald}
}
@inbook {19640,
	title = {On the Black-Box Complexity of Optimally-Fair Coin Tossing},
	booktitle = {Theory of Cryptography},
	series = {Lecture Notes in Computer Science},
	year = {2011},
	month = {2011/01/01/},
	pages = {450 - 467},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {A fair two-party coin tossing protocol is one in which both parties output the same bit that is almost uniformly distributed (i.e., it equals 0 and 1 with probability that is at most negligibly far from one half). It is well known that it is impossible to achieve fair coin tossing even in the presence of fail-stop adversaries (Cleve, FOCS 1986). In fact, Cleve showed that for every coin tossing protocol running for r rounds, an efficient fail-stop adversary can bias the output by Ω(1/r). Since this is the best possible, a protocol that limits the bias of any adversary to O(1/r) is called optimally-fair. The only optimally-fair protocol that is known to exist relies on the existence of oblivious transfer, because it uses general secure computation (Moran, Naor and Segev, TCC 2009). However, it is possible to achieve a bias of O(1/r√)O(1/\sqrt{r}) in r rounds relying only on the assumption that there exist one-way functions. In this paper we show that it is impossible to achieve optimally-fair coin tossing via a black-box construction from one-way functions for r that is less than O(n/logn), where n is the input/output length of the one-way function used. An important corollary of this is that it is impossible to construct an optimally-fair coin tossing protocol via a black-box construction from one-way functions whose round complexity is independent of the security parameter n determining the security of the one-way function being used. Informally speaking, the main ingredient of our proof is to eliminate the random-oracle from {\textquotedblleft}secure{\textquotedblright} protocols with {\textquotedblleft}low round-complexity{\textquotedblright} and simulate the protocol securely against semi-honest adversaries in the plain model. We believe our simulation lemma to be of broader interest.},
	keywords = {Algorithm Analysis and Problem Complexity, black-box separations, Coding and Information Theory, coin tossing, Computer Communication Networks, Data Encryption, lower-bound, Math Applications in Computer Science, optimally-fair coin tossing, round-complexity, Systems and Data Security},
	isbn = {978-3-642-19570-9, 978-3-642-19571-6},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-19571-6_27},
	author = {Dana Dachman-Soled and Lindell, Yehuda and Mahmoody, Mohammad and Malkin, Tal},
	editor = {Ishai, Yuval}
}
@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 {19635,
	title = {Efficient Robust Private Set Intersection},
	booktitle = {Applied Cryptography and Network Security},
	series = {Lecture Notes in Computer Science},
	year = {2009},
	month = {2009/01/01/},
	pages = {125 - 142},
	publisher = {Springer Berlin Heidelberg},
	organization = {Springer Berlin Heidelberg},
	abstract = {Computing Set Intersection privately and efficiently between two mutually mistrusting parties is an important basic procedure in the area of private data mining. Assuring robustness, namely, coping with potentially arbitrarily misbehaving (i.e., malicious) parties, while retaining protocol efficiency (rather than employing costly generic techniques) is an open problem. In this work the first solution to this problem is presented.},
	keywords = {Coding and Information Theory, Computer Communication Networks, Cryptographic protocols, Data Encryption, Data Structures, Cryptology and Information Theory, Information Systems Applications (incl.Internet), Privacy Preserving Data Mining, Secure Two-party Computation, Set Intersection, Systems and Data Security},
	isbn = {978-3-642-01956-2, 978-3-642-01957-9},
	url = {http://link.springer.com/chapter/10.1007/978-3-642-01957-9_8},
	author = {Dana Dachman-Soled and Malkin, Tal and Raykova, Mariana and Yung, Moti},
	editor = {Abdalla, Michel and Pointcheval, David and Fouque, Pierre-Alain and Vergnaud, Damien}
}
