Preql is a no-code data transformation solution built for business users. Check us out at preql.com!

Preql

This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license.
Authors:
(1) U Jin Choi, Department of mathematical science, Korea Advanced Institute of Science and Technology & ujchoi@kaist.ac.kr;
(2) Kyung Soo Rim, Department of mathematics, Sogang University & ksrim@sogang.ac.kr. Table of Links Introduction
Organization and notation
Problem Setting and Preliminaries
Generalized Wiener algebra and Fréchet derivative
Characterization of coefficients
Coefficients from an ergodic process
Conclusion & References 3. Problem Setting and Preliminaries. This section will set the mathematical model that is being addressed and provide basic background information relevant to understanding it. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. Authors: (1) U Jin Choi, Department of mathematical science, Korea Advanced Institute of Science and Technology & ujchoi@kaist.ac.kr; (2) Kyung Soo Rim, Department of mathematics, Sogang University & ksrim@sogang.ac.kr. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. Authors: Authors: (1) U Jin Choi, Department of mathematical science, Korea Advanced Institute of Science and Technology & ujchoi@kaist.ac.kr; (2) Kyung Soo Rim, Department of mathematics, Sogang University & ksrim@sogang.ac.kr. Table of Links Introduction Organization and notation Problem Setting and Preliminaries Generalized Wiener algebra and Fréchet derivative Characterization of coefficients Coefficients from an ergodic process Conclusion & References Introduction Introduction Organization and notation Organization and notation Problem Setting and Preliminaries Problem Setting and Preliminaries Generalized Wiener algebra and Fréchet derivative Generalized Wiener algebra and Fréchet derivative Characterization of coefficients Characterization of coefficients Coefficients from an ergodic process Coefficients from an ergodic process Conclusion & References Conclusion & References 3. Problem Setting and Preliminaries. This section will set the mathematical model that is being addressed and provide basic background information relevant to understanding it.

Variational Non-Bayesian Inference: Problem Setting and Preliminaries

Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal: Preliminaries

