Volume 2009 Abstracts
- Legally Enforceable Fairness in Secure Two-Party Communication by Yehuda Lindell.
June 12, 2009.
In the setting of secure multiparty computation, a set of mutually
distrustful parties wish to
securely compute some joint function of their private inputs. The computation
should be carried
out in a secure way, meaning that the properties privacy, correctness,
independence of inputs,
fairness and guaranteed output delivery
should all be preserved. Unfortunately, in the case of no
honest majority -- and specifically in the important two-party case -- it is
impossible to achieve fairness and guaranteed output delivery.
In this paper we show how a legal infrastructure that respects digital
signatures can be used to enforce fairness in two-party computation. Our
protocol has the property that if one party obtains output while the
other does not (meanig that fairness is breached) then the party not obtaining
output has a digitally signed cheque from the other party. Thus, fairness can
be "enforced" int the sense that any breach results in a loss of money by the
- Fast C-K-R Partitions of Sparse Graphs
by Manor Mendel and Chaya Schwab.
July 16, 2009.
We present fast algorithms for constructing probabilistic embeddings
and approximate distance oracles in sparse graphs. The main ingredient is a
fast algorithm for sampling the probabilistic partitions of Calinescu,
Karloff, and Rabani in sparse graphs.
Quantum Merlin-Arthur Proof Systems:
Are Multiple Merlins More Helpful to Arthur?
by Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. July 17, 2009.
This paper introduces quantum "multiple--Merlin"--Arthur proof systems
in which Arthur receives multiple
quantum proofs that are unentangled with each other. Although classical
multi-proof systems are obviously
equivalent to classical single-proof systems (i.e., standard Merlin-Arthur
proof systems), it is unclear whether
or not quantum multi-proof systems collapse to quantum single-proof
systems (i.e., standard quantum Merlin-Arthur proof systems). This
paper presents a way of reducing the number of proofs to two while keeping the
two-sided bounded-error property, which gives a necessary and sufficient
condition under which the number
of quantum proofs is reducible to two. It is also proved that, in the case of
perfect soundness, using multiple quantum proofs does not increase the power
of quantum Merlin-Arthur proof systems.
Volume 2008 Abstracts