César Sabater
email: cesar.sabater@inria.fr

Florian Hahn
email: f.w.hahn@utwente.nl

Andreas Peter
email: andreas.peter@uni-oldenburg.de

Jan Ramon
email: jan.ramon@inria.fr

Private Sampling with Identifiable Cheaters

Keywords: differential privacy, sampling, zero knowledge proofs, multiparty computation

In this paper we study verifiable sampling from probability distributions in the context of multi-party computation. This has various applications in randomized algorithms performed collaboratively by parties not trusting each other. One example is differentially private machine learning where noise should be drawn, typically from a Laplace or Gaussian distribution, and it is desirable that no party can bias this process. In particular, we propose algorithms to draw random numbers from uniform, Laplace, Gaussian and arbitrary probability distributions, and to verify honest execution of the protocols through zero-knowledge proofs. We propose protocols that result in one party knowing the drawn number and protocols that deliver the drawn random number as a shared secret.

INTRODUCTION

Nowadays, randomization is an important algorithmic technique. Its numerous applications include randomized algorithms, e.g., for many problems the simplest or most efficient known solution strategy is a randomized algorithm, and hiding information, e.g., in cryptography or in differential privacy. While true randomness is hard to achieve in most cases it is sufficient to be able to generate pseudo-random numbers. A wide range of approaches exist to generate pseudo-random numbers of good quality.

The situation becomes more complicated when we consider generating random numbers in the context of multi-party computation between parties which do not trust each other. We are particularly interested in algorithms which allow multiple parties to draw a random number from a specified probability distribution in such a way that all parties can be convinced that the number drawn is truly random and that either all parties, only one party, or none of the parties learn the drawn random number. This implies that no party should be able to influence the probability distribution or be able to predict or guess the random number.

Such algorithms are particularly useful for differentially private federated machine learning using sensitive data from multiple data owners. In this setting, one would like to learn a statistical model M with parameters 𝜃 on the sensitive data of multiple data owners. Such model could reveal sensitive information and therefore one possible technique is to perturb the model before publication sufficiently such that it becomes differentially private [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF], i.e., such that from the perturbed model M with parameters θ one cannot distinguish a change in a single individual. This can be achieved by drawing some noise 𝜂 from an appropriate probability distribution, e.g., 𝜂 often is a vector of Laplace or Gaussian random variables, and setting θ = 𝜃 +𝜂. In such scenario it is important nobody knows 𝜂 as else that party could subtract 𝜂 from the published θ to obtain the sensitive model parameters 𝜃 . At the same time, all data owners want to be sure that 𝜂 is drawn correctly: if anyone can bias the distribution of this noise, privacy may not be guaranteed anymore or the model parameters may be biased in a way similar as what one can achieve with data poisoning [START_REF] Meital | Exploiting Social Navigation[END_REF][START_REF] Weckert | Google Maps hacks[END_REF].

In this paper we develop algorithms to verifiably draw random numbers. We consider uniform distributions, Laplace distributions, Gaussian distributions and arbitrary distributions. We develop strategies with three different privacy levels for the random number: strategies which verifiably draw a publicly known random number, strategies which verifiably draw a random number which is revealed to only one party and strategies which verifiably draw a random number and output it as a shared secret so that none of the parties knows the random number.

An important tool to prove correct behavior can be found in zero knowledge proofs (ZKP). These are cryptographic techniques that allow a party to prove statements without revealing anything else. Typically, one considers statements involving logical and arithmetic relations over private values which can be expressed using additions, multiplications and other elementary operations such as comparisons. For drawing from Laplace or Gaussian distributions, transcendental functions are needed. We work towards bridging this gap based on Cordic [START_REF] Walther | A unified algorithm for elementary functions[END_REF], a classic technique for computing such functions.

The main contributions of this paper can be summarized as follows: [START_REF] Aly | Benchmarking Privacy Preserving Scientific Operations[END_REF] we propose strategies to prove relationships involving logarithms or trigonometric functions in zero knowledge, [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF] we propose and compare several strategies to let a party verifiably draw Gaussian random numbers, [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF] we propose algorithms to let one party verifiably sample from the Laplace distribution and from an arbitrary distribution, [START_REF] Bayatbabolghani | Secure fingerprint alignment and matching protocols[END_REF] we propose algorithms to draw from the Gaussian or Laplace distribution a random number represented as a shared secret.

The remainder of this paper is structured as follows:

After reviewing some common notations and concepts in Section 2, we formalize our problem statement in Section 3. Next, in Section 4 we discuss related work and in Section 5 we provide a high-level overview of our method. After that, in Section 6 we review the Cordic algorithm and adapt it for zero-knowledge proofs. In Sections 7 and 8 we apply these techniques for sampling from the Laplace and Gaussian distributions. To show how our methods work in practice, in Section 9 we provide an experimental comparison of the several possible strategies to sample from the Gaussian distribution. In Section 10 we discuss the application of our techniques to the problem of differentially private machine learning. Finally, in Section 11 we conclude and outline directions of future work.

PRELIMINARIES

We will denote the set of the first 𝑘 positive integers by [𝑘] = {𝑖 ∈ N | 1 ≤ 𝑖 ≤ 𝑘 }. We denote the security parameter by 𝜆. We say that a function is negligible in 𝜆 if, for each positive polynomial 𝑓 , it is smaller than 1 𝑓 (𝜆) for sufficiently big 𝜆. We omit 𝜆 sometimes in negligible functions when it is clear it refers to 𝜆. 𝑎 ← 𝑅 𝑆 means that 𝑎 is sampled uniformly at random from elements of 𝑆. For vectors a = (𝑎 1 , . . . , 𝑎 𝑘 ) and b = (𝑏 1 , . . . , 𝑏 𝑘 ), a + b and a * b are the element wise addition and product. a b is the multi-exponentiation 𝑘 𝑖=1 𝑎 𝑏 𝑖 𝑖 . For a scalar 𝑠, 𝑠 + a = (𝑠, . . . , 𝑠) + a, 𝑠 * a = (𝑠, . . . , 𝑠) * a and a 𝑠 = a (𝑠,...,𝑠) . The function sign(𝑥) is equal to 1 if 𝑥 ≥ 0 and to -1 otherwise.

Setting and Threat Model

We consider a set of 𝑛 parties P = {𝑃 1 , . . . , 𝑃 𝑛 }. We assume parties have access to a public-key infrastructure which they can use to prove their identity when sending messages. Parties communicate through secure channels and have access to a public bulletin board that they can use to post messages. When a party sends a message to the bulletin board, it is forwarded to all other agents as when using a broadcast channel. In addition, all broadcasted messages remain publicly visible in the bulletin board, which allows to have publicly verifiable protocols.

We assume that a subset of parties P 𝑐𝑜𝑟 ⊂ P is corrupted and controlled by an adversary A. A can make corrupted parties to deviate arbitrarily from the protocol and perform coordinated attacks. Our protocols are secure if at least one party is honest. The set P 𝑐𝑜𝑟 of corrupted parties is assumed to be static, meaning that it does not change after the beginning of the execution.

We prove security in the simulation paradigm, using the model of security with identifiable abort [START_REF] Ishai | Secure Multi-Party Computation with Identifiable Abort[END_REF] for the stand-alone setting [START_REF] Goldreich | Foundations of cryptography: volume 2, basic applications[END_REF]. This setting allows to obtain sequentially composable protocols in which parties are able to detect malicious actions and can in such cases abort the protocol. Deterrence measures may be in place to discourage parties from being detected as malicious. In fact, unless parties stop participating our protocols either complete successfully or abort with a proof that a specific party is a cheater, i.e., in case our protocols abort the message trace (which is kept on the bulletin board) allows for proving that a specific party did not follow the protocol. Assuming that adversaries will be deterred if they risk getting caught is a standard assumption that applies in many scenarios [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF].

In parts of our protocols, we make use of specific Zero Knowledge Proofs that are non-interactive versions of compressed Σ-protocols whose security relies on the Random Oracle Model [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF]. We provide a detailed description of our security framework and prove the security of our protocols in Appendix B.

Commitment Schemes

A commitment scheme allows for committing to values while keeping them hidden. We use the vector variant of the Pedersen commitment scheme [START_REF] Pryds | Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[END_REF]. Let G be a cyclic multiplicative group of prime order 𝑝 exponential in 𝜆 in which the Discrete Logarithm Assumption (DLA) holds. The setup of the commitment scheme takes as input a string of length 𝑂 (1 𝜆 ) and outputs a vector g = (𝑔 1 , . . . , 𝑔 𝑘 ) of elements sampled at random from G \ {1}. It is required that no pairwise discrete logarithm on the elements 𝑔 1 , . . . , 𝑔 𝑘 is known, which can be guaranteed without a trusted party as the setup only requires public randomness. A commitment 𝑃 ∈ G of a vector x = (𝑥 1 , . . . , 𝑥 𝑘 ) ∈ Z 𝑘 𝑝 satisfies 𝑃 = g x . We say that x is an opening of 𝑃. The scheme is binding as no computationally bounded adversary can find two openings x and x ′ of 𝑃 such that x ≠ x ′ except with probability negligible in 𝜆. If x = ( x, 𝑟 ), where x is the data and 𝑟 is sampled uniformly at random from Z 𝑝 , 𝑃 is uniformly distributed in G and therefore does not reveal any information about x. This is known as the hiding property. In our protocols, one coordinate of g is always reserved for randomness. The scheme is also homomorphic as, given commitments 𝑃 and 𝑄 of x and y respectively, 𝑃𝑄 is a commitment of x + y.

Arithmetic Circuits

An arithmetic circuit (or just circuit) 𝐶 : Z 𝑘 𝑝 → Z 𝑠 𝑝 is a function that only contains additions and multiplications modulo 𝑝. In the following sections we will define circuits using the notation

𝐶 (𝑎; 𝑖 1 , . . . , 𝑖 𝑘 )        𝑜 1 . . . 𝑜 𝑠       
, where (𝑖 1 , . . . , 𝑖 𝑘 ) is the input, (𝑜 1 , . . . , 𝑜 𝑠 ) is the output, and 𝑎 are constants that may change the circuit structure, for example, in the case we are defining a family of similar circuits.

Compressed Σ-Protocols

We will prove statements about private committed values using Zero Knowledge Proofs [START_REF] Goldwasser | The Knowledge Complexity of Interactive Proof Systems[END_REF]. In such proofs, for a NP relation R, a prover P interacts with a verifier V to prove, for a public statement 𝑎, the knowledge of a private witness 𝑤 such that (𝑎; 𝑤) ∈ R. At the end of the interaction, V either accepts or rejects the proof. ZKPs are (1) complete, as V always accepts a proof of an honest P, (2) sound, as a proof of a dishonest P is rejected except with negligible probability and (3) zero knowledge, as no information other than (𝑎; 𝑤) ∈ R is revealed by the protocol. The ZKPs that we use are also called zero knowledge arguments, as they are sound if P is computationally bounded. Additionally, they rely on the DLA.

The ZKPs we use are called compressed Σ-protocols [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF]. Particularly, we use Protocol Π 𝑐𝑠 of [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF], that proves the nullity of the output of arithmetic circuits in Z 𝑝 applied to private inputs. Let G, Z 𝑝 , and g be as defined for commitments, then for any circuit 𝐶 : Z 𝑘 𝑝 → Z 𝑠 𝑝 , by applying Π 𝑐𝑠 to 𝐶 we obtain a complete, sound and zero knowledge proof for the relation

{(𝑃 ∈ G; x ∈ Z 𝑘 𝑝 ) : 𝑃 is a commitment of x ∧ 𝐶 (x) = 0)}.
While Π 𝑐𝑠 is an interactive protocol between P and V, it can be turned into a non-interactive proof using the Strong Fiat-Shamir heuristic [START_REF] Bernhard | How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios[END_REF]. By this transformation, ZKPs can be generated offline by P and later be verified by any party.

Let 𝑚 be the number of multiplication gates of 𝐶, then the proof generated by the execution of Π 𝑐𝑠 has a size of 2⌈log(𝑘 +2𝑚 +4)⌉ -1 elements of G and 6 elements of Z 𝑝 . To generate such proof, the dominant computations are modular exponentiations in G (GEX). P performs 5𝑘 + 8𝑚 + 2⌈log 2 (𝑘 + 2𝑚 + 4)⌉ + 6 GEX, and the verification cost is of 𝑘

+ 2𝑚 + 2⌈log 2 (𝑘 + 2𝑚 + 4)⌉ -1 GEX.
We provide a detailed explanation of compressed Σ-protocols, their cost and some optimizations in Appendix A.

Secret Sharing

Consider again 𝑛 parties {𝑃 𝑖 } 𝑛 𝑖=1 . For a positive prime 𝑝, group Z 𝑝 , and a number 𝑎 ∈ Z 𝑝 , one can generate an additive secret share for 𝑎 by drawing a random vector (𝑎 1 , . . . , 𝑎 𝑛 ) ∈ Z 𝑛 𝑝 subject to the constraint that 𝑛 𝑖=1 𝑎 𝑖 = 𝑎 mod 𝑝. We then denote this sharing of 𝑎 as ⟦𝑎⟧ = (𝑎 1 . . . 𝑎 𝑛 ). The process of computing and revealing 𝑎 from the sharing ⟦𝑎⟧ is called opening the sharing ⟦𝑎⟧. If every party 𝑃 𝑖 only receives 𝑎 𝑖 (for 𝑖 ∈ [𝑛]), then if not all parties collude each party can only see at most 𝑛 -1 uniformly randomly distributed numbers, and hence has no information about the value of 𝑎.

If for one or more values a sharing is available, it is possible to perform various operations on them without revealing any new information, see [START_REF] Damgard | Practical Covertly Secure MPC for Dishonest Majority -Or: Breaking the SPDZ Limits[END_REF] for an overview. If ⟦𝑎⟧ = (𝑎 1 . . . 𝑎 𝑛 ) is a sharing of 𝑎 and ⟦𝑏⟧ is a sharing of 𝑏, then ⟦𝑎 + 𝑏⟧ = (𝑎 1 + 𝑏 1 . . . 𝑎 𝑛 + 𝑏 𝑛 ) is a sharing of 𝑎 + 𝑏. Given a sharing ⟦𝑎⟧ of 𝑎 and a public constant 𝑐, then ⟦𝑐𝑎⟧ = (𝑐𝑎 1 . . . 𝑐𝑎 𝑛 ) is a sharing of 𝑐𝑎. For multiplying two sharings, one can use pre-computed triples of sharings (⟦𝑥⟧, ⟦𝑦⟧, ⟦𝑧⟧) with 𝑥 and 𝑦 random and 𝑥𝑦 = 𝑧. Given such triple, and two sharings ⟦𝑎⟧ and ⟦𝑏⟧ which one wants to multiply, one can compute ⟦𝑑⟧ = ⟦𝑎⟧ -⟦𝑥⟧ and ⟦𝑒⟧ = ⟦𝑏⟧ -⟦𝑦⟧ and open both ⟦𝑑⟧ and ⟦𝑒⟧. Then, a sharing of 𝑐 = 𝑎𝑏 is obtained by ⟦𝑐⟧ = ⟦𝑧⟧ + 𝑑⟦𝑦⟧ + 𝑒⟦𝑥⟧ + 𝑑𝑒. Several approaches have been proposed to generate such triples of sharings (⟦𝑎⟧, ⟦𝑏⟧, ⟦𝑐⟧) efficiently, typically involving a somewhat homomorphic encryption (SHE) scheme with distributed decryption, where the parties can generate random sharings ⟦𝑎⟧ and ⟦𝑏⟧ uniformly at random, encrypt them, multiply them and decrypt the product in a distributed way to obtain ⟦𝑐⟧ [START_REF] Damgard | Practical Covertly Secure MPC for Dishonest Majority -Or: Breaking the SPDZ Limits[END_REF].

We'll adopt a number of ideas from [START_REF] Damgard | Unconditionally secure constant rounds multi-party computation for equality, comparison, bits and exponentiation[END_REF]. In particular, we will represent sharings in binary form, denoting by 𝐵𝐼𝑇 𝑆 (𝑥, (𝑥 (𝑖) ) 𝑙-1 𝑖=0 ) the relation ⟦𝑥⟧ = 𝑙-1 𝑖=0 ⟦𝑥 (𝑖) ⟧2 𝑖 with 𝑥 (𝑖) ∈ {0, 1}. The protocol Bit-add((⟦𝑥 (𝑖) ⟧) 𝑙-1 𝑖=0 ; (⟦𝑦 (𝑖) ⟧) 𝑙-1 𝑖=0 ) returns (⟦𝑧 (𝑖) ⟧) 𝑙-1 𝑖=0 such that there holds 𝑧 = 𝑥 +𝑦 for 𝐵𝐼𝑇 𝑆 (𝑥, (⟦𝑥 (𝑖) ⟧) 𝑙-1 𝑖=0 ), 𝐵𝐼𝑇 𝑆 (𝑦, (⟦𝑦 (𝑖) ⟧) 𝑙-1 𝑖=0 ) and 𝐵𝐼𝑇 𝑆 (𝑧, (⟦𝑧 (𝑖) ⟧) 𝑙-1 𝑖=0 ). To implement it, let 𝑐 (-1) = 0. For 𝑖 = 0 . . . 𝑙 -1:

⟦𝑧 (𝑖) ⟧ = Bit-xor(⟦𝑥 (𝑖) ⟧, Bit-xor(⟦𝑦 (𝑖) ⟧, ⟦𝑐 (𝑖-1) ⟧))
where Bit-xor(𝑎, 𝑏) = (𝑎 -𝑏) 2 ; and ⟦𝑐 (𝑖) ⟧ = ⟦𝑥 (𝑖) ⟧⟦𝑦 (𝑖) ⟧ + ⟦𝑐 (𝑖-1) ⟧((1 -⟦𝑥 (𝑖) ⟧)⟦𝑦 (𝑖) ⟧ + ⟦𝑥 (𝑖) ⟧(1 -⟦𝑦 (𝑖) ⟧)). After this loop, return (⟦𝑧 (𝑖) ⟧) 𝑙 𝑖=1 .

Random Numbers

PROBLEM STATEMENT

We call 𝜋 a sampling protocol over a domain X if 𝜋 is a randomized multi-party protocol which outputs sequences of elements of X.

We consider sampling protocols which take only one input per party at the beginning of the protocol. In particular, let P = {𝑃 𝑖 } 𝑛 𝑖=1 be the set of 𝑛 parties which participate to a sampling protocol 𝜋, and let 𝑠 𝑖 be the input (also called seed) of party 𝑃 𝑖 (for 𝑖 ∈ [𝑛]). We denote the output of 𝜋 by 𝜋 (s) where s = (𝑠 𝑖 ) 𝑛 𝑖=1 is the vector of seeds. We assume that there is some increasing polynomial 𝑝 : N → N such that if s ∈ {0, 1} 𝑘×𝑛 then 𝜋 (s) ∈ X 𝑝 (𝑘) . Let s -𝑖 = (𝑠 1 , . . . , 𝑠 𝑖-1 , 𝑠 𝑖+1 , . . . , 𝑠 |𝑠 | ) denote the vector s without the 𝑖-th component.

Definition 1 (Correct Sampling). For a multi-party protocol 𝜋, we say a party is honest if it follows the steps of protocol 𝜋 correctly and does not collude with other parties. We say that a sampling protocol 𝜋 correctly samples from a probability distribution D if there is a function 𝜇 with 𝜇 (𝑘) negligible in 𝑘 such that for every run of 𝜋 by parties P = {𝑃 𝑖 } 𝑛 𝑖=1 among which there is at least one 𝑖 ∈ [𝑛] such that party 𝑃 𝑖 is honest, for every s -𝑖 ∈ {0, 1} 𝑘×(𝑛-1) , for any probabilistic polynomial time algorithm 𝐴 : {0, 1} 𝑘 (𝑛-1) ×X 𝑝 (𝑘) → {0, 1}, there holds that either 𝜋 finishes correctly and

|𝑃 𝑠 𝑖 ← 𝑅 {0,1} 𝑘 (𝐴(s -𝑖 , 𝜋 (s)) = 1) -𝑃 𝑡 ← 𝑅 {0,1} 𝑘 (𝑛-1) ,𝑥← 𝑅 D 𝑝 (𝑘 ) (𝐴(𝑡, 𝑥) = 1)| ≤ 𝜇 (𝑘),
or 𝜋 aborts and detects a party that attempted to cheat, where D 𝑝 (𝑘) draws vectors from X 𝑝 (𝑘) whose components are independently distributed according to D.

