Julien Devigne
email: julien.devigne@intradef.gouv.fr

Céline Duguey
email: celine.duguey@irisa.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@irisa.fr

MLS: how Zero-Knowledge can secure Updates

Keywords: Cryptographic Protocols, Messaging Layer Security -MLS, Secure Messaging, Zero-Knowledge

The Messaging Layer Security (MLS) protocol currently developed by the IETF aims at providing a group secure messaging solution. The goal is to provide end-to-end security, including Forward Secrecy and Post Compromise Secrecy, properties well studied for one-toone protocols. MLS proposes a tree-based regular asynchronous update of the group secrets, where a single user can alone perform a complete update. A main drawback is that a malicious user can create a denial of service attack by sending invalid update information. In this work, we propose a solution to prevent this kind of attacks, giving a checkpoint role to the server that transmits the messages. In our solution, the user sends to the server a proof that the update has been computed correctly, without revealing any information about this update. We use a Zero-Knowledge (ZK) protocol together with verifiable encryption as building blocks. As a main contribution, we provide two different ZK protocols to prove knowledge of the input of a pseudo random function implemented as a circuit, given an algebraic commitment of the output and the input.

Introduction

Secure messaging protocols have been widely adopted over the last few years. The privacy offered by encrypted communication seduces billions of users worldwide. A significant number of application providers have settled their security on the Double Ratchet Algorithm [START_REF] Marlinspike | The double ratchet algorithm[END_REF], often identified as Signal. This protocol provides End-to-End confidentiality, as well as Forward Secrecy (FS) and Post Compromise Secrecy (PCS). The Double Ratchet however is dedicated to oneto-one communications. Messaging Layer Security (MLS) targets secure group messaging and is developed by the Internet Engineering Task Force (IETF). The goal is to obtain similar security properties as those in one-to-one protocols. The group keys are computed and regularly updated in a protocol called TreeKEM, based on a tree structure. In MLS, each member of the group is represented by a tree leaf and the group secret is given by the tree root. Each member can update the group secret as well as its own keys. He can also, if authorized, add or remove members. To perform an update, a user sends to the other leaves secret information which depend on their position in the tree. In this paper, we are concerned with an open problem identified in the MLS draft: how to be sure that each user receives a valid update information? In other words: how to be sure that the updating user is not cheating? The current protocol provides verification elements for each user to check whether the update he received is valid, but it does not prevent a malicious updater to create denial of service attacks. Such attacks would prevent the updating process, seriously damaging FS and PCS properties, that seduce the users. Consequently, we propose a solution in which the users only receive valid updates: the server which transmits the update messages can check their validity before forwarding them. The server is given a check-point role. If the server were to be dishonest, he could not create a malicious update by himself. Hence we only add a layer of security, through the server, without modifying the core of MLS. A main building block of our solution is a ZK protocol, inspired from the recent multi party computation (MPC) in the head solutions ( [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF], [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF], [START_REF] Katz | Improved non-interactive zero knowledge with applications to post-quantum signatures[END_REF]).

Our contribution. As a first contribution, we show how to combine a ZK protocol with a verifiable encryption solution to solve the open problem identified in the IETF draft for MLS, in a light version of the protocol. The idea is to enable an intermediate server to perform a blind verification (on encrypted and committed data) that each update information sent by the updater is correctly computed. The ZK proof is provided on a statement that mixes a circuit evaluation (an HKDF derivation, defined in [START_REF] Krawczyk | Cryptographic extraction and key derivation: The HKDF scheme[END_REF]) and an algebraic commitment (typically a Pedersen commitment, described in [START_REF] Pedersen | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF]). The verifiable encryption scheme proves to the server (i.e. the verifier) that the encrypted data is the one that is committed to and verified in the proof. As a second contribution, we propose two ZK protocols for statements that compose an algebraic commitment and the circuit computation of a pseudorandom function family (PRF) f . More precisely, we prove the knowledge of a witness x such that public commitments C x , C y are algebraic commitments of x and f (x), with f (x) remaining secret. Our approach is based on the MPC in the head paradigm, introduced in [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF]. We consider the recent ZK proof system ZKBoo [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF] and its improvements ZKBoo++ [START_REF] Chase | Post-quantum zero-knowledge and signatures from symmetric-key primitives[END_REF] as well as KKW [START_REF] Katz | Improved non-interactive zero knowledge with applications to post-quantum signatures[END_REF]. Our first approach consists in considering a Boolean circuit that computes two tags of the form t = ax + b. One tag is on the secret input x, the second is on the secret output f (x). The proof on this circuit binds the secret input and output to the tag values. In a second step, we use the linear properties of the algebraic commitment to show that the committed values are also bound by the tags. Finally, we invoke properties of the PRF to show that their exists only one solution to the tag equations. Our second approach is directly inspired by a recent work of Backes et al. [START_REF] Backes | Efficient noninteractive zero-knowledge proofs in cross-domains without trusted setup[END_REF]. The first step is to provide commitments to the bits of the secret input and output. Then, we call the algebraic properties of the commitment scheme to link those bits with values used in the circuit proof. Previous works have proposed solutions for such algebraic and circuit composition statements [START_REF] Chase | Efficient zero-knowledge proof of algebraic and non-algebraic statements with applications to privacy preserving credentials[END_REF] and [1] that we describe in the following. However, the former is inherently interactive and the latter uses SNARKs, where the burden of the proof is mainly on the prover side, which does not fit our case as smartphones have resources to be saved. Related work. Secure Messaging. Secure messaging, and more particularly Ratcheted Key Exchange (RKE) have been widely studied over the past ten years. We can cite the first analysis of the Signal protocol [START_REF] Cohn-Gordon | A formal security analysis of the signal messaging protocol[END_REF] as well as the following works on RKE ( [START_REF] Bellare | Ratcheted encryption and key exchange: The security of messaging[END_REF], [START_REF] Poettering | Towards bidirectional ratcheted key exchange[END_REF], [START_REF] Jaeger | Optimal channel security against fine-grained state compromise: The safety of messaging[END_REF], [START_REF] Jost | Efficient ratcheting: Almost-optimal guarantees for secure messaging[END_REF], [3]). Literature for the group version is more limited. In [START_REF] Cohn-Gordon | On ends-toends encryption: Asynchronous group messaging with strong security guarantees[END_REF] Cohn Gordon et al. introduced the notion of Asynchronous Ratcheted Trees (ART). These ART are Diffie Hellman based binary trees in which the update process of a node involves entropy coming from both its children. In MLS, the underlying TreeKEM protocol is inspired by ART. A main difference is that a single leaf can generate the update data for each of its ancestor nodes. TreeKEM has been initially formalized in the technical paper [START_REF] Bhargavan | Treekem: Asynchronous decentralized key management for large dynamic groups[END_REF] and has then evolved to reach the actual description available on the prevailing draft 11 [?]. Alwen et al. formalize in [4] a Continuous Group Key Agreement (CGKA) derived from the two-party Continuous Key Agreement defined in [3]. They provide a security model for CGKA and show that the protocol TreeKem does not achieve optimal FS and PCS security. However they prove that a better security can obtained by using an updatable public key encryption scheme. Our solution is compatible with this improvement. In [START_REF] Alwen | Keep the Dirt: Tainted TreeKEM, Adaptively and Actively Secure Continuous Group Key Agreement[END_REF], Alwen et al. focus on the addition and revocation process. Both works consider a partially active attacker, that can leak a user's state, has full control on message delivery but cannot use the knowledge of secret keys to insert his own data.

