Radu Sion, Bogdan Carbunar.
"On the Computational Practicality of Private Information Retrieval".
In Proceedings of the 14th ISOC Network and Distributed Systems Security Symposium (NDSS)[15%],
San Diego, February-March 2007
[pdf]
In this paper we explore the limits of single-server
computational private information retrieval (PIR) for the purpose
of preserving client access patterns leakage. We show that deployment
of non-trivial single server PIR protocols on real hardware
of the recent past would have been orders of magnitude less
time-efficient than trivially transferring the entire database.
We stress that these results are beyond existing knowledge
of mere ``impracticality'' under unfavorable assumptions.
They rather reflect an inherent limitation with respect to
modern hardware, likely the result of a communication-cost
centric protocol design. We argue that this is likely to hold
on non-specialized traditional hardware in the foreseeable
future. We validate our reasoning in an experimental setup
on modern off-the-shelf hardware. Ultimately, we hope our
results will stimulate practical designs.
Bogdan Carbunar, Yang Yu, Weidong (Larry) Shi, Michael Pearce, Venu Vasudevan.
"Query Privacy in Wireless Sensor Networks".
In Proceedings of the 4th IEEE International Conference on Sensor and Ad Hoc Communications and Networks (SECON)[20%],
San Diego, June 2007
[pdf]
Existing mechanisms for querying wireless
sensor networks leak client interests to the servers performing
the queries. The leaks are not only in terms of
specific regions but also of client access patterns. In this
paper we introduce the problem of preserving the privacy
of clients querying a wireless sensor network owned by
untrusted organizations. We investigate two architectures
and their corresponding trust models. For the first model,
consisting of multiple, mutually distrusting servers governing
the network, we devise an efficient protocol, SPYC,
and show that it provides full query privacy. For the
second model, where all queries are performed through
a single server, we introduce two metrics for quantifying
the privacy achieved by a client's query sequence. We
propose a suite of practical algorithms, then analyze the
privacy and efficiency levels they provide. Our TOSSIM
simulations show that the proposed query mechanisms
are communication efficient while significantly improving
client query privacy levels.
Larry Shi, Bogdan Carbunar, Radu Sion.
"Conditional E-Cash".
In Proceedings of the 11th Financial Cryptography and Data Security (FC)[18%],
Trinidad/Tobago, February 2007
[pdf]
In this paper we introduce a novel conditional e-cash protocol allowing
future anonymous cashing of bank-issued e-money only upon the
satisfaction of an agreed-upon public condition. Payers are able to remunerate
payees for services that depend on future, yet to be determined outcomes
of events. Once payments complete, any double-spending attempt by the
payer will reveal its identity; no double-spending by the payee is possible.
Payers can not be linked to payees or to ongoing or past transactions.
The flow of cash within the system is thus both correct and anonymous.
We discuss several applications of conditional e-cash including online
trading of financial securities, prediction markets, and betting systems.
Bogdan Carbunar, Radu Sion.
"Uncheatable Reputation for Distributed Computation Markets".
In Proceedings of the 10th Financial Cryptography and Data Security (FC)[29%],
Anguilla, British West Indies, February 2006
[pdf]
Reputation systems aggregate mutual feedback of interacting
peers into a reputation metric for each participant. This is then available
to prospective service ``requesters'' (clients) for the purpose of evaluation
and subsequent selection of potential service providers (servers). For
a reputation framework to be effective, it is paramount for both the
individual feedback and the reputation storage mechanisms to be trusted
and able to deal with faulty behavior of participants such as
``ballot stuffing'' (un-earned positive feedback) and ``bad-mouthing'' (incorrect
negative feedback). While, in human-driven (e.g. Ebay) environments, these
issues are dealt with by hired personnel, on a case by case basis, in auto-
mated environments, this ad-hoc manner of handling is likely not acceptable.
Stronger, secure mechanisms of trust are required.
In this paper we propose a solution for securing reputation mechanisms in
computing markets and grids where servers offer and clients demand compute
services. We introduce ``threshold witnessing'', a mechanism in which a
minimal set of ``witnesses'' provide service interaction feedback and sign
associated ratings for the interacting parties. This endows traditional
feedback rating with trust while handling both ballot-stuffing and
bad-mouthingi attacks. Witnessing relies on a challenge-response protocol in
which servers provide verifiable computation execution proofs. An added
benefit is an assurance of computation result correctness.
|