In other words, if there is at least one honest party, then 𝜋 acts as a (generalized) PRG even if all parties except that honest party would disclose their seeds. As a result, as soon as a single party is honest it can trust that any output of 𝜋 used by any party is pseudorandom and no party could predict it in advance. We denote the fact that 𝑥 is correctly drawn from D by 𝑥 ← * 𝑅 D. We say a protocol 𝜋 verifiably samples from D if 𝜋 correctly samples from D and after every execution of 𝜋 the value of 𝑥 is uniquely defined given the union of the information obtained by all parties and the information published by 𝜋 is sufficient to convince any party that 𝑥 has been correctly drawn. We denote the fact that 𝑥 is verifiably drawn from D by 𝑥 ← 𝑉 𝑅 D. In this paper, we will often informally consider both discrete and continuous probability distributions, and 𝑃 D then either represents a probability mass or probability density according to the context. As computers work with finite precision, we will eventually discretize up to some parameter-defined precision. While in the end all distributions will be discrete, we will use the continuous representations whenever this simplifies the explanation.

In the sequel, unless made explicit otherwise, we'll assume there are 𝑛 parties among whom at least one is honest, and that D is a publicly agreed probability distribution. Also, to simplify the explanation we will often describe protocols generating just one random number, the extension to streams of random numbers is then straightforward.

We can distinguish several types of verifiable sampling protocols, depending on how they output the sampled number 𝑥. For a verifiable sampling protocol 𝜋, we say it is a In this paper, we study the problem of finding efficient verifiable sampling protocols of each of the three above types given the probability distribution D. This problem is reasonably straightforward if D is the uniform distribution over the integers in the interval [0, 𝐿) for some 𝐿 > 0: Protocol 1 (Public uniform sampling). For each 𝑖 ∈ [𝑛] let party 𝑃 𝑖 generate its own random number 𝑟 𝑖 uniformly distributed over [0, 𝐿) from its own secret seed 𝑠 𝑖 and publish a commitment 𝐶 𝑖 to it. Then, all parties open their commitment, i.e., they publish 𝑟 𝑖 and the randomness associated to the commitment to prove that 𝐶 𝑖 was a commitment to 𝑟 𝑖 . Finally, all parties compute publicly 𝑛 𝑖=1 𝑟 𝑖 mod 𝐿.

It is easy to see Protocol 1 draws 𝑟 verifiably: if at least one party 𝑃 𝑖 is honest, it has generated a uniformly distributed number 𝑟 𝑖 and 𝑟 is also uniformly distributed because non-honest parties 𝑃 𝑗 cannot change their 𝑟 𝑗 as a function of other parties because they start with a commitment on their 𝑟 𝑗 . Note that Protocol 1 is a generalization for multiple parties of [START_REF] Blum | Coin flipping by telephone a protocol for solving impossible problems[END_REF]. We present the protocol in more detail and prove its security in Appendix B.3. Protocol 2 (Private uniform sampling). One can sample a vector of 𝑘 numbers private to 𝑃 1 as follows: 𝑃 1 draws uniformly at random a vector a = (𝑎 1 , . . . , 𝑎 𝑘 ) ∈ [0, 𝐿) 𝑘 and publishes a vector commitment 𝐶 to it. Then, all parties generate jointly a public random number 𝑟 ∈ [0, 𝐿) with Protocol 1. 𝑃 1 expands 𝑟 to random numbers (𝑟 1 , . . . , 𝑟 𝑘 ) ∈ [0, 𝐿) 𝑘 using a PRG. Finally, for 𝑖 ∈ [𝑘], 𝑃 1 computes 𝑢 𝑖 = 𝑎 𝑖 +𝑟 𝑖 mod 𝐿 and performs a zero knowledge proof of the modular sum for each 𝑢 𝑖 . (𝑢 1 , . . . , 𝑢 𝑘 ) is a vector of private uniform random numbers.

Again, it is easy to see that (𝑢 1 , . . . , 𝑢 𝑘 ) is drawn verifiably. This protocol has many aspects in common with the Augmented Coin-Tossing protocol defined in [START_REF] Goldreich | Foundations of cryptography: volume 2, basic applications[END_REF]Section 7.4.3.5]. We provide a proof of the security of Protocol 2 in Appendix B.4. Protocol 3 (Hidden uniform sampling). For each 𝑖 ∈ [𝑛] let party 𝑃 𝑖 generate its own random number 𝑟 𝑖 uniformly distributed over [0, 𝐿) and publish a commitment 𝐶 𝑖 to it. Then, they consider (𝑟 1 , . . . , 𝑟 𝑛 ) as a secret share of the random number 𝑟 = 𝑛 𝑖=1 𝑟 𝑖 mod 𝐿. After running Protocol 3, if there is a honest party, 𝑟 is fixed and follows the right probability distribution, and as not all parties collude no party knows more about 𝑟 than that it follows the uniform distribution over [0, 𝐿).

The problem of finding efficient verifiable sampling protocols becomes more challenging when D is not the uniform distribution, but a more general distribution such as a normal distribution or a Laplace distribution. Even for single party computation there sometimes exist multiple approaches with varying cost and precision.

RELATED WORK

Below we describe lines of work that are related to ours.

Multiparty Computation between unreliable participants. The seminal work of [START_REF] Blum | Coin flipping by telephone a protocol for solving impossible problems[END_REF] proposed the first protocol to sample a public random bit (i.e. tossing a coin) between two parties that do not trust each other. Subsequent works such as [START_REF] Broder | Flipping Coins In Many Pockets (Byzantine Agreement On Uniformly Random Values)[END_REF] proposed protocols to perform coin tossing between an arbitrary number of parties.

The work of [START_REF] Cleve | Limits on the Security of Coin Flips When Half the Processors Are Faulty[END_REF] proved that in the malicious model without aborts it is impossible that a multiparty protocol is guaranteed to finish correctly and perform an unbiased coin toss if the number of malicious users is half or more of the total of participants. For such cases, there is no other possibility than providing weaker security guarantees. In the framework of malicious security with abort [START_REF] Goldreich | Foundations of cryptography: volume 2, basic applications[END_REF], protocols either end correctly or are aborted by malicious parties. This could lead to bias in the computations if a protocol is restarted after an abort and the adversary speculatively chooses when allow the protocol to finish correctly. To prevent this, a possible solution is to identify and punish malicious parties that cause aborts. The work of [START_REF] Aumann | Security against covert adversaries: Efficient protocols for realistic adversaries[END_REF] proposes covert security, where cheating adversaries can get caught with certain probability. This is weaker than malicious security with abort, but allows cheaters to be detected. A stronger notion is malicious security with identifiable abort [START_REF] Ishai | Secure Multi-Party Computation with Identifiable Abort[END_REF], where a party that cheats causes the protocol to abort with overwhelming probability and, in addition, the cheater is identified. Our work fits in that framework.

If deterrence measures are strong enough, this could be sufficient to discourage malicious behavior. Otherwise, if corrupted peers are willing to sacrifice themselves at any cost, other measures can be taken to attenuate the bias as much as possible [START_REF] Beimel | Protocols for Multiparty Coin Toss with Dishonest Majority[END_REF][START_REF] Moran | An Optimally Fair Coin Toss[END_REF].

The work [START_REF] Goldreich | How to Play ANY Mental Game[END_REF] proposes a method to securely perform a wide family of randomized computations (related to interactive games) over private data and private random numbers, using zero knowledge proofs to verify correctness. They prove that this is secure in the ideal paradigm without abort if the majority of parties is honest.

Sampling from Gaussians and other popular non-uniform distributions. Distributions such as the Gaussian distribution, the Laplace distribution, the Poisson distribution or the exponential distribution are important in the field of statistics. Algorithms to securely draw from such distributions have applications in federated machine learning. Several contributions concern the problem of verifiable noise for differential privacy [START_REF] Kato | Preventing Manipulation Attack in Local Differential Privacy Using Verifiable Randomization Mechanism[END_REF][START_REF] Tsaloli | Differential Privacy meets Verifiable Computation: Achieving Strong Privacy and Integrity Guarantees[END_REF] and hence can benefit from secure drawing.

Even in the semi-honest model where parties follow the specified protocol, drawing hidden random numbers is sometimes non-trivial. For example, in [START_REF] Choi | Differentially-Private Multi-Party Sketching for Large-Scale Statistics[END_REF] one needs to make a sum of statistics and a Laplacian-distributed noise term, hence the authors propose a protocol where parties generate random numbers summing to a Laplacian distributed value which can then be included in a secure aggregation without being revealed.

In [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], protocols are proposed to generate secret-shared samples for Gaussian, Exponential and Poisson distributions. For the Gaussian distribution, their approach generates samples by averaging uniform seeds, a method which we call the Central Limit Theorem (CLT) approach. We compare the CLT approach with our approaches in Section 9. Even if more than a decade has passed since [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], recent contributions still resort to these techniques to generate Gaussian samples among unreliable participants. For example, recent protocols use the technique of [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF] by adapting it to generate private draws from the Exponential distribution [START_REF] Garrido | Towards Verifiable Differentially-Private Polling[END_REF] and to sample hidden draws from the Binomial distribution [START_REF] Biswas | Verifiable Differential Privacy For When The Curious Become Dishonest[END_REF]. The work of [START_REF] Mazloom | Secure Computation with Differentially Private Access Patterns[END_REF] proposes techniques to securely sample from the geometrical and Gaussian distributions, both building on [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], and studies them in the light of differentially private memory access patterns. In addition, [START_REF] Mazloom | Secure Computation with Differentially Private Access Patterns[END_REF] defines an extension of the malicious security model which includes information leakage, as measured in differential privacy, and proves the security of their protocols within this model.

In our work, we propose new techniques for privately drawing from the Gaussian distribution and show that all our techniques for all but the lowest precision requirements outperform the technique of [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], which is the most efficient method known so far. The same dynamics are at play for exponential, Poisson and Laplace distributions. Compared to the techniques in [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], our methods have a better complexity as a function of the precision parameter. We extend our methodology to hidden draws of Gaussian, Laplacian and Arbitrary distributions. Achieving sufficient precision when sampling is important for both the statistical quality and the security of the algorithms [START_REF] Mironov | On Significance of the Least Significant Bits for Differential Privacy[END_REF].

Implementation of math functions using cryptographic primitives.

Using secret sharing techniques, there is a large body of work on how to compute math functions such as square roots, logarithms and trigonometric [START_REF] Aly | Benchmarking Privacy Preserving Scientific Operations[END_REF][START_REF] Bayatbabolghani | Secure fingerprint alignment and matching protocols[END_REF][START_REF] Dimitrov | Alternative Implementations of Secure Real Numbers[END_REF][START_REF] Gupta | LLAMA: A Low Latency Math Library for Secure Inference[END_REF][START_REF] Gupta | LLAMA: A Low Latency Math Library for Secure Inference[END_REF][START_REF] Liedel | Secure Distributed Computation of the Square Root and Applications[END_REF]. However they usually rely on splines or other approximation techniques that approximate functions by splitting the domain and using low-degree polynomials for each part. Alternatively, they rely on rational approximations. Piecewise approximations require the use of conditionals which are expensive when computing with secret shares, and rational approximations only allow for a fixed precision. Our work uses iterative approximations which allow to customize the precision of the approximation and are easy to compute given that we avoid the use of comparison gates in our circuits. Furthermore, for the Gaussian distribution, piecewise approximations require an external method to sample from the tails of the distribution. We also show protocols for private sampling from Gaussian and Laplace distributions where we avoid the high cost of secret shared computation by letting one party perform the calculation and then prove correct behavior using compressed Σ-protocols.

Zero Knowledge Proofs for such functions, as we apply in our work, is a less explored technique. [START_REF] Zhao | VeriML: Enabling Integrity Assurances and Fair Payments for Machine Learning as a Service[END_REF] proposes techniques to prove a limited set of relations involving common activation functions in machine learning.

METHOD

We start with discussing two generic approaches: a strategy based on the inverse cumulative probability distribution and a strategy based on table lookup.

Inverse Cumulative Probability Distribution

Assume D is a probability distribution on X ⊆ R. The cumulative probability distribution is defined as

𝐹 D (𝑥) = ∫ 𝑡 ≤𝑥 𝑃 D (𝑡) d𝑡
To the extent D is discrete, we can see 𝑃 D as a sum of scaled Dirac delta functions over which integration is possible and results in a sum. Then, the inverse 𝐹 -1 D is a function on the interval (0, 1). An approach to sampling from arbitrary distributions D on domains X ⊆ R, known as the inversion method, consists of sampling uniformly from the (0, 1) interval and applying the inverse of the cumulative distribution function 𝐹 -1 D . Indeed, if 𝑡 ← 𝑅 (0, 1), then

𝑃 (𝐹 -1 D (𝑡) = 𝑥) = 𝑃 D (𝑥).
Public Sampling from an Arbitrary Distribution. This approach can easily be applied to draw random numbers publicly: Protocol 4 (Public draw from arbitrary distribution). Run protocol 1 to generate a public uniformly distributed random number 𝑟 ′ , and then publicly compute 𝑟 = 𝐹 -1 D (𝑟 ′ ).

Using the inversion method for private or hidden draws is more involved since one needs a multi-party algorithm to compute 𝐹 -1 D or a ZKP algorithm to prove to other parties that 𝐹 -1 D was applied correctly. In many practical cases, 𝐹 -1 D does not have a simple closed form. This especially holds for the Gaussian distribution which we will discuss in more detail in Section 8.

We can extend this method to multi-variate distributions. For example, consider a distribution D over R 2 . To sample a pair (𝑥, 𝑦) according to D, we first define 𝑃 𝑥 (𝑥) = ∫ 𝑃 D (𝑥, 𝑦) d𝑦, apply the inversion method to draw a random number 𝑥 according to 𝑃 𝑥 , and then define 𝑃 𝑦 |𝑥 (𝑦) = 𝑃 D (𝑦|𝑥) = 𝑃 D (𝑥, 𝑦)/𝑃 𝑥 (𝑥) and apply again the inversion method to draw a random 𝑦.

Table Lookup

As pointed out above, practical inverse cumulative probability functions are often expensive to compute, especially in a secure multiparty setting. In such scenarios approaches such as the ones discussed in Sections 5.1 and 8 incur a high cost for each drawn random number. In this section we consider an approach based on table lookup. While the involved techniques are well-known, this approach is interesting as a baseline, especially as it has a number of properties which are different from the other methods considered in this paper. In particular, the method studied here has a high pre-processing cost but then allows for drawing random numbers at a low constant cost per drawn random number.

Protocol 5 (Table-lookup private sampling).

• Preprocessing. Let 𝑀 ∈ N. The parties publicly pre-compute

the pairs 𝑖, 𝐹 -1 D 2𝑖-1 2𝑀
for all 𝑖 ∈ [𝑀] and store them into a database DB.

• Sampling. Party 𝑃 1 privately draws using Protocol 2 a random number

𝑟 ′ distributed uniformly in [𝑀]. Then, 𝑃 1 sets 𝑟 = 𝐹 -1 D 2𝑟 ′ -1
2𝑀 , publishes commitments to 𝑟 ′ and 𝑟 , and publishes a ZKP that (𝑟 ′ , 𝑟 ) ∈ DB.

In Protocol 5 a zero knowledge set membership proof is needed. There is a large body of work on this topic since in [START_REF] Camenisch | Efficient Protocols for Set Membership and Range Proofs[END_REF] the first method was shown that has a large preprocessing cost (linear in 𝑀) but only a unit communication cost for proving membership. Several improvements have been proposed which vary in their assumptions and efficiency, [START_REF] Benarroch | Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular[END_REF] discusses some lines of recent work.

Only already storing the database DB may take a prohibitive amount of space if a high precision is needed, as 𝑀 is exponential in the number of desired correct digits. As a result, this technique can only be used when the needed precision is not too high. If it is feasible, it is expensive for drawing only a few random numbers but it can become more efficient than other methods if a huge number of random numbers need to be drawn, as asymptotically the cost per sample will dominate.

Laplace Distribution

The Laplace distribution, denoted 𝐿𝑎𝑝 (𝑏) is defined by

𝑃 𝐿𝑎𝑝 (𝑏) (𝑥) = exp(-|𝑥 |/𝑏)/2𝑏.

The cumulative distribution is

𝐹 𝐿𝑎𝑝 (𝑥) = 1/2 + sign(𝑥)/2 -sign(𝑥) exp(-|𝑥 |/2).
To sample a number 𝑟 from 𝐿𝑎𝑝 (𝑏) it is convenient to separately draw the sign 𝑠 and absolute value 𝑎 of 𝑟 . Then,

𝑃 (𝑠 = -1) = 𝑃 (𝑠 = 1) = 1/2 and 𝑃 (𝑎) = 1 𝑏 exp -𝑎 𝑏 and 𝑃 (𝑎 ≤ 𝑡) = 1 -exp -𝑡 𝑏 .
In Section 7 we will describe protocols for both private and hidden Laplace-distributed draws.

Gaussian Distribution

The Gaussian distribution, denoted by N (𝜇, 𝜎 2 ), is defined by

𝑃 N (𝜇,𝜎 2 ) (𝑥) = exp(-(𝑥 -𝜇) 2 /2𝜎 2 )/ √ 2𝜋𝜎.
We will sometimes use the shorthand

𝑃 N = 𝑃 N (0,1) . The cumulative distribution is 𝐹 N (𝑥) = (1 + erf(𝑥/ √ 2))/2 (1)
where erf is the error function. There is no closed form for 𝑃 N , 𝐹 N nor its inverse. In the single party setting multiple strategies have been investigated to sample from this important distribution:

• the Central Limit Theorem (CLT) approach, which consists of sampling repeatedly from a uniform distribution and computing the average, which is simple but requires 𝑂 (1/Δ 2 ) time for a root mean squared error Δ, • the Box-Müller method [START_REF] Box | A Note on the Generation of Random Normal Deviates[END_REF], that can obtain two Gaussian numbers from two uniform samples by the application of a closed form formula, but involves the computation of a square root, trigonometric functions and a logarithm, • rejection sampling methods, such as the polar version of Box-Müller [START_REF] Knop | Remark on algorithm 334 [G5]: normal random deviates[END_REF] or the Ziggurat Method [START_REF] Marsaglia | The ziggurat method for generating random variables[END_REF] are efficient and highly accurate. While the former avoids the computation of trigonometric functions and leads to an efficient verifiable implementation, the latter uses several conditional branches which are expensive to prove in zero knowledge and requires an external method for sampling in the tails of the distribution, • the inversion method for Gaussians that involves the approximation of the inverse error function erf -1 , which can be done with rational functions or Taylor polynomials, and • the recursive method of Wallace [START_REF] Wallace | Fast pseudorandom generators for normal and exponential variates[END_REF], which is very popular for its efficiency, but requires as input a vector of already generated Gaussian samples to generate an output vector of the same size; furthermore, samples from input and output vectors are correlated, which deteriorates the statistical quality.

Before studying some of these in the multi-party setting, we will first provide Σ-protocols of relations involving approximations of certain elementary functions.

PROOFS OF ELEMENTARY FUNCTIONS

In this section, we construct zero knowledge proofs of statements that involve the approximation of elementary functions, i.e. sine, cosine, natural logarithm and square root. These functions can be numerically approximated using basic operations such as addition and multiplication. While classic cryptographic tools are used to prove statements over integers, we operate with real numbers which we approximate with fixed precision. Therefore, we use representations of integer multiples of 2 -𝜓 by multiplying our values with 2 𝜓 and rounding them deterministically to obtain elements of Z 𝑝 . Negative numbers are represented in the upper half of Z 𝑝 . For example, the number 𝑎 < 0 is represented with 𝑝 + 2 𝜓 𝑎. The set of representable numbers is denoted by

Q ⟨𝑝,𝜓 ⟩ = {𝑣 ∈ Q : 2 𝜓 𝑣 ∈ Z ∧ -𝑝/2 ≤ 2 𝜓 𝑣 < 𝑝/2}
which is closed under addition and multiplication modulo 𝑝 (rounded up to 2 -𝜓 ). The encoding of 𝑣 ∈ Q ⟨𝑝,𝜓 ⟩ is denoted by ⟨𝑣⟩ = 2 𝜓 𝑣 mod 𝑝.

We show circuits such that the nullity of their output is equivalent to the statements we want to prove. We will first construct circuits to describe low level statements and then use these as building blocks for higher level statements. In the end, we apply compressed Σ-protocols (see Section 2.4) to produce zero knowledge proofs of these circuits. For parameters (𝑎; 𝑏) of all circuits defined below, 𝑎 always contains public constants and 𝑏 private values.

