Publications

Complexity

• "A constant-round public-coin protocol for sampling with size, and applications " [Abs, Bib, PS, PDF]
  I. Haitner, M. Mahmoody-Ghidary, and D. Xiao. Princeton Technical Report TR-867-09, 2009.
  x

  We present a constant-round public-coin protocol between an efficient verifier and an all-powerful (but possibly cheating) prover that achieves the following. Both parties take as input an efficiently verifiable set $S$, an approximation $s \approx |S|$, and an efficiently computable partition $f : S \rightarrow \zo^*$ where $f(x) = f(x')$ if and only if $x, x'$ belong to the same set of the partition. The verifier is guaranteed to output with high probability a uniformly random $x \getsr S$ along with a number $s_x$ that approximates the size of the set $|f^{-1}(f(x))|$.

  Our main application is to rule out certain black-box reductions from the worst-case hardness of $\SAT$ to the task of breaking the binding of a constant-round statistically hiding commitment scheme. We show that the existence of a $k$-adaptive randomized reduction for the above task implies that $\coNP$ has a $O(k)$-round public-coin interactive protocol, namely $\coNP \subseteq \AM[k]$. As corollaries, we derive the following:

  1. A $O(1)$-adaptive reduction implies that the Polynomial Hierarchy collapses to the second level (Boppana et al., Inf. Proc. Letters 1987).
  2. A $\polylog(n)$-adaptive reduction implies the Exponential Hierarchy collapses to its third level (Pavan et al., Theor. Comp. Sci. 2007).
  3. A $o(n)$-adaptive reduction improves the round-complexity of the best known interactive proof for $\UNSAT$ (the language of unsatisfiable formulas).

  Our impossibility result holds even if the hiding property of the commitment scheme is only guaranteed to hold against honest receivers. Naturally, our result extends to any primitive that implies constant-round statistically hiding commitment via a black-box proof of security. Most notably, this includes collision resistant hash functions, as well as constant-round protocols for single-server private information retrieval and oblivious transfer with statistical security for one of the parties.

  x

  @techreport {HMX09,
  author = "Haitner, Iftach and Mahmoody-Ghidary, Mohammad and Xiao, David",
  title = "A constant-round public-coin protocol for sampling with size, and applictions",
  institution = "Princeton University",
  number = "TR-867-09",
  year = "2009",
  }
• "New Perspectives on the Complexity of Computational Learning, and Other Problems in Theoretical Computer Science " [Abs, Bib, PS, PDF]
  D. Xiao. Ph. D thesis. Princeton University, 2009.

  x

  In this thesis we present the following results.

  • Learning theory, and in particular PAC learning, was introduced by Valiant [CACM 1984] and has since become a major area of research in theoretical and applied computer science. One natural question that was posed at the very inception of the field is whether there are classes of functions that are hard to learn.

    PAC learning is hard under widely held conjectures such as the existence of one-way functions, and on the other hand it is known that if PAC learning is hard then $\P \neq \NP$. We further study sufficient and necessary conditions for PAC learning to be hard, and we prove that:

    1. $\ZK \neq \BPP$ implies that PAC learning is hard.
    2. It is unlikely using standard techniques that one can prove that PAC learning is hard implies that $\ZK \neq \BPP$.
    3. It is unlikely using standard techniques that one can prove that $\P \neq \NP$ implies that $\ZK \neq \BPP$.

    Here, ``standard techniques'' refers to various classes of efficient reductions. Together, these results imply that the hardness of PAC learning lies between the non-triviality of $\ZK$ on the one hand and the hardness of $\NP$ on the other hand. Furthermore, the hardness of PAC learning lies ``strictly'' between the two, in the sense that most standard techniques cannot prove equivalence with either $\ZK \neq \BPP$ or $\NP \neq \P$.

    xIn proving these results, we show new connections between PAC learning and auxiliary-input one-way functions, which were defined by Ostrovsky and Wigderson [ISTCS 1993] to better understand $\ZK$. We also define new problems related to PAC learning that we believe of are independent interest, and may be useful in future studies of the complexity of PAC learning.

  • A secure failure-localization (FL) protocol allows a sender to localize faulty links on a single path through a network to a receiver, even when intermediate nodes on the path behave adversarially. Such protocols were proposed as tools that enable Internet service providers to select high-performance paths through the Internet, or to enforce contractual obligations. We give the first formal definitions of security for FL protocols and prove that for such protocols, security requires each intermediate node on the path to have some shared secret information (\eg keys), and that every black-box construction of a secure FL protocol from a random oracle requires each intermediate node to invoke the random oracle. This suggests that achieving this kind of security is unrealistic as intermediate nodes have little incentive to participate in the real world.

  • Ahlswede and Winter [IEEE Trans. Inf. Th. 2002] introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan [JCSS 1988]). As a consequence, we derandomize a construction of Alon and Roichman [RSA 1994] to efficiently construct an expanding Cayley graph of logarithmic degree on any (possibly non-abelian) group. This gives an optimal solution to the homomorphism testing problem of Shpilka and Wigderson [STOC 2004]. We also apply these pessimistic estimators to the problem of solving semi-definite covering problems, thus giving a deterministic algorithm for the quantum hypergraph cover problem of Ahslwede and Winter.

  x

  @phdthesis{XiaoThesis09,
  author = "David Xiao",
  title = "New Perspectives on the Complexity of Computational Learning, and Other Problems in Theoretical Computer Science",
  school = "Princeton University",
  year = "2009"
  }