This paper is under CC 4.0 license. available on arxiv Authors: (1) Kota Chin, University of Tsukuba, National Institute of Information and Communications Technology Japan; (2) Keita Emura, Kanazawa University, Japan National Institute of Information and Communications Technology Japan; (3) Kazumasa Omote, University of Tsukuba National Institute of Information and Communications Technology Japan. Table of Links Abstract & Introduction Preliminaries Proposed Anonymous Yet Accountable Contract Wallet System Implementation Conclusion & References II. PRELIMINARIES A. Accountable Ring Signatures As a generalization of ring signatures [29] and group signatures [13], Xu and Yung proposed accountable ring signatures [34]. Briefly, as in ring signatures, each user generates their own public key pk and secret key sk. This decentralized structure matches blockchain systems. An opener has a public key opk and a secret key osk. When a user who has (pk,sk) generates a ring signature Σ on a message M, the user selects a set of public keys, which we refer to as ring R, and we assume that pk ∈ R, and selects the opener by indicating opk. We say that (Σ, M) is valid if the signer is a member of R, i.e., there exists pk ∈ R for which the corresponding sk has been used to generate Σ. As in group signatures, the designated opener can trace the signer using osk. Moreover, the opening algorithm produces a proof π proving that Σ is generated by sk corresponding to pk ∈ R. We introduce the syntax defined by Bootle et al. [10] as follows. Definition 1 (Syntax of Accountable Ring Signatures [10]): • Setup(1λ ): The setup algorithm takes the security parameter λ ∈ N as input and outputs the common parameter pp. • OKGen(pp): The opener key generation algorithm takes pp as input and outputs the opener public and secret keys opk and osk, respectively. • UKGen(pp): The user key generation algorithm takes pp as input and outputs the user public verification key pk and user secret signing key sk. • RSign(opk, M, R,sk): The signing algorithm takes opk, a message M to be signed, a ring R, and sk as inputs and outputs a ring signature Σ. Here, R is a set of user public keys and the pk corresponding to sk is assumed to be pk ∈ R. • RVerify(opk, M, R, Σ): The verification algorithm takes opk, M, R, and Σ as inputs and outputs 1 (accept) or 0 (reject). • Open(M, R, Σ, osk): The open algorithm takes as M, R, Σ, and osk as inputs and outputs pk ∈ R of the signer and its proof π or ⊥ otherwise. • Judge(opk, M, R, Σ, pk, π): The judge algorithm takes opk, M, R, Σ, pk, and π as inputs and outputs 0 if RVerify(opk, M, R, Σ) = 0; otherwise, it outputs 1 to indicate that Σ is generated by sk corresponding to pk, and 0 otherwise. We require correctness holds where an honestly generated signature is always valid (the RVerify algorithm outputs 1), and a proof generated by the Open algorithm against the signature and corresponding verification key is always accepted by the Judge algorithm. Bootle et al. defined full unforgeability, anonymity, traceability, and tracing soundness, which are briefly explained as follows. Refer to the literature [10] for details on these security definitions. • Full Unforgeability: It ensures that no adversary A (who may control the opener) can falsely accuse an honest user of creating a ring signature, nor A can forge a ring signature on behalf of an honest ring. • Anonymity: It ensures that no adversary A (who does not have osk) can identify the signer, i.e., a signature does not reveal the identity of the ring member who generated it. • Traceability: It ensures that no adversary A can produce a signature that is valid but untraceable. • Tracing Soundness: It ensures that no adversary A can produce proofs for a signature that are accepted by the Judge algorithm for different verification keys. Some studies have employed accountable ring signatures in blockchain systems [19], [31] due to its decentralized structure. In addition, Qiao et al. [28] removed the opening functionality from group signatures to reduce its centralized structure; however, it still has a centralized structure because a group manager issues signing keys to the group members unlike to (accountable) ring signatures. Linkable ring signatures [8], [23], [24] have been employed to provide a pseudonymity level privacy protection. As mentioned previously, this is insufficient; thus, anonymity level privacy protection is desirable. Delegatable anonymous credentials (DAC) [12] have been employed for eKYC systems [9], [32], where KYC stands for Know-Your-Customer. However, DACs are not applicable in the proposed system because they do not provide tracing functionality. Connolly et al. [14] proposed a revocable and auditable anonymous credential scheme called Protego, and they considered its application to Hyperledger Fabric. Although it might be employed in the proposed system, Connolly et al. only considered permissioned blockchains. Thus, accountable ring signatures are employed in the proposed system. B. Layer 2 Ethereum is widely recognized as providing high security as a smart contract-enabled blockchain. However, in terms of ensuring security and providing a distributed structure, there is room for improvement regarding scalability. Concretely, the number of transactions that can be processed within a certain time period is less than that of other blockchain systems. Thus, transaction fees (gas costs) will increase when many EOAs want to issue transactions. To solve this problem, we can issue a transaction off-chain, and the proof that the transaction is generated correctly, is only stored on the Ethereum blockchain. In this case, the blockchain and off-chain are referred to as Layer 1 (L1) and Layer 2 (L2), respectively. For example, when a Merkle tree is used to generate a hash chain, the proof that the hash chain satisfies the Merkle tree is stored in L1. To reduce the proof size stored in L1, the zk-STARK (zeroknowledge Scalable Transparent ARgument of Knowledge) [6] or zk-SNARK (zero-knowledge Succinct Non-interactive ARguments of Knowledge) [21], [27] are employed. zkSync [3] is an Ethereum L2 network technology that supports zk-SNARK. The goal of L2 technologies to provide the same execution environment of Ethereum (i.e., the EVM: Ethereum Virtual Machine), and zkSync nearly supports the same execution environment of Ethereum, i.e., it is EVMcompatible and can run a smart contract programed by Solidity. Thus, we can utilize Ethereum ecosystem tools, and smart contracts on zkSync are described by Solidity. This means that the proposed system can be used directly when Ethereum supports account abstraction. C. Account Abstraction In the following, we describe account abstraction. A user sends the code of a contract wallet to nodes that support account abstraction, and requests to its deployment. Note that the user does not need to be an issuer of a transaction. After deploying the contract wallet, an issuer sends transaction data to blockchain via nodes. Finally, the contract wallet runs the transaction according to the rule described in the code. We illustrate the flow of transaction issuing when account abstraction is/is not employed in Figure 3 and Figure 4. Here, the issuer (User (EOA)) communicates with nodes, their IP address is known by nodes which break anonymity trivially. Thus, we exclude the nodes in our anonymity requirement.[6] [6] This restriction can be removed if a user (who issued a transaction) prepares a node. However, currently only a test net su