We present in Section 6.1 circuits for proving various types of simple statements. In Section 6.2, we introduce Cordic, the core approximation algorithm. We implement circuits to prove its correct execution in Section 6.3, and details on how to expand its domain of application, particularly for our sampling techniques, in Section 6.4.

Building Blocks

We introduce below proofs of basic statements that we will use to prove approximations, including the handling of some statements of numbers in Q ⟨𝑝,𝜓 ⟩ . Note that additions, multiplication by an integer and range proofs port directly to Z 𝑝 by our encoding ⟨•⟩. In Appendix A.5, we show that to prove that an integer 𝑥 ∈ Z 𝑝 belongs to [0, 2 𝑘 ) we can use the circuit

𝐶 𝑅𝑎 (𝑘; 𝑥, x) x * (1 -x) 𝑥 -𝑘 𝑖=1 𝑥 𝑖 2 𝑖-1
where x = (𝑥 1 , . . . , 𝑥 𝑘 ) is the bit map of 𝑥. Here, x * (1x) is a vector with at position 𝑖 the value

𝑥 𝑖 (1-𝑥 𝑖 ), which is 0 if 𝑥 𝑖 ∈ {0, 1}.
The second expression evaluates to 0 if x is indeed the correct bit map of 𝑥. Hence, the nullity of the circuit, i.e., its righthandside evaluating to the zero vector, proves 𝑥 ∈ [0, 2 𝑘 ).

Generalized range proof. 𝐶 𝑅𝑎 can be used twice to prove membership in any range [𝑎, 𝑏] ⊂ Z 𝑝 . To prove 𝑥 ∈ [𝑎, 𝑏] we use the circuit

𝐶 𝐺𝑅𝑎 (𝑎, 𝑏; 𝑥, s 1 , s 2 ) 𝐶 𝑅𝑎 (⌊log(𝑏 -𝑎)⌋ + 1; 𝑥 -𝑎, s 1 ) 𝐶 𝑅𝑎 (⌊log(𝑏 -𝑎)⌋ + 1; 𝑏 -𝑥 + 𝑎, s 2 )
where s 1 , s 2 ∈ {0, 1} ⌊log(𝑏-𝑎) ⌋+1 the auxiliary bit vectors required for 𝐶 𝑅𝑎 .

(Right) Bit-shift. For 𝑎 ∈ Q ⟨𝑝,𝜓 ⟩ and an integer 𝑘 > 0, a bit shift 𝑎 >> 𝑘 is equal to the biggest value in Q ⟨𝑝,𝜓 ⟩ smaller than 𝑎/2 𝑘 . We have that 𝑏 = 𝑎 >> 𝑘 if ⟨𝑎⟩ -2 𝑘 ⟨𝑏⟩ ∈ [0, 2 𝑘 ). For the vector s of the bit decomposition of ⟨𝑎⟩ -2 𝑘 ⟨𝑏⟩, the circuit is

𝐶 >> (𝑘; ⟨𝑎⟩, ⟨𝑏⟩, s) 𝐶 𝑅𝑎 (𝑘; ⟨𝑎⟩ -2 𝑘 ⟨𝑏⟩, s).
Note that in the definition of 𝐶 >> , as in all subsequent circuits, the evaluation of inputs to sub-circuits such as 𝐶 𝑅𝑎 are computations performed within the circuit.

Approximate product. For private 𝑎, 𝑏, 𝑐 ∈ Q ⟨𝑝,𝜓 ⟩ , it can be proven that 𝑐 is the rounding of 𝑎𝑏, that is by proving that ⟨𝑐⟩ -⟨𝑎⟩⟨𝑏⟩ + ⟨1/2⟩ ∈ [0, 2 𝜓 ). For s ∈ {0, 1} 𝜓 the bitmap of ⟨𝑐⟩ -⟨𝑎⟩⟨𝑏⟩ + ⟨1/2⟩ our circuit is 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝑎⟩, ⟨𝑏⟩, ⟨𝑐⟩, s) 𝐶 𝑅𝑎 (𝜓 ; ⟨𝑐⟩ -⟨𝑎⟩⟨𝑏⟩ + ⟨1/2⟩, s).

Approximate division. For private 𝑎, 𝑏, 𝑐 ∈ Q ⟨𝑝,𝜓 ⟩ , we prove that 𝑐 is approximately 𝑎/𝑏 with error 2 -𝜓 . We also require that 𝑏 ∈ [𝐴, 𝐵] for public 𝐴, 𝐵 ∈ Q ⟨𝑝,𝜓 ⟩ . We prove that ⟨𝑏⟩⟨𝑐⟩ -2 𝜓 ⟨𝑎⟩ + ⟨𝑏⟩ ∈ [0, 2⟨𝑏⟩). Our range proofs require that the bounds are public, so we prove that ⟨𝑏⟩⟨𝑐⟩ -

2 𝜓 ⟨𝑎⟩ + ⟨𝑏⟩ ∈ [0, 2 𝑠 𝑏 +1 ) and 2 𝜓 ⟨𝑎⟩ -⟨𝑏⟩⟨𝑐⟩ ∈ [0, 2 𝑠 𝑏 +1 ) where 𝑠 𝑏 = ⌊log 2 (⟨𝐵⟩ -⟨𝐴⟩)⌋ + 1. For s 1 , s 2 ∈ Z 𝑠 𝑏 +1 𝑝 auxiliary bit vectors, the circuit is 𝐶 𝐷𝑖𝑣 (𝜓, 𝑠 𝑏 ; ⟨𝑎⟩, ⟨𝑏⟩, ⟨𝑐⟩, s 1 , s 2 ) 𝐶 𝑅𝑎 (𝑠 𝑏 ; ⟨𝑏⟩⟨𝑐⟩ -2 𝜓 ⟨𝑎⟩ + ⟨𝑏⟩, s 1 ) 𝐶 𝑅𝑎 (𝑠 𝑏 ; 2 𝜓 ⟨𝑎⟩ -⟨𝑏⟩⟨𝑐⟩, s 2 )
.

Exponentiation in Z 𝑝 . Let 𝑦, 𝑥 ∈ Z 𝑝 be private values with 𝑥 ∈ [0, 2 𝑘 ) and 𝐸 ∈ Z 𝑝 a public integer such that 𝐸 𝑥 < 𝑝/2. We prove that 𝑦 = 𝐸 𝑥 . Let x ∈ {0, 1} 𝑘 the vector of bits of 𝑥, we prove that 𝑦 = 𝑘 𝑦=1 𝑦 𝑖 where for 𝑖 ∈ {1, . . . , 𝑘 }, 𝑦 𝑖 is equal to

𝐸 2 𝑖-1 if x 𝑖 = 1, or to 1 if x 𝑖 = 0. The circuit is 𝐶 𝐼 𝐸𝑥 (𝑘, 𝐸; 𝑥, 𝑦, x) 𝐶 𝑅𝑎 (𝑘; 𝑥, x) 𝑦 -𝑘 𝑖=1 1 + x 𝑖 (𝐸 2 𝑖-1 -1)
.

Modular sum. We prove, for private 𝑥, 𝑧 ∈ Z 𝑝 and public 𝑦 ∈ Z 𝑝 such that all belong to [0, 𝑀), that 𝑧 = 𝑥 + 𝑦 mod 𝑀. Let x 1 , x 2 , z 1 and z 2 vectors of intermediate values for 𝐶 𝐺𝑅𝑎 , and let 𝑏 ∈ {0, 1}, our circuit is

𝐶 𝑀𝑜𝑑 (𝑀, 𝑦; 𝑥, 𝑧, x 1 , x 2 , z 1 , z 2 , 𝑏)         𝐶 𝐺𝑅𝑎 (0, 𝑀 -1; 𝑥, x 1 , x 2 ) 𝐶 𝐺𝑅𝑎 (0, 𝑀 -1; 𝑧, z 1 , z 2 ) 𝑏 (1 -𝑏) 𝑧 -(𝑥 + 𝑦 -𝑏𝑀)         .
Ideas for 𝐶 𝐼 𝐸𝑥 and 𝐶 𝑀𝑜𝑑 are taken from pages 112-115 of [START_REF] Camenisch | Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes[END_REF].

Private magnitude shift. Here, we prove that 𝑦 = 𝑥 >> 𝑘 for public 𝐾 and private 𝑘 ≤ 𝐾. Let k, k ′ , k ′′ ∈ {0, 1} 𝐾 and ℎ ∈ Z 𝑝 be intermediate values for range proofs and integer exponentiations and

I >> = (ℎ, k, k ′ , k ′′ ), our circuit is 𝐶 𝑃 >> (𝐾; 𝑥, 𝑘, 𝑦, I >> )       𝐶 𝐼 𝐸𝑥 (𝐾, 2; 𝑘, ℎ, k) 𝐶 𝑅𝑎 (𝐾; 𝑥 -ℎ𝑦, k ′ ) 𝐶 𝑅𝑎 (𝐾; ℎ -𝑥 + ℎ𝑦 -1, k ′′ )       .

Cordic Algorithm

We use the Cordic algorithm [START_REF] Walther | A unified algorithm for elementary functions[END_REF] for approximations, which has long been state of the art for computations of elementary functions from simple operations [START_REF] Muller | Elementary Functions: Algorithms and Implementation[END_REF]. Essentially, it uses the same core iteration algorithm, which only uses additions and bit-shifts, for all elementary function approximations. We will use Cordic parameterized for two settings described below, the first is used for sine and cosine and the second for square root and logarithm. In what follows, we only provide an algorithmic description of the Cordic algorithm as is needed in order to understand our extension to the zero knowledge setting in Section 6.3.

Setting 1 (Sine and Cosine). Let 𝜃 0 = 0. From input values 𝑋 0 , 𝑌 0 , 𝜃 ∈ Q ⟨𝑝,𝜓 ⟩ , the following iterations are performed:

𝑋 𝑖 = 𝑋 𝑖-1 -𝜉 𝑖 (𝑌 𝑖-1 >> 𝑖) 𝑌 𝑖 = 𝑌 𝑖-1 + 𝜉 𝑖 (𝑋 𝑖-1 >> 𝑖) 𝜃 𝑖 = 𝜉 𝑖 tan -1 (1 >> 𝑖) + 𝜃 𝑖-1
where 𝜉 𝑖 ∈ {-1, 1} is equal to sign(𝜃 -𝜃 𝑖-1 ) and tan -1 (1 >> 𝑖) is taken from a precomputed table. Let 𝜈 be the total number of iterations, and let constants 𝐾 1,𝜈 = 𝜈 𝑗=0 1 + (1 >> 2𝑗) and 𝐾 1 = lim 𝜈→∞ 𝐾 1,𝜈 ≈ 1.6. We have that lim

𝜈→∞       𝑋 𝜈 𝑌 𝜈 𝜃 𝜈 -𝜃       = 𝐾 1       𝑋 0 cos 𝜃 -𝑌 0 sin 𝜃 𝑋 0 sin 𝜃 + 𝑌 0 cos 𝜃 0       .
Recall the representation parameter 𝜓 of Q ⟨𝑝,𝜓 ⟩ defined at the beginning of the section. By the convergence rate of Cordic, if 𝜓 ≥ 𝜈 + ⌈log 2 (𝜈)⌉ + 1, with input 𝑋 0 = 1/𝐾 1,𝜈 , 𝑌 0 = 0, and 𝜃 ∈ [-𝜋/2, 𝜋/2], then 𝑋 𝜈 and 𝑌 𝜈 are approximations of sin(𝜃 ) and cos(𝜃 ) respectively with error at most 2 1-𝜈 .

Setting 2 (ln(𝑥) and √ 𝑥). In this setting Cordic only takes two inputs 𝑋 0 , 𝑌 0 ∈ Q ⟨𝑝,𝜓 ⟩ and, with 𝜃 0 = 0, it performs the iterations

𝑋 𝑖 = 𝑋 𝑖-1 + 𝜉 𝑖 (𝑌 𝑖-1 >> 𝐹 𝑖 ) 𝑌 𝑖 = 𝑌 𝑖-1 + 𝜉 𝑖 (𝑋 𝑖-1 >> 𝐹 𝑖 ) 𝜃 𝑖 = 𝜉 𝑖 tanh -1 (1 >> 𝐹 𝑖 ) + 𝜃 𝑖-1
with 𝜉 𝑖 = sign(-𝑌 𝑖-1 ) and shift magnitude 𝐹 𝑖 = 𝑖 + 1 -𝑘 where the small value 𝑘 is equal to the biggest integer such that 3

𝑘+1 + 2𝑘 -1 ≤ 2(𝑖 + 1). Now let 𝐾 2,𝜈 = 𝜈 𝑗=1 1 + (1 >> 2𝐹 𝑗-1 ) and 𝐾 2 = lim 𝜈→∞ 𝐾 2,𝜈 ≈ 0.8. In Setting 2, we have that lim 𝜈→∞       𝑋 𝜈 𝑌 𝜈 𝜃 𝜈       =         𝐾 2 𝑋 2 0 -𝑌 2 0 0 tanh -1 𝑌 0 𝑋 0         .
With 𝜓 as in Setting 1, 𝑥 ∈ [ 1 4 , 1) and fixing 𝑋 0 = 𝑥 + 1, 𝑌 0 = 𝑥 -1 we get by the identity ln(𝑥) = 2 tanh -1 ( 𝑥-1 𝑥+1 ) that 𝜃 𝜈 is an approximation of 1 2 ln(𝑥) with error at most 2 1-𝐹 𝜈 . Similarly, for the same 𝜓 and domain of 𝑥,

√

𝑥 can be obtained by setting

(𝑋 0 , 𝑌 0 ) = 𝑥 + 1 𝐾 2 2,𝑛+1 , 𝑥 -1 𝐾 2 2,𝑛+1
with error at most 2 1-𝐹 𝜈 .

Cordic in Zero Knowledge

We first specify a set of statements that together are equivalent to a correctly performed Cordic computation. Note that the iterations in Settings 1 and 2 are very similar. Except for the correctness of the 𝜉 𝑖 values, they can be described by equations

𝜉 𝑖 = -1 ∨ 𝜉 𝑖 = 1 ∀𝑖 ∈ {1, . . . , 𝜈 }, (2)
𝑌 𝑖 = 𝑌 𝑖-1 + 𝜉 𝑖 (𝑋 𝑖-1 >> 𝐹 𝑖 ) ∀𝑖 ∈ {1, . . . , 𝜈 }, (3)
𝑋 𝑖 = 𝑋 𝑖-1 -𝑚𝜉 𝑖 (𝑌 𝑖-1 >> 𝐹 𝑖 ) ∀𝑖 ∈ {1, . . . , 𝜈 }, (4)
𝜃 𝜈 = 𝜈 𝑖=1 𝜉 𝑖 𝛼 𝑖 , (5)
where the constants in Setting 1 are 𝑚 = 1, 𝐹 𝑖 = 𝑖 and 𝛼 𝑖 = tan -1 (1 >> 𝑖) and in Setting 2, 𝐹 𝑖 is already defined, 𝑚 = -1 and 𝛼 𝑖 = tanh -1 (1 >> 𝐹 𝑖 ). To prove the correct value of the 𝜉 𝑖 's, we avoid wide range checks at each iteration (on 𝜃 -𝜃 𝑖 or 𝑌 𝑖-1 ), but instead we use properties of the convergence of Cordic: all of 𝜉 1 , . . . , 𝜉 𝜈 ∈ {-1, 1} have been chosen correctly if

𝜃 𝜈 -𝜃 ∈ [-𝛼 𝜈 , 𝛼 𝜈 ] (6)
in Setting 1, and

𝑌 𝜈 ∈ [-2 -𝐹 𝜈-1 , 2 -𝐹 𝜈-1 ] (7)
in Setting 2.

We outline below the circuits that imply the above statements. Let 𝑆 ∈ {1, 2} be the Cordic setting that defines the involved constants. Let 𝜉 * = (𝜉 1 , . . . , 𝜉 𝜈 ) and let

I = (⟨𝑋 𝑖 ⟩, ⟨𝑌 𝑖 ⟩) 𝜈-1 𝑖=1 , (s 𝑖 , s ′ 𝑖 , ⟨𝑋 ′ 𝑖 ⟩, ⟨𝑌 ′ 𝑖 ⟩) 𝜈-1 𝑖=0 , 𝜉 * )
be the vector of all intermediate values. The nullity of circuit

𝐶 𝐶𝑟𝑑 (𝜈, 𝑆; ⟨𝑋 0 ⟩, ⟨𝑌 0 ⟩, ⟨𝑋 𝜈 ⟩, ⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I)             𝐶 >> (𝐹 𝑖 ; ⟨𝑋 𝑖-1 ⟩, ⟨𝑋 ′ 𝑖-1 ⟩, s 𝑖-1 ) ∀𝑖 ∈ [𝜈] 𝐶 >> (𝐹 𝑖 ; ⟨𝑌 𝑖-1 ⟩, ⟨𝑌 ′ 𝑖-1 ⟩, s ′ 𝑖-1 ) ∀𝑖 ∈ [𝜈] (1 + 𝜉 * ) * (1 -𝜉 * ) ⟨𝑌 𝑖 ⟩ -⟨𝑌 𝑖-1 ⟩ -𝜉 𝑖 ⟨𝑋 ′ 𝑖-1 ⟩ ∀𝑖 ∈ [𝜈] ⟨𝑋 𝑖 ⟩ -⟨𝑋 𝑖-1 ⟩ + 𝑚𝜉 𝑖 ⟨𝑌 ′ 𝑖-1 ⟩ ∀𝑖 ∈ [𝜈] ⟨𝜃 𝜈 ⟩ -𝜈 𝑖=1 𝜉 𝑖 ⟨𝛼 𝑖 ⟩           
 is a proof of the core of the execution in eqs. ( 2) to [START_REF] Beimel | Protocols for Multiparty Coin Toss with Dishonest Majority[END_REF]. Here, for 𝑖 ∈ {1, . . . , 𝜈 }, s 𝑖 , s ′ 𝑖 ∈ {0, 1} 𝐹 𝑖 are auxiliary bit vectors to prove bit shifts of 𝑋 𝑖 and 𝑌 𝑖 with result 𝑋 ′ 𝑖-1 and 𝑌 ′ 𝑖-1 respectively. We complete the above core circuit for Setting 1. Let

𝛾 = ⌊log 2 (2⟨𝛼 𝜈 ⟩)⌋ + 1,
and let s 𝛼 ∈ {0, 1} 𝛾 be the bit decomposition of ⟨𝜃 ⟩ -⟨𝜃 𝜈 ⟩. The circuit

𝐶 𝐶𝑟𝑑1 (𝜈; ⟨𝜃 ⟩, ⟨𝑋 0 ⟩, ⟨𝑌 0 ⟩, ⟨𝑋 𝜈 ⟩, ⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I, s 𝛼 ) 𝐶 𝐶𝑟𝑑 (𝜈, 1; ⟨𝑋 0 ⟩, ⟨𝑌 0 ⟩, ⟨𝑋 𝜈 ⟩, ⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I) 𝐶 𝑅𝑎 (𝛾; ⟨𝜃 ⟩ -⟨𝜃 𝜈 ⟩ + ⟨𝛼 𝜈 ⟩, s 𝛼 )
.

proves eqs. ( 2) to [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF]. Similarly, we extend the core circuit to a complete one for setting 2: for s 𝑌 equal to the bit decomposition of 𝑌 𝜈 , 𝐶 𝐶𝑟𝑑2 (𝜓, 𝜈; ⟨𝑋 0 ⟩, ⟨𝑌 0 ⟩, ⟨𝑋 𝜈 ⟩, ⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I, s 𝑌 )

𝐶 𝐶𝑟𝑑 (𝜈, 2; ⟨𝑋 0 ⟩, ⟨𝑌 0 ⟩, ⟨𝑋 𝜈 ⟩, ⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I) 𝐶 𝑅𝑎 (𝜓 -𝐹 𝜈 ; ⟨𝑌 𝜈 ⟩, s 𝑌 )

.

proves eqs. (2) to ( 5) and [START_REF] Benarroch | Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular[END_REF]. The instantiation of 𝐶 𝐶𝑟𝑑1 and 𝐶 𝐶𝑟𝑑2 for elementary functions is straightforward. Inputs that are intermediate values are defined as above. For trigonometric functions, we set I 𝑇 = (⟨𝜃 𝜈 ⟩, I, s 𝛼 ) and use proves 𝑠 = √ 𝑥. Finally, we point out that, with minor adjustments to the above approximations, proofs of hyperbolic trigonometric functions and 𝑒 𝑥 can be obtained.