Zero-Knowledge proofs. ZK proofs have proved to be a powerful tool in cryptography, since their conception in the mid 1980s. It has been shown that ZK proofs exist for any NP language. However, efficient ZK protocols are designed for a small class of language and do not extend to any NP languages. Sigma protocols (Σ-protocols), clearly described in [START_REF] Damgård | A State-of-the-art Diffie Hellman Function[END_REF], are very efficient for proving algebraic relations, whereas other protocols have been designed for proving statements that can be expressed as a circuit. Among them, Garbled Circuits based schemes, as introduced in [START_REF] Jawurek | Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently[END_REF], which are inherently interactive, and SNARKs, as designed in [START_REF] Gennaro | Quadratic span programs and succinct NIZKs without PCPs[END_REF], [START_REF] Groth | Short pairing-based non-interactive zero-knowledge arguments[END_REF], [START_REF] Kilian | A note on efficient zero-knowledge proofs and arguments (extended abstract)[END_REF]. SNARKs are non-interactive arguments (with computational soundness) of knowledge with small proofs and light verification: the burden of the proof is on the prover side. They are proven secure in the common reference string (CRS) model: a common trusted public input has to be shared by the prover and the verifier. Practical implementations based on pairings are in use in real life protocols such as cryptocurrencies. More recently, the MPC in the head paradigm, introduced in [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF], leads to very efficient proof system without CRS. The seminal paper [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF] introducing ZKBoo proposes the first efficient ZK proof of a hash function computation. Further works significantly optimize the efficiency, such as Ligero [START_REF] Ames | Ligero: Lightweight sublinear arguments without a trusted setup[END_REF], or ZKBoo++ [START_REF] Chase | Post-quantum zero-knowledge and signatures from symmetric-key primitives[END_REF] and KKW [START_REF] Katz | Improved non-interactive zero knowledge with applications to post-quantum signatures[END_REF] that were directly incorporated in the post quantum signature scheme Picnic. In real life however, many applications need to provide proofs on statements that mix algebraic and non algebraic parts. Expressing the algebraic part as a circuit would considerably increase the circuit size and reduce the efficiency. One can express each gate of a circuit as an algebraic relation that can be proven with a Σ-protocol, but this solution is clearly non desirable as circuits for hashing may have thousands of gates. Considering this, combining efficiently algebraic and non algebraic proofs has revealed to be an important challenge. In [START_REF] Chase | Efficient zero-knowledge proof of algebraic and non-algebraic statements with applications to privacy preserving credentials[END_REF], Chase et al. combine for the first time proofs on algebraic and non algebraic statements, solving the open problem described above. They propose two constructions to provide a circuit proof on a committed input. Their two constructions are based on Garbled Circuits, which enable efficient ZK proofs for non algebraic statements but are inherently interactive. Our solutions are close to theirs in the sense that their first proposal uses bit wise commitment on an secret input, and their second proposal includes a one-time mac computation in the circuit to be garbled. However, their proposal heavily relies on the garbling protocol and can not be transposed to the non interactive setting. In terms of efficiency, their second solution augments the cost of garbling in O(|x|s + s) where s is the security parameter required for the one time mac (which can be chosen less than the size of the witness x). This corresponds to the multiplication on integers ax included in the circuit. In our tag based solution, we show that the multiplication does not significantly increase the proof size. More recently, Agrawal et al. in [1] propose a solution for modular composition of algebraic and non algebraic proofs. Their solution is non interactive, based on Sigma protocols and QAP-based SNARKs. As explained in their work, the "key ingredient we need from a SNARK construction is that the proof contains a multi-exponentiation of the input/output". They compose it with a proof that the exponents in a multi-exponentiation correspond to values committed to in a collection of commitments. From this result, they show how to obtain proofs for AND, OR and composition of two statements, either algebraic or circuit. The authors work with SNARK proofs for the circuit part in order to obtain small proofs and a light verification step. These properties are desirable for their applications such as privacy-preserving credentials or crypto-currencies proofs of solvency. The counterpart is that the prover has to provide a higher computational effort. In our application case -a proof of an honest key update in MLSthe verifier turns out to have a larger computation power than the prover. Finally, Backes et al. propose in [START_REF] Backes | Efficient noninteractive zero-knowledge proofs in cross-domains without trusted setup[END_REF] an extended version of ZKBoo++ that allows algebraic commitments on the secret input of the circuit. Their protocol is non interactive and the computational cost is balanced between the prover and the verifier. Their solution requires to commit to each bit of the secret input and to commit to internal values of the ZKBoo++ circuit proof. We extend their result to the case of a committed output in our second zero-knowledge solution. We focus on the MPC in the head paradigm in order to provide proofs in which the amount of work is balanced between both parties.

Organization of the paper. In section 2, we quickly recall the definitions concerning ZK proofs, commitment schemes, and verifiable encryption. We detail more particularly ZKBoo, an efficient protocol for large boolean circuits such as hash computation. In section 3, we present the protocol MLS, focusing on the process to update the group secret, and we describe our solution to improve the security of the update mechanism. The section 4 is dedicated to our two proto-cols, CopraZK and (bitwise) ComInOutZK, for proving knowledge of the preimage of a PRF function when only commitments of the input and the output are publicly available. Finally, in section 5 we present implementation results concerning our first solution CopraZK.

Backgrounds

Zero-Knowledge. Consider an NP relation R, i.e. given a witness w and an input x, R(x, w) = 1 can be decided in polynomial time. Let L be the language associated to R, L = {x|∃w such that R(x, w) = 1}. A ZK proof of knowledge for L allows a prover to convince a verifier (who knows x), that he knows a witness w for R, without revealing any further information on w. It shall be correct (if the prover and the verifier are honest, the verifier always accepts), sound (a corrupted prover can make the verifier accept a false statement only with negligible probability), and zero-knowledge (no information on w leaks from the proof). Following the notation of [START_REF] Camenish | Proof systems for general statements about discrete logarithms 14[END_REF], we write PK{w 1 , . . . w s : R(w 1 , . . . , w s , x 1 . . . x t ) = 1} to denote the proof of knowledge of the secret witnesses w 1 , . . . w s that satisfy the relation R with the public values x 1 , . . . , x t .

Commitment Schemes. A commitment scheme involves a Committer and a Receiver who share public parameters. On entrance a message x and an additional opening information r, the commitment protocol produces a value c = Com(x, r) such that c shall not reveal any information about x; this is the hiding property. The Committer can open its commitment c by revealing r and x with the property that only the secret x shall produce a valid opening for c; this is the binding property. For our second ZK protocol, we will require an extra property, called equivocality. Briefly, a commitment is equivocable if there exists a trapdoor T such that, given a commitment C, its opening information, and T , it is possible to open C to any value. Equivocality comes with a specific extractor that, given two different openings (x 1 , r 1 ), (x 2 , r 2 ) to a single commitment C, can extract the trapdoor T . The Pedersen commitment scheme [START_REF] Pedersen | Non-interactive and information-theoretic secure verifiable secret sharing[END_REF] is an equivocable scheme with unconditional hiding and computational binding. It is routinely used because it interacts nicely with linear relations. This scheme is defined as follows: let G be a cyclic group of prime order q, P a generator and Q ∈ G such that the discrete log of Q in base P is unknown. Then, Com(x) = xP + rQ where r is sampled at random in Z q . Let C 1 , C 2 be commitments to values x 1 , x 2 . If a, b ∈ Z q are public values, then one can efficiently prove the following :

P K{x 1 , x 2 , r 1 , r 2 : C 1 = x 1 P + r 1 Q ∧ C 2 = x 2 P + r 2 Q ∧ ax 1 + x 2 = b mod q}.
The trapdoor for equivocality is given by the discrete log of Q in base P .

