Volume 2009 Abstracts
 Legally Enforceable Fairness in Secure TwoParty 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 twoparty 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 twoparty 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
adversarial party.
 Fast CKR 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 MerlinArthur Proof Systems:
Are Multiple Merlins More Helpful to Arthur?
by Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. July 17, 2009.
This paper introduces quantum "multipleMerlin"Arthur proof systems
in which Arthur receives multiple
quantum proofs that are unentangled with each other. Although classical
multiproof systems are obviously
equivalent to classical singleproof systems (i.e., standard MerlinArthur
proof systems), it is unclear whether
or not quantum multiproof systems collapse to quantum singleproof
systems (i.e., standard quantum MerlinArthur proof systems). This
paper presents a way of reducing the number of proofs to two while keeping the
twosided boundederror 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 MerlinArthur proof systems.
Volume 2008 Abstracts
Volume 2007
Published articles
Janos Simon