Extending the Domain

Here we extend the domain of approximations, which is necessary for our sampling applications. We sometimes do not define inputs such as bit vectors for range proofs and other intermediate values that are clear from the context or that are already defined in previous circuits.

Sine and cosine. As shown, sine and cosine can be approximated in -𝜋 2 , 𝜋 2 . For 𝑄 ∈ {1, 2, 3, 4} we use the identity sin 𝑄 𝜋 2

+ 𝜃 ′ =              cos(𝜃 ′ ) if 𝑄 = 1 -sin(𝜃 ′ ) if 𝑄 = 2 -cos(𝜃 ′ ) if 𝑄 = 3 sin(𝜃 ′ ) if 𝑄 = 4 extend the domain to [0, 2𝜋]. Let s 𝜋 , s ′
𝜋 be bit vectors as needed for 𝐶 𝐺𝑅𝑎 , and

I 𝑇𝑔 = (⟨𝜃 ′ ⟩, ⟨𝑠 ′ ⟩, ⟨𝑐 ′ ⟩, 𝑄, s 𝜋 , s ′ 𝜋 , I 𝑇 ). Let ( [ 𝑗 1 ], [ 𝑗 2 ], [ 𝑗 3 ], [ 𝑗 4 ]) = (⟨𝑐 ′ ⟩, -⟨𝑠 ′ ⟩, -⟨𝑐 ′ ⟩, ⟨𝑠 ′ ⟩) and ( [𝑘 1 ], [𝑘 2 ], [𝑘 3 ], [𝑘 4 ]) = ([ 𝑗 2 ], [ 𝑗 3 ], [ 𝑗 4 ], [ 𝑗 1 ])
for 𝑖 ∈ {1, 2, 3, 4} be literal variable replacements. Circuit

𝐶 𝑇 𝑟𝐺 (𝜈; ⟨𝜃 ⟩, ⟨𝑠⟩, ⟨𝑐⟩, I 𝑇𝑔 )         𝐶 𝑇 𝑟 (𝜈; ⟨𝜃 ′ ⟩, ⟨𝑠 ′ ⟩, ⟨𝑐 ′ ⟩, I 𝑇 ) 𝐶 𝐺𝑅𝑎 (⟨-𝜋 2 ⟩, ⟨ 𝜋 2 ⟩; ⟨𝜃 ′ ⟩, s 𝜋 , s ′ 𝜋 ) ⟨𝜃 ⟩ -𝑄 ⟨ 𝜋 2 ⟩ -⟨𝜃 ′ ⟩ 4 𝑖=1 (𝑄 -𝑖) 2 + ([ 𝑗 𝑖 ] -⟨𝑠⟩) 2 + ([𝑘 𝑖 ] -⟨𝑐⟩) 2         proves 𝑠 = 𝑠𝑖𝑛(𝜃 )
and 𝑐 = cos(𝜃 ) in the extended domain.

Natural logarithm. We extend the domain of ln(𝑥) to (0, 1). For 𝑥 ′ ∈ [ 1 2 , 1) and non-negative integer 𝑒 such that 𝑥 = 2 -𝑒 𝑥 ′ ∈ (0, 1). We prove that 𝑙 = ln(𝑥 ′ ) -𝑒 ln(2) = ln(𝑥). Let I 𝐿𝑔 = (𝑒, ℎ, e, s 𝑥 ′ , ⟨𝑥 ′ ⟩, ⟨𝑙 ′ ⟩, I 𝐿 ), then

𝐶 𝐿𝑜𝑔𝐺 (𝜓, 𝜈; ⟨𝑥⟩, ⟨𝑙⟩, I 𝐿𝑔 )           𝐶 𝐿𝑜𝑔 (𝜓, 𝜈; ⟨𝑥 ′ ⟩, ⟨𝑙 ′ ⟩, I 𝐿 ) 𝐶 𝑅𝑎 (𝜓 -1; ⟨𝑥 ′ ⟩ -⟨0.5⟩, s 𝑥 ′ ) 𝐶 𝐼 𝐸𝑥 (𝜓 -1, 2; 𝑒, ℎ, e) ℎ⟨𝑥⟩ -⟨𝑥 ′ ⟩ ⟨𝑙⟩ -⟨𝑙 ′ ⟩ + 𝑒 ⟨ln(2)⟩           proves our approximation.
Square root. Now, for a public bound 𝐵 > 0 and a private 𝑥 ∈ [0, 𝐵], we prove that 𝑠 = √ 𝑥.

Let 𝛾 = ⌊log 2 (𝐵)⌋ + 1. We choose 𝑥 ′ ∈ [ 1 2 , 1
) and an integer 𝑒 ∈ [-𝜓, 𝛾] such that 𝑥 = 2 𝑒 𝑥 ′ , and we have that

√ 𝑥 = 2 𝑒/2 √ 𝑥 ′ if 𝑒 is even 2 (𝑒+1)/2 𝑥 ′ /2
if 𝑒 is odd.

We break the proof in several circuits to handle different cases. For that we use bit variables as flags to decide which computation will be proven. Let 𝑛 𝑒 ∈ {0, 1} be the "negativity flag" of 𝑒 and 𝑒 ′ ≥ 0 such that 𝑒 = (1 -𝑛 𝑒 )𝑒 ′ . Let 𝑖 𝑒 ∈ {0, 1} be the "parity flag" of 𝑒, such that 𝑒 = 2𝑓 -𝑖 𝑒 for an integer 𝑓 . We also define 𝑓 ′ ≥ 0 such that 𝑓 = (1 -𝑛 𝑒 )𝑓 ′ . We first handle the relations between 𝑥, 𝑥 ′ , 𝑠 = √ 𝑥 and 𝑠 ′ = 𝑥 ′ /(1 + 𝑖 𝑒 ) when 𝑒 is non-negative, or equivalently, when 𝑛 𝑒 = 0. Let I 𝐷1 = (𝑙, f, I >> ), then our circuit is

𝐶 𝑆𝐷𝑜𝑚1 (𝐵; ⟨𝑥⟩, ⟨𝑠⟩, ⟨𝑥 ′ ⟩, ⟨𝑠 ′ ⟩, 𝑖 𝑒 , 𝑒 ′ , 𝑓 ′ , I 𝐷1 )         𝐶 𝑃 >> (𝛾; ⟨𝑥⟩, 𝑒 ′ + 𝑖 𝑒 , ⟨𝑥 ′ ⟩, I >> ) 𝑒 ′ -2𝑓 ′ + 𝑖 𝑒 𝐶 𝐼 𝐸𝑥 (𝛾, 2; 𝑓 ′ , 𝑙, f) ⟨𝑠⟩ -⟨𝑠 ′ ⟩𝑙         .
Similarly, for I 𝐷2 = (ℎ, e, I ′ >> ) the case when 𝑒 is negative is described by

𝐶 𝑆𝐷𝑜𝑚2 (𝜓 ; ⟨𝑥⟩, ⟨𝑠⟩, ⟨𝑥 ′ ⟩, ⟨𝑠 ′ ⟩, 𝑖 𝑒 , 𝑒 ′ , 𝑓 ′ , I 𝐷2 )         𝐶 𝐼 𝐸𝑥 (𝜓 -1, 2; 𝑒 ′ -𝑖 𝑒 , ℎ, e) ⟨𝑥 ′ ⟩ -ℎ⟨𝑥⟩ 𝑒 ′ -2𝑓 ′ -𝑖 𝑒 𝐶 𝑃 >> (𝜓 -1; ⟨𝑠⟩, 𝑓 ′ , ⟨𝑠 ′ ⟩, I ′ >> )        
.

Now
              𝐶 𝑆𝑞𝑟𝑡 (𝜓, 𝜈; ⟨𝑥 ′ ⟩, ⟨𝑠 ′ ⟩, I 𝑆 ) 𝑖 𝑒 (1 -𝑖 𝑒 ) 𝑛 𝑒 (1 -𝑛 𝑒 ) 𝑖 𝑒 * 𝐶 𝑅𝑎 (𝜓 -2; ⟨𝑥 ′ ⟩ -⟨0.25⟩, s 𝑥 ′ ) (1 -𝑖 𝑒 ) * 𝐶 𝑅𝑎 (𝜓 -1; ⟨𝑥 ′ ⟩ -⟨0.5⟩, s 𝑥 ′ ) (1 -𝑛 𝑒 ) * 𝐶 𝑆𝐷𝑜𝑚1 (𝐵; ⟨𝑥⟩, ⟨𝑠⟩, I 𝐷 , I 𝐷1 ) 𝑛 𝑒 * 𝐶 𝑆𝐷𝑜𝑚2 (𝜓, ⟨𝑥⟩, ⟨𝑠⟩, I 𝐷 , I 𝐷2 )               .
While the circuit above is easier to read, the practical implementation contains a number of further optimizations to reduce the number of multiplications. In particular, additional variables are introduced to avoid multiplying flags such as 𝑖 𝑒 with larger vectors such as the output of a 𝐶 𝑅𝑎 circuit. This introduces additional variables, e.g., 𝑖 𝑒 * 𝐶 𝑅𝑎 (𝜓 -2; ⟨𝑥 ′ ⟩ -⟨0.25⟩, s 𝑥 ′ ) would become 𝑖 𝑒 (𝑥 ′ -𝑥 ′ 𝑎𝑢𝑥 ) and 𝐶 𝑅𝑎 (𝜓 -2; ⟨𝑥 ′ 𝑎𝑢𝑥 ⟩ -⟨0.25⟩, s 𝑥 ′ 𝑎𝑢𝑥 ).

THE LAPLACE DISTRIBUTION 7.1 Private Laplace Sampling

Protocol 6 (private drawing from Laplace). First, party 𝑃 1 privately draws 𝑠 0 and 𝑎 ′ uniformly at random in [0, 𝐿) with 𝐿 sufficiently large (Protocol 2). Then, 𝑃 1 computes 𝑎 = -𝑏 log(1 -𝑎 ′ /𝐿), 𝑠 = 2(𝑠 0 mod 2) -1 and 𝑟 = 𝑠𝑎, and provides a ZKP for these relations (in Section 6.3 we showed a ZKP for the logarithm function, in Section 6.1 for approximate division).

As Protocol 2 verifiably draws random numbers uniformly and for the other computations in Protocol 6 a ZKP is provided, Protocol 6 verifiably draws random numbers from the 𝐿𝑎𝑝 (𝑏) distribution.

An alternative method could be based on work by [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF] (see also [START_REF] Choi | Differentially-Private Multi-Party Sketching for Large-Scale Statistics[END_REF] for related ideas). In particular, [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF] proposes a technique to sample directly from the exponential distribution using a range of independent biased coin flips. The main advantage of our method is that we only need one uniformly sampled public random number, which strongly reduces the communication cost.

This remark also holds for the protocol of Laplace hidden draws which we will present in Section 7.2 below.

Hidden Laplace Sampling

We can also make hidden draws from the Laplace distribution, i.e., drawing a Laplace-distributed random number 𝑟 as a secret share ⟦𝑟 ⟧. For this, we build on the basic operations discussed in Section 2.5.

First, we observe that one can sample a sign 𝑠 uniformly from {-1, 1} as follows: the parties apply Protocol 3 to draw a secret shared random number uniformly distributed in Z 𝑝 , obtaining the sharing ⟦𝑡⟧, next they multiply the sharing with itself to obtain 𝑡 2 and open 𝑡 2 to reveal 𝑡 2 , and finally they multiply ⟦𝑡⟧ with the public constant 1/ √ 𝑡 2 to obtain ⟦𝑠⟧ = 𝑡/ √ 𝑡 2 ∈ {-1, 1}. Drawing a secret shared random bit 𝑏 ∈ {0, 1} is then just drawing a sign ⟦𝑠⟧ and computing ⟦𝑏⟧ = (⟦𝑠⟧ + 1) /2 (this is protocol 𝑅𝐴𝑁 2 in [START_REF] Damgard | Unconditionally secure constant rounds multi-party computation for equality, comparison, bits and exponentiation[END_REF]).

The Cordic algorithm for logarithm computation described in Section 6.2 requires only additions, bit shifts and comparisons (when setting 𝜉 𝑖 = sign (-𝑌 𝑖-1 )). While it does not directly use multiplications, implementations of bit operations and comparisons, e.g., as in [START_REF] Damgard | Unconditionally secure constant rounds multi-party computation for equality, comparison, bits and exponentiation[END_REF], often are using multiplications so the use of multiplications cannot be fully avoided. Alternative strategies to compute the logarithm suffer from similar challenges.

As in Section 7.1, we want to draw a number 𝑎 ′ uniformly from [0, 𝐿), compute 𝑎 = -𝑏 log(1 -𝑎 ′ /𝐿) and multiply it with a random sign 𝑠 to get the random number 𝑎𝑠 distributed according to 𝐿𝑎𝑝 (𝑏). To compute log(𝑥), Cordic expects 𝑥 ∈ [1/4, 1), so before applying Cordic we may need to scale its input to fit this interval.

We set 𝐿 = 2 𝑙 for some sufficiently large integer 𝑙 and generate 𝑎 ′ as an 𝑙-bit number, i.e., ⟦𝑎 ′ ⟧ = 𝑙-1 𝑖=0 𝑎 (𝑖) 2 𝑖 where 𝑎 (𝑖) are random bits.

We can find the highest zero bit of 𝑎 ′ as follows: set ℎ 𝑙 = 0, ℎ ′ 𝑙 = 1 and 𝑎 (-1) = 0, and for 𝑖 = 𝑙 -1 . . . -1, set ℎ ′ 𝑖 = ℎ ′ 𝑖+1 ⟦1ℎ 𝑖+1 ⟧ and ⟦ℎ 𝑖 ⟧ = ℎ ′ 𝑖 1 -𝑎 (𝑖) . The meaning of ℎ 𝑖 then is 'bit 𝑖 is the highest 0-bit', and the meaning of ℎ ′ 𝑖 is 'the bits higher than bit 𝑖 are all ones'. Exactly one ℎ 𝑖 equals 1 and all others are 0 among 𝑖 = -1 . . . 𝑙 -1. We then can write log(1 -𝑎 ′ /𝐿) = 𝑎 h + log(𝑥) with 𝑎 h = 𝑙-1 𝑖=0 ⟦ℎ 𝑖 ⟧ log(2 𝑖+1-𝑙 ) and 𝐵𝐼𝑇 𝑆 (𝑥, (𝑥 (𝑖) ) 𝑙 𝑖=0 ) where (⟦𝑥 (𝑖) ⟧) 𝑙 𝑖=0 = Bit-add(2 𝑙 , (⟦𝑥 (𝑖) -⟧) 𝑙-1 𝑖=0 )

and ⟦𝑥 (𝑖) -⟧ = 𝑙-1 𝑗=0 ⟦ℎ 𝑗 ⟧⟦𝑎 (𝑖+𝑗+1-𝑙) ⟧ (with 𝑎 (𝑖) = 0 for 𝑖 < 0). Now we can apply Cordic on 𝑥. Cordic needs additions (using the Bit-add protocol), bit shifts (moving bits to the right and duplicating the highest bit), the sign(•) function (check the highest bit) and negation (invert all bits and add 1). Protocol 7 (hidden drawing from Laplace). One can verifiably draw a hidden Laplace-distributed random number by following the steps explained above, and by providing ZKP for all computations. The ZKP are similar to those for private sampling, where parts of secret shares are transfered between parties, the parties can agree on the commitment which will represent the shared number.

THE GAUSSIAN DISTRIBUTION

In this section we elaborate several strategies to sample from the Gaussian distribution.

In particular, we are interested in protocols such that upon termination one party has a private number 𝑦 ∈ Q ⟨𝑝,𝜓 ⟩ and has provided a zero knowledge argument that 𝑦 ∼ N (𝜇, 𝜎 2 ) for some public 𝜇 and 𝜎.

All methods require as a subprotocol sampling uniformly distributed numbers. Therefore all our protocols for private drawing numbers from the Gaussian distribution follow the same high-level structure:

(1) use Protocol 2 to verifiably draw uniformly distributed number(s), (2) transform the uniformly distributed number(s) into Gaussian distributed number(s), and (3) use an arithmetic circuit matching this transformation together with compressed Σ-protocols (see Section 2.4) to prove the transformation.

We implement ZKPs of the correct execution of Gaussian draws. The sampling methods we implement are (1) the central limit theorem approach (averaging over uniform samples), (2) the Box Müller method [START_REF] Box | A Note on the Generation of Random Normal Deviates[END_REF], (3) the Polar Method [START_REF] Marsaglia | A Convenient Method for Generating Normal Variables[END_REF], (4) the inversion method using a series expansion for erf -1 [START_REF] Chevillard | The functions erf and erfc computed with arbitrary precision and explicit error bounds[END_REF], and (5) the inversion method using a fractional polynomial to approximate erf -1 [START_REF] Giles | Approximating the erfinv function[END_REF].

The Central Limit Theorem Method

The uniform distribution over the interval [0, 𝐿) has variance 𝐿 2 /12. Let a party privately draw 𝑁 random numbers {𝑥 𝑖 } 𝑁 𝑖=1 uniformly distributed over [0, 𝐿), and compute

𝑥 = 𝜇 + 𝜎 √ 12 𝐿 √ 𝑁 𝑁 𝑖=1 𝑥 𝑖 -𝐿 2 .
Then, 𝑥 is N (𝜇, 𝜎 2 ) distributed. For a ZKP for this relation between 𝑥 and the 𝑥 𝑖 we only need the homomorphic property of the Pedersen commitment (for the additions and the multiplication with a constant) and a range proof (for the rounding). This method is essentially the technique of [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF] to sample from the Gaussian distribution.

The Box Müller Method

The Box Müller method [START_REF] Box | A Note on the Generation of Random Normal Deviates[END_REF] consists of drawing two uniform samples 𝑈 1 and 𝑈 2 in the interval (0, 1) and to compute

𝜌 = -2 ln(𝑈 1 ), 𝑋 1 = 𝜌 cos(2𝜋𝑈 2 ) 𝑎𝑛𝑑 𝑋 2 = 𝜌 sin(2𝜋𝑈 2 ).
Then, 𝑋 1 and 𝑋 2 are distributed according to N (0, 1). Now we use circuits of elementary functions defined in Section 6 to construct our proof. Recall parameters 𝜓 and the number of Cordic iterations 𝜈 defined therein. Let

I 𝐵𝑀 = (s 1 , s 2 , s 3 , ⟨𝑠⟩, ⟨𝑐⟩, I 𝑇𝑔 , ⟨𝑎 𝜋 ⟩, ⟨𝑋 ′ 1 ⟩, ⟨𝑋 ′ 2 ⟩ I 𝑆𝑔 , ⟨𝜌⟩, I 𝐿𝑔 , ⟨𝑙⟩, a ′ 1 , a ′ 2 , U ′ 1 , U ′ 2 , a ′′ 1 , a ′′ 2 , U ′′ 1 , U ′′ 2 )
be a vector containing all intermediate values of the computation.

Then the approximation circuit is

𝐶 𝐵𝑀 (𝜓, 𝜈, 𝑧 1 , 𝑧 2 ; ⟨𝑈 1 ⟩, ⟨𝑈 2 ⟩, ⟨𝑋 1 ⟩, ⟨𝑋 2 ⟩, I 𝐵𝑀 )                 𝐶 𝑀𝑜𝑑 (2 𝜓 -1, 𝑧 1 ; 𝑎 1 , ⟨𝑈 1 ⟩ -1, a ′ 1 , a ′ 2 , U ′ 1 , U ′ 2 ) 𝐶 𝑀𝑜𝑑 (2 𝜓 -1, 𝑧 2 ; 𝑎 2 , ⟨𝑈 2 ⟩ -1, a ′′ 1 , a ′′ 2 , U ′′ 1 , U ′′ 2 ) 𝐶 𝐿𝑜𝑔𝐺 (

The Polar Box-Müller Method

The polar method [START_REF] Knop | Remark on algorithm 334 [G5]: normal random deviates[END_REF]

⟨𝑉 ′ 2 ⟩, ⟨𝑉 ′ 1 ⟩, v ′ , v, a ′ 1 , a ′ 2 , V ′ 1 , V ′ 2 , a ′′ 1 , a ′′ 2 , V ′′ 1 , V ′′
2 ) be a vector of intermediate computation values, then the implemented circuit is

