With the demand of cryptocurrencies, threshold ECDSA recently regained popularity. So far, several methods have been proposed to construct threshold ECDSA, including the usage of OT and homomorphic encryptions (HE). Due to the mismatch between the plaintext space and the signature space, HE-based threshold ECDSA always requires zero-knowledge range proofs, such as Paillier and Joye-Libert (JL) encryptions. However, the overhead of range proofs constitutes a major portion of the total cost.
Ron Steinfeld, Amin Sakzad, Muhammed F. Esgin, Veronika Kuchta · 6 authors
We introduce the first candidate Lattice-based designated verifier (DV) zero knowledge sUccinct Non-interactive Argument (ZK-SNARG) protocol, named LUNA, with quasi-optimal proof length (quasi-linear in the security/privacy parameter). By simply relying on mildly stronger security assumptions, LUNA is also a candidate ZK-SNARK (i.e. argument of knowledge). LUNA achieves significant improvements in concrete proof sizes, reaching below 6 KB (compared to >32 KB in prior work) for 128-bit security/privacy level. To achieve our quasi-optimal succinct LUNA, we give a new regularity result for 'private' re-randomization of Module LWE (MLWE) samples using discrete Gaussian randomization vectors, also known as a lattice-based leftover hash lemma with leakage, which applies with a discrete Gaussian re-randomization parameter that is polynomial in the statistical privacy parameter (avoiding exponential smudging), and hides the coset of the re-randomization vector support set. Along the way, we derive bounds on the smoothing parameter of the intersection of short integer solution (SIS), gadget, and Gaussian perp module lattices over the power of 2 cyclotomic rings. We then introduce a new candidate linear-only homomorphic encryption scheme called Module Half-GSW (HGSW), and apply our regularity theorem to provide smudging-free circuit-private homomorphic linear operations for Module HGSW. Our implementation and experimental performance evaluation show that, for typical instance sizes, Module HGSW provides favourable performance for ZK-SNARG applications involving lightweight verifiers. It enables significantly (around 5x) shorter proof lengths while speeding up CRS generation and encryption time by 4-16x and speeding up decryption time by 4.3x, while incurring just 1.2-2x time overhead in linear homomorphic proof generation operations, compared to a Regev encryption used in prior work in the ZK-SNARG context. We believe our techniques are of independent interest and will find application in other privacy-preserving lattice-based protocols.
Michael L. Rosenberg, Tushar Mopuri, Hossein Hafezi, Ian Miers · 5 authors
Zero-knowledge Succinct Non-interactive ARguments of Knowledge (zkSNARKs) allow a prover to convince a verifier of the correct execution of a large computation in private and easily-verifiable manner.These properties make zkSNARKs a powerful tool for adding accountability, scalability, and privacy to numerous systems such as blockchains and verifiable key directories.Unfortunately, existing zkSNARKs are unable to scale to large computations due to time and space complexity requirements for the prover algorithm.As a result, they cannot handle real-world instances of the aforementioned applications.In this work, we introduce Hekaton, a zkSNARK that overcomes these barriers and can efficiently handle arbitrarily large computations.We construct Hekaton via a new "distribute-and-aggregate" framework that breaks up large computations into small chunks, proves these chunks in parallel in a distributed system, and then aggregates the resulting chunk proofs into a single succinct proof.Underlying this framework is a new technique for efficiently handling data that is shared between chunks that we believe could be of independent interest.We implement a distributed prover for Hekaton, and evaluate its performance on a compute cluster.Our experiments show that Hekaton achieves strong horizontal scalability (proving time decreases linearly as we increase the number of nodes in the cluster), and is able to prove large computations quickly: it can prove computations of size 2 35 gates in under an hour, which is much faster than prior work.Finally, we also apply Hekaton to two applications of realworld interest: proofs of batched insertion for a verifiable key directory and proving correctness of RAM computations.In both cases, Hekaton is able to scale to handle realistic workloads with better efficiency than prior work.
Space-efficient SNARKs aim to reduce the prover's space overhead which is one the main obstacles for deploying SNARKs in practice, as it can be prohibitively large (e.g., orders of magnitude larger than natively performing the computation). In this work, we propose Sparrow, a novel space-efficient zero-knowledge SNARK for data-parallel arithmetic circuits with two attractive features: (i) it is the first space-efficient scheme where, for a given field, the prover overhead increases with a multiplicative sublogarithmic factor as the circuit size increases, and (ii) compared to prior space-efficient SNARKs that work for arbitrary arithmetic circuits, it achieves prover space asymptotically smaller than the circuit size itself. Our key building block is a novel space-efficient sumcheck argument with improved prover time which may be of independent interest. Our experimental results for three use cases (arbitrary data parallel circuits, multiplication trees, batch SHA256 hashing) indicate Sparrow outperforms the prior state-of-the-art space-efficient SNARK for arithmetic circuits Gemini (Bootle et al., EUROCRYPT'22) by 3.2-28.7x in total prover space and 3.1-11.3x in prover time. We then use Sparrow to build zero-knowledge proofs of tree training and prediction, relying on its space efficiency to scale to large datasets and forests of multiple trees. Compared to a (non-space-efficient) optimal-time SNARK based on the GKR protocol, we observe prover space reduction of 16-240x for tree training while maintaining essentially the same prover and verifier times and proof size. Even more interestingly, our prover requires comparable space to natively perform the underlying computation. E.g., for a 400MB dataset, our prover only needs 1.4x more space than the native computation.
Interactive theorem provers (ITPs), such as Lean and Coq, can express formal proofs for a large category of theorems, from abstract math to software correctness. Consider Alice who has a Lean proof for some public statement T. Alice wants to convince the world that she has such a proof, without revealing the actual proof. Perhaps the proof shows that a secret program is correct or safe, but the proof itself might leak information about the program's source code. A natural way for Alice to proceed is to construct a succinct, zero-knowledge, non-interactive argument of knowledge (zkSNARK) to prove that she has a Lean proof for the statement T.
The paper presents a comparative efficiency analysis of hashing algorithms in terms of applicability in zk-SNARK based systems. We have considered the hash functions sha256, sha3, blake2, mimc and poseidon, which are most widely used in modern distributed ledgers. To conduct experiments with measuring parameters, an infrastructure based on the ZoKrates toolbox was developed. A series of measurements with different input data was carried out for each algorithm. The number of constraints in the R1CS representation of the algorithm, the length of the proof key and the verification key, the running time of the setup phase of the protocol, and the proof generation time were measured. Based on the obtained results, we determined the boundaries of the practical applicability of algorithms for the problem of proving the knowledge of the preimage of a hash function using zk-SNARK circuits in distributed ledgers, and also identified emerging efficiency problems.
Open access
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
The hardness of lattice problems offers one of the most promising security foundations for quantum-safe cryptography. Basic schemes for public key encryption and digital signatures are already close to standardization at NIST and several other standardization bodies, and the research frontier has moved on to building primitives with more advanced privacy features. At the core of many such primitives are zero-knowledge proofs. In recent years, zero-knowledge proofs for (and using) lattice relations have seen a dramatic jump in efficiency and they currently provide arguably the shortest, and most computationally efficient, quantum-safe proofs for many scenarios. The main difficulty in using these proofs by non-experts (and experts!) is that they have a lot of moving parts and a lot of internal parameters depend on the particular instance that one is trying to prove.
Daniel Escudero, Antigoni Polychroniadou, Yifan Song, Chenkai Weng
In this work we study the efficiency of Zero-Knowledge (ZK) arguments of knowledge, particularly exploring Multi-Verifier ZK (MVZK) protocols as a midway point between Non-Interactive ZK and Designated-Verifier ZK, offering versatile applications across various domains. We introduce a new MVZK protocol designed for the preprocessing model, allowing any constant fraction of verifiers to be corrupted, potentially colluding with the prover. Our contributions include the first MVZK over rings. Unlike recent prior works on fields in the dishonest majority case, our protocol demonstrates communication complexity independent of the number of verifiers, contrasting the linear complexity of previous approaches. This key advancement ensures improved scalability and efficiency. We provide an end-to-end implementation of our protocol. The benchmark shows that it achieves a throughput of 1.47 million gates per second for 64 verifiers with 50% corruption, and 0.88 million gates per second with 75% corruption.
This paper presents the first comprehensive analysis of the address poisoning attack surged on the Ethereum blockchain. This phishing attack typically exploits the address shortening feature of Ethereum explorers and digital wallets (e.g., Etherscan and MetaMask) by crafting token transfer events with a seemingly correct address to poison victims' transfer history, waiting for them to mistakenly transfer assets to the attacker's address.
Kasra Abbaszadeh, Christodoulos Pappas, Jonathan Katz, Dimitrios Papadopoulos
A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer provable security and privacy guarantees, succinct proof size and verifier runtime, and practical prover efficiency. In this work, we present Kaizen, a zkPoT targeted for deep neural networks (DNNs) that achieves all these goals at once. Our construction enables a prover to iteratively train their model via (mini-batch) gradient descent, where the number of iterations need not be fixed in advance; at the end of each iteration, the prover generates a commitment to the trained model parameters attached with a succinct zkPoT, attesting to the correctness of the executed iterations. The proof size and verifier time are independent of the number of iterations.
M S, Chaitrali Mulay, Karthiganesh Durai, G. Murali · 16 authors
Abstract Blockchain technology is a highly developed database system that shares information within a business web. It stores details in blocks connected chronologically, ensuring information integrity through consensus mechanisms that prevent unauthorised alterations. This decentralised system removes the need for a believable mediator, mitigating vulnerabilities and enhancing transaction security. Blockchain’s application spans the energy, finance, media, entertainment, and retail sectors. However, classical blockchain faces threats from quantum computing advancements, necessitating the development of quantum blockchain technology. Quantum blockchain, leveraging quantum computation and information theory, offers enhanced security and immutability. In this paper, different mathematical foundations, practical implementations and effectiveness of lattice‐based cryptography in securing blockchain applications are discussed. Analysis of how the cryptographic techniques can protect blockchain systems against quantum attacks is being done by using mathematical formulations and examples. Quantum computing strengthens blockchain security with advanced encryption and authentication, which is critical for safeguarding diverse sectors from evolving cyber threats. Further study on quantum‐resistant design is necessary if blockchain networks are to be robust and intact in the face of future technological developments.
Open access
Blockchain Technology Applications and Security
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
Abstract In an Instance-Hiding Interactive Proof (IHIP) (Beaver et al., in: Menezes and Vanstone (eds) Advances in cryptology—CRYPTO 1990, proceedings, lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), Springer, pp 326–338, 1990), an efficient verifier with a private input x interacts with an unbounded prover to determine whether x is contained in a language $$\mathcal {L}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>L</mml:mi> </mml:math> . In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties and may be seen as a generalization of the influential concept of randomized encodings (Ishai and Kushilevitz, in: Proceedings 41st annual symposium on foundations of computer science, pp 294–304, 2000; Applebaum et al., in: 45th annual IEEE symposium on foundations of computer science, pp 166–175, 2004; Agrawal et al., in: Halldórsson, Iwama, Kobayashi, Speckmann (eds) Automata, languages, and programming, Springer, Berlin, Heidelberg, pp 1–13, 2015) and as a counterpart to zero-knowledge proofs (Goldwasser et al., in: Symposium on the theory of computing, 1985). We investigate the properties and power of such instance-hiding proofs and show the following: Any language with an IHIP is contained in $${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>NP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> <mml:mo>∩</mml:mo> <mml:mrow> <mml:mi>coNP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> </mml:mrow> </mml:math> . If an average-case hard language has a constant-round IHIP, then infinitely often non-uniform one-way functions exist. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof. IHIP’s are closed under composition with any efficiently computable function. We further study a stronger version of IHIP (that we call Simulatable IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above: Any language with a Simulatable IHIP is contained in $${\textsf{AM}}\cap {\textsf{coAM}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>AM</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>coAM</mml:mi> </mml:mrow> </mml:math> . If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist.
Open access
2 source records
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
Current mobile payment schemes gather detailed information about purchases customers make. This data can then be used to infer a customer’s spending behaviour, potentially violating their privacy. To tackle this problem, we propose an untraceable mobile payment scheme that strikes a better balance, preserving user privacy while allowing the Third-Party Service Provider (TPSP) to collect necessary information such as card details and transaction amount for regulatory compliance. Our scheme offers untraceability for legitimate users from malicious adversaries and curious TPSPs using cryptographic primitives such as partially blind signatures, zero-knowledge proofs, and identity-based signatures. It also guarantees that only authorised TPSPs can issue valid payment tokens, and even with limited data, the TPSP can still prevent dishonest customers/merchants from double-spending a payment token. We also propose a comprehensive evaluation framework to assess the untraceable payment schemes against seven key criteria such as untraceability, exculpability—merchant double-spending, exculpability—customer double-spending, unforgeability, confidentiality, message authenticity, efficiency, and regulatory compliance. We rigorously benchmark the security and privacy of our proposed payment scheme against this framework and other established schemes. Furthermore, we formally verify these properties using complexity-based analysis and Proverif modelling.
Preethi Preethi, Mohammed Mujeer Ulla, Ashwitha Anni, Pavithra Narasimha Murthy · 5 authors
Smart contracts are automated agreements executed on a blockchain, offering reliability through their immutable and distributed nature. Yet, their unalterable deployment necessitates precise preemptive security checks, as vulnerabilities could lead to substantial financial damages henceforth testing for vulnerabilities is necessary prior to deployment. This paper presents the graphical attention model distillation and inference network (GAMDI-Net), a pioneering methodology that significantly enhances smart contract vulnerability detection. GAMDI-Net introduces a unique graphical learning module that employs attention mechanism networks to transform complex contract code into a smart graphical representation. In addition to this a dual-modality model distillation and mutual modality learning mechanism, GAMDI-Net excels in synthesizing semantic and control flow data to predict absent bytecode embeddings with high accuracy. This methodology not only improves the precision of vulnerability detection but also addresses scalability and efficiency challenges, reinforcing trust in the deployment of secure smart contracts within the blockchain ecosystem.
Baowei Wang, Fengxiao Guo, Yuting Liu, Bin Li · 5 authors
Abstract Voting plays a vital role in democratic societies. Adopting electronic voting can effectively increase voter participation and significantly reduce the financial burden on the organizers. In recent years, with the prevalence of blockchain technology, numerous blockchain-based electronic voting schemes have emerged. Compared with traditional electronic voting schemes, they have more favorable security features. However, existing schemes generally suffer from inefficient voting procedures, limited functionality, and dependence on specific blockchain platforms, making them challenging to deploy in diverse voting scenarios. This paper proposes an efficient and versatile electronic voting scheme on blockchain that addresses these problems using our proposed smart contract-based aggregated blind signature, zero-knowledge proofs, and threshold encryption scheme. In the paper, the scheme’s various features, including security, are analyzed in detail, and the scheme is deployed and tested on the Hyperledger Fabric and Ethereum blockchain platform. The experiment results demonstrate that the voting scheme satisfies the security requirement, and it has outstanding advantages in performance.
Open access
Internet Traffic Analysis and Secure E-voting
Cryptography and Data Security
Advanced Steganography and Watermarking Techniques
Janak Dhokrat, Namita Pulgam, Tabassum Maktum, Vanita Mane
In digital landscape of today’s ongoing world, the imperative for enhanced security in cloud-based data processing is paramount. This paper introduces an innovative framework that seamlessly integrates Homomorphic Encryption and Zero-Knowledge Proofs (ZKPs) to bolster data privacy and confidentiality. This paper explores the technical intricacies, real-world applications, and potential implications of this fusion framework. Homomorphic Encryption empowers computations on encrypted data without compromising privacy, while Zero-Knowledge Proofs offer a mechanism to verify computations without exposing sensitive details. The effectiveness and adaptability of the proposed framework is demonstrated through meticulous analysis and practical deployment in safeguarding cloud-based data processing. The proposed framework marks a significant stride towards creating an environment where data security is unequivocally prioritized.
Valeh Farzaliyev, Calvin Pärn, Heleen Saarse, Jan Willemson
Abstract This paper studies several building blocks needed for electronic voting in order to prepare for the post-quantum era. In particular, we present lattice-based constructions for a generic zero-knowledge (ZK) proof of ballot correctness, a ZK proof of ballot correctness applicable for the homomorphic tallying scenario, and a ZK proof to achieve cast-as-intended verification during the vote casting period. We implement and benchmark our ballot correctness proofs, giving concrete estimations comparing the performance of homomorphic tallying and mix-net based e-voting systems in case of our lattice-based constructions.
In database applications involving sensitive data, the dual imperatives of data confidentiality and provable (verifiable) query processing are important. This paper introduces PoneglyphDB, a database system that leverages non-interactive zero-knowledge proofs (ZKP) to support both confidentiality and provability. Unlike traditional databases, PoneglyphDB enhances confidentiality by ensuring that raw data remains exclusively with the host, while also enabling verifying the correctness of query responses by providing proofs to clients. The main innovation in this paper is proposing efficient ZKP designs (called circuits) for basic operations in SQL query processing. These basic operation circuits are then combined to form ZKP circuits for larger, more complex queries. PoneglyphDB's circuits are carefully designed to be efficient by utilizing advances in cryptography such as PLONKish-based circuits, recursive proof composition techniques, and designing with low-order polynomial constraints. We demonstrate the performance of PoneglyphDB with the standard TPC-H benchmark. Our experimental results show that PoneglyphDB can efficiently achieve both confidentiality and provability, outperforming existing state-of-the-art ZKP methods.
In crowd-sourced data aggregation over the Internet, participants share their data points with curators. However, a lack of strong privacy guarantees may discourage participation, which motivates the need for privacy-preserving aggregation protocols. Moreover, existing solutions remain limited with respect to public auditing without revealing the participants’ data. In realistic applications, however, there is an increasing need for public verifiability (i.e., verifying the protocol correctness) while preserving the privacy of the participants’ inputs, since the participants do not always trust the data curators. At the same time, while publicly distributed ledgers may provide public auditing, these schemes are not designed to protect sensitive information. In this work, we introduce two protocols, dubbed Masquerade and zk-Masquerade, for computing private statistics, such as sum, average, and histograms, without revealing anything about participants’ data. We propose a tailored multiplicative commitment scheme to ensure the integrity of data aggregations and publish all the participants’ commitments on a ledger to provide public verifiability. zk-Masquerade detects malicious participants who attempt to poison the aggregation results by adopting two zero-knowledge proof protocols that ensure the validity of shared data points before being aggregated and enable a broad range of numerical and categorical studies. In our experiments, we use homomorphic ciphertexts and commitments for a variable number of participants and evaluate the runtime and the communication cost of our protocols.
Decentralized Federated Learning improves data privacy and eliminates single points of failure by removing reliance on centralized storage and model aggregation in distributed computing systems. Ensuring the integrity of computations during local model training is a significant challenge, especially before sharing gradient updates from each local client. Current methods for ensuring computation integrity often involve patching local models to implement cryptographic techniques, such as Zero-Knowledge Proofs. However, this approach becomes highly complex and sometimes impractical for large-scale models that use techniques such as random dropouts to improve training convergence. These random dropouts create non-deterministic behavior, making it challenging to verify model updates under deterministic protocols. We propose ProxyZKP, a novel framework combining Zero-Knowledge Proofs with polynomial proxy models to provide computation integrity in local training to address this issue. Each local node combines a private model for online deep learning applications and a proxy model that mediates decentralized model training by exchanging gradient updates. The multivariate polynomial nature of proxy models facilitates the application of Zero-Knowledge Proofs. These proofs verify the computation integrity of updates from each node without disclosing private data. Experimental results indicate that ProxyZKP significantly reduces computational load. Specifically, ProxyZKP achieves proof generation times that are 30-50% faster compared to established methods like zk-SNARKs and Bulletproofs. This improvement is largely due to the high parallelization potential of the univariate polynomial decomposition approach. Additionally, integrating Differential Privacy into the ProxyZKP framework reduces the risk of Gradient Inversion attacks by adding calibrated noise to the gradients, while maintaining competitive model accuracy. The results demonstrate that ProxyZKP is a scalable and efficient solution for ensuring training integrity in decentralized federated learning environments, particularly in scenarios with frequent model updates and the need for strong model scalability.
With the development of the data-sharing system in recent years, financial management systems and their privacy have sparked great interest. Existing financial data-sharing systems store metadata, which include a hash value and database index on the blockchain, and store high-capacity actual data in the center database. However, current data-sharing systems largely depend on centralized systems, which are susceptible to distributed denial-of-service (DDoS) attacks and present a centralized attack vector. Furthermore, storing data in a local center database has a high risk of information disclosure and tampering. In this paper, we propose the ChainMaker Privacy Computing (CPC) system, a new decentralized data-sharing system for secure financial data, to solve this problem. It provides a series of financial data information and a data structure rather than actual data on the blockchain to protect the privacy of data. We utilize a smart contract to establish a trusted platform for the local database to obtain encrypted data. We design a resource catalog to provide a trusted environment of data usage in the privacy computing system that is visible for members on the blockchain. Based on cipher-policy attribute-based encryption (CP-ABE), We design a CPC-CP-ABE algorithm to enable fine-grained access control through attribute based encryption. Finally, We propose an efficient scheme that allows authenticated data-sharing systems to perform Boolean searches on encrypted data information. The results of experiment show that the CPC system can finish trusted data sharing to all organizations on the blockchain.
To enhance the security of ciphertext-policy attribute-based encryption (CP-ABE) and achieve fully distributed key generation (DKG), this paper proposes a ciphertext access control scheme integrating blockchain and off-chain computation with zero knowledge proof based on Layer-2 and multi-authority CP-ABE. Firstly, we enhance the system into two layers and construct a Layer-2 distributed key management service framework. This framework improves system efficiency and scalability while reducing costs. Secondly, we design the proof of trust contribution (PoTC) consensus algorithm to elect high-trust nodes responsible for DKG and implement an incentive mechanism for key computation through smart contract design. Finally, we design a non-interactive zero-knowledge proof protocol to achieve correctness verification of off-chain key computation. Security analysis and simulation experiments demonstrate that our scheme achieves high security while significantly improving system performance. The time consumption for data users to obtain attribute private keys is controlled at tens of milliseconds.