We consider the task of communicating a data stream-a long, possibly infinite message not known in advance to the sender-over a channel with adversarial noise. For any given noise rate c1/2.

An alibi provides evidence of a person's past location and can be critical in proving ones innocence. An alibi involves two parties: the owner, who benefits from the alibi, and the corroborator, who testifies for the owner. As mobile devices become ubiquitous, they can determine where we are and what we are doing, and help us to establish evidence of our location as they accompany us on our daily activities. Existing location-based services like Google Latitude can already track and record our every move, but these systems require us to reveal our identity when recording our location. This leaves our privacy at risk, and requires a trusted third party to maintain our location information.

A "partial broadcast channel" enables one processor to send the same message---simultaneously and privately---to a fixed subset of processors. Suppose that a collection of processors are connected by an arbitrary network of partial broadcast channels (a hypergraph). We initiate the study of necessary and sufficient conditions, complexity bounds, and protocols for individual processors to exchange private messages across this network. Private message exchange, in turn, enables the realization of general secure computation primitives. The model (motivated by various environments such as multicast network architectures and group communication in distributed systems) is an intermediate setting between the private channels model and the full information model, both of which have been investigated extensively in the last few years. We assume a computationally unlimited adversary (i.e., the information theoretic notion of security), and our techniques are combinatorial. Both the possibility and the polynomial-time feasibility of private message exchange are investigated.

We propose a fully functional identity-based encryption (IBE) scheme. The scheme has chosen ciphertext security in the random oracle model assuming a variant of the computational Diffie--Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on elliptic curves is an example of such a map. We give precise definitions for secure IBE schemes and give several applications for such systems.

We address the problem of establishing a group key amongst a dynamic group of users over an unreliable, or lossy, network. We term our key distribution mechanisms self-healing because users are capable of recovering lost group keys on their own, without requesting additional transmissions from the group manager thus cutting back on network traffic, decreasing the load on the group manager and reducing the risk of user exposure through traffic analysis. A user must be a member both before and after the session in which a particular key is sent in order to be able to recover the key through self-healing. Binding the ability to recover keys to membership status enables the group manager to use short broadcasts to establish group keys, independent of the group size. In addition, the self-healing approach to key distribution is stateless, meaning that a group member who has been off-line for some time is able to recover new session keys immediately after coming back on-line.

We present a new solution to the problem of determining the path a packet traversed over the Internet (called the traceback problem) during a denial-of-service attack. This article reframes the traceback problem as a polynomial reconstruction problem and uses algebraic techniques from coding theory and learning theory to provide robust methods of transmission and reconstruction.

We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus N = pq is publicly known. None of the parties know the factorization of N . In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication. All results are presented in the honest but curious scenario (passive adversary).

Digital content distribution systems will enable business models in the near future that cannot be predicted today.I n t h i s paper, we i d e n tify a new security problem that can be crucial to this enablement.The problem arises from the con icting privacy and integrity goals of middlemen in digital distribution chains.Our solution is a novel system design that incorporates obfuscated digital contracts, semi-trusted contract certi ers, and zero-knowledge proofs of arithmetic relations.Our implementation and timing experiments demonstrate that our solution is practical and eÆcient.

We initiate a graph-theoretic study of privacy in distributed environments with mobile eavesdroppers ("bugs"). For two privacy tasks—distributed database maintenance and message transmission—a computationally unbounded adversary “plays an eavesdrpping game,” coordinating the moment of the bugs among the sites to learn the current memory contents. Many different adversaries are considered, motivated by differences in eavesdropping technologies. We characterize the feasibility of the two privacy tasks combinatorially, construct protocols for the feasible cases, and analyze their computational complexity.

We develop new schemes for anonymous authentication that support identity escrow. Our protocols also allow a prover to demonstrate membership in an arbitrary subset of users; key revocation is an important special case of this feature. Using the Fiat-Shamir heuristic, our interactive authentication protocols yield new constructions for non-interactive group signature schemes. We use the higher-residuosity assumption, which leads to greater efficiency and more natural security proofs than previous constructions. It also leads to an increased vulnerability to collusion attacks, although countermeasures are available.

A bstra& A major impediment to using recommendation systems and collective knowledge for electronic commerce is the reluctance of individuals to reveal preferences in order to find groups of people that share them.An equally important barrier to fluid electronic commerce is the lack of agreed upon trusted third parties.We propose new non-third party mechanisms to overcome these barriers.Our solutions facilitate finding shared preferences, discovering communities with shared values, removing disincentives posed by liabilities, and negotiating on behalf of a group.We adapt known techniques from the cryptographic literature to enable these new capabilities.

We introduce a search problem called “mutual search” where k agents, arbitrarily distributed over n sites, are required to locate one another by posing queries of the form “Anybody at site i ?”. We ask for the least number of queries that is necessary and sufficient. For the case of two agents using deterministic protocols, we obtain the following worst-case results: In an oblivious setting (where all pre-planned queries are executed), there is no savings: n -1 queries are required and are sufficient. In a nonoblivious setting, we can exploit the paradigm of “no news is also news” to obtain significant savings: in the synchronous case 0.586 n queries are required; in the asynchronous case 0.896 n queries suffice and a fortiori 0.536 n queries are required; for o(√n) agents using a synchronous deterministic protocol less than n queries suffice; there is a simple randomized protocol for two agents with worst-case expected 0.5 n queries and all radomized protocols require at least 0.25 n worst-case expected queries. The graph-theoretic framework we formulate for expressing and analyzing algorithms for this problem may be of independent interest.