Anonymous, Accountable Contract Wallet System With Account Abstraction: Preliminaries

This paper is available on arxiv under CC BY-SA 4.0 DEED license. Authors: (1) Tomáš Jakl, Czech Academy of Sciences and Czech Technical University; (2) Dan Marsden, School of Computer Science University of Nottingham; (3) Nihil Shah, Department of Computer Science University of Oxford. Table of Links Abstract & Introduction Prelimenaries FVM Theorems for Positive Existential Fragments FVM Theorems for Counting Logic FVM Theorems for The Full Logic Abstract FVM Theorems for Products Adding Equality and Other Enrichment Conclusions, Acknowledgments & References Appendix A FVM theorems for coproducts Appendix B Proofs Omitted from Section III Appendix C Proofs Omitted from Section IV Appendix D Proofs Omitted from Section V Appendix E Proofs Omitted from Section VI Appendix F Proofs Omitted from Section VII II. PRELIMINARIES A. Categories of Relational Structures We assume the basic definitions of category theory, including categories, functors and natural transformations, as can be found in any standard introduction such as [29] or [30]. Background on comonads, and any less standard material is introduced as needed. troduced as needed. A relational signature σ is a set of relation symbols, each with an associated strictly positive natural number arity. A σstructure A consists of a universe set, also denoted A, and for each relation symbol R ∈ σ of arity n, an n-ary relation RA on A. A morphism of σ-structures f : A → B is a function of type A → B, preserving relations, in the sense that for n-ary R ∈ σ For a fixed σ, σ-structures and their morphisms form our main category of interest R(σ). We will also have need of the category of pointed relational structures R∗(σ). Here the objects (A, a) are a σ-structure A with a distinguished element a ∈ A. The morphisms are σ-structure morphisms that also preserve the distinguished element. B. Comonads The intuition for each of these comonads is that they encode the moves within one structure during the corresponding model comparison game. We shall introduce their mathematical properties as needed in later sections. See [11] for detailed discussions of all three comonads.

A Categorical Account of
Composition Methods in Logic: Prelimenaries

This paper is available on arxiv under CC 4.0 license. Authors: (1) Jeffrey Ouyang-Zhang, UT Austin (2) Daniel J. Diaz, UT Austin (3) Adam R. Klivans, UT Austin (4) Philipp Krähenbühl, UT Austin Table of Links Abstract & Introduction Related Works Preliminary Methodology Results Limitations Conclusion, Acknowledgements, & References Experimental Setting & Additional Results 3 Preliminary

Predicting a Protein’s Stability
under a Million Mutations: Preliminary