MPC in the head. Ishai et al. introduced in [START_REF] Ishai | Zero-knowledge from secure multiparty computation[END_REF] a new paradigm for ZK proofs, called MPC in the head. This solution reveals to be very competitive in terms of efficiency for ZK proofs performed on circuits. The idea is that the prover performs a virtual MPC and obtains several views. He commits to these views and opens only a sub-part of them required by the verifier. This Σ-protocol can be turned into a non-interactive proof using Fiat-Shamir transformation [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. ZKBoo [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF] generalizes IKOS to any relation R φ defined by a function φ : X → Y (R φ (y, x) ↔ y = φ(x)), as long as the function φ can be computed in a specific manner identified as a (2,3)-decomposition. Given this specific MPC computation, the prover first shares its secret input x into (x 1 , x 2 , x 3 ) = Share(x) such that x = x 1 ⊕ x 2 ⊕ x 3 . Then he runs the MPC and obtains three distinct views w 1 , w 2 , w 3 and from each of this view he gets an output share y i = Output(w i ), i ∈ {1, 2, 3} such that y 1 ⊕ y 2 ⊕ y 3 = φ(x). A detailed description is given in Appendix A.

Verifiable encryption. Verifiable encryption aims at convincing a verifier that an encrypted data satisfies some properties without leaking any information about the data itself. In such 2-party protocol, a prover and a verifier share in a common input string a public key encryption scheme Enc, a public key pk for Enc, and a public value y. At the end, the verifier either accepts and obtains the encryption of a secret value x under pk such that x and y verify some relation R or rejects. It is worth noticing that the prover does not need to know the secret key sk, that usually belongs to a third party. Verifiable encryption often appears in the domain of anonymous credentials, fair exchange signatures, or verifiable secret sharing [START_REF] Stadler | Publicly verifiable secret sharing[END_REF]. In [START_REF] Camenisch | Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes[END_REF], Camenish and Damgård describe how to provide a proof that an encrypted value is a valid signature, using any semantically secure encryption scheme. The idea is to take advantage of the Σ-protocol that already exists for a relation R(x, y), to provide an evidence that an encrypted value is the witness x for this relation. In our application, we need to prove that the encrypted data x, is the one that is linked by a Pedersen commitment C x = y. As a Pedersen commitment comes with an associated Σ-protocol, the Camenish-Damgård scheme applies naturally. There are interesting ways towards more efficient schemes, e.g. [START_REF] Chase | The Signal private group system and anonymous credentials supporting efficient verifiable encryption[END_REF] or [14]. However, the main benefit of the Camenish-Damgård solution is that it does not introduce any change in the original MLS specification, as we can still use the encryption scheme required in MLS draft. More details are given in Appendix B. We denote by VerifEnc Enc,pk (m : r) the encryption of a message m (using randomness r) under the public key pk with the encryption scheme Enc and the associated proof. We omit the randomness r when it is not necessary to explicitly mention it.

MLS Updates

We explain how the MLS update mechanism works and our more secure solution.

Message Layer Security

MLS is a protocol currently under development by the IETF to provide an Endto-End secure group messaging application. The idea is to enable a group of users to share a common secret that can be updated regularly by any user. One of the open issues in the IETF draft is that the validity of an update message can only be checked after it has been received. This open issue was clearly identified until draft 9 included. In the recent draft 11, all open issues have been removed. However, to our knowledge, there is still no solution to this problem, which can lead to denial of service attacks. Currently in MLS, the authors require an hybrid public key encryption (HPKE) scheme, as designed in [START_REF] Barnes | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF], which comprises a KEM, an AEAD encryption scheme and a hash function. Briefly, an asymmetric KEM protocol is used to compute and transmit a symmetric key k. Then data are symmetrically encrypted under key k with the AEAD encryption scheme. As symmetric encryption is far more efficient than its asymmetric counterpart, this hybrid method is a common practice. In the rest of this work, we denote by Enc pk (m : r) the HPKE encryption of a message m under the public key pk using randomness r. The asymmetric part of Enc is based on an elliptic curve E defined on a finite field Z/pZ with base point P of order a prime q. MLS also supposes the existence of a broadcast channel for each group, which distributes all the messages to each group member, conserving the order. MLS tree. MLS is based on a binary tree structure (Figure 1) where users correspond to leaves and each node is associated to a secret value. Each user U has a long term identity signing key and an initial key package for the encryption scheme Enc (both certified by a PKI). We will simply represent the key package as a public/private key pair (pk U , sk U ) valid for the encryption scheme Enc.

A B C -E F G H psA psB psC psE psF psG psH • ps2 • ps6 • ps10 • ps14 • ps12 • ps4
• psroot Fig. 1. A view of the MLS tree. Nodes are implicitly numbered from left to right, independently from their height. Leaves are associated to a user represented as a letter. Each node i has a secret psi. A leaf secret is indexed with its user name.

The group key is derived from the root secret. Each child node knows the secret of each of its ancestors and only of its ancestors. To each node i corresponds:

-a path secret ps i ; -a secret and public key sk i , pk i = deriveKeyPair(ps i ).

The exact derivation depends on the elliptic curve. We define, w.l.o.g, (sk i , pk i ) = deriveKeyPair(ps i ) = (deriveSK(ps i ), deriveSK(ps i )P ) where deriveSK is a PRF. A user knows the secret (and so the secret keys) in its direct path, composed of itself and its direct ancestors. Moreover, each user keeps an up-to-date global view of the tree, as a hash value of each node's public information.

Updates. The path secrets and derived keys are regularly updated. Each update gives birth to a new epoch. Each epoch corresponds to a root secret, from which are derived several application keys. We focus on how the root secret is updated, not on how it is used.

To update the tree, a user B generates a new secret ps B . The path secrets in the direct path will be successively derived from ps B . We note H p (ps i ) for the function HKDFexpand(ps i , "path", "", Hash.length). The update mechanism is given in Figure 2.

A B C -E F G H psA ps B psC psE psF psG psH • Hp(ps B ) = ps 2 • ps6 • ps10 • ps14 • ps12 • Hp(ps 2 ) = ps 4
• Hp(ps 4 ) = ps root Fig. 2. Update process. User B updates its secrets. Path secrets are updated along its direct path (in red). The update secrets are sent to its copath nodes (in green).

When B updates its secret ps B → ps B , he first computes the new node data for each node on its path:

-ps 2 = H p (ps B ), pk 2 = deriveSK(ps 2 ) • P -ps 4 = H p (ps 2 ), pk 4 = deriveSK(ps 4) • P -ps root = H p (ps 4 ), pk root = deriveSK(ps root ) • P Then he sends for each node on its copath the necessary secret material for the users under this node to perform the same update (i.e., to obtain the new secret keys for their updated ancestors). Following our example in Figure 2 From there, a malicious user can send non valid updates (to everyone or any branch) causing a denial of service. Given the mechanisms for a user to check whether the update is valid, there are two options: either the update is accepted by all only once each user has confirmed that he received a valid update, this can imply a huge latency, if some users are seldom online. Or the update is validated without such a feedback approach. In such a case, the users that received non valid secret values are ejected from the group de facto. In both case, this seriously hampers with the security of the service provided by the protocol.

Securing MLS updates

We now explain how to combine a ZK protocol and a verifiable encryption to secure the update process in MLS. We first focus on a single step of the update process (a user updates his direct parent) and then explain how this solution can be extended to the global tree.

Server-checking in MLS. As described in Figure 2, let assume that B generates a new secret ps B and computes:

-deriveKeyPair(ps B ) to obtain a new key package;

-ps 2 = H p (ps B ) the new secret for node 2;

-(sk 2 , pk 2 ) = deriveKeyPair(ps 2 ) the new keys for node 2;