𝐶 𝑃𝑜𝑙 (𝜓, 𝜈, 𝑧 1 , 𝑧 2 ; ⟨𝑉 1 ⟩, ⟨𝑉 2 ⟩, ⟨𝑌 1 ⟩, ⟨𝑌 2 ⟩, I 𝑃𝑜𝑙 )                           𝐶 𝑀𝑜𝑑 (2 2𝜓 -2, 𝑧 1 ; 𝑎 1 , ⟨𝑉 1 ⟩ + ⟨1⟩ -1, a ′ 1 , a ′ 2 , V ′ 1 , V ′ 2 ) 𝐶 𝑀𝑜𝑑 (2 2𝜓 -2, 𝑧 2 ; 𝑎 2 , ⟨𝑉 2 ⟩ + ⟨1⟩ -1, a ′′ 1 , a ′′ 2 , V ′′ 1 , V ′′ 2 ) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝑉 1 ⟩, ⟨𝑉 1 ⟩, ⟨𝑉 ′ 1 ⟩, v) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝑉 2 ⟩, ⟨𝑉 2 ⟩, ⟨𝑉 ′ 2 ⟩, v ′ ) ⟨𝛼⟩ -⟨𝑉 ′ 1 ⟩ -⟨𝑉 ′ 2 ⟩ 𝐶 𝐺𝑅𝑎 (1, ⟨1⟩ -1; ⟨𝛼⟩, s 1 , s 2 )
𝐶 𝐿𝑜𝑔𝐺 (𝜓, 𝜈; ⟨𝛼⟩, ⟨𝑙⟩, I 𝐿𝑔 ) 𝐶 𝐷𝑖𝑣 (𝜓 ; -2⟨𝑙⟩, ⟨𝛼⟩, ⟨𝑑⟩, s 3 , s 4 ) 𝐶 𝑆𝑞𝑟𝑡𝐺 (𝜓, 𝜈, 2 𝜓 +1 𝜓 ln(2); ⟨𝑑⟩, ⟨𝑠⟩,

I 𝑆𝑔 ) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝑠⟩, ⟨𝑉 1 ⟩, ⟨𝑌 1 ⟩, s 5 ) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝑠⟩, ⟨𝑉 2 ⟩, ⟨𝑌 2 ⟩, s 6 )                           .
To avoid multiple interactions due to rejection, Protocol 2 is set to draw a sufficiently large number of uniform samples such that at least one pair is not rejected with high probability. The cost of the extra samples is negligible. To obtain a distribution with different mean and variance, we scale 𝑉 1 and 𝑉 2 with addition and product.

The Inversion Method

Inverting eq. ( 1) we get

𝐹 -1 N (𝑥) = √ 2erf -1 (2𝑥 -1).
There are many numerical strategies to approximate either erf or erf -1 , of which we implemented two.

A first strategy due to [START_REF] Chevillard | The functions erf and erfc computed with arbitrary precision and explicit error bounds[END_REF] is to use the series

erf(𝑥) = 2 √ 𝜋 ∞ 𝑙=0 (-1) 𝑙 𝑥 2𝑙+1 𝑙!(2𝑙 + 1)
.

However, its approximation error gets larger as 𝑥 gets bigger. Therefore, when 𝑥 is large, it is better approximate erfc(𝑥) = 1erf(𝑥) using the series

erfc(𝑥) = 𝑒 -𝑥 2 𝑥 √ 𝜋 𝐿-1 𝑙=0 (-1) 𝑙 (2𝑙 -1)!! (2𝑥 2 ) 𝑙 + 𝑅 𝐿 (𝑥),
where

𝑅 𝐿 (𝑥) ≤ 𝑒 -𝑥 2 𝑥 √ 𝜋 (2𝐿 -1)!! (2𝑥 2 ) 𝐿
is the remainder, 𝑙!! = 1 for 𝑙 < 1 and (2𝑙 -1)!! = 𝑙 𝑖=1 (2𝑖 -1). The number of terms 𝐿 of the series is tuned for minimal error. If we set 𝐵 to be the maximum error of our approximation, we use erf if

𝑥 < ln(1/𝐵) 2
+ 0.788 and erfc otherwise. The ZKP of this method proves that 𝑦 = erf(𝑥) or 1 -𝑦 = erfc(𝑥) depending on the domain of 𝑥.

A second strategy is proposed in [START_REF] Giles | Approximating the erfinv function[END_REF] and uses a rational approximation. Therein, erf -1 is computed by

erfinv SP (𝑥) = 𝑥𝑝 1 (𝑤) if 𝑤 ≤ 5 (central region) 𝑥𝑝 2 (𝑠) if 𝑤 > 5 (tail region)
where 𝑤 =log(1-𝑥 2 ), 𝑠 = √ 𝑤 and 𝑝 1 and 𝑝 2 are two polynomials of degree 8. We use Cordic, product and range ZKPs to prove its computation.

Hidden Drawing

For the several strategies for sampling the Gaussian distribution described above, one can construct a protocol based on secret sharing for hidden sampling. Similar considerations apply as for the discussion in Section 7.2. As an example, we show a protocol using the Central Limit Theorem approach.

𝑗 = 0. Let (⟦𝑦 (𝑖) 1 ⟧) 𝑙+log 2 𝑁 𝑖=0 = (⟦𝑥 1 ⟧) 𝑙+log 2 𝑁 𝑖=0 and for 𝑗 = 2 . . . 𝑁 let (⟦𝑦 (𝑖) 𝑗 ⟧) 𝑙+log 2 𝑁 𝑖=0 = Bit-add((⟦𝑦 (𝑖) 𝑗-1 ⟧) 𝑙+log 2 𝑁 𝑖=0 , (⟦𝑥 (𝑖) 𝑗 ⟧) 𝑙+log 2 𝑁 𝑖=0
).

Finally let ⟦𝑟 ⟧ = 𝑙+log 2 𝑁 𝑖=log 2 (𝑁 /12)/2 𝑦 (𝑖)
𝑁 2 𝑖-log 2 (𝑁 /12)/2 . Then, 𝑟 approximates N (2 𝑙 √ 3𝑁 , 2 𝑙 ). The computations can be made verifiable using a ZKP where parties send a number to each other can agree on using the same commitment.

EVALUATION

In this section, we present an empirical comparison of several methods to privately sample from the Gaussian distribution. We will publish code to reproduce all experiments together with the final version of this paper.

Setup

We evaluate the costs of the methods presented in Section 8. Namely, the Central Limit Theorem approach (CLT), the Box Müller (BM), the Polar Method (PolM) and the inversion method. In the latter, we evaluate the two described strategies: using series (InvM-S) and rational approximations (InvM-R). Samples are generated for the N (0, 1) distribution.

We evaluate the cost of each method instantiated for several parameters against the statistical quality of the generated samples. For the computational cost we measure the exponentiations in G (GEX), which dominate the computation. The total communication cost is the number of elements of G and Z 𝑝 sent (see Section 2.4). To measure the statistical quality, we generate 10 7 samples and measure the Mean Squared Error (MSE) from the ideal Gaussian CDF.

The varying parameter for BM and PolM is the number of iterations 𝜈 of their Cordic approximations, which is chosen between 2 and 14. For CLT we vary the number of averaged uniform terms between 2 and 400. For InvM-R, the number of terms of the approximation series is changed in order to obtain different approximations with errors between 0.5 and 2 -20 . The rational approach InvM-R has no varying parameter. The representation parameter 𝜓 which defines Q ⟨𝑝,𝜓 ⟩ is chosen to be the smallest as allowed by BM, PolM, InvM-S due to approximation constraints, and for CLT is set to optimize the quality/cost tradeoff .

Results

Figure 1 shows the communication costs, i.e., the number of elements of G required to prove one Gaussian draw. Note that, as described in Section 2.4, 6 elements of Z 𝑝 must be added to obtain the final cost. If high precision isn't important, CLT performs well, but in general PolM, BM and Inv-R give the best precision for a given computational investment. The Inv-R method is much simpler but can't be tuned to other precisions.

Figure 2 shows the number of GEX to prove (by the party who draws the number) or to verify (by another party) one Gaussian draw. Here too, BM and PolM are the most efficient methods as soon as a good statistical quality is required. We note that, as the communication cost is logarithmic in the number of inputs and multiplication gates, several parameter settings give different points in Figure 2 but may have the same communication cost, so in Figure 1 we just show the proof with best statistical quality.

For illustration, if we implement Pedersen commitments using the secp256k1 1 elliptic curve, we obtain 128 bit security and an element of G can be represented with 257 bits. One GEX using this 1 See https://www.secg.org/SEC2-Ver-1.0.pdf and https://github.com/bitcoin-core/ secp256k1 curve takes no more than 30 microseconds on an Intel Core i7-6600U at 2.60 GHz CPU. With BM, PolM and InvM-R, a sample with MSE < 2 -20 requires less than 900 Bytes of communication. With PolM, such sample takes less than 360 milliseconds (ms) to prove and 75 ms for its verification. While CLT quickly gets very expensive, if quality is less important and an MSE > 2 -13 is satisfactory, it is the most efficient approach. A proof of a sample using CLT with MSE 0.01 can be generated in less than 10 ms, verified in 3 ms and has a size of 482 Bytes. We also note that it is possible to further optimize our implementation using special-purpose algorithms [START_REF] Möller | Algorithms for Multi-exponentiation[END_REF] to compute multiple exponentiations in the form g b .

Finally, in Figure 3 we show the gap in the communication cost between our PolM and CLT sampling techniques implemented with classic (non-compressed) Σ-protocols [START_REF] Cramer | Modular Design of Secure yet Practical Cryptographic Protocols[END_REF][START_REF] Cramer | Zero-knowledge proofs for finite field arithmetic, or: Can zero-knowledge be for free?[END_REF] to the presented compressed techniques.

APPLICATION: DIFFERENTIALLY PRIVATE MACHINE LEARNING

An important application of verifiable sampling can be found in the field of federated machine learning under differential privacy.

Consider parties P = {𝑃 𝑖 } 𝑛 𝑖=1 where each party 𝑃 𝑖 has some sensitive private data 𝑥 𝑖 . The parties P want to keep their data 𝑥 𝑖 private but want to collaborate to obtain statistical information 𝜃 of common interest. For example, assume that 𝑥 𝑖 ∈ R and the parties in P would like to compute 𝜃 = 1 𝑛 𝑛 𝑖=1 𝑥 𝑖 . Even if no inputs nor intermediate results are revealed, computing and sharing the exact statistic 𝜃 may impact privacy. For example, suppose thet 𝑥 𝑖 = 1 if 𝑃 𝑖 likes a particular idea or 𝑥 𝑖 = 0 if 𝑃 𝑖 doesn't like it. It may turn out that no party likes the idea of interest, in which case we would get 𝜃 = 0. If we publish that 𝜃 = 0 no party can claim anymore that it liked the idea, so its privacy is lost. Statistical notions of privacy, such as differential privacy [START_REF] Dwork | The algorithmic foundations of differential privacy[END_REF], add noise to guarantee the privacy of the individuals independently of the output. In particular, let 𝜃 be a function mapping datasets on values in X. We say datasets are adjacent if they differ in the data of only one party. Then, we say a randomized algorithm 𝐴 is (𝜖, 𝛿)differentially private (DP) if for any two adjacent datasets 𝐷 1 and 𝐷 2 and for any subset 𝑋 ∈ X, 𝑃 (𝐴(𝐷

1 ) ∈ 𝑋 ) ≤ 𝑒 𝜖 𝑃 (𝐴(𝐷 2 ) ∈ 𝑋 ) +𝛿. 𝐴 is 𝜖-DP if it is (𝜖, 0)-DP.
The most common strategy to make information DP before publication is to add noise from appropriately scaled Laplace or Gaussian distributions. For example, consider again the above example where the parties in P want to average their private 𝑥 𝑖 . Assume that ∀𝑖 ∈ [𝑛] : 0 ≤ 𝑥 𝑖 ≤ 1. Then, for any 𝜖 > 0, if we set θ = 𝜃 + 𝜂 with 𝜂 ∼ Lap(1/𝜖) there holds that θ is 𝜖-DP. Alternatively, for any 𝜖 > 0 and 𝛿 > 0, if we set θ = 𝜃 + 𝜂 with 𝜂 ∼ N (0, 2ln(1.25/𝛿)/𝜖 2 ) there holds that θ is (𝜖, 𝛿)-DP.

It is important that no party knows the added noise 𝜂, because knowing both θ and 𝜂 would allow to reconstruct 𝜃 = θ -𝜂. We present two protocols, one privately drawing random numbers, which produces a less accurate result, and one based on the more expensive hidden drawing which has optimal precision. Protocol 9 (DP learning using private sampling). Let P 𝑐𝑜𝑟 ⊂ P be the set of corrupted parties of size at most 𝜌𝑛 (with 0 ≤ 𝜌 < 1). As described in Section 8, let all parties 𝑃 𝑖 (𝑖 ∈ [𝑛]) privately verifiably draw a Gaussian random number 𝜂 ∼ N (0, 𝜎 2 /𝑛(1 -𝜌)), where noise with variance 𝜎 2 on 𝜃 would be sufficient to achieve the desired privacy level. Then, securely sum θ = 1 𝑛 𝑛 𝑖=1 (𝑥 𝑖 + 𝜂 𝑖 ) and publish θ .

Even if the corrupted parties would collect all noise they have contributed 𝜂 𝑐𝑜𝑙𝑙 = 𝑖 ∈P 𝑐𝑜𝑟 𝜂 𝑖 and subtracts it from θ to obtain 𝜃 𝑐𝑜𝑙𝑙 = θ -𝜂 𝑐𝑜𝑙𝑙 /𝑛, then there is still Gaussian noise with variance

𝜎 2 1-𝜌 -𝜌 𝜎 2
1-𝜌 = 𝜎 2 left on their best estimation of 𝜃 . This strategy, which adopts some ideas from [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF], works best for Gaussian noise, as the sum of Gaussian distributions is again a Gaussian distribution.

Protocol 10 (DP learning using hidden sampling). Let all parties 𝑃 𝑖 (with 𝑖 ∈ [𝑛]) represent their private number 𝑥 𝑖 as a shared secret. Let the parties next together verifiably drawn a hidden random number 𝜂, i.e., a random number they obtain only as a shared secret. Finally, let them sum the secret shares and reveal θ = 𝑛 𝑖=1 𝑥 𝑖 + 𝜂

The advantage of this protocol is that no parties see 𝜂 or parts of it, so it is impossible to get back towards the sensitive statistic 𝜃 . On the other hand, the full computation needs to be performed through multi-party computations, e.g., using shared secrets, which is clearly more expensive than the ZKPs which are needed in Protocol 9, especially as compressed Σ-protocols allow for ZKPs of size only logarithmic in the circuit size while calculations on secret shares have a linear communication cost.

As such drawing of random noise is a basic building block and needs to be performed repeatedly by secure federated differentially private machine learning algorithms, being able to draw from these probability distributions with low communication cost is essential to make algorithms more efficient.

Issues of finite precision. The work of [START_REF] Mironov | On Significance of the Least Significant Bits for Differential Privacy[END_REF] shows the impact that finite precision approximation of continuous distributions can have on DP guarantees. As explained in [42, Sec. 5.2], these vulnerabilities can be overcome by appropriately adjusting the precision and truncating the outcome after the noise is added to private values. This can be achieved in our protocols by using the correct precision parameters and range proofs.

To overcome vulnerabilities of finite precision approximations, other lines of work have explored the use of discrete distributions [START_REF] Clément L Canonne | The Discrete Gaussian for Differential Privacy[END_REF][START_REF] Kairouz | The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation[END_REF]. These methods require in expectation comparable computational effort as our protocols. However, sampling from a discrete distribution requires in the worst case many iterations which results in longer zero-knowledge proofs.

CONCLUSION

We have presented novel methods for drawing random numbers in a verifiable way in a public, private and hidden setting. We applied the ideas to the Laplace and Gaussian distribution, and evaluated several alternatives to sample from the Gaussian distribution.

We see several interesting directions for future work. First, we hope to develop novel strategies to let our methods scale better when in the course of an algorithm many random numbers are needed. Second, we would like to develop new methods which allow for more efficient sampling in the hidden setting where the random numbers are output as shared secrets. In particular, our current methods based on generic secret sharing techniques require multiple rounds of computation and communication, it may be possible to develop more efficient special-purpose strategies.

A COMPRESSED Σ-PROTOCOLS

In this appendix, we explain all necessary notions to understand compressed Σ-protocols [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF]. In Appendix A.1, we explain the basic concepts of ZKP. Classic approaches to construct ZKP of linear relations are shown in Appendix A.2 and techniques to compress the communication cost in Appendix A.3. In Appendix A.4 we explain how linear proofs can be used to construct ZKP involving circuit computations. Finally, Appendix A.5 has an application for range proofs and Appendix A.6 discusses the costs of the techniques.

A.1 Zero Knowledge Proofs and Arguments

An interactive proof of knowledge (PoK) for an NP relation R is a protocol between a prover P and a verifier V in which P tries to prove to V that they know a witness 𝑤 such that (𝑎, 𝑤) ∈ R for a public statement 𝑎. At the end of the protocol, V either accepts or rejects the proof. We denote by (𝑎; 𝑤) a member of a relation or an input of a protocol, using a semicolon to separate the public statement 𝑎 from the private witness 𝑤. The tuple of all messages in a proof is called the conversation or transcript. Proofs may satisfy the following properties:

• Completeness: a proof is complete if V always accepts the proof when (𝑎; 𝑤) ∈ R and P knows 𝑤. • Soundness: a proof is sound if any prover whose proof for statement 𝑎 is accepted by the verifier knows a valid witness 𝑤 such that (𝑎; 𝑤) ∈ R with overwhelming probability.

The notion of soundness we use is called witness extended emulation [START_REF] Lindell | Parallel Coin-Tossing and Constant-Round Secure Two-Party Computation[END_REF]. Proofs that are sound only if the prover is computationally bounded are also called arguments. • Zero Knowledge: a proof is zero knowledge if its transcript reveals no or negligible information about the witness other than its validity.

A.2 Σ-protocols for Linear Relations

We now show how to prove linear relations over secret committed values. Recall the definition of Pedersen vector commitments presented in Section 2.2, which defines the commitment domain Z 𝑝 , our underlying cryptographic group G and vector of elements g. As explained in Section 2.2, we reserve one of the components of g for randomness so that commitments are hiding. For 𝐿 :

Z 𝑘 𝑝 → Z 𝑝 a linear function in Z 𝑝 , that is 𝐿(𝑥 1 , . . . , 𝑥 𝑘 ) = 𝑎 1 𝑥 1 + • • • + 𝑎 𝑘 𝑥 𝑘 for coefficiens 𝑎 1 , . . . , 𝑎 𝑘 ∈ Z 𝑝 ,
a vector commitment 𝑃 ∈ G and a value 𝑦 ∈ Z 𝑝 , a prover P proves to know an opening x ∈ Z 𝑘 𝑝 of 𝑃 such that 𝐿(x) = 𝑦. We formally describe our linear relation by

R 𝐿 = {(𝑃 ∈ G, 𝑦 ∈ Z 𝑝 ; x ∈ Z 𝑘 𝑝 ) : 𝑃 = g x ∧ 𝑦 = 𝐿(x)}.
Note that in our case x has a coordinate reserved for randomness, so in valid relations the correspondent coefficient of 𝐿 must be 0. However, in later auxiliary protocols we will not impose such restriction. To provide a zero knowledge proof for R 𝐿 we use a family of zero knowledge proofs called Σ-protocols [START_REF] Cramer | Modular Design of Secure yet Practical Cryptographic Protocols[END_REF] and its compressed version proposed in [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF]. They provide soundness under the Discrete Logarithm Assumption (DLA). Protocol Π 0 below describes a classic proof of R 𝐿 originally stated for more general types of commitments defined in [START_REF] Cramer | Modular Design of Secure yet Practical Cryptographic Protocols[END_REF][START_REF] Cramer | Zero-knowledge proofs for finite field arithmetic, or: Can zero-knowledge be for free?[END_REF] and which we instantiate for the Pedersen scheme. Π 0 takes as input (𝑃, 𝑦; x): Protocol Π 0 (𝑃, 𝑦, x):