This paper is under CC 4.0 license. available on arxiv Authors: (1) Tariq Bontekoe, University of Groningen; (2) Dimka Karastoyanova, University of Groningen; (3) Fatih Turkmen, University of Groningen. Table of Links Abstract & Introduction Preliminaries Zero-knowledge proofs and verifiable computing Privacy-preserving computations Requirements: an application’s perspective Verifiable, privacy-preserving computing Open challenges and future directions Conclusion & References 2. Preliminaries This section provides background on DLTs and methods for decentralized computation. Next to this, we provide an overview of the most common threat models used to describe cryptographic solutions for verifiable or privacypreserving computations. 2.1. DLTs and decentralized computations DLTs describe the collection of technologies where a (large) number of parties collectively create, maintain, and agree on a shared state or ledger. The shared state can be known completely to all parties, but can also be spread out over the respective parties. A well-known example of a DLT is blockchain, where all parties agree — via some predetermined consensus mechanism — on a public ledger containing the full state of a system. Blockchain is best known for realizing decentralized currencies such as Bitcoin [10], or smart contract systems like Ethereum [11]. However, DLTs, and specifically blockchains, also have applications in many other domains: from identity management [12] (e.g., self-sovereign identity (SSI)) to healthcare [13]. We specifically observe the proliferation of decentralized apps (or dApps), each of which can be seen as a blockchainbased autonomous application, whose behavior is defined by a collection of scripts (or smart contracts). In lockstep with an increasing number of dApps, we also observe an increase in using DLT for decentralized computations. Such decentralized computations can be applied in a DLT setting, but more importantly to any situation where multiple parties wish to perform a group computation. In this case, group computation can refer to: (1) a single computation on distributed data; (2) a decentralized computation on centrally stored data; (3) a combination of the first two. Decentralized computation becomes especially of interest when privacy of data or computation has to be taken into consideration. Examples of decentralized computation use cases that take privacy into account can be found in literature on outsourced computations, MPC, federated learning (FL), and DLTs. In subsequent sections, we will see that both DLTs and MPC are often used as base building blocks for realizing decentralized, verifiable, privacypreserving computation schemes. To analyze the privacy and security guarantees provided by those schemes, we also require an understanding of relevant threat models. 2.2. Threat models We informally describe the three most common security models regarding the possible behavior of the parties that have been corrupted by the adversary. For a more detailed treatment of the topic, we refer the reader to e.g., [14]: • Semi-honest adversaries: In this scenario, also known as the honest-but-curious or passive model, corrupted parties do not deviate from the selected protocol. The adversary does have access to all data received and owned by the corrupted parties, and tries to deduce as much as possible from this. • Malicious adversaries: In the malicious or active setting, the adversary can make corrupted parties deviate from the protocol in any way. A protocol is secure if it can prevent any malicious adversary from breaking security or privacy. When a protocol not only prevents cheating but also allows for determining who cheated, the protocol is said to support cheater detection, e.g., [15]. • Covert adversaries: Corrupted parties show the same behavior as in the malicious model. However, honest parties need only detect cheating parties with a given probability. In practice, it is assumed that the risk of getting caught and receiving a financial or reputation penalty is sufficient to deter an adversary. The notion of covert security with public verifiability was introduced in [16]. With public verifiability, not only can honest parties detect cheating with some probability, they can also construct a publicly verifiable certificate proving that a certain party has cheated, without revealing information on the private data of any honest party.

Verifiable Privacy-Preserving Computing: Preliminaries