Finally he sends (Enc pk A (ps 2 ), pk 2 ) so that everyone gets pk 2 but only A can access ps 2 . Now suppose there exists a ZK protocol which, given public values C x and C y , provides the following proof: PK{x, r x , r y :

C x = Com(x, r x ) ∧ C y = Com(f (x),
C 2 = Com((ps 2 ), r 2 ) ∧ C 4 = Com(H p (ps 2 ), r 4 ) ∧ C sk4 = Com(deriveSK(H p (ps 2 )), r sk 4 ) ∧ pk 4 = deriveSK(H p (ps 2
))P } together with VerifEnc Enc,pk6 (ps 4 ). The crucial point is that, as the commitment C 2 is linked with ps B in Π 2 , it can be used as a base value for Π 4 and so on. Some special care must be taken as we commit, in a group of order q prime, to an element sk ∈ {0, 1} 256 that does not lie naturally in Z/qZ. We explain how to handle with this in Appendix C.

About the server. Several reasons appear for calling on a third party. Firstly, this central node with the largest computational power is the one that can discard invalid updates with the most efficiency. If one relies on users to check for the validity of the data they received, this means that one must wait for each user to process the update and to send back an acknowledgement. As a user can be off-line for a long time, this can be very inefficient. Another solution would be to allow users to adopt the update as soon as they are individually convinced it is correct, while providing a "backup solution". This would probably imply keeping old keys and drastically impoverish FS. Secondly, in MLS architecture, all the update encrypted messages are gathered and sent as one big message to all the users. It may be of interest to think of a solution where only the needed encryption is sent to a specific user. In this case, only the server will see all the messages together. He is then the only one able to perform a verification on a global proof to see whether all the updates are correctly generated from a single secret seed.

ZK for a PRF on committed input and output

In this section, we provide two protocols to prove the knowledge of an input x and randoms r x , r y , such that, for a public values C x , C y , and a function f evaluated as a circuit, C x = Com(x, r x ) and C y = Com(f (x), r y ). This goal can be written as an ideal functionality, as in Figure 3.

The Verifier inputs Cy, Cx. The Prover inputs values x, rx, ry.

The functionality outputs accept if (x, rx) opens Cx and (f (x), ry) opens Cy. The efficient ZK proofs for a function evaluation require this function to be evaluated as a circuit, but efficient commitments are algebraic. Consequently, we want to achieve the best of both worlds by combining a proof on a circuit and algebraic commitments. Our first solution, CopraZK (Commitment and PRF alternative ZK), is specific to the case of f being a PRF. The secret x is the PRF key and we evaluate f on a public message m. We consider the circuit that evaluates two equations on x and on another secret input a. We call the results of these equations tag values. The first tag t 1 only depends on f (x, m) and f (a, m). The second tag t 2 depends on x and a. Calling PRF properties, we show that the pair of equations have a single solution. Hence, the input pair (x, a) is bound to the tag pair t 1 , t 2 . In a second step, we call the homomorphic properties of the commitment to show that the values committed in C x and C y also verify the equations. Then it must be that the values committed to corresponds to the values used in the circuit.

Our second solution, ComInOutZK (Committed Input and Output ZK) is directly inspired from [START_REF] Backes | Efficient noninteractive zero-knowledge proofs in cross-domains without trusted setup[END_REF], which provides a proof of a circuit evaluation on a committed input and public output. We extend their work to a committed output. The idea is to commit to the bits of the output and, for each round, to the output shares given by the circuit decomposition of ZKBoo. Then, calling the homomorphic properties of the commitment scheme, one can bind the bit wise commitments to the share commitments by revealing the difference of randomness between those elements.

CopraZK adds a negligible number of algebraic operations. The prover performs around 20 computations on the curve (public key operations) and 8 additions in Z/qZ (symmetric operations). For the verifier, 12 additions on the curve and 2 in Z/qZ are needed. However, the circuit part of the proof is more than doubled to compute the two tags. On the challenge size When we expose our solutions, in both case we mention a unique challenge, that is used for the algebraic Σ-protocol and for the ZKBoo proof. This means that the challenge space size for the Σ-protocol is 3 and that we shall perform λ/3 rounds to obtain a soundness error in 2 -λ . The σ-protocol can benefit from a larger challenge space, that allows for a single round. As explained in [START_REF] Backes | Efficient noninteractive zero-knowledge proofs in cross-domains without trusted setup[END_REF], it is possible to define distinct challenges e ρ ∈ {1, 2, 3} for each ZKBoo round and a global challenge e = σ i=1 3 i e i for the algebraic Σ-protocols, hence the algebraic part of the proof can be performed a single time.

Our first solution: CopraZK

Let us denote by Func(D, R) the set of all functions from D to R and by FF(K, D, R) the set of all function families with parameter (key) in K, domain D and range R. We write f : K × D → R for a function family in FF(K, D, R) (and call it a function, by ease of language). Let f be a function:

Z 2 × Z * 2 → Z 2 and m a public input, m ∈ Z * 2 .
Let G be a group of prime order q, such that 2 ≤ q. There is a natural embedding Z 2 → G. Let P be a generator for this group and Q an element of G such that log P (Q) is unknown. Let h be a hash function

Z * 2 → Z * 2 .
Let Com be the Pedersen commitment scheme. Those elements are the public parameters of the prover and the verifier. We use a ZKBoo proof for the circuit part, but the protocol and its proof are valid for any circuit based ZK proof or argument. Let C x , C y be public commitments, known to the verifier. The main idea is to consider the circuit two tags t 1 = f (x, m) + f (a, m) and t 2 = x + a where a is a random mask considered as a second secret entry of the circuit. A MPC in the head proof on this circuit ensures that t 1 and t 2 are correctly computed from two secret values x and a known to the prover. The prover also provides commitments C a and C b for values a and f (a, m). Considering Pedersen commitments, we complete the circuit proof with an algebraic proof that the committed values in C a , C x , C y , C b verify the relations t 1 and t 2 . These linear relations together with the properties of f defined below, bind the values of C x and C y such that the verifier can be convinced that the value committed in C y is equal to the evaluation of f on the value committed in C x . The detailed description of the protocol CopraZK is given in Figure 4. The following theorem states the security of CopraZK.

Theorem 1. Let f be a secure special pseudo-random function, h be a secure hash function and Com a homomorphic commitment scheme. Then the CopraZK protocol described in Figure 4 defines a ZK argument with computational Zero-Knowledge.

ComInOutZK: a bit-wise solution

In [START_REF] Backes | Efficient noninteractive zero-knowledge proofs in cross-domains without trusted setup[END_REF], the authors propose a non interactive proof P K{x : C x = Com(x, r x )∧y = f (x)} based on bit commitments and ZKBoo++. Their optimized solution increases the ZKBoo++ prover's and verifier's work with O(|x| + σ) exponentiations and multiplications on the group G of order q chosen for the commitment, Let Cy, Cx be public commitments and m a public message. The Prover wants to convince the Verifier that he knows x, rx, ry such that Cx = Com(x, rx) and Cy = Com(f (x, m), ry).

Prover

Commit phase:

1. samples a, ra, r b ←$ Z 2 .

computes Ca

= Com(a : ra), C b = Com(f (a, m) : r b ). 3. computes α = h(Cx||Cy||Ca||C b ).
4. computes (t1, t2) = (f (x, m) -αf (a, m) mod q, x -αa mod q). 5. Evaluates the commit phase output aΠ for the Σ protocol Π = P K{x, rx, y, ry, a, ra, b, r b :

Cx = xP + rxQ ∧ Cy = yP + ryQ ∧ Ca = aP + raQ ∧ C b = bP + r b Q ∧ t1 = y -αb ∧ t2 = x -αa} for ρ ∈ [1, σ] (ZKBoo part): 6. samples random tapes k ρ 1 , k ρ 2 , k ρ 3 . 7. generates x ρ 1 , x ρ 2 , x ρ 3 = Share(x, k ρ 1 , k ρ 2 ) s.t. x = x ρ 1 ⊕ x ρ 2 ⊕ x ρ 3 . 8.
evaluates the MPC protocol on the circuit Circ: on (x, a), (t1, t2) = (f (x, m) -αf (a, m) mod q, x -αa mod q), and obtains three views w ρ 1 , w ρ 2 , w ρ 3 . 9. obtains the output shares :

o ρ 1 = (t1,1, t2,1), o ρ 2 = (t1,2, t2,2), o ρ 3 = (t1,3, t2,3) s.t. t1 = t ρ 1,1 ⊕ t ρ 1,2 ⊕ t ρ 1,3 , t2 = t ρ 2,1 ⊕ t ρ 2,2 ⊕ t ρ 2,3 . 10. commits to the views: c ρ 1 = h(w ρ 1 , k ρ 1 ), c ρ 2 = h(w ρ 2 , k ρ 2 ), and c ρ 3 = h(w ρ 3 , k ρ 3 ). a = Ca, C b , Cx, t1, t2, (c ρ 1 , c ρ 2 , c ρ 3 , o ρ = (o ρ 1 , o ρ 2 , o ρ 3 ))ρ, aΠ .
Challenge: e = h(a)

Response phase:

1. computes the response zΠ for the proof Π Reconstruct a and reject if e = h(a) where |x| is the number of bits of the input x and σ is the number of rounds in ZKBoo++. The proof size grows by O(|x| + σ) group elements and O(|x| + σ) elements in Z/qZ. We adapt this strategy in the case of a committed output.

for ρ ∈ [1, σ] : 2. b ρ = (o ρ e+2 = (t1,e+2, t2,e+2), c ρ e+2 ) 3. z ρ = (w ρ e+1 , k ρ e ,
As the output of the circuit, y, shall remain secret, we will not be able to call ZKBoo++ as a full black box. This is of prime importance when we prove the zero-knowledge property. Compared to CopraZK, the bit-wise commitment strategy does not require to augment the circuit with a second evaluation of f . Another advantage is that we do not require specific hypothesis on f . As a drawback, we add O(|x|

+
C b⊕β = Com(1, 0) -C b = Com(1 -b, -r b ). For any x = |x|-1 i=0 2 i x[i], denote C x[i] = Com(x[i], r x[i] ) a commitment to the i-th bit of x. Then |x|-1 i=0 2 i C x[i] is a valid commitment to x with opening randomness |x|-1 i=0 2 i r x[i]
. And one can easily compute a commitment to x ⊕ β for an element β as

C x⊕β = |x|-1 i=0 2 i C x[i]⊕β[i] , with opening randomness |x|-1 i=0 2 i (-1) β[i] r x[i] .
We describe in Figure 5 the protocol on committed output only, for readability reasons. Combining Backes et al. protocol for committed input and ours for committed output leads to the functionality described in Figure 3. The public parameters are: f a function from Z 2 to Z 2 evaluated as a circuit (not necessarily PRF), G is a prime order q group, such that 2 ≤ p with a natural embedding Z 2 → G, and P be a generator of G and Q ∈ G such that log P (Q) is unknown. We consider a hash function h : Z * 2 → Z * 2 and Com a Pedersen commitment scheme.

Theorem 2. Given that ZKBoo and the Π j are Σ protocols with 3-special soundness and honest verifier Zero Knowledge property, and Com is a homomorphic and equivocal commitment scheme, then the protocol described in Figure 5 is a Σ-protocol with 3-special soundness and honest verifier property.

Implementation

We now discuss the efficiency of our protocol CopraZK, both in terms of time and size of the proof. We focused on CopraZK because it was more prone to benefit from optimized MPC protocols such as KKW ( [START_REF] Katz | Improved non-interactive zero knowledge with applications to post-quantum signatures[END_REF]), that are designed for large circuits. We detail the results we obtained from a simple implementation of CopraZK on top of the existing ZKBoo code. We remind that the efficiency of the MPC in the head protocols is directly related to the number of AND gates in the circuit. In fact, in ZKBoo, ZKBoo++ and KKW, only AND gates

The Prover knows x, y = f (x), and ry such that Cy = Com(f (x), ry). The Verifier knows the statement Cy. Prover Commit phase 1. samples random r y[j] and commits to the bits of y : C y[j] = Com(y[j], r y[j] ) for j ∈ [0, |y|]. 2. computes the commit phase aΠ j for the proofs Πj = P K{y[j], r y

[j] : C y[j] = Com(y[j], r y[j] ) ∧ y [ j] ∈ {0, 1}} for j ∈ [0, |y|]. for ρ ∈ [1, σ] : 3. samples random seeds k ρ 1 , k ρ 2 , k ρ 3 . 4. generates the shares x ρ 1 , x ρ 2 , x ρ 3 = Share(x, k ρ 1 , k ρ 2 ) such that x = x ρ 1 ⊕ x ρ 2 ⊕ x ρ 3 . 5.
simulates the MPC to obtain three views w ρ 1 , w ρ 2 , w ρ 3 . 6. evaluates y ρ i = Output(w ρ i ), i ∈ {1, 2, 3}. 7. commits to the views :

c ρ i = h(w ρ i , k ρ i ), i ∈ {1, 2
, 3}. 8. samples random r y ρ i and commits to the outputs :

C y ρ i = Com(y ρ i , r y ρ i ), i ∈ {1, 2, 3}. a = ((C y ρ 1 , C y ρ 2 , C y ρ 3 , c ρ 1 , c ρ 2 , c ρ 3 )σ, (C y[j] ) |y| , (aΠ j ) |y| ) Challenge : e = h(a)

Response phase

1. computes the responses zΠ j for the proofs Πj

for ρ ∈ [1, σ] : 2. b ρ = (C y ρ e+2 , c ρ e+2 ) 3. z ρ = (w ρ e+1 , k ρ e , k ρ e+1 , r y ρ e , r y ρ e+1 ) 4. β ρ = y ρ e ⊕ y ρ e+1 5. C ρ z = |y|-1 i=0 2 i C y[i]⊕β ρ [i] 6. r ρ z = r y ρ e+2 -|y|-1 i=0 2 i (-1) β[i]
, z ρ , r ρ z )σ 2. Parse a as (C y ρ 1 , C y ρ 2 , C y ρ 3 , c ρ 1 , c ρ 2 , c ρ 3 )σ, (C y[j] ) | y|, aΠ j ) 3. Reconstruct the proof Πj 4. Reject if Cy = |y|-1 i=0 2 i C y[i]
for ρ ∈ [1, σ] : 5. runs the MPC protocol to reconstruct w ρ e from w ρ e+1 , k ρ e , k ρ e+1 6. obtains y ρ e = Output(we),

y ρ e+1 = Output(we+1) 7. Computes β ρ = ye ⊕ ye+1 8. Computes C ρ z = |y|-1 i=0 2 i C y[i]⊕β ρ [i] 9. Reject if C y ρ e+2 = Com(0, rz) + C ρ z
Reconstruct a and reject if e = h(a) Fig. 5. Our second protocol. When the Verifier reconstructs the challenge in the final step, he computes the commitments and can check that their openings were correct.

are randomized to provide the Zero-Knowledge property. Hence, the verifier can compute the other gates by himself but he needs the output of the AND gates to recompose a complete view and check the consistency of the proof. The views sent by the prover then only contain the output of the AND gates.

Our implementation. We implemented the circuit part of our CopraZK protocol on top of the ZKBoo code, available at https://github.com/Sobuno/ZKBoo. This code provides ZKBoo versions for elementary operations. These functions operate on three views and each binary AND call is randomized as recommended in the ZKBoo description. The code provides ZKBoo versions of operations on 32 bits vectors: addition, XOR, AND, addition with a constant. They also provide a ZKBoo version of a SHA 256 circuit, that comprises around 23300 binary AND gates. We implemented a ZKBoo version for the HMAC function, with two calls to SHA 256, and a 256-bit addition. The function HMAC corresponds to HKDFexpand when the desired output length equals the output length of the underlying hash function. Our final circuit, with input x and a computes t 1 = x + a and t 2 = HMAC(x) + HMAC(a) for a total of 93696 AND gates. We did not implement the modular reduction. However, as we expect our entries x and a (similarly HMAC(x) and HMAC(a)) to be in the cyclic group Z/qZ (using solutions described in Appendix C), t 1 and t 2 may only exceed q by one q. Hence modular reduction can be instantiated as a comparison and subtraction if necessary. Using Cingulata (a compiler toolchain for homomorphic encryption, available at https://github.com/CEA-LIST/Cingulata), we estimated the number of AND gates for this operation on 8 and 16 bits integers, and obtained respectively 48 and 103 AND gates. From this result, we can expect that a modular reduction on 256 bits integer can be implemented using around 2000 AND gates. This number being far from representative in our circuit, we did not considered this operation in a basic implementation. We consider the running time for a soundness parameter σ = 80 (corresponding to a soundness error of 2 Our tests were run on a Dell laptop with Processor IntelCore i7-7600U CPU running a single core at 2, 8 Ghz with 15.5 GB of RAM. Results are given in Table 2. We see that the prover's running time is better than the verifier's one, which is not the case in [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF], running ZKBoo on the mere SHA 256 circuit. Running a proof on a bigger circuit increases the verifier's load more than the prover's one. The running time of the prover is around half a second when the verification takes around 0.8 seconds. These results are better than what can be expected from SNARKs, as we explain in Appendix F. In [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF], the authors show that a parallelized implementation can seriously improve those results (with 8 threads, they divide the running time by 3.4 for the prover and by 5 for the verifier). This experimental proof size is larger but in Appendix F that it can be improved with optimized MPC in the head protocols.

Conclusion

In this work we provide a concrete solution to a practical problem that appears in the MLS specification. We describe how existing cryptographic tools such as ZK proofs and verifiable encryption can be combined to secure the update process. As the regular update of the group secret is the key to obtain the FS and PCS properties, we think our solution may be of interest. Additionally, we propose two protocols to obtain ZK proofs on circuit with committed input and output, such that our improvement proposal for MLS is settled on protocols as efficient as possible. Hence, an interesting way for future work is in the optimization of the verifiable encryption. The CL framework, introduced by Castagnos and Laguillaumie in [START_REF] Castagnos | Linearly homomorphic encryption from DDH[END_REF] and enriched with Zero-Knowledge properties in [14], that considers a cyclic group G where the DDH assumption holds together with a subgroup F of G where the discrete logarithm problem is easy, may provide novel and efficient solutions. Proposition 1 ( [START_REF] Giacomelli | ZKBoo: Faster zero-knowledge for Boolean circuits[END_REF]). The ZKBoo protocol is a Σ-protocol for the relation R φ , with 3-special soundness.

In [START_REF] Katz | Improved non-interactive zero knowledge with applications to post-quantum signatures[END_REF], a more efficient solution is proposed by considering a MPC solution with n virtual participants, instead of 3 in ZKBoo. The soundness error is also better for one round so that, less rounds are needed to reach the desired security level.

B Verifiable encryption

We recall here the formal definition of verifiable encryption as detailed in [START_REF] Camenisch | Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes[END_REF]. Let (KeyGen, Enc, Dec) be a probabilistic public key encryption scheme and (pk, sk) = KeyGen(1 λ ) a valid key pair. The verifiable encryption mechanism, attached to an encryption scheme (KeyGen, Enc, Dec), to the binary relation R and to the associated language L R = {(x, w) : R(x, w) = 1}, is defined as a two-party protocol Π between a prover P (who encrypts the data) and a couple composed of a verifier V on the one hand and a recovery algorithm Rec on the other hand. The protocol Π takes as public parameters a valid public key pk, a statement x and a security parameter λ. Let V P (pk, x, λ) denote the final out-put of V interacting with P on input (pk, x, λ). The recovery algorithm takes as input the secret key sk and V P (pk, x, λ).

Definition 2 (Secure Verifiable encryption). The couple protocol/recovery algorithm described above is a secure verifiable encryption scheme if the following holds:

-completeness: if P and V are honest, then V P (pk, x, λ) = ⊥ for all (pk, sk) valid key pair for the subsequent encryption scheme and x ∈ L R ; -validity: for all PPT malicious Prover P , all valid key pairs (sk, pk), Pr[R(x, Rec(sk, V P (pk, x, λ))] = 1 and V P (pk, x, λ) = ⊥ is negligible; -computational Zero-Knowledge: for every unbounded malicious Verifier Ṽ , there exists an expected poly-time Simulator Sim Ṽ with black-box access to Ṽ such that for all distinguisher A, all positive polynomial p(•), all x ∈ L and all sufficiently large λ we have:

Pr[A(pk, x, α i ] = i : (pk, sk) = KeyGen(1 λ ), α 0 = V P (pk, x, λ), α 1 = Sim Ṽ (pk, x, λ), i ∈ {0, 1} ≤ 1 2 + 1 p(λ) .
Informally, validity ensures that a malicious prover P * will always be caught, except with negligible probability, because the recovery algorithm shall be able to compute a witness. The recovery success guaranties that the decryption will be correct. In the soundness property of ZKPoK, one needs a third party, the extractor, to unmask a cheating prover. We also note that the revelation process "kills" the Zero-Knowledge feature of the proof. Verifiable encryption follows the same rules, except that the third party -the recovery algorithm -needs an additional ingredient : the secret key sk. The verifier is not supposed to be honest here.

The Camenish-Damgård verifiable encryption scheme In Figure 7, we describe the verifiable encryption solution given in [START_REF] Camenisch | Verifiable encryption, group encryption, and their applications to separable group signatures and signature sharing schemes[END_REF], adapted to the Σprotocol dedicated to a Pedersen commitment.

As for any cut-and-choose protocols, the probability that a cheating prover wins is 1 2 for one round. One has to repeat the protocol σ times to obtain a cheating probability (a validity error) of 2 -σ . The protocol described in Figure 7 can be optimized by gathering all rounds in a single one as described in the original paper, dropping to O(log(σ)) the number of encryptions to store.

C Key size and group orders in MLS updates

In [?], several suitable cipher suites are described. We focus on one of them for a practical example, for a 128-bit security level. This suite uses X25519 for ECDH We design by deriveSK the application of SHA256 followed by the above transformation such that for any 32-byte sequence of random data X, deriveSK(X) is a valid secret key for X25519. The public key is obtained by multiplying the secret key by the base point of the curve. Hence, given a 32-byte secret X, DeriveKeyPair(X) = (deriveSK(X), deriveSK(X)P ). This last encoding can be integrated in the circuit computing the last derivation. We adopt this notation DeriveKeyPair(X) = (deriveSK(X), deriveSK(X)P ) independently from the curve targeted.

Group order and commitments. Considering an elliptic curve E on a base field of order p, together with a base point P of prime order q, the discrete logarithm problem is supposed to be hard in the subgroup P generated by P .

Curves are chosen such that q and p are close, but not equal. From now on, we consider commitments and discrete logarithm proofs in groups of order q. Considering X25519, a random element in {0, 1} 256 , interpreted as an integer, will not lie naturally in F q . We consider that rejection sampling can provide efficiently an element in F q , without introducing a non negligible bias on the distribution. Let X the element out of HKDF to be committed. The method consists in cancelling the first bits of X, obtaining X such that log 2 ( X) = log 2 (q) + 1 then discarding X if X > q -1. If the initial number of bits of X is sufficiently big compared to log 2 (q) (log 2 (X) > log 2 (q) + 64 as advised by the NIST for instance), then simply considering X mod q can be done without introducing a non negligible bias. For all intermediate values in the tree, one of the two above methods (depending on the curve) is available. The last step is the commitment of the secret key : sk = Encode(X). For this element, we directly consider the encoding provided with the curve. The commitment C sk of sk in a group of order q (the group P ) will result in the same implicit reduction modulo q than the computation of the public key. Then we can produce an AND ZK proof that the value committed to in C sk is the discrete log of the pk: P K{sk : C sk = skP + rQ ∧ pk = skP } where Q is an element in P such that its discrete log relatively to P is unknown, and r a random element in Z/qZ.

D Security definition of PRF

We detail in this Appendix the formal definitions for the security of a PRF. Our security definitions are related to the correlated robustness introduced by Ishai et al. [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF], and to the related-key attack (RKA) scenario described by Bellare and Kohno [9]. Our notion 1-varCI-ow, formalizes the fact that the equation eq 1 :

t 1 = f (x) -αf ( t2-x α
) is hard to solve. This will be of prime importance in the soundness proof. The reduction to Correlated Input one-wayness, accessible in the full version (shorturl.at/eDJMY), states that if it is difficult to find a solution only to a simple evaluation f ( t2-x α ), then it should not be easier to find a solution to eq 1 . Our 1-varRKA-wPRF notion follows the same path but on the indistinguishability side. It stipulates that the function f does not leak information when evaluated as f (x) -αf ( t2-x α ). This second notion is called when proving the Zero-Knowledge property. The reduction to RKA security, also given in the full version, tells that if f does not leak any information when evaluated on values f ( t2-x α ), then it does not leak more information when evaluated as eq 1 . This will be of prime importance in the proof of the Zero-Knowledge property, as the Simulator will not be able to compute t 1 and so will sample it at random. In real life, most of the widely used hash functions are build from compression functions, based on a keyed block cipher (SHA-2 family) or on an unkeyed block defined permutation (Keccak family). PRF are mostly derived from those kind of hash functions. This the case of the HKDF-expand function, built from HMAC and instantiated in MLS with a SHA family. If few literature exists concerning RKA or CI one-wayness for real-life PRF, we state that finding a preimage or correlations on inputs and outputs of a hash function is among the most difficult problem for symmetric cryptography experts.

The 1-varRKA-wPRF experiment Exp 1-varRKA-wPRF A,f,p . Let p be a prime, let f be a public efficiently computable function K × D → R such that there exists an embedding R → Z/pZ. Let A be a PPT adversary. The experiment runs as follows: SetUp. The Challenger samples a key k ←$ K, a random input r ←$ D and b ←$ {0, 1}. He sends D, R and r to A.

Queries Computation. For i ∈ [1, q] the adversary computes his queries q i = (α i , t 1,i ) ∈ K × K. He sends those queries to the Challenger. Answers. The Challenger samples g ←$ FF(K, D, R). For i ∈ [1, q] the Challenger answers to the query q i with a value t

2,i = f (k, r) -α i f ( k-t1,i αi , r) if b = 0, t 2,i = g(k, r) -α i g( k-t1,i αi , r) if b = 1.
Guess. A outputs a guess bit b. The Challenger accepts if b = b. Definition 3 (1-varRKA-wPRF security). Let f : K × D → R be an efficiently computable function. f is 1-varRKA-wPRF-secure if, for all adversary A, running in probabilistic polynomial time t and making at most q queries, the quantity Adv 1-varrka-wprf A,f,p (t, q) defined as:

Pr Exp 1-varRKA-wPRF A,f,p (t, q) = 1|b = 0 -Pr Exp 1-varRKA-wPRF A,f,p (t, q) = 1|b = 1 is negligible. The 1-varCI-ow experiment Exp 1-varCI-ow A,H,p
. Let p be a prime number, f be an efficiently computable function K × D → R, such that there exists an embedding R → Z/pZ and A a PPT adversary. The experiment rus as follows: SetUp. The Challenger selects a random key k and samples a random public input r. He sends r to A. Queries. For i ∈ [1, q] the adversary computes his queries q i = (α i , t 1,i ) ∈ K × K. He sends them to the Challenger. He receives a value t 2,i = f (k, r)α i f ( k-t1,i αi , r) ∈ R. Invert. A sends a couple (x, j) with x ∈ K and j the index of a query. The Challenger accepts if f (x, r) -α j f (

x-t1,j αj , r) = t 2,j .

Definition 4 (1-varCI-ow security). Let f : K × D → R be an efficiently computable function. f is said to be (q, t)-1-varCI-ow-secure if, for all adversary A running in PPT t and making q queries, the following advantage: Adv 1-varci-ow A,f,p (t, q) = Pr Exp 1-varCI-ow A,f,p (t, q) = 1 is negligible.

E Security of our zero-knowledge protocols

E.1 Theorem 1
We prove the security of the construction CopraZK construction, enunciated in Theorem 2, in a simulation based paradigm. Hence we confront an ideal world, represented by the ideal functionality defined in Figure 3 and the real world corresponding to the protocol. The output distributions of both the functionality and the protocol should be indistinguishable, even in the presence of the opening (y [j], r y [j] ) of the bit commitments C y[j] , for j ∈ [0, |j| -1]. From his knowledge of the r y [j] and the r yi he can recompose a valid randomnness r * such that y * , r * opens C y . Hence x * , r * is a valid extraction.

Zero-Knowledge. Again, we cannot directly call the Simulator of ZKBoo as the output of the circuit is not public. Instead we build a simulator that runs as the original ZKBoo simulator, and simulates two views w e and w e+1 for a fixed e and their associated outputs y e and y e+1 . He also generates the associated commitments with random values r ye , r y[e+1] The simulator also commits to random bit to generates the C y[j] except for the last that he computes as

C y [0] = C y - |y|-1 j=1 C y[j]
such that the relation is verified. He can produce all the proofs that the y[j] are bits except for y[0] for which he call the Simulator for Π 0 . With non negligible probabilities, the simulator obtains a valid transcript for the same challenge e. In a last step, he samples a random r z and, putting together C y , the C y[j] and a Com(0, r) he can produce the missing C ye+2 . As the only values our Simulator adds to the ZKBoo and the Π 0 simulations are Commitments, the hiding properties of the commitment scheme provides the indistinguishability between the simulation and a real execution of the protocol.

F Implementation optimization

The first improvement, ZKBoo++ is given in [START_REF] Chase | Post-quantum zero-knowledge and signatures from symmetric-key primitives[END_REF]. The authors meticulously analyse which data should be sent by the prover and which one can be directly computed by the verifier. They show that one can cut by more than half the size of the proof, at no computational cost. They implemented their solution on an optimized circuit for SHA 256 with 22272 AND gates and obtained a proof size of 618KB for a soundness error of 2 -128 (48% of ZKBoo proof size on the same circuit). For a soundness parameter σ = 80 they obtain 385KB. Considering this reduction, our own proof would drop to 1.6MB. Moreover, the optimized SHA 256 circuit enables to save around 4000 AND gates, cancelling the cost of the modular reduction. We now turn to the KKW protocol [START_REF] Katz | Improved non-interactive zero knowledge with applications to post-quantum signatures[END_REF]. The author use another MPC solution to decrease the number of rounds required to reach a desired soundness security. They show that the improvement one can expect on the size of the proof depends on the number of AND gates. Considering an average of 95000 AND gates for our circuit, the proof size drops by 70KB compared to ZKBoo++. Hence we could obtain proofs around 90KB.

F.1 Comparison with SNARKs solutions

Agrawal et al. proposed in [1] a ZK protocol mixing algebraic commitments on input and output and circuit evaluation (comIOSnark). It is worth comparing their solution to ours. No implementation is available in [1], however they estimate the prover's work to four exponentiation in addition to the number of exponentiations for computing the SNARK proof when the Verifier has to perform 4 exponentiations and 30 pairings. To compare to more practical results, we consider the protocol Pinocchio [START_REF] Parno | Pinocchio: Nearly practical verifiable computation[END_REF], on which the protocol of [1] bases its description. The implementation for Pinocchio is performed on a single core of a 2.67 GHz Intel Core i7 with 8 GB of RAM, which is comparable to our test setting. A proof on a SHA 1 evaluation with 23785 multiplication gates requires, first, a public key generation of 11 seconds. The proof computation takes 15.7 seconds. As expected however, the Verifier 's running time is only around 10ms and the proof size is 288. Even if optimizations can be performed, the Prover 's work is far more important than in our solution. Hence we believe that, depending on the applications targeted, either one or the other solution might be of interest.

Fig. 3 .

 3 Fig. 3. The ideal functionality F f,Com .

Fig. 4 .

 4 Fig. 4. The CopraZK protocol. The reconstruction of the algebraic proof means the verification by reconstruction of the challenge in the Fiat-Shamir version.

  |y| + 2σ) algebraic operations to the basic ZKBoo++ proof. The work of Backes et al. and our extension rely on a result given by the homomorphic property of a commitment scheme such as Pedersen scheme. For any scalar k, and any two commitments Com(x, r x ), Com(y, r y ), k • Com(x, r x ) + Com(y, r y ) = Com(kx + y, kr x + r y ). For any commitment C b = Com(b, r b ) to a secret bit b and any public bit β, one can easily compute the commitment of b ⊕ β as follows: if β = 0, C b⊕β = C b and if β = 1 then

  r y[i] return p = (e, (b ρ , z ρ , r ρ z )ρ), (zΠ j )j . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Verifier (a, p) 1. Parse p as e, (b ρ

Fig. 6 .

 6 Fig. 6. The protocol ZKBoo++. Share and Output are functions specific to the (2,3)decomposition defined in ZKBoo. (We omit the index for the Output.)

Fig. 7 .

 7 Fig.7. The simple version of verifiable encryption scheme. The Verifier knows a public commitment to x, Cx and a public key pk. The Prover proves knowledge of the encrypted message x and of the random r used in the commitment Cx.

  As a child knows the secret key sk i for each of its ancestors, B will only have to perform three encryptions, one for each secret. He encrypts ps 2 under pk A , ps 4 under pk 6 and ps root under pk 12 . From ps 2 (respectively ps 4 ), A (resp. C) shall be able to compute the root secret. We recall that from this root secret is derived a new epoch secret S E+1 . Before sending his Commit, B computes S E+1 and uses it to produce a confirmation key. This value shall enable A and C to check that they have derived the correct root secret and so, that they received a correct update. Other mechanisms such as the transmission of the updated view of the tree, or of intermediate hash values are provided for a user to check that he received a correct update. However, all those mechanisms enable a verification after receiving the update information.

, B has to send ps 2 to A, ps 4 to nodes C and 6 and ps root to nodes E, 10, F, 12, G, 14, H.

  To extend the proof to the complete tree, one has to repeat the above steps for each level. To certify the update value ps 4 corresponding to the parent node 4, B will send the server values C 4 , C sk 4 , pk 4 , the proof Π 4 = P K{ps 2 , r 2 , r 4 , r sk 4 :

r y )} for any PRF f . Then B can send to the server the public values C B , C 2 , C sk 2 , pk 2 together with a proof Π 2 = PK{ps B , r B , r 2 , r sk 2 : C B = Com(ps B , r B )∧C 2 = Com(H p (ps B ), r 2 )∧C sk 2 = Com(deriveSK(H p (ps B )), r sk 2 )∧ pk 2 = deriveSK(H p (ps B ))P } (the last part of the proof being a classic discrete log proof). In addition, verifiable encryption (detailed in section 2) allows to link the message encrypted with VerifEnc with the data committed in C 2 . To sum up, B will send for a node update, the public values C B , C 2 , C sk 2 , and pk 2 , the proof Π 2 together with VerifEnc Enc,pk A (ps 2 ). If the server accepts the proof, then he transmits the public key pk 2 as well as VerifEnc Enc,pk A (ps 2 ) to A.

Table 1 .

 1 Considering ZKBoo, the prover effort is O(σ|F |) symmetric operations, where |F | is the number of AN D gates of the circuit and σ the number of rounds. Our solution requires O(σ(2|F | + |mod|)) + 8 symmetric operations and 20 public key operations, where |mod| is the size of the circuit for a modular addition. We show in section 5 that |mod| is negligible compared to |F | and finally, our solution requires on the prover side (O(2σ|F |) symmetric + 20 public key operations. The computational cost is dominated by the symmetric part. The size of the proof and the work on the verifier's side are also dominated by the circuit part. One inconvenient is that it is limited to PRF evaluation and that the security proof requires non usual hypothesis on PRF. Comparison of the efficiency of the different solution for Circuit proof on committed input and output. pub stands for the cost of a public key operation (multiplication and addition on the curve for instance), while sym stands for the cost of a symmetric operation. |F | is the circuit size, |x| the input size and |y| the output size. In most applications, |F | >> (|x|, |y|, λ).

		Non	No	Prover's work	Verifier's work	Proof size
		inter-	CRS
		active
	SNARK
	based [1]
	CopraZK	yes	yes O(2|F |λ • sym)	O(2|F |λ • sym)	O(2|F |λ)
	ComInOutZK yes	yes O(|F |λ • sym +	O(|F |λ • sym + (|x| +	O((|F | + |x| +
				(|x| + |y| + λ) • pub)	|y| + λ) • pub)	|y| + λ)λ)

On the opposite side, ComInOutZK is valid for any circuit, only requires equivocality of the commitment scheme, which is a common hypothesis, and leaves the circuit evaluation untouched. But it requires a non negligible number of algebraic commitments. Considering |x| (respectively |y|) the bit size of the input (of the output), we obtain on the prover side O(|x| + |y| + 2σ) public key operations and O(σ|F |) symmetric operations. The verifier's work is equivalent. The proof size of ZKBoo is augmented with O(|x| + |y| + 6σ) curve points which is asymptotically O((|x| + |y| + λ)λ) as σ augments with λ. We compare in Table

1

our two solutions with the SNARK based solution of

[1]

. yes no O((|F | + λ) • pub) O((|x| + |y| + λ) • pub) λ

Table 2 .

 2 -80 ), requiring 136 rounds. Running meantime of the Prover and the Verifier over 1 000 executions for 136 rounds.

	Prover (ms)	Verifier (ms)
	Generating random	21 Loading file	1
	Sharing secrets	1 Generating challenge 0
	Running circuit	534 Verifying	799
	Committing	20
	Total generating proof data 578 Total verifying	800
	Proof size (MB)	3.3

A ZKBoo

We recall here the construction of the protocol ZKBoo. A (2,3)-decomposition is a set of functions that separates the evaluation of a function into three symmetric parts such that, given any two parts, nothing is revealed about the third one, and so on the input. Definition 1 ((2,3)-decomposition). A (2,3)-decomposition for the function φ is a set of functions D = (Share, Output 1 , Output 2 , Output 3 , Rec)∪F, such that:

-Share is an onto function that splits the input x into 3 shares;

-F is a finite family of efficiently computable functions described as {φ j 1 , φ j 2 , φ j 3 } j∈[1,N ] ; -Output i computes a value y i called the output share; -Rec computes the final value y = φ(x) from y 1 , y 2 and y 3 .

A (2,3)-decomposition produces three distinct views w e , each composed of an input share x e and the output values of the corresponding intermediate functions φ j e 's. Two properties are required from a decomposition: correctness and 2-privacy. The first means that the decomposition allows to correctly evaluate the function. The second guarantees that given any two views, one cannot learn the secret input x. ZKBoo is built over the decomposition. Briefly, the prover commits to the views and only reveals two of them. A soundness error of 2 -σ , i.e. the probability for a cheating prover not to be caught is less than 2 -σ , is obtained by repeating the process t = σ/(log 2 3 -1) times. The size of the proof is essentially the size of the 2 views, thus depends on the size of the circuit. ZKBoo++ ( [START_REF] Chase | Post-quantum zero-knowledge and signatures from symmetric-key primitives[END_REF]) improves the original protocol by cutting by half the size of the proof. The authors obtain such a result by avoiding sending in the proof any value that the verifier can compute himself. Figure 6 gives a detailed description of the improved version ZKBoo++. an adversary. To prove this, we use a Simulator that operates the transition from the ideal world to the real one. Note that it is possible to directly build an extractor from distinct transcripts, following the same reasoning, but it seemed to us less intuitive to expose. We give a sketch of proof, the detailed proof can be found in the full version (shorturl.at/eDJMY). As m is a common public input, we write f (x) for f (x, m). Corrupted prover P * : soundness. We first describe a Simulator, interacting with a corrupted prover and having access to all the extractable information, calling as a subroutine the extractors for ZKBoo and for the proof Π on three accepting transcripts (a, e 1 , p 1 ), (a, e 2 , p 2 ), (a, e 3 , p 3 ). This Simulator obtains the desired witnesses and sends them to the functionality only if he is sure that they are correct. Facing the Simulator, P * has no chance to cheat (no statement without a correct witness can lead to an accept). Then, following a game based reduction, we show that the view of P * playing with this Simulator is indistinguishable from the view of P * playing in the real protocol. The key point is when the Simulator does not check the equality between the values extracted from ZKBoo and the values extracted from the algebraic commitment, and only rely on the relations given by the tag values. There we show that the 1-varCI-ow-security of f induces the equalities. As the Simulator does not use its extraction knowledge, he acts as a real verifier.

Corrupted verifier V * : Zero-Knowledge. We describe how a Simulator facing a corrupted verifier manages to provide a view that is indistinguishable from a real protocol execution view. The Simulator first acts as if he did not know the witness x and the opening informations r x , r y . Then by successive games we go back to the original protocol. The transition from the Simulation to the real protocol consists in substituting, step by step, the random witness and correlated values used by the Simulator by real values. For each step, we show that there is little chance that the corrupted verifier sees any difference (the probability of distinguishing the two distributions is bounded by a negligible value that depends on the security of the underlying functions). For most of the transcript, the indistinguishability is obtained by calling the hiding property of the commitment scheme and the ZK knowledge property of ZKBoo and Π. However, this is not the case for t 1 , t 2 . For those elements, we show that 1-varRKA-wPRF security provides us with the desired indistinguishability.

E.2 Theorem 2

Again, we give a sketch of the proof. A detailed proof can be found in the full version (shorturl.at/eDJMY). Correctness follows by inspection. Soundness. Considering the soundness, an extractor accessing three distinct accepting transcripts works as follows. In a first step it acts as the ZKBoo extractor and uses the transcripts to recompose a value x * = x 1 ⊕ x 2 ⊕ x 3 and a value y * = y 1 ⊕ y 2 ⊕ y 3 such that y * = f (x * ). From the equivocality of the commitment, he also knows that the two randomness given in each transcript only corresponds to 3 random values r yi such that (y i , r yi ) opens C yi . In a second step, the simulator extracts