(1) P computes: r ← 𝑅 Z 𝑘 𝑝 , 𝐴 = g r , 𝑡 = 𝐿(r) (2) P sends to V: 𝐴, 𝑡 (3) V sends to P: 𝑐 ← 𝑅 Z 𝑝 (4) P sends to V: z = 𝑐x + r (5) V: if g z = 𝐴𝑃 𝑐 and 𝐿(z) = 𝑐𝑦 + 𝑡 then accept, else reject. Theorem 2. Π 0 is a complete, sound and zero knowledge proof of R 𝐿 .

We provide an intuition of how these properties are obtained. Completeness follows directly from the homomorphic property. For soundness, consider a prover P * that by following Π 0 can produce an accepting transcript ((𝐴, 𝑡), 𝑐 1 , z 1 ) with significant probability. Then it is shown that also with non-negligible probability, by using P * 's strategy many times, another accepting transcript of the form ((𝐴, 𝑡), 𝑐 2 , z 2 ) can be produced, where the first message is equal in both transcripts and such that 𝑐 1 ≠ 𝑐 2 . Now, since both transcripts are accepting, we have g z 1 = 𝐴𝑃 𝑐 1 and g z 2 = 𝐴𝑃 𝑐 2 so P * can efficiently compute the witness x = z 1 -z 2 𝑐 1 -𝑐 2 such that g x = 𝑃. Acceptance also implies that 𝐿(z 1 ) = 𝑐 1 𝑦 + 𝑡 and 𝐿(z 2 ) = 𝑐 2 𝑦 + 𝑡 and it follows that 𝐿(x) = 𝑦. Therefore is x a valid witness. Either P * already knew it or they can efficiently compute the discrete logarithms between components of g, which is a contradiction due to the DLA.

Zero knowledge is obtained by showing that all information seen in the proof is random that does not depend on the secrets. By only knowing the statement (𝑃, 𝑦) one can compute z ′ ← 𝑅 Z 𝑝 , 𝑐 ′ ← 𝑅 Z 𝑝 , 𝐴 ′ = 𝑃 -𝑐 ′ g z ′ and 𝑡 ′ = 𝐿(z ′ ) -𝑐 ′ 𝑦, and the transcript ((𝐴 ′ , 𝑡 ′ ), 𝑐 ′ , z ′ ) has the same distribution as a conversation between an honest prover and a honest verifier. Note that, as it is computed in reverse, ((𝐴 ′ , 𝑡 ′ ), 𝑐 ′ , z ′ ) cannot be efficiently produced in the actual protocol by a dishonest prover. Note that this reasoning only holds if the verifier is honest and generates its messages uniformly at random. To circumvent this, we implement our proofs transforming them into non-interactive proofs using the Strong Fiat-Shamir heuristic [START_REF] Bernhard | How Not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios[END_REF], where the verifier is replaced by a hash function and therefore without the need of involving a trusted party. The construction is secure under the Random Oracle Model [START_REF] Bellare | Random oracles are practical: a paradigm for designing efficient protocols[END_REF].

A.3 Compression Mechanism

Now we reduce the communication cost of Π 0 using ideas of compressed Σ-protocols [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF] and also present in [START_REF] Bootle | Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting[END_REF][START_REF] Bunz | Bulletproofs: Short Proofs for Confidential Transactions and More[END_REF]. The transfer in Π 0 is dominated by the third message of the protocols in Step 4, with size of 𝑘 elements of Z 𝑝 . It can be reduced if instead of sending z, P proves that (𝐴𝑃 𝑐 , 𝑐𝑦 + 𝑡; z) ∈ R 𝐿 which would imply the condition tested in Step 5. Note that this proof does not need to be zero knowledge as z is originally revealed in Π 0 . We first present Π 1 , a proof of R that halves communication cost by "folding" z before sending it. Next, we show how to use this protocol to reduce cost of Π 0 . By assuming that 𝑘 is even, we define g 𝐿 = (𝑔 1 , . . . , 𝑔 𝑘/2 ) ∈ G 𝑘/2 and g 𝑅 = (𝑔 (𝑘/2)+1 , . . . , 𝑔 𝑘 ) ∈ G 𝑘/2 and analogously for x 𝐿 ∈ Z 𝑘/2 𝑝 and x 𝑅 ∈ Z 𝑘/2 𝑝 . We also define 𝐿 𝐿 : Z 𝑘/2 𝑝 → Z 𝑝 and 𝐿 𝑅 : Z 𝑘/2 𝑝 → Z 𝑝 such that 𝐿 𝐿 (a) = 𝐿(a, 0) and 𝐿 𝑅 (a) = 𝐿(0, a). We use, an additional group element ĝ ∈ G generated in the same way as the components of g.

Protocol Π 1 (𝑃, 𝑦; x):

(1) P computes:

𝐴 = g x 𝐿 𝑅 ĝ𝐿 𝑅 (x 𝐿 ) , 𝐵 = g x 𝑅 𝐿 ĝ𝐿 𝐿 (x 𝑅 ) (2) P sends to V: 𝐴, 𝐵 (3) V sends to P: 𝑐 ← 𝑅 Z 𝑝 (4) P sends to V: z = x 𝐿 + 𝑐x 𝑅 (5) V: if (g 𝑐 𝐿 * g 𝑅 ) z ĝ𝑐𝐿 𝐿 (z)+𝐿 𝑅 (z) = 𝐴(𝑃 ĝ𝐿(x) ) 𝑐 𝐵 𝑐 2 then accept, else reject
Π 1 is a complete and sound proof of R 𝐿 with half the communication of Π 0 . The communication of Step 4, can be further reduced by applying Π 1 recursively until the size of z is sufficiently small. Let Π 𝐵 ⋄ Π 𝐴 be the interactive proof obtained executing Π 𝐴 except for the last message and then executing Π 𝐵 . Now we can define to Π 𝑐 = Π 1 ⋄ . . . ⋄ Π 1 ⋄ Π 0 where the ⋄ is applied log 2 (𝑘) -2 times.

Note that 𝑘 requires to be a power of 2, but padding vectors with 0's is sufficient to fix this. Presented with more detail, it is proven in Theorem 3 of [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF], that Π 𝑐 is a complete, sound and zero knowledge protocol for R 𝐿 . Completeness is straightforward, and for zero knowledge it is sufficient to see that Π 0 is already zero knowledge, and the rest of the protocol only reveals as much as Π 0 . Soundness follows from similar ideas than those shown for Theorem 2.

Amortization techniques can be applied to prove many nullity checks, where the prover claims for linear relations 𝐿 1 , . . . , 𝐿 𝑟 that 𝐿 𝑖 (x) = 0 for all 𝑖 ∈ {1, . . . , 𝑟 }. For that, V sends a random value 𝜌 ← Z 𝑝 and then P and V execute Π 𝑐 on input (𝑃, 𝑟 𝑖=1 𝜌 𝑖-1 𝐿 𝑖 , 0; x). If 𝐿(x) = 0 then 𝐿 𝑖 (x) = 0 for all 𝑖 with overwhelming probability 1 -(𝑟 -1)/𝑝. Amortized nullity checks also hold when replacing linear forms by affine forms Φ 1 , . . . , Φ 𝑟 where each one is the application of a linear form plus a constant. We denote this protocol by Π 𝑁 and its input by (𝑃, (Φ 1 , . . . , Φ 𝑟 ); x). A prover can prove the opening of an affine map Φ : Z 𝑘 𝑝 → Z 𝑟 𝑝 to y = (𝑦 1 , . . . , 𝑦 𝑟 ) ∈ Z 𝑟 𝑝 by running Π 𝑁 on input (𝑃, (Φ 1 -𝑦 1 , . . . , Φ 𝑟 -𝑦 𝑟 ); x) where Φ 1 , . . . , Φ 𝑟 : Z 𝑘 𝑝 → Z 𝑝 are the affine forms that compose Φ. The communication cost of these protocols sends 𝑟 -1 elements of Z 𝑝 more than Π 𝑐 , which account for the size of y.

A.4 Proving Multiplications and Circuits

Now, we show the idea of [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF] to prove multiplicative relations only with black-box access to Π 𝑁 . For a set committed triplets (𝛼 1 , 𝛽 1 , 𝛾 1 ), . . . , (𝛼 𝑚 , 𝛽 𝑚 , 𝛾 𝑚 ), P proves to V that 𝛼 𝑖 𝛽 𝑖 = 𝛾 𝑖 for all 𝑖 ∈ {1, . . . , 𝑚}. Let 𝛼 = (𝛼 1 , . . . , 𝛼 𝑚 ), 𝛽 = (𝛽 1 , . . . , 𝛽 𝑚 ) and 𝛾 = (𝛾 1 , . . . , 𝛾 𝑚 ).

Protocol Π 𝑀 :

(1) P: samples random polynomials 𝑓 (𝑋 ), 𝑔(𝑋 ) in Z 𝑝 of degree at most 𝑚 that define a secret sharing over 𝛼 and 𝛽 by fixing 𝑓 (𝑖) = 𝛼 𝑖 and 𝑔(𝑖) = 𝛽 𝑖 for all 𝑖 ∈ {1, . . . , 𝑚} and sampling 𝑓 (0), 𝑔(0) ← 𝑅 Z 𝑝 . (2) P: computes the product polynomial ℎ(𝑋 ) = 𝑓 (𝑋 )𝑔(𝑋 )

which has degree at most 2𝑚. (3) P sends to V: a vector commitment of x = (𝛼, 𝛽, 𝑓 (0), 𝑔(0), ℎ(0), . . . , ℎ(2𝑚)).

Note that 𝛾 = (ℎ(1), . . . , ℎ(𝑛)). (4) V sends to P: 𝑐 ← 𝑅 Z 𝑝 \ {0, . . . , 𝑚} (5) P and V run Π 𝑁 to prove that 𝑓 (𝑐), 𝑔(𝑐), ℎ(𝑐) open to some points 𝑢, 𝑣 and 𝑤 respectively. This is possible by Lagrange interpolation, where by having sufficient points of 𝑓 ,𝑔 and ℎ, which are in the commitment of x, they can be evaluated its domain by applying an affine form to x (6) V: if 𝑢𝑣 = 𝑤 then accept else reject As before, completeness is straightforward. Zero knowledge follows from fact that 𝑓 , 𝑔 and ℎ are random polynomials and their evaluations do not reveal information and that Π 𝑁 is zero knowledge. If the multiplicative relations does not hold in all triplets, the probability that 𝑢𝑣 = 𝑤 is negligible. From that and the soundness of Π 𝑁 , soundness is obtained. Now, let 𝐶 : Z 𝑘 𝑝 → Z 𝑠 𝑝 be a circuit, i.e. a function that only contains addition and multiplication gates in Z 𝑝 . For a vector commitment 𝑃, we adapt ideas from Π 𝑀 to construct a proof that P knows a opening x ∈ Z 𝑘 𝑝 of 𝑃 such that 𝐶 (x) = 0. Suppose that 𝐶 has 𝑚 multiplication gates. We enumerate the multiplication gates

We note that the model of [START_REF] Ishai | Secure Multi-Party Computation with Identifiable Abort[END_REF] is defined for more general types of composition. Nevertheless, it is compatible with the definition described above.

Assumptions on adversaries. We can see A as a deterministic algorithm with a special input which is a random tape of uniformly distributed bits. In the ideal model, we can also rewind A to a previous state in execution, where the random tape also rewinds.

B.2 Compressed Σ-protocols as Ideal Functionalities

We will use compressed Σ-protocols implemented with the Fiat-Shamir heuristic which are proven secure in the random oracle model [START_REF] Pointcheval | Security Proofs for Signature Schemes[END_REF]. They have been proven secure against (by definition) malicious provers and there is no interaction with malicious verifiers. Therefore we can consider them as secure and abstract them as hybrid functionalities. In particular, when we write 𝑃 → F 𝑅 Σ :

(𝑥; 𝑤); F 𝑅 Σ → O : [𝑏, 𝑥 ′ ],
we mean that F 𝑅 Σ gets as input from party 𝑃 the public data 𝑥 and secret witness 𝑤, gets from all other relevant parties as input the empty string, and returns to all parties in O the same pair [𝑏, 𝑥 ′ ] where 𝑥 ′ is the data provided as input by 𝑃 and 𝑏 is 1 if (𝑥; 𝑤) ∈ 𝑅 (the proof succeeds) and 0 otherwise.

B.3 Proof of Protocol 1

Let 𝑈 be the random variable uniformly distributed over the interval [0, 𝐿) for 𝐿 ≤ 𝑝. We consider the ideal functionality F 𝑝1 ({} . . . {}) = (𝑈 . . . 𝑈 ), i.e., F 𝑝1 takes as input from each of the 𝑛 parties an empty string and outputs to every party the same uniformly distributed 𝑈 . (1) For 𝑖 = 1 . . . 𝑛 :

• 𝑃 𝑖 : choose 𝑥 𝑖 ∈ [0, 𝐿), 𝑟 𝑖 ∈ Z 𝑝 at random • 𝑃 𝑖 : compute the commitment 𝐶 𝑖 = 𝐶𝑜𝑚(𝑥 𝑖 , 𝑟 𝑖 ) • 𝑃 𝑖 : broadcast 𝐶 𝑖 • 𝑃 𝑖 → F 𝑅 1 Σ : (𝐶 𝑖 ; 𝑥 𝑖 , 𝑟 𝑖 ) • F 𝑅 1 Σ : broadcast [𝑏 𝑖 , 𝐶 ′ 𝑖 ] • 𝑃 -𝑖 : if 𝑏 𝑖 ≠ 1 or 𝐶 ′
𝑖 ≠ 𝐶 𝑖 , detect 𝑃 𝑖 as a cheater and abort (2) For 𝑖 = 1 . . . 𝑛:

• 𝑃 𝑖 → F 𝑅 2 Σ : (𝐶 𝑖 , 𝑥 𝑖 ; 𝑟 𝑖 ) • F 𝑅 2 Σ : broadcast [𝑏 ′ 𝑖 , 𝐶 ′′ 𝑖 , 𝑥 ′ 𝑖 ] • 𝑃 -𝑖 : if 𝑥 𝑖 ∉ [0, 𝐿), 𝑏 ′
𝑖 ≠ 1 or 𝐶 ′′ 𝑖 ≠ 𝐶 𝑖 , detect 𝑃 𝑖 as a cheater and abort (3) For 𝑖 = 1 . . . 𝑛:

• output 𝑛 𝑖=1 𝑥 ′ 𝑖 mod 𝐿. We state the security of protocol Π 𝑝1 in the theorem below.

Theorem 5 (Security of Π 𝑝1 ). Let 𝐶𝑜𝑚 be a computationally binding and perfectly hiding commitment scheme and let F 𝑅 1 Σ and F 𝑅 2 Σ be secure multiparty functionalities of computationally sound zero-knowledge proofs of relations 𝑅 1 and 𝑅 2 respectively. Then, Protocol Π 𝑝1 securely computes F 𝑝1 in the (F 𝑅 1 Σ , F 𝑅 2 Σ )-hybrid model with identifiable abort if at least one party is honest.

Proof. It is clear that Π 𝑝1 securely computes F 𝑝1 in the honestbut-curious setting.

Below, we will use A to denote a non-uniform probabilistic polynomial-time (PPT) adversary that controls covert parties.

In Figure 4, we define four very similar algorithms S 𝑣 , 𝑣 ∈ {0, 1, 2, 3} where S 0 is a simulator and for which we will prove that their ideal execution output is indistinguishable from the hybrid execution output. Each simulator S 𝑣 will internally run a copy of A which we will denote by A 𝑣 . Without loss of generality, we can assume that at the points where all parties send messages, the messages of the honest parties arrive first, as everything an adversary can infer from the messages of a subset of honest parties it can also infer from the messages of all honest parties.

To see that the simulation of S 0 is indistinguishable from the

(F 𝑅 1 Σ , F 𝑅 2 Σ
)-hybrid model with adversary A, we define our simulators such that • The outputs of S 0 and S 1 are identically distributed, because their only difference is the moment on which 𝑧 is chosen uniformly at random (and hence independently from other variables). • The outputs of S 1 and S 2 are identically distributed, the only difference is that S 1 first draws 𝑧 in line 28 and then computes 𝑥 𝑖 ′ from it, while S 2 first draws 𝑥 𝑖 ′ and then computes 𝑧 from it. • The outputs of S 2 and S 3 are indistinguishable. All inputs to A are the same, except for a commitment 𝐶𝑜𝑚(0, 𝑟 𝑖 ′ ) versus a commitment 𝐶𝑜𝑚(𝑥 𝑖 ′ , 𝑟 𝑖 ′ ). As the commitment scheme is hiding and 𝑟 𝑖 ′ is chosen independetly, the distributions of these commitments are indistinguishable and for any A 3 getting input 𝐶𝑜𝑚(𝑥 𝑖 ′ , 𝑟 𝑖 ′ ) there is an A 2 producing a computationally indistinguishable output. • The output of S 3 is identically distributed as the output of Π 𝑝1 in the hybrid model.

□

Vectorized version. We can now consider the ideal functionality

F (𝑘) 𝑝1 ({} . . . {}) = ((𝑈 1 . . . 𝑈 𝑘 ) . . . (𝑈 1 . . . 𝑈 𝑘 )), i.e., F (𝑘)
𝑝1 takes as input from each of the 𝑛 parties an empty string and outputs to every party the same vector (𝑈 1 . . . 𝑈 𝑘 ) where every 𝑈 𝑖 is uniformly distributed in [0, 𝐿) independently for 𝑖 = 1 . . . 𝑘. We can then similarly construct a protocol Π (𝑘) 𝑝1 that draws a vector 𝑧 uniformly distributed in [0, 𝐿) 𝑘 .

In this protocol we will use a pseudo-random number generator as we defined in 2.6. We use a similar but equivalent definition which is more convenient in our proof, in particular, for some polynomial 𝑝, this is a function 𝐺 : {0, 1} 𝑞 → [0, 𝐿) 𝑝 (𝑞) such that for any if 𝑣 = 0 then 3: F 𝑝1 → S 0 : 𝑧 (S 0 invokes trusted party delivering ideal functionality) We describe this protocol in the hybrid model using the ideal functionality F 𝑝1[0, 2 𝑞 ) , which is a variant on the F 𝑝1 functionality we introduced above where 𝐿 is set to 2 𝑞 . The protocol Π (𝑘) 𝑝1 is described below: 𝑝1 in the F 𝑝1[0, 2 𝑞 ) -hybrid model with identifiable abort if at least one party is honest.

Proof. It follows from the definition of random number generator that the output of the protocol is indistinguishable from the output of the ideal functionality when all parties are honest-butcurious.

The protocol consists of first a call to a secure sub-protocol and then a public computation which each agent can do for himself without any interaction. It is hence easy to see that the protocol is secure. □

B.4 Proof of Protocol 2

Now we prove the security of Protocol 2, which performs a private uniform draw. Without loss of generality, we assume that the drawn sample should be private to 𝑃 1 . The ideal functionality F 𝑝2 : ({0, 1} * ) 𝑛 → ({0, 1} * ) 𝑛 is defined as F 𝑝2 ({} . . . {}) = ((𝑧, 𝑟 𝑧 ), 𝐶 𝑧 , . . . , 𝐶 𝑧 )

where 𝐶 𝑧 = 𝐶𝑜𝑚(𝑧, 𝑟 𝑧 ), 𝑧 is uniformly randomly distributed in [0, 𝐿) 𝑘 and 𝑟 𝑧 is uniformly randomly distributed in Z 𝑝 (as a consequence of the distributions of 𝑧 and 𝑟 𝑧 , 𝐶 𝑧 is uniformly distributed over G). The pair (𝑧, 𝑟 𝑧 ) is private to 𝑃 1 while 𝐶 𝑧 is known by all parties. We will describe a detailed version of Protocol 2 in the hybrid model. Our hybrid functionalities will be F 𝑝1 and F (𝑘)

𝑝1 , which correspond to Protocol 1, and F 𝑅 𝑚 Σ , which, for some modulus 𝐿 ≤ 𝑝 is the ideal functionality of a zero knowledge proof for relation Such proof can be performed by applying the techiques decribed in Section 6.1. In Figure 5, we define the protocol Π 𝑝2 which describes Protocol 2 in more detail. Theorem 7. Let 𝐶𝑜𝑚 be a computationally binding and perfectly hiding commitment scheme and let F 𝑅 𝑚 Σ be a secure multiparty functionality of a computationally sound zero-knowledge proof of relation 𝑅 𝑚 . Let F (𝑘) 𝑝1 and F 𝑝1[0, 2 𝑞 ) be secure multiparty functionalities as defined above. Then, protocol Π 𝑝2 securely computes F 𝑝2 in the (F (𝑘) 𝑝1 , F 𝑝1Z 𝑝 , F 𝑅 𝑚 Σ )-hybrid model with identifiable abort if at least one party is honest.

