Zero-knowledge proof is emerging to enable privacy. Among existing techniques, zk-SNARK (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) [1] supports the shortest verification time and the smallest proof size. However, using zk-SNARK requires the execution of trusted setup ceremony in advance. The trusted setup ceremony generates common reference string (CRS) which is shared with prover and verifier. Currently, an external trusted third party is assumed for trusted setup ceremony, which causes significant security vulnerability in zk-SNARK. In this paper, we propose a blockchain-based protocol of trusted setup ceremony without trusted third party. Three different types of protocols are classified in terms of where to store CRS and how to validate CRS through pairing check. We analyze the protocol complexity of CRS pairing check computations and on-chain storage space.
We exploit the idea of [Fen22] which proposes to build an efficient signature scheme based on a zero-knowledge proof of knowledge of a solution of a MinRank instance. The scheme uses the MPCitH paradigm, which is an efficient way to build ZK proofs. We combine this idea with another idea, the hypercube technique introduced in [AMGH+22], which leads to more efficient MPCitH-based scheme. This new approach is more efficient than classical MPCitH, as it allows to reduce the number of party computation. This gives us a first scheme called MIRA-Additive. We then present an other scheme, based on low-threshold secret sharings, called MIRA-Threshold, which is a faster scheme, at the price of larger signatures. The construction of MPCitH using threshold secret sharing is detailed in [FR22]. These two constructions allows us to be faster than classical MPCitH, with a size of signature around 5.6kB with MIRA-Additive, and 8.3kB with MIRA-Threshold. We detail here the constructions and optimizations of the schemes, as well as their security proofs.
We present a signature scheme based on the Syndrome-Decoding problem in rank metric. It is a construction from multi-party computation (MPC), using a MPC protocol which is a slight improvement of the linearized-polynomial protocol used in [Fen22], allowing to obtain a zero-knowledge proof thanks to the MPCitH paradigm. We design two different zero-knowledge proofs exploiting this paradigm: the first, which reaches the lower communication costs, relies on additive secret sharings and uses the hypercube technique [AMGH+22]; and the second relies on low-threshold linear secret sharings as proposed in [FR22]. These proofs of knowledge are transformed into signature schemes thanks to the Fiat-Shamir heuristic [FS86].
Jesús García-Rodríguez, Stephan Krenn, Jorge Bernal Bernabé, Antonio Skármeta
PREPRINT: The increasing user awareness and regulatory framework (e.g., GDPR) have contributed to considering data minimization and privacy-by-design as central guiding principles for new systems.<br> Among others, this has led to a paradigm shift towards Self-Sovereign Identity solutions to put the user in full control over their data.<br> Despite the promising landscape, privacy-preserving Attribute-Based Credentials (p-ABC) have not been widely adopted, mainly due to the lack of secure, flexible and efficient implementations that cover the basic and advanced needs in p-ABC systems. In this work, we tackle this gap by formalizing an improved zero-knowledge showing protocol of a distributed p-ABC scheme based on Pointcheval-Sanders Multi-Signatures to allow for modular extensions through commit-and-prove techniques. We use it to implement a flexible p-ABC system with decentralized issuance that, apart from the basic notions of p-ABCs, covers range proofs, pseudonyms, inspection and revocation. Lastly, we thoroughly evaluate the performance of the system under different testbed conditions, showing a significant efficiency improvement over previous implementations.
\n\t\n\t\t\n\t\t\t\n\t\t\tWith the rapid development of technology and the large amount of digitization in various fields of human life, it is necessary to pay attention to the security and certainty of privacy so that there is no leakage of confidential data, both in the private and governmental domains, especially in Indonesia. In this case cyber-attacks will grow and become more numerous; therefore we need a security principle that can prevent these cyber-attacks, especially in sending something that is sensitive which can be called cryptography. One of the applications that can be implemented regarding this cryptography is the Whatsapp application. WhatsApp claims that the application is safe from data theft and messages being intercepted. However, this is doubtful with the presence of Whatsapp Mod which offers more features than the official application. The security of the modified Whatsapp is questionable, so in this study a test was carried out using the MobSF Framework to find out whether there were security holes that could endanger its users. The results of this research are in the form of a report issued by MobSF regarding the level of danger of the Whatsapp Mod Application. With this research, it is hoped that it will be able to make Whatsapp Mod users aware of the dangers of modified applications and Whatsapp can provide advice and strict action against the Whatsapp Mod developers.\n\t\t\t\n\t\t\n\t\n
Rabimba Karanjai, Sangwon Shin, Xiong, and Wujie, Xinxin Fan · 11 authors
Cryptographic schemes like Fully Homomorphic Encryption (FHE) and Zero-Knowledge Proofs (ZKPs), while offering powerful privacy-preserving capabilities, are often hindered by their computational complexity. Polynomial multiplication, a core operation in these schemes, is a major performance bottleneck. While algorithmic advancements and specialized hardware like GPUs and FPGAs have shown promise in accelerating these computations, the recent surge in AI accelerators (TPUs/NPUs) presents a new opportunity. This paper explores the potential of leveraging TPUs/NPUs to accelerate polynomial multiplication, thereby enhancing the performance of FHE and ZKP schemes. We present techniques to adapt polynomial multiplication to these AI-centric architectures and provide a preliminary evaluation of their effectiveness. We also discuss current limitations and outline future directions for further performance improvements, paving the way for wider adoption of advanced cryptographic tools.
Zero-knowledge proof (ZKP) frameworks have the potential to revolutionize the handling of sensitive data in various domains. However, deploying ZKP frameworks with real-world data presents several challenges, including scalability, usability, and interoperability. In this project, we present Fact Fortress, an end-to-end framework for designing and deploying zero-knowledge proofs of general statements. Our solution leverages proofs of data provenance and auditable data access policies to ensure the trustworthiness of how sensitive data is handled and provide assurance of the computations that have been performed on it. ZKP is mostly associated with blockchain technology, where it enhances transaction privacy and scalability through rollups, addressing the data inherent to the blockchain. Our approach focuses on safeguarding the privacy of data external to the blockchain, with the blockchain serving as publicly auditable infrastructure to verify the validity of ZK proofs and track how data access has been granted without revealing the data itself. Additionally, our framework provides high-level abstractions that enable developers to express complex computations without worrying about the underlying arithmetic circuits and facilitates the deployment of on-chain verifiers. Although our approach demonstrated fair scalability for large datasets, there is still room for improvement, and further work is needed to enhance its scalability. By enabling on-chain verification of computation and data provenance without revealing any information about the data itself, our solution ensures the integrity of the computations on the data while preserving its privacy.
Secure data deletion enables data owners to have full control over the erasure of their data stored on local or cloud data centers, and it is essential for preventing data leakage, especially in cloud storage. However, traditional data deletion methods based on unlinking, overwriting, and cryptographic key management are either ineffective in cloud storage or rely on impractical assumptions. In this paper, we introduce SevDel, a secure and verifiable data deletion scheme that utilizes zero-knowledge proofs to achieve verification of the encryption of outsourced data without retrieving the ciphertexts. Meanwhile, the deletion of encryption keys is guaranteed based on Intel SGX. SevDel implements secure interfaces for performing data encryption and decryption in secure cloud storage. It also utilizes smart contracts to enforce the operations of the cloud service provider, ensuring compliance with service level agreements with data owners and imposing penalties on the service provider for disclosing cloud data on its servers. Evaluation using real-world workloads demonstrates that SevDel efficiently achieves data deletion verification and maintains high bandwidth savings.
Mobile sign language apps have drawn a lot of interest recently as a way to minimize communication barriers between hearing people and people with hearing impairments. However, there are issues with the criteria and standards that should be taken into account when developing these apps. This study proposes a set of development criteria for sign language mobile apps and standardizes these criteria using the Fuzzy Delphi approach. Furthermore, the Fuzzy-Weighted Zero Inconsistency (FWZIC) approach is utilized to assign weights to the criteria and establish a ranking order. An initial set of requirements is developed based on the literature review. The Fuzzy Delphi technique is used, involving a panel of experts made up of developers, sign language experts, and users of sign language mobile apps, to assess the validity and reliability of the criteria. The FWZIC technique is used to give the criterion weights and determine their ranking order in order to further improve the decision-making process. The relative relevance of each criterion is determined by the FWZIC technique, which involves expert input and makes use of their knowledge and expertise. A thorough ranking is generated by taking into account the effects of each criterion on several zones, assisting in efficient decision-making during the creation of sign language mobile apps. Six Malaysian Sign Language apps that have been shortlisted are being utilized as a proof of concept to test the idea. The result of 6 apps is obtained based on the final standard criteria, their weights, and rankings.
Training contemporary AI models requires investment in procuring learning data and computing resources, making the models intellectual property of the owners. Popular model watermarking solutions rely on key input triggers for detection; the keys have to be kept private to prevent discovery, forging, and removal of the hidden signatures. We present ZKROWNN, the first automated end-to-end framework utilizing Zero-Knowledge Proofs (ZKP) that enable an entity to validate their ownership of a model, while preserving the privacy of the watermarks. ZKROWNN permits a third party client to verify model ownership in less than a second, requiring as little as a few KBs of communication.
Laasya Bangalore, Mohammad Hossein Faghihi Sereshgi, Carmit Hazay, Muthuramakrishnan Venkitasubramaniam
In this work, we introduce a lightweight secure aggregation protocol that guarantees liveness (i.e., guaranteed output delivery), robust against faulty inputs and security against malicious clients. First, we improve upon prior works in the “star”-like topology network with a central coordinating (also output) party, Bonawitz et al. (ACM CCS 2017) and Bell et al. (ACM CCS 2020), which are not robust against faulty inputs. Recent works, RoFL (Burkhalter et al.) and (concurrent work) ACORN (Bell et al.) show how to rely on zero-knowledge proofs to address such attacks at expense of significantly high computation costs. We also compare our protocol against the PRIO system by Gibbs and Boneh (USENIX 2017) which achieves the same task in an incomparable security model. We benchmark our protocol with implementation and demonstrate its concrete efficiency. Our solution scales to 1000s of clients, requires only a constant number of rounds, outperforms prior work in computational cost, and has competitive communication cost.
This paper proposes a novel voting system that incorporates an intersectional Privilege Index to address social inequalities and power imbalances that often lead to marginalized groups being underrepresented in the political sphere. The Privilege Index is a composite measure that takes into account various factors, such as race, gender, socioeconomic status, and education, which contribute to an individual's social privilege. By incorporating this index into the voting process, the proposed blockchain-based system aims to counteract the effects of systemic inequalities and ensure that underrepresented groups have a more significant impact on the outcome of elections and other democratic processes. This paper provides a comprehensive analysis of the proposed Privilege Index-based voting system, outlining its design, potential benefits, and associated ethical, legal, and practical challenges. The system incorporates zero-knowledge proofs to protect the privacy of citizens' personal information and assigns a vote token based on the Privilege Index score. During the voting process, citizens burn their vote tokens to cast their ballots, and the final results are determined by the sum of the token values for each candidate or option. Despite the potential benefits of the Privilege Index-based voting system, it also raises several ethical, legal, and practical challenges that must be carefully considered, such as accuracy of the Privilege Index, privacy concerns, potential for manipulation, legal and ethical considerations, and practical challenges. This paper examines these challenges and presents strategies for mitigating them to ensure a fair and inclusive democratic process.
Ning Lin, Shaocong Wang, Yi Li, Bo Wang · 22 authors
The human brain is a complex spiking neural network (SNN), capable of learning multimodal signals in a zero-shot manner by generalizing existing knowledge. Remarkably, it maintains minimal power consumption through event-based signal propagation. However, replicating the human brain in neuromorphic hardware presents both hardware and software challenges. Hardware limitations, such as the slowdown of Moore's law and Von Neumann bottleneck, hinder the efficiency of digital computers. Additionally, SNNs are characterized by their software training complexities. To this end, we propose a hardware-software co-design on a 40 nm 256 Kb in-memory computing macro that physically integrates a fixed and random liquid state machine (LSM) SNN encoder with trainable artificial neural network (ANN) projections. We showcase the zero-shot LSM-based learning of multimodal events on the N-MNIST and N-TIDIGITS datasets, including visual and audio data association, as well as neural and visual data alignment for brain-machine interfaces. Our co-design achieves classification accuracy comparable to fully optimized software models, resulting in a 152.83 and 393.07-fold reduction in training costs compared to SOTA contrastive language-image pre-training (CLIP) and Prototypical networks, and a 23.34 and 160-fold improvement in energy efficiency compared to cutting-edge digital hardware, respectively. These proof-of-principle prototypes demonstrate zero-shot multimodal events learning capability for emerging efficient and compact neuromorphic hardware.
The exponential growth in connected devices with Internet-of-Things (IoT) and next-generation wireless networks requires more advanced and dynamic spectrum access mechanisms. Blockchain-based approaches to Dynamic Spectrum Access (DSA) seem efficient and robust due to their inherited characteristics such as decentralization, immutability, and transparency. However, conventional consensus mechanisms used in blockchain networks are expensive to be used due to the cost, processing, and energy constraints. Moreover, addressing spectrum violations (i.e., unauthorized access to the spectrum) is not well-discussed in most blockchain-based DSA systems in the literature. In this work, we propose a newly tailored energy-efficient consensus mechanism called “Distributed-Proof-of-Sense (DPoS)” that is specially designed to enable DSA and detect spectrum violations. The proposed consensus algorithm motivates blockchain miners to perform spectrum sensing, which leads to the collection of a full spectrum of sensing data. An elliptic curve cryptography-based zero-knowledge proof is used as the core of the proposed mechanism. We use MATLAB simulations to analyze the performance of the consensus mechanism and implement several consensus algorithms in a microprocessor to highlight the benefits of adopting the proposed system.
We propose a middleware solution designed to facilitate seamless integration of privacy using zero-knowledge proofs within various multi-chain protocols, encompassing domains such as DeFi, gaming, social networks, DAOs, e-commerce, and the metaverse. Our design achieves two divergent goals. zkFi aims to preserve consumer privacy while achieving regulation compliance through zero-knowledge proofs. These ends are simultaneously achievable. zkFi protocol is designed to function as a plug-and-play solution, offering developers the flexibility to handle transactional assets while abstracting away the complexities associated with zero-knowledge proofs. Notably, specific expertise in zero-knowledge proofs (ZKP) is optional, attributed to zkFi's modular approach and software development kit (SDK) availability.
The objective of this memory is to give a purely algebraic proof of the Sauer- Shelah-Perles Lemma (inspired by the elegant proof in [FrPa,1983]), based only in duality in the Q−algebra Q[Vn] of polynomial functions de_ned on the zero-dimensional algebraic variety of subsets of the set [n] := {1, 2, . . . , n}. In fact, two di_erent proofs of this lemma will be given. Furthermore, we prove how several other classical results from Combinatorics are particular examples of a Trace (Inversion) Formula in _nite Q−algebras. For instance, one of this results is the general form of the Inclusion-Exclusion Principle (both with direct and reverse order associated to subsets inclusion). This approach also allows us to show a basis of the space of null t−designs, which di_ers from the one described in Theorem 4 of [DeFr,1982]. All results are still true if we replace Q[Vn] by K[Vn], where K is a perfect _eld of characteristic di_erent from 2. This memory has then the underlying purpose of connecting two _elds of mathematical knowledge that are not usually connected, at least not in this form.
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).
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.
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.