We formalize security properties of zero-knowledge protocols and their proofs in EasyCrypt. Specifically, we focus on sigma protocols (three-round protocols). Most importantly, we also cover properties whose security proofs require the use of rewinding; prior work has focused on properties that do not need this more advanced technique. On our way we give generic definitions of the main properties associated with sigma protocols, both in the computational and information-theoretical setting. We give generic derivations of soundness, (malicious-verifier) zero-knowledge, and proof of knowledge from simpler assumptions with proofs which rely on rewinding. Also, we address sequential composition of sigma protocols. Finally, we illustrate the applicability of our results on three zero-knowledge protocols: Fiat-Shamir (for quadratic residues), Schnorr (for discrete logarithms), and Blum (for Hamiltonian cycles, NP-complete).
Despite the great potential and flexibility of smart contract-enabled blockchains, building privacy-preserving applications using these platforms remains an open question. Existing solutions fall short since they ask end users to coordinate and perform the computation off-chain themselves. While such an approach reduces the burden of the miners of the system, it largely limits the ability of lightweight users to enjoy privacy since performing the actual computation on their own and attesting to its correctness is expensive even with state-of-the-art proof systems.To address this limitation, we propose smartFHE, a framework to support private smart contracts using fully homomorphic encryption (FHE). To the best of our knowledge, smartFHE is the first to use FHE in the blockchain model; moreover, it is the first to support arbitrary privacy-preserving applications for lightweight users under the same computation-on-demand model pioneered by Ethereum. smartFHE does not overload the user since miners are instead responsible for performing the private computation. This is achieved by employing FHE so miners can compute over encrypted data and account balances. Users are only responsible for proving well-formedness of their private inputs using efficient zero-knowledge proof systems (ZKPs). We formulate a notion for a privacy-preserving smart contract (PPSC) scheme and show a concrete instantiation of our smartFHE framework. We address challenges resulting from using FHE in the blockchain setting—including concurrency and dealing with leveled schemes. We also show how to choose suitable FHE and ZKP schemes to instantiate our framework, since naively choosing these will lead to poor performance in practice. We formally prove correctness and security of our construction. Finally, we conduct experiments to evaluate its efficiency, including comparisons with a state-of-the-art scheme and testing several private smart contract applications. We have open-sourced our (highly optimized) ZKP library, which could be of independent interest.
I discussed on zero trust and hybrid cloud with John Kindervag when he worked at Forrester Research around 2010. He asked why traditional security controls are not effective. He said that network segmentation I to static, and when the attacker is let inside the network segment, we are no longer tracking what resources the attacker is accessing. We need to change from “trust and verify” to “verify and then trust”. In this chapter, we will discuss that another security aspect is zero-knowledge proof, which means you actually are in possession of knowledge without sharing the secret. Zero trust and zero knowledge and how they are different. So, you can convince someone that you have a secret without disclosing the secret.
SNAP (Standar Nasional OPEN API Pembayaran) is an implementation of open banking for encouraging digital transformation in the banking industry. SNAP was submitted by several sub-working groups formed jointly by ASPI and the Bank of Indonesia. In the document Pedoman Tata Kelola (Bank of Indonesia, n.d.), there is already a customer data protection mechanism between the bank, the owner of Open API, and the user of Open API. However, there is no data protection process carried out by consumers so third parties, that use the Open API of the bank, do not need to know the customer's data. Based on the web3 protocol, users can store data and transmit only in encrypted form which can only be opened by calculating the data with a pre-agreed smart contract. Banks can work like a decentralized network on web3, where the process of calculating proof and witness is carried out by the bank. Proof and witness are calculated using a zero-knowledge proof protocol, making it difficult to duplicate. For this reason, we propose a new architecture using smart contracts between banks and customers using the ZK-SNARK method. Therefore, there is no significant performance difference between using ZK-SNARK and without ZK-SNARK in the API call process.
Abner F. B. Costa, Henrique Hepp, Murilo V. G. da Silva, Leandro M. Zatesko
The Hidden Subgroup Problem (HSP) generalises many problems that are candidates to be NP-intermediate. It was shown that the decision version of HSP belongs to the zero-knowledge complexity class HVPZK and that, if the size of the group is known, it also belongs to NISZK. We show that whenever we can sample uniformly at random elements of the group and of a set, with the same size of the group, that contains the image of the function that hides the subgroup, the problem is in NIPZK1 (i.e. NIPZK with perfect completeness). As a second contribution, we show that NIPZK1 has a complete promise problem that is a restricted version of a complete promise problem for the NIPZK class.
The total number of solar power-producing facilities whose Feed-in Tariff (FIT) Program-based ten-year contracts will expire by 2023 is expected to reach approximately 1.65 million in Japan. If the facilities that produce or consume renewable energy would increase to reach a large number, e.g., two million, blockchain would not be capable of processing all the transactions. In this work, we propose a blockchain-based electricity-tracking platform for renewable energy, called ‘ZGridBC,’ which consists of mutually cooperative two novel decentralized schemes to solve scalability, storage cost, and privacy issues at the same time. One is the electricity production resource management, which is an efficient data management scheme that manages electricity production resources (EPRs) on the blockchain by using UTXO tokens extended to two-dimension (period and electricity amount) to prevent double-spending. The other is the electricity-tracking proof, which is a massive data aggregation scheme that significantly reduces the amount of data managed on the blockchain by using zero-knowledge proof (ZKP). Thereafter, we illustrate the architecture of ZGridBC, consider its scalability, security, and privacy, and illustrate the implementation of ZGridBC. Finally, we evaluate the scalability of ZGridBC, which handles two million electricity facilities with far less cost per environmental value compared with the price of the environmental value proposed by METI (=0.3 yen/kWh).
Robust subgroup multisignature allows any subgroup of signers from a global set to sign a given message on behalf of the whole group, and the individual signatures should be verified before the combination process, which resists poison signature attacks. An emerging application of robust subgroup multisignatures in blockchain is that a qualified subgroup of a global set of users has reached agreement. In the integrated blockchain and edge computing system, the edge server can naturally act as a combiner in multisignatures and help other end devices produce the final aggregate signature. In this paper, we propose a robust subgroup multisignature with one-time public keys in order that has two advantages for solving the signers ordering problem and one-time public key problem simultaneously. Our scheme is a nontrivial extension of Galindo et al.’s robust subgroup multisignature scheme and can be proven unforgeable, robust and chronological in random oracles. Our scheme can also be suitable for the consortium blockchain by adding a noninteractive zero-knowledge (NIZK) proof system for certifying the one-time public keys.
In classical planning, the aim is to find a sequence of deterministic actions leading from the initial to a goal state. In this work, we consider the scenario where a party who knows the solution to a planning task, called the prover, wants to convince a second party, the verifier, that it has the solution without revealing any information about the solution itself. This is relevant in domains where privacy is important, for example when plans contain sensitive information or when the solution should not be revealed upfront. We achieve this by introducing a zero-knowledge protocol for plan existence. By restricting ourselves to tasks with polynomially-bounded plan length, we are able to construct a protocol that can be run efficiently by both the prover and verifier. The resulting protocol does not rely on any reduction, has a constant number of rounds, and runs in time polynomial in the size of the task.
Liu Shenglong, Ge Zhang, Jiawei Jiang, Xin Zhou · 5 authors
With the application of new technologies such as Internet of Things and big data in smart grid industry, new power systems based on new energy sources have emerged in response to the call of “Peak carbon, carbon neutrality.” The power grid enterprise concentrates the data assets and business access to the data external service, which needs to connect a large number of data sources. Ensuring the authenticity of the data without tampering becomes a big challenge. The power system adopts the identity authentication mechanism to resist the security attack and protect the sensitive data. However, in the process of user authentication, the sending of real identity information will lead to the reduction of system privacy, which is easy to cause the leakage of sensitive data. This paper proposes an anonymous authentication mechanism based on zero-knowledge proof for power system, which authenticates the server without revealing the identity. This mechanism uses zero-knowledge proof algorithm to design an anonymous authentication protocol framework, which consists of three stages: registration, mutual authentication and revocation. In this method, anonymous certificate and elliptic curve encryption technology are used to realize the anonymity and authenticity of users. The mechanism effectively protects the user's real identity information and maintains the sensitive data in the power system.
Finding efficient signature schemes based on coding theory is an important issue for post-quantum cryptography. One can build signature schemes based on zero-knowledge proofs using the Stern protocol and its variants as demonstrated both in Hamming metric [1], [2] and rank metric [3], [4]. These constructions feature a high soundness error hence have a rather large signature size. Recently, some techniques based on secure Multi-Party Computation (MPC) have made it possible to lower this soundness error thus resulting in smaller signatures in both Hamming metric [5], [6] and rank metric [7], [8]. Even more recently, a hypercube-based approach has improved the Hamming metric approach [9]. In this paper, we adapt the idea of [9] to rank metric using the protocol from [8]. Given a fixed number of parties, this hypercube-based approach improves the performances of the underlying scheme. It is thus possible to consider additional trade-offs between sizes and performances thus reducing the signature size up to 4.5kB by increasing the number of parties of the MPC protocol.
John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba · 6 authors
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot easily be characterized using traditional complexity theory, which focuses on tasks with classical inputs and outputs. To study the complexity of such state transformation tasks, we introduce a framework for unitary synthesis problems, including notions of reductions and unitary complexity classes. We use this framework to study the complexity of transforming one entangled state into another via local operations. We formalize this as the Uhlmann Transformation Problem, an algorithmic version of Uhlmann's theorem. Then, we prove structural results relating the complexity of the Uhlmann Transformation Problem, polynomial space quantum computation, and zero knowledge protocols. The Uhlmann Transformation Problem allows us to characterize the complexity of a variety of tasks in quantum information processing, including decoding noisy quantum channels, breaking falsifiable quantum cryptographic assumptions, implementing optimal prover strategies in quantum interactive proofs, and decoding the Hawking radiation of black holes. Our framework for unitary complexity thus provides new avenues for studying the computational complexity of many natural quantum information processing tasks.
Modern cryptographic protocols such as zero-knowledge proofs and secure multi-party computation have increased the demand for a novel category of symmetric primitives. These primitives are not optimized for traditional platforms such as servers, microcontrollers, and desktop computers but rather for their ability to be implemented in arithmetic circuits. To enable efficient arithmetic operations, they define operations over larger finite fields and use low-degree invertible functions to construct their non-linear layers. Grendel is an arithmetization-oriented permutation that leverages the Legendre Symbol to enhance the growth of algebraic degrees in its non-linear layer. In this paper, we present a preimage attack on the sponge hash function instantiated with the full rounds of the Grendel permutation using algebraic methods. We introduce a technique that allows us to eliminate two full rounds of substitution permutation networks (SPN) in the sponge hash function with minimal or no additional cost. This method can be combined with univariate root-finding techniques and Gröbner basis attacks to break the number of rounds claimed by the designers. By utilizing this strategy, our attack achieves an improvement of two additional rounds compared to the previous state-of-the-art attack. While not breaking its security margin, it allows us to further understand the design and analysis of such cryptographic primitives.
Nguyễn Văn Nghị, Lại Thị Thu Vân, Hà Như Tuấn, Lê Minh Hiếu · 5 authors
Zero-Knowledge Proof (ZKP) - bằng chứng không lộ tri thức là một dạng kỹ thuật mật mã được công bố đầu tiên từ thập niên 90 của thế kỷ trước. Tuy nhiên, trong vòng 10 năm trở lại đây thì ZKP mới được ứng dụng phổ biến trong thực tế như: công nghệ Blockchain, hệ thống xác thực và kết hợp vào các thuật toán mật mã khác. Các lược đồ ZKP đang sử dụng này thì đa phần có cơ sở toán học trên trường hữu hạn có chi phí triển khai lớn và tốc độ chậm. Trong bài báo này, chúng tôi đề xuất một lược đồ ZKP kiểu Schnorr với cơ sở toán học dựa trên đường cong Elliptic. Mục tiêu giải pháp ZKP đề xuất trên Elliptic này có độ an toàn cao và hiệu năng tốt hơn so với lược đồ ZKP kiểu Schnorr trên trường hữu hạn, đồng thời có thêm một số cải tiến tốt hơn về mặt bảo mật so với các phiên ZKP kiểu Schnorr đã công bố khác trên đường cong Elliptic. Các kết quả này được lập luận dựa trên phương pháp nghiêncứu cơ sở lý thuyết toán học của các công trình đã công bố và thực nghiệm bằng ngôn ngữ lập trình python. Qua đó kết luận rằng đây là lược đồ ZKP rất có tiềm năng áp dụng vào thực tế trong các hệ thống xác thực và trong công nghệ Blockchain.
Federated learning can effectively alleviate the data privacy problem of the participants, but the parameters or gradients passed in the model training may still leak the private data of the participants. Worse, aggregation server may return fake aggregation results. Existing solutions either use complex cryptographic primitives such as zero-knowledge proofs, or require interaction among participants, causing them high computation or communication overhead. Therefore, this paper proposes a secure and verifiable federated learning (SVFL) scheme. Specifically, SVFL performs privacy protection by introducing noise that can be offset during the aggregation process, and utilizes linear homomorphic hash to verify the correctness of the aggregation results. Compared with existing schemes, SVFL hardly loses accuracy due to the introduced security mechanism, and has low computation and communication overhead. Experimental results show that the performance of SVFL is almost consistent with the original federated learning without any protection, which makes SVFL applicable to edge devices. The computation and communication overhead of SVFL does not increase with the number of participants, which makes SVFL applicable to high-concurrency scenarios.
A commitment scheme is a cryptographic tool that allows one to commit to a hidden value, with the option to open it later at requested places without revealing the secret itself. Commitment schemes have important applications in zero-knowledge proofs and secure multi-party computation, just to name a few. This survey introduces a few multivariate polynomial commitment schemes that are built from a variety of mathematical structures. We study how Orion is constructed using hash functions; Dory, Bulletproofs, and Vampire using the inner-product argument; Signatures of Correct Computation using polynomial factoring; DARK and Dew using groups of unknown order; and Orion+ using a CP-SNARK. For each protocol, we prove its completeness and state its security assumptions.
Lattice-based cryptography is one of the most promising candidates for designing post-quantum cryptographic algorithms that resist emerging quantum computing attacks. The recent NIST PQC standardization process is nearing its completion, with practical lattice-based algorithms for basic cryptographic functionalities (namely digital signature and public-key encryption) selected for standardization in the near future. However, practical lattice-based solutions for more advanced privacy-preserving protocols, in particular, Zero-Knowledge Proofs (ZKPs), have only emerged recently and are an active area of research. We discuss some recent developments in design and analysis of practical lattice-based post-quantum ZKPs and their applications. In particular, we review some challenges that arise in designing ZKPs in the lattice setting and some recent progress on efficient lattice-based Schnorr-like proofs for important relations, such as binary/range proofs, one-out-of-many proofs and rounding proofs [1, 2, 4]. We discuss applications and optimization of such proof systems as building blocks for practical advanced cryptographic protocols such as ring signatures and balance proofs for privacy-preserving cryptocurrency payment protocols [2, 3]. We also discuss our recent work on succinct designated-verifier ZKPs (DV-ZKSNARKS) for verifying correctness of general delegated computations [5].
Many existing anonymous parking payment schemes lack high efficiency and flexibility. For instance, the calculation and communication costs involved in payment may linearly increase with the payment amount. In this paper, we propose an anonymous payment system (dubbed AnoPay) for vehicle parking, which leverages updatable attribute-based anonymous credentials and efficient zero-knowledge proof (ZKP) to achieve user anonymity and constant overhead for parking fee payment. To further improve the efficiency, we design a secure parking fee aggregation protocol based on linear homomorphic encryption to aggregate parking transactions, where the amount of each parking transaction is hidden and the privacy of the parking lot in terms of its revenue is guaranteed. AnoPay achieves both unlinkability and accountability, malicious payments can be efficiently traced when it is necessary. We provide a security model and rigorous proof for each security property of AnoPay. Extensive experiments and comparisons demonstrate the efficiency and practicality of the system.
Blockchain technology promises a disruptive enhancement in trust establishment among supply chain actors. In particular, transparency and traceability can significantly get improved by a blockchain based data exchange platform which provides an immutable source of truth driven by a multi-stakeholder consensus. This also helps authenticate the provenance of products which is an added value that can be monetized by the supply chain participants. Nonetheless, due to the transparent nature of the blockchain, privacy and confidentiality are still a major concern for industries. In this paper, we present zk-BeSC, a blockchain enabled supply chain scheme based on zero-knowledge proofs of polynomials. The scheme allows transactions between supply chain participants in a privacy preserving fashion. It also offers tamper-resistance and replication due to the intrinsic nature of the blockchain. ZK-BeSC is fully implemented using an ethereum testnet and a web3 application. The scheme performs efficient proofs and has reduced gas consumption during verification.
Motivated by new applications such as secure Multi-Party Computation (MPC), Fully Homomorphic Encryption (FHE), and Zero-Knowledge proofs (ZK), many MPC-, FHE- and ZK-friendly symmetric-key primitives that minimize the< number of multiplications over Fp for a large prime p have been recently proposed in the literature. These symmetric primitives are usually defined via invertible functions, including (i) Feistel and Lai-Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes. However, the “invertibility” property is actually never required in any of the mentioned applications.In this paper, we discuss the possibility to set up MPC-/FHE-/ZK-friendly symmetric primitives instantiated with non-invertible bounded surjective functions. In contrast to one-to-one functions, each output of a l-bounded surjective function admits at most l pre-images. The simplest example is the square map x → x2 over Fp for a prime p ≥ 3, which is (obviously) 2-bounded surjective. When working over Fnp for n ≥ 2, we set up bounded surjective functions by re-considering the recent results proposed by Grassi, Onofri, Pedicini and Sozzi at FSE/ToSC 2022 as starting points. Given a quadratic local map F : Fmp → Fp for m ∈ {1, 2, 3}, they proved that the shift-invariant non-linear function over Fnp defined as SF (x0, x1, . . . , xn−1) = y0∥y1∥ . . . ∥yn−1 where yi := F(xi, xi+1) is never invertible for any n ≥ 2 · m − 1. Here, we prove that • the quadratic function F : Fmp → Fp for m ∈ {1, 2} that minimizes the probability of having a collision for SF over Fnp is of the form F(x0, x1) = x20 + x1 (or equivalent);• the function SF over Fnp defined as before via F(x0, x1) = x20 +x1 (or equivalent) is 2n-bounded surjective.As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the FHE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the bounded surjective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.
Tal Derei, Benjamin Aulenbach, Victor Carolino, Caleb Geren · 8 authors
Zero-Knowledge proofs are a cryptographic technique to reveal knowledge of information without revealing the information itself, thus enabling systems optimally to mix privacy and transparency, and, where needed, regulatability. Application domains include health and other enterprise data, financial systems such as central-bank digital currencies, and performance enhancement in blockchain systems. The challenge of zero-knowledge proofs is that, although they are computationally easy to verify, they are computationally hard to produce. This paper examines the scalability limits of leading zero-knowledge algorithms and addresses the use of parallel architectures to meet performance demands of applications.
With the rapid development of information and communication technology, vehicular AD hoc networks (VANETs) has attracted more and more attention. In order to provide traffic safety services, vehicles frequently share information related to road traffic, such as vehicle motion data and traffic flow data. Reliable key generation is the basis of VANET security system construction. Presently, most key generation schemes rely on a trusted third party, so there are security risks. Traditional key agreement protocols have high overhead, and is not suitable for the latency-sensitive requirements of VANET. The physical layer security technology extracts the fingerprint of the wireless channel and the identity of the device, and generates the key quickly and in real time without the third party distribution. A physical layer key generation scheme based on received signal strength (RSS) is proposed to realize Vehicle-to-Vehicle (V2V) secure communications. First, a network model based on long short-term memory (LSTM) network and the Kalman filtering is proposed to effectively enhance the reciprocity of physical layer information in dynamic environment. Second, a lossless quantization scheme is proposed, which achieves a lower bit disagreement rate and a higher bit generation rate. Third, the inconsistent bits are corrected by fuzzy extractor, the confidentiality of the key exchange process is enhanced by zero knowledge proof, and the security of the key is improved by using hash function for privacy amplification. Finally, the experimental results show that the proposed scheme has great improvements in data correlation, bit disagreement rate, bit generation rate and bit distribution randomness.
We present a simple quantum interactive proof (QIP) protocol using the quantum state teleportation (QST) and quantum energy teleportation (QET) protocols. QET is a technique that allows a receiver at a distance to extract the local energy by local operations and classical communication (LOCC), using the energy injected by the supplier as collateral. QET works for any local Hamiltonian with entanglement and, for our study, it is important that getting the ground state of a generic local Hamiltonian is quantum Merlin Arthur (QMA)-hard. The key motivations behind employing QET for these purposes are clarified. Firstly, in cases where a prover possesses the correct state and executes the appropriate operations, the verifier can effectively validate the presence of negative energy with a high probability (Completeness). Failure to select the appropriate operators or an incorrect state renders the verifier incapable of observing negative energy (Soundness). Importantly, the verifier solely observes a single qubit from the prover's transmitted state, while remaining oblivious to the prover's Hamiltonian and state (Zero-knowledge). Furthermore, the analysis is extended to distributed quantum interactive proofs, where we propose multiple solutions for the verification of each player's measurement. The complexity class of our protocol in the most general case belongs to QIP(3)=PSPACE, hence it provides a secure quantum authentication scheme that can be implemented in small quantum communication devices. It is straightforward to extend our protocol to Quantum Multi-Prover Interactive Proof (QMIP) systems, where the complexity is expected to be more powerful (PSPACE$\subset$QMIP=NEXPTIME). In our case, all provers share the ground state entanglement, hence it should belong to a more powerful complexity class QMIP$^*$.