Proof. First note that, except for 𝑃 1 , the other parties are only supposed to perform ideal calls and do not interact with each other. We will consider first the most difficult case in which 𝑃 1 is among the corrupted parties controlled by A. In Figure 6, we define our adversary S that simulates the output of A in the ideal model.

We show that the ideal and hybrid execution outputs are indistinguishable. We first start by analyzing the view of A in the hybrid protocol and when interacting with S.

• Since A has not seen any other message, the first commitment 𝐶 𝑥 of A is the same in both hybrid and ideal executions • 𝑦 and 𝑟 𝑦 have the same distribution in the hybrid and ideal model as they are part of an ideal call. Therefore, also the 𝐶 𝑧 broadcasted by A follows the same distribution in the hybrid and ideal model. 𝑝1 draws publicly a random number from [0, 𝐿) 𝑘 . • F 𝑝1Z 𝑝 is a variant of F 𝑝1 that draws a random number from Z 𝑝 rather than from [0, 𝐿).

• F 𝑅 𝑚 Σ performs a zero-knowledge proof for the relation 𝑅 𝑚 defined above 4: Protocol: transformation. For private draws, this transformation is a noninteractive compressed Σ-protocol as described in Appendix B.2. For each technique, we explain the appropriate transformation in Sections 7.1, 8.1, 8.2, 8.3 and 8.4. This procedure is secure as it is essentially a secure drawing of a uniformly distributed random number as discussed in the previous sections followed by a private but verifiable single-party post-processing.

𝐶

  𝑇 𝑟 (𝜈; ⟨𝜃 ⟩, ⟨𝑐⟩, ⟨𝑠⟩, I 𝑇 ) 𝐶 𝐶𝑟𝑑1 (𝜈; ⟨𝜃 ⟩, ⟨1/𝐾 1,𝜈 ⟩, 0, ⟨𝑠⟩, ⟨𝑐⟩, I 𝑇 ) to compute 𝑠 = sin(𝜃 ) and 𝑐 = cos(𝜃 ). For the logarithm, letI 𝐿 = (⟨𝑋 𝜈 ⟩, ⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I, s 𝑌 ).Then, 𝐶 𝐿𝑜𝑔 (𝜓, 𝜈; ⟨𝑥⟩, ⟨𝑙⟩, I 𝐿 ) 𝐶 𝐶𝑟𝑑2 (𝜓, 𝜈; ⟨𝑥⟩ + ⟨1⟩, ⟨𝑥⟩ -⟨1⟩, I 𝐿 ) ⟨𝑙⟩ -2⟨𝜃 𝜈 ⟩ proves 𝑙 = ln(𝑥). For the square root let I 𝑆 = (⟨𝑌 𝜈 ⟩, ⟨𝜃 𝜈 ⟩, I, s 𝑌 ), then 𝐶 𝑆𝑞𝑟𝑡 (𝜓, 𝜈; ⟨𝑥⟩, ⟨𝑠⟩, I 𝑆 ) 𝐶 𝐶𝑟𝑑2 (𝜓, 𝜈; ⟨𝑥⟩ + ⟨1/4𝐾 2 2,𝜈+1 ⟩, ⟨𝑥⟩ -⟨1/4𝐾 2 2,𝜈+1 ⟩, ⟨𝑠⟩, I 𝑆 )

Protocol 8 .

 8 Let 𝑁 /12 be a power of 4. For 𝑖 = 0 . . . 𝑙 -1 and 𝑗 = 1 . . . 𝑁 , draw a random bit sharing ⟦𝑥 (𝑖) 𝑗 ⟧. This yields 𝑁 random numbers {𝑥 𝑗 } 𝑁 𝑗=1 in the interval [0, 2 𝑙 ). For 𝑗 ∈ [𝑁 ] and 𝑖 = 𝑙 . . . 𝑙 + log 2 𝑁 , set 𝑥 (𝑖)

Figure 1 :

 1 Figure 1: (Comm. costs) Required Group Elements for one sample against the MSE for BM, PolM, InvM and CLT approaches.

Figure 2 :

 2 Figure 2: (Comp. costs) Required group exponentiations for one sample against the MSE for BM, PolM, InvM and CLT approaches. Costs in the left side plots are in logarithmic scale. The right side plots are zooms of their left plots, in linear scale and with a detailed view on the most efficient methods.

Figure 3 :

 3 Figure 3: (Comparison w. classic Σ-protocols) Required Group Elements for one sample against the MSE using compressed and classic Σ-protocols for PolM (left) and CLT (right).

Protocol.

  The protocol Π 𝑝1 is explained below. Protocol Π 𝑝1 : Security Parameter: 𝜆 Hybrid Functionality sub-protocols: Functionalities F 𝑅 1 Σ and F 𝑅 2 Σ are zero knowledge proofs of respectively • 𝑅 1 = {(𝐶; 𝑥, 𝑟 ) : 𝐶 = 𝐶𝑜𝑚(𝑥, 𝑟 )} • 𝑅 2 = {(𝐶, 𝑥; 𝑟 ) : 𝐶 = 𝐶𝑜𝑚(𝑥, 𝑟 )} (only 𝑟 is secret), Protocol:

Figure 4 :

 4 Figure 4: Simulators S 𝑣 , for 𝑣 ∈ {0, 1, 2, 3}.

2 :

 2 Security parameter: 𝜆 3: Hybrid functionality sub-protocols:• F 𝑝1[0, 2 𝑞 ) : draws a single public random number in [0, 2 𝑞 ).

4: Protocol: 5 : 6 : 8 :

 568 All parties collaboratively perform:𝑧 ′ = F 𝑝1[0, 2 𝑞 ) ({} . . . {}) 7:For 𝑃 𝑖 ∈ P:𝑃 𝑖 : Output 𝑧 = (𝑧 1 . . . 𝑧 𝑘 ) with 𝑧 𝑗 containing bits ( 𝑗 -1) ⌈log(𝐿)⌉ + 1 . . . 𝑗 ⌈log(𝐿)⌉ of 𝐺 (𝑧 ′ ) for 𝑗 = 1 . . . 𝑘 Theorem 6 (Security of Π (𝑘) 𝑝1 ). Let F 𝑝1[0, 2 𝑞) be a secure multiparty functionality and G be a PRG as defined above. Then, Protocol Π (𝑘) 𝑝1 securely computes F (𝑘)

𝑅

  𝑚 = {(𝑦 ∈ [0, 𝐿) 𝑘 , 𝑟 𝑦 ∈ Z 𝑝 , 𝐶 𝑥 ∈ G, 𝐶 𝑧 ∈ G; 𝑥 ∈ [0, 𝐿) 𝑘 , 𝑟 𝑥 ∈ Z 𝑝 , 𝑧 ∈ [0, 𝐿) 𝑘 , 𝑟 𝑧 ∈ Z 𝑝 ) : 𝐶 𝑥 = 𝐶𝑜𝑚(𝑥, 𝑟 𝑥 ) ∧ 𝐶 𝑧 = 𝐶𝑜𝑚(𝑧, 𝑟 𝑧 ) ∧ 𝑥 ∈ [0, 𝐿) ∧ 𝑧 = 𝑥 + 𝑦 mod 𝐿 ∧ 𝑟 𝑧 = 𝑟 𝑥 + 𝑟 𝑦 mod Z 𝑝 }.

Figure 5 :

 5 Figure 5: Protocol Π 𝑝2 , a detailed description of Protocol 2.

Figure 6 :

 6 Figure 6: Simulator of advesary A in Protocol Π 𝑝2 , for the case when 𝑃 1 is corrupted.

  1} 𝑝 (𝑘) → {0, 1} there holds |𝑃 𝑥← 𝑅 {0,1} 𝑘 (𝐴(𝐺 (𝑥)) = 1)-𝑃 𝑥← 𝑅 {0,1} 𝑝 (𝑘 ) (𝐴(𝑥) = 1)| ≤ 𝜇 (𝑘) for some function 𝜇 negligible in 𝑘. In other words, a PRG is a function which takes a string 𝑥 as input and outputs a longer string 𝐺 (𝑥) which cannot be distinguished from a random sequence by a polynomial time algorithm.

A (secure) pseudo-random number generator (PRG) is a function 𝐺 : {0, 1} 𝑘 → {0, 1} 𝑝 (𝑘) for some polynomial 𝑝 with 𝑝 (𝑘) > 𝑘 such that for any randomized polynomial time algorithm 𝐴 : {0,

  • public draw if after running 𝜋 the value of 𝑥 is published. • private draw if after running 𝜋 exactly one party knows 𝑥, but the other parties have no information on 𝑥 next to the prior distribution D. • hidden draw if after running 𝜋 the parties have received an additive secret share (𝑥 1 , . . . , 𝑥 𝑛 ) for 𝑥, but still no party has any information about 𝑥 next to the prior distribution D.

  we describe the main circuit. For I 𝐷 = (⟨𝑥 ′ ⟩, ⟨𝑠 ′ ⟩, 𝑖 𝑒 , 𝑒 ′ , 𝑓 ′ ) and I 𝑆𝑔 = (𝑛 𝑒 , s 𝑥 ′ , I 𝑆 , I 𝐷 , I 𝐷1 , I 𝐷2 ) vectors of intermediate values, we prove 𝑠 =

	√
	𝑥 with
	𝐶

𝑆𝑞𝑟𝑡𝐺 (𝜓, 𝜈, 𝐵; ⟨𝑥⟩, ⟨𝑠⟩, I 𝑆𝑔 )

  𝜓, 𝜈; ⟨𝑈 1 ⟩, ⟨𝑙⟩, I 𝐿𝑔 ) 𝐶 𝑆𝑞𝑟𝑡𝐺 (𝜓, 𝜈, 2𝜓 ln(2); -2⟨𝑙⟩, ⟨𝜌⟩, I 𝑆𝑔 ) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; 2⟨𝜋⟩, ⟨𝑈 2 ⟩, ⟨𝑎 𝜋 ⟩, s 1 ) 𝐶 𝑇 𝑟𝐺 (𝜈; ⟨𝑎 𝜋 ⟩, ⟨𝑠⟩, ⟨𝑐⟩, I 𝑇𝑔 ) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝜌⟩, ⟨𝑐⟩, ⟨𝑋 ′ 1 ⟩, s 2 ) 𝐶 𝑃𝑟𝑜𝑑 (𝜓 ; ⟨𝜌⟩, ⟨𝑠⟩, ⟨𝑋 ′ 2 ⟩, s 3 ) Private values 𝑎 1 and 𝑎 2 and public challenges 𝑧 1 and 𝑧 2 are used in the modular proofs of circuit 𝐶 𝑀𝑜𝑑 to generate 𝑈 1 and 𝑈 2 with Protocol 2. To obtain a sample with standard deviation different than 1, the resulting samples can be scaled with an extra 𝐶 𝑃𝑟𝑜𝑑 circuit. Different mean requires an extra addition gate.

	               	.

  is an optimization of Box-Müller that avoids the computation of sine and cosine by the use of rejection sampling. It samples two uniform values 𝑉 1 and 𝑉 2 in the (-1, 1) interval, and keeps the result only if 0 < 𝑉 2 1 + 𝑉 2 2 ≤ 1. Otherwise 𝑉 1 and 𝑉 2 are re-sampled. For non rejected 𝑉 1 and 𝑉 2 it computes In the private sampling, if 𝑉 1 and 𝑉 2 are rejected, the prover can just reveal them and start new uniform draws until acceptance, when it proves the correctness of accepting pairs. As in Box Müller, parameters 𝜈 and 𝜓 define our elementary function approximations, and 𝑎 1 , 𝑎 2 , 𝑧 1 , 𝑧 2 are used to generate 𝑉 1 and 𝑉 2 in Protocol 2. Let I 𝑃𝑜𝑙 = (⟨𝑠⟩, I 𝑆𝑔 , ⟨𝑑⟩, ⟨𝛼⟩, ⟨𝑙⟩, I 𝐿𝑔 , s 6 , s 5 , s 4 , s 3 , s 2 , s 1 , ⟨𝛼⟩,

	𝛼 = 𝑉 2 1 + 𝑉 2 2 , 𝑌

1 = 𝑉 1 -2 ln(𝛼)/𝛼, 𝑎𝑛𝑑 𝑌 2 = 𝑉 2 -2 ln(𝛼)/𝛼 .

𝑌 1 and 𝑌 2 have distribution N (0, 1).

1 :

 1 Phase 1: choosing 𝑧 (see also phase 4)

2:

S

  𝑣 : 𝑖 ′ = max{𝑖 | 𝑃 𝑖 ∈ P \ P 𝑐𝑜𝑟 } for 𝑃 𝑖 ∈ (P \ P 𝑐𝑜𝑟 ) \ {𝑃 𝑖 ′ } do

	4:	end if
	5: Phase 2: S 𝑣 simulates honest parties:
	6:
	7:
	8:

S

  𝑣 : choose 𝑥 𝑖 randomly in [0, 𝐿) and 𝑟 𝑖 randomly in Z 𝑝

	9:

S

  𝑣 : 𝐶 𝑖 = 𝐶𝑜𝑚(𝑥 𝑖 , 𝑟 𝑖 ); [𝑏 𝑖 , 𝐶 ′ 𝑖 ] = F 𝑅 1 Σ (𝐶 𝑖 ; 𝑥 𝑖 , 𝑟 𝑖 ) 𝑣 → A 𝑣 : [𝑏 𝑖 , 𝐶 ′ 𝑖 ] (as if it is sent by 𝑃 𝑖 ) 𝑟 𝑖 ′ randomly; 𝐶 𝑖 ′ = 𝐶𝑜𝑚(0, 𝑟 𝑖 ′ ); [𝑏 𝑖 ′ , 𝐶 ′ 𝑖 ′ ] = [1, 𝐶 𝑖 ′ ] 𝑥 𝑖 ′ and 𝑟 𝑖 ′ randomly; 𝐶 𝑖 ′ = 𝐶𝑜𝑚(𝑥 𝑖 ′ ; 𝑟 𝑖 ′ ); [𝑏 𝑖 ′ , 𝐶 ′ 𝑖 ′ ] = F 𝑅 1 Σ (𝐶 𝑖 ′ ; 𝑥 𝑖 ′ , 𝑟 𝑖 ′ ) 𝐶 ′ 𝑖 ′ ] (as if it is the answer of F 𝑅 1 Σ (𝐶 𝑖 ′ ; 𝑥 𝑖 ′ , 𝑟 𝑖 ′ ))𝑅 1 Σ : (𝐶 𝑖 ; 𝑥 𝑖 , 𝑟 𝑖 ); S 𝑣 records 𝐶 𝑖 , 𝑥 𝑖 and 𝑟 𝑖 . 𝑥 𝑖 ′ = 𝑧 -𝑖≠𝑖 ′ 𝑥 𝑖 mod 𝐿 𝑥 𝑖 ′ uniformly at random and set 𝑧 = 𝑖 ∈P 𝑥 𝑖 mod 𝐿 𝑖 ≠ 𝑥 𝑖 or 𝐶 ′′ 𝑖 ≠ 𝐶 𝑖 or 𝑏 ′ 𝑖 = 0 detect 𝑃 𝑖 as cheater

	10: S 11: end for
	12:	if 𝑣 ∈ {0, 1, 2} then
	13: draw 14: else
	15: draw 16: end if
	17:
	22: → S 24: F 𝑅 1 Σ end for
	25: Phase 4: choosing 𝑧 and 𝑥 𝑖 ′
	26:	if 𝑣 ∈ {0, 1} then
	27:	if 𝑣 = 1 then
	28:	S 1 chooses 𝑧 uniformly at random
	29:	end if
	30:
	31:	else (i.e., if 𝑣 ∈ {2, 3})
	32: draw 33: end if
	34: Phase 5:
	35:	for 𝑃 𝑖 ∈ P \ P 𝑐𝑜𝑟 do
	36: S 38: end for
	39: Phase 6: S 𝑣 continues simulation of A 𝑣
	40:	for 𝑃 𝑖 ∈ P 𝑐𝑜𝑟 do
	41: 42: 43:	A 𝑣 → F 𝑅2 Σ F 𝑅2 → S 𝑣 : [𝑏 ′ : (𝐶 ′′ 𝑖 , 𝑥 ′ 𝑖 ; 𝑟 ′ 𝑖 ); S 𝑣 records 𝐶 ′′ 𝑖 , 𝑥 ′ 𝑖 and 𝑟 ′ 𝑖 𝑖 , 𝐶 ′′ 𝑖 , 𝑥 ′ 𝑖 ] Σ If 𝑥 ′
	44:	end for
	45: Phase 7: Output
	46:

