The Clifford hierarchy $\mathcal{C}_1 \subset \mathcal{C}_2 \subset \cdots$ was introduced by Gottesman and Chuang (Nature 402, 1999) to characterize gates that admit fault-tolerant implementation by gate teleportation. Yet, despite its rich mathematical structure and the attention it has received in recent years, little is known about $\mathcal{C}_k$ for $k > 3$. Most progress has focused on identifying structural properties of restrictions of the hierarchy, such as diagonal gates and gates on systems of small dimension $d$ or with few qudits.

The generalized semi-Clifford conjecture, proposed by Zeng et al. (Phys. Rev. A 77, 2008), states that every gate in $\cup_k \mathcal{C}_k$ is, up to multiplication by Cliffords, the product of a permutation and a diagonal matrix. Beigi and Shor proved the case $d=2$, $k=3$ (Quantum Inf. Comput. 10, 2010) and Pllaha et al. found an alternative proof by exploiting fixed points of the conjugation map induced by (a Clifford correction of) $U \in \mathcal{C}_3$ on the span of maximal stabilizer subgroups (Quantum 4, 2020). By extending their fixed-point arguments to the group $\Gamma_1(U)$ generated by $U \mathcal{P} U^\dagger$ and beyond, we prove the conjecture for $k \leq 4$ and any prime dimension $d$.

Our proof centers on conjugation groups $\Gamma_1(U), \Gamma_2(U), \ldots$ of $U \in \mathcal{C}_k$, which we expect to be a useful tool in the study of the Clifford hierarchy more generally. We also show a natural sufficient condition on such groups for gates in higher levels to be generalized semi-Clifford.

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the BCS transformation is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding.

Prior work established the post-quantum security of Kilian’s succinct interactive argument, a special case of the BCS transformation for one-message IOPs (i.e., PCPs). That analysis is inherently limited to one message because the reduction, like all prior quantum rewinding reductions, aims to extract classical information (a PCP string) from the quantum argument adversary. Our reduction overcomes this limitation by instead extracting a quantum algorithm that implements an IOP adversary; representing such an adversary classically may in general require exponential complexity.

Along the way we define collapse position binding, which we propose as the “correct” definition of collapse binding for vector commitment schemes, eliminating shortcomings of prior definitions.

As an application of our results, we obtain post-quantum secure succinct arguments, in the standard model (no oracles), with the best asymptotic complexity known.

Sigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr’s protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of Schnorr’s protocol in the standard model is not fully understood.

In this paper we study Kilian’s protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian’s protocol is proved secure via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr’s protocol, a precise understanding of the security of Kilian’s protocol remains elusive. We contribute new insights via upper bounds and lower bounds.

• Upper bounds. We establish the tightest known bounds on the security of Kilian’s protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian’s protocol.

• Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian’s protocol would imply improving the security analysis of Schnorr’s protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian’s protocol.

We initiate the study of zero-knowledge proofs for data streams. Streaming interactive proofs (SIPs) are well-studied protocols whereby a space-bounded algorithm with one-pass access to a massive stream of data communicates with a powerful but untrusted prover to verify a computation that requires large space.

We define the notion of zero-knowledge in the streaming setting and construct zero-knowledge SIPs for the two main building blocks in the streaming interactive proofs literature: the sumcheck and polynomial evaluation protocols. To the best of our knowledge all known streaming interactive proofs are based on either of these tools, and indeed, this allows us to obtain zero-knowledge SIPs for many central streaming problems, such as index, frequency moments, and inner product. Our protocols are efficient in terms of time and space, as well as communication: the space complexity is $\mathrm{polylog}(n)$ and, after a non-interactive setup that uses a random string of near-linear length, the remaining parameters are $n^{o(1)}$.

En route, we develop a toolkit for designing zero knowledge data stream protocols that may be of independent interest, consisting of a homomorphic streaming commitment protocol and a temporal commitment protocol. The analysis of our protocols relies on delicate information-theoretic arguments and reductions from average-case communication complexity.

