@article {15126,
	title = {Complete Fairness in Secure Two-Party Computation},
	journal = {Journal of the ACM},
	volume = {58},
	year = {2011},
	month = {2011/12//},
	pages = {24:1{\textendash}24:37 - 24:1{\textendash}24:37},
	abstract = {In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an {\textquotedblleft}embedded XOR{\textquotedblright}; this class of functions includes boolean AND/OR as well as Yao{\textquoteright}s {\textquotedblleft}millionaires{\textquoteright} problem{\textquotedblright}. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.},
	keywords = {cryptography, fairness, secure computation},
	isbn = {0004-5411},
	doi = {10.1145/2049697.2049698},
	url = {http://doi.acm.org/10.1145/2049697.2049698},
	author = {Gordon,S. Dov and Hazay,Carmit and Katz, Jonathan and Lindell,Yehuda}
}
@article {15165,
	title = {Bounds on the efficiency of black-box commitment schemes},
	journal = {Theoretical Computer Science},
	volume = {411},
	year = {2010},
	month = {2010/03/04/},
	pages = {1251 - 1260},
	abstract = {Constructions of cryptographic primitives based on general assumptions (e.g., one-way functions) tend to be less efficient than constructions based on specific (e.g., number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) cryptographic constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of perfectly-binding schemes. Our bounds hold in an extension of the Impagliazzo{\textendash}Rudich model: we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a statistically-binding commitment scheme could be constructed {\textquotedblleft}from scratch{\textquotedblright}).},
	keywords = {Commitment schemes, cryptography},
	isbn = {0304-3975},
	doi = {10.1016/j.tcs.2009.10.021},
	url = {http://www.sciencedirect.com/science/article/pii/S0304397509007737},
	author = {Horvitz,Omer and Katz, Jonathan}
}
@conference {17585,
	title = {Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks},
	booktitle = {IEEE INFOCOM 2009},
	year = {2009},
	month = {2009/04/19/25},
	pages = {1521 - 1529},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters{\textquoteright} decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.},
	keywords = {access hash function, Channel allocation, channel assignment algorithm, channel capacity, collision avoidance, Computer science, cryptography, distributed algorithm, distributed algorithms, Educational institutions, inductive-scheduling technique, Interference, interference set, packet scheduling algorithm, Peer to peer computing, Radio network, radio networks, radiofrequency interference, random oracle methodology, scheduling, Scheduling algorithm, simultaneous channel allocation, software radio, software-defined radio wireless network capacity, telecommunication congestion control, telecommunication security, Throughput, wireless channels, Wireless networks},
	isbn = {978-1-4244-3512-8},
	doi = {10.1109/INFCOM.2009.5062069},
	author = {Han,Bo and Kumar,V. S.A and Marathe,M. V and Parthasarathy,S. and Srinivasan, Aravind}
}
@article {15127,
	title = {Efficient and secure authenticated key exchange using weak passwords},
	journal = {Journal of the ACM (JACM)},
	volume = {57},
	year = {2009},
	month = {2009/11//},
	pages = {3:1{\textendash}3:39 - 3:1{\textendash}3:39},
	abstract = {Mutual authentication and authenticated key exchange are fundamental techniques for enabling secure communication over public, insecure networks. It is well known how to design secure protocols for achieving these goals when parties share high-entropy cryptographic keys in advance of the authentication stage. Unfortunately, it is much more common for users to share weak, low-entropy passwords which furthermore may be chosen from a known space of possibilities (say, a dictionary of English words). In this case, the problem becomes much more difficult as one must ensure that protocols are immune to off-line dictionary attacks in which an adversary exhaustively enumerates all possible passwords in an attempt to determine the correct one. We propose a 3-round protocol for password-only authenticated key exchange, and provide a rigorous proof of security for our protocol based on the decisional Diffie-Hellman assumption. The protocol assumes only public parameters{\textemdash}specifically, a {\textquotedblleft}common reference string{\textquotedblright}{\textemdash}which can be {\textquotedblleft}hard-coded{\textquotedblright} into an implementation of the protocol; in particular, and in contrast to some previous work, our protocol does not require either party to pre-share a public key. The protocol is also remarkably efficient, requiring computation only (roughly) 4 times greater than {\textquotedblleft}classical{\textquotedblright} Diffie-Hellman key exchange that provides no authentication at all. Ours is the first protocol for password-only authentication that is both practical and provably-secure using standard cryptographic assumptions.},
	keywords = {Authentication, cryptography, passwords},
	isbn = {0004-5411},
	doi = {10.1145/1613676.1613679},
	url = {http://doi.acm.org/10.1145/1613676.1613679},
	author = {Katz, Jonathan and Ostrovsky,Rafail and Yung,Moti}
}
@article {15114,
	title = {On expected constant-round protocols for Byzantine agreement},
	journal = {Journal of Computer and System Sciences},
	volume = {75},
	year = {2009},
	month = {2009/02//},
	pages = {91 - 112},
	abstract = {In a seminal paper, Feldman and Micali show an n-party Byzantine agreement protocol in the plain model that tolerates t \&lt; n / 3 malicious parties and runs in expected constant rounds. Here, resolving a question that had been open since their work, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., t \&lt; n / 2 ), and relying only on the existence of signature schemes and a public-key infrastructure. Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network under the same assumptions. Our key technical tool {\textemdash} a new primitive we introduce called moderated VSS {\textemdash} also yields a simpler proof of the Feldman{\textendash}Micali result.In addition, we show a simple technique for sequential composition of Byzantine agreement protocols that do not achieve simultaneous termination, something that is inherent for protocols using o ( t ) rounds.
},
	keywords = {broadcast, cryptography, Distributed computing, secure computation},
	isbn = {0022-0000},
	doi = {10.1016/j.jcss.2008.08.001},
	url = {http://www.sciencedirect.com/science/article/pii/S0022000008000718},
	author = {Katz, Jonathan and Koo,Chiu-Yuen}
}
@conference {17531,
	title = {Fighting Spam with the NeighborhoodWatch DHT},
	booktitle = {IEEE INFOCOM 2009},
	year = {2009},
	month = {2009/04/19/25},
	pages = {1755 - 1763},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {In this paper, we present DHTBL, an anti-spam blacklist built upon a novel secure distributed hash table (DHT). We show how DHTBL can be used to replace existing DNS-based blacklists (DNSBLs) of IP addresses of mail relays that forward spam. Implementing a blacklist on a DHT improves resilience to DoS attacks and secures message delivery, when compared to DNSBLs. However, due to the sensitive nature of the blacklist, storing the data in a peer-to-peer DHT would invite attackers to infiltrate the system. Typical DHTs can withstand fail-stop failures, but malicious nodes may provide incorrect routing information, refuse to return published items, or simply ignore certain queries. The neighborhoodwatch DHT is resilient to malicious nodes and maintains the O(logiV) bounds on routing table size and expected lookup time. NeighborhoodWatch depends on two assumptions in order to make these guarantees: (1) the existence of an on-line trusted authority that periodically contacts and issues signed certificates to each node, and (2) for every sequence of k + 1 consecutive nodes in the ID space, at least one is alive and non-malicious. We show how NeighborhoodWatch maintains many of its security properties even when the second assumption is violated. Honest nodes in NeighborhoodWatch can detect malicious behavior and expel the responsible nodes from the DHT.},
	keywords = {Communications Society, computer crime, cryptography, Databases, IP addresses, IP networks, on-line trusted authority, Peer to peer computing, peer-to-peer computing, peer-to-peer distributed hash table, Postal services, Relays, Resilience, Routing, Security, table size routing, Unsolicited electronic mail},
	isbn = {978-1-4244-3512-8},
	doi = {10.1109/INFCOM.2009.5062095},
	author = {Bender,A. and Sherwood,R. and Monner,D. and Goergen,N. and Spring, Neil and Bhattacharjee, Bobby}
}
@book {15195,
	title = {Introduction to Modern Cryptography},
	year = {2008},
	month = {2008///},
	publisher = {CRC Press},
	organization = {CRC Press},
	abstract = {Cryptography plays a key role in ensuring the privacy and integrity of data and the security of computer networks. Introduction to Modern Cryptography provides a rigorous yet accessible treatment of modern cryptography, with a focus on formal definitions, precise assumptions, and rigorous proofs. The authors introduce the core principles of modern cryptography, including the modern, computational approach to security that overcomes the limitations of perfect secrecy. An extensive treatment of private-key encryption and message authentication follows. The authors also illustrate design principles for block ciphers, such as the Data Encryption Standard (DES) and the Advanced Encryption Standard (AES), and present provably secure constructions of block ciphers from lower-level primitives. The second half of the book focuses on public-key cryptography, beginning with a self-contained introduction to the number theory needed to understand the RSA, Diffie-Hellman, El Gamal, and other cryptosystems. After exploring public-key encryption and digital signatures, the book concludes with a discussion of the random oracle model and its applications. Serving as a textbook, a reference, or for self-study, Introduction to Modern Cryptography presents the necessary tools to fully understand this fascinating subject.},
	keywords = {Computer networks, computer security, Computers / Operating Systems / General, Computers / Security / General, cryptography, Language Arts \& Disciplines / Communication Studies, Mathematics / Combinatorics},
	isbn = {9781584885511},
	author = {Katz, Jonathan and Lindell,Yehuda}
}
@conference {19036,
	title = {Multi-Dimensional Range Query over Encrypted Data},
	year = {2007},
	month = {2007},
	pages = {350 - 364},
	abstract = {We design an encryption scheme called multi-dimensional range query over encrypted data (MRQED), to address the privacy concerns related to the sharing of network audit logs and various other applications. Our scheme allows a network gateway to encrypt summaries of network flows before submitting them to an untrusted repository. When network intrusions are suspected, an authority can release a key to an auditor, allowing the auditor to decrypt flows whose attributes (e.g., source and destination addresses, port numbers, etc.) fall within specific ranges. However, the privacy of all irrelevant flows are still preserved. We formally define the security for MRQED and prove the security of our construction under the decision bilinear Diffie-Hellman and decision linear assumptions in certain bilinear groups. We study the practical performance of our construction in the context of network audit logs. Apart from network audit logs, our scheme also has interesting applications for financial audit logs, medical privacy, untrusted remote storage, etc. In particular, we show that MRQED implies a solution to its dual problem, which enables investors to trade stocks through a broker in a privacy-preserving manner.},
	keywords = {auditing, cryptography, data privacy, decision bilinear Diffie-Hellman, decision linear assumptions, encrypted data, multi-dimensional range query, network audit logs, network gateway, network intrusions},
	author = {Elaine Shi and Bethencourt, J. and Chan, T.-H.H. and Song, Dawn and Perrig, A.}
}
@article {12088,
	title = {The dangers of mitigating security design flaws: a wireless case study},
	journal = {IEEE Security \& Privacy},
	volume = {1},
	year = {2003},
	month = {2003/02//Jan},
	pages = {28 - 36},
	abstract = {Mitigating design flaws often provides the only means to protect legacy equipment, particularly in wireless local area networks. A synchronous active attack against the wired equivalent privacy protocol demonstrates how mitigating one flaw or attack can facilitate another.},
	keywords = {Communication system security, computer security, cryptography, design flaw mitigation, Dictionaries, legacy equipment, privacy, Protection, Protocols, security design flaws, security of data, synchronous active attack, telecommunication security, Telecommunication traffic, wired equivalent privacy protocol, Wireless LAN, wireless local area networks, Wireless networks},
	isbn = {1540-7993},
	doi = {10.1109/MSECP.2003.1176993},
	author = {Petroni,N. L. and Arbaugh, William A.}
}
@article {14653,
	title = {A secure PLAN},
	journal = {IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews},
	volume = {33},
	year = {2003},
	month = {2003/08//},
	pages = {413 - 426},
	abstract = {Active networks, being programmable, promise greater flexibility than current networks. Programmability, however, may introduce safety and security risks. This correspondence describes the design and implementation of a security architecture for the active network PLANet. Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN, with an environment of general-purpose service routines governed by trust management. In particular, a technique is used which expands or contracts a packet{\textquoteright}s service environment based on its level of privilege, termed namespace-based security. The design and implementation of an active-network firewall and virtual private network is used as an application of the security architecture. Measurements of the system show that the addition of the firewall imposes an approximately 34\% latency overhead and as little as a 6.7\% space overhead to incoming packets.},
	keywords = {active networks, active-network firewall, Authentication, Authorization, Contracts, cryptography, Environmental management, Extraterrestrial measurements, functionally restricted packet language, general-purpose service routines, Internet, latency overhead, namespace-based security, packet switching, PLANet, Planets, privilege level, programmable networks, Safety, safety risks, secure PLAN, security of data, security risks, trust management, two-level architecture, virtual private network, Virtual private networks, Web and internet services},
	isbn = {1094-6977},
	doi = {10.1109/TSMCC.2003.817347},
	author = {Hicks, Michael W. and Keromytis,A. D and Smith,J. M}
}
@conference {17642,
	title = {P5 : a protocol for scalable anonymous communication},
	booktitle = {2002 IEEE Symposium on Security and Privacy, 2002. Proceedings},
	year = {2002},
	month = {2002///},
	pages = {58 - 70},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We present a protocol for anonymous communication over the Internet. Our protocol, called P5 (peer-to-peer personal privacy protocol) provides sender-, receiver-, and sender-receiver anonymity. P5 is designed to be implemented over current Internet protocols, and does not require any special infrastructure support. A novel feature of P5 is that it allows individual participants to trade-off degree of anonymity for communication efficiency, and hence can be used to scalably implement large anonymous groups. We present a description of P5, an analysis of its anonymity and communication efficiency, and evaluate its performance using detailed packet-level simulations.},
	keywords = {Broadcasting, communication efficiency, Computer science, cryptography, data privacy, Educational institutions, Internet, large anonymous groups, P5 protocol, packet-level simulations, Particle measurements, Peer to peer computing, peer-to-peer personal privacy protocol, privacy, Protocols, receiver anonymity, scalable anonymous communication, security of data, sender anonymity, sender-receiver anonymity, Size measurement, telecommunication security},
	isbn = {0-7695-1543-6},
	doi = {10.1109/SECPRI.2002.1004362},
	author = {Sherwood,R. and Bhattacharjee, Bobby and Srinivasan, Aravind}
}
@conference {18690,
	title = {Quantifying the cost of providing intrusion tolerance in group communication systems},
	year = {2002},
	month = {2002///},
	pages = {229 - 238},
	abstract = {Group communication systems that provide consistent group membership and reliable, ordered multicast properties in the presence of faults resulting from malicious intrusions have not been analyzed extensively to quantify the cost of tolerating these intrusions. This paper attempts to quantify this cost by presenting results from an experimental evaluation of three new intrusion-tolerant microprotocols that have been added to an existing crash-fault-tolerant group communication system. The results are analyzed to identify the parts that contribute the most overhead during provision of intrusion tolerance at the group communication system level.},
	keywords = {consistent group membership, crash-fault-tolerant group communication system, cryptography, finite state machines, groupware, intrusion-tolerant microprotocols, malicious intrusions, multicast communication, reliable ordered multicast properties, security of data, Transport protocols},
	doi = {10.1109/DSN.2002.1028904},
	author = {Ramasamy,H. V. and Pandey,P. and Lyons,J. and Michel Cukier and Sanders,W. H.}
}
@conference {14654,
	title = {A secure PLAN (extended version)},
	booktitle = {DARPA Active NEtworks Conference and Exposition, 2002. Proceedings},
	year = {2002},
	month = {2002///},
	pages = {224 - 237},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {Active networks promise greater flexibility than current networks, but threaten safety and security by virtue of their programmability. We describe the design and implementation of a security architecture for the active network PLANet (Hicks et al., 1999). Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN (Hicks et al., 1998), with an environment of general-purpose service routines governed by trust management (Blaze et al., 1996). In particular, we employ a technique which expands or contracts a packet{\textquoteright}s service environment based on its level of privilege, termed namespace-based security. As an application of our security architecture, we present the design and implementation of an active-network firewall. We find that the addition of the firewall imposes an approximately 34\% latency overhead and as little as a 6.7\% space overhead to incoming packets},
	keywords = {active internetwork, active networks, active-network firewall, Authentication, authorisation, Authorization, Cities and towns, Computer networks, Computer science, cryptography, functionally restricted packet language, general-purpose service routines, Information security, internetworking, IP networks, latency overhead, namespace-based security, PLAN, PLANet, Planets, programmability, Safety, security architecture, telecommunication security, trust management, two-level architecture, Web and internet services},
	isbn = {0-7695-1564-9},
	doi = {10.1109/DANCE.2002.1003496},
	author = {Hicks, Michael W. and Keromytis,A. D and Smith,J. M}
}
@article {12089,
	title = {Secure quality of service handling: SQoSH},
	journal = {IEEE Communications Magazine},
	volume = {38},
	year = {2000},
	month = {2000/04//},
	pages = {106 - 112},
	abstract = {Proposals for programmable network infrastructures, such as active networks and open signaling, provide programmers with access to network resources and data structures. The motivation for providing these interfaces is accelerated introduction of new services, but exposure of the interfaces introduces many new security risks. We describe some of the security issues raised by active networks. We then describe our secure active network environment (SANE) architecture. SANE was designed as a security infrastructure for active networks, and was implemented in the SwitchWare architecture. SANE restricts the actions that loaded modules can perform by restricting the resources that can be named; this is further extended to remote invocation by means of cryptographic credentials. SANE can be extended to support restricted control of quality of service in a programmable network element. The Piglet lightweight device kernel provides a {\textquotedblleft}virtual clock{\textquotedblright} type of scheduling discipline for network traffic, and exports several tuning knobs with which the clock can be adjusted. The ALIEN active loader provides safe access to these knobs to modules that operate on the network element. Thus, the proposed SQoSH architecture is able to provide safe, secure access to network resources, while allowing these resources to be managed by end users needing customized networking services. A desirable consequence of SQoSH{\textquoteright}s integration of access control and resource control is that a large class of denial-of-service attacks, unaddressed solely with access control and cryptographic protocols, can now be prevented},
	keywords = {Acceleration, Access control, active networks, ALIEN active loader, Clocks, Computer network management, cryptographic credentials, cryptography, customized networking services, Data security, Data structures, denial-of-service attacks, interfaces, Kernel, loaded modules, network resources, network traffic, open signaling, packet switching, Piglet lightweight device kernel, programmable network element, programmable network infrastructures, Programming profession, Proposals, quality of service, remote invocation, resource control, restricted control of quality of service, SANE, scheduling, scheduling discipline, secure active network environment architecture, secure quality of service handling, security infrastructure, security risks, SQoSH, SwitchWare architecture, telecommunication security, tuning knobs, virtual clock},
	isbn = {0163-6804},
	doi = {10.1109/35.833566},
	author = {Alexander,D. S and Arbaugh, William A. and Keromytis,A. D and Muir,S. and Smith,J. M}
}
@article {12103,
	title = {Security for virtual private intranets},
	journal = {Computer},
	volume = {31},
	year = {1998},
	month = {1998/09//},
	pages = {48 - 55},
	abstract = {As telecommuting grows, businesses must consider security when extending their network environment to employees{\textquoteright} homes. Researchers at the University of Pennsylvania have addressed the problem with smart cards, operating system modifications, and network authentication. We note the distinction between trust and integrity: trust is determined through the verification of components and the dependencies among them, while integrity demonstrates that components haven{\textquoteright}t been modified. Thus integrity checking in a trustworthy system is about preserving an established trust or trust relationship. Our solution to the challenge of isolating functional roles that may share a single hardware platform is called secure identity based lending (SIBL). SIBL provides multiple personalities by partitioning the hard drive into n+1 partitions, where n is the number of supported personalities. All personalities use the system partition for core operating system components and shared applications. Each of the personalities is also associated with one of the remaining partitions, which are encrypted using a symmetric algorithm},
	keywords = {businesses, Clouds, Companies, core operating system components, cryptography, Data security, employee homes, encryption, functional roles, hard drive, Home computing, home working, integrity checking, Internet, Local area networks, multiple personalities, network authentication, network environment, operating system modifications, Operating systems, Roads, secure identity based lending, security management, security of data, shared applications, SIBL, single hardware platform, smart cards, symmetric algorithm, system partition, telecommuting, Teleworking, trust relationship, trustworthy system, virtual private intranets},
	isbn = {0018-9162},
	doi = {10.1109/2.708450},
	author = {Arbaugh, William A. and Davin,J. R and Farber,D. J and Smith,J. M}
}
@article {12079,
	title = {The SwitchWare active network architecture},
	journal = {IEEE Network},
	volume = {12},
	year = {1998},
	month = {1998/06//May},
	pages = {29 - 36},
	abstract = {Active networks must balance the flexibility of a programmable network infrastructure against the safety and security requirements inherent in sharing that infrastructure. Furthermore, this balance must be achieved while maintaining the usability of the network. The SwitchWare active network architecture is a novel approach to achieving this balance using three layers: active packets, which contain mobile programs that replace traditional packets; active extensions, which provide services on the network elements and can be dynamically loaded; and a secure active router infrastructure, which forms a high-integrity base on which the security of the other layers depends. In addition to integrity checking and cryptography-based authentication, security in our architecture depends heavily on verification techniques from programming languages, such as strong type checking},
	keywords = {active extensions, active packets, Authentication, Computer languages, Computer networks, cryptography, cryptography-based authentication, high-integrity base, integrity checking, IP networks, LAN interconnection, mobile programs, network operating systems, packet switching, programmable network infrastructure, programming languages, Protocols, Safety, safety requirements, scalability, secure active router infrastructure, Security, security requirements, services, strong type checking, Switches, SwitchWare active network architecture, telecommunication network routing, Tin, usability, verification techniques},
	isbn = {0890-8044},
	doi = {10.1109/65.690959},
	author = {Alexander,D. S and Arbaugh, William A. and Hicks, Michael W. and Kakkar,P. and Keromytis,A. D and Moore,J. T and Gunter,C. A and Nettles,S. M and Smith,J. M}
}
@conference {17577,
	title = {Computing with very weak random sources},
	booktitle = {, 35th Annual Symposium on Foundations of Computer Science, 1994 Proceedings},
	year = {1994},
	month = {1994/11/20/22},
	pages = {264 - 275},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {For any fixed ε>0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy R(ε). Such a weak random source is asked once for R(ε) bits; it outputs an R-bit string such that any string has probability at most 2-R(ε). If ε>1-1/(k+1), our BPP simulations take time nO(log(k n)) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and the hardness of approximation. Also of interest is our randomness-efficient Leftover Hash Lemma, found independently by Goldreich and Wigderson},
	keywords = {Application software, BPP simulations, Chor-Goldreich sources, computational complexity, Computational modeling, Computer science, Computer simulation, cryptography, distributed algorithms, expander constructions, hardness, MATHEMATICS, min-entropy, Physics computing, Polynomials, probability, R-bit string, randomness-efficient Leftover Hash Lemma, RP algorithms simulation, Testing, time-space tradeoffs, very weak random sources},
	isbn = {0-8186-6580-7},
	doi = {10.1109/SFCS.1994.365688},
	author = {Srinivasan, Aravind and Zuckerman,D.}
}