S 𝑣 → A 𝑣 : [1, 18: Phase 3: S 𝑣 simulates A 𝑣 : 19: for 𝑖 ∈ P 𝑐𝑜𝑟 do 20: A 𝑣 → S 𝑣 : 𝐶 𝑖 21: A 𝑣 → F 𝑣 : [𝑏 𝑖 , 𝐶 ′ 𝑖 ] (as if sent to members of P \ P 𝑐𝑜𝑟 ) 23: If 𝐶 ′ 𝑖 ≠ 𝐶 𝑖 or 𝐶 𝑖 ≠ 𝐶𝑜𝑚(𝑥 𝑖 , 𝑟 𝑖 ) detect 𝑃 𝑖 as cheater 𝑣 : set 𝑥 ′ 𝑖 = 𝑥 𝑖 ; 𝐶 ′′ 𝑖 = 𝐶 𝑖 ; 𝑏 ′ 𝑖 = 1 37: S 𝑣 → A 𝑣 : [𝑏 ′ 𝑖 , 𝐶 ′′ 𝑖 , 𝑥 ′ 𝑖 ] (as if it is sent by F 𝑅 2 Σ in answer to (𝑥 𝑖 , 𝐶 𝑖 ; 𝑟 𝑖 ))

A

  𝑣 → S 𝑣 : 𝑧 ′ (the output of A 𝑣 )

	47:	output 𝑧 ′

  • if A cheats in 𝐶 𝑧 (i.e., 𝐶 𝑧 is not a commitment according to relation 𝑅 𝑚 ), it gets caught both in the hybrid and ideal executions • before rewinding A, S recovers 𝑥 and 𝑟 𝑥 such that 𝐶 𝑥 = 𝐶𝑜𝑚(𝑥, 𝑟 𝑥 ) with overwhelming probability (this is because A cannot fake the zero knowledge proof in F 𝑅 𝑚 Σ except with negligible probability) • in the ideal world, S sets 𝑦 and 𝑟 𝑦 such that 𝑧 = 𝑥 + 𝑦 mod 𝐿 and 𝑟 𝑧 = 𝑟 𝑥 + 𝑟 𝑦 mod 𝑝, where 𝑥 and 𝑟 𝑥 are chosen by A, 𝑧 and 𝑦 are uniformly randomly distributed in [0, 𝐿) 𝑘 and 𝑟 and 𝑟 𝑦 are uniformly randomly distributed in Z 𝑝 . This is the same distribution as in the hybrid world. • now A broadcast 𝐶 ′′ 𝑧 and either is detected as cheater or 𝐶 ′′ 𝑧 = 𝐶𝑜𝑚(𝑧, 𝑟 𝑧 ) with overwhelming probability both in the hybrid or ideal executions Up to this point, from the view of A the transcripts simulated by S in the ideal execution and the transcript in the hybrid execution are indistinguishable. Since A runs in polynomial time, his output must be indistinguishable in both executions. Now we analyze the case where 𝑃 1 is among then honest parties. Particularly, consider the worst case where all other parties are malicious and 𝑃 1 is the only honest party. This case is still easy since the only interaction of malicious users is to perform ideal calls to F 𝑝1 , F 𝑝1Z 𝑝 and F 𝑅 𝑚 Σ . The only role of S is to send inputs that might be consistent according to the behavior of A. Even if all the verifiers are malicious, the honest party can still detect them. □ B.5 Non-uniform Public and Private Draws Public and Private draws from many distributions such as Gaussians or Laplace distributions can be performed by first drawing uniformly distributed samples with either Protocol 1 for public draws or Protocol 2 for private draws, then applying a non-interactive 1: Protocol Π 𝑝2 (to generate single private sample): 2: Security Parameter: 𝜆 3: Hybrid Functionalitiy sub-protocols:

	• F	(𝑘)
		(𝑘)

5 :

 5 𝑃 1 : 6: draw 𝑥 ∈ [0, 𝐿) 𝑘 and 𝑟 𝑥 ∈ Z 𝑝 uniformly at random 7: compute 𝐶 𝑥 = 𝐶𝑜𝑚(𝑥, 𝑟 𝑥 ) 𝑝1 to obtain a public 𝑦 uniformly distributed over [0, 𝐿) 𝑘 11: call F 𝑝1Z 𝑝 to obtain a public 𝑟 𝑦 uniformly distributed over Z 𝑝 12: 𝑃 1 : 13: Compute 𝑧 = 𝑥 + 𝑦 mod 𝐿 and 𝑟 𝑧 = 𝑟 𝑥 + 𝑟 𝑦 mod 𝑝 14: Compute 𝐶 𝑧 = 𝐶𝑜𝑚(𝑧, 𝑟 𝑧 ) 15:broadcast 𝐶 𝑧 16: Parties perform an ideal call to F 𝑅 𝑚 Σ :𝑃 1 → F 𝑅 𝑚 Σ : (𝑦, 𝑟 𝑦 , 𝐶 𝑥 , 𝐶 𝑧 ; 𝑥, 𝑟 𝑥 , 𝑧, 𝑟 𝑧 ) 𝑃 -1 : if 𝑏 = 0 ∨ 𝑟 𝑢 ≠ 𝑟 ′ 𝑦 ∨ 𝑦 ≠ 𝑦 ′ ∨ 𝐶 𝑥 ≠ 𝐶 ′ 𝑥 ∨ 𝐶 𝑍 ≠ 𝐶 ′ 𝑧 ,detect 𝑃 1 as a cheater and abort, otherwise continue the execution 20: 𝑃 1 : output (𝑧, 𝑟 𝑧 ) 21: 𝑃 -1 : output 𝐶 𝑧

	8:	broadcast 𝐶 𝑥
	9: All parties in P collaboratively:
	10:	call F	(𝑘)
	17:
	18:	F 𝑅 𝑚

Σ : broadcast [𝑏, 𝑦 ′ , 𝑟 ′ 𝑦 , 𝐶 ′ 𝑥 , 𝐶 ′ 𝑧 ]

19:

1 :

 1 S: internally run A until broadcast 𝐶 𝑥 (line 8 in Π 𝑝2 ) 2: A → S : 𝐶 𝑥 3: S: continue the run of A until after the ideal call to F 𝑝1 (line 10 in Π 𝑝2 ) 4: S: draw a random value 𝑦 ∈ [0, 𝐿) 𝑘 5: S → A : 𝑦 (as if it came from F S: continue the run of A until after the ideal call to F 𝑝1Z 𝑝 (line 11 in Π 𝑝2 ) 7: S: draw a random value 𝑟 𝑦 ∈ Z 𝑝 8: S → A : 𝑟 𝑦 (as if it came from F 𝑝1Z 𝑝 ) 9: A → S : 𝐶 𝑧 10: S: continue run of A:𝑃 1 → F 𝑅 𝑚 Σ : (𝑦 ′ , 𝑟 ′ 𝑦 , 𝐶 ′ 𝑥 , 𝐶 ′ 𝑧 , 𝑥 ′ , 𝑟 ′ 𝑥 , 𝑧 ′ , 𝑟 ′ 𝑧 ) 11: F 𝑅 𝑚 Σ : broadcast [𝑏, 𝑦 ′ , 𝑟 ′ 𝑦 , 𝐶 ′ 𝑥 , 𝐶 ′ 𝑧 ] 12: if 𝑏 = 0 ∨ 𝑦 ′ ≠ 𝑦 ∨ 𝑟 ′ 𝑦 ≠ 𝑟 𝑦 ∨ 𝐶 ′ 𝑥 ≠ 𝐶 𝑥 ∨ 𝐶 ′ 𝑧 ≠ 𝐶 𝑧 , detect𝑃 1 as a cheater 13: S: invoke trusted party computing F 𝑝2 14: F 𝑝2 returns ((𝑧, 𝑟 𝑧 ) ∈ [0, 𝐿) 𝑘 × Z 𝑝 , (𝐶 𝑧 , . . . , 𝐶 𝑧 ) ∈ G |P 𝑐𝑜𝑟 |-1 ) to S and (𝐶 𝑧 , . . . , 𝐶 𝑧 ) ∈ G |P\P 𝑐𝑜𝑟 | to the honest parties 15: S sets 𝑦 = 𝑧 -𝑥 mod 𝐿 and 𝑟 𝑦 = 𝑟 𝑧 -𝑟 𝑥 mod 𝑝 16: S rewinds A to before the invocation of F

	(𝑘)
	(𝑘) 𝑝1 )
	6: (𝑘)

𝑝1 17 :

 17 S continues the internal run of A, which performs ideal calls to F 𝑝1 and F 𝑝1Z 𝑝 . 18: S → A : 𝑦, 𝑟 𝑦 (as if they were sent by F 𝑝1 and F 𝑝1Z 𝑝 ) 19: A → S : 𝐶 ′′ 𝑧 ; if 𝐶 ′′ 𝑧 ≠ 𝐶 𝑧 , detect 𝑃 1 as a cheater 20: S continues to run A: 𝑃 1 → F 𝑅 𝑚 Σ : (𝑦 ′′ , 𝑟 ′′ 𝑦 , 𝐶 ′′ 𝑥 , 𝐶 ′′ 𝑧 , 𝑥 ′′ , 𝑟 ′′ 𝑥 , 𝑧 ′′ , 𝑟 ′′ 𝑧 ) 21:F 𝑅 𝑚 Σ : broadcast [𝑏 ′ , 𝑦 ′′ , 𝑟 ′′ 𝑦 , 𝐶 ′′ 𝑥 , 𝐶 ′′ 𝑧 ] 22: if 𝑏 ′ = 0 ∨ 𝑦 ′′ ≠ 𝑦 ∨ 𝑟 ′′ 𝑦 ≠ 𝑟 𝑦 ∨ 𝐶 ′′ 𝑥 ≠ 𝐶 𝑥 ∨ 𝐶 ′′ 𝑧 ≠ 𝐶 𝑧 ,detect 𝑃 1 as a cheater 23: output whatever A outputs

	(𝑘)
	(𝑘)

Proceedings on Privacy Enhancing Technologies YYYY(X) César Sabater, Florian Hahn, Andreas Peter, and Jan Ramon

Proceedings on Privacy Enhancing Technologies YYYY(X)

ACKNOWLEDGMENTS

We thank Christian Weinert for fruitful discussions. This project was partially supported by ANR project ANR-20-CE23-0013 'PMR', the 'Chair TIP' project funded by ANR and MEL, and the Horizon Europe TRUMPET project grant no. 101070038.

from 1 to 𝑚. For 𝑖 ∈ {1, . . . , 𝑚}, let 𝛼 𝑖 and 𝛽 𝑖 be inputs of the 𝑖th multiplication gate, and 𝛾 𝑖 its output. Let 𝛼,𝛽 and 𝛾 as defined in the multiplication protocol. It is not necessary to commit to 𝛼 and 𝛽 as a commitment of them can be obtained from affine forms on inputs (x, 𝛾) which are only dependent on 𝐶. Similarly, the output of 𝐶 can be computed from an affine map 𝜔 : Z 𝑘+2𝑚 𝑝 → Z 𝑠 𝑝 that takes as input (x, 𝛾). When committing to x and 𝛾, the prover only needs to prove that multiplication gates hold and that 𝜔 opens to 0. This can be done with amortized nullity checks. Let [a] be a hiding vector commitment of a i.e., [a] = g (a,𝑟 ) where 𝑟 ∈ Z 𝑝 is chosen at random.

Protocol Π 𝑐𝑠 (𝐶):

(1) P: Computes 𝑓 , 𝑔 and ℎ from 𝛼, 𝛽 as in Steps 1 and 2 of Π 𝑀 .

(2) P sends to V: [y], where y = (x, 𝑓 (0), 𝑔(0), ℎ(0), ℎ(1), . . . , ℎ(2𝑚)) ∈ Z 𝑘+2𝑚+3 𝑝 .

(3) V sends to P: 𝑐 ← 𝑅 Z 𝑝 \ {1, . . . , 𝑚}.

(4) P sends to V: 𝑧 1 = 𝑓 (𝑐), 𝑧 2 = 𝑓 (𝑐), 𝑧 3 = 𝑓 (𝑐).

(5) P and V run Π 𝑁 with input

where linear forms are obtained by Lagrange interpolation as in Step 5 of Π 𝑀 . (6) V: if 𝑧 1 𝑧 2 = 𝑧 3 then accept else reject Note that [y], additionally to 𝛼 and 𝛽, is an implicit commitment to 𝛾 = (ℎ(1), . . . , ℎ(𝑚)). Properties of completeness, zero knowledge and soundness, which can be found in Theorem 4 of [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF], follow from the same arguments as the multiplication protocol.

A.5 Range Proofs

A straightforward application of circuit proofs are range proofs. Namely, for a secret 𝑥 ∈ Z 𝑝 and an integer 𝑘 < log 2 (𝑝), that 𝑥 ∈ [0, 2 𝑘 ). For that you commit to the first 𝑘 bits 𝑏 1 , . . . , 𝑏 𝑘 of 𝑥. Then, for b = (𝑏 1 , . . . , 𝑏 𝑘 ), a circuit proof for circuit

𝑏 𝑖 implies the range constraint. Note that in 𝐶 𝑅𝑎 the output of the multiplication gates is 0. Therefore, in protocol Π 𝑐𝑠 , it is not necessary to include in y the elements ℎ(1), . . . , ℎ(𝑘), which reduces the proof cost.

A.6 Cost of Proofs

We now briefly summarize communication and computational cost of the proofs. As previously stated in the Appendix, 𝑘 is the number of inputs and 𝑚 of multiplication gates in circuits.

Theorems 3 and 4 of [START_REF] Attema | Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics[END_REF] give the communication costs for Π 𝑐 and Π 𝑐𝑠 respectively. As we use versions of the protocols transformed by the Fiat-Shamir heuristic, the verifier does not send any message. Therefore, the proof sizes are 2⌈log(𝑘 + 1)⌉ elements of G and 3 elements of Z 𝑝 for Π 𝑐 , and 2⌈log(𝑘 + 2𝑚 + 4)⌉ -1 elements of G and 6 elements of Z 𝑝 for Π 𝑐𝑠 .

For the computational cost, we count the amount of group exponentiations in G (GEX) as they dominate the work. In protocol Π 0 , P performs 𝑘 GEX to compute 𝐴, and V performs 𝑘 + 1 GEX, which corresponds to the verification of Step 5. In Π 1 , P performs 𝑘 + 2 GEX to compute 𝐴 and 𝐵, and V does 𝑘/2 + 4 GEX in the verification of Step 4. Π 𝑐 is a composition of one instance of Π 0 and 𝜇 = ⌈log 2 (𝑘)⌉ -2 instances of Π 1 . After the first Π 1 proof, 𝑘 halves at each instance of Π 1 . Additionally, P and V have to compute g ′ = g 𝑐 𝐿 + g 𝑅 after the first Π 1 to update parameters for each of following sub-protocols. V avoids each of the verification checks except for the last one, which requires a constant amount of GEX. Therefore, P performs 𝑘 + 2

In Π 𝑐𝑠 , P is required to compute a (hiding) commitment of y ∈ Z 𝑘+2𝑚+3 𝑝 , which costs 𝑙 = 𝑘 + 2𝑚 + 4 GEX. Then P and V engage in Π 𝑁 for an affine form of 𝑙 inputs. The final costs for Π 𝑐𝑠 are then 5𝑘 + 8𝑚 + 2⌈log 2 (𝑘 + 2𝑚 + 4)⌉ + 6 GEX for P and 𝑘 + 2𝑚 + 2⌈log 2 (𝑘 + 2𝑚 + 4)⌉ -1 GEX for V. For a proof of membership to the range [0, 2 𝑘 ), as discussed in Appendix A.5, ℎ(1), . . . , ℎ(𝑘) are not included in y which then has 2𝑘 + 4 elements. The costs are of 9𝑘 + 2⌈log 2 (2𝑘 + 5)⌉ + 11 GEX for P, and 2𝑘 + 2⌈log 2 (2𝑘 + 5)⌉ GEX for V.

We apply the same optimization done for range proofs to all of our circuits. That is, multiplication gates that are expected to be equal to 0 are not included in y. Therefore, for circuits with 𝑘 inputs, 𝑚 multiplication gates, and 𝑚 0 multiplication gates that will be equal to 0,

B SECURITY OF OUR PROTOCOLS

In this section, we prove the security of the protocols presented in the main paper. In the sequel, we will often restate in more detail and more formally the protocols. We consider a set of 𝑛 parties P = {𝑃 1 . . . 𝑃 𝑛 }. We will denote by 𝑃 -𝑖 the set of all parties except 𝑖, i.e., 𝑃 -𝑖 = P \ {𝑃 𝑖 }. We assume that a subset of parties P 𝑐𝑜𝑟 ⊂ P is corrupted and controlled by an adversary A. The set P 𝑐𝑜𝑟 of corrupted parties is static, i.e. does not change after the beginning of the execution.

For the description of our protocols, we will denote the fact that a party 𝐴 sends a message 𝑀 to a party 𝐵 by "𝐴 → 𝐵: 𝑀". Recall that we use a bulletin board for communication. Among others, this means that when a protocol contains a broadcast instruction a single message is sent from one party to all others, in practice by sending it from that party to the bulletin board, which forwards it to all other agents. We will also use hiding vector Pedersen commitments defined in Section 2.2. Recall the finite groups Z 𝑝 and G defined therein. For any integer 𝑘 > 0, we will denote by 𝐶𝑜𝑚(x; 𝑟 ) ∈ G the commitment of the 𝑘-dimension vector x ∈ Z 𝑘 𝑝 with randomness 𝑟 ∈ Z 𝑝 .

We describe our security framework in Appendix B.1. In Appendix B.2, we describe our model of compressed Σ-protocols in our security analysis. In appendices B.3 and B.4 we prove the security of Protocols 1 and 2 respectively. We conclude by discussing the security of our protocols for public and private draws from some other distributions in Appendix B.5.

B.1 Security Definitions

We prove security in the simulation paradigm, using the model of malicious security with identifiable abort [START_REF] Ishai | Secure Multi-Party Computation with Identifiable Abort[END_REF] in the stand-alone setting [START_REF] Goldreich | Foundations of cryptography: volume 2, basic applications[END_REF]. Therefore, we assume parties are able to detect malicious actions and can in such cases abort the protocol. Deterrence measures may be in place to discourage parties from being detected as malicious. In fact, unless parties stop participating our protocols either complete successfully or abort while detecting that a specific party is a cheater.

We start by introducing the key concepts of multiparty computation under the model of security with identifiable abort in the stand-alone setting (see [33, App. B of the full version]). A multiparty computation between our 𝑛 parties in P is a protocol that computes a stochastic process F : ({0, 1} * ) 𝑛 → ({0, 1} * ) 𝑛 , which is also called an ideal functionality, where for all 𝑖 ∈ {1, . . . , 𝑛}, the 𝑖th component of the input and output of F maps respectively to the private input and output of party 𝑃 𝑖 .

In the simulation paradigm, a multiparty protocol securely computes an ideal functionality in the presence of malicious adversaries if any possible malicious behavior in the protocol caused by colluding malicious parties is not more harmful than what such party can cause in the ideal model as defined below.

Ideal model. In this model, it is assumed that there exists a trusted party that computes F. A malicious adversary S controls a set of corrupted parties P 𝑐𝑜𝑟 . The ideal execution comprises 7 phases and goes as follows:

(1) Inputs: Each party 𝑃 𝑖 receives a private input 𝑢 𝑖 . Additionally, S has an auxiliary input 𝑢 * which represents the extra knowledge other than its regular input. (2) Send inputs to the trusted party: All honest parties send their input to the trusted party, while parties controlled by S might deviate and send what S wishes. (3) Early abort or corrupted input: S can send abort 𝑖 instead of a valid input, which means that some corrupted party 𝑃 𝑖 performed an early abortion or sent a corrupted input. In that case, the trusted party sends abort 𝑖 (choosing the index 𝑖 deterministically if many parties aborted or sent a corrupted input) to all honest parties and halts. (4) Detect cheating parties: During the execution, S can send abort 𝑖 to the trusted party, which means that a corrupted party 𝑃 𝑖 attempted to cheat. In that case, the trusted party sends abort 𝑖 to all parties (i.e. the attempt of cheating is detected). ( 5) Trusted party answers the adversary: If no abort 𝑖 is sent, then the trusted party sends to S the outputs of F of the corrupted parties. After receiving them, S can send abort 𝑖 to the trusted party or instruct it to continue. (6) Trusted party answers the honest parties: If S instructed the trusted party to continue, then the latter sends their outputs of F to the honest parties. [START_REF] Benarroch | Zero-Knowledge Proofs for Set Membership: Efficient, Succinct, Modular[END_REF] Output: The honest parties always output what the trusted party sent to them. S outputs any arbitrary computable function of the inputs {𝑢 𝑖 } 𝑖 ∈P 𝑐𝑜𝑟 , the auxiliary input 𝑢 * and the messages obtained from the trusted party.

Let ū = (𝑢 1 . . . 𝑢 𝑛 ) be the vector of inputs of all parties and 𝑢 * the auxiliary input of S. Recall that 𝜆 is the security parameter. We denote by ideal F,S (𝑢 * ),P 𝑐𝑜𝑟 ( ū, 𝜆) to the vector of outputs of parties in the above execution.

The real model. The real model of an 𝑛-party protocol Π describes its execution in the presence of non-uniform probabilistic polynomial time advesary A that corrupts a set of parties P 𝑐𝑜𝑟 . Parties in P \ P 𝑐𝑜𝑟 behave as described by Π. We denote by real Π,A (𝑢 * ) ( ū, 𝜆) the vector of outputs of parties in the real execution of Π with input ū and where A has auxiliary input 𝑢 * .

We formalize the notion of security with identifiable abort [33, Def. 16 of the full version] below.

Definition 3 (Security with identifiable abort in the stand-alone setting). Let 𝜆 be the security parameter and F : ({0, 1} * ) 𝑛 → ({0, 1} * ) 𝑛 be an 𝑛-party ideal functionality. A protocol Π securely computes F with identifiable abort if for every non-uniform probabilistic polynomial time (PPT) adversary A in the real model, there exist a non-uniform PPT adversary S in the ideal model such that the distributions of Hybrid model. In addition to the security definition, the simulation paradigm facilitates tools to prove security of protocols which use sub-protocols already known to be secure. Given functionalities F 1 , . . . , F 𝑘 , where 𝑘 is polynomial in 𝜆, it allows to define a protocol in which both parties can send messages to each other and place "ideal calls" to a trusted party that computes F 𝑖 for 𝑖 ∈ {1, . . . , 𝑘 }. In these ideal calls, parties can send their input to the trusted party and wait for the output of F 𝑖 . However, (1) they cannot send any messages between each other after invoking an ideal functionality and before its response is returned by the trusted party and (2) functionalities cannot be called concurrently. In other words, functionalities can only be sequentially composed with all other interactions. We denote such model as the (F 1 , . . . , F 𝑘 )-hybrid model. When we describe a protocol in the (F 1 , . . . , F 𝑘 )-hybrid model, we say that F 1 , . . . , F 𝑘 are hybrid functionalities. Sequential composition. Consider the protocol Π and functionalities F 1 , . . . , F 𝑘 as defined above and let 𝜌 1 , . . . , 𝜌 𝑘 be protocols. We define the protocol Π 𝜌 1 ,...,𝜌 𝑘 to be the protocol in the ideal model that behaves exactly as Π in real messages, but for all 𝑖 ∈ {1, . . . , 𝑘 } each ideal call to F 𝑖 is replaced by the execution of protocol 𝜌 𝑖 . We now state conditions such in which sequential composition is secure.

Theorem 4 (Seqential composition [START_REF] Goldreich | Foundations of cryptography: volume 2, basic applications[END_REF]). Let F 1 , . . . , F 𝑘 be secure multiparty functionalities and let 𝜌 1 , . . . , 𝜌 𝑘 be protocols that securely compute F 1 , . . . , F 𝑘 respectively with identifiable abort. Let G be a multiparty functionality and let Π be a multiparty protocol that securely computes G in the (F 1 , . . . , F 𝑘 )-hybrid model with identifiable abort. Then Π 𝜌 1 ,...,𝜌 𝑘 securely computes G in the real model with identifiable abort.