This paper is available on arxiv under CC 4.0 license. Authors: (1) Ruta Jawale; (2) Dakshita Khurana. Table of Links Abstract and Introduction Technical Overview Preliminaries Unclonable Non-Interactive Zero-Knowledge in the CRS Model Unclonable NIZK in the Quantum Ramdon Oracle Model Unclonable Signatures of Knowledge References 3 Preliminaries 3.1 Post-Quantum Commitments and Encryption (Post-Quantum Commitments). Com is a post-quantum commitment scheme if it has the following syntax and properties. Definition 3.1 Syntax. • c ← Com(m; r): The polynomial-time algorithm Com on input a message m and randomness r ∈ {0, 1} r(λ) outputs commitment a c. Properties. (Post-Quantum Commitment). [LS19] Assuming the polynomial quantum hardness of LWE, there exists a non-interactive commitment with perfect binding and computational hiding (Definition 3.1). Theorem 3.2 (Post-Quantum Public-Key Encryption). (Gen, Enc, Dec) is a post-quantum publickey encryption scheme if it has the following syntax and properties. Definition 3.3 Syntax. • (pk,sk) ← Gen(1λ ): The polynomial-time algorithm Gen on input security parameter 1 λ outputs a public key pk and a secret key sk. • c ← Enc(pk, m; r): The polynomial-time algorithm Enc on input a public key pk, message m and randomness r ∈ {0, 1} r(λ) outputs a ciphertext c. • m ← Dec(sk, c): The polynomial-time algorithm Dec on input a secret key sk and a ciphertext c outputs a message m. Properties. 3.2 Sigma protocols Definition 3.4 (Post-Quantum Sigma Protocol for NP). [LZ19] Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N. Π = (P = (P.Com, P.Prove),V = (V.Ch,V.Ver)) is a post-quantum sigma protocol if it has the following syntax and properties. . The input 1 λ is left out when it is clear from context. Syntax • (α,st) ← P.Com(1λ , x, w): The probabilistic polynomial-size circuit on input an instance and witness pair (x, w) ∈ Lλ outputs a commitment α and an internal prover state st. P.Com • β ← V.Ch(1λ , x, α): The probabilistic polynomial-size circuit V.Ch on input an instance x outputs a uniformly random challenge β. • γ ← P.Prove(1λ , x, w,st, β): The probabilistic polynomial-size circuit on input an instance and witness pair (x, w) ∈ Lλ, an internal prover state st, and a challenge β outputs the partial opening (to α as indicated by β) γ. P. Prove • (1λ , x, α, β, γ) ∈ {0, 1}: The probabilistic polynomial-size circuit V.Ver on input an instance x, a commitment α, a challenge β, and a partial opening γ outputs 1 iff γ is a valid opening to α at locations indicated by β. V. Ver Properties. . For every λ ∈ N and every (x, w) ∈ Rλ, • Perfect Completeness There exists a quantum polynomial-size circuit Sim and a negligible function negl(·) such that for every polynomial-size quantum circuit D, every sufficiently large λ ∈ N, and every (x, w) ∈ Rλ, • Computational Honest-Verifier Zero-Knowledge with Quantum Simulator. • Unpredictable Commitment. There exists a negligible function such that for every sufficiently large λ ∈ N and every (x, w) ∈ Rλ, negl(·) We note that the unpredictable commitment property in the definition above may appear to be an unusual requirement, but this property is w.l.o.g. for post quantum sigma protocols as shown in [LZ19]. In particular, any sigma protocol which does not have unpredictable commitments, can be modified into one that does: the prover can append a random string r to the end of their commitment message α, and the verifier can ignore this appended string r when they perform their checks. 3.3 NIZKs in the CRS model We consider the common reference string model. Definition 3.5 (Post-Quantum (Quantum) NIZK for NP in the CRS Model). Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N is a non-interactive post-quantum (quantum) zero-knowledge argument for in the CRS model if it has the following syntax and properties. Π = (Setup, P,V) NP Syntax. The input 1 λ is left out when it is clear from context. • ← Setup(1λ ): The probabilistic polynomial-size circuit Setup on input 1 λ outputs a common reference string crs. crs • π ← P(1λ , , x, w): The probabilistic (quantum) polynomial-size circuit P on input a common reference string crs and instance and witness pair (x, w) ∈ Rλ, outputs a proof π. crs • V(1λ , , x, π) ∈ {0, 1}: The probabilistic (quantum) polynomial-size circuit V on input a common reference string , an instance x, and a proof π outputs 1 iff π is a valid proof for x. crs crs Properties. For every λ ∈ N and every (x, w) ∈ Rλ, • Perfect Completeness. There exists a negligible function such that for every polynomial-size quantum circuit A and every sufficiently large λ ∈ N, • Adaptive Computational Soundness. negl(·) There exists a probabilistic (quantum) polynomial-size circuit Sim = ( ) and a negligible function such that for every polynomial-size quantum circuit A, every polynomial-size quantum circuit D, and every sufficiently large λ ∈ N, • Adaptive Computational Zero-Knowledge. Sim0, Sim1 negl(·) (Post-Quantum NIZK argument for NP in the CRS Model). [PS19] Theorem 3.6 Assuming the polynomial quantum hardness of LWE, there exists a non-interactive adaptively computationally sound, adaptively computationally zero-knowledge argument for NP in the common reference string model (Definition 3.5). (Post-Quantum (Quantum) Simulation-Sound NIZK for NP in CRS Model). Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N Definition 3.7 Π = ( ) is a post-quantum (quantum) non-interactive simulation-sound, adaptive multi-theorem computational zero-knowledge protocol for in the CRS model if it has the following syntax and properties. Setup, P,V NP • Π is a post-quantum (quantum) non-interactive zero-knowledge argument for in the model (Definition 3.5). NP CRS • Adaptive Multi-Theorem Computational Zero-Knowledge. [FLS90] There exists a probabilistic (quantum) polynomial-size circuit Sim = ( ) 1 and a negligible function such that for every polynomial-size quantum circuit A, every polynomial-size quantum circuit D, and every sufficiently large λ ∈ N, Sim0, Sim1 negl(·) [Sah99, SCO+01] Let Sim = (Sim0, Sim1) be the simulator given by the adaptive multi-theorem computational zero-knowledge property. There exists a negligible function negl(·) such that for every oracle-aided polynomial-size quantum circuit A and every sufficiently large λ ∈ N, • Simulation Soundness. where is the list of queries from to Q A Sim1. REMARK 3.1. In Definition 3.7, adaptive multi-theorem computational zero-knowledge implies adaptive computational zero-knowledge. REMARK 3.2. As defined in Definition 3.7, a simulation-sound zero-knowledge protocol has adaptive computational soundness (Definition 3.5). (Simulation Sound Compiler). [SCO+01] Given one-way functions and a single-theorem NIZK proof system for NP, then there exists a non-interactive simulation sound, adaptively multi-theorem computationally zero-knowledge proof for NP in the common reference string model (Definition 3.7). Theorem 3.8 (Post-Quantum Simulation Sound NIZK for NP). Assuming the polynomial quantum hardness of LWE, there exists a post-quantum non-interactive simulation sound, adaptively multi-theorem computationally zero-knowledge proof for NP in the common reference string model (Definition 3.7). Corollary 3.9 . This follows from Theorem 3.6 and Theorem 3.8. Proof 3.4 NIZKs in the QRO model We now consider the quantum random oracle model. For sake of completeness, we briefly outline a definition for a quantum random oracle. A quantum random oracle O is a random function which support quantum queries and allows for the following accesses: Definition 3.10. On input a message, O outputs a uniformly random value. This is the usual access provided. When quantum access may be invoked, we denote the oracle as |O. • Query Access. Given programmability access, O can be set to output a specified value on a specified input. An arbitrary number of distinct points can be programmed. • Programmability Access. Given extractability access, specific queries to |O can be read. • Extractability Access. Definition 3.11 ((Quantum) Post-Quantum for in QROM). [LZ19] Let O be a random oracle. Let NP relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N. NIZKPoK NP Π = ( ) is a (quantum) non-interactive zero-knowledge proof of knowledge protocol with respect to a random oracle if it has the following syntax and properties. P,V Syntax. The input 1 λ is left out when it is clear from context. Properties. • Perfect Completeness. For every λ ∈ N and every (x, w) ∈ Rλ, There exists a quantum polynomial-size circuit Sim which ignores its second input and a negligible function such that for every oracle-aided polynomial-size quantum circuit D which is limited to making queries (x, ω) ∈ Rλ on input 1 λ , and every sufficiently large λ ∈ N, • Zero-Knowledge with Quantum Simulator. negl(·) • Proof of Knowledge with Quantum Extractor. There exists an oracle-aided quantum polynomial-size circuit extractor Ext that simulates a random oracle |O , a constant c, a polynomial p(·), and negligible functions negl0 (·), negl1 (·) such that for every polynomial-size quantum circuit A and every x with associated λ ∈ N satisfying Exti (NIZKPoK in QROM [Unr17, LZ19]). Let Π be a post-quantum sigma protocol (Definition 3.4). The Fiat-Shamir heuristic applied to Π yields a classical post-quantum NIZKPoK in the QROM (Definition 3.11). Theorem 3.12 3.5 Quantum Money (Public Key Quantum Money Mini-Scheme). [AC13, Zha19b] (Gen,Ver) is a public key quantum money scheme if it has the following syntax and properties. Definition 3.13 Syntax. Properties. (Quantum Money from Subspace Hiding Obfuscation [AC13, Zha19b]). Theorem 3.14 If injective one-way functions and post-quantum iO exist, then public-key quantum money exists (Definition 3.13). (Public Key Quantum Money Mini-Scheme in QROM). ( ) is a public key quantum money scheme with respect to a quantum random oracle O if it has the following syntax and properties. Definition 3.15 Gen, Ver Syntax. Properties The unpredicable serial number property is w.l.o.g., just as above. 3.6 Quantum Signature of Knowledge Definition 3.16 (Quantum SimExt-secure Signature [CL06]). Let relation R with corresponding language L be given such that they can be indexed by a security parameter λ ∈ N. Let a message space M be given such that it can be indexed by a security parameter λ ∈ N. NP ( ) is a SimExt-secure quantum signature of knowledge of a witness with respect to L and M if it has the following syntax and properties. Syntax. The input 1 λ is left out when it is clear from context. Setup, Sign, Verify • ( ) ← Setup(1λ ): The probabilistic polynomial-time algorithm Setup on input 1 λ outputs a common reference string and a trapdoor td. crs, td crs • σ ← (1λ , , x, w, m): The polynomial-time quantum algorithm Sign on input a common reference string , an instance and witness pair (x, w) ∈ Rλ, and a message m ∈ Mλ, outputs a signature σ. Sign crs crs • (1λ , crs, x, m, σ) ∈ {0, 1}: The polynomial-time quantum algorithm Verify on input a common reference string crs, an instance x, a message m ∈ Mλ, and a signature σ, outputs 1 iff σ is a valid signature of m with respect to crs, Rλ, and x. Verify Properties.