In this work we suggest a new mechanism for metering the popularity of Web sites: the compact metering scheme. Our approach does not rely on client authentication or on a third party. Instead, we suggest the notion of a timing function, a computation

We present new protocols for two parties to exchange documents with fairness, i.e., such that no party can gain an advantage by quitting prematurely or otherwise misbehaving.We use a third party that is L'semi-trusted", in the sense that it may misbehave on its own but will not conspire with either of the main parties.In our solutions, disruption by any one of the three parties will not allow the disrupter gain any useful new information about the documents.Our solutions are efficient and can be based on any of several cryptographic assumptions (e.g., factoring, discrete log, graph isomorpbism).We also discuss the application of our techniques to electronic commerce protocols to achieve fair payment.

In this paper we i.ntroduce R, a distributed public key management service for open networks. f’l offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access control policy. R is built using multiple servers in a way that ensures its correct operation despite the malicious corruption of fewer than one-third of its component servers. We describe the design of R, the protocols underlying its operation, performance in our present implementation, and an experimental application of the service.

In this paper we introduce Ω, a distributed public key management service for open networks. Ω offers interfaces by which clients can register, retrieve, and revoke public keys, and escrow, use (to decrypt messages), and recover private keys, all of which can be subjected to access control policy. Ω is built using multiple servers in a way that ensures its correct operation despite the malicious corruption of fewer than one-third of its component servers. We describe the design of Ω, the protocols underlying its operation, performance in our present implementation, and an experimental application of the service.

We present the design and implementation of a distributed service for performing sealed bid auctions. This service provides an interface by which clients, or "bidders", can issue secret bids to the service for an advertised auction. Once the bidding period has ended, the auction service opens the bids, determines the winning bid, and provides the winning bidder with a ticket for claiming the item bid upon. Using novel cryptographic techniques, the service is constructed to provide strong protection for both the auction house and correct bidders, despite the malicious behavior of any number of bidders and fewer than one third of the servers comprising the auction service. Specifically, it is guaranteed that: bids of correct bidders are not revealed until after the bidding period has ended; the auction house collects payment for the winning bid; losing bidders forfeit no money; and only the winning bidder can collect the item bid upon. We also discuss techniques to enable anonymous bidding.

We present the design and implementation of a distributed service for performing sealed-bid auctions. This service provides an interface by which clients, or "bidders", can issue secret bids to the service for an advertised auction. Once the bidding period has ended, the auction service opens the bids, determines the winning bid, and provides the winning bidder with a ticket for claiming the item bid upon. Using novel cryptographic techniques, the service is constructed to provide strong protection for both the auction house and correct bidders, despite the malicious behavior of any number of bidders and even a constant fraction of the servers comprising the auction service. Specifically, it is guaranteed that (i) bids of correct bidders are not revealed until after the bidding period has ended, (ii) the auction house collects payment for the winning bid, (iii) losing bidders forfeit no money, and (iv) only the winning bidder can collect the item bid upon. We also discuss techniques to enable anonymous bidding.>

Article Secure hypergraphs: privacy from partial broadcast Share on Authors: Matthew Franklin AT&T Bell Laboratories, Holmdel, NJ AT&T Bell Laboratories, Holmdel, NJView Profile , Moti Yung IBM Research Division, T.J. Watson Center, Yorktown, NY IBM Research Division, T.J. Watson Center, Yorktown, NYView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 36–44https://doi.org/10.1145/225058.225077Online:29 May 1995Publication History 40citation399DownloadsMetricsTotal Citations40Total Downloads399Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We initiate a graph-theoretic approach to study the (information-theoretic) maintenance of privacy in distributed environments in the presence of a bounded number of mobile eavesdroppers ("bugs"). For two fundamental privacy problems-secure message transmission and distributed database maintenance-we assume an adversary is "playing eavesdropping games," coordinating the movement of the bugs among the sites to learn the current memory contents. We consider various mobility settings (adversaries), motivated by the capabilities (strength) of the bugging technologies (e.g., how fast can a bug be reassigned). We combinatorially characterize and compare privacy maintenance problems, determine their feasibility (under numerous bug models), suggest protocols for the feasible cases, and analyze their computational complexity.>

A secret-ballot vote for a single proposition is an example of a secure distributed computation. The goal is for m participants to jointly compute the output of some n-ary function (in this case, the sum of the votes), while protecting their individual inputs against some form of misbehavior.

A two-step method is presented for verifying that safety properties are not violated by an HMS (hierarchical multistate) specification of a system. In the first step, the question of safety verification is recast as a reachability problem in an extension of the HMS machine. In the second step, reachability is determined by the use of correctness-preserving and partial correctness-preserving transformations. The method is shown to be complete, and it is illustrated by verifying that a safety property holds for a simple railroad-crossing system if all of its deadlines are met.>

A state-based specification methodology for real-time systems is presented that reduces the number of states by orders of magnitude compared to standard techniques and provides explicit representation for temporal constraints. Formal definitions and a graphic notation for the associated hierarchical multistate (HMS) machines are presented, and various concepts of hierarchy of HMS machines are explored. A promising approach to reusability of specifications using generic nondeterministic HMS machines is introduced. Some preliminary results are presented on the formal verification of properties of an HMS machine by (1) extending it to represent requirements as new states and (2) performing reachability analysis on the extended machine to prove the consistency of the requirements with the original specification.>