Zero Knowledge Proof (ZKP) is a very effective method of preserving privacy as it hides the most confidential information throughout the transaction. In this paper, we present a security and privacy-preserving approach for blockchain that relies on account and multi-data asset models using the Zero Knowledge Proof (ZKP) mechanism. We provide options for transferring data assets and detecting duplicate expenditures, and we also develop transaction structures, anonymised addresses and anonymised metadata for the data assets. To create and validate the ZKP, we use the zk-SNARKs algorithm and specify validation criteria for masked transactions, and finally conduct experimental tests to validate it. Creating better algorithms for ZKP will be the focus of our future efforts.
Decentralizing crowdsourcing through blockchain technology eliminates the need for trusted third-party intermediaries that may introduce social biases in data aggregation, thereby enhancing transparency and ensuring appropriate rewards for workers. However, open permissionless blockchain platforms typically disclose all transaction data on public ledgers, which compromises the privacy and anonymity of workers and encourages free-riding. Blockchain-based anonymous crowdsourcing systems have recently emerged, offering anonymity but requiring identity registration for workers and a trusted setup for key generation. These systems in general, fail to support anonymous payments, potentially compromising worker identities. In this paper, we integrate anonymous payments into crowdsourcing, eliminating the need for identity registration and trusted setup, thus fostering open and anonymous participation from any worker. Our solution utilizes the decentralized anonymous payment system framework, such as Zerocoin, and includes staking mechanisms for participation in crowdsourcing as well as efficient one-out-of-many zero-knowledge proofs. Additionally, our empirical evaluations reveal that the system incurs moderate and practical gas costs.
The ongoing regulation of blockchain-based services and applications requires the identification of users who are issuing transactions on the blockchain. This systematic review explores the current status, identifies research gaps, and outlines future research directions for establishing trusted and privacy-compliant identities on the blockchain (on-chain identity). A systematic search term was applied across various scientific databases, collecting 2232 potentially relevant research papers. These papers were narrowed down in two methodologically executed steps to 98 and finally to 13 relevant sources. The relevant articles were then systematically analyzed based on a set of screening questions. The results of the selected studies have provided insightful findings on the mechanisms of on-chain identities. On-chain identities are established using zero-knowledge proofs, public key infrastructure/certificates, and web of trust approaches. The technologies and architectures used by the authors are also highlighted. Trust has emerged as a key research gap, manifesting in two ways: firstly, a gap in how to trust the digital identity representation of a physical human; secondly, a gap in how to trust identity providers that issue identity confirmations on-chain. Potential future research avenues are suggested to help fill the current gaps in establishing trust and on-chain identities.
Abstract Suppose that a sequence of $${\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> cards, numbered 1 to $${\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> , is placed face up in random order. Let $${\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> be the number on the first card in the sequence. Then take the first $${\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> cards from the sequence, rearrange that subsequence of $${\varvec{k}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> </mml:mrow> </mml:math> cards in reverse order, and return them to the original sequence. Repeat this prefix reversal until the number on the first card in the sequence becomes 1. This is a one-player card game called Topswops. The computational complexity of Topswops has not been thoroughly investigated. For example, letting $${\varvec{f}}({\varvec{n}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>f</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> denote the maximum number of prefix reversals for Topswops with $${\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> cards, values of $${\varvec{f}}({\varvec{n}})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>f</mml:mi> </mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> for $${\varvec{n}}\ge 20$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> <mml:mo>âĽ</mml:mo> <mml:mn>20</mml:mn> </mml:mrow> </mml:math> remain unknown. In general, there is no known efficient algorithm for finding an initial sequence of $${\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> cards that requires exactly $$\ell $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>â</mml:mi> </mml:math> prefix reversals for any integers $${\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> and $${\varvec{\ell }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>â</mml:mi> </mml:mrow> </mml:math> . In this paper, using a deck of cards, we propose a physical zero-knowledge proof protocol that allows a prover to convince a verifier that the prover knows an initial sequence of $${\varvec{n}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> cards that requires $${\varvec{\ell }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>â</mml:mi> </mml:mrow> </mml:math> prefix reversals without leaking knowledge of that sequence. We also deal with Botdrops, a variant of Topswops.
Wenqian Xue, Bosen Lian, Yusuf Kartal, Jialu Fan ¡ 6 authors
This paper proposes a data-driven model-free inverse reinforcement learning (IRL) algorithm tailored for solving an inverse$H_{\infty } $control problem. In the problem, both an expert and a learner engage in$H_{\infty } $control to reject disturbances and the learnerâs objective is to imitate the expertâs behavior by reconstructing the expertâs performance function through IRL techniques. Introducing zero-sum game principles, we first formulate a model-based single-loop IRL policy iteration algorithm that includes three key steps: updating the policy, action, and performance function using a new correction formula and the standard inverse optimal control principles. Building upon the model-based approach, we propose a model-free single-loop off-policy IRL algorithm that eliminates the need for initial stabilizing policies and prior knowledge of the dynamics of expert and learner. Also, we provide rigorous proof of convergence, stability, and Nash optimality to guarantee the effectiveness and reliability of the proposed algorithms. Furthermore, we showcase the efficiency of our algorithm through simulations and experiments, highlighting its advantages compared to the existing methods.Note to PractitionersâGenerally, the cost function for optimal tracking or imitation control is manually defined, which is a challenging task and may result in large tracking errors and slow tracking. In such cases, IRL is a powerful tool for reconstructing proper cost functions. Real-world systems, as demonstrated in practical cases, are frequently exposed to external disturbances and come with unknown models. Employing$H_{\infty } $control is an effective strategy to handle disturbances. However, applying model-free IRL to solve the inverse problem of$H_{\infty } $control for imitation remains an underexplored domain. This paper explores model-free inverse$H_{\infty } $control for imitating expert behaviors, specifically addressing the time-consuming nature of the existing IRL studies that employ a two-loop iteration structure. We propose an efficient single-loop IRL algorithm with a new framework to do this. It is data-driven and model-free, eliminating the need to find an initial stabilizing control policy, which is typically challenging. Additionally, it ensures convergence, stability, and optimality with provable guarantees.
Blockchain full nodes are pivotal for transaction availability, as they store the entire ledger, but verifying their storage integrity faces challenges from malicious remote storage attacks such as Sybil, outsourcing, and generation attacks. However, there is no suitable proof-of-storage solution for blockchain full nodes to ensure a healthy number of replicas of the ledger. Existing proof-of-storage solutions are designed for general-purpose settings where a data owner uses secret information to verify storage, rendering them unsuitable for blockchain where proof-of-storage must be fast, publicly verifiable, and data owner-agnostic. This paper introduces a decentralised and quantum-resistant solution named Non-interactive Practical Proof of Storage (nPPoS) with an asymmetric encoding and decoding scheme, for fast and secure PoStorage, and Zero-Knowledge Scalable Transparent Arguments of Knowledge (zk-STARKs), for public variability in blockchain full nodes. The algorithm with asymmetric times for encoding and decoding creates unique block replicas and corresponding proofs for each storage node to mitigate malicious remote attacks and minimise performance degradation. The intentional resource-intensive encoding deters attacks, while faster decoding minimises performance overhead. Through zk-STARKs, nPPoS achieves public verifiability enabling one-to-many verification for scalability, quantum resistance and decentralisation. It also introduces a two-phase randomisation technique and a time-weighted trustworthiness measurement for scalability and adaptability.
As intelligent vehicles gradually become prevalent, the identity verification and data security in V2X communication are increasingly garnering attention. This study is dedicated to addressing the management and querying of revocation lists in vehicle-road cooperative environments, striving to enhance the reliability and trustworthiness of the revocation lists. By integrating blockchain technology and smart contracts, this paper ensures the immutability and transparency of certificate revocation data. The adoption of the SSMS multi-signature algorithm reduces the reliance on a single node, thereby enhancing the security of the system. In response to the security challenges faced by vehicles in cross-domain operations, this research introduces a verification mechanism based on zero-knowledge proofs, accomplishing secure vehicle verification while simultaneously protecting vehicle privacy. Further more, considering the need for communication security of vehicles under complex road conditions, this paper innovatively designs a query accumulative filter to support efficient identity verification.
Abstract In response to the dual privacy protection challenges concerning the confidentiality of transaction amounts and identities in crossâborder trade, a transaction scheme that combines + HomEIG Zero Knowledge Proof ( + HomEIGâZKProof) and the national encryption algorithm SM2 is proposed. While ensuring transaction traceability and verifiability, this scheme achieves privacy protection for both payersâ and recipientsâ identities, specifically tailored for crossâborder trade scenarios. Additionally, customs authorities play the role of supervisory nodes to verify the identities of transaction parties and the zeroâknowledge proofs for transaction information. The RAFT consensus algorithm is employed to construct a secure authentication application, demonstrating how zeroâknowledge proofs, combined with homomorphic encryption, can be verified through a consensus process. In this scenario, the legitimacy of transaction amounts is subject to zeroâknowledge verification during consensus interactions. Merchant identity verification is accomplished using SM2 ring signatures. The analysis indicates that this scheme offers strong security features such as resistance to tampering attacks, public key replacement attacks, impersonation attacks, and anonymity. Testing results demonstrate that this scheme can effectively provide dual privacy protection for transaction amounts and identities in crossâborder trade, meeting the practical requirements of privacy protection in crossâborder trade transactions.
Frederico Baptista, Marina Dehez-Clementi, Jonathan Detchart
The integration of Unmanned Aircraft Systems (UASs) into the current airspace poses significant challenges in terms of safety, security, and operability. As an example, in 2019, the European Union defined a set of rules to support the digitalization of UAS traffic management (UTM) systems and services, namely the U-Space regulations. Current propositions opted for a centralized and private model, concentrated around governmental authorities (e.g., AlphaTango provides the Registration service and depends on the French government). In this paper, we advocate in favor of a more decentralized and transparent model in order to improve safety, security, operability among UTM stakeholders, and legal compliance. As such, we propose DFly, a publicly auditable and privacy-preserving UAS traffic management system on Blockchain, with two initial services: Registration and Flight Authorization. We demonstrate that the use of a blockchain guarantees the public auditability of the two services and corresponding service providersâ actions. In addition, it facilitates the comprehensive and distributed monitoring of airspace occupation and the integration of additional functionalities (e.g., the creation of a live UAS tracker). The combination with zero-knowledge proofs enables the deployment of an automated, distributed, transparent, and privacy-preserving Flight Authorization service, performed on-chain thanks to the blockchain logic. In addition to its construction, this paper details the instantiation of the proposed UTM system with the Ethereum Sepoliaâs testnet and the Groth16 ZK-SNARK protocol. On-chain (gas cost) and off-chain (execution time) performance analyses confirm that the proposed solution is a viable and efficient alternative in the spirit of digitalization and offers additional security guarantees.
Abstract A zero-knowledge proof is a cryptographic primitive that enables a prover to convince a verifier the validity of a mathematical statement (an NP statement) without revealing any secret inputs to the verifier. A special case, called zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK) is particularly designed for arithmetic circuit proof systems which have important applications in blockchain privacy. The major computations in this type of zkSNARK proofs with post-quantum security are polynomial evaluations and Lagrange interpolations over finite fields. Given a sequence over a finite field, in the field of coding and sequences research, we understand that there are two representations of the sequence, one is a univariate polynomial and the other, a multivariate polynomial. This is exactly what is done in those zero-knowledge proof systems to transform the proof of a R1CS relation to evaluate uni/multi variate polynomials at some random points in the finite field. In this paper, we present a comparative analysis on how to convert a rank 1 constrained satisfiability (R1CS) system (more general than a circuit system) into a polynomial equality and provide analysis on the concrete complexities of provers, proof sizes and verifiers. We use two concrete zkSNARK schemes, i.e., Polaris, univariate polynomial encodings and Spartan, multivariate polynomial encodings, as examples to show our analysis. Secondly, we propose to select interpolating sets as subfields instead of affine spaces of a large field for Lagrange interpolation. This new method has improved the performance of R1CS encodings largely. We comment that post-quantum secure zkSNARKs yield post-quantum digital signatures with security only depending on symmetric-key schemes. Some open problems are proposed at the end of the paper.
The application of Internet of Vehicles (IoV) technology has greatly improved usersâ driving experience, but it also faces some challenges: 1) the central server is not powerful enough to support the rapid growth of IoV identity authentication requests and 2) there is a privacy leakage issue during vehicle authentication. To address these issues, we propose an anonymous authentication scheme based on trustworthy roadside unit group (TRUG)-PBFT main secondary chains and zero-knowledge proof (ZKP). First, to enhance authentication efficiency, we propose the TRUG-PBFT consensus algorithm. It improves the traditional PBFT by optimizing the PBFT consensus process, reducing the number of consensus nodes using fractional grouping, and selecting main node using verifiable random functions (VRFs). Second, we use a lattice-based ZKP scheme to achieve anonymous authentication of vehicles, and important data in the vehicle authentication process is stored by the main chain maintained by the base station group and the secondary chain maintained by the roadside unit group. Finally, experimental results demonstrate that compared to PBFT consensus, TRUG-PBFT in terms of consensus efficiency is improved by approximately 33%, and the authentication schemeâs computational cost is only 7.08 ms, superior to existing authentication schemes.
Preserving privacy in blockchain-based systems is crucial for ensuring anonymity and confidentiality during transactions. While cryptographic solutions can address on-chain privacy concerns, their implementation on blockchains may introduce performance overhead, which remains unclear to researchers and practitioners. This paper investigates the performance impact of integrating zero-knowledge proofs (ZKPs) into the widely adopted permissioned blockchain framework called Hyperledger Fabric. The study focuses on evaluating the scalability and bottleneck aspects of blockchain platforms incorporating ZKPs. Through comprehensive experimentation and analysis, the study reveals that the integration of ZKPs compromises performance in terms of transaction rates and latency, while effectively safeguarding usersâ personal information. Implementing on-chain ZKP feature would result in a performance loss of 30% to 87.5% in various experimental configurations in Hyperledger Fabric. The findings presented in this paper are informative for the design and implementation of blockchain-based systems with strict privacy requirements.
Open access
Blockchain Technology Applications and Security
Advanced Steganography and Watermarking Techniques
The Internet of Medical Things (IoMT) has emerged substantial growth within the healthcare sector, spurred by advancements in smart devices that generate and process critical healthcare data. Sharing this data among trusted healthcare entities is vital for efficient patient care but raises substantial security and privacy concerns. Existing solutions have focused on authentication techniques employing Self-Sovereign Identity (SSI) and Zero-Knowledge Proofs (ZKPs), aiming to ensure secure, auditable, and anonymous authentication. These solutions often prioritize either lightweight authentication or robust security, yet a flexible approach that integrates both characteristics is essential for adaptive cross-domain authentication in the IoMT landscape. Furthermore, the importance of lightweight authentication combined with adaptive verification, pivotal for scaling access control in cross-domain environments, has been underexplored in existing frameworks. Addressing this gap, we proposed a scheme called LSAC which is a lightweight, scalable, and anonymous authentication for SSI-based cross-domain authentication for IoMT setting. Our proposed LSAC scheme not only facilitates rapid and robust identity verification across multiple IoMT domains within a consortium blockchain network but also incorporates the advanced ZK-STARK and Plonk ZKP protocols to enable efficient and secure verification processes. By leveraging Hyperledger for generating smart contracts and managing user interactions across domains, our system represents a significant step forward in cross-domain authentication. Our comprehensive functionality and performance analysis confirms the effectiveness of our solution in providing scalable and secure access to IoMT resources, supporting the ongoing evolution of healthcare services.
In this thesis, the aim is to understand the possibilities and limitations of Zero Knowledge Proofs (ZKP) in blockchain technology. The first chapters focus on the presentation of distributed ledger systems and the tools that will be used, with particular reference to Remix, the IDE of choice for programming smart contracts in Solidity, and Sepolia, the Ethereum Testnet where the smart contracts were deployed. Subsequently, zero knowledge proofs are defined, their characteristics are explained, and the difference between interactive and non-interactive proofs is discussed; the latter will be emphasized as they are the most interesting in this context. The thesis then moves on to possible theoretical application contexts, with a particular focus on verifiable computation. Zokrates, a framework used to implement the non-interactive ZKP protocol, will be presented, explaining its language, features, functioning, and differences compared to other programming languages. A focal point for explaining how to implement verifiable computation will be introducing the various representations of an arithmetic circuit, fundamentally of textual and matrix types. Through various tests, the limitations of Zokrates and, to some extent, the entire arithmetic circuits sector for ZKP were highlighted. The thesis concludes with a possible implementation on the subject and an attack that this technology may be able to avoid.
Proposals for Ultra-Large-Scale-System (ULSS), particularly the gridâs energy management systems (EMSs), to adopt the Ethereum blockchain are increasing as its support for privacy-preserving, encrypted, decentralized computing via sharding, rollups, Smart-Contracts (SC), and Zero-Knowledge-proofs (ZK) address the increasing topological, behavioral, and data-processing challenges. In this context, the aggregation and verification of aggregated, ZK Kate-Zaverucha-Goldberg constant-sized polynomials commitments (KZG) are a bottleneck limiting deployment to Internet-of-Things (IoT) nodes used by the EMS due to high O(b G+blog2b F) computationincurred when aggregating or verifying by recreation. The alternative, expensive pairing checks involve two pairings, three exponentiations (Exp), three multiplications (Mul), and one addition (Add), a security factor S times for the n aggregated KZG. The proposed pairing checks significantly reduce costs for both: 1) Verifiers: two pairings, no Exp, one Mul, and one Add, and 2) Provers: one pairing check, no Exp, four Mul, and one Add. The aggregation method, based on multidimensional differential addition chains, costs only O(â) computation, where â is the bit length of the scalars. This approach demonstrates the feasibility of operating a KZG-centric blockchain with KZG rollups on IoT networks, marking a significant advancement in ULSS.
Abstract A zero-knowledge proof protocol is a cryptographic protocol in which a prover, who knows the witness to a statement, can convince a verifier that the statement is true without revealing any information about the witness. Although zero-knowledge proof protocols are typically executed on electronic computers, there is a line of research to design zero-knowledge proof protocols based on physical objects (e.g., a deck of cards). This is called physical zero-knowledge proof. In this paper, we construct a physical zero-knowledge proof protocol for a logical puzzle called Sukoro. Sukoro has many cells on the puzzle board, like Sudoku, where each cell must be empty or filled with a number from one to four, and each number must match the number of adjacent filled cells, and the same numbers must not be adjacent to each other. In addition, it has a rule that all filled cells must be connected, which is called the connectivity condition. Although some existing protocols deal with the connectivity condition, all existing methods are interactive , which requires the proverâs knowledge to determine how the cards are manipulated during the execution of the protocols. In this paper, we give a new method for verifying the connectivity condition in the non-interactive setting, which means that the protocol can be executed without the proverâs knowledge, and construct a physical zero-knowledge proof protocol for Sukoro.
Marijana SreÄkoviÄ, Dominik Hartmann, Thomas Preindl, Martin Kjäer ¡ 6 authors
Existing challenges in policy, practice, and digital innovation, and their integration into Circular Economy (CE) result in a complex undertaking. Currently, frameworks for the digital optimization of a buildingâs End-of-Life (EoL) and its related processes are mainly lacking. This paper explores the digitalization of the EoL process with blockchain technology, by analysing an applied Use Case of a closed loop reuse product in Austria. A blockchain based solution designed to enhance the verifiability of the reuse process is proposed, by introducing a semi-private zero-knowledge proof application which can increase, among other things, transparency and trust to promote Circular Economy.
Chunjie Guo, Lin You, Xingyu Li, Gengran Hu ¡ 6 authors
Biometric authentication is a very convenient and user-friendly method. The popularity of this method requires strong privacy-preserving technology to prevent the disclosure of template information. Most of the existing privacy protection technologies rely on classic encryption techniques, such as homomorphic encryption, which incur huge system overhead and cannot be popularized. To address these issues, we propose a novel biometric authentication scheme with privacy protection based on support vector machine and zero knowledge proof (BioAuâSVM+ZKP). BioAuâSVM+ZKP allows users to authenticate themselves to different service providers without disclosing any biometric template information. The evidence is generated through the zero-knowledge proof utilizing polynomial commitments. Our approach for generating a unique and repeatable biometric identifier from the userâs fingerprint image leverages the multi-classification property of SVM. Notably, our scheme not only reduces the communication overhead but also provides the privacy protection features. Besides, the communication overhead of BioAuâSVM+ZKP is constant. We have simulated the authentication scheme on the common dataset NIST, analyzed the performance and proved the security.
Open access
Biometric Identification and Security
User Authentication and Security Systems
Advanced Steganography and Watermarking Techniques
Changxu Liu, Hao Zhou, Patrick Dai, Li Shang ¡ 5 authors
Multi-Scalar Multiplication (MSM) is a computationally intensive task that operates on elliptic curves based on GF(P) . It is commonly used in zero-knowledge proof (ZKP), where it accounts for a significant portion of the computation time required for proof generation. In this article, we present PriorMSM, an efficient acceleration architecture for MSM. We propose a Priority-Based Scheduling Mechanism (PBSM) based on a multi-FIFO and multi-bank architecture to accelerate the implementation of MSM. By increasing the pairing success rate of internal points, PBSM reduces the number of bubbles in the pipeline of point addition (PADD), consequently improving the data throughput of the pipeline. We also introduce an advanced parallel bucket aggregation algorithm, leveraging PADDâs fully pipelined characteristics to significantly accelerate the implementation of bucket aggregation. We perform a sensitivity analysis on the crucial parameter of window size in MSM. The results indicate that the window size of the MSM significantly impacts its latency. Area-Time Product (ATP) metric is introduced to guide the selection of the optimal window size, balancing the performance and cost for practical applications of subsequent MSM implementations. PriorMSM is evaluated using the TSMC 28 nm process. It achieves a maximum speedup of 10.9Ă compared to the previous custom hardware implementations and a maximum speedup of 3.9Ă compared to the GPU implementations.
Sizai Hou, Songze Li, Tayyebeh Jahani-Nezhad, Giuseppe Caire
Federated learning (FL) has recently gained significant momentum due to its potential to leverage large-scale distributed user data while preserving user privacy. However, the typical paradigm of FL faces challenges of both privacy and robustness: the transmitted model updates can potentially leak sensitive user information, and the lack of central control of the local training process leaves the global model susceptible to malicious manipulations on model updates. Current solutions attempting to address both problems under the one-server FL setting fall short in the following aspects: 1) designed for simple validity checks that are insufficient against advanced attacks (e.g., checking norm of individual update); and 2) partial privacy leakage for more complicated robust aggregation algorithms (e.g., distances between model updates are leaked for multi-Krum). In this work, we formalize a novel security notion of aggregated privacy that characterizes the minimum amount of user information, in the form of some aggregated statistics of users' updates, that is necessary to be revealed to accomplish more advanced robust aggregation. We develop a general framework PriRoAgg, utilizing Lagrange coded computing and distributed zero-knowledge proof, to execute a wide range of robust aggregation algorithms while satisfying aggregated privacy. As concrete instantiations of PriRoAgg, we construct two secure and robust protocols based on state-of-the-art robust algorithms, for which we provide full theoretical analyses on security and complexity. Extensive experiments are conducted for these protocols, demonstrating their robustness against various model integrity attacks, and their efficiency advantages over baselines.
Federated learning (FL) enables distributed clients to privately train machine learning models using their own local data, thus avoiding the security risk of directly exchanging private data between clients and servers. However, there is a risk in federated learning: a malicious party may launch a reverse attack based on the parameters uploaded by the client to analyze the attributes of the clientâs local private data. Some studies use the Shamir secret sharing method and zero-knowledge proofs (ZKP) to ensure the privacy and integrity of the inputs in FL. However, the Shamir secret sharing scheme often requires an optimistic guarantee on the number of malicious clients, which cannot obtain a sufficient number of secret slices through collusion, and the general ZKP scheme requires the clients to compute the proof belongs to others during the proof and verification stages, and its efficiency needs to be improved. In this paper, we propose VSSPFL method to achieve efficient and secure data collaboration, which improves the Shamir secret sharing scheme to prevent reverse attacks by an unknown number of malicious clients and reduces the cost of ZKP by using a probabilistic integrity check method.
A connected loopless graph is 2-edge-connected if it remains connected after the removal of at most one of its edges. Many combinatorial optimization problems seek, for a given graph with costs on its edges, a spanning subgraph satisfying certain connectivity constraints. The minimum 2-edge-connected spanning subgraph problem (2-ECSSP) is a problem of this type. It can be formulated as an integer linear program that selects edges of minimum total cost satisfying the restriction that every cut of the given graph is covered by at least two of the selected edges. This problem is known to be NP-hard. This thesis develops rounding algorithms for three variants of 2-ECSSP, focusing on rounding half-integral solutions of the corresponding linear relaxation. This family of solutions often yields the largest known integrality ratio for various subproblems of 2-ECSSP. The first problem we investigate is the half-integral 2-ECSSP with unrestricted costs. We develop a novel 5/3-rounding that, to the best of our knowledge, is the first one with a factor better than 2. Moreover, we design a reduction scheme, restricting the problem to 4-edge-connected graphs with maximum degree at most five. Then, we study the matching augmentation problem (MAP), a subproblem of 2-ECSSP in which the edge costs are either 0 or 1 and the zero cost edges define a matching. We survey a better-than-2-approximation, obtained in 2022 by Bamas, Drygala, and Svensson, presenting a comprehensive proof of their result and determining an improved factor. Additionally, we address conjectures posed in their work and present computational experiments to support our findings. Finally, we discuss the 2-edge-connected spanning multisubgraph problem (2-ECSMP), a variation of 2-ECSSP in which multiple copies of the same edge can be selected. We survey a recent work by Boyd et al. on a 4/3-rounding for the half-integral 2-ECSMP and leverage their techniques to prove novel decomposition theorems for 4-regular 4-edge-connected graphs. Finally, we pose two conjectures concerning extensions of the decomposition results, suggesting new research directions.