Collapse binding and collapsing were proposed by Unruh (Eurocrypt ‘16) as post-quantum strengthenings of computational binding and collision resistance, respectively. These notions have been very successful in facilitating the “lifting” of classical security proofs to the quantum setting. A basic and natural question remains unanswered, however: are they the weakest notions that suffice for such lifting?

In this work we answer this question in the affirmative by giving a classical commit-and-open protocol which is post-quantum secure if and only if the commitment scheme (resp. hash function) used is collapse binding (resp. collapsing). We also generalise the definition of collapse binding to mph{quantum commitment schemes}, and prove that the equivalence carries over even when the sender in the commit-and-open protocol above communicates quantum information.

This establishes that a variety of “weak” binding notions (sum binding, CDMS binding and unequivocality) are in fact equivalent to collapse binding, both for post-quantum and quantum commitments.

Finally, we establish a “win-win” result, showing that a post-quantum computationally binding commitment scheme that is not collapse binding can be used to build an equivocal commitment scheme (which can, in turn, be used to build one-shot signatures and other useful quantum primitives). This strengthens a result due to Zhandry (Eurocrypt ‘19) showing that the same object yields quantum lightning.

We initiate the systematic study of QMA algorithms in the setting of property testing, to which we refer as QMA proofs of proximity (QMAPs). These are quantum query algorithms that receive explicit access to a sublinear-size untrusted proof and are required to accept inputs having a property $\Pi$ and reject inputs that are $\varepsilon$-far from $\Pi$, while only probing a minuscule portion of their input.

Our algorithmic results include a general-purpose theorem that enables quantum speedups for testing an expressive class of properties, namely, those that are succinctly decomposable. Furthermore, we show quantum speedups for properties that lie outside of this family, such as graph bipartitneness.

We also investigate the complexity landscape of this model, showing that QMAPs can be exponentially stronger than both classical proofs of proximity and quantum testers. To this end, we extend the methodology of Blais, Brody and Matulef (Computational Complexity, 2012) to prove quantum property testing lower bounds via reductions from communication complexity, thereby resolving a problem raised by Montanaro and de Wolf (Theory of Computing, 2016).

We prove a general structural theorem for a wide family of local algorithms, which includes property testers, local decoders, and PCPs of proximity. Namely, we show that the structure of every algorithm that makes $q$ adaptive queries and satisfies a natural robustness condition admits a sample-based algorithm with $n^{1- 1/O(q^2 \log^2 q)}$ sample complexity, following the definition of Goldreich and Ron (TOCT 2016). We prove that this transformation is nearly optimal. Our theorem also admits a scheme for constructing privacy-preserving local algorithms.

Using the unified view that our structural theorem provides, we obtain results regarding various types of local algorithms, including the following.

• We strengthen the state-of-the-art lower bound for relaxed locally decodable codes, obtaining an exponential improvement on the dependency in query complexity; this resolves an open problem raised by Gur and Lachish (SODA 2020).

• We show that any (constant-query) testable property admits a sample-based tester with sublinear sample complexity; this resolves a problem left open in a work of Fischer, Lachish, and Vasudev (FOCS 2015) by extending their main result to adaptive testers.

• We prove that the known separation between proofs of proximity and testers is essentially maximal; this resolves a problem left open by Gur and Rothblum (ECCC 2013, Computational Complexity 2018) regarding sublinear-time delegation of computation.

Our techniques strongly rely on relaxed sunflower lemmas and the Hajnal–Szemerédi theorem.

Contemporary staged performances frequently utilize advanced lighting and projection techniques. The design and creation of these stage effects are rarely accessible to actual performers and must be designed by professional lighting designers or highly-paid programmers. With MotionDraw we want to create an affordable system that is easily controlled and manipulated by performers. With intuitive gestures, non-specialized users can control the MotionDraw visual library and interact with the captured visual record of their own movements. Possible uses of our system grew out of research with dancers and performers, and the current technical implementation sets a framework for including additional visual libraries and capabilities.