Jack Doerner, Yashvanth Kondi, Eysa Lee, Abhi Shelat
Cryptocurrency applications have spurred a resurgence of interest in the computation of ECDSA signatures using threshold protocols---that is, protocols in which the signing key is secret-shared among n parties, of which any subset of size t must interact in order to compute a signature. Among the resulting works to date, that of Doerner et al. requires the most natural assumptions while also achieving the best practical signing speed. It is, however, limited to the setting in which the threshold is two. We propose an extension of their scheme to arbitrary thresholds, and prove it secure against a malicious adversary corrupting up to one party less than the threshold under only the Computational Diffie-Hellman assumption in the Random Oracle model, an assumption strictly weaker than those under which ECDSA is proven. Whereas the best current schemes for threshold-two ECDSA signing use a Diffie-Hellman Key Exchange to calculate each signature's nonce, a direct adaptation of this technique to a larger threshold t would incur a round count linear in t; thus we abandon it in favor of a new mechanism that yields a protocol requiring log(t)+6 rounds in total. We design a new consistency check, similar in spirit to that of Doerner et al., but suitable for an arbitrary number of participants, and we optimize the underlying two-party multiplication protocol on which our scheme is based, reducing its concrete communication and computation costs. We implement our scheme and evaluate it among groups of up to 256 of co-located and 128 geographically-distributed parties, and among small groups of embedded devices. We find that in the LAN setting, our scheme outperforms all prior works by orders of magnitude, and that it is efficient enough for use even on smartphones or hardware tokens. In the WAN setting we find that, despite its logarithmic round count, our protocol outperforms the best constant-round protocols in realistic scenarios.
The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post‐quantum world. To this end, the authors study the witness indistinguishability (WI) and witness hiding (WH) of proof systems against quantum adversaries. They give formal definitions of quantum WI (QWI) and quantum WH (QWH), present proof systems satisfying these definitions, and specify a condition under which QWI implies QWH. Regarding the non‐interactive proof systems, they prove that, even if a common reference string is used to generate polynomially many non‐interactive proofs, the QWI is still preserved, while quantum zero‐knowledge has no such beneficial property. To show the strength of QWI, they present two applications of them. First, they prove that the construction proposed by Feige et al . that transforms any non‐interactive bounded zero‐knowledge proof system to a general one is also feasible against quantum adversaries. Second, they construct a quantum‐secure signature scheme in the CRS model, which is existentially unforgeable against quantum adversaries and remains secure even if a common random string is used to sign polynomially many messages.
Eli Ben‐Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space U is δ-far in relative Hamming distance from a linear code V - this is the worst-case assumption - then most elements of U are almost-δ-far from V - this is the average case. However, this result was known to hold only below the "double Johnson" function of the relative distance δ_V of the code V, i.e., only when δ < 1-(1-δ_V)^(1/4). First, we increase the soundness-bound to the "one-and-a-half Johnson" function of δ_V and show that the average distance of U from V is nearly δ for any worst-case distance δ smaller than 1-(1-δ_V)^(1/3). This bound is tight, which is somewhat surprising because the one-and-a-half Johnson function is unfamiliar in the literature on error correcting codes. To improve soundness further for Reed Solomon codes we sample outside the box. We suggest a new protocol in which the verifier samples a single point z outside the box D on which codewords are evaluated, and asks the prover for the value at z of the interpolating polynomial of a random element of U. Intuitively, the answer provided by the prover "forces" it to choose one codeword from a list of "pretenders" that are close to U. We call this technique Domain Extending for Eliminating Pretenders (DEEP). The DEEP method improves the soundness of the worst-case-to-average-case reduction for RS codes up their list decoding radius. This radius is bounded from below by the Johnson bound, implying average distance is approximately δ for all δ < 1-(1-δ_V)^(1/2). Under a plausible conjecture about the list decoding radius of Reed-Solomon codes, average distance from V is approximately δ for all δ. The DEEP technique can be generalized to all linear codes, giving improved reductions for capacity-achieving list-decodable codes. Finally, we use the DEEP technique to devise two new protocols: - An Interactive Oracle Proof of Proximity (IOPP) for RS codes, called DEEP-FRI. The soundness of the protocol improves upon that of the FRI protocol of [Ben-Sasson et al., ICALP 2018] while retaining linear arithmetic proving complexity and logarithmic verifier arithmetic complexity. - An Interactive Oracle Proof (IOP) for the Algebraic Linking IOP (ALI) protocol used to construct zero knowledge scalable transparent arguments of knowledge (ZK-STARKs) in [Ben-Sasson et al., eprint 2018]. The new protocol, called DEEP-ALI, improves soundness of this crucial step from a small constant < 1/8 to a constant arbitrarily close to 1.
Zero-knowledge and multi-prover systems are both central notions in classical and quantum complexity theory. There is, however, little research in quantum multi-prover zero-knowledge systems. This paper studies complexity-theoretical aspects of the quantum multi-prover zero-knowledge systems. This paper has two results: 1.QMIP* systems with honest zero-knowledge can be converted into general zero-knowledge systems without any assumptions. 2.QMIP* has computational quantum zero-knowledge systems if a natural computational conjecture holds. One of the main tools is a test (called the GHZ test) that uses GHZ states shared by the provers, which prevents the verifier's attack in the above two results. Another main tool is what we call the Local Hamiltonian based Interactive protocol (LHI protocol). The LHI protocol makes previous research for Local Hamiltonians applicable to check the history state of interactive proofs, and we then apply Broadbent et al.'s zero-knowledge protocol for QMA \cite{BJSW} to quantum multi-prover systems in order to obtain the second result.
We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).
We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is $\mathrm{NP}$-complete to decide whether the classical value of a non-local game is 1 or $1- ε$. Furthermore, as long as $ε$ is small enough, this result does not depend on the gap $ε$. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap $ε$ decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of $\mathrm{MIP}^{co}(2,1,1,s)$ (proofs with two provers, one round, completeness probability $1$, soundness probability $s$, and commuting-operator strategies) can increase without bound as the gap $1-s$ gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class $\mathrm{PZK}$-$\mathrm{MIP}^{co}_δ(2,1,1,s)$ of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap $1-s$ gets arbitrarily small. While we do not know any computable time upper bound on the class $\mathrm{MIP}^{co}$, a result of the first author and Vidick shows that for $s = 1-1/\text{poly}(f(n))$ and $δ= 1/\text{poly}(f(n))$, the class $\mathrm{MIP}^{co}_δ(2,1,1,s)$, with constant communication from the provers, is contained in $\mathrm{TIME}(\exp(\text{poly}(f(n))))$. We give a lower bound of $\mathrm{coNTIME}(f(n))$ (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis.
The focus of this thesis is twofold: on one hand we study the query complexity of equilibrium computation in games, and on the other hand, we use equilibrium concepts from game theory as a tool to understand miner incentives in Bitcoin. In terms of query complexity, we mostly focus on algorithms that have access to utility queries in large games and best response queries in bimatrix games. For the former, we demonstrate query-efficient completely uncoupled dynamics that achieve non-trivial approximate equilibria. For the latter, we reduce the problem of query-efficient approximate equilibrium computation to a natural geometric learning problem: approximately learning partitions of an 𝑛-dimensional simplex into disjoint convex polytopes via membership queries. Given this reduction we show query-efficient algorithms for the geometric problem, and ultimately provide an algorithm for computing e-well-supported Nash equilibria in 𝑚×𝑛 bimatrix games with a query cost that is polynomial in log(1/e)and max(𝑚,𝑛) provided that min(𝑚,𝑛) is constant.This leads to a polynomial query complexity algorithm for 2-player games,provided that one of the players has a constant number of strategies. As for incentives in Bitcoin, we shed some light into how robust honest mining protocols are to the presence of strategic agents. Our focus is on the strategic aspects of both solo mining and pool mining in Bitcoin. For the former, we take a multiplayer approach and exhibit specific strategy profiles of multiple strategic miners that outperform honest mining, even if said miners would not be incentivised to be dishonest individually. This effectively renders the Bitcoin protocol less secure than previously thought. As for the latter, we propose a new mining pool protocol that is a randomised variant of the already-ubiquitous pay-per-last-N-shares (PPLNS) mining pool scheme in Bitcoin. Our pool protocol, randomised pay-per-last-N-shares (RPPLNS),enjoys the same desirable properties of PPLNS, but with the added benefit of an exponentially reduced state space required to maintain the protocol. More importantly, this reduced state space also allows us to prove robust guarantees against a richer class of strategic pool mining than before.
Compact multisignature is vital for shrinking the signature size of decentralized blockchain. All practical compact multisignature schemes have been constructed from the discrete logarithm problem which is potentially vulnerable to quantum computing attacks. Lattice-based multisignature schemes are potential candidates for resisting quantum attacks. However, the existing lattice-based multisignature schemes suffer either loose signatures or large public key and signature sizes after compressing, which makes them unsuitable for blockchains. In this paper, we first present a practical lattice-based multisignature scheme with much smaller signature sizes than previous lattice-based multisignature schemes. Then, we extend our scheme to support public key aggregation with almost the same performance. Both of our multisignature schemes are provably secure in the random oracle model under the ring version of the short integer solution (Ring-SIS) assumption. They outperform the recent lattice-based multisignature scheme proposed by Bansarkhani and Sturm (BS) in terms of both signature size and communication overhead.
We define a new query measure we call quantum distinguishing complexity, denoted QD(f) for a Boolean function f. Unlike a quantum query algorithm, which must output a state close to |0> on a 0-input and a state close to |1> on a 1-input, a "quantum distinguishing algorithm" can output any state, as long as the output states for any 0-input and 1-input are distinguishable. \nUsing this measure, we establish a new relationship in query complexity: For all total functions f, Q_0(f)=O~(Q(f)^5), where Q_0(f) and Q(f) denote the zero-error and bounded-error quantum query complexity of f respectively, improving on the previously known sixth power relationship. \nWe also define a query measure based on quantum statistical zero-knowledge proofs, QSZK(f), which is at most Q(f). We show that QD(f) in fact lower bounds QSZK(f) and not just Q(f). QD(f) also upper bounds the (positive-weights) adversary bound, which yields the following relationships for all f: Q(f) >= QSZK(f) >= QD(f) = Omega(Adv(f)). This sheds some light on why the adversary bound proves suboptimal bounds for problems like Collision and Set Equality, which have low QSZK complexity. \nLastly, we show implications for lifting theorems in communication complexity. We show that a general lifting theorem for either zero-error quantum query complexity or for QSZK would imply a general lifting theorem for bounded-error quantum query complexity.
This project was focused on designing a tool for optimizing complex transactions in a traditional bank accounts, Bitcoin wallet accounts and Bitcoin exchanges. The challenges include transference fees eroding the amounts transferred, Bitcoin volatility and arbitrage. The tool should support hundreds of accounts with each account identifi ed by a bank or exchange, and a currency. The basic user-case, we call it Debit Scenario, appears when an account consumes it capital and has very little funding (sink or demand account), then the user set a minimum funding for the account, and we need to balance all the accounts of the network, using many currency circulations though many paths to satisfy the specifi ed funding limits. Another user case, we called it Custodian Scenario, is when certain accounts (i.e. supply or non-custodians) has upper limit on the amount of capital so we need to distribute the excess value in other accounts (i.e. demand or custodians) of the network. The problem was modelled as a multi-commodity min-cost max- flow problem with specifi c constraints including arbitrage information, and solved with linear programming. Simple and complex numerical scenarios are presented too.
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP , as long as one is willing to make a suitable physical assumption : if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP * model captures this setting. In this work, we study the following question: Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP * . Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP * model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
This paper investigates the power of quantum statistical zero knowledge interactive proof systems in the relativized setting. We prove the existence of an oracle relative to which quantum statistical zero-knowledge does not contain UP intersect coUP, and we prove that quantum statistical zero knowledge does not contain UP relative to a random oracle with probability 1. Our proofs of these statements rely on a bound on output state discrimination for relativized quantum circuits based on the quantum adversary method of Ambainis, following a technique similar to one used by Ben-David and Kothari to prove limitations on a query complexity variant of quantum statistical zero-knowledge.
Since the seminal paper on Fully Homomorphic Encryption (FHE) by Gentry in 2009, a lot of work and improvements have been proposed, with an amazing number of possible applications. It allows outsourcing any kind of computations on encrypted data, and thus without leaking any information to the provider who performs the computations. This is quite useful for many sensitive data (finance, medical, etc.).
In this paper, we propose a zero-knowledge proof for a special case of the hidden subset sum problem. This problem was presented by [Boyko et al. 1998] as the underlying problem of methods for generating random pairs of the form (x, gx (mod p)) using precomputations. The proof we propose is an adaptation of a zero-knowledge protocol for the subset sum problem presented by [Blocki 2009].
We consider a problem we call StateIsomorphism: given two quantum states of n qubits, can one be obtained from the other by rearranging the qubit subsystems? Our main goal is to study the complexity of this problem, which is a natural quantum generalisation of the problem StringIsomorphism. We show that StateIsomorphism is at least as hard as GraphIsomorphism, and show that these problems have a similar structure by presenting evidence to suggest that StateIsomorphism is an intermediate problem for QCMA. In particular, we show that the complement of the problem, StateNonIsomorphism, has a two message quantum interactive proof system, and that this proof system can be made statistical zero-knowledge. We consider also StabilizerStateIsomorphism (SSI) and MixedStateIsomorphism (MSI), showing that the complement of SSI has a quantum interactive proof system that uses classical communication only, and that MSI is QSZK-hard.
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner
Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure. In this work, we develop algebraic techniques for obtaining zero knowledge variants of proof protocols in a way that leverages and preserves their algebraic structure. Our constructions achieve unconditional (perfect) zero knowledge in the Interactive Probabilistically Checkable Proof (IPCP) model of Kalai and Raz [KR08] (the prover first sends a PCP oracle, then the prover and verifier engage in an Interactive Proof in which the verifier may query the PCP). Our main result is a zero knowledge variant of the sumcheck protocol [LFKN92] in the IPCP model. The sumcheck protocol is a key building block in many IPs, including the protocol for polynomial-space computation due to Shamir [Sha92], and the protocol for parallel computation due to Goldwasser, Kalai, and Rothblum [GKR15]. A core component of our result is an algebraic commitment scheme, whose hiding property is guaranteed by algebraic query complexity lower bounds [AW09,JKRS09]. This commitment scheme can then be used to considerably strengthen our previous work [BCFGRS16] that gives a sumcheck protocol with much weaker zero knowledge guarantees, itself using algebraic techniques based on algorithms for polynomial identity testing [RS05,BW04]. We demonstrate the applicability of our techniques by deriving zero knowledge variants of well-known protocols based on algebraic techniques, including the protocols of Shamir and of Goldwasser, Kalai, and Rothblum, as well as the protocol of Babai, Fortnow, and Lund [BFL91].
We demonstrate that the Bitcoin Script language allows not only for primitive recursion, but in the deployment of an Ackerman function and hence the ability to simply recurse in Bitcoin script, we show that the script system is Turing complete. From this, we introduce a new class of Turing Machine, the PTTM or probabilistic Total Turing machine and note that Bitcoin acts as a decider or Total Turing Machine which allows us to find a NIZKPoK that can act as a TM based verifier to a Non-Interactive Proof that is run on an external and non-associated TM as a proof system. Bitcoin can extend to securely offer contracts such as best fit solutions to common logistic systems and optimisation problems including the Travelling Salesman class of problems and to the optimisation of systems. This can be offered as an open or time bound contract that guarantees payment and can be solved which allowing Pseudonymity of the bidder.