Unclonable Non-Interactive Zero-Knowledge: Preliminaries

This paper is available on arxiv under CC BY 4.0 DEED license. Authors: (1) Zhipeng Wang, Department of Computing, Imperial College London; (2) Nanqing Dong Department of Computer Science, University of Oxford; (3) Jiahao Sun, Data Science Institute, Imperial College London; (4) William Knottenbelt, Department of Computing, Imperial College London. TABLE OF LINKS Abstract & Introduction Related Work & Preliminaries Methodology Theoretical and Empirical Analysis Results Conclusion & References Related Work Zero-Knowledge Proofs. Zero-knowledge proofs (ZKPs) have emerged as a revolutionary cryptographic concept that allows one party (the prover) to demonstrate the truth of a statement to another party (the verifier) without revealing any information beyond the statement’s validity [12]. One of the most notable applications of ZKPs is in privacy-preserving authentication, where a user can prove to a aggregator that they know a secret without revealing the secret itself. ZKPs have also been applied in other areas, including blockchains [28,30], machine learning [22,31,9] and FL [6]. However, existing research, such as RoFL [6,21], has predominantly focused on using ZKPs to address malicious client behaviors or enhance the client privacy, while assuming the existence of a “honest-butcurious” (i.e., semi-honest) aggregator. In this work, we break away from this assumption and leverage ZKPs to ensure the honest aggregation of the centralized aggregator without requiring trust in the aggregator itself. Blockchain-based Federated Learning. Blockchain is a decentralized and immutable distributed ledger technology [15,10,4] that underpins cryptocurrencies such as Bitcoin [25] and Ethereum [33]. It provides a secure and transparent way to record and verify transactions across a network of nodes. Blockchain has been integrated with FL to tackle the security and privacy issues in existing FL [34,16,27,19,32]. Specifically, blockchain is used to store and manage the training model’s updates and the associated metadata securely and transparently. Instead of relying solely on a centralized aggregator to manage the model updates, the blockchain enables a decentralized and distributed consensus mechanism among the participating clients. However, existing blockchain-based FL designs [8] rely heavily on the computation of smart contracts (i.e., self-executing programs that run on a blockchain network and are triggered by blockchain events), which will cause expensive costs for FL networks with a large number of parameters. In our work, we address the scalability issue of blockchain-based FL by using zero-Knowledge proofs. Preliminaries In this section, we present the cryptographic building blocks for our zkFL system. Commitments. A commitment scheme enables an entity to conceal a value while committing to it, with the ability to disclose the value at a later time if desired. The commitment scheme typically comprises two rounds: the committing round and the revealing round. In the committing round, the client commits to specific values while ensuring their confidentiality from others. The client retains the option to reveal the committed value in the subsequent revealing round. A commitment scheme includes two algorithms: cm ← Commit(m, r) accepts a message m and a secret randomness r as inputs and returns the commitment cm. 0/1 ← Verify(m, r, cm) accepts a message m, a commitment cm and a decommitment value r as inputs, and returns 1 if the commitment is opened correctly and 0 otherwise. In this paper, we leverage Pedersen commitments [26,1] to compute the clients’ commitments/encryption on their local training model updates. Specifically, given the model update wi , a client will encrypt the update by computing Enc(wi) = g wi · h si , where g and h are public parameters and si is a random number generated by the client. Zero-Knowledge Proof Zero-knowledge proof [18,11,29] is a cryptographic primitive that allows a prover to convince the verifier about the correctness of some assertions without providing any meaningful information to the verifier. A zeroknowledge proof of some statement satisfies the following three properties: Completeness: If the statement st is true, an honest verifier will always be convinced by an honest prover. Soundness: For false statements, a prover cannot convince the verifier (even if the prover cheats and deviates from the protocol). Zero-knowledge: No verifier learns anything other than the fact that st is valid if it is true. In other words, knowing the statement, but not the secret, is enough to construct a scenario in which the prover knows the secret. A zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARK) is a “succinct” non-interactive zero-knowledge proof (NIZK) for arithmetic circuit satisfiability. The construction of zk-SNARK is based on a field F and an arithmetic circuit C. An arithmetic circuit satisfiability problem of a circuit C : F n × F h → F l is captured by the statement stC : {(x,wit) ∈ F n × F h : C(x,wit) = 0l}, with the language LC = {x ∈ F n | ∃ wit ∈ F h s.t. C(x,wit) = 0 l}. Apart from correctness, soundness, and zero-knowledge properties of zeroknowledge proof, a zk-SNARK requires two additional properties, i.e., succinctness and simulation extractability [12,2]. System and Threat Models In this section, we outline our system model, threat model, and system goals. System Model In the context of FL, clients represent individual devices, such as smartphones, tablets, or computers, each possessing its local dataset. These datasets remain secure and never leave the clients’ devices. Instead, the clients independently train their machine learning models on their local data and communicate only the model updates to the central aggregator. Clients: The aggregator acts as a central entity responsible for aggregating these model updates from multiple clients and computing a global model. This global model is then sent back to the clients, ensuring that each client benefits from the collective knowledge of the entire network while preserving data privacy and security. Aggregator: Threat Model We consider a malicious aggregator that can choose not to honestly aggregate the local model updates from clients. The malicious aggregator can deviate from the protocol by: Abandoning the updates generated from one or several honest clients. Creating fake model updates to replace the updates generated from honest clients Inserting fake model updates to the updates generated from honest clients. We would like to remark that the scope of this work centers around the malicious aggregator rather than the honest-but-curious one, with a specific emphasis on ensuring aggregation integrity. We also acknowledge the potential for the aggregator to carry out model inversion attacks on the clients, a topic we intend to delve into in a future study. System Goals The aggregator cannot abandon or replace the local model updates generated from honest clients, nor insert any fake model updates into the final aggregated model update. Otherwise, the clients will detect the malicious behaviors of the aggregator and halt the FL training process. Security: Only the participants (i.e., the aggregator and clients) in the FL system can know the aggregated model updates during each round. Privacy:

Preql

preql.com

11-50 employees

Since 2022

COMPANY RANKING

PREQL

EVERGREEN INDEX #8904

Preql WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!

Preql

preql.com

11-50 employees

Since 2022

COMPANY RANKING

PREQL

EVERGREEN INDEX #8904

RELATED COMPANIESRANK

STORIES ABOUT PREQL

Preql WIKI

Apply to get your Tech Company News Page live on HackerNoon.com today!