Chicago Journal of Theoretical Computer Science

Volume 2009 Abstracts

  1. 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 adversarial party.
  2. 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.
  3. 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
[back] Volume 2007 [back] Published articles
[CJCTS home]

Janos Simon