• "On basing ZK != BPP on the hardness of PAC learning " [Abs, Bib,PS, PDF]
  D. Xiao. CCC 2009.

  x

  Learning is a central task in computer science, and there are various formalisms for capturing the notion. One important model studied in computational learning theory is the PAC model of Valiant (CACM 1984). On the other hand, in cryptography the notion of "learning nothing" is often modelled by the simulation paradigm: in an interactive protocol, a party learns nothing if it can produce a transcript of the protocol by itself that is indistinguishable from what it gets by interacting with other parties. The most famous example of this paradigm is zero knowledge proofs, introduced by Goldwasser, Micali, and Rackoff (SICOMP 1989).

  Applebaum et al. (FOCS 2008) observed that a theorem of Ostrovsky and Wigderson (ISTCS 1993) combined with the transformation of one-way functions to pseudo-random functions (Håstad et al. SICOMP 1999, Goldreich et al. J. ACM 1986) implies that if there exist non-trivial languages with zero-knowledge arguments, then no efficient algorithm can PAC learn polynomial-size circuits. They also prove a weak reverse implication, that if a certain non-standard learning task is hard, then zero knowledge is non-trivial. This motivates the question we explore here: can one prove that hardness of PAC learning is equivalent to non-triviality of zero-knowledge? We show that this statement cannot be proven via the following techniques:

  1. Relativizing techniques: there exists an oracle relative to which learning polynomial-size circuits is hard and yet the class of languages with zero knowledge arguments is trivial.
  2. Semi-black-box techniques: if there is a black-box construction of a zero-knowledge argument for an NP-complete language (possibly with a non-black-box security reduction) based on hardness of PAC learning, then NP has statistical zero knowledge proofs, namely NP is contained in SZK.

  Under the standard conjecture that NP is not contained in SZK, our results imply that most standard techniques do not suffice to prove the equivalence between the non-triviality of zero knowledge and the hardness of PAC learning. Our results hold even when considering non-uniform hardness of PAC learning with membership queries. In addition, our technique relies on a new kind of separating oracle that may be of independent interest.

  x

  @inproceedings{Xiao09,
  author = {David Xiao},
  title = {On basing $\ZK \neq \BPP$ on the hardness of PAC learning},
  booktitle = {In Proc. CCC '09},
  pages = {304--315},
  year = {2009},
  }
• "On basing lower-bounds for learning on worst-case assumptions" [Abs, Bib, PS, PDF]
  B. Applebaum, B. Barak, D. Xiao. FOCS 2008
  x

  We consider the question of whether $\P\neq\NP$ implies that there exists some concept class that is efficiently representable but is still hard to learn in the PAC model of Valiant (CACM '84). We show that unless the Polynomial Hierarchy collapses, such a statement cannot be proven via a large class of reductions including Karp reductions, truth-table reductions, and a restricted form of non-adaptive Turing reductions. Also, a proof that uses a Turing reduction of constant levels of adaptivity would imply an important consequence in cryptography as it yields a transformation from any average-case hard problem in $\NP$ to a one-way function. Our results hold even in the stronger model of agnostic learning.

  These results are obtained by showing that lower bounds for improper learning are intimately related to the complexity of zero-knowledge arguments and to the existence of weak cryptographic primitives. In particular, we prove that if a language $L$ reduces to the task of improper learning circuits, then, depending on the type of the reduction in use, either (1) $L$ has a statistical zero-knowledge argument system, or (2) the worst-case hardness of $L$ implies the existence of a weak variant of one-way functions defined by Ostrovsky-Wigderson (ISTCS '93). Interestingly, we observe that the converse implication also holds. Namely, if (1) or (2) hold then the intractability of L implies that improper learning is hard.

  x

  @inproceedings{ABX08,
  author = {Benny Applebaum and Boaz Barak and David Xiao},
  title = {On Basing Lower-Bounds for Learning on Worst-Case Assumptions},
  year = {2008},
  booktitle = {Proc. FOCS '08},
  pages = {211-220}
  }
• "Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators and applications" [Abs, Bib, PS, PDF]
  A. Wigderson and D. Xiao, Theory of Computing, Vol. 4 #3 (2008)
  x

  Ahlswede and Winter [IEEE Trans. Inf. Th. 2002] introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan [JCSS 1988]). As a consequence, we derandomize a construction of Alon and Roichman [RSA 1994] to efficiently construct an expanding Cayley graph of logarithmic degree on any (possibly non-abelian) group. This gives an optimal solution to the homomorphism testing problem of Shpilka and Wigderson [STOC 2004]. We also apply these pessimistic estimators to the problem of solving semi-definite covering problems, thus giving a deterministic algorithm for the quantum hypergraph cover problem of Ahslwede and Winter.

  The results above appear as theorems in our paper ``A randomness-efficient sampler for matrix-valued functions and applications'' [FOCS 2005, ECCC 2005], as consequences of the main claim of that paper: a randomness efficient sampler for matrix valued functions via expander walks. However, we discovered an error in the proof of that main theorem (which we briefly describe in the appendix). That claim stating that the expander walk sampler is good for matrix-valued functions thus remains open. One purpose of the current paper is to show that the applications in that paper hold true despite our inability to prove the expander walk sampler theorem for matrix-valued functions.

  x

  @article{WX08,
  author = {Avi Wigderson and David Xiao},
  title = {Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications},
  journal = {Theory of Computing},
  year = {2008},
  pages = {53-76},
  publisher = {Theory of Computing},
  volume = {4},
  number = {3},
  URL = {http://www.theoryofcomputing.org/articles/v004a003},
  eprint = {toc:v004/a003},
  }
• "A randomness-efficient sampler for matrix-valued functions and applications" [Abs, Bib, PS, PDF]
  A. Wigderson and D. Xiao, FOCS 2005
  x

  N.B.: refer to [WX08] for details about errors in this paper.

  In this paper we give a randomness-efficient sampler for matrix-valued functions. Specifically, we show that a random walk on an expander approximates the recent Chernoff-like bound for matrix-valued functions of Ahlswede and Winter [IEEE Trans. Inf. Th. '02], in a manner which depends optimally on the spectral gap. The proof uses perturbation theory, and is a generalization of Gillman's [FOCS '93] and Lezaud's [Ann. App. Prob. '98] analyses of the Ajtai-Komlos-Szemeredi sampler for real-valued functions [STOC '87].

  Derandomizing our sampler gives a few applications, yielding deterministic polynomial time algorithms for problems in which derandomizing independent sampling gives only quasi-polynomial time deterministic algorithms. The first (which was our original motivation) is to a polynomial-time derandomization of the Alon-Roichman theorem [Rand. St. and Alg. '94]: given a group of size $n$, find $O(\log n)$ elements which generate it as an expander. This implies a second application - efficiently constructing a randomness-optimal homomorphism tester, significantly improving the previous result of Shpilka and Wigderson [FOCS '04]. The third is to a ``non-commutative'' hypergraph covering problem - a natural extension of the set-cover problem which arises in quantum information theory, in which we efficiently attain the integrality gap when the fractional semi-definite relaxation cost is constant.

  x

  @inproceedings{WX05,
  author = {Avi Wigderson and David Xiao},
  title = {A randomness-efficient sampler for matrix-valued functions and applications},
  booktitle = {Proc.\ $46$th FOCS},
  pages = {397--406},
  year={2005},
  }

Cryptography and Security

• "(Nearly) optimal black-box constructions of commitments secure against selective opening attacks " [Abs, Bib, PS, PDF]
  D. Xiao. Manuscript 2009.
  x

  Selective opening attacks against commitment schemes occur when the commitment scheme is repeated in parallel (or concurrently) and an adversary can choose depending on the commit-phase transcript to see the values and openings to some subset of the committed bits. Commitments are secure under such attacks if one can prove that the remaining, unopened commitments stay secret.

  We prove the following black-box constructions and black-box lower bounds for commitments secure against selective opening attacks:

  1. For parallel composition, $4$ rounds are necessary and sufficient to build computationally binding and computationally hiding commitments.
  2. For parallel composition, $O(1)$-round statistically-hiding commitments are equivalent to $O(1)$-round statistically-binding commitments.
  3. For concurrent composition, $\omega(\log n)$ rounds are sufficient to build statistically binding commitments and are necessary even to build computationally binding and computationally hiding commitments, up to $\log \log n$ factors.

  Our lower bounds improve upon the parameters obtained by the impossibility results of Bellare et al. (EUROCRYPT '09), and are proved in a fundamentally different way, by observing that essentially all known impossibility results for black-box zero-knowledge can also be applied to the case of commitments secure against selective opening attacks.

  In addition to the impossibility results mentioned above, we also rule out the existence of commitments with zero statistical binding error and receiver public-coin commitments for parallel composition.

  x

  @misc{XiaoCom09,
  author = "David Xiao",
  title = "(Nearly) optimal black-box constructions for commitments secure against selective opening attacks",
  note = "Manuscript",
  year = "2009"
  }
• "On the round complexity of zero-knowledge proofs from one-way permutations " [Abs, Bib, PS, PDF]
  S. Gordon, H. Wee, D. Xiao, and A. Yerukhimovich. Manuscript 2009.
  x

  We consider the following problem: can we construct constant-round zero-knowledge proofs (with negligible soundness) for $\NP$ assuming only the existence of one-way permutations? We answer the question in the negative for fully black-box constructions (using only black-box access to both the underlying primitive and the cheating verifier) that satisfy a natural restriction on the ``adaptivity'' of the simulator's queries. Specifically, we show that only languages in $\coAM$ have constant-round zero-knowledge proofs of this kind.

  x

  @misc{GWXY09,
  author = "S. Dov Gordon and Hoeteck Wee and David Xiao and Arkady Yerukhimovich",
  title = "On the round complexity of zero-knowledge proofs from one-way permutations",
  note = "Manuscript",
  year = "2009"
  }
• "Path-quality monitoring in the presence of adversaries" [Abs, Bib,PS, PDF]
  S. Goldberg, D. Xiao, E. Tromer, B. Barak, and J. Rexford. SIGMETRICS 2008
  x

  Edge networks connected to the Internet need effective monitoring techniques to drive routing decisions and detect violations of Service Level Agreements (SLAs). However, existing measurement tools, like ping, traceroute, and trajectory sampling, are vulnerable to attacks that can make a path look better than it really is. In this paper, we design and analyze path-quality monitoring protocols that reliably raise an alarm when the packet-loss rate and delay exceed a threshold, even when an adversary tries to bias monitoring results by selectively delaying, dropping, modifying, injecting, or preferentially treating packets.

  Despite the strong threat model we consider in this paper, our protocols are efficient enough to run at line rate on high-speed routers. We present a secure sketching protocol for identifying when packet loss and delay degrade beyond a threshold. This protocol is extremely lightweight, requiring only 250–600 bytes of storage and periodic transmission of a comparably sized IP packet to monitor billions of packets. We also present secure sampling protocols that provide faster feedback and accurate round-trip delay estimates, at the expense of somewhat higher storage and communication costs. We prove that all our protocols satisfy a precise definition of secure path-quality monitoring and derive analytic expressions for the trade-off between statistical accuracy and system overhead. We also compare how our protocols perform in the client-server setting, when paths are asymmetric, and when packet marking is not permitted.

  .
  x

  @article{GXTBR08,
  author = {Goldberg, Sharon and Xiao, David and Tromer, Eran and Barak, Boaz and Rexford, Jennifer},
  title = {Path-quality monitoring in the presence of adversaries},
  journal = {SIGMETRICS Perform. Eval. Rev.},
  volume = {36},
  number = {1},
  year = {2008},
  issn = {0163-5999},
  pages = {193--204},
  doi = {http://doi.acm.org/10.1145/1384529.1375480},
  publisher = {ACM},
  address = {New York, NY, USA},
  }
• "Protocols and lower bounds for failure localization in the Internet" [Abs, Bib,PS, PDF]
  B. Barak, S. Goldberg, and D. Xiao. EUROCRYPT 2008
  x

  A secure failure-localization path-quality-monitoring (FL-PQM) protocol allows a sender to localize faulty links on a single path through a network to a receiver, even when intermediate nodes on the path behave adversarially. Such protocols were proposed as tools that enable Internet service providers to select high-performance paths through the Internet, or to enforce contractual obligations. We give the first formal definitions of security for FL-PQM protocols and construct:

  1. A simple FL-PQM protocol that can localize a faulty link every time a packet is not correctly delivered. This protocol’s communication and storage overhead is O(1) additional messages of length O(n) per packet (where n is the security parameter).
  2. A two more efficient FL-PQM protocols that can localize a faulty link when a noticeable fraction of the packets sent during some time period are not correctly delivered. Our sampling-based protocol has a storage and communication overhead that is an arbitrarily small fraction of the total number of packets sent T. Our sketching-based protocol requires O(n + log T ) storage and only two additional messages of similar length.

  We also prove lower bounds for such protocols:

  1. Every secure FL-PQM protocol requires each intermediate node on the path to have some shared secret information (e.g., keys).
  2. If secure FL-PQM protocol exist then so do one-way functions.
  3. Every black-box construction of a FL-PQM protocol from a random oracle that securely localizes every packet and adds at most O(log n) messages overhead per packet requires each intermediate node to invoke the oracle. These results show that implementing FL-PQM requires active cooperation (i.e., maintaining keys and agreeing on, and performing, cryptographic protocols) from all of the intermediate nodes along the path. This may be problematic in the Internet, where links operate at extremely high speeds, and intermediate nodes are owned by competing business entities with little incentive to cooperate.
  x

  @inproceedings{BGX08,
  author = {Boaz Barak and Sharon Goldberg and David Xiao},
  title = {Protocols and Lower Bounds for Secure Failure Localization on the Internet},
  booktitle = {Proc. EUROCRYPT '08},
  pages = {341--360},
  year = {2008}
  }

Graph theory

• "The Evolution of Expander Graphs " [Abs, Bib,PS, PDF]
  D. Xiao, AB thesis, Harvard College 2003
  x

  This thesis has two goals. First, we present an introduction to the line of work that began with the study of expander graphs in the non-constructive setting, which then led to the algebraic con- struction of expanders, and finally has recently produced combinatorial constructions. Second, we extend the work on combinatorial constructions by new analyses and new constructions.

  x

  @thesis{Xiao03,
  author = "David Xiao",
  title = "The Evolution of Expander Graphs",
  institution = "Harvard University",
  year = "2003"
  }

Miscellaneous

• "Estimating and comparing entropy across written natural languages using PPM compression", [Abs, Bib,PS, PDF]
  F. Behr, V. Fossum, M. Mitzenmacher, D. Xiao, Data Compression Conference 2003
  x

  Previous work on estimating the entropy of written natural language has focused primarily on English. We expand this work by considering other natural languages, including Arabic, Chinese, French, Greek, Japanese, Korean, Russian, and Spanish. We present the results of PPM compression on machine-generated and human-generated translations of texts in various languages.

  Under the assumption that languages are equally expressive, and that PPM compression does well across languages, one would expect that translated documents would compress to approximately the same size. We verify this empirically on a novel corpus of translated documents. We suggest as an application of this finding using the size of compressed natural language texts as a mean of automatically testing translation quality.

  x

  @inproceedings{BFMX03,
  author = "F. Behr and V. Fossum and M. Mitzenmacher and D. Xiao",
  title = "Estimating and comparing entropy across written natural languages using PPM compression",
  booktitle = "Proc. DCC '03",
  year = "2003",
  pages = "416"
  }