No-signalling (NOSIG) correlations, that are stronger than those allowed by quantum entanglement yet do not violate relativistic causality, are a valuable resource for understanding information processing systems. Such correlations can be achieved between non-communicating players in games when the players use what is called non-local strategies, and can give the players better odds at winning in these games. We propose definitions for non-local strategies in relativistic multi-player non-local games. We prove a conjecture by Crépeau stating that any non-local strategy that can be simultaneously produced by any pi-signalling strategy in a multi-player non-local game, has to be a NOSIG strategy. Pi-signalling strategies are achieved when 1-way signalling is allowed between players arranged on a line defined by some permutation. This result gives us a better understanding of how NOSIG strategies fit with the other non-local strategies, and can help in constructing novel NOSIG multi-player strategies and help prove they produce NOSIG correlations. Finally, we extend the definition of zero-knowledge proof systems to the relativistic multi-prover, multi-verifier setting, and propose definitions for what it means for a non-local strategy to have polynomial time complexity
The HighGear protocol (Eurocrypt 2018) is the fastest currently known approach to preprocessing for the SPDZ Multi-Party Computation scheme. Its backbone is formed by an Ideal Lattice-based Somewhat Homomorphic Encryption Scheme and accompanying Zero-Knowledge proofs. Unfortunately, due to certain characteristics of HighGear such current implementations limit the security parameters in a number of places. This is mainly due to memory and bandwidth consumption constraints. In this work we present a new approach to the ZKPoKs for the SPDZ Multi-Party Computation scheme. We rigorously formalize the original approach of HighGear and show how to improve upon it using a different proof strategy. This allows us to increase the security of the underlying protocols, whilst simultaneously also increasing the performance in terms of memory and bandwidth consumption as well as overall throughput of the SPDZ offline phase.
Bitcoinin julkaisu merkitsi samalla lohkoketjusovellusten syntymää. Johtuen muun muassa julkisen todennettavuuden tarpeesta, lohkoketjussa säilytettävä tieto on tyypillisesti läpinäkyvää, joka voi olla ongelmallista yksityisyyden kannalta. Yksityisyyden parantamiseksi on kehitetty menetelmiä, jotka hämärtävät lohkoketjun tietojen läpinäkyvyyttä säilyttäen niiden eheyden ja todennettavuuden. Lupaava kryptografinen menetelmä tähän tarkoitukseen on nollatietotodistus, joka mahdollistaa väitteen todistamisen siten, että ainoa todistuksessa paljastuva tieto on väitteen totuusarvo. \n \nNollatietotodistuksiin perehtyminen aloitetaan niiden teoreettisesta perustasta. Lohkoketjujen kannalta tärkeitä vaatimuksia nollatietotodistuksille ovat ei-interaktiivisuus ja ytimekkyys, ja nämä ehdot täyttäviä todistusrakenteita kutsutaan yleisesti nimellä zk-SNARK. Fiat-Shamir muunnos on käyttökelpoinen menetelmä ei-interaktiivisen nollatietotodistuksen muodostamiseen tapauksissa, joissa ytimekkyys ei ole tärkeää. Nollatietotodistusten käyttöä tutkitaan erityisesti yksityisyyden ja käyttökelpoisuuden kannalta kolmessa lohkoketjusovelluksessa, jotka ovat Zcash, Ethereum ja Monero.
Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.
Zero-knowledge proofs have always provided a clear solution when it comes to conveying information from a prover to a verifier or vice versa without revealing essential information about the process. Advancements in zero-knowledge have helped develop proofs which are succinct and provide non-interactive arguments of knowledge along with maintaining the zero-knowledge criteria. zk-SNARKs (Zero knowledge Succinct Non-Interactive Argument of Knowledge) are one such method that outshines itself when it comes to advancement of zero-knowledge proofs. The underlying principle of the Zcash algorithm is such that it delivers a full-fledged ledger-based digital currency with strong privacy guarantees and the root of ensuring privacy lies fully on the construction of a proper zk-SNARK. In this paper we elaborate and construct a concrete zk-SNARK proof from scratch and explain its role in the Zcash algorithm.
In a recent seminal work, Bitansky and Shmueli (STOC '20) gave the first construction of a constant round zero-knowledge argument for NP secure against quantum attacks. However, their construction has several drawbacks compared to the classical counterparts. Specifically, their construction only achieves computational soundness, requires strong assumptions of quantum hardness of learning with errors (QLWE assumption) and the existence of quantum fully homomorphic encryption (QFHE), and relies on non-black-box simulation. In this paper, we resolve these issues at the cost of weakening the notion of zero-knowledge to what is called $\epsilon$-zero-knowledge. Concretely, we construct the following protocols:
- We construct a constant round interactive proof for NP that satisfies statistical soundness and black-box $\epsilon$-zero-knowledge against quantum attacks assuming the existence of collapsing hash functions, which is a quantum counterpart of collision-resistant hash functions. Interestingly, this construction is just an adapted version of the classical protocol by Goldreich and Kahan (JoC '96) though the proof of $\epsilon$-zero-knowledge property against quantum adversaries requires novel ideas.
- We construct a constant round interactive argument for NP that satisfies computational soundness and black-box $\epsilon$-zero-knowledge against quantum attacks only assuming the existence of post-quantum one-way functions.
At the heart of our results is a new quantum rewinding technique that enables a simulator to extract a committed message of a malicious verifier while simulating verifier's internal state in an appropriate sense.
We put forth a new framework for building pairing-based non-interactive zero-knowledge (\(\mathsf {NIZK}\)) arguments for a wide class of algebraic languages, which are an extension of linear languages, containing disjunctions of linear languages and more. Our approach differs from the Groth-Sahai methodology, in that we rely on pairings to compile a \(\varSigma \)-protocol into a \(\mathsf {NIZK}\). Our framework enjoys a number of interesting features:
conceptual simplicity, parameters derive from the \(\varSigma \)-protocol;
proofs as short as resulting from the Fiat-Shamir heuristic applied to the underlying \(\varSigma \)-protocol;
fully adaptive soundness and perfect zero-knowledge in the common random string model with a single random group element as CRS;
yields simple and efficient two-round, public coin, publicly-verifiable perfect witness-indistinguishable (WI) arguments(ZAPs) in the plain model. To our knowledge, this is the first construction of two-rounds statistical witness-indistinguishable arguments from pairing assumptions.
Muhammed F. Esgin, Ngoc Khanh Nguyen, Gregor Seiler
We propose a very fast lattice-based zero-knowledge proof system for exactly proving knowledge of a ternary solution \(\vec {s} \in \{-1,0,1\}^n\) to a linear equation \(A\vec {s}=\vec {u}\) over \(\mathbb {Z}_q\), which improves upon the protocol by Bootle, Lyubashevsky and Seiler (CRYPTO 2019) by producing proofs that are shorter by a factor of 8.
We survey the state-of-the-art non-interactive zero-knowledge argument schemes and their applications in confidential transactions and private smart contracts on blockchain. The main goal of this paper is to serve as a reference for blockchain application developers in finding the most suitable scheme for a particular use case. We give an overview and compare the state-of-the-art protocols for confidential transactions and private smart contracts regarding the protection of the transaction graph and amounts, data and functionality. However, our main focus is on state-of-the-art zero-knowledge argument schemes. We briefly describe their backgrounds, proof lengths and computational complexities and discuss their cryptographic security models. Our focus is on seminal, otherwise notable and, especially, implemented methods that are ready to be applied in practice. We also survey the existing implementations of transforming computations into circuit representations required by those methods. We note that the existing schemes have different strengths and drawbacks regarding usability, setup, proof length and proving and verification costs.
As a kind of point-to-point distributed public ledger technology, blockchain has been widely concerned in recent years. The privacy protection of blockchain technology has always been the core issue of people's attention. In this paper, some existing solutions to the current problems of user identity and transaction privacy protection are surveyed, including coin mixing mechanism, zero knowledge proof, ring signature and other technologies. Secondly, five typical applications of privacy protection technology based on blockchain are proposed and analyzed, which are mainly divided into technology applications based on coin mixing protocol, encryption protocol, secure channel protocol and so on. Finally, in view of the shortages of the existing blockchain privacy protection technology, we explore future research challenges that need to be studied in order to preserve privacy in blockchain system, and looks forward to the future development direction.