Aggregated Set Membership Proofs Aggregated Signature-Based Set Membership Proofs and im- plementation in Client and Server Verifiable Additive Homo- morphic Secret Sharing Master’s thesis in Computer science and engineering Hanna Ek Department of Computer Science and Engineering CHALMERS UNIVERSITY OF TECHNOLOGY UNIVERSITY OF GOTHENBURG Gothenburg, Sweden 2021 Master’s thesis 2021 Aggregated Set Membership Proofs Aggregated Signature-Based Set Membership Proofs and implementation in Client and Server Verifiable Additive Homomorphic Secret Sharing Hanna Ek Department of Computer Science and Engineering Chalmers University of Technology University of Gothenburg Gothenburg, Sweden 2021 Aggregated Set Membership Proofs Aggregated Signature-Based Set Membership Proofs and implementation in Client and Server Verifiable Additive Homomorphic Secret Sharing Hanna Ek © Hanna Ek, 2021. Supervisor: Georgia Tsaloli and Katerina Mitrokotsa, Department of Computer Science and Engineering Examiner: Katerina Mitrokotsa, Department of Computer Science and Engineering Master’s Thesis 2021 Department of Computer Science and Engineering Chalmers University of Technology and University of Gothenburg SE-412 96 Gothenburg Telephone +46 31 772 1000 Gothenburg, Sweden 2021 iv Aggregated Set Membership Proofs Aggregated Signature-Based Set Membership Proofs and implementation in Client and Server Verifiable Additive Homomorphic Secret Sharing Hanna Ek Department of Computer Science and Engineering Chalmers University of Technology and University of Gothenburg Abstract This thesis addresses the issue of inflated computational complexity for the verifi- cation of multiple zero-knowledge proofs. More precisely, verification of numerous zero-knowledge set membership proofs performed by a single verifier is considered. To reduce the computations required by such a verifier Aggregated Set Membership Proofs are introduced. Aggregated set membership proofs unifies multiple set membership proofs into one aggregated proof, such that the validity of the aggregated proof implies the validity of all individual proofs. Completeness, soundness and zero-knowledge requirements are established for zero-knowledge aggregated set membership proofs. A concrete construction of aggregated set membership proofs is presented and proved to satisfy the completeness, soundness and zero-knowledge requirements. The con- struction is a partial aggregation of signature-based set membership proofs, [5], and is referred to as aggregated signature-based set membership proofs. A general technique to verify clients in verifiable additive homomorphic secret shar- ing is derived. The clients are verified by computing zero-knowledge proofs, derived from Pedersen commitments, of some given statement and then the proofs are val- idated by a verifier. If the proved statement is that the shared secrets belong to a discrete set, clients construct set membership proofs. Usually, several clients partic- ipate in verifiable additive homomorphic secret sharing protocols resulting in that the verification of clients is computationally expensive. A prototype implementation considering 100 clients showed that the runtime for ver- ification of clients was reduced by 13% when verifying an aggregated signature-based set membership proof compared to verifying the same proofs without performing the aggregation. Keywords: Aggregated Set Membership Proofs, Zero-knowledge proofs, VAHSS, cryptography v Acknowledgements I wish to express my gratitude towards my supervisors Georgia Tsaloli and Katerina Mitrokotsa for the support and help during the work. The thesis would not have been as extensive without your guidance, expertise and innovation. I also want to thank Markus Pettersson for consultation regarding the implementa- tion of the constructions. Hanna Ek, Gothenburg, July 2021 vii Contents List of Figures xi List of Tables xiii 1 Introduction 1 2 Background 5 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Set Membership Proofs and Range Proofs . . . . . . . . . . . . . . . 9 3 Aggregated Set Membership Proofs 13 4 Aggregated Signature-Based Set Membership Proofs 17 4.1 Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 Soundness of Aggregation . . . . . . . . . . . . . . . . . . . . . . . . 19 4.3 Completeness, Soundness and Zero-Knowledge . . . . . . . . . . . . . 22 5 Implementation and Evaluation 27 5.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Trade-off between Aggregation and Verification . . . . . . . . . . . . 28 5.3 Comparison to Bulletproofs . . . . . . . . . . . . . . . . . . . . . . . 29 6 Application in VAHSS 33 6.1 VAHSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Client and Server VAHSS . . . . . . . . . . . . . . . . . . . . . . . . 34 6.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.4 Prototype analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 7 Discussion and Conclusion 43 Bibliography 47 A Correctness, Security and Verifiability of VAHSS I B Multiple Aggregating Parties III C Naive Aggregation V ix Contents D Complete Aggregation VII x List of Figures 2.1 Extending range proofs to consider arbitrary ranges. It is illustrated that if x ∈ [b− ul, b) ∧ x ∈ [a, a+ ul) then x ∈ [a, b] . . . . . . . . . . 11 3.1 Schematic figure of the interaction between Provers, Aggregator and Verifier in aggregated set membership proofs. . . . . . . . . . . . . . 15 4.1 Provers outsourcing their set membership proofs to their assigned ag- gregator that in turn publishes an aggregated set membership proof. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.1 Timing in seconds for running the algorithmsAggregate andVerify in Construction 5 considering different numbers of aggregating par- ties. The number of aggregating parties varies between 1, 2, 5 and 10. The figure is a visualisation of the results presented in Table 5.1. . . 29 5.2 Runtime for verification of multiple provers as a function of the num- ber of provers. Verification of four different constructions of proofs are considered: aggregated signature-based set membership proofs, signature-based set membership proofs, Bulletproofs with a maximal upper bound equal to 28 and Bulletproofs with a maximal upper bound equal to 232. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 xi List of Figures xii List of Tables 5.1 Timing in seconds for algorithms Aggregate and Verify in Con- struction 5 considering different numbers of aggregating parties, |K|. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2 Runtime for verification of 100 proofs constructed using three different ZKP. The three considered proof constructions are: Bulletproofs, with a maximal upper bound equal to 28 and 232, and aggregated signature- based set membership proofs. . . . . . . . . . . . . . . . . . . . . . . 30 6.1 Runtime for the algorithms in Construction 3 and 4. The runtime of Construction 3 is presented using Bulletproofs and signature-based set membership proofs to verify clients. Aggregated signature-based set membership proofs are used to verify clients in Construction 4 . . 40 xiii List of Tables xiv 1 Introduction The digitalisation of our society leads to a need for cryptographic protocols to ob- tain online security and privacy. In many online applications, users are required to provide some information to legitimise themselves. This could for example be providing your membership number to verify that you are a member of a site. In many applications, however, it is sufficient to share more abstract information. Consider the example with the membership number. To prove that you are a member of a group it is sufficient to prove that you are one of the members, without specifying which one. To illustrate the above idea, consider two parties Alice and Bob. Alice is a subscriber to Bob’s paper and wishes to convince Bob of this, without revealing who she is. Bob has a list of all subscribers, but without knowing who Alice is, he does not feel certain that she is on the list. Therefore, Alice constructs a proof that her name is on the list. Bob receives this proof and checks its validity. Bob is now convinced that Alice’s name is on the list, but not which of the names it is, and allows Alice to get access to the paper. For the remainder of this thesis, Alice will be denoted as the prover and Bob as the verifier. A cryptographic construction that allows a prover to convince a verifier that a secret is in a set without revealing the secret is called a set membership proof. Con- structions of set membership proofs are computationally expensive. Consequently, a lot of research has been done to reduce the computations required to construct and verify set membership proofs. Usually, the constructions are optimised considering one prover and one verifier, as in the example above with Alice and Bob. We are considering constructions consisting of multiple provers and one verifier. An exam- ple of such a construction is the verification of clients in a VAHSS protocol, [19]. In such a construction, using set membership proofs, the computational complexity for the verifier grows linearly with the number of provers. This since the verifier has to verify all received proofs individually. A method for reducing the computations required of the verifier is aggregating the proofs beforehand. Then the verifier only needs to verify one proof, the ag- gregated proof. The aggregated proof should be such that its validity implies the validity of all individual proofs. The aim of this thesis is to investigate the possibilities to aggregate set mem- bership proofs, in order to reduce the computational complexity for verification of multiple provers. 1 1. Introduction Purpose This paper consists of two parts. The first is to explore the possibility to aggregate set membership proofs, in order to reduce the computational complexity required to verify multiple proofs of different instances. Initially, a general description of aggregate set membership proofs is sought. Then, given such a description we provide a concrete construction of an aggregated set membership proof and prove its security. The second purpose is to obtain a method for extending a VAHSS construction, [19], to verify clients’ inputs. Then we compare the runtime of using aggregated set membership proof contra Bulletproof for the verification of clients. Limitations The exploration of obtaining a construction of an aggregated set membership proofs is limited to investigate if one specific set membership proof can be aggregated. Contribution The main results obtained in this paper are: • A general description of aggregated set membership proofs including the com- pleteness, soundness and zero-knowledge requirements such proofs should ful- fil. • A construction and implementation of an aggregated signature-based set mem- bership proof. The presented construction is proved to satisfy the complete- ness soundness and zero-knowledge properties for aggregated set membership proofs. • The VAHSS construction using homomorphic hash functions to verify servers [19] is modified to additionally verifying clients’ inputs. The clients’ inputs are verified using either range proofs or set membership proofs. The construction is also modified to be compatible with aggregated set membership proofs for the verification of clients. • Implementation of all proposed constructions in Golang and runtime compar- ison of the constructions. Related work Zero-Knowledge proofs Set membership proofs Set membership proofs are zero-knowledge proofs proving that a secret belongs to a discrete set. A construction of set membership proofs based on bilinear groups and public signatures of elements in the set is presented in [5]. Their construction has a computational complexity of O(1) for the construction and verification of 2 1. Introduction the set membership proofs. However, when multiple proofs are verified at once the computational complexity grows linearly in the number of proofs. Range Proofs Range proofs are strongly connected to set membership proofs, but instead of prov- ing that a secret belongs to a discrete set, they prove that a secret belongs to a numerical range. Bulletproofs are state-of-the-art range proofs used in many real-world applica- tions. Bulletproofs prove that a secret belongs to a given range, by making use of an inner-product argument [4]. Bulletproofs can be aggregated using a simple multi-party computation protocol. Consequently, aggregation of Bulletproofs re- quires interaction between the provers during the construction of the proof. Unlike the focus of this paper, where non-interactive aggregation of zero-knowledge proofs is considered. A recently published paper presents range proofs that are faster than Bullet- proofs for both the prover and the verifier, [8]. Their range proofs make use of square decomposition methods by converting commitment schemes over Zp into proofs over Z between bounded-range integers. In applications where multiple provers partici- pate each proof is verified individually, leading to that the computational complexity of the verification grows linearly in the number of provers. Prio+ Prio+, [1], computes aggregated statistics on multiple clients data, without revealing the data of individual clients and is robust against malicious clients. Communication between the servers, of constant size per client, is required to compute the aggregated statistics of the clients’ data. Prio+ is strongly connected to the Prio construction, [7], and can be seen as a development that reduces the computations required by the clients. In Prio+ clients use Boolean secret-sharing to convince servers of their honesty, instead of computationally expensive zero-knowledge proofs. Prio+ consti- tutes the same purpose as client and server VAHSS. However, in Prio+ the servers must communicate to verify the clients unlike client and server VAHSS where no communication is required between the servers. Organisation In chapter 2 the theoretical background is presented. First cryptographic principles are treated then a more detailed description of set membership proofs and range proofs is given. Chapter 3 presents a general definition of aggregated set member- ship proofs. Based on this definition chapter 4 presents a construction of an aggre- gation of signature-based set membership proofs. This construction is implemented and compared in terms of runtime with itself for different settings and additionally compared to the state-of-the-art Bulletproofs in chapter 5. Chapter 6 presents a client and server VAHSS. Clients are verified using Bulletproofs, aggregated and not 3 1. Introduction aggregated signature-based set membership proofs. In chapter 7 a discussion about the results is given together with a conclusion. 4 2 Background This chapter presents the theory used in this paper. In section 2.1 first notation, theorems, definitions and assumptions are stated, then cryptographic preliminar- ies are explained. In section 2.2 two different types of zero-knowledge proofs are presented, more precisely signature-based set membership proofs and Bulletproofs. 2.1 Preliminaries Notations To make the text more comprehensive the following notations and definitions are defined here: F = Zp denotes a finite field, where p is a large prime and G denotes a unique subgroup of order q. g ∈ G is defined to be the group generator of G and h ∈ G a group element, such that logg h is unknown and h is a co-prime to p. The notation y ∈R Y, means that an element y is chosen at random from the set Y. Definitions, Theorems and Assumptions The assumptions given here are the assumptions that all cryptographic construc- tions in this paper rely on. The discrete logarithm assumption and the q-strong Diffie Hellman assumption defined below does not hold in the presence of quantum computers. Thus the cryptographic constructions presented in this paper are not guaranteed to be post quantum secure. Definition 1 (Pseudorandom Function (PRF)). Let S be a distribution over {0, 1}l and Fs : {0, 1}m → {0, 1}n a family of functions indexed by a string s in the support S. It is defined that {Fs} is a pseudo random function family if, for every PPT (probabilistic polynomial time) adversary A, there exists a negligable function ε such that: |Pr[AFs(·) = 1]− Pr[AR(·) = 1]| ≤ ε, where s is distributed according to S and R is a function sampled uniformly at random from the set of all functions mapping from {0, 1}n to {0, 1}m. Definition 2 (Euler’s totient function). The function Φ(n) is defined as the counter of the number of integers that are relative primes to n in the set {1, ..., n} . Note if n is a prime number φ(n) = n− 1. 5 2. Background Theorem 1 (Euler’s Theorem). For all integers x and n that are co-prime it holds that: xΦ(n) = 1 (mod n), where Φ(n) is Euler’s totient function. From Theorem 1 it follows that for arbitrary y it holds that xyΦ(n) = 1 (mod n). Assumption 1 (Discrete logarithmic assumption). Let G be a group of prime order q, further let g ∈ G be a group generator of G and y ∈ G be an arbitrary group element. Then it is infeasible to find x ∈ F, such that y = gx Assumption 2 (q-strong Diffie Hellman Assumption). Given a group G, a random generator g ∈ G and powers gx, ..., gxq , for x ∈R F and q = |G|. It is then infeasible for an adversary to find (c, g 1 x+c ), where c ∈ F. Homomorphic Secret Sharing Homomorphic secret sharing (HSS), [15], hides a secret x by splitting it into shares, such that any subset, S, of shares smaller than a threshold τ , i.e |S| < τ , reveals no information about the value of x. If a secret x is split into m shares denoted xi, such that i ∈ {1, ...,m} and to reconstruct the value of x at least τ shares has to be combined, it is called a (τ,m)-threshold scheme. In this paper, the threshold is set equal to the number of shares, τ = m. Verifiable Additive Homomorphic secret sharing In this paper Verifiable Additive homomorphic secret sharing (VAHSS) is of interest. The additivity property for a HSS means that the secret is reconstructed by computing the sum of at least τ shares, i.e x = ∑τ i=1 xi. This is denoted Additive Homomorphic Secret Sharing (AHSS). VAHSS is a construction of AHSS where m parties, referred to as servers, col- laborates to compute the sum of multiple clients’ secrets. Each client split their secret into m shares and sends one share to each server. The servers compute and output a partial sum of all received shares. The final sum is computed by summing the servers outputs. For VAHSS constructions a proof σ is constructed that verifies that the final sum is the correctly computed sum of the clients’ secrets. In section 6.1 a specific construction of a VAHSS is presented and in Appendix A the correctness, security and verifiability requirement of a VAHSS construction is stated. Homomorphic hash functions Let H be a cryptographic hash function, H : F 7→ G, any such function should satisfy the following two properties: • Collision-resistant It should be hard to find x, x′ ∈ F such that x 6= x′ and H(x) = H(x′). • One-Way It should be computationally hard to find H−1(x). A homomorphic hash function should also satisfy the following property: 6 2. Background • Homomorphism For any x, x′ ∈ F it should hold that H(x + x′) = H(x) ∗ H(x′). A homomorphic hash function that satisfies the thee properties is the function H1(x) : F 7→ G and H1(x) = gx, [20]. Pedersen Commitment scheme A Pedersen commitment is a commitment to a secret x ∈ F, defined as E(x,R) = gxhR, where R ∈R F, [14]. The Pedersen commitment satisfies the following theo- rem: Theorem 2. For any x ∈ F and for R ∈R F, it follows that E(x,R) is uniformly distributed in G. If two commits satisfies E(x,R) = E(x′, R′) while x 6= x′ then it must hold that R 6= R′ mod q and x− x′ = (R−R′) logg h mod p (2.1) Proof. The statements of the theorem follows from solving for logg(h) in E(x,R) = E(x′, R′) Theorem 2 implies that if someone knows the discrete logarithm of h with re- spect to g this person is able to provide two equal commits, E(x,R) = E(x′, R′) such that x 6= x′. It is impossible to construct two equal commits hiding different secrets, since loggh is assumed to be unknown. The Pedersen commitment scheme is computationally binding under the discrete logarithm assumption and it is perfectly hiding of the secret, [14]. The Pedersen commitment is homomorphic. Hence for arbitrary messages x1, x2 ∈ F, random values R1, R2 ∈R F and the commits Ci = E(xi, Ri), i ∈ {1, 2}, it holds that C1 · C2 = E(x1 + x2, R1 +R2). A Pedersen commitment scheme can also be defined for vectors and is then called Pedersen vector commitment. Consider a n dimensional vector x ∈ Fn, let g = (g1, ..., gn) ∈ Gn and h ∈ G where G is a group of order q as above. A commitment to the vector x = (x1, ..., xn) with the random value R ∈R F is then defined as E(x, R) = gxhR = hR ∏n i=1 g xi i and the commitment is a value in the one-dimensional group G. Bilinear mapping Bilinear mapping (also called bilinear pairing) maps two group elements from one group to an element in another group. This paper considers admissible bilinear mapping fulfilling Definition 3. Generally, the definition of an admissible bilinear mapping maps two elements from different groups to a third group, i.e the map e : G1 × G2 → GT , in this paper it always holds that G1 = G2 and thereby the definition is given on this form. Definition 3 (Admissible Bilinear Map). Let G1,GT be two multiplicative cyclic groups of prime order p such that there exists an admissible bilinear map e : G1 × G1 → GT . Let G∗1 = G1\{1}. Then the bilinear map e fulfils: 7 2. Background • Bilinear: for any group element g ∈ G∗1 and a, b ∈ F, e(ga, gb) = e(g, g)ab • Non-degenerated: e(g, g) 6= 1 • The bilinear map is efficiently computable Bohen-Boyen Signatures Consider a bilinear map e, defined in the previous section. The bilinear property of the mapping e can be used to create digital signatures. Bohen-Boyen presented a signature scheme that exploits the bilinear property of the mapping e to verify signatures [3]. In short, the scheme works as: the signer knows the secret key x and distributes the public key gx. To sign a message m the signer uses the secret key, x, and computes σ = g1/(x+m). This signature is q − secure to forgery under the q-Strong Diffie Hellman Assumption. Verification is done by checking that e(σ, y · gm) = e(g, g), which holds due to the bilinearity of e. Non-interactive Zero-Knowledge proof Zero-Knowledge proofs (ZKP) is a cryptographic primitive that was first presented in [10]. The idea behind a ZKP is that after successfully performing a ZKP a certain statement has been verified to be true (or false) without having revealed any other information beyond the statement begin true (or false). In this thesis non-interactive ZKP (NIZKP) that ensures proof of knowledge (PoK) are considered. A NIZKP consists of two parties the prover and the verifier. The prover knows a witness and wants to prove to the verifier that the witness satisfies a statement. Denote the statement with S and the witness by x such that (S, x) ∈ R, where R is a polynomial time computable binary relationship. Let L denote a NP language consisting of statements with witnesses in R. A definition of NIZKP is given in Definition 4. Definition 4. NIZKP of the relation R consists of three ppt algorithms: SetUp, Prove and a Verify [11]. The algorithm SetUp outputs a common reference string denoted σ given the security parameter and an intended statement size. The al- gorithm Prove takes as input the common reference sting σ, the statement S and witness x such that (S, x) ∈ R and outputs a proof Σ. The algorithm Verify takes the common reference sting σ, the statement S and the proof Σ as input and outputs 0 or 1, where 0 is interpreted as rejection and 1 as acceptance. A NIZKP scheme should fulfil the three properties: • Completeness Given proof Σ of a witness x satisfying the statement S, it should hold that Prob[Verify(σ, S,Σ) = 1] = 1. • Soundness Given a proof Σ of a witness x not satisfy the statement S Prob[Verify(σ, S,Σ) = 1] < ε, for a sufficiently small ε. • Zero-knowledge A NIZKP is computationally zero-knowledge if it is possible to simulate the proof of a true statement without knowing the witness. Con- sider a polynomial time simulator Sim = (Sim1, Sim2). Where Sim1 outputs a simulated reference string σ̃ and a simulated trapdoor τ . Sim2 takes the 8 2. Background simulated trapdoor τ and a statement as input and outputs a simulated proof π̃ For a non-uniform stateful adversary A , it should hold that: Prob[(S, x) ∈ R and A(π) = 1] ≈ Prob[(S̃, x̃) ∈ R and A(π̃) = 1], where (S, x) = A(σ) and (S̃, x̃) = A(σ̃). Zero-knowledge range proof (ZKRP) and zero-knowledge set membership proofs (ZKSM) where the statement being proved is that the witness belongs to a prede- termined range or set, will be considered in this paper. Fiat-Shamir heuristic The Fiat-Shamir heuristic [2] can be used to convert an interactive construction to a non-interactive construction. In this paper, it is used to construct non-interactive ZKP. A non-interactive ZKP requires no communication between the prover and verifier during the construction of the proof. In interactive constructions, the verifier sends a challenge c ∈R F to the prover that is included in the proof to convince the verifier of its validity. The Fiat-Shamir heuristic replaces the random challenge sent by the verifier with the output of a hash function computed from the partial-proof up to this point. The Fiat-Shamir heuristic converts an interactive ZKP to a non- interactive ZKP while preserving security and full zero-knowledge, relying on the random oracle model (ROM) [2] . 2.2 Set Membership Proofs and Range Proofs Zero-knowledge set memberships proofs allow a prover to convince a verifier that the value is in an allowed set, without revealing any other information about the value. Formally they are proofs of the statement: {(g, h ∈ G, C;x,R ∈ F) : C = gxhR ∧ x ∈ Φ}, (2.2) where Φ is some known set. Zero-knowledge range proofs prove that a value belongs to a range, instead of a set. Since ranges are continuous sets, zero-knowledge range proofs are less general than zero-knowledge set membership proofs. Zero-knowledge range proofs do not reveal any information beyond the fact that the value belongs to the range. Formally they are proofs of the following statement: {(g, h ∈ G, C;x,R ∈ F) : C = gxhR ∧ x ∈ {"predetermined allowed range"}. (2.3) Hereafter zero-knowledge set memberships proofs and zero-knowledge range proofs are denoted set memberships proofs and range proofs respectively. Note that the above statements assume that x is a secret hidden in a Pedersen commitment. This is not a requirement for set membership proofs and range proofs, however only such proofs are studied in this thesis. All set membership proofs and range proofs presented in this paper fulfils Defi- nition 4. 9 2. Background Signature-based Set membership proofs This section presents a construction of set membership proofs referred to as signature- based set membership proofs, originally presented in [5]. Bohen-Boyen signatures, Ai for each element i in the set Φ, is published in the set up phase. The signature-based set membership proofs have a computational complexity of O(1) for the proof construction and verification, assuming that the signatures {Ai}i∈Φ are known to both the prover and the verifier To prove a secret is in the set Φ, the prover chooses the public signature repre- senting the secret x, i.e Ax, and publishes the value V = Aτx, where τ ∈R F. Then constructs a proof that convinces the verifier that: 1) the published value V is indeed equal to Aτx where Ax is a signature of x ∈ Φ. 2) the secret in the pre-published Pedersen commitment C is a commitment to the same secrets as the signature V . Construction 1 describes the PPT algorithms (SetUp, Prove, Verify) that builds a signature-based set membership proof. Construction 1 is modified compared to the original construction of signature-based set membership proof, presented in [5], according to the Fiat-Shamir heuristic. The notation e(·, ·) in the construction refers to an admissible bilinear mapping as defined previously in section 2.1. Construction 1 : Non-interactive set membership proofs Goal: Given a Pedersen commitment C = gxhR and a set Φ, prove that the secret x in the commitment belongs to the set Φ without revealing anything else about x. • SetUp (1λ,Φ) −→ (sk, pp) Let g be a generator of the group G and h an element in the group such that logg(h) is unknown. Pick uniformly at random χ ∈R F and put sk = χ. Define y = gχ and Ai = g 1 χ+i ∀i ∈ Φ, output pp = (g, h, y, {Ai}i∈Φ). • Prove (pp, C, x,Φ) −→ Σ = (V, a,D, zx, zτ , zR) Pick uniformly at random τ ∈R F, choose from the set {Ai} the element Ax and calculate V = Aτx. Pick uniformly at random three values s, t,m ∈R F. Put a = e(V, g)−se(g, g)t and D = gshm. Then use these values to compute the challenge, c = Hash(C, V, a,D). Given this challenge compute zx = s−xc, zR = m − Rc and zτ = t − τc, finally construct and publish the proof, Σ = (V, a,D, zx, zτ , zR). • Verify (pp, C,Σ) −→ {0, 1} Check if D ?= CchzRgzx ∧ a ?= e(V, y)ce(V, g)−zxe(g, g)zτ . If the equality holds return 1 otherwise return 0. Signature-based range proofs Signature-based set membership proofs can be used to construct efficient signature- based range proofs. Rewriting the secret x in base u such that, x = l−1∑ j=0 xju j, 10 2. Background b− ul a b a+ ul Figure 2.1: Extending range proofs to consider arbitrary ranges. It is illustrated that if x ∈ [b− ul, b) ∧ x ∈ [a, a+ ul) then x ∈ [a, b] and then using set membership proofs to prove that xj ∈ [0, u) ∀j ∈ Zl, constructs to a range proof that x ∈ [0, ul). This range proof can be generalised to consider arbitrary ranges [a, b], where a > 0 and b > a. This is obtained by realising that proving that x ∈ [a, a + ul) and x ∈ [b− ul, b), is equivalent to proving that the secret, x, belongs to the range [a, b]. Figure 2.1 illustrates the intuition and correctness of the statement. Proving x ∈ [a, a + ul) and x ∈ [b− ul, b) can be translated into proving x− a ∈ [0, ul) and x− b+ ul ∈ [0, ul), since both a, b are public. In [6] an optimised implementation of the signature-based range proof, for arbi- trary ranges, is presented, reducing the complexity with a factor of 2. This rather small reduction is important when a verifier is required to check the validity of multiple range proofs simultaneously. Bulletproofs Bulletproofs are state-of-the-art range proofs that are integrated into many real- world protocols. They are for example used in crypto-currencies, to prove that a value is in an allowed range or above some threshold. In this paper, Bulletproofs are used for runtime comparison with other constructions and to verify the clients’ inputs in a VAHSS construction. Bulletproofs are originally presented in [4] and prove that a secret in a Pedersen commitment belongs to the range [0, 2n), where n is a power of 2. The construction of Bulletproofs builds on the inner product argument. The inner product argument is an argument of knowledge that s,q in a Pedersen vector commitment, Pv = gshq, satisfies a given inner product. Given a Pedersen com- mitment C = gxhR, of the secret x, a prover wants to convince a verifier that the secret belongs to the interval [0, 2n). The binary representation of the secret x is x ∈ {0, 1}n which can be equivalently written as x = 〈x,2n〉. This inner product can the be used to construct an inner product argument of the vector x, i.e the secret x. Bulletproofs modified according to the Fiat-Shamir heuristic are considered. A construction of non-interactive Bulletproofs and a non-interactive inner product argument is given in [12]. 11 2. Background 12 3 Aggregated Set Membership Proofs It is of high importance to keep the computational complexity for the verification of set membership proofs small, specially in applications where one verifier validates multiple provers. If set membership proofs, which are proofs of the statement: {(g, h ∈ G, C ∈ G;x,R ∈ F) : C = gxhR ∧ x ∈ Φ}, are used to verify multiple provers then the verifier would have to verify each prover individually. This leads to that the computational complexity for verification grows linearly in the number of provers and the verification algorithm quickly becomes a bottleneck in application where many provers participates. This motivates the question if set membership proofs can be aggregated, and thereby decreasing the computations required to verify multiple provers. A definition of aggregated set membership proofs is presented in Definition 5. An aggregated set membership proof is defined to be a 5-tuple of PPT algorithms, (SetUp, Prove, Aggregate, CalculateChallanges, Verify ). Definition 5 (Aggregated set membership proofs). Aggregated set membership proofs are a zero-knowledge proof of the statement:{ (g, h ∈ G, {Ci}i∈S ∈ Gn; {xi}i∈S , {Ri}i∈S ∈ Fn) : Ci = gxihRi ∀i ∈ S ∧ xi ∈ Φ ∀i ∈ S } . (3.1) Where Ci is a Pedersen commitment to the secret xi ∈ F and Ri ∈R F are chosen at random, for all i ∈ S. The statement implies that after successfully having performed an aggregated set membership proof protocol, it is proved that for all i ∈ S: Ci is a Pedersen commitment to a secret xi belonging to the set Φ. A construction of aggregated set membership proofs is a 5-tuple of PPT-algorithms (SetUp, Prove, Aggregate, CalculateChallanges, Verify). • SetUp (1λ,Φ) −→ (pp, sk) On the input 1λ, where λ is the security parameter and the set Φ the algorithm outputs a secret key, sk, and public parameters, pp. • Prove (pp, i, Ci, xi,Φ) −→ Σi On the input, the public parameters pp, i ∈ S denoting the index of the prover pi, a secret xi and a Pedersen commitment Ci of the secret. The algorithm 13 3. Aggregated Set Membership Proofs outputs a polynomial time verifiable zero-knowledge proof of the statement in equation (2.2), denoted Σi. • Aggregate (pp, {Σi}i∈S −→ Σa Given a set of set membership proofs {Σi}i∈S the algorithm aggregates the proofs into one zero-knowledge proof of the statement in equation (3.1) denoted Σa. • CalculateChallenges ({Ci}∈S , {σi}i∈S) −→ {ci}i∈S On the input {Σi}i∈S the algorithm computes and outputs the challenges ci = Hash(Σi) for all i ∈ S. • Verify (pp,Σa, {Ci}i∈S , {ci}i∈S) −→ {0, 1} On input the aggregated set membership proof public parameters, pp, aggregated proof, Σa, the Pedersen commitments, {Ci}i∈S , and challenges ,{ci}i∈S , the algorithm outputs either 1 or 0. Aggregated set membership proofs consist of the following parties: provers, an aggregator and a verifier. A schematic figure of the interaction between the parties is seen in Figure 3.1. The provers, a group of many individual provers, individually run the algorithm Prove and publishes the computed proof. The aggregating party retrieves all proofs, runs the algorithm Aggregate and publishes the aggregated proof. Finally, the verifier validates the aggregated proof by running the algorithm Verify. The aggregation can be split between multiple parties implying there are many aggregators, this is discussed more in the next chapter. The algorithms SetUp and CalculateChallenges is either performed by the verifier or by an independent trusted party. The algorithms of aggregated set membership proofs, presented in Definition 5, should fulfil the below completeness, soundness and zero-knowledge requirements: • Completeness Given xi ∈ Φ, where Ci is a Pedersen commitment of xi, for all i ∈ S, it should hold that Verify(Aggregate({Prove(pp, i, Ci,Φ)}i∈S)) = 1. • Soundness If for any i ∈ S xi /∈ Φ, then the probability Prob[Verify(Aggregate({Prove(pp, i, Ci,Φ)}i∈S)) = 1] < ε, for a sufficiently small ε. • Zero-knowledge It should be possible to simulate the proof of a true state- ment without knowing the witness. These requirements can be seen as a modification of the requirements given in Definition 4 to aggregated set membership proof. 14 3. Aggregated Set Membership Proofs Figure 3.1: Schematic figure of the interaction between Provers, Aggregator and Verifier in aggregated set membership proofs. 15 3. Aggregated Set Membership Proofs 16 4 Aggregated Signature-Based Set Membership Proofs This chapter presents a construction of aggregated set membership proofs derived from the non-interactive signature-based set membership proofs, [5]. In section 4.2 it is proved that the aggregation is sound and in section 4.3 the completeness, soundness and zero-knowledge requirements, stated in the chapter 3, is proved to hold for the aggregated signature-based set membership proofs. 4.1 Construction Construction 2 presents an aggregated signature-based set membership proof, de- rived from the non-interactive signature-based set membership proofs [5]. The algorithm Aggregate, in Construction 2, partly aggregates a group of set membership proofs by constructing the aggregated proof, Σa. The aggregated values Da, zxa , zRa in Σa are computed according to Equation (4.1). Da = ∏ i∈S D ∏ j∈S j 6=i cj i = g ∑ i∈S (∏ j∈S j 6=i cj ) si h ∑ i∈S (∏ j∈S j 6=i cj ) mi zxa = ∑ i∈S ( ∏ j∈S j 6=i cj ) zxi = ∑ i∈S ( ∏ j∈S j 6=i cj ) si − ( ∏ j∈S cj )∑ i∈S xi zRa = ∑ i∈S ( ∏ j∈S j 6=i cj ) zRi = ∑ i∈S ( ∏ j∈S j 6=i cj ) mi − ( ∏ j∈S cj )∑ i∈S Ri (4.1) The set S denotes the index set of the provers and each prover pi i ∈ S publishes a set membership proof Σi = (Vi, ai, Di, zxi , zτi , zRi) constructed according to the algorithm Prove. The challenges, denoted ci for i ∈ S, are computed according to the algorithm CalculateChallenges. The above aggregation has the computational complexity O(|S|2). This is re- duced to be linear in |S|, by considering the following optimization. Instead of computing the product ∏j∈S, j 6=i cj for each i, it is sufficient to compute the product c = ∏ j∈S cj once and then the truncated product can be obtained by noting that∏ j∈S,j 6=i cj = c/ci. Thereby, for each i ∈ S, it is sufficient to perform one division instead of computing the product ∏j∈S, j 6=i cj. Due to the aggregation, the equality Da = ∏ i∈S C ∏ i∈S ci i hzRagzxa is checked 17 4. Aggregated Signature-Based Set Membership Proofs once instead of once for each proving party in the protocol. This can bee seen by comparing the algorithm Verify in Construction 2 with running the algorithm Verify in Construction 1 once for each prover. Construction 2 : Aggregation of non interactive set membership proof Goal: Given the Pedersen commitments Ci = gxihRi , for i ∈ S. The construction proves that all secrets xi belong to the set Φ, without revealing anything else about the secrets. • SetUp (1λ,Φ) −→ (sk, pp) Let g be a generator of the group G and h an element in the group such that logg(h) is unknown. Pick uniformly at random χ ∈R F and put sk = χ. Define y = gχ and Ai = g 1 χ+i ∀i ∈ Φ, output pp = (g, h, y, {Ai}i∈Φ). • Prove (pp, i, Ci, xi,Φ) −→ Σi Pick uniformly at random τi ∈R F, choose from the set {Ai} the element Axi and calculate Vi = Aτixi . Pick uniformly at random three values si, ti,mi ∈R F. Put ai = e(Vi, g)−sie(g, g)ti , D = gsihmi , c = Hash(Ci, Vi, ai, Di) and compute zxi = si − xici, zRi = mi − Rici and zτi = ti − τici. Finally construct and publish the proof Σi = (Vi, ai, Di, zxi , zτi , zRi). • Aggregate (pp, {Σi}i∈S) −→ Σa Given a set of proofs {Σi}i∈S . Aggregate the values ({Di}i∈S , {zxi}i∈S , {zri}i∈S) 7→ Da, zxa , zRa according to equa- tion (4.1). Construct and publish the aggregated proof Σa = ({Vi}i∈S , {ai}i∈S , Da, {zxi}i∈S , zxa , {zτi}i∈S , zRa). • CalculateChallenges ({Ci}i∈S , {Σi}i∈S) −→ {ci}i∈S For all i ∈ S parse the proof Σi, then compute the challenge ci = Hash(Ci, Vi, ai, Di). Finally output the set of all challenges {ci}i∈S . • Verify (pp,Σa, {Ci}i∈S , {ci}i∈S) −→ {0, 1} Compute the product of the challenges c = ∏ i∈S ci. Check if Da ?=(∏ i∈S Ci )c hzRagzxa ∧ ai ?= e(Vi, y)cie(Vi, g)−zxie(g, g)zτi for all i ∈ S. If the equalities hold return 1 otherwise return 0. In Construction 2 the algorithm Prove is run by all provers, the algorithm Aggregate is run by the aggregating party and the algorithm Verify is performed by the verifier. The algorithm SetUp is assumed to be performed in advance by a trusted party. In the aggregated signature-based set membership proof the challenges are given as input to the verification algorithm, unlike Construction 1 where they are com- puted in the verification algorithm. This raises the question, which party should be responsible for computing the challenges? It is not desired that the party performing the aggregation computes the challenges since it creates opportunities for cheating. For the same reason, the proving parties should not compute the challenges. The challenges are constructed according to the Fiat-Shamir heuristic. Two important characteristics of the Fiat-Shamir heuristic are that: the prover does not know the challenge when constructing the proof and that the verifier re-computes the chal- lenge, to check that it is correctly computed. If the challenges are computed by the aggregating party they are known when constructing the aggregated proof and if 18 4. Aggregated Signature-Based Set Membership Proofs they are computed by the provers they are never checked. Thereby, the algorithm CalculateChallenges in Construction 2 is assumed to be performed by an honest party independent of both the proving parties and the aggregating party. Another alternative is to provide the entire proofs {Σi}i∈S as input to the ver- ification algorithm, enabling the verifier to compute the challenges. This would consequently increase the computations required by the verifier. For the rest of this paper, if nothing else is mentioned, it is assumed that the algorithm Calculate- Challenges is performed according to Construction 2 by a trusted party. Multiple aggregating parties To reduce the computational load of the aggregating party it is possible to split the aggregation between multiple parties. Let the set K represent the set of parties performing the aggregation, and the set Sk represent the assigned set of set membership proofs to the kth aggregating party. The sets Sk for k ∈ K are such that ⋃k∈K Sk = S and Si ⋂Sj = ∅ for all i, j ∈ K such that i 6= j. An aggregated signature-based set membership proof, where the aggregation is split between several parties, is presented in appendix B in Construction 5. The adjustments made compared to Construction 2 are: the algorithm Aggregate is performed by each party in the set K on the input (pp, {Σi}i∈Sk), outputting the aggregated proof Σak . The algorithm Verify is performed once on the input (pp, {Σak}k∈K, {Ci}i∈S , {ci}i∈S) and is modified, compared to Construction 2, such that it verifies multiple aggregated proofs. By letting the set of aggregating parties K consist of one element k, and Sk = S constructions 2 and 5 are equivalent. An illustrative figure of how the aggregation is split between the aggregating parties is seen in Figure 4.1. Each prover generates a set membership proof, and then sends it to its assigned aggregating party. Then each aggregating party aggre- gates the received set membership proofs, according to the algorithm Aggregate in Construction 5, and sends the aggregated proof to the verifier. Finally the verifier validates all aggregated proofs. In Figure 4.1 the computation of the challenges is done by an independent party, which introduces a new party to the scheme. To compute the challenges without introducing a new party the aggregating parties can compute the challenges. However, as discussed previously the same party that aggregates a set of proofs should not compute the challenges for these proofs. To use the aggregating parties for the computations, assume that they are not collaborating and linked in a closed chain. Then each aggregating party computes the challenges for the set of proofs aggregated by the consecutive party in the chain. 4.2 Soundness of Aggregation In this section it is proved that the aggregation must be performed according to the algorithm Aggregate if the aggregated proof Σa validates true in Construction 2. This is proved under the assumption that: proving parties are not communicat- ing or collaborating between themselves, proving parties are not communicating or 19 4. Aggregated Signature-Based Set Membership Proofs Figure 4.1: Provers outsourcing their set membership proofs to their assigned aggregator that in turn publishes an aggregated set membership proof. 20 4. Aggregated Signature-Based Set Membership Proofs collaborating with the aggregating party (or parties), the set membership proof in Construction 1 is sound and Da 6= Cc. In this section the product of the Pedersen commitments, ∏i∈S Ci, is denoted C and the product of the challenges, ∏i∈S ci, is denoted c. If Da = Cc, it would be possible for an aggregating party to choose the values Da, zxa , zRa according to: Da = Cc, zxa = φ(p), zRa = φ(p). For the above choice of Da, zxa , zRa the equation, Da ?= CchzRagzxa holds trivially true, independent of whether the commitment Ci and the values zxi , thereby zxa , hides the same secret for all i ∈ S. Therefore it is required that Da 6= Cc. Under the assumption discussed above, Theorem 3 states that the aggregation must be performed according to the algorithm Aggregate for the algorithm Verify to validate true, in Construction 2. Theorem 3 (Soundness of aggregation). Let A be a PPT adversary. Assume A has access to the input to the algorithm Aggregate in Construction 2 and the Pedersen commitment, {Ci}i∈S , but no other information. Assume that the adver- sary A cannot collaborate with the provers, that the provers cannot collaborate with each other and that the set membership proof in Construction 1 is sound. Under these assumptions the adversary A has a negligible probability of con- struction Σa such that: Prob(Verify(pp,Σa, {Ci}i∈S , {ci}i∈S)) = 1, where Da 6= Cc and zxa 6= ∑ i∈S (∏ j∈S,j 6=i cj ) zxi. Proof. The soundness of signature-based set membership proofs and that the algo- rithm Verify checks that ai ?= e(Vi, y)cie(Vi, g)−zxie(g, g)zτi , for all i ∈ S, implies that the values Vi, ai, zxi , zτi of Σi must be computed according to the algorithm Prove in Construction 2. The values zRi and Di are not used directly in the ver- ification, thus the only requirements are that zRi ∈ F and Di ∈ G, for all i ∈ S. Assume, without loss of generality that Da = gαhβ, where α, β ∈ F. Assume that the adversaryA, can construct a valid proof Σa, such that: Da ∈ G, zxa , zRa ∈ F and zxa 6= ∑ i∈S (∏ j∈S,j 6=i cj ) zxi . For the aggregated proof to be valid it must hold that Da = CchzRagzxa which implies that the values α, β, zxa , zRa must satisfy: gαhβ = CcgzxahzRa . The values of Cc cannot be modified by the adversary since it is sent directly from the provers to the verifier. The Pedersen commitments are assumed to be on the form Ci = gxihRi for all i ∈ S and the challenges are correctly computed and checked by a trusted party. Consequently, by expanding the right hand side of the equality it follows that, gαhβ = gc ∑ i∈S xi+zxahc ∑ i∈S Ri+zRa . If α 6= c ∑ i∈S xi + zxa and β 6= c ∑ i∈S Ri + zRa , the above equality contradicts to the binding property of the Pedersen commitments. Thereby, the values α, β, zxa and zRa must satisfy: α = c ∑ i∈S xi + zxa and β = c ∑ i∈S Ri + zRa . 21 4. Aggregated Signature-Based Set Membership Proofs This can be rewritten as α− zxa = c ∑ i∈S xi mod Φ(p) and β − zRa = c ∑ i∈S Ri mod Φ(p). The sums ∑i∈S xi and ∑ i∈S Ri are assumed to be unknown. Thereby, under the assumption that zxa 6= ∑ i∈S (∏ j∈S,j 6=i cj ) zxi the adversary has a negligible probability of choosing α, β, zxa , zRa such that Da = CchzRagzxa . It follows that zxa = ∑ i∈S (∏ j∈S,j 6=i cj ) zxi , which contradicts the assumption and proves the theorem. Note that the theorem would still hold even if several untrusted parties aggre- gated subsets of the proofs and a verifier validated all the aggregated proofs. 4.3 Completeness, Soundness and Zero-Knowledge In this section, it is proved that Construction 2 fulfils the completeness, soundness and zero-knowledge requirements stated in chapter 3. This is proved under the as- sumption that the aggregation is performed according to the algorithm Aggregate, provers cannot communicate or collaborate with each other and that Construction 1 satisfies the requirement stated in Definition 4. The requirements also hold for Construction 5, considering |K| > 1. Completeness To prove the completeness of Construction 2, it has to be proved that Verify(Aggregate({Prove(pp, i, Ci, xi,Φ)}i∈S)) = 1. To prove this, let Σi for i ∈ S denote proofs constructed by the algorithm Prove and Σa denote the aggregation of these proofs obtained according to algorithm Aggregate. For all i ∈ S, let Ci denote the Pedersen commitment of the secrets xi and ci denote the challenge used in the proof. Then by the completeness property of the signature-based set membership proof [5], it holds that: ai = e(Vi, y)cie(V, g)zxie(g, g)zτi ∀ i ∈ S. It remains to argue that Da = CchzRagzxa , where C = ∏ i∈S Ci and c = ∏ i∈S ci. 22 4. Aggregated Signature-Based Set Membership Proofs By construction it holds that: Da =g ∑ i∈S (∏ j∈S j 6=i cj ) si h ∑ i∈S (∏ j∈S j 6=i cj ) mi , CchzRagzxa = (∏ i∈S Ci )∏ i∈S ci h ∑ i∈S (∏ j∈S j 6=i cj ) mi g ∑ i∈S (∏ j∈S j 6=i cj ) si− (∏ j∈S cj )∑ i∈S xi = ( g ∑ i∈S xih ∑ i∈S Ri )∏ i∈S ci h ∑ i∈S (∏ j∈S j 6=i cj ) mi− (∏ j∈S cj )∑ i∈S Ri g ∑ i∈S (∏ j∈S j 6=i cj ) si− (∏ j∈S cj )∑ i∈S xi =g ∑ i∈S (∏ j∈S j 6=i cj ) si h ∑ i∈S (∏ j∈S j 6=i cj ) mi , =⇒ Da = CchzRagzxa Combining the above results it has been shown that Da = CchzRagzxa ∧ ai = e(Vi, y)cie(Vi, g)−zxie(g, g)zτi for all i ∈ S. Implying thatVerify(Aggregate({Prove( pp, i, Ci, xi,Φ)}i∈S)) = 1. Zero-Knowledge The zero-knowledge property of Construction 2 follows from the zero-knowledge property of Construction 1. Soundness The aggregated set membership proof in Construction 2 satisfies the soundness prop- erty stated in chapter 3 under the assumptions that the aggregation is performed according to the algorithm Aggregate in Construction 2, that provers cannot com- municate or collaborate and that the set membership proof in Construction 1 satisfies the soundness in Definition 4. To prove this it has to be shown that if for any i ∈ S the secret xi /∈ Φ then it holds that Prob[Verify(Aggregate({Prove(pp, i, Ci, xi,Φ)}i∈S)) = 1] < ε, for some negligible ε. Let T denote the index-set of the malicious provers. Assume that all honest provers pi, such that i ∈ S\T , computes their set membership proofs, Σi, according to Prove. If the algorithm Verify validates true then ai = e(Vi, y)cie(V, g)zxie(g, g)zτi for all i ∈ S. Thereby the soundness assumption of the set membership proofs in Construction 1 implies that the values ai, Vi, zxi , zτi must be computed according to the algorithm Prove in Construction 2. Implying that the malicious provers, pi for i ∈ T , must construct their set membership proofs, Σi, and Pedersen commitments, 23 4. Aggregated Signature-Based Set Membership Proofs Ci, such that the following is fulfilled: Vi = Aτixi , ai = e(Vi, g)−sie(g, g)ti , Di = gs̃ihm̃i , zxi = si − xici, zτi = ti − τici, zRi ∈ F, Ci = gx̃ihR̃i , where x̃i 6= xi and xi ∈ Φ. It is not required that s̃i = si, m̃i = mi, R̃i = Ri are equalities nor inequalities. For the algorithm Verify to validate true it has to hold that Da = CchzRagzxa , where Da, zRa , zxa is the aggregation of Σi for all i ∈ S according to equation (4.1). By expanding the equality it follows that: Da =g ∑ i∈T (∏ j∈S j 6=i cj ) s̃i+ ∑ i∈S\T (∏ j∈S j 6=i cj ) si h ∑ i∈T (∏ j∈S j 6=i cj ) m̃i+ ∑ i∈S\T (∏ j∈S j 6=i cj ) mi CchzRagzxa = ( g ∑ i∈T x̃i+ ∑ i∈S\T xih ∑ i∈T R̃i+ ∑ i∈S\T Ri )∏ j∈S cj h ∑ i∈T (∏ j∈S j 6=i cj ) zRi h ∑ i∈S\T (∏ j∈S j 6=i cj ) mi− ∑ i∈S\T (∑ i∈S cj ) Ri g ∑ i∈S (∏ j∈S j 6=i cj ) si− (∏ j∈S cj )∑ i∈S xi = g ∏ j∈S cj (∑ i∈T x̃i+ ∑ i∈T xi ) + ∑ i∈T (∏ j∈S j 6=i cj ) si h (∏ j∈S cj )∑ i∈T R̃i+ ∑ i∈T (∏ j∈S j 6=i cj ) zRi g ∑ i∈S\T (∏ j∈S j 6=i cj ) si h ∑ i∈S\T (∏ j∈S j 6=i cj ) mi . Both above equations can be interpreted as Pedersen commitments. It is as- sumed, under the discrete logarithm assumption, that two Pedersen commitments cannot be equal unless their arguments are equal. This implies that the exponents of g and h are equal for the two above equations. Consider the exponent of g this leads to: ∑ i∈T ( ∏ j∈S j 6=i cj ) s̃j = ∏ j∈S cj (∑ i∈T x̃i + ∑ i∈T xi ) + ∑ i∈T ( ∏ j∈S j 6=i cj ) si. (4.2) It remains to argue that the equality in equation (4.2) cannot hold unless x̃i = xi for all i ∈ S. First consider the case when the set T only consists of one element, implying that there is only one malicious prover. Without loss of generality assume that this is the kth prover, pk. Under this assumption equation (4.2) can be rewritten as,( ∏ j∈S j 6=k cj ) s̃k = ( ∏ j∈S j 6=k cj ) ck ( x̃k + xk ) + ( ∏ j∈S j 6=k cj ) sk =⇒ s̃k = ck ( x̃k + xk ) + sk If it would be possible to choose s̃k = ck ( x̃k + xk ) + sk, it would contradict the soundness assumption of Construction 1. Thereby if |T | = 1, it must hold that x̃k = xk. 24 4. Aggregated Signature-Based Set Membership Proofs Assume |T | > 1 and k ∈ T such that pk is a malicious prover. Under the assump- tion that the provers cannot communicate or collaborate, the proofs {Σi}i∈S,i 6=k, can be considered random values for the prover pk. Equation (4.2) can be rewritten as: ( ∏ j∈S j 6=i cj ) s̃k + Random︷ ︸︸ ︷∑ i∈T i 6=k ( ∏ j∈S j 6=i cj ) s̃j = ( ∏ j∈S j 6=k cj ) ck ( x̃k + xk ) + ( ∏ j∈S j 6=k cj ) sk + Random︷ ︸︸ ︷∏ j∈S cj (∑ i∈T i 6=k x̃i + ∑ i∈T i 6=k xi ) + Random︷ ︸︸ ︷∑ i∈T i 6=k ( ∏ j∈S j 6=i cj ) si If x̃k 6= xk, this would imply that it is possible to cheat in Construction 1 by adding random values to Di and zxi . This is a contradiction to the soundness assumption of the set membership proof in Construction 1. This implies that x̃k = xk. Thereby, it is proved that if for any i ∈ S the secret xi /∈ Φ, it holds that Prob[Verify(Aggregate({Prove(pp, i, Ci, xi,Φ)}i∈S)) = 1] < ε, for a negligible ε. Theorem 4 (Completeness, Zero-Knowledge and Soundness). Assume that the aggregated proof Σa is computed according to algorithm Aggregate in Construc- tion 2, that the parties constructing the proofs, {Σi}i∈S , cannot communicate and that the set membership proof in Construction 1 satisfies the requirements stated in Definition 4. Then the aggregated signature-based set membership proof in Con- struction 2 satisfies the completeness, zero-knowledge and soundness requirements for aggregated set membership proofs, stated in chapter 3. Proof. The proof follows from the arguments given above. 25 4. Aggregated Signature-Based Set Membership Proofs 26 5 Implementation and Evaluation The construction of aggregated signature-based set membership proofs derived in chapter 4 is in this chapter implemented and evaluated in terms of runtime. The construction is compared with itself for different settings in section 5.2 and in section 5.3 it is compared to the state-of-the-art Bulletproofs. 5.1 Implementation A prototype of the aggregated signature-based set membership proofs is imple- mented in Golang. The implementation is based on the code for the signature-based set membership [13], and is available on GitHub [9]. Both the construction consid- ering one aggregating party and the construction considering multiple aggregating parties are implemented in Golang. The purpose of the implementation is to test the above-proposed constructions and provide runtime evaluations, consequently the code should not be considered as a secure implementation. Implementation parameters The parameter settings used for the implementation are defined below. The number of provers is fixed to 100, unless otherwise stated, and the verifier is assumed to be a single party. The number of aggregating parties, |K|, varies between |K| = 1, 5, 10 or 20. The set of proofs are split evenly between all aggregating parties implying that |Sk| is equal for all k ∈ K. The set Φ consists of 182 elements belonging to the interval [0, 1000]. The signature-based set membership proofs are based on an elliptic curve group, using the libsecp256k1 library from the Go-Ethereum repository. Since the fastest known algorithm to solve the elliptic curve discrete logarithm problem (ECDLP) requires O( √ n) steps, the underlying field has to be of size ∼ 256-bits to obtain a 128-bit security. Therefore the finite field F = Zp, where p is a 256-bit prime number. The hardware used for benchmarking, throughout the entire paper, has 1.6 GHz Dual-Core Intel Core i5−5250U CPU, 8GB 1600 MHz DDR3 RAM and runs macOS 10.15. 27 5. Implementation and Evaluation Table 5.1: Timing in seconds for algorithms Aggregate and Verify in Construc- tion 5 considering different numbers of aggregating parties, |K|. |K| Aggregate [s] Verify [s] 1 58.84 8.09 2 19.10 8.15 5 2.22 8.16 10 0.60 8.33 Not aggregated - 9.29 5.2 Trade-off between Aggregation and Verifica- tion The aggregation of set membership proofs is computationally heavy. To reduce the computation required by a single aggregating party the aggregation can be split between several aggregating parties as in Construction 5 in Appendix B. If the set K in Construction 5 consists of one single element and Sk = S, then constructions 2 and 5 are equivalent. Hence this section will consider Construction 5 for various number of aggregating parties. Table 5.1 presents the trade-off between increased verification time due to vali- dating multiple aggregated proofs and reduced runtime of an individual aggregating party obtained by splitting the aggregation between several parties. The number of aggregating parties varies between 1, 2, 5 and 10, while the number of proofs is fixed to 100. An individual aggregating party thus has to aggregate 100, 50, 20 or 10 proofs respectively and the verifier has to verify 1, 2, 5 or 10 aggregated proofs respectively. In Table 5.1 the runtime for the algorithm Aggregate is given per aggregating party and the runtime for Verify is for verification of all aggregated proofs. It is noted that the aggregation is a computationally demanding procedure. Considering one aggregating party, the runtime required to aggregate 100 proofs is almost one minute. While the reduction in runtime for verifying the aggregated proof instead of verifying all 100 proofs separately is just above one second. This illustrates that aggregation does not reduce the total runtime for the entire construction, but rather move computations from one party to another and thereby allows offloading computations from the verifier. Figure 5.1, which is a visualisation of the values in Table 5.1, shows that if the aggregation is shared between a set of aggregating parties the runtime per aggregat- ing party is reduced almost exponentially. At the same time the increased runtime for verifying multiple aggregated proofs is linear. Resulting in that splitting the aggregation between a set of aggregating parties reduced the total runtime for the construction and per aggregating party. 28 5. Implementation and Evaluation Figure 5.1: Timing in seconds for running the algorithms Aggregate and Verify in Construction 5 considering different numbers of aggregating parties. The number of aggregating parties varies between 1, 2, 5 and 10. The figure is a visualisation of the results presented in Table 5.1. 5.3 Comparison to Bulletproofs In this section, the construction of aggregated signature-based set membership proofs are compared to the state-of-the-art Bulletproofs. The focus of compari- son is the runtime of a party verifying of multiple proving parties. In this section the aggregation is considered to be performed by a single party, i.e |K| = 1. Before presenting the results, Bulletproofs are described in more detail. Bulleproofs settings The original paper about Bulletproofs [4] presents a method for aggregating Bul- letproofs such that n parties, each having committed to a Pedersen commitment, can generate a single Bulletproof verifying that each commitment hides a secret in an allowed range. The proposed method for aggregation is an interactive construc- tion, since it is required that all provers construct their proofs using for the same challenges. If the provers were to use different challenges the verification would fail. To Conclude, Bulletproofs can be aggregated with the cost of an interactive construction. Since this paper aims to investigate non-interactive constructions, non aggregated Bulletproofs are considered. Therefore the verifier has to verify all Bulletproofs separately, i.e once for each prover. The computational complexity for verification of a Bulletproof depends on the maximum upper bound of the range, i.e it depends on n determining the range [0, 2n). This motivates to see how the runtime is affected by considering different 29 5. Implementation and Evaluation Table 5.2: Runtime for verification of 100 proofs constructed using three different ZKP. The three considered proof constructions are: Bulletproofs, with a maximal upper bound equal to 28 and 232, and aggregated signature-based set membership proofs. Verify [s] Bulletproofs, n = 8 2.98 Bulletproofs, n = 32 10.22 Aggregated Set Membership Proofs 8.09 maximal upper bounds. The maximal upper bound of Bulletproofs is 2n, for some n that is a power of 2. Two different values of n are considered for comparison n = 8 and n = 32. Bulletproofs can be modified to allow arbitrary ranges [a, b], such that b < 2n and a < b , with the same approach as presented for the signature-based range proofs and illustrated in Figure 2.1. This is exploited and the range is set to [18, 200]. Runtime Comparison This section will compare runtime results considering the verification of 100 proofs using Bulletproofs and aggregated signature-based set membership proofs. Bullet- proofs with an upper bound equal to 28 and 232 are considered meaning that in total three constructions are compared. A remark is that the computational complexity of Bulletproofs depend on the variable n, where n determines the maximal upper bound of the range. The signature- based set membership proofs have a computational complexity of O(1) for the proof construction and verification, meaning that the complexity is independent of the size of the set Φ. Therefore, to provide a comparison between Bulletproofs and ag- gregated signature-based set membership proofs considering different applications scenarios, the runtime for verification of Bulletproofs is presented considering two different values of n. Table 5.2 shows the runtime for the verification of 100 proofs using the three considered constructions. Bulletproofs with an upper bound equal to 28 is considerably faster than the other constructions, however, it is highly limited in its applications since the upper bound is fairly low. The runtime for Bulletproof with an upper bound equal to 232 is longer than for aggregated set membership proofs. Thus, aggregated signature- based set membership proofs is a relatively fast and yet flexible implementation. In Figure 5.2 the runtime for verification is given as a function of the number of provers. In addition to the above constructions, signature-based set membership proofs are considered. The runtime has been measured considering 1, 25, 50, 75, 100, 125 and 150 provers respectively. From the figure, it is seen that there is a linear rela- tionship between the number of provers and the runtime for verification. It is also seen that the runtime relationship between the different constructions seen in Table 5.2, appears to remain independent of the number of provers. 30 5. Implementation and Evaluation Figure 5.2: Runtime for verification of multiple provers as a function of the num- ber of provers. Verification of four different constructions of proofs are considered: aggregated signature-based set membership proofs, signature-based set membership proofs, Bulletproofs with a maximal upper bound equal to 28 and Bulletproofs with a maximal upper bound equal to 232. In Figure 5.2 it is noted that the difference between the runtime for the aggre- gated signature-based set membership proof and the ordinary signature-based set membership proofs, increases with the number of provers. This result is expected since the difference in the number of computation performed by the verifier increases linearly with the number of provers. To conclude, whether Bulletproofs or aggregated signature-based set member- ship proofs are faster in terms of runtime for the verifier depends on the application, since the runtime for verifying Bulletproofs depends on the maximal upper bound of the range. The rule of thumb is that aggregated signature-based set membership proofs are faster when considering a large range and Bulletproofs are faster when considering a small range. It is however always true that set membership proofs are more flexible than range proofs since they allow non-continuous discrete sets. An important thing to mention, although not the focus of this comparison, is that the set-up phase of aggregated signature-based set membership proofs is linear in the number of elements in the set, resulting in that it is computationally demanding for large sets. 31 5. Implementation and Evaluation 32 6 Application in VAHSS In this chapter, an application of the aggregated set membership proof is presented and evaluated. As discussed in chapter 1, VAHSS is an example where multiple data providers, henceforth denoted clients, participate. In this chapter first a construction of VAHSS that verifies the servers computation is presented, then it is derived how to extend the verification to also include the clients. Then different methods for verifying clients are compared. The comparison mainly focuses on comparing aggregated signature-based set membership proof presented in Construction 2 with the state-of-the-art Bulletproofs for verification of clients to see how the runtime of the construction is affected. 6.1 VAHSS The considered construction of VAHSS presented in [19], implemented and bench- marked in [18], makes use of homomorphic hash functions to verify the computations performed by servers. Assume that n clients and m servers participate in the VAHSS construction. The sets N = {1, ..., n} and M = {1, ...,m} are introduced to simplify notation. The clients are denoted ci for i ∈ N , and their respective data xi. The servers in the construction are refereed to sj for j ∈M. Each client ci splits the secret xi into m shares, denoted {xij}j∈M, such that xi = ∑ j∈M xij and sends one share to each server. Each server sj, j ∈ M, receives shares from all n clients and computes and publishes the partial sum yj = ∑ i∈N xij. Then the final sum can be computed by any party by summing the public partial sums, which gives y = ∑ j∈M yj = ∑ j∈M ∑ i∈N xij = ∑ i∈N ∑ j∈M xij = ∑ i∈N xi. A proof σ of the servers computations is obtained accordingly. Each client ci publishes a checksum τi = gxi+Ri , where xi is the secret hidden by the distributed shares and Ri ∈R F is such that Rn = φ(p)d ∑n−1 i=1 Ri φ(p) e − ∑n−1 i=1 Ri. Each server sj computes a partial proof σj = gyj . Finally the verification is done by checking if∏ j∈M σj = ∏ i∈N τi ∧ ∏ i∈N τi = gy. If it holds the servers computations are proved to be correct. For a precise implementation and proof of correctness, security and verification the reader is refereed to the original paper about VAHSS [19]. 33 6. Application in VAHSS 6.2 Client and Server VAHSS The VAHSS construction discussed in section 6.1 assumes honest clients and verifies the servers. This section extends the VAHSS construction to verify both the clients’ input and the computations performed by the servers. First it is stated how to extend the VAHSS construction to additionally verify clients. Then a construction, using range proofs or set membership proofs, to verify clients is derived. It is then discussed how such a construction can be modified to use aggregated set membership proofs for verification of client’ inputs. Extending VAHSS to verify clients To ensure honest clients it is not sufficient to construct and perform a set member- ship proof and a VAHSS scheme separately. In such a protocol the verifier cannot be sure that the secret proven to be in the allowed set is the same as the secret hid- den by the shares. The same principle holds considering range proofs. Therefore, a connection between the shares generated in the algorithm ShareSecret in the VAHSS construction and the secret hidden in a Pedersen commitment is desired. Proving that the sum of the shares is equal to the secret in a Pedersen commitment and then proving that the secret in the Pedersen commitment is in an allowed range or set convinces the verifier that the shares represent a secret that is in the allowed range or set. In the VAHSS construction the clients publishes, in addition to the shares, the checksums τi for the secrets xi. Recall that the definition of the checksum is τi = gxi+Ri . Hereafter, the clients compute and outputs the Pedersen commitments πi = gxihRi , instead of the previously computed checksums τi. Given a commitment πi, the clients can construct a range proof or set membership proof of the committed secret. It remains to argue that this would ensure the verifier that the secret hidden by the shares is the same secret proved to be in the allowed range or set as for all i ∈ N . Assume that client ck commits to the value x̂k in the Pedersen commitment πk, constructs the shares {xkj}j∈M such that xk = ∑ j∈M xkj 6= x̂k and generates a ZKP that x̂k belongs to the set Φ or range [a, b]. Since xk 6= x̂k this does not necessarily imply that the secret hidden by the shares belongs to the range or set. Then ∏m i=1 πi 6= gy and thereby the verification of servers does not succeed. Thus it has to hold that xk = x̂k for the protocol to succeed and any cheating client is detected. It is not possible to determine which party cheated and more precisely not even if the cheating party was a client or a server. Remark 1. The correctness, security and verifiability requirements of a VAHSS construction holds after replacing the checksums τi = gxi+Ri with a Pedersen com- mitment πi = gxihRi in the VAHSS construction, [19]. Additionally if a range proof or set membership proof, denoted Σi, that satis- fies the soundness, completeness and zero-knowledge requirements of zero-knowledge proofs is constructed of the secret xi in the Pedersen commitment πi, for all clients ci in the VAHSS construction. Then any PPT adversary A who can modify the 34 6. Application in VAHSS Pedersen commitments πi to any π′i ∀i ∈ T , where T is the set of corrupted clients, has a negligible probability of choosing a commitment π′i such that verification of all the proofs Σi and the VAHSS validates true. Proof of remark: The remark follows from that replacing τi with πi for i = 1, ..., n, it still holds that: ∏ i∈N πi = ∏ i∈N gxihRi = g ∑ i∈N xih ∑ i∈N Ri = gyh φ(N) ⌈∑n−1 i=1 Ri φ(N) ⌉ = gy Thereby it follows that: n∏ i∈N τi = ∏ i∈N πi. Further the Pedersen commitment is perfectly hiding as well as computationally binding and thus it follows that the requirements are still fulfilled. From the soundness of range proofs and set membership proofs, and the above argument that the secret hidden in the commitment πi must be the same as the secret obtained by combining the the shares {xij}j∈M for all i = N , it follows that any adversary who can modify the commitments πi has a negligible probability of doing so such that the proofs Σi and the VAHSS construction validates true. � Verifying clients using set membership proofs or range proofs A VAHSS where clients are verified by publishing range proofs or set membership proofs is presented in Construction 3. In order to clarify the changes made to extend the construction to verify clients, the differences to the VAHSS construction presented in [19] are pointed out. The algorithms ShareSecret andVerify has been modified, and the algorithms ProveSecret and GenerateCommitment have been added. More precisely, the algorithm ShareSecret does not output the checksum τi, instead the Pedersen com- mitment πi is computed in the algorithm GenerateCommitment. The algorithm ProveSecret constructs a set membership proof or range proof denoted Σi given the commitment πi. In addition to the steps of the algorithm Verify in the VAHSS construction presented in [19], the algorithm Verify also validates the proofs Σi for all i ∈ N . The algorithmsGenerateCommitment andProveSecret are executed by the clients and the other algorithms are executed by the same party as in the VAHSS construction in [19]. Remark 1 implies that Construction 3 satisfies the correctness, security and ver- ification requirements for a VAHSS construction and that the verification of clients’ input satisfies the completeness, soundness and zero-knowledge requirements of the considered range proofs or set membership proofs. Verifying clients using aggregated set membership proofs Construction 4 describes a client and server VAHSS compatible with aggregated set membership proofs for verification of clients. The algorithms in Construction 4 are the same as in Construction 3 except that the algorithm PartialAggregate is introduced and the algorithm Verify is modified. 35 6. Application in VAHSS Construction 3 : Client and Server Verifiable additive homomorphic se- cret sharing Goal: Compute the sum y = ∑n i=1 xi. The values xi are kept secret. The servers computations and the clients shared values are verified. • ShareSecret (1λ, i, xi) 7→ {xij}j∈M Pick uniformly at random the coefficients, {ai}i∈{1,..,t} ∈R F and define a t- degree polynomial pi to be on the form pi(X) = xi +a1X + ...+atX t. Put the shares xij = λijpi(θij) for j ∈M. The parameters θij and Lagrange coefficients λij are chosen such that pi(0) = ∑m j=1 λijpi(θij). Output {xij}j∈M. • GenereteCommitment(1λ, i, xi) 7→ πi Let Ri ∈ F be the output of a PRF such that Rn ∈ F satisfies Rn = φ(N)d ∑n−1 i=1 Ri φ(N) e − ∑n−1 i=1 Ri. Compute and output πi = E(xi, Ri) = gxihRi . • ProveSecret (pp, xi, πi) 7→ Σi Construct a range proof or set membership proof, denoted Σi, for the Pedersen commitment πi of the secret xi, on the range [a, b] or a set Φ. All required public parameters, pp, needed to construct the proof Σi is assumed to be pre-shared and known by all parties. • PartialEval (j, {xij}i∈N ) −→ yj Compute and output yj = ∑n i=1 xij. • PartialProof (j, {xij}i∈N ) −→ σj Compute and output σj = ∏n i=1 g xij = g ∑n i=1 xij = gyj = H1(yj). • FinalEval ({yj}j∈M) −→ y Compute and output y = ∑m j=1 yj. • FinalProof ({σj}j∈M) −→ σ Compute and output σ = ∏m j=1 σj = ∏m j=1 g yj = g ∑m j=1 yj = gy = H1(y). • Verify ({πi}i∈N , x, y, {Σi}i∈N ) −→ {0, 1} Compute and output σ = ∏n i=1 πi ∧ ∏n i=1 πi = H1(y)∧{VerifyProof(Σi)}i∈N . VerifyProof is the verification algorithm of the proofs {Σi}i∈N . 36 6. Application in VAHSS The algorithm PartialAggregate is run by all aggregating parties in the set K and the algorithm Verify is modified such that it verifies the aggregated proofs instead of the individual clients’ proofs. If the server computing the partial sums yj are responsible for aggregation of the clients set membership proofs, then no new parties are introduced to the VAHSS construction to aggregate the proofs. Then the set K is equal toM in construction 4. For aggregation in Construction 4 to be sound, the aggregation must either be performed by a trusted party or split between at least two aggregating parties. If the aggregation is performed by an untrusted party, this party can cheat in the aggregation of the proofs, by exploiting that the sum y can be computed once the servers have performed the algorithm PartialEval and that h ∑ i∈N Ri = 1modφ(p). Note that this induces that the assumptions of Theorem 3 are not fulfilled, since the aggregation party has additional knowledge beyond the input to the algorithm Aggregate and the commitments {Ci}i∈S . Since y is known to the aggregating party, the aggregated proof Σa can be constructed as, Da = Ck+c, zRa = kφ(N) and zxa = ky, where y = ∑ i∈N xi and k ∈R F. Then it follows that: Da = Ck+c = ( gk ∑n i=1 xihk ∑n i=1 Ri) )( g( ∏n i=1 ci) ∑n i=1 xi)h( ∏n i=1 ci) ∑n i=1 Ri) ) CchzRagzxa = Cchkφ(N)gky = ( g( ∏n i=1 ci) ∑n i=1 xi)h( ∏n i=1 ci) ∑n i=1 Ri) ) hkφ(N)gky = ( g( ∏n i=1 ci) ∑n i=1 xi)h( ∏n i=1 ci) ∑n i=1 Ri) ) gkyhkφ(N)d ∑n−1 i=1 Ri φ(N) e) =⇒ Da = CchzRagzxa . It has been shown that if one party aggregating all clients’ set membership proofs the aggregation is not sound, since the aggregated proof can be constructed such that it validates true without proving the statement in equation 3.1. If multiple parties aggregates subsets of the proofs, the assumptions in Theorem 3 holds, this follows from that the sum of the secrets and random values are unknown considering any true subset of the clients. Under the assumption that the aggregation is sound, Remark 1 applies to Con- struction 4. Thereby, if the aggregation is performed by a trusted party or is split between at least two independent aggregating parties, Construction 4 satisfies the correctness, security and verification requirements for a VAHSS construction and the verification of clients’ input satisfies the completeness, soundness and zero-knowledge requirements of the considered range proofs or set membership proofs. 6.3 Implementation An implementation of Constructions 3 and 4 is obtained to investigate the proposed clients and server VAHSS in a practical setting and comparing the runtime for different methods for verifying clients. Bulletproofs, aggregated and non-aggregated signature-based set membership proofs implemented in Golang are publically available on Github, [13] [9]. The VAHSS construction implemented in both python and C++, is available at [17] and [16] respectively. 37 6. Application in VAHSS Construction 4 : Client and Server Verifiable additive homomorphic se- cret sharing Goal: Compute the sum y = ∑n i=1 xi. The values xi are kept secret. Servers computations and clients shared values are verified. • ShareSecret (1λ, i, xi) 7→ {xij}j∈M Pick uniformly at random the coefficients, {ai}i∈{1,..,t} ∈R F and define a t- degree polynomial pi to be on the form pi(X) = xi +a1X + ...+atX t. Put the shares xij = λijpi(θij) for j ∈M. The parameters θij and Lagrange coefficients λij are chosen such that pi(0) = ∑m j=1 λijpi(θij). Output {xij}j∈M. • GenereteCommitment(1λ, i, xi) 7→ πi Let Ri ∈ F be the output of a PRF such that Rn ∈ F satisfies Rn = φ(N)d ∑n−1 i=1 Ri φ(N) e − ∑n−1 i=1 Ri. Compute and output πi = E(xi, Ri) = gxihRi . • ProveSecret (pp, xi, πi) 7→ Σi Construct a range proof or set membership proof, denoted Σi, for the Pedersen commitment πi of the secret xi, on the range [a, b] or a set Φ. All required public parameters, pp, needed to construct the proof Σi is assumed to be pre-shared and known by all parties. • PartialEval (j, {xij}i∈N ) −→ yj Compute and output yj = ∑n i=1 xij. • PartialProof (j, {xij}i∈N ) −→ σj Compute and output σj = ∏n i=1 g xij = g ∑n i=1 xij = gyj = H1(yj). • PartialAggregate (pp, k,Sk, {Σi}i∈Sk) −→ Σak On the input {Σi}i∈Sk where Sk ⊆ {1, ..., n}, the set of proofs is aggregated according to the algorithmAggregate in Construction 2 and aggregated proof Σak is published. • FinalEval ({yj}j∈M) −→ y Compute and output y = ∑m j=1 yj. • FinalProof ({σj}j∈M) −→ σ Compute and output σ = ∏m j=1 σj = ∏m j=1 g yj = g ∑m j=1 yj = gy = H(y). • Verify ({πi}i∈N , x, y, {Σak}k∈K) −→ {0, 1} Compute and output σ = ∏n i=1 πi∧ ∏n i=1 πi = H(y)∧{VerifyProof(Σak)}k∈K. VerifyProof is the verification algorithm in Construction 2. 38 6. Application in VAHSS To implement Construction 3 and 4, the VAHSS algorithms need to be callable from the same programs as the algorithms for Bulletproofs, signature-based set mem- bership proofs and aggregated signature-based set membership proofs. The VAHSS algorithms have been translated to Golang, to solve the problem of having the im- plementations written in different programming languages. The implementation is available at [9]. To provide an implementation of Construction 3 and 4 besides translating the VAHSS code to Golang the implementations have also been slightly modified. The VAHSS construction has as discussed above been adjusted such that it considers a Pedersen commitment πi instead of the checksum τi. The implementations of Bulletproofs, signature-based set membership proofs and aggregated signature-based set membership proofs have also been adjusted to be compatible with the VAHSS algorithms. These adjustments are merely to merge the constructions and does not change the semantics of the constructions. The modified implementations are available at [9]. Implementation parameters The finite field F is generated by a prime of size 256-bit. The number of servers is set to 5, |M| = 5, and the number of clients to 100, |N | = 100. The set of aggregation parties K is assumed to consist of a single party, meaning that |K| = 1. Remark that the trade-off between runtime for aggregation and verification de- pending on the number of aggregation parties is presented in section 5.2. The result presented there translates directly to the runtime of the aggregation and the veri- fication of clients in a server and client VAHSS. Thereby, although |K| = 1 in this section the runtime considering multiple aggregating parties can be obtained by studying the results presented in chapter 5. The range is set to [18, 200] for the implementation of Bulletproofs, and thus the upper bound of the Bulletproof is set to 2n, where n = 8. The size of the set Φ is put to the length of the range, |Φ| = 200− 18 = 182, for both the aggregated and not aggregated signature-based set membership proofs. A final remark about the implementation is that its purpose is to test the above- proposed constructions and provide runtime evaluations, the code has not been tested enough to be considered as a secure implementation. 6.4 Prototype analysis The runtime for the algorithms in Construction 3 and 4 is presented in Table 6.1. Construction 3 is benchmarked considering two different constructions for verifying clients: Bulletproofs and signature-based set membership proofs. Construction 4 is benchmarked considering aggregated signature-based set membership proofs, with a single trusted aggregating party. In Construction 3 and 4 there is one algorithm called Verify, verifying both clients and servers. To separately measure the runtime for verifying the servers and clients the algorithm Verify is split into two procedures, VerifyServers and 39 6. Application in VAHSS VerifyClients. The first procedure, VerifyServers, performs the verification of the servers computations. The second procedure VerifyClients, verifies the clients by evaluating their range proofs or set membership proofs. To clearly state what the algorithms VerifyServers and VerifyClients correspond to, consider the following reformulation of the algorithm Verify: • Verify (pp, {πi}i∈N , y, {Σi}i∈N ) −→ {0, 1} Verify the clients and servers according to, – VerifyServers ({πi}i∈N , y) −→ {0, 1}) Compute and output σ = ∏n i=1 πi ∧ ∏n i=1 πi = H(y). – VerifyClients ({πi}i∈N{Σi}i∈N ) −→ {0, 1} For each proof Σi, verify that it is correct. This implies runningVerifyProof(πi,Σi) for all i ∈ N , where VerifyProof is the verification algorithm associated with the algorithm used to construct the proof, Σi. If the proofs have been aggregated then the verification is performed for each aggregated proof instead of for each clients proofs. If all proofs are correct return 1, else 0. Return VerifyServers ∧VerifyClients Table 6.1: Runtime for the algorithms in Construction 3 and 4. The runtime of Construction 3 is presented using Bulletproofs and signature-based set membership proofs to verify clients. Aggregated signature-based set membership proofs are used to verify clients in Construction 4 Construction 3 Construction 4 Bulletproofs Set membership Aggregated Set membership GenerateShares 95 [µs] 98 [µs] 98 [µs] ProveSecret 53 [ms] 66 [ms] 66 [ms] PartialEval 78 [µs] 71 [µs] 71 [µs] PartialProof 273 [µs] 5255 [µs] 5255 [µs] Aggregate 59 [s] FinalEval 689 [ns] 699 [ns] 699 [ns] FinalProof 50 [µs] 115 [µs] 115 [µs] VerifyClients 2979 [ms] 9288 [ms] 8120 [ms] VerifyServers 1672 [µs] 7947 [µs] 7947 [µs] In Table 6.1 the runtime for all algorithms are consistently faster when using Bulletproofs to verify the clients. Note that the considered range is [18, 200], hence it is sufficient to use n = 8 for the upper bound for the Bulletproofs. In section 5.3 it is noted that the runtime for verification of multiple clients increased significantly if the upper bound of the range is increased. This implies that if a larger range is considered the aggregated signature-based set membership would be faster than Bulletproofs for verification of all clients. This is seen in Chapter 5 in Figure 5.2. Uniformly, independent of which construction used to verify clients, the runtime for VerifyServers is approximately 103 times faster than for VerifyClients. This highlights how expensive the verification of clients is and motivates the attempt to reduce the computations required to verify multiple clients by aggregating set 40 6. Application in VAHSS membership proofs. Considering the runtime of VerifyClients, it is noted that aggregation of signature-based set membership proofs reduce the runtime by 13%. The set mem- bership proofs are only partly aggregated and thereby the runtime depends on the number of provers. Consequently, when a large number of clients participate the verification of clients still becomes a bottleneck of the construction. It is noted that the algorithms PartialProof, FinalProof and VerifyServers differs noteworthy in runtime for different constructions for verifying clients. These algorithms, as described in Construction 3 and 4, are seemingly independent of the construction used to verify clients. The difference in runtime comes from that different libraries for the elliptic curve groups are used for Bulletproofs and the signature-based set membership proofs. The libraries have not been benchmarked against each other, and whether the difference in runtime can be reduced via opti- misations has not been investigated. 41 6. Application in VAHSS 42 7 Discussion and Conclusion Discussion The simplest aggregation of set membership proofs is to construct the aggregated proof as the element-wise product of all individual proofs. Appendix C states how such an aggregation can be implemented. It also shows that it results in a construc- tion that does not satisfy the completeness requirement of aggregated set member- ship proofs, implying that cleverer aggregation is required. Moreover, it is noted that if the challenges are equal for all proofs, then the completeness requirement is satisfied for the first part of the validation. The chal- lenges depend on randomness in the proofs, thereby it cannot be guaranteed that they are equal. In the aggregated signature-based set membership proof presented in chapter 4 the challenges appear as a product, which resolves the problem of unequal challenges. The complexity of the presented aggregated signature-based set membership proof depends on the number of provers, since ai = e(Vi, y)cie(Vi, g)−zxie(g, g)zτi is checked separately for each proof Σi, i ∈ S, in the verification. Therefore it can be interpreted as a partial aggregation of the proofs. A complete aggregation of the signature-based set membership proofs fulfilling the completeness requirement has not been found nor proved impossible to construct. The reasoning of why a complete aggregation of the signature-based set membership proofs does not fulfil the completeness requirement is given in appendix D. In the verification of the signature- based range proofs derived from the signature-based set membership proofs [5], the equality ai = e(Vi, y)ce(Vi, g)−zxie(g, g)zτi is checked separately for each j ∈ Zl. This can be seen as an indicator that it is not possible to efficiently aggregate the entire signature-based set membership proofs. The presented construction of aggregated signature-based set membership proof can be translated to a construction of aggregated signature-based range proofs. The signature-based range proofs are very similar in construction to the signature- based set membership proofs and thereby the aggregation can easily be adjusted to aggregate the range proofs. Details on how to generalise the aggregation are not given, but it follows directly from inspection. Using set membership proofs or range proofs to verify clients in a VAHSS con- struction prevents clients from cheating, but no requirement ensures that clients do not lie. Cheating means that a client shares a value not in the allowed set or range and lying means that the client shares a value in the allowed set or range, but not the truthful value. 43 7. Discussion and Conclusion Conclusion This paper has presented a definition of aggregated set membership proofs, including the completeness, soundness, and zero-knowledge requirements that it should fulfil. According to the definition of aggregated set membership proofs, signature-based set membership proofs have been partly aggregated. Since a part of the proofs is verified separately for each prover, the complexity for verification depends on the number of provers. However, the computational complexity required per prover is decreased, due to that, a part of the proofs is aggregated, such that it is checked once to validate all provers. It has been proved that an untrusted party must perform the aggregation ac- cording to the protocol, for the verification to validate true. The assumptions made to prove this are that: the provers do not collaborate with each other or the ag- gregating party and that the aggregated proof Σa is such that Da 6= Cc. C is the product of all provers Pedersen commitments and c is the product of all challenges. The completeness, soundness and zero-knowledge requirements for aggregated set membership proofs are proved to hold for the presented construction of aggre- gated signature-based set membership proofs. This was proved under the assump- tions that the aggregation was performed according to the algorithm Aggregate, proves does not collaborate and that the signature-based set membership, [5], sat- isfies the requirements in Definition 4. The aggregated signature-based set membership proof has been implemented in Golang. Considering 100 provers, each having constructed a signature-based set membership proof, the verification was found to be approximately 13% faster for verifying an aggregated proof, computed according to algorithm Agrgegate, compared to verifying the proofs individually. The prototype analysis also showed that splitting the aggregation between several parties decreased the runtime per aggregating party almost exponentially. The verification time, in tandem, does not increase exponentially. The second part of this paper focused on the verification of clients in VAHSS constructions and comparing different methods for verifying clients. The VAHSS construction, presented in [19] has been modified to additionally verify the clients. Clients are verified by publishing set membership proofs or range proofs. Then the verifier, in addition to validating the servers computations, validates all clients set membership proofs or range proofs. To reduce the computations required by the verifier aggregated set membership proofs are considered for verification of clients. Implementations in Golang have been provided for the client and server VAHSS, considering Bulletproofs, aggregated and non-aggregated signature-based set mem- bership proofs for verification of clients. Future work In this section some question that has raised during the work is mentioned and discussed as possible future work. • A complete aggregation of a set membership proofs. The presented aggregated 44 7. Discussion and Conclusion signature-based set membership proof is partly aggregated and therefore the computational complexity of verification dependent on the number of provers. Providing a full aggregation of the signature-based set membership proof or alternatively construct a complete aggregation of some other set membership proofs would be two interesting results. • Constructing a non-interactive aggregation of Bulletproofs. Bulletproofs are state of the art range proofs aggregating them using a non-interactive construc- tion would be useful in many applications. To the knowledge of the author no such construction exists. • Prio+, [1], constitutes the same purpose as client and server VAHSS. The computations required by the clients in Prio+ is smaller compare to client and server VAHSS, due to that they are not required to construct a ZKP. However, the servers must communicate to verify the clients. An interesting topic would be to investigate if Prio+ can be modified such that the verification of clients can be obtained without communication between the servers and with a computational complexity independent of the number of clients. This would result in a construction highly efficient for both clients and servers. 45 7. Discussion and Conclusion 46 Bibliography [1] S. Addanki, K. Garbe, E. Jaffe, R. Ostrovsky, and A. Polychroniadou. Prio+: Privacy preserving aggregate statistics via boolean shares. Cryptology ePrint Archive, Report 2021/576, 2021. https://eprint.iacr.org/2021/576. [2] M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Proceedings of the 1st ACM Conference on Computer and Communications Security, CCS ’93, page 62–73, New York, NY, USA, 1993. Association for Computing Machinery. [3] D. Boneh and X. Boyen. Short signatures without random oracles. In C. Cachin and J. L. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, pages 56–73, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. [4] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bul- letproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy (SP), pages 315–334, 2018. [5] J. Camenisch, R. Chaabouni, and a. shelat. Efficient protocols for set mem- bership and range proofs. In J. Pieprzyk, editor, Advances in Cryptology - ASIACRYPT 2008, pages 234–252, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. [6] R. Chaabouni, H. Lipmaa, and A. Shelat. Additive combinatorics and discrete logarithm based range protocols. In R. Steinfeld and P. Hawkes, editors, Infor- mation Security and Privacy, pages 336–351, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. [7] H. Corrigan-Gibbs and D. Boneh. Prio: Private, robust, and scalable com- putation of aggregate statistics. In 14th USENIX Symposium on Networked Systems Design and Implementation (NSDI 17), pages 259–282, Boston, MA, Mar. 2017. USENIX Association. [8] G. Couteau, M. Klooß, H. Lin, and M. Reichle. Efficient range proofs with trans- parent setup from bounded integer commitments. Cryptology ePrint Archive, Report 2021/540, 2021. https://eprint.iacr.org/2021/540. [9] H. Ek. Aggregated signature based set membership proofs. https://github. com/ek-k-hanna/Aggregated-SMP, 2021. [10] S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of inter- active proof systems. SIAM Journal on Computing, 18(1):186–208, 1989. [11] J. Groth. Short non-interactive zero-knowledge proofs. In M. Abe, editor, Ad- vances in Cryptology - ASIACRYPT 2010, pages 341–358, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. [12] E. Morais, T. Koens, C. van Wijk, and A. Koren. A survey on zero knowledge range proofs and applications. SN Applied Sciences, 1(946), 2019. 47 https://eprint.iacr.org/2021/576 https://eprint.iacr.org/2021/540 https://github.com/ek-k-hanna/Aggregated-SMP https://github.com/ek-k-hanna/Aggregated-SMP Bibliography [13] E. Morais, T. Koens, C. van Wijk, A. Koren, P. Rudgers, and C. Ramaekers. Zero knowledge range proof implementation. https://github.com/ing-bank/ zkrp, 2020. [14] T. P. Pedersen. Non-interactive and information-theoretic secure verifiable se- cret sharing. In J. Feigenbaum, editor, Advances in Cryptology — CRYPTO ’91, pages 129–140, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg. [15] A. Shamir. How to share a secret. Commun. ACM, 22(11):612–613, Nov. 1979. [16] G. Tsaloli and G. Banegas. Additative vhsss implemented in c++. https: //github.com/tsaloligeorgia/AddVHSS, 2020. [17] G. Tsaloli and G. Banegas. Additative vhsss implemented in python. https: //github.com/gbanegas/VHSSS_temp, 2020. [18] G. Tsaloli, G. Banegas, and A. Mitrokotsa. Practical and provably secure dis- tributed aggregation: Verifiable additive homomorphic secret sharing. Cryp- tography, 4(3), 2020. [19] G. Tsaloli and A. Mitrokotsa. Sum it up: Verifiable additive homomorphic secret sharing. In J. H. Seo, editor, Information Security and Cryptology – ICISC 2019, pages 115–132, Cham, 2020. Springer International Publishing. [20] H. Yao, C. Wang, B. Hai, and S. Zhu. Homomorphic hash and blockchain based authentication key exchange protocol for strangers. In 2018 Sixth International Conference on Advanced Cloud and Big Data (CBD), pages 243–248, 2018. 48 https://github.com/ing-bank/zkrp https://github.com/ing-bank/zkrp https://github.com/tsaloligeorgia/AddVHSS https://github.com/tsaloligeorgia/AddVHSS https://github.com/gbanegas/VHSSS_temp https://github.com/gbanegas/VHSSS_temp A Correctness, Security and Verifiability of VAHSS Assume that a VAHSS construction consists of n clients and m servers, and that the index set of clients and servers are N and M respectively. A construction of VAHSS is a 7-tuple of PPT-algorithms (Setup, ShareSecret, PartialEval, PartialProof, FinalEval, FinalProof, Verify). Assuming that the algorithms are as defined in [19] they should satisfy the following correctness, verifiability and security requirements [19]: • Correctness It should always hold that Pr[Verify(pp, σ, y) = 1] = 1. pp are the public parameters constructed by the algorithm Setup, σ is the output of the algorithm FinalProof computed by the partial proofs σj, which are outputs of the algorithm PartialProof for ∀j ∈M. The value y is the output of the algorithm FinalEval. • Verifiability For any set T of corrupted servers and any PPT adversary A it should h