<figure><img src="image_1.png" /></figure>

**HAL**
open science

Secure Keyless Multi-Party Storage Scheme

Pascal Lafourcade, Lola-Baie Mallordy, Charles Olivier-Anclin, Léo Robert

► To cite this version:

Pascal Lafourcade, Lola-Baie Mallordy, Charles Olivier-Anclin, Léo Robert. Secure Keyless Multi-Party Storage Scheme. ESORICS: European Symposium On Research In Computer Security, Sep 2024, Bydgoszcz, Poland. hal-04540895

HAL Id: hal-04540895

https://hal.science/hal-04540895

Submitted on 10 Apr 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Secure Keyless Multi-Party Storage Scheme

Pascal Lafourcade, Lola-Baie Mallordy, Charles Olivier-Anclin, Léo Robert

► To cite this version:

Pascal Lafourcade, Lola-Baie Mallordy, Charles Olivier-Anclin, Léo Robert. Secure Keyless Multi-Party Storage Scheme. ESORICS: European Symposium On Research In Computer Security, Sep 2024, Bydgoszcz, Poland. pp.279-298, 10.1007/978-3-031-70896-1_14. hal-04540895

HAL Id: hal-04540895

https://hal.science/hal-04540895v1

Submitted on 10 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Secure Keyless Multi-Party Storage Scheme

Pascal Lafourcade¹[0000-0002-4459-511X], Lola-Baie Mallordy¹[0009-0005-1308-4412], Charles Olivier-Anclin¹,²,⁴[0000-0002-9365-3259], and Léo Robert³[0000-0002-9638-3143]

¹ Université Clermont Auvergne, LIMOS, CNRS, Clermont-Ferrand, France

² be ys Pay

³ Université de Picardie Jules Verne, Amiens, France

⁴ LIFO, Université d'Orléans, INSA Centre Val de Loire, Bourges, France

**Abstract.** Using threshold secret sharing, we propose a solution tailored for forgetful clients (i.e., not required to keep any cryptographic secret) while accommodating the dynamic nature of multi-cloud deployments. Furthermore, we delegate the computation and distribution of shares to an intermediate server (proxy), effectively minimizing the client workload. We propose two variants of a keyless, space-efficient multi-cloud storage scheme named KAPRE and KAME. Our solution KAPRE requires less communications and computations, while KAME preserves data confidentiality against a colluding proxy. Our protocols offer robust guarantees for data integrity, and we demonstrate the proxy's ability to identify and attribute blame to servers responsible for sending corrupted shares during data reconstruction. We establish a comprehensive security model and provide proofs of the security properties of our protocols. To complement this theoretical analysis, we present a proof-of-concept to illustrate the practical implementation of our proposed scheme.

## 1 Introduction

Cloud storage services like Amazon S3, OVHcloud, or Google Drive are increasingly popular, both among companies and users to store large amounts of sensitive data. However, handing data over to a single third party often raises availability, integrity and confidentiality issues [31, 22]. The user does not want to neither lose access to its data in case of server failure, nor retrieve data that has been altered in any way (maliciously or not). It also should not have to reveal any of its sensitive content to the *Cloud Storage Provider* (CSP). Multi-cloud, the simultaneous use of several cloud services, counterbalances data centralisation [9]. It introduces redundancy in the stored data, hence providing availability and integrity even in the case of several server failures (e.g., as in Strasbourg, France where several OVH servers were destroyed in a fire).

Numerous solutions exist to ensure data confidentiality within multi-cloud architecture. The seminal work of Shamir on secret sharing [32] showed an elegant solution to split a file into shares and to distribute them to a set of CSPs. It provides information-theoretic secrecy [25], meaning that no party can learn
# Secure Keyless Multi-Party Storage Scheme

Pascal Lafourcade¹[0000-0002-4459-511X], Lola-Baie

Mallordy¹[0009-0005-1308-4412], Charles Olivier-Anclin¹,²,⁴[0000-0002-9365-3259],
and Léo Robert³[0000-0002-9638-3143]

¹ Université Clermont Auvergne, LIMOS, CNRS, Clermont-Ferrand, France

² be ys Pay

³ Université de Picardie Jules Verne, Amiens, France

⁴ LIFO, Université d'Orléans, INSA Centre Val de Loire, Bourges, France

**Abstract.** Using threshold secret sharing, we propose a solution tailored for forgetful clients (i.e., not required to keep any cryptographic secret) while accommodating the dynamic nature of multi-cloud deployments. Furthermore, we delegate the computation and distribution of shares to an intermediate server (proxy), effectively minimizing the client workload. We propose two variants of a keyless, space-efficient multi-cloud storage scheme named KAPRE and KAME. Our solution KAPRE requires less communications and computations, while KAME preserves data confidentiality against a colluding proxy. Our protocols offer robust guarantees for data integrity, and we demonstrate the proxy's ability to identify and attribute blame to servers responsible for sending corrupted shares during data reconstruction. We establish a comprehensive security model and provide proofs of the security properties of our protocols. To complement this theoretical analysis, we present a proof-of-concept to illustrate the practical implementation of our proposed scheme.

# 1 Introduction

Cloud storage services like Amazon S3, OVHcloud, or Google Drive are increasingly popular, both among companies and users to store large amounts of sensitive data. However, handing data over to a single third party often raises availability, integrity and confidentiality issues [31, 22]. The user does not want to neither lose access to its data in case of server failure, nor retrieve data that has been altered in any way (maliciously or not). It also should not have to reveal any of its sensitive content to the *Cloud Storage Provider* (CSP). Multi-cloud, the simultaneous use of several cloud services, counterbalances data centralisation [9]. It introduces redundancy in the stored data, hence providing availability and integrity even in the case of several server failures (e.g., as in Strasbourg, France where several OVH servers were destroyed in a fire).

Numerous solutions exist to ensure data confidentiality within multi-cloud architecture. The seminal work of Shamir on secret sharing [32] showed an elegant solution to split a file into shares and to distribute them to a set of CSPs. It provides information-theoretic secrecy [25], meaning that no party can learn
anything about the content of the data without the cooperation of the others. A perk of secret sharing is that its security relies on the need of other parties' cooperation rather than on the knowledge of a cryptographic secret. Hence, the security of the data does not rely on any cryptographic secret. Otherwise, this can lead to great loss, as in cryptocurrencies where losing the secret key results in the inability to access the money.

Despite its security, secret sharing is memory-consuming, as the shares must be as large as the secret. This means that storing a secret $S$ of size $|S|$ requires $|S|$ storage space for each CSP, which scales poorly. Memory-efficient algorithms as Rabin's Information Dispersal Algorithm [28] (IDA) produce shares of optimal size, which depends on the number of shares needed to reconstruct the initial data. They achieve high fault-tolerance and small buffer size, but they were often not designed to provide confidentiality [29].

In multi-cloud setting, delegating the sharing and reconstruction of its data to a third party can benefit the user. For the user, it can be a hassle to communicate with each CSP, distribute its data and check the CSPs availability for download. This task is even more complicated if the user wants to make sure its data has not been altered during recovery and detect any corrupted share. All of this can be delegated to a proxy (a particular CSP with additional tasks). However, if the client does not trust the CSPs with its data content, it should not have to trust the proxy either. A solution can be to encrypt the data before sending it to the proxy with a block cipher [10]. But, as the key is needed for data retrieval, this shifts the problem from protecting the files to protecting the key: if the key is compromised, so is the data.

We tackle the problem of storage in multi-cloud infrastructure, where the client delegates most of the computations to an untrusted proxy, which handles the communications with the CSPs. The data must remain: (1) confidential, (2) available even if some of the CSPs are unavailable, (3) unaltered, any modification must be detected, and (4) liable to the entity that produce a fault. We consider a forgetful user, so no security values are stored between the upload and the download phases (e.g., long-term keys or hashes for integrity). The keyless design not only simplifies the overall storage infrastructure but also eliminates the risk of key exposure, reducing the attack surface and enhancing the overall security.

**Our Contributions.** We design a *Keyless Multi-Party Storage* (KMPS) scheme, depicted in Fig. 1, to split client's data through $n+1$ shareholders (one proxy and $n$ providers) such that only $k \le n+1$ of them are needed for data recovery. We enforce data confidentiality with regards to the proxy and up to $k-1$ colluding CSPs. We prove the size of the shares is almost optimal ($|S|/k+\lambda$ for initial data of size $|S|$ and the security parameter $\lambda$). We expect a setup independent of any long-term key, nor any additional value to check data integrity. Thanks to the proxy, we minimise the computations and communication overhead on client-side. To our knowledge, there is no multi-cloud storage protocol delegating all the communications and most of computations to a proxy with a keyless client, while guaranteeing data's integrity without storing any additional value.
anything about the content of the data without the cooperation of the others. A perk of secret sharing is that its security relies on the need of other parties' cooperation rather than on the knowledge of a cryptographic secret. Hence, the security of the data does not rely on any cryptographic secret. Otherwise, this can lead to great loss, as in cryptocurrencies where losing the secret key results in the inability to access the money.

Despite its security, secret sharing is memory-consuming, as the shares must be as large as the secret. This means that storing a secret $S$ of size $|S|$ requires $|S|$ storage space for each CSP, which scales poorly. Memory-efficient algorithms as Rabin's Information Dispersal Algorithm [28] (IDA) produce shares of optimal size, which depends on the number of shares needed to reconstruct the initial data. They achieve high fault-tolerance and small buffer size, but they were often not designed to provide confidentiality [29].

In multi-cloud setting, delegating the sharing and reconstruction of its data to a third party can benefit the user. For the user, it can be a hassle to communicate with each CSP, distribute its data and check the CSPs availability for download. This task is even more complicated if the user wants to make sure its data has not been altered during recovery and detect any corrupted share. All of this can be delegated to a proxy (a particular CSP with additional tasks). However, if the client does not trust the CSPs with its data content, it should not have to trust the proxy either. A solution can be to encrypt the data before sending it to the proxy with a block cipher [10]. But, as the key is needed for data retrieval, this shifts the problem from protecting the files to protecting the key: if the key is compromised, so is the data.

We tackle the problem of storage in multi-cloud infrastructure, where the client delegates most of the computations to an untrusted proxy, which handles the communications with the CSPs. The data must remain: (1) confidential, (2) available even if some of the CSPs are unavailable, (3) unaltered, any modification must be detected, and (4) liable to the entity that produce a fault. We consider a forgetful user, so no security values are stored between the upload and the download phases (e.g., long-term keys or hashes for integrity). The keyless design not only simplifies the overall storage infrastructure but also eliminates the risk of key exposure, reducing the attack surface and enhancing the overall security.

**Our Contributions.** We design a *Keyless Multi-Party Storage* (KMPS) scheme, depicted in Fig. 1, to split client's data through $n+1$ shareholders (one proxy and $n$ providers) such that only $k \le n+1$ of them are needed for data recovery. We enforce data confidentiality with regards to the proxy and up to $k-1$ colluding CSPs. We prove the size of the shares is almost optimal ($|S|/k+\lambda$ for initial data of size $|S|$ and the security parameter $\lambda$). We expect a setup independent of any long-term key, nor any additional value to check data integrity. Thanks to the proxy, we minimise the computations and communication overhead on client-side. To our knowledge, there is no multi-cloud storage protocol delegating all the communications and most of computations to a proxy with a keyless client, while guaranteeing data's integrity without storing any additional value.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Overview of KMPS upload and download phases for $k = 3, n + 1 = 4$ (Here we consider that the proxy also holds a share, just as the CSPs).</figcaption></figure>

**KMPS Threat model:** Let $k$ be the secret sharing threshold and $n$ the number of providers. We define a generic model for a KMPS scheme formalizing strong security properties, namely:

**$N$-collusion-secrecy:** a proxy colluding with $N$ providers cannot learn anything on the client's data. We assume the proxy follows the protocol during the upload.

**Provider-secrecy:** a collusion of $k-1$ malicious providers cannot learn anything on the client's data.

**User-Integrity:** any collusion of the proxy with less than $k-2$ malicious providers cannot alter the data without the user noticing. The proxy is assumed to follow the protocol during upload.

**Accountability:** if a share has been corrupted, the proxy will detect it and blame the corresponding CSP with overwhelming probability.

We leave open the design of a system that allows a malicious proxy to handle user data during upload, without compromising security and integrity.

**Two protocols:** We propose two KMPS variants, KAPRE (Keyless Archivage with Proxy REencryption) relying on homomorphic proxy re-encryption [14] and KAME (Keyless Archivage with Multikey Encryption) relying on homomorphic multikey encryption [27]. Both rely on Shamir's secret sharing [32] and an IDA [28]. Our two solutions balance in between efficiency and security. Indeed, KAPRE is round optimal in communications but some trust should be kept toward the proxy while KAME requires less trust in the proxy, but has an additional round of communication. We formally model and prove the security of our protocols. We prove that both schemes provide accountability and user-integrity. As for data's secrecy, we show that KAPRE has 0-collusion secrecy and provider-secrecy while KAME achieves $(k-2)$-collusion secrecy.
<figure><img src="image_1.png" /><figcaption>**Fig. 1.** Overview of KMPS upload and download phases for $k = 3, n + 1 = 4$ (Here we consider that the proxy also holds a share, just as the CSPs).</figcaption></figure>

**KMPS Threat model:** Let $k$ be the secret sharing threshold and $n$ the number of providers. We define a generic model for a KMPS scheme formalizing strong security properties, namely:

**$N$-collusion-secrecy:** a proxy colluding with $N$ providers cannot learn anything on the client's data. We assume the proxy follows the protocol during the upload.

**Provider-secrecy:** a collusion of $k-1$ malicious providers cannot learn anything on the client's data.

**User-Integrity:** any collusion of the proxy with less than $k-2$ malicious providers cannot alter the data without the user noticing. The proxy is assumed to follow the protocol during upload.

**Accountability:** if a share has been corrupted, the proxy will detect it and blame the corresponding CSP with overwhelming probability.

We leave open the design of a system that allows a malicious proxy to handle user data during upload, without compromising security and integrity.

**Two protocols:** We propose two KMPS variants, KAPRE (Keyless Archivage with Proxy REencryption) relying on homomorphic proxy re-encryption [14] and KAME (Keyless Archivage with Multikey Encryption) relying on homomorphic multikey encryption [27]. Both rely on Shamir's secret sharing [32] and an IDA [28]. Our two solutions balance in between efficiency and security. Indeed, KAPRE is round optimal in communications but some trust should be kept toward the proxy while KAME requires less trust in the proxy, but has an additional round of communication. We formally model and prove the security of our protocols. We prove that both schemes provide accountability and user-integrity. As for data's secrecy, we show that KAPRE has 0-collusion secrecy and provider-secrecy while KAME achieves $(k-2)$-collusion secrecy.
**Implementation:** We provide an implementation of our two solutions. This allows us to give an overview of the efficiency, and show a linear complexity on the user-side for both schemes.

**External authentication.** Our security model does not consider user's authentication. In download, any user could retrieve another user's data so we assume authentication throughout the protocol. Hence, our schemes are compatible with any pre-existing identity system such as mutual TLS [30] or other solutions [21].

**Related Work.** Usually, multi-cloud storage protocols security relies on the user encrypting its data before storing it, often with a symmetric encryption for cost efficiency [37, 26, 19]. This preserves data's privacy against the CSPs. The user must keep long-term keys, which shifts the concern of protecting data to protect the keys. To tackle this issue, the authors in [23] use a *Credentials-less Permission Mechanism*. While the user has access to its key, it uses it to actively block any demand for a new key generation. Hence, if the user loses its key, there is no one to block its request for a new one. However, this system can be broken if the attacker guesses whenever the user loses its key, and outruns the user in its request for a new key. Filecoin [5] is another example of using long-term keys. Filecoin is a decentralized storage network using blockchain to provide privacy, proof of spacetime and replication. Yet, the use of blockchain makes their protocol quite slow and prevents from deleting data. We prefer a solution which does not require the user to keep any cryptographic secret.

Some multi-cloud storage protocols use secret sharing to ensure confidentiality without permanent keys [10, 22]. However, the secret sharing must be done by a trusted party, i.e., the user itself, hence no delegation is possible. Additionally, secret sharing is not memory efficient. The authors of [22] proposed an improved variant of Shamir's secret sharing achieving a storage ratio of about 2 to 4 times the initial data size, this is still far for the optimal ratio of $n/k$ which we achieve. Krawczyk proposed a solution to obtain small shares by pairing an information-theoric secret sharing with erasure codes [17]. His scheme is used in both [9, 10]. Their protocol encrypts the user's data with a symmetric encryption, and distributes it with an erasure code for each CSP. The key is shared with a secret sharing. However, in these schemes all the sharing must be done by the user itself or a fully trusted third-party, when our solution relieves the user from these tasks. When multi-cloud protocols involve a proxy, it is usually a trusted-party [36, 26, 38]. Some protocols only consider server failure in their threat model [34, 24]. They aim for efficiency and data's availability, and do not consider confidentiality or trust issues. Some protocols do consider data's confidentiality w.r.t. individual cloud providers, but do not consider colluding CSPs [35]. Our model addresses all of these cases, as we consider the proxy as trustworthy as any other CSP.

Regarding integrity, most storage protocols also rely on keeping long-term values as hashes [37, 19], or long-term keys by signing the data [22, 38]. For example, the solution in [38] uses blockchain to provide integrity, which makes it quite slow. Also, the user must keep a secret key to sign its data, which we want
**Implementation:** We provide an implementation of our two solutions. This allows us to give an overview of the efficiency, and show a linear complexity on the user-side for both schemes.

**External authentication.** Our security model does not consider user's authentication. In download, any user could retrieve another user's data so we assume authentication throughout the protocol. Hence, our schemes are compatible with any pre-existing identity system such as mutual TLS [30] or other solutions [21].

**Related Work.** Usually, multi-cloud storage protocols rely on the user encrypting its data before storing it, often with a symmetric encryption for cost efficiency [37, 26, 19]. This preserves data's privacy against the CSPs. The user must keep long-term keys, which shifts the concern of protecting data to protect the keys. To tackle this issue, the authors in [23] use a *Credentials-less Permission Mechanism*. While the user has access to its key, it uses it to actively block any demand for a new key generation. Hence, if the user loses its key, there is no one to block its request for a new one. However, this system can be broken if the attacker guesses whenever the user loses its key, and outruns the user in its request for a new key. Filecoin [5] is another example of using long-term keys. Filecoin is a decentralized storage network using blockchain to provide privacy, proof of spacetime and replication. Yet, the use of blockchain makes their protocol quite slow and prevents from deleting data. We prefer a solution which does not require the user to keep any cryptographic secret.

Some multi-cloud storage protocols use secret sharing to ensure confidentiality without permanent keys [10, 22]. However, the secret sharing must be done by a trusted party, i.e., the user itself, hence no delegation is possible. Additionally, secret sharing is not memory efficient. The authors of [22] proposed an improved variant of Shamir's secret sharing achieving a storage ratio of about 2 to 4 times the initial data size, this is still far for the optimal ratio of $n/k$ which we achieve. Krawczyk proposed a solution to obtain small shares by pairing an information-theoretic secret sharing with erasure codes [17]. His scheme is used in both [9, 10]. Their protocol encrypts the user's data with a symmetric encryption, and distributes it with an erasure code for each CSP. The key is shared with a secret sharing. However, in these schemes all the sharing must be done by the user itself or a fully trusted third-party, when our solution relieves the user from these tasks. When multi-cloud protocols involve a proxy, it is usually a trusted-party [36, 26, 38]. Some protocols only consider server failure in their threat model [34, 24]. They aim for efficiency and data's availability, and do not consider confidentiality or trust issues. Some protocols do consider data's confidentiality w.r.t. individual cloud providers, but do not consider colluding CSPs [35]. Our model addresses all of these cases, as we consider the proxy as trustworthy as any other CSP.

Regarding integrity, most storage protocols also rely on keeping long-term values as hashes [37, 19], or long-term keys by signing the data [22, 38]. For example, the solution in [38] uses blockchain to provide integrity, which makes it quite slow. Also, the user must keep a secret key to sign its data, which we want
<table><caption>**Fig. 2.** Comparison of existing storage schemes (Proxy: the file splitting is delegated to a proxy, CSP: confidentiality is preserved against CSPs colluding, Coll: confidentiality is preserved against the proxy colluding with CSPs, Keyless: the client does not hold permanent key, Integrity: whether/how data integrity is checked).</caption><thead><tr><th></th><th>Proxy</th><th>CSPs</th><th>Coll.</th><th>Keyless</th><th>Integrity</th></tr></thead><tbody><tr><td>[37]</td><td><b>X</b></td><td>✓</td><td>–</td><td><b>X</b></td><td>Merkle Tree</td></tr><tr><td>[23]</td><td>✓</td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>[35]</td><td><b>X</b></td><td><b>X</b></td><td>–</td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>[26, 19]</td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td><td>Hashes [19]</td></tr><tr><td>[22, 10, 13]</td><td><b>X</b></td><td>✓</td><td>–</td><td>✓</td><td>Signature [22], Quorum [10]</td></tr><tr><td>[36]</td><td>✓</td><td><b>X</b></td><td><b>X</b></td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>[38]</td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td><td>Signature</td></tr><tr><td>KAPRE</td><td>✓</td><td>✓</td><td><b>X</b></td><td>✓</td><td>auth. encryption/PRF</td></tr><tr><td>KAME</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>auth. encryption/PRF</td></tr></tbody></table>

to avoid. We summarize all of these properties in Fig. 2, and compare previous works with ours. Finally, most of these works [37, 10, 36, 26, 19, 38] do not formally prove the security of their solutions, which we do in our long version [2].

**Outline.** In Section 2, we present a technical overview of our scheme. In Section 3, we present a generic model for KMPS schemes and their security properties. In Section 4, we propose two instantiations which differ in upload, and a common download. Security is discussed in Section 5. In Section 6, we discuss our implementation for both schemes. Section 7 concludes.

## 2 Technical Overview

**Notations.** We write $\text{negl}$ for any negligible function in the security parameter $\lambda$. Sampling an element $x$ uniformly from a set $S$ is denoted $x \leftarrow_S S$. The set of possible outputs for any given inputs is denoted as $[\text{Alg}(\cdot)]$. Also, by $\text{P}(\langle E_1(i_1), E_2(i_2) \rangle)$, we denote the protocol P played between parties $E_j$, taking as input $i_j$. We denote concatenation of elements by $||$. By $\mathcal{C}$, we denote the challenge of a security experiment and by $\mathcal{A}$ the adversary, both being probabilistic polynomial-time algorithms.

**Overview.** To achieve small data shares, the user encrypts its data with an authenticated symmetric encryption [7]. The proxy distributes the encrypted data among the clouds with an IDA. Then, the key is shared between the clouds, with secret sharing as the data's confidentiality relies on the secrecy of the key.

### 2.1 Symmetric Encryption

We use a symmetric encryption to let the user encrypt its data at a low cost. To provide integrity on the user side, we use an authenticated encryption mode [8].

**Definition 1 (Symmetric Encryption [33]).** A symmetric-key encryption scheme $E = (\text{KeyGen}, \text{Enc}, \text{Dec})$ is a triple of the following algorithms:
<table><caption>**Fig. 2.** Comparison of existing storage schemes (Proxy: the file splitting is delegated to a proxy, CSP: confidentiality is preserved against CSPs colluding, Coll: confidentiality is preserved against the proxy colluding with CSPs, Keyless: the client does not hold permanent key, Integrity: whether/how data integrity is checked).</caption><thead><tr><th></th><th>Proxy</th><th>CSPs</th><th>Coll.</th><th>Keyless</th><th>Integrity</th></tr></thead><tbody><tr><td>[37]</td><td><b>X</b></td><td>✓</td><td>–</td><td><b>X</b></td><td>Merkle Tree</td></tr><tr><td>[23]</td><td>✓</td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>[35]</td><td><b>X</b></td><td><b>X</b></td><td>–</td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>[26, 19]</td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td><td>Hashes [19]</td></tr><tr><td>[22, 10, 13]</td><td><b>X</b></td><td>✓</td><td>–</td><td>✓</td><td>Signature [22], Quorum [10]</td></tr><tr><td>[36]</td><td>✓</td><td><b>X</b></td><td><b>X</b></td><td><b>X</b></td><td><b>X</b></td></tr><tr><td>[38]</td><td>✓</td><td>✓</td><td><b>X</b></td><td><b>X</b></td><td>Signature</td></tr><tr><td>KAPRE</td><td>✓</td><td>✓</td><td><b>X</b></td><td>✓</td><td>auth. encryption/PRF</td></tr><tr><td>KAME</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>auth. encryption/PRF</td></tr></tbody></table>

to avoid. We summarize all of these properties in Fig. 2, and compare previous works with ours. Finally, most of these works [37, 10, 36, 26, 19, 38] do not formally prove the security of their solutions, which we do in our long version [2].

**Outline.** In Section 2, we present a technical overview of our scheme. In Section 3, we present a generic model for KMPS schemes and their security properties. In Section 4, we propose two instantiations which differ in upload, and a common download. Security is discussed in Section 5. In Section 6, we discuss our implementation for both schemes. Section 7 concludes.

## 2 Technical Overview

**Notations.** We write $\text{negl}$ for any negligible function in the security parameter $\lambda$. Sampling an element $x$ uniformly from a set $S$ is denoted $x \leftarrow_S S$. The set of possible outputs for any given inputs is denoted as $[\text{Alg}(\cdot)]$. Also, by $\text{P}(\langle E_1(i_1), E_2(i_2) \rangle)$, we denote the protocol P played between parties $E_j$, taking as input $i_j$. We denote concatenation of elements by $||$. By $\mathcal{C}$, we denote the challenge of a security experiment and by $\mathcal{A}$ the adversary, both being probabilistic polynomial-time algorithms.

**Overview.** To achieve small data shares, the user encrypts its data with an authenticated symmetric encryption [7]. The proxy distributes the encrypted data among the clouds with an IDA. Then, the key is shared between the clouds, with secret sharing as the data's confidentiality relies on the secrecy of the key.

### 2.1 Symmetric Encryption

We use a symmetric encryption to let the user encrypt its data at a low cost. To provide integrity on the user side, we use an authenticated encryption mode [8].

**Definition 1 (Symmetric Encryption [33]).** A symmetric-key encryption scheme $E = (\text{KeyGen}, \text{Enc}, \text{Dec})$ is a triple of the following algorithms:
<table><caption>**Fig. 3.** Security games: secret sharing perfect-secrecy $Exp_A^{PS}(λ, k, n)$, multi-key encryption internal security $Exp_A^{INT}(λ)$, and proxy re-encryption indistinguishability $Exp_A^{PRE-IND}(λ)$ with their oracles.</caption><thead><tr><th>Exp<sup>IND-CPA</sup><sub>A</sub>(λ)</th><th>Oracle OEnc<sub>k</sub>(m)</th></tr></thead><tbody><tr><td>1: k ← $E.KeyGen(λ), b ← $ {0, 1}</td><td>1: return E.Enc(m, k)</td></tr><tr><td>2: m<sub>0</sub>, m<sub>1</sub> ← A</td><td>Exp<sup>PRE</sup><sub>A</sub>(λ)</td></tr><tr><td>3: c ← E.Enc(m<sub>b</sub>, k)</td><td>1: nb<sub>k</sub> ← 0, Hon, Corr ← ∅</td></tr><tr><td>4: b' ← A<sup>OEnc<sub>k</sub></sup>(c)</td><td>2: b ← $ {0, 1}</td></tr><tr><td>5: return (b = b')</td><td>3: nb<sub>k</sub>, Hon, Corr ← A<sup>OKey</sup>(λ)</td></tr><tr><td>Exp<sup>AUTH</sup><sub>A</sub>(λ)</td><td>4: rk<sub>i→j</sub> ← PRE.ReKey(pk<sub>i</sub>, sk<sub>i</sub>)</td></tr><tr><td>1: k ← E.KeyGen(λ)</td><td>5: i, m<sub>0</sub>, m<sub>1</sub> ← A<sup>ORk,ORenc</sup>(nb<sub>k</sub>)</td></tr><tr><td>2: for i ∈ [1, q]:</td><td>6: if i ∈ Hon, c ← PRE.Enc(pk<sub>i</sub>, m<sub>b</sub>)</td></tr><tr><td>3: m ← A, c<sub>i</sub> ← E.Enc(m, k)</td><td>7: else c ← ⊥</td></tr><tr><td>4: c ← A({c<sub>i</sub>}<sup>q</sup><sub>i=1</sub>)</td><td>8: b' ← A(c)</td></tr><tr><td>5: if ∃i, c = c<sub>i</sub>: return ⊥</td><td>9: return (b = b')</td></tr><tr><td>6: return E.Dec(c, k) ≠ ⊥</td><td>Exp<sup>INT</sup><sub>A</sub>(λ)</td></tr><tr><td>Oracle ORk(i, j)</td><td>1: pk<sub>0</sub> ← A(λ), b ← $ {0, 1}</td></tr><tr><td>1: if (i ∈ Hon ∧ j ∈ Corr)</td><td>2: (pk<sub>i</sub>, sk<sub>i</sub>)<sup>n</sup><sub>i=1</sub> ← MKE.KeyGen(λ)</td></tr><tr><td>2: return ⊥</td><td>3: i, m<sub>0</sub>, m<sub>1</sub> ← A(pk<sub>1</sub>, ..., pk<sub>n</sub>)</td></tr><tr><td>3: return PRE.ReKey(sk<sub>i</sub>, pk<sub>j</sub>)</td><td>4: c ← MKE.Enc(m<sub>b</sub>, pk<sub>0</sub>, ..., pk<sub>n</sub>)</td></tr><tr><td>Oracle OKey(λ, b)</td><td>5: ∀j ≠ i, p<sub>j</sub> ← MKE.PartDec(c, sk<sub>j</sub>)</td></tr><tr><td>1: (pk<sub>n<sub>b</sub>k</sub>, sk<sub>n<sub>b</sub>k</sub>) ← PRE.KeyGen(λ)</td><td>6: b' ← A({p<sub>j</sub>}<sup>j≠i</sup>)</td></tr><tr><td>2: increment nb<sub>k</sub></td><td>7: return (b = b')</td></tr><tr><td>3: if b = 0: add nb<sub>k</sub> to Corr</td><td>Exp<sup>PS</sup><sub>A</sub>(λ, k, n)</td></tr><tr><td>4: return (pk<sub>n<sub>b</sub>k</sub>, sk<sub>n<sub>b</sub>k</sub>)</td><td>1: m<sub>0</sub>, m<sub>1</sub> ← A(λ)</td></tr><tr><td>5: add nb<sub>k</sub> to Hon</td><td>2: b ← $ {0, 1}</td></tr><tr><td>6: return pk<sub>n<sub>b</sub>k</sub></td><td>3: {s<sub>i</sub>}<sup>n</sup><sub>i=1</sub> ← SS Split(m<sub>b</sub>, n, k)</td></tr><tr><td>Oracle OEnc(i, j, ct<sub>i</sub>)</td><td>4: b' ← A(s<sub>1</sub>, ..., s<sub>k-1</sub>)</td></tr><tr><td>1: if (i ∈ Hon ∧ j ∈ Corr)</td><td>5: return (b = b')</td></tr><tr><td>2: return ⊥</td><td></td></tr><tr><td>3: return PRE.ReEnc(ct<sub>i</sub>, rk<sub>i→j</sub>)</td><td></td></tr></tbody></table>

E.KeyGen(λ) → k: returns a key k according to the security parameter λ.

E.Enc(m, k) → c: outputs a ciphertext c.

E.Dec(c, k) → m/⊥: outputs a message m such that $E.Dec(E.Enc(m, k), k) = m$, outputs ⊥ if the ciphertext is invalid.

It must be IND-CPA for symmetric encryption (Definition 2).

**Definition 2 (Chosen Plaintext Security [6]).** Let $λ$ be a security parameter and $q \in \mathbb{N}$ a value polynomial in $λ$. A symmetric-key encryption scheme $E$ is IND-CPA if for any $A$ in game $Exp_A^{IND-CPA}(λ)$ (Fig. 4), we have: $Adv_A^{IND-CPA}(A) := |Pr[Exp_A^{IND-CPA}(λ) = 1] - 1/2| \le \text{negl.}$
<table><caption>**Fig. 3.** Security games: secret sharing perfect-secrecy Exp<sup>PS</sup><sub>A</sub>(λ, k, n), multi-key encryption internal security Exp<sup>INT</sup><sub>A</sub>(λ), and proxy re-encryption indistinguishability Exp<sup>PRE</sup><sub>A</sub>-IND(λ) with their oracles.</caption><thead><tr><th>Exp<sup>IND-CPA</sup><sub>A</sub>(λ)</th><th>Oracle OEnc<sub>k</sub>(m)</th></tr></thead><tbody><tr><td>1: k ← $E.KeyGen(λ), b ← $ {0, 1}</td><td>1: return E.Enc(m, k)</td></tr><tr><td>2: m<sub>0</sub>, m<sub>1</sub> ← A</td><td>Exp<sup>PRE</sup><sub>A</sub>(λ)</td></tr><tr><td>3: c ← E.Enc(m<sub>b</sub>, k)</td><td>1: nb<sub>k</sub> ← 0, Hon, Corr ← ∅</td></tr><tr><td>4: b' ← A<sup>OEnc<sub>k</sub></sup>(c)</td><td>2: b ← $ {0, 1}</td></tr><tr><td>5: return (b = b')</td><td>3: nb<sub>k</sub>, Hon, Corr ← A<sup>OKey</sup>(λ)</td></tr><tr><td>Exp<sup>AUTH</sup><sub>A</sub>(λ)</td><td>4: rk<sub>i→j</sub> ← PRE.ReKey(pk<sub>i</sub>, sk<sub>i</sub>)</td></tr><tr><td>1: k ← E.KeyGen(λ)</td><td>5: i, m<sub>0</sub>, m<sub>1</sub> ← A<sup>ORk,ORenc</sup>(nb<sub>k</sub>)</td></tr><tr><td>2: for i ∈ [1, q]:</td><td>6: if i ∈ Hon, c ← PRE.Enc(pk<sub>i</sub>, m<sub>b</sub>)</td></tr><tr><td>3: m ← A, c<sub>i</sub> ← E.Enc(m, k)</td><td>7: else c ← ⊥</td></tr><tr><td>4: c ← A({c<sub>i</sub>}<sup>q</sup><sub>i=1</sub>)</td><td>8: b' ← A(c)</td></tr><tr><td>5: if ∃i, c = c<sub>i</sub>: return ⊥</td><td>9: return (b = b')</td></tr><tr><td>6: return E.Dec(c, k) ≠ ⊥</td><td>Exp<sup>INT</sup><sub>A</sub>(λ)</td></tr><tr><td>Oracle ORk(i, j)</td><td>1: pk<sub>0</sub> ← A(λ), b ← $ {0, 1}</td></tr><tr><td>1: if (i ∈ Hon ∧ j ∈ Corr)</td><td>2: (pk<sub>i</sub>, sk<sub>i</sub>)<sup>n</sup><sub>i=1</sub> ← MKE.KeyGen(λ)</td></tr><tr><td>2: return ⊥</td><td>3: i, m<sub>0</sub>, m<sub>1</sub> ← A(pk<sub>1</sub>, ..., pk<sub>n</sub>)</td></tr><tr><td>3: return PRE.ReKey(sk<sub>i</sub>, pk<sub>j</sub>)</td><td>4: c ← MKE.Enc(m<sub>b</sub>, pk<sub>0</sub>, ..., pk<sub>n</sub>)</td></tr><tr><td>Oracle OKey(λ, b)</td><td>5: ∀j ≠ i, p<sub>j</sub> ← MKE.PartDec(c, sk<sub>j</sub>)</td></tr><tr><td>1: (pk<sub>n<sub>b</sub>k</sub>, sk<sub>n<sub>b</sub>k</sub>) ← PRE.KeyGen(λ)</td><td>6: b' ← A({p<sub>j</sub>}<sup>j≠i</sup>)</td></tr><tr><td>2: increment nb<sub>k</sub></td><td>7: return (b = b')</td></tr><tr><td>3: if b = 0: add nb<sub>k</sub> to Corr</td><td>Exp<sup>PS</sup><sub>A</sub>(λ, k, n)</td></tr><tr><td>4: return (pk<sub>n<sub>b</sub>k</sub>, sk<sub>n<sub>b</sub>k</sub>)</td><td>1: m<sub>0</sub>, m<sub>1</sub> ← A(λ)</td></tr><tr><td>5: add nb<sub>k</sub> to Hon</td><td>2: b ← $ {0, 1}</td></tr><tr><td>6: return pk<sub>n<sub>b</sub>k</sub></td><td>3: {s<sub>i</sub>}<sup>n</sup><sub>i=1</sub> ← SS Split(m<sub>b</sub>, n, k)</td></tr><tr><td>Oracle OEnc(i, j, ct<sub>i</sub>)</td><td>4: b' ← A(s<sub>1</sub>, ..., s<sub>k-1</sub>)</td></tr><tr><td>1: if (i ∈ Hon ∧ j ∈ Corr)</td><td>5: return (b = b')</td></tr><tr><td>2: return ⊥</td><td></td></tr><tr><td>3: return PRE.ReEnc(ct<sub>i</sub>, rk<sub>i→j</sub>)</td><td></td></tr></tbody></table>

E.KeyGen(λ) → k: returns a key k according to the security parameter λ.

E.Enc(m, k) → c: outputs a ciphertext c.

E.Dec(c, k) → m/⊥: outputs a message m such that E.Dec(E.Enc(m, k), k) = m, outputs ⊥ if the ciphertext is invalid.

It must be IND-CPA for symmetric encryption (Definition 2).

**Definition 2 (Chosen Plaintext Security [6]).** Let $\lambda$ be a security parameter and $q \in \mathbb{N}$ a value polynomial in $\lambda$. A symmetric-key encryption scheme $E$ is IND-CPA if for any $A$ in game Exp<sup>IND-CPA</sup><sub>A</sub>(λ) (Fig. 4), we have: Adv<sup>IND</sup><sub>λ</sub>-CPA(A) := $|\Pr[\text{Exp<sup>IND-CPA</sup><sub>A</sub>(λ) = 1}] - 1/2| \le \text{negl.}$
**Definition 3 (Authenticated Encryption [7]).** A symmetric-key encryption scheme E has authenticity if for any $\mathcal{A}$ in game $\text{Exp}_{\mathcal{A}}^{\text{AUTH}}(\lambda)$ (Fig. 4) we have: $\text{Adv}_{\lambda}^{\text{AUTH}}(\mathcal{A}) := \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{AUTH}}(\lambda) = 1] \le \text{negl}$.

## 2.2 Information Dispersal Algorithm

In our scheme, the user's encrypted data are stored using a memory-efficient Information Dispersal Algorithm (IDA) [28]. In essence IDA works similarly to secret sharing: splitting a message into $n$ shares with only $k$ of them allowing recovery. However shares do not retain the secrecy of the message, allowing better memory efficiency (e.g., for a threshold $k$, Rabin's IDA creates shares of size $|S|/k$ for initial message of size $|S|$).

**Definition 4 (IDA [28]).** An Information Dispersal Algorithm scheme IDA is given by the following set of algorithms:

* IDA.Split($m, n, k$) $\rightarrow r_1, \dots, r_n$: outputs $n$ shares of $m$.

* IDA.Rec($k, r_1, \dots, r_j$) $\rightarrow m$: given that $j \ge k$, recovers the initial message such that for all $I \subset \{1, \dots, n\}$ with $|I| = k$, IDA.Split($m, n, k$) $\rightarrow \{r_i\}_{i=1}^n$, we have IDA.Rec($k, \{r_i\}_{i \in I}$) = $m$.

## 2.3 Secret Sharing

The symmetric key used to encrypt the user's data is split in shares using secret sharing.

**Definition 5 (Secret Sharing [32]).** A $(k, n)$ secret sharing scheme SS is given by:

* SS.Split($m, k, n$) $\rightarrow (s_1, \dots, s_n)$: on input a secret $m$, returns the shares $(s_1, \dots, s_n)$ according to $n$ and $k$.

* SS.Rec($k, s_1, \dots, s_j$) $\rightarrow m$: reconstructs the secret from the shares given that $j \ge k$ such that SS.Rec($k, SS.Split($m, k, n$)) = $m$.

It must achieve perfect secrecy (Definition 6).

**Definition 6 (Perfect Secrecy [25]).** A secret sharing scheme SS has perfect secrecy if for any $k, n$ such that $1 < k \le n$, any $\mathcal{A}$ in game $\text{Exp}_{\mathcal{A}}^{\text{PS}}(\lambda, k, n)$ (Fig. 4) we have:

$$ \text{Adv}_{\lambda}^{\text{PS}}(\mathcal{A}) := |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PS}}(\lambda, k, n) = 1] - 1/2| \le \text{negl}. $$

We use Shamir's secret sharing described in Fig. 4, which perfect secrecy is shown in [32]. As we want to delegate the sharing to the proxy, the user encrypts the key with an homomorphic encryption, such that the proxy can compute a secret sharing on the encrypted key resulting on encrypted shares of the key. Indeed as we want our setup to be independent of any long-term key, the CSPs need to store the key shares in plaintext. The key point of our constructions is using an asymmetric encryption PKE = (KeyGen, Enc, Dec) that commutes with a secret sharing. We model this property in the following definition:
**Definition 3 (Authenticated Encryption [7]).** A symmetric-key encryption scheme E has authenticity if for any $\mathcal{A}$ in game $\text{Exp}_{\mathcal{A}}^{\text{AUTH}}(\lambda)$ (Fig. 4) we have: $\text{Adv}_{\lambda}^{\text{AUTH}}(\mathcal{A}) := \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{AUTH}}(\lambda) = 1] \le \text{negl}$.

## 2.2 Information Dispersal Algorithm

In our scheme, the user's encrypted data are stored using a memory-efficient Information Dispersal Algorithm (IDA) [28]. In essence IDA works similarly to secret sharing: splitting a message into $n$ shares with only $k$ of them allowing recovery. However shares do not retain the secrecy of the message, allowing better memory efficiency (e.g., for a threshold $k$, Rabin's IDA creates shares of size $|S|/k$ for initial message of size $|S|$).

**Definition 4 (IDA [28]).** An Information Dispersal Algorithm scheme IDA is given by the following set of algorithms:

IDA.Split($m, n, k$) $\rightarrow r_1, \dots, r_n$: outputs $n$ shares of $m$.

IDA.Rec($k, r_1, \dots, r_j$) $\rightarrow m$: given that $j \ge k$, recovers the initial message such that for all $I \subset \{1, \dots, n\}$ with $|I| = k$, $\text{IDA.Split}(m, n, k) \rightarrow \{r_i\}_{i=1}^n$, we have $\text{IDA.Rec}(k, \{r_i\}_{i \in I}) = m$.

## 2.3 Secret Sharing

The symmetric key used to encrypt the user's data is split in shares using secret sharing.

**Definition 5 (Secret Sharing [32]).** A $(k, n)$ secret sharing scheme SS is given by:

SS.Split($m, k, n$) $\rightarrow (s_1, \dots, s_n)$: on input a secret $m$, returns the shares $(s_1, \dots, s_n)$ according to $n$ and $k$.

SS.Rec($k, s_1, \dots, s_j$) $\rightarrow m$: reconstructs the secret from the shares given that $j \ge k$ such that $\text{SS.Rec}(k, \text{SS.Split}(m, k, n)) = m$.

It must achieve perfect secrecy (Definition 6).

**Definition 6 (Perfect Secrecy [25]).** A secret sharing scheme SS has perfect secrecy if for any $k, n$ such that $1 < k \le n$, any $\mathcal{A}$ in game $\text{Exp}_{\mathcal{A}}^{\text{PS}}(\lambda, k, n)$ (Fig. 4) we have:

$$ \text{Adv}_{\lambda}^{\text{PS}}(\mathcal{A}) := |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PS}}(\lambda, k, n) = 1] - 1/2| \le \text{negl}. $$

We use Shamir's secret sharing described in Fig. 4, which perfect secrecy is shown in [32]. As we want to delegate the sharing to the proxy, the user encrypts the key with an homomorphic encryption, such that the proxy can compute a secret sharing on the encrypted key resulting on encrypted shares of the key. Indeed as we want our setup to be independent of any long-term key, the CSPs need to store the key shares in plaintext. The key point of our constructions is using an asymmetric encryption PKE = (KeyGen, Enc, Dec) that commutes with a secret sharing. We model this property in the following definition:
<figure><img src="image_3.png" /><figcaption>Fig. 4. Description of Shamir’s secret sharing algorithms.</figcaption></figure>

**Definition 7.** We say that PKE commutes with a secret sharing SS if it verifies $\forall(\text{pk}, \text{sk}) \leftarrow \text{PKE.KeyGen}(\lambda), \forall m \in \{0, 1\}^*, \forall k, n \in \mathbb{N} \text{ such that } k \le n \text{ and} \\ \forall(s_1, \dots, s_n) \in [\text{SS.Split}(\text{PKE.Enc}(m, \text{pk}), n, k)], \text{ we have} \\ \forall \mathcal{I} \subseteq [1, n], |\mathcal{I}| = k, \text{ SS.Rec}(k, \{\text{PKE.Dec}(s_i, \text{sk})\}_{i \in \mathcal{I}}) = m.$

As Shamir’s secret sharing produces shares of a secret $m$ which are linear relations in $m$ and the random coefficients $a_i$, any additively homomorphic encryption scheme (integer scalar multiplication is given) PKE commutes with it by computing encrypted shares as:

$$ \text{PKE.Enc}(m, \text{pk}) + \sum_{j=1}^{k-1} \text{PKE.Enc}(a_j, \text{pk})x_i^j \in [\text{PKE.Enc}(y_i, \text{pk})]. $$

Reciprocally, recovering the encrypted secret is given by:

$$ \sum_{i=1}^{k} \text{PKE.Enc}(y_i, \text{pk})\ell_i \in [\text{PKE.Enc}(\sum_{i=1}^{k} y_i \ell_i = m, \text{pk})]. $$

The shares of the key cannot be accessible to the proxy. This is where our two protocols differ: our first solution KAPRE uses proxy re-encryption [27, 15] to tackle this issue, while KAME uses multikey encryption [14, 18]. At the end, our two protocols result in the same state, and have a common download phase.

## 2.4 Proxy Re-Encryption Scheme

Our first protocol KAPRE uses proxy re-encryption [27, 11] to let each provider decrypts its share with its own private key.

**Definition 8 (Proxy Re-encryption [27]).** A proxy re-encryption scheme PRE is given by:

PRE.KeyGen($\lambda$) → (pk, sk) : outputs a key pair according to $\lambda$.

PRE.Enc($m$, pk) → $c$ : on input pk and a message $m$, outputs a ciphertext.

PRE.Dec($c$, sk) → $m$ : returns a decryption $m$ of $c$.

PRE.ReKey(sk, pk) → $rk_{i \to j}$ : returns a re-encryption key which allows to transform ciphertexts under $pk_i$ into ciphertexts under $pk_j$.

PRE.ReEnc($c_i$, $rk_{i \to j}$) → $c_j$ : on input a ciphertext encrypted under $pk_i$ and a re-encryption key $rk_{i \to j}$, returns a ciphertext encrypted under $pk_j$.

It must be correct and have IND-CPA security for PRE (PRE-IND) (Definition 9).
<figure><img src="image_2.png" /><figcaption>Fig. 4. Description of Shamir’s secret sharing algorithms.</figcaption></figure>

**Definition 7.** We say that PKE commutes with a secret sharing SS if it verifies $\forall(\text{pk}, \text{sk}) \leftarrow \text{PKE.KeyGen}(\lambda), \forall m \in \{0, 1\}^*, \forall k, n \in \mathbb{N} \text{ such that } k \le n \text{ and} \\
\forall(s_1, \dots, s_n) \in [\text{SS.Split}(\text{PKE.Enc}(m, \text{pk}), n, k)], \text{ we have} \\
\forall \mathcal{I} \subseteq [1, n], |\mathcal{I}| = k, \text{ SS.Rec}(k, \{\text{PKE.Dec}(s_i, \text{sk})\}_{i \in \mathcal{I}}) = m.$

As Shamir’s secret sharing produces shares of a secret $m$ which are linear relations in $m$ and the random coefficients $a_i$, any additively homomorphic encryption scheme (integer scalar multiplication is given) PKE commutes with it by computing encrypted shares as:

$$ \text{PKE.Enc}(m, \text{pk}) + \sum_{j=1}^{k-1} \text{PKE.Enc}(a_j, \text{pk})x_i^j \in [\text{PKE.Enc}(y_i, \text{pk})]. $$

Reciprocally, recovering the encrypted secret is given by:

$$ \sum_{i=1}^{k} \text{PKE.Enc}(y_i, \text{pk})\ell_i \in [\text{PKE.Enc}(\sum_{i=1}^{k} y_i\ell_i = m, \text{pk})]. $$

The shares of the key cannot be accessible to the proxy. This is where our two protocols differ: our first solution KAPRE uses proxy re-encryption [27, 15] to tackle this issue, while KAME uses multikey encryption [14, 18]. At the end, our two protocols result in the same state, and have a common download phase.

## 2.4 Proxy Re-Encryption Scheme

Our first protocol KAPRE uses proxy re-encryption [27, 11] to let each provider decrypts its share with its own private key.

**Definition 8 (Proxy Re-encryption [27]).** A proxy re-encryption scheme PRE is given by:

PRE.KeyGen($\lambda$) $\rightarrow$ (pk, sk) : outputs a key pair according to $\lambda$.

PRE.Enc($m$, pk) $\rightarrow$ c : on input pk and a message m, outputs a ciphertext.

PRE.Dec(c, sk) $\rightarrow$ m : returns a decryption m of c.

PRE.ReKey(sk, pk) : returns a re-encryption key which allows to transform ciphertexts under pk into ciphertexts under pk.

PRE.ReEnc(c, pk) : on input a ciphertext encrypted under pk and a re-encryption key pk, returns a ciphertext encrypted under pk.

It must be correct and have IND-CPA security for PRE (PRE-IND) (Definition 9).
**Definition 9 (PRE-IND [15]).** The scheme PRE is PRE-IND if for any $\mathcal{A}$ in game $\text{Exp}_{\mathcal{A}}^{\text{PRE-IND}}$ (Fig. 3), $\text{Adv}_{\lambda}^{\text{PRE-IND}}(\mathcal{A}) := |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRE-IND}}(\lambda) = 1] - 1/2| \le \text{negl}$.

## 2.5 Multikey Encryption Scheme

In our second protocol KAME, we use multi-key encryption [20, 14]. That way, the providers can also each decrypt their own share, this time with the cooperation of the others.

**Definition 10 (Multi-key Encryption [14]).** A multi-key encryption scheme MKE is given by:

MKE.KeyGen($\lambda$) → (pk, sk) : outputs a key pair (pk, sk).

MKE.Enc($m$, pk) → $c$ : on input pk and a message $m$, outputs a ciphertext.

MKE.PartDec($c$, sk) → $p_i$ : returns a partial decryption $p_i$ of $c$.

MKE.FinDec($p_1, \dots, p_n$) → $m$ : given all the partial decryptions, outputs $m$.

It must be correct and internally secure (Definition 11).

**Definition 11 (Internal Security [18]).** The MKE has internal security if for any $\mathcal{A}$ in $\text{Exp}_{\mathcal{A}}^{\text{INT}}$ (Fig. 3), we have: $\text{Adv}_{\lambda}^{\text{INT}}(\mathcal{A}) := |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{INT}}(\lambda) = 1] - 1/2| \le \text{negl}$.

During download, the proxy checks the shares integrity using commitments computed by the user from key-homomorphic pseudorandom function (PRF) families [33, 4, 16]. This avoids sending the user any corrupted data. As the proxy receives shares that have been re-randomized, usual methods like keeping hashes cannot be used to provide integrity.

## 2.6 Pseudorandom Function Family

To let the proxy check the data's integrity, we create commitments using key-homomorphic pseudorandom function families [12, 4]. Consider three finite sets: $D$, $R$, and $S$, and let $\Gamma_{D,R}$ represent the set of all functions from $D$ to $R$.

**Definition 12 (Pseudo-random Function Family [33]).** Let $\mathcal{F} = \{F_s\}_{s \in S}$ be a family of keyed functions mapping $D$ to $R$. The family $\mathcal{F}$ is pseudorandom if the PRF-advantage of any adversary $\mathcal{A}$ is negligible:

$$ \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A}) := |\text{Pr}[s \leftarrow \mathcal{S} : \mathcal{A}^{F_s} = 1] - \text{Pr}[f \leftarrow \Gamma_{D,R} : \mathcal{A}^f = 1]| $$

**Definition 13 (Key-Homomorphic PRF [4]).** A PRF family $\mathcal{F} = \{F_s\}_{s \in S}$ is key-homomorphic if $S$ has a group structure and if there is a polynomial time algorithm that, given $F_s(x)$ and $F_t(x)$, outputs $F_{s+t}(x)$.
**Definition 9 (PRE-IND [15]).** The scheme PRE is PRE-IND if for any $\mathcal{A}$ in game $\text{Exp}_{\mathcal{A}}^{\text{PRE-IND}}$ (Fig. 3), $\text{Adv}_{\lambda}^{\text{PRE-IND}}(\mathcal{A}) := |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{PRE-IND}}(\lambda) = 1] - 1/2| \le \text{negl}$.

## 2.5 Multikey Encryption Scheme

In our second protocol KAME, we use multi-key encryption [20, 14]. That way, the providers can also each decrypt their own share, this time with the cooperation of the others.

**Definition 10 (Multi-key Encryption [14]).** A multi-key encryption scheme MKE is given by:

MKE.KeyGen($\lambda$) → (pk, sk) : outputs a key pair (pk, sk).

MKE.Enc($m$, pk) → $c$ : on input pk and a message $m$, outputs a ciphertext.

MKE.PartDec($c$, sk) → $p_i$ : returns a partial decryption $p_i$ of $c$.

MKE.FinDec($p_1, \dots, p_n$) → $m$ : given all the partial decryptions, outputs $m$.

It must be correct and internally secure (Definition 11).

**Definition 11 (Internal Security [18]).** The MKE has internal security if for any $\mathcal{A}$ in $\text{Exp}_{\mathcal{A}}^{\text{INT}}$ (Fig. 3), we have: $\text{Adv}_{\lambda}^{\text{INT}}(\mathcal{A}) := |\text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{INT}}(\lambda) = 1] - 1/2| \le \text{negl}$.

During download, the proxy checks the shares integrity using commitments computed by the user from key-homomorphic pseudorandom function (PRF) families [33, 4, 16]. This avoids sending the user any corrupted data. As the proxy receives shares that have been re-randomized, usual methods like keeping hashes cannot be used to provide integrity.

## 2.6 Pseudorandom Function Family

To let the proxy check the data's integrity, we create commitments using key-homomorphic pseudorandom function families [12, 4]. Consider three finite sets: $D$, $R$, and $S$, and let $\Gamma_{D,R}$ represent the set of all functions from $D$ to $R$.

**Definition 12 (Pseudo-random Function Family [33]).** Let $\mathcal{F} = \{F_s\}_{s \in S}$ be a family of keyed functions mapping $D$ to $R$. The family $\mathcal{F}$ is pseudorandom if the PRF-advantage of any adversary $\mathcal{A}$ is negligible:

$$ \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A}) := |\text{Pr}[s \leftarrow \mathcal{S} : \mathcal{A}^{F_s} = 1] - \text{Pr}[f \leftarrow \Gamma_{D,R} : \mathcal{A}^f = 1]|. $$

**Definition 13 (Key-Homomorphic PRF [4]).** A PRF family $\mathcal{F} = \{F_s\}_{s \in S}$ is key-homomorphic if $S$ has a group structure and if there is a polynomial time algorithm that, given $F_s(x)$ and $F_t(x)$, outputs $F_{s+t}(x)$.
## 2.7 Asymmetric Encryption

We use asymmetric encryption in download to let the user send secret values to the providers without having to deal with any key agreement.

**Definition 14 (Asymmetric Encryption).** An asymmetric encryption scheme

PKE = (KeyGen, Enc, Dec) is defined by:

PKE.KeyGen($\lambda$) → (pk, sk) : on input $\lambda$, outputs a key pair (pk, sk).

PKE.Enc($m$, pk) → $c$ : outputs a ciphertext $c$.

PKE.Dec($c$, sk) → $m$ : outputs $m$ such that PKE.Dec(PKE.Enc($m$, pk), sk) = $m$.

It must be IND-CPA for asymmetric encryption (Definition 15).

**Definition 15 (IND-CPA).**

Any adversary $\mathcal{A}$ verifies the following

$$ \Pr \left[ \begin{array}{l} (\mathit{sk}, \mathit{pk}) \leftarrow \mathit{PKE}\cdot\mathit{KeyGen}(1^{\lambda}), \\ (m_0, m_1) \leftarrow \mathcal{A}(\mathit{pk}), \\ b \leftarrow \{0, 1\}, \qquad : b = b^* \\ c \leftarrow \mathit{PKE}\cdot\mathit{Enc}(m_b, \mathit{pk}), \\ b^* \leftarrow \mathcal{A}(c) \end{array} \right] - \frac{1}{2} \le \text{negl.} $$

# 3 Generic Model

Our Keyless Multi-Party Storage (KMPS) scheme involves three types of party: a User interacting with a Proxy which interacts with n Cloud Storage Providers CSP, for $i \in [1, n]$. There are two phases: an upload where the user stores some data m interacting only with the proxy, and a download where at least $k-1$ of the CSPs cooperate with the proxy (gathering a total of $k$ shares) to send back m to the user.

## 3.1 Multi-Party Storage scheme

**Definition 16 (Keyless Multi-Party Storage).** A Keyless Multi-Party Storage scheme KMPS is a tuple KMPS = (Setup, KeyGen, Transform, Distrib, Open, Designate, Hide, Merge, Recover) of probabilistic polynomial time algorithms with:

Setup($\lambda$, $n$, $k$) → $\mathit{param}$: sets the global parameters.
$\mathit{The parameters param}$, $n$ and $k$ are implicit parameters of all algorithms.

$\mathit{KeyGen}(\lambda) \to (\mathit{pk}, \mathit{sk})$: returns a key pair (pk, sk) according to $\lambda$.

### Upload

$\mathit{Transform}(m, \mathit{pk}_0, \dots, \mathit{pk}_n) \to \mathit{com}_U, \mathit{parts}_U$: on input a message m, the proxy and providers' public keys, outputs $\mathit{parts}_U$ and a commitment $\mathit{com}_U$ to m.

$\mathit{Distrib}(\mathit{parts}_U) \to \{h_i\}_{i=0}^n$: produces shares $\{h_i\}_{i=0}^n$ from $\mathit{parts}_U$, $h_0$ being the proxy's share and $\{h_i\}_{i=1}^n$ the providers shares.

$\mathit{Open}$: This is either an algorithm $\mathit{Open}(h_i, \mathit{sk}_i) \to s_i$ or a protocol between the providers and the proxy taking as input each party's shares $\{h_i\}_{i=0}^n$ and each party's secret keys $\{\mathit{sk}_i\}_{i=0}^n$, outputting $\{s_i\}_{i=0}^n$.
## 2.7 Asymmetric Encryption

We use asymmetric encryption in download to let the user send secret values to the providers without having to deal with any key agreement.

**Definition 14 (Asymmetric Encryption).** An asymmetric encryption scheme

PKE = (KeyGen, Enc, Dec) is defined by:

PKE.KeyGen($\lambda$) → (pk, sk) : on input $\lambda$, outputs a key pair (pk, sk).

PKE.Enc($m$, pk) → $c$ : outputs a ciphertext $c$.

PKE.Dec($c$, sk) → $m$ : outputs $m$ such that PKE.Dec(PKE.Enc($m$, pk), sk) = $m$.

It must be IND-CPA for asymmetric encryption (Definition 15).

**Definition 15 (IND-CPA).**

Any adversary $\mathcal{A}$ verifies the following

$$ \Pr \left[ \begin{array}{l} (\mathit{sk}, \mathit{pk}) \leftarrow \mathit{PKE}\cdot\mathit{KeyGen}(1^{\lambda}), \\ (m_0, m_1) \leftarrow \mathcal{A}(\mathit{pk}), \\ b \leftarrow \{0, 1\}, \qquad : b = b^* \\ c \leftarrow \mathit{PKE}\cdot\mathit{Enc}(m_b, \mathit{pk}), \\ b^* \leftarrow \mathcal{A}(c) \end{array} \right] - \frac{1}{2} \le \text{negl.} $$

# 3 Generic Model

Our Keyless Multi-Party Storage (KMPS) scheme involves three types of party: a User interacting with a Proxy which interacts with n Cloud Storage Providers CSP, for $i \in [1, n]$. There are two phases: an upload where the user stores some data m interacting only with the proxy, and a download where at least $k-1$ of the CSPs cooperate with the proxy (gathering a total of $k$ shares) to send back m to the user.

## 3.1 Multi-Party Storage scheme

**Definition 16 (Keyless Multi-Party Storage).** A Keyless Multi-Party Storage scheme KMPS is a tuple KMPS = (Setup, KeyGen, Transform, Distrib, Open, Designate, Hide, Merge, Recover) of probabilistic polynomial time algorithms with:

Setup($\lambda$, $n$, $k$) → param: sets the global parameters.
The parameters param, $n$ and $k$ are implicit parameters of all algorithms.

KeyGen($\lambda$) → (pk, sk): returns a key pair (pk, sk) according to $\lambda$.

### Upload

Transform($m$, $\mathit{pk}_0, \dots, \mathit{pk}_n$) → $\mathit{com}_U$, $\mathit{parts}_U$: on input a message $m$, the proxy and providers' public keys, outputs $\mathit{parts}_U$ and a commitment $\mathit{com}_U$ to $m$.

Distrib($\mathit{parts}_U$) → {$h_i$}$_{i=0}^n$: produces shares {$h_i$}$_{i=0}^n$ from $\mathit{parts}_U$, $h_0$ being the proxy's share and {$h_i$}$_{i=1}^n$ the providers shares.

Open: This is either an algorithm Open($h_i$, $\mathit{sk}_i$) → $s_i$ or a protocol between the providers and the proxy taking as input each party's shares {$h_i$}$_{i=0}^n$ and each party's secret keys {$\mathit{sk}_i$}$_{i=0}^n$, outputting {$s_i$}$_{i=0}^n$.
<figure><img src="image_4.png" /><figcaption>Fig. 5. Overview of an KMPS protocol.</figcaption></figure>

We write $\underline{Upload}(m) \rightarrow \{s_i\}_{i=0}^n, \underline{com_U}$ for the concatenation of the three previous algorithms with keys as implicit input and $\underline{Dec}$ executed for each share.

Download

$\underline{Designate}(pk_1, \dots, pk_k) \rightarrow \underline{com_D}, \underline{state_U}, \{\underline{nc_i}\}_{i=1}^k$: The user computes for each provider involved in download an encryption $\underline{nc_i}$ of a nonce $n_i$ under its public key $pk_i$, and a commitment $\underline{com_D}$ to the nonces. It also returns in $\underline{state_U}$ the values needed for the final recovery.

$\underline{Hide}(s_i, \underline{nc_i}, \underline{sk_i}) \rightarrow s'_i$: a provider or the proxy encrypts its share $s_i$ with $\underline{nc_i}$.

$\underline{Merge}(\underline{com_U}, \underline{com_D}, \{s'_i\}_{i=0}^{k-1}) \rightarrow (\underline{parts_D}, \mathcal{I})$: if there are invalid shares, $\underline{parts_D} = \perp$ and $\mathcal{I}$ contains their indexes. Otherwise, $\mathcal{I} = \perp$ and $\underline{parts_D}$ is computed from the shares.

$\underline{Recover}(\underline{parts_D}, \underline{state_U}) \rightarrow m/\perp$: outputs $m$ from $\underline{parts_D}$, $\underline{state_U}$ and the nonces, $\perp$ if the data has been corrupted.
<figure><img src="image_3.png" /><figcaption>Fig. 5. Overview of an KMPS protocol.</figcaption></figure>

We write $\underline{Upload}(m) \rightarrow \{s_i\}_{i=0}^n, \underline{com_U}$ for the concatenation of the three previous algorithms with keys as implicit input and $\underline{Dec}$ executed for each share.

Download

$\underline{Designate}(pk_1, \dots, pk_k) \rightarrow \underline{com_D}, \underline{state_U}, \{\underline{nc_i}\}_{i=1}^k$: The user computes for each provider involved in download an encryption $\underline{nc_i}$ of a nonce $n_i$ under its public key $pk_i$, and a commitment $\underline{com_D}$ to the nonces. It also returns in $\underline{state_U}$ the values needed for the final recovery.

$\underline{Hide}(s_i, \underline{nc_i}, \underline{sk_i}) \rightarrow s'_i$: a provider or the proxy encrypts its share $s_i$ with $\underline{nc_i}$.

$\underline{Merge}(\underline{com_U}, \underline{com_D}, \{s'_i\}_{i=0}^{k-1}) \rightarrow (\underline{parts_D}, \mathcal{I})$: if there are invalid shares, $\underline{parts_D} = \perp$ and $\mathcal{I}$ contains their indexes. Otherwise, $\mathcal{I} = \perp$ and $\underline{parts_D}$ is computed from the shares.

$\underline{Recover}(\underline{parts_D}, \underline{state_U}) \rightarrow m/\perp$: outputs $m$ from $\underline{parts_D}$, $\underline{state_U}$ and the nonces, $\perp$ if the data has been corrupted.
Note that between upload and download, the algorithms run by the user Transform, Designate and Recover only require the public keys of the CSPs and the proxy (which can be updated between the two phases). This is what we mean by keyless: the user do not keep any cryptographic secret between these two phases.

## 3.2 KMPS Security Model

We give formal definitions of the security properties for a secure KMPS scheme.

**Correctness.** The composition of the algorithms of a KMPS scheme must allow to recover the original data from the $n + 1$ shares ($n$ for the providers and one for the proxy).

**Definition 17 (Correctness).** A KMPS scheme is correct if it verifies the following $\forall \lambda \in \mathbb{N}, \forall n \in \mathbb{N}^*, \forall m \in \{0, 1\}^*: \forall k \text{ s.t. } k \le n + 1, \forall \mathit{param} \in [\mathit{Setup}(\lambda, n, k)],$

$$ \forall i \in [0, n], \forall (\mathbf{pk}_i, \mathbf{sk}_i) \in [\text{KeyGen}(\lambda)], \forall \mathcal{I} \subseteq [0, n] \text{ s.t. } |\mathcal{I}| = k, $$

$$ \forall \mathit{com}_U, \mathit{parts}_U \in [\text{Transform}(m, \{\mathbf{pk}_i\}_{i=0}^n)], \forall \mathit{com}_U, \{h_i\}_{i=0}^n \in [\text{Distrib}(\mathit{parts}_U)], $$

$$ \forall \mathit{com}_D, \mathit{state}_U, \{\mathit{nc}_i\}_{i \in \mathcal{I}} \in [\text{Designate}(\{\mathbf{pk}_i\}_{i \in \mathcal{I}})], $$

$$ \forall i \in I, h'_i \in [\text{Hide}(\text{Open}(h_i, \mathbf{sk}_i), \mathit{nc}_i, \mathbf{sk}_i)], $$

$$ \forall (\mathit{parts}_D, \mathcal{I}) \in [\text{Merge}(\mathit{com}_U, \mathit{com}_D, \{h_i\}_{i \in \mathcal{I}})], \text{Recover}(\mathit{parts}_D, \mathit{state}_U) = m. $$

**Data's Secrecy.** We model the data's secrecy properties through indistinguishability games [33]. The adversary chooses two messages, and tries to guess which one is being uploaded and downloaded by the challenger. There are two properties depending on the adversary's capacities. The first one, *provider-secrecy*, considers the proxy is trusted. The adversary models $k-1$ colluding providers while the challenger simulates the other parties (game $\mathit{Exp}_{\mathcal{A}}^{\text{CSP}}$ in Fig. 6).

**Definition 18 (Provider-Secrecy).** A KMPS scheme is Provider-secret if for any adversary $\mathcal{A}$ we have $\mathit{Adv}_{\lambda}^{\text{CSP}}(\mathcal{A}) := |\Pr[\mathit{Exp}_{\mathcal{A}}^{\text{CSP}}(\lambda) = 1] - 1/2| \le \text{negl}$.

The second property $N$-collusion-secrecy, depicted in game $\mathit{Exp}_{\mathcal{A},N}^{\text{Coll}}$ (Fig. 6), considers the proxy colluding with $N$ CSPs as the adversary. The challenger plays the role of the user and the remaining $n-N$ honest CSPs. To model the fact that the proxy follows the protocol, the challenger executes the proxy's algorithms but reveals all intermediate values to the adversary. Note that $0$-collusion-secrecy means that data are confidential for a proxy not colluding with any provider.

**Definition 19 ($N$-Collusion-Secrecy).** A KMPS scheme is $N$-collusion-secret if for any $\mathcal{A}$ we have $\mathit{Adv}_{\lambda}^{N-\text{Coll}}(\mathcal{A}) := |\Pr[\mathit{Exp}_{\mathcal{A},N}^{\text{Coll}}(\lambda) = 1] - 1/2| \le \text{negl}$.

Note that based on the above definition, an KMPS scheme cannot achieve $(k-2)$-collusion-secrecy unless it achieves provider-secrecy as the proxy is essentially a provider with more power (it also holds a share of the data). Our first protocol KAPRE achieves Provider-Secrecy and $0$-collusion-secrecy (Section 4.1), and our second one KAME achieves $(k-2)$-Collusion-Secrecy (Section 4.2).
Note that between upload and download, the algorithms run by the user Transform, Designate and Recover only require the public keys of the CSPs and the proxy (which can be updated between the two phases). This is what we mean by keyless: the user do not keep any cryptographic secret between these two phases.

## 3.2 KMPS Security Model

We give formal definitions of the security properties for a secure KMPS scheme.

**Correctness.** The composition of the algorithms of a KMPS scheme must allow to recover the original data from the $n + 1$ shares ($n$ for the providers and one for the proxy).

**Definition 17 (Correctness).** A KMPS scheme is correct if it verifies the following $\forall \lambda \in \mathbb{N}, \forall n \in \mathbb{N}^*, \forall m \in \{0, 1\}^*: \forall k \text{ s.t. } k \le n + 1, \forall \mathit{param} \in [\mathit{Setup}(\lambda, n, k)],$

$$ \forall i \in [0, n], \forall (\mathbf{pk}_i, \mathbf{sk}_i) \in [\mathit{KeyGen}(\lambda)], \forall \mathcal{I} \subseteq [0, n] \text{ s.t. } |\mathcal{I}| = k, $$

$$ \forall \mathit{com}_U, \mathit{parts}_U \in [\mathit{Transform}(m, \{\mathbf{pk}_i\}_{i=0}^n)], \forall \mathit{com}_U, \{h_i\}_{i=0}^n \in [\mathit{Distrib}(\mathit{parts}_U)], $$

$$ \forall \mathit{com}_D, \mathit{state}_U, \{\mathit{nc}_i\}_{i \in \mathcal{I}} \in [\mathit{Designate}(\{\mathbf{pk}_i\}_{i \in \mathcal{I}})], $$

$$ \forall i \in I, h'_i \in [\mathit{Hide}(\mathit{Open}(h_i, \mathbf{sk}_i), \mathit{nc}_i, \mathbf{sk}_i)], $$

$$ \forall (\mathit{parts}_D, \mathcal{I}) \in [\mathit{Merge}(\mathit{com}_U, \mathit{com}_D, \{h_i\}_{i \in \mathcal{I}})], \mathit{Recover}(\mathit{parts}_D, \mathit{state}_U) = m. $$

**Data's Secrecy.** We model the data's secrecy properties through indistinguishability games [33]. The adversary chooses two messages, and tries to guess which one is being uploaded and downloaded by the challenger. There are two properties depending on the adversary's capacities. The first one, *provider-secrecy*, considers the proxy is trusted. The adversary models $k-1$ colluding providers while the challenger simulates the other parties (game $\mathit{Exp}_{\mathcal{A}}^{\mathit{CSP}}$ in Fig. 6).

**Definition 18 (Provider-Secrecy).** A KMPS scheme is Provider-secret if for any adversary $\mathcal{A}$ we have $\mathit{Adv}_{\lambda}^{\mathit{CSP}}(\mathcal{A}) := |\Pr[\mathit{Exp}_{\mathcal{A}}^{\mathit{CSP}}(\lambda) = 1] - 1/2| \le \text{negl.}$

The second property $N$-collusion-secrecy, depicted in game $\mathit{Exp}_{\mathcal{A},N}^{\mathit{Coll}}$ (Fig. 6), considers the proxy colluding with $N$ CSPs as the adversary. The challenger plays the role of the user and the remaining $n-N$ honest CSPs. To model the fact that the proxy follows the protocol, the challenger executes the proxy's algorithms but reveals all intermediate values to the adversary. Note that 0-collusion-secrecy means that data are confidential for a proxy not colluding with any provider.

**Definition 19 (N-Collusion-Secrecy).** A KMPS scheme is N-collusion-secret if for any $\mathcal{A}$ we have $\mathit{Adv}_{\lambda}^{N-\mathit{Coll}}(\mathcal{A}) := |\Pr[\mathit{Exp}_{\mathcal{A},N}^{\mathit{Coll}}(\lambda) = 1] - 1/2| \le \text{negl.}$

Note that based on the above definition, an KMPS scheme cannot achieve (k-2)-collusion-secrecy unless it achieves provider-secrecy as the proxy is essentially a provider with more power (it also holds a share of the data). Our first protocol KAPRE achieves Provider-Secrecy and 0-collusion-secrecy (Section 4.1), and our second one KAME achieves (k-2)-Collusion-Secrecy (Section 4.2).
<figure><img src="image_5.png" /><figcaption>**Fig. 6.** Security Games: Provider-Secrecy, N-Collusion-Secrecy, User-Integrity and Accountability Games.</figcaption></figure>

**Integrity and Accountability.** First, we define integrity as the user's capacity to know whether or not its data has been altered. Here, the proxy is considered an adversary and is *malicious* only during the download phase.

This property is depicted in game $Exp_A^{INTG}(\lambda)$ of Fig. 6. The adversary plays the role of $k-2$ malicious providers that would collude with a proxy during download phase (and honest during the upload phase). Hence, it controls $k-1$ providers in total. The challenger emulates the user and the $n-k+2$ honest providers remaining. To win, the adversary's final answer must contain a forged parts$_D$ that would be accepted as the user's data during recovery, but corresponding to a modified $m' \neq m$ with non-negligible probability. We assume that the honest providers consistently return the correct shares, and the proxy cannot manipulate them to return incorrect data, such as shares from a different file. It
<figure><img src="image_4.png" /><figcaption>**Fig. 6.** Security Games: Provider-Secrecy, N-Collusion-Secrecy, User-Integrity and Accountability Games.</figcaption></figure>

**Integrity and Accountability.** First, we define integrity as the user's capacity to know whether or not its data has been altered. Here, the proxy is considered an adversary and is malicious only during the download phase.

This property is depicted in game $Exp_A^{INTG}(\lambda)$ of Fig. 6. The adversary plays the role of $k-2$ malicious providers that would collude with a proxy during download phase (and honest during the upload phase). Hence, it controls $k-1$ providers in total. The challenger emulates the user and the $n-k+2$ honest providers remaining. To win, the adversary's final answer must contain a forged parts$_D$ that would be accepted as the user's data during recovery, but corresponding to a modified $m' \neq m$ with non-negligible probability. We assume that the honest providers consistently return the correct shares, and the proxy cannot manipulate them to return incorrect data, such as shares from a different file. It
can be achieved if the proxy demonstrates the legitimacy of its request to the providers.

**Definition 20 (User-Integrity).** A KMPS scheme achieves user-integrity if for any adversary $\mathcal{A}$ we have $\text{Adv}_{\lambda}^{\text{INTG}}(\mathcal{A}) := \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{INTG}}(\lambda) = 1] \le \text{negl.}$

We define accountability as the proxy's capacity to check the shares integrity, and blame the corresponding provider whenever there is a corrupted share. We model this property with the game $\text{Exp}_{\mathcal{A}}^{\text{ACC}}$ of Fig. 6. The adversary plays the role of $k-1$ colluding CSPs during download aiming to alter the user's data. The challenger emulates the proxy, who wants to check which shares are corrupted. To win, the adversary's final answer $h_1, \dots, h_{k-1}$ must contain at least one corrupted share that would be accepted as correct by the proxy, but corresponding to a modified $m' \ne m$ with non-negligible probability. We let the adversary choose the initial message.

**Definition 21 (Accountability).** A KMPS scheme achieves accountability if for any adversary $\mathcal{A}$ we have $\text{Adv}_{\lambda}^{\text{ACC}}(\mathcal{A}) := \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{ACC}}(\lambda) = 1] \le \text{negl.}$

# 4 KMPS instantiations

Keyless storage schemes are secure up to a given corruption level. First, we propose a KMPS scheme KAPRE (Section 4.1), offering protection against a corrupted proxy or $k-1$ colluding providers. It remains vulnerable to a proxy colluding with a provider. Secondly, at the cost of an additional round of communications between the proxy and the providers, we propose another scheme KAME (Section 4.2) robust against a proxy colluding with $k-2$ providers.

The resulting state of an upload is the same in both schemes, allowing a common download (Section 4.3).

## 4.1 KAPRE – Upload using Proxy Re-Encryption

Let $p$ be a prime of at least $\lambda$ bits. Our design of KAPRE upload relies on an additively homomorphic proxy re-encryption scheme PRE and a key homomorphic pseudorandom function family $\mathcal{F} = \{F_s\}_{s \in \mathbb{Z}_p}$. As PRE is additively homomorphic, it commutes with Shamir's secret sharing (Definition 7). We describe the protocol below while the algorithms (KeyGen, Transform, Distrib, Open) are detailed in Fig. 8.

Consider a user willing to store some data $m$ among $n$ providers with a threshold recovery level of $k$ shares. First, in Transform the user samples a random key $\text{rekK}$ to encrypt its data $m$ as $ct$ with the symmetric encryption E. Then, it prepares a Shamir's secret sharing by encrypting $a_0 \leftarrow \text{rekK}$ and $k-1$ random coefficients $a_i$ with the additively homomorphic proxy re-encryption scheme as $\tilde{a}_i$. The user computes one share $y_0$ for the proxy in plaintext. Next, the user commits the coefficients used in $\text{comU}$ by evaluating the key homomorphic pseudorandom functions $F_{a_i}$ at a same random point $x$. The user also computes re-encryption
can be achieved if the proxy demonstrates the legitimacy of its request to the
providers.

**Definition 20 (User-Integrity).** A KMPS scheme achieves user-integrity if for any adversary $\mathcal{A}$ we have $\text{Adv}_{\lambda}^{\text{INTG}}(\mathcal{A}) := \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{INTG}}(\lambda) = 1] \le \text{negl.}$

We define accountability as the proxy's capacity to check the shares integrity, and blame the corresponding provider whenever there is a corrupted share. We model this property with the game $\text{Exp}_{\mathcal{A}}^{\text{ACC}}$ of Fig. 6. The adversary plays the role of $k-1$ *colluding* CSPs during download aiming to alter the user's data. The challenger emulates the proxy, who wants to check which shares are corrupted. To win, the adversary's final answer $h_1, \dots, h_{k-1}$ must contain at least one corrupted share that would be accepted as correct by the proxy, but corresponding to a modified $m' \neq m$ with non-negligible probability. We let the adversary choose the initial message.

**Definition 21 (Accountability).** A KMPS scheme achieves accountability if for any adversary $\mathcal{A}$ we have $\text{Adv}_{\lambda}^{\text{ACC}}(\mathcal{A}) := \text{Pr}[\text{Exp}_{\mathcal{A}}^{\text{ACC}}(\lambda) = 1] \le \text{negl.}$

# 4 KMPS instantiations

Keyless storage schemes are secure up to a given corruption level. First, we propose a KMPS scheme KAPRE (Section 4.1), offering protection against a corrupted proxy or $k-1$ colluding providers. It remains vulnerable to a proxy colluding with a provider. Secondly, at the cost of an additional round of communications between the proxy and the providers, we propose another scheme KAME (Section 4.2) robust against a proxy colluding with $k-2$ providers.

The resulting state of an upload is the same in both schemes, allowing a
common download (Section 4.3).

## 4.1 KAPRE – Upload using Proxy Re-Encryption

Let $p$ be a prime of at least $\lambda$ bits. Our design of KAPRE upload relies on an additively homomorphic proxy re-encryption scheme PRE and a key homomorphic pseudorandom function family $\mathcal{F} = \{F_s\}_{s \in \mathbb{Z}_p}$. As PRE is additively homomorphic, it commutes with Shamir's secret sharing (Definition 7). We describe the protocol below while the algorithms (KeyGen, Transform, Distrib, Open) are detailed in Fig. 8.

Consider a user willing to store some data $m$ among $n$ providers with a threshold recovery level of $k$ shares. First, in Transform the user samples a random key $\text{rekK}$ to encrypt its data $m$ as $ct$ with the symmetric encryption E. Then, it prepares a Shamir's secret sharing by encrypting $a_0 \leftarrow \text{rekK}$ and $k-1$ random coefficients $a_i$ with the additively homomorphic proxy re-encryption scheme as $\tilde{a}_i$. The user computes one share $y_0$ for the proxy in plaintext. Next, the user commits the coefficients used in $\text{comU}$ by evaluating the key homomorphic pseudorandom functions $F_{a_i}$ at a same random point $x$. The user also computes re-encryption
keys $rk_i$ towards each provider, although this only needs to be done whenever a party changes its keys. Finally, the user sends $\text{parts}_U \leftarrow (\{\tilde{a}_i\}_{i=0}^{k-1}, ct, \{rk_i\}_{i=1}^n, y_0)$ and $\text{com}_U \leftarrow (x, \{c_{a_i}\}_{i=0}^{k-1})$ to the proxy.

The proxy stores $\text{com}_U$, which will be used in download to check the shares integrity. Now the proxy can split the data into shares with Distrib. Confidentiality is ensured by the absence of any re-encryption key toward the proxy. It splits the encrypted data $ct$ with an IDA in shares $\{r_i\}_{i=0}^n$. Then, from the homomorphically encrypted coefficients $\tilde{a}_i$, the proxy evaluates encrypted Shamir shares $(i+1, \tilde{y}_i)$ as described in Section 2. Essentially, the proxy plays the role of the dealer in Shamir's secret sharing, that computes the shares blindly as the values are hidden by the encryption PRE that it cannot decrypt. Due to the homomorphic property of PRE, the resulting shares are exactly the ones that would be computed by the dealer in classical Shamir's secret sharing, hence still benefitting from its perfect secrecy. The proxy sends to each provider a share of the form $h_i \leftarrow (i+1, \text{PRE.ReEnc}(\tilde{y}_i, rk_i), r_i)$ while it stores its share $(1, y_0, r_0)$. Finally, each provider decrypts $\tilde{y}_i$ and stores its share $s_i \leftarrow (i+1, y_i, r_i)$.

Under the assumption that no more than $k$ providers may leak their share, $\text{rekC}$ is protected by Shamir's secret sharing perfect secrecy, and $m$ is protected by $E$'s security. On the other hand, the key is disposable as long as at least $k$ parties are accessible. Ultimately, as Shamir shares are of the size of their secret and IDA like Rabin's [28] produces shares of size $1/k$ of the secret, each provider holds a share of size $\lambda + |ct|/k$, which is almost optimal$^5$.

## 4.2 KAME – Upload Using Multikey Encryption

Our protocol KAME's achieves improved security properties. This section highlights the differences between KAPRE and KAME's upload. KAME's algorithms are formally described in Fig. 8. We consider an additively homomorphic multi-key encryption scheme MKE. Due to its homomorphic property, MKE also commutes with Shamir's secret sharing. The KAME scheme resembles KAPRE, where multikey encryption replaces proxy re-encryption. Each provider and the proxy possess a key pair for MKE. The polynomial coefficients $a_i$ of Shamir's secret sharing are encrypted under all the public keys. This mechanism requires the cooperation of all parties to decrypt each share. Hence, the decryption process becomes a two-round protocol involving the providers and the proxy. This approach provides higher security guarantees, as even one honest party can prevent a dishonest decryption.

## 4.3 Common Download

Due to the common structure of the resulting shares from an upload (a pair of a share from Shamir's secret sharing of $\text{rekC}$ and an IDA share of $ct$), we propose

<footnote>$^5$ As a ciphertext from a symmetric encryption usually is about the size of the plaintext, our protocol stores shares close to the optimal size of $|m|/k$, with an additional overhead of the size of the security parameter.</footnote>
keys $rk_i$ towards each provider, although this only needs to be done whenever a party changes its keys. Finally, the user sends $\text{parts}_U \leftarrow (\{\tilde{a}_i\}_{i=0}^{k-1}, ct, \{rk_i\}_{i=1}^n, y_0)$ and $\text{com}_U \leftarrow (x, \{c_{a_i}\}_{i=0}^{k-1})$ to the proxy.

The proxy stores $\text{com}_U$, which will be used in download to check the shares integrity. Now the proxy can split the data into shares with Distrib. Confidentiality is ensured by the absence of any re-encryption key toward the proxy. It splits the encrypted data $ct$ with an IDA in shares $\{r_i\}_{i=0}^n$. Then, from the homomorphically encrypted coefficients $\tilde{a}_i$, the proxy evaluates encrypted Shamir shares $(i+1, \tilde{y}_i)$ as described in Section 2. Essentially, the proxy plays the role of the dealer in Shamir's secret sharing, that computes the shares blindly as the values are hidden by the encryption PRE that it cannot decrypt. Due to the homomorphic property of PRE, the resulting shares are exactly the ones that would be computed by the dealer in classical Shamir's secret sharing, hence still benefitting from its perfect secrecy. The proxy sends to each provider a share of the form $h_i \leftarrow (i+1, \text{PRE.ReEnc}(\tilde{y}_i, rk_i), r_i)$ while it stores its share $(1, y_0, r_0)$. Finally, each provider decrypts $\tilde{y}_i$ and stores its share $s_i \leftarrow (i+1, y_i, r_i)$.

Under the assumption that no more than $k$ providers may leak their share, $\text{rekC}$ is protected by Shamir's secret sharing perfect secrecy, and $m$ is protected by $E$'s security. On the other hand, the key is disposable as long as at least $k$ parties are accessible. Ultimately, as Shamir shares are of the size of their secret and IDA like Rabin's [28] produces shares of size $1/k$ of the secret, each provider holds a share of size $\lambda + |ct|/k$, which is almost optimal$^5$.

## 4.2 KAME – Upload Using Multikey Encryption

Our protocol KAME's achieves improved security properties. This section highlights the differences between KAPRE and KAME's upload. KAME's algorithms are formally described in Fig. 8. We consider an additively homomorphic multi-key encryption scheme MKE. Due to its homomorphic property, MKE also commutes with Shamir's secret sharing. The KAME scheme resembles KAPRE, where multikey encryption replaces proxy re-encryption. Each provider and the proxy possess a key pair for MKE. The polynomial coefficients $a_i$ of Shamir's secret sharing are encrypted under all the public keys. This mechanism requires the cooperation of all parties to decrypt each share. Hence, the decryption process becomes a two-round protocol involving the providers and the proxy. This approach provides higher security guarantees, as even one honest party can prevent a dishonest decryption.

## 4.3 Common Download

Due to the common structure of the resulting shares from an upload (a pair of a share from Shamir's secret sharing of $\text{rekC}$ and an IDA share of $ct$), we propose

<footnote>$^5$ As a ciphertext from a symmetric encryption usually is about the size of the plaintext, our protocol stores shares close to the optimal size of $|m|/k$, with an additional overhead of the size of the security parameter.</footnote>
<table><caption>**Fig. 7.** Description of KAPRE and KAME uploads’ algorithms.</caption><thead><tr><th>Upload of KAPRE Protocol</th><th>Upload of KAME Protocol</th></tr></thead><tbody><tr><td>KeyGen(λ):<br>1: (pk<sup>PK</sup>, sk<sup>PK</sup>) ← PKE.KeyGen(λ)<br>2: (pk<sup>PR</sup>, sk<sup>PR</sup>) ← PRE.KeyGen(λ)<br>3: return (pk<sup>PK</sup>, pk<sup>PR</sup>), (sk<sup>PK</sup>, sk<sup>PR</sup>)<br>Transform(m, ⊥, pk<sub>1</sub><sup>PR</sup>, ..., pk<sub>n</sub><sup>PR</sup>):<br>1: recK ← E.KeyGen(λ)<br>2: ct ← E.Enc(m, recK)<br>3: (pk<sup>PR</sup>, sk<sup>PR</sup>) ← PRE.KeyGen(λ)<br>4: for i ∈ [1, n]:<br>5: rk<sub>i</sub> ← PRE.ReKey(sk, pk<sub>i</sub><sup>PR</sup>)<br>6: ˜a<sub>0</sub> ← PRE.Enc(recK, pk<sup>PR</sup>)<br>7: x ← $D, c_{a_0} \leftarrow F_{\text{recK}}(x)<br>8: for i \in [1, k-1]:<br>9: a_i ← $\mathbb{Z}_p, c_{a_i} \leftarrow F_{a_i}(x)<br>10: ˜a_i ← PRE.Enc(a_i, pk<sup>PR</sup>),<br>11: y_0 \leftarrow recK + \sum_{i=1}^{k-1} a_i<br>12: return com<sub>U</sub> = ({\tilde{a}_i}^k_{i=0}, ct, {rk_i}^n_{i=1}, y_0),<br>parts<sub>U</sub> = (x, {c_{a_i}}^k_{i=0})<br>Distrib(y_0, {\tilde{a}_i}^k_{i=0}, ct, {rk_i}^n_{i=1}):<br>1: {r_i}^n_{i=0} \leftarrow \text{IDA.Split}(ct, n+1, k)<br>2: \tilde{P}(x) = \sum_{i=0}^{k-1} \tilde{a}_i x^i<br>3: for i \in [1, n]: \tilde{y}_i \leftarrow \tilde{P}(i+1)<br>4: \tilde{y}_i \leftarrow \text{PRE.ReEnc}(\tilde{y}_i, rk_i)<br>5: return (1, y_0, r_0),<br>(i+1, \tilde{y}_i, r_i)}^n_{i=1}<br>Open(\tilde{y}_i, sk_i<sup>PR</sup>):<br>1: return y_i := \text{PRE.Dec}(\tilde{y}_i, sk_i<sup>PR</sup>)</td><td>KeyGen(λ):<br>1: (pk<sup>PK</sup>, sk<sup>PK</sup>) ← PKE.KeyGen(λ)<br>2: (pk<sup>MK</sup>, sk<sup>MK</sup>) ← MKE.KeyGen(λ)<br>3: return (pk<sup>PK</sup>, pk<sup>MK</sup>), (sk<sup>PK</sup>, sk<sup>MK</sup>)<br>Transform(m, pk<sub>0</sub><sup>MK</sup>, ..., pk<sub>n</sub><sup>MK</sup>):<br>1: recK ← E.KeyGen(λ)<br>2: ct ← E.Enc(m, recK)<br>3: ˜a<sub>0</sub> ← MKE.Enc(recK, {pk<sub>i</sub><sup>MK</sup>}<sup>n</sup><sub>i=0</sub>)<br>4: x ← $D, c_{a_0} \leftarrow F_{\text{recK}}(x)<br>5: for i \in [1, k-1]: a_i ← $\mathbb{Z}_p<br>6: ˜a_i ← MKE.Enc(a_i, {pk<sub>i</sub><sup>MK</sup>}<sup>n</sup><sub>i=0</sub>)<br>7: c_{a_i} \leftarrow F_{a_i}(x)<br>8: return ({\tilde{a}_i}^k_{i=0}, ct), (x, {c_{a_i}}^k_{i=0})<br>Distrib({\tilde{a}_i}^k_{i=0}, ct):<br>1: {r_i}^n_{i=0} \leftarrow \text{IDA.Split}(ct, n+1, k)<br>2: \tilde{P}(x) = \sum_{i=0}^{k-1} \tilde{a}_i x^i<br>3: for i \in [0, n]: \tilde{y}_i \leftarrow \tilde{P}(i+1)<br>4: return ({i+1, \tilde{y}_i, r_i})^n_{i=0}<br>Open(CSP_i(\tilde{y}_i, sk_i<sup>MK</sup>)^n_{i=1}, Proxy(\tilde{y}_0, sk<sub>0</sub><sup>MK</sup>)):<br>1: CSP_i:<br>2: y_j^{(i)} \leftarrow MKE.PartDec(\tilde{y}_j, sk_i<sup>MK</sup>)<br>3: CSP_i \to Proxy: \{y_j^{(i)}\}_{j \neq i}<br>4: Proxy \to CSP_i: \{y_i^{(j)}\}_{j \neq i}<br>5: CSP_i:<br>6: y_i \leftarrow MKE.FinDec(\{y_i^{(j)}\}_{j=0}^n)<br>6: Proxy:<br>7: y_0 \leftarrow MKE.FinDec(\{y_0^{(j)}\}_{j=0}^n)</td></tr></tbody></table>
<table><caption>Fig. 7. Description of KAPRE and KAME uploads’ algorithms.</caption><thead><tr><th>Upload of KAPRE Protocol</th><th>Upload of KAME Protocol</th></tr></thead><tbody><tr><td>KeyGen(λ):<br>1: (pk<sup>PK</sup>, sk<sup>PK</sup>) ← PKE.KeyGen(λ)<br>2: (pk<sup>PR</sup>, sk<sup>PR</sup>) ← PRE.KeyGen(λ)<br>3: return (pk<sup>PK</sup>, pk<sup>PR</sup>), (sk<sup>PK</sup>, sk<sup>PR</sup>)<br>Transform(m, ⊥, pk<sub>1</sub><sup>PR</sup>, ..., pk<sub>n</sub><sup>PR</sup>):<br>1: recK ← E.KeyGen(λ)<br>2: ct ← E.Enc(m, recK)<br>3: (pk<sup>PR</sup>, sk<sup>PR</sup>) ← PRE.KeyGen(λ)<br>4: for i ∈ [1, n]:<br>5:     rk<sub>i</sub> ← PRE.ReKey(sk, pk<sub>i</sub><sup>PR</sup>)<br>6:     ˜a<sub>0</sub> ← PRE.Enc(recK, pk<sup>PR</sup>)<br>7:     x ← $D, c_{a_0} \leftarrow F_{\text{recK}}(x)<br>8:     for i \in [1, k-1]:<br>9:         a_i ← $\mathbb{Z}_p, c_{a_i} \leftarrow F_{a_i}(x)<br>10:        ˜a_i ← PRE.Enc(a_i, pk<sup>PR</sup>),<br>11:        y_0 \leftarrow recK + \sum_{i=1}^{k-1} a_i<br>12:        return com<sub>U</sub> = ({\tilde{a}_i}^{k-1}_{i=0}, ct,<br>           {rk_i}^n_{i=1}, y_0),<br>           parts<sub>U</sub> = (x, {c_{a_i}}^{k-1}_{i=0})<br>           Distrib(y_0, {\tilde{a}_i}^{k-1}_{i=0}, ct, {rk_i}^n_{i=1}):<br>1:     {r_i}^n_{i=0} \leftarrow \text{IDA.Split}(ct, n+1, k)<br>2:     \tilde{P}(x) = \sum_{i=0}^{k-1} \tilde{a}_i x^i<br>3:     for i \in [1, n]: \tilde{y}_i \leftarrow \tilde{P}(i+1)<br>4:     \tilde{y}_i \leftarrow \text{PRE.ReEnc}(\tilde{y}_i, rk_i)<br>5:     return (1, y_0, r_0),<br>        ({i+1, \tilde{y}_i, r_i})^n_{i=1}<br>Open(\tilde{y}_i, sk_i^{PR}):<br>1: return y_i := \text{PRE.Dec}(\tilde{y}_i, sk_i^{PR})</td><td>KeyGen(λ):<br>1: (pk<sup>PK</sup>, sk<sup>PK</sup>) ← PKE.KeyGen(λ)<br>2: (pk<sup>MK</sup>, sk<sup>MK</sup>) ← MKE.KeyGen(λ)<br>3: return (pk<sup>PK</sup>, pk<sup>MK</sup>), (sk<sup>PK</sup>, sk<sup>MK</sup>)<br>Transform(m, pk<sub>0</sub><sup>MK</sup>, ..., pk<sub>n</sub><sup>MK</sup>):<br>1: recK ← E.KeyGen(λ)<br>2: ct ← E.Enc(m, recK)<br>3: ˜a<sub>0</sub> ← MKE.Enc(recK, {pk<sub>i</sub><sup>MK</sup>}<sup>n</sup><sub>i=0</sub>)<br>4: x ← $D, c_{a_0} \leftarrow F_{\text{recK}}(x)<br>5: for i \in [1, k-1]: a_i ← $\mathbb{Z}_p<br>6:     ˜a_i ← MKE.Enc(a_i, {pk<sub>i</sub><sup>MK</sup>}<sup>n</sup><sub>i=0</sub>)<br>7:     c_{a_i} \leftarrow F_{a_i}(x)<br>8: return ({\tilde{a}_i}^{k-1}_{i=0}, ct), (x, {c_{a_i}}^{k-1}_{i=0})<br>Distrib({\tilde{a}_i}^{k-1}_{i=0}, ct):<br>1: {r_i}^n_{i=0} \leftarrow \text{IDA.Split}(ct, n+1, k)<br>2: \tilde{P}(x) = \sum_{i=0}^{k-1} \tilde{a}_i x^i<br>3: for i \in [0, n]: \tilde{y}_i \leftarrow \tilde{P}(i+1)<br>4: return ({i+1, \tilde{y}_i, r_i})^n_{i=0}<br>Open(CSP_i(\tilde{y}_i, sk_i^{MK})^n_{i=1}, Proxy(\tilde{y}_0, sk<sub>0</sub><sup>MK</sup>)):<br>1: CSP_i:<br>    y_j^{(i)} \leftarrow \text{MKE.PartDec}(\tilde{y}_j, sk_i^{MK})<br>2: CSP_i \rightarrow \text{Proxy}: \{y_j^{(i)}\}_{j \neq i}<br>3: Proxy \rightarrow CSP_i: \{y_i^{(j)}\}_{j \neq i}<br>4: CSP_i:<br>    y_i \leftarrow \text{MKE.FinDec}(\{y_i^{(j)}\}_{j=0}^n)<br>5: Proxy:<br>    y_0 \leftarrow \text{MKE.FinDec}(\{y_0^{(j)}\}_{j=0}^n)</td></tr></tbody></table>
<figure><img src="image_6.png" /><figcaption>Fig. 8. Description of the download algorithms.</figcaption></figure>

a common download. Let PKE = (KeyGen, Enc, Dec) be an IND-CPA asymmetric encryption scheme.

Only $k$ shares are needed for data recovery. The proxy and the providers use their public key $pk_i^{PK}$ from PKE. The process starts with the client choosing $k$ providers to participate in the download, and executing *Designate*. It samples $k$ nonces, commits them in $com_D$ and encrypts one with each $pk_i^{PK}$. These ciphertexts and $com_D$ are sent to the proxy, which redirects each encrypted nonce to the designated provider. In *Hide*, each provider decrypts its nonce and adds it to its share $(i+1, y'_i := y_i + n_i)$ of $recK$ (this is essentially a one-time pad).

After gathering the shifted shares from the providers, the proxy computes a secret sharing reconstruction shiftK $\leftarrow \sum_{i=1}^{k} y'_{i} \ell_{i}$. First, the proxy does a batched verification on the shares by checking whether $recK + \sum_{i=1}^{k} n_{i} \ell_{i} = \sum_{i=1}^{k} y'_{i} \ell_{i}$ with $F_{recK}(x) \in com_U$ stored in upload and $F_{n_i}(x) \in com_D$, using the key-homomorphic property of $\mathcal{F}$. If the equality holds, the shares are correct and shiftK is sent back to the user along with the values $\ell_i$ and the reconstructed ct from the IDA. The user recover its data by shifting back $recK \leftarrow shiftK - \sum n_i \ell_i$ and decrypting ct with $recK$. By using an authenticated encryption [8], the decryption will fail if ct was altered. Otherwise, to detect which shares are corrupted, the proxy checks for each share if $y'_i - n_i = \sum_{j=0}^{k-1} a_j x_i^j$ from $c_{a_i} \in com_U$ and $com_D$, again using the key-homomorphic property of $\mathcal{F}$. Whenever the equality does not hold, the proxy blames the corresponding provider. The detailed process of the download algorithms is presented in Fig. 8.

The user can store the value $x$ to compute the commitments to the nonces. Otherwise, as the proxy stores $x$ in $com_U$ during upload, the user can ask the proxy for $x$ in the beginning of the download. Additionally, the user might not need to select which CSPs participate in the download, albeit at the cost of
<figure><img src="image_5.png" /><figcaption>Fig. 8. Description of the download algorithms.</figcaption></figure>

a common download. Let PKE = (KeyGen, Enc, Dec) be an IND-CPA asymmetric encryption scheme.

Only $k$ shares are needed for data recovery. The proxy and the providers use their public key $pk_i^{PK}$ from PKE. The process start with the client choosing $k$ providers to participate in the download, and executing **Designate**. It samples $k$ nonces, commits them in $com_D$ and encrypts one with each $pk_i^{PK}$. These ciphertexts and $com_D$ are sent to the proxy, which redirects each encrypted nonce to the designated provider. In **Hide**, each provider decrypts its nonce and adds it to its share $(i+1, y'_i := y_i + n_i)$ of **recK** (this is essentially a one-time pad).

After gathering the shifted shares from the providers, the proxy computes a secret sharing reconstruction **shiftK** $\leftarrow \sum_{i=1}^{k} y'_{i} \ell_{i}$. First, the proxy does a batched verification on the shares by checking whether **recK** + $\sum_{i=1}^{k} n_{i} \ell_{i} = \sum_{i=1}^{k} y'_{i} \ell_{i}$ with $F_{\text{recK}}(x) \in \text{comU}$ stored in upload and $F_{n_i}(x) \in \text{comD}$, using the key-homomorphic property of $\mathcal{F}$. If the equality holds, the shares are correct and **shiftK** is sent back to the user along with the values $\ell_i$ and the reconstructed $ct$ from the IDA. The user recover its data by shifting back **recK** $\leftarrow \text{shiftK} - \sum n_i \ell_i$ and decrypting $ct$ with **recK**. By using an authenticated encryption [8], the decryption will fail if $ct$ was altered. Otherwise, to detect which shares are corrupted, the proxy checks for each share if $y'_i - n_i = \sum_{j=0}^{k-1} a_j x_i^j$ from $c_{a_i} \in \text{comU}$ and $\text{comD}$, again using the key-homomorphic property of $\mathcal{F}$. Whenever the equality does not hold, the proxy blames the corresponding provider. The detailed process of the download algorithms is presented in Fig. 8.

The user can store the value $x$ to compute the commitments to the nonces. Otherwise, as the proxy stores $x$ in $com_U$ during upload, the user can ask the proxy for $x$ in the beginning of the download. Additionally, the user might not need to select which CSPs participate in the download, albeit at the cost of
slightly more computations. Instead, it can send nonces for all the providers,
allowing the proxy to determine which shares to utilize for reconstruction.

# 5 Security Analysis

In KAPRE, all shares are re-encrypted under $pk_i$ using $rk_i$. It's important to highlight that the proxy does not possess any re-encryption key and must obtain its share in plaintext. Otherwise, this situation opens up a direct attack: if the client sends the proxy a re-encryption key $rk_0$, allowing it to decrypt its share, the proxy could re-encrypt all parts of rek using its own public key and subsequently decrypt it, thereby revealing the content of ct. This implies that only 0-collusion-secrecy can be achieved for KAPRE in addition to provider-secrecy. We give sketch proofs that KAPRE indeed achieves these two properties in addition to user-integrity and accountability, and that KAME has $(k-2)$-collusion-secrecy, user-integrity and accountability. The full proofs are given in the long version [2]. Both schemes are correct, our implementation [2] demonstrate this.

## 5.1 Confidentiality

We assume that the designated parties participating in download are always the $k-1$ first CSPs and the proxy, up to a permutation (the proxy is essentially a CSP with additional knowledge).

**Theorem 1.** *Assume that PRE is PRE-IND, E is IND-CPA, $\mathcal{F}$ is pseudorandom and PKE is IND-CPA. Then KAPRE achieves 0-collusion-secrecy.*

*Proof.* We prove this theorem by a sequence of reductions.

Game $G_0$: the original game $\text{Exp}_{\mathcal{A},0}^{\text{Coll}}(\lambda)$ (Fig. 6) instantiated with KAPRE's algorithms.

Game $G_1$: the same game as $G_0$ except that the functions $\{F_{a_i}\}_{i=0}^{k-1}$ in $\text{com}_U$ and $\{F_{n_i}\}_{i=0}^{k-1}$ in $\text{com}_D$ are replaced by random functions.

Game $G_2$: the same game as $G_1$ except that $\{\tilde{a}_i\}_{i=0}^{k-1}$ are uniformly drawn in $[\text{PRE.Enc}]$.

Game $G_3$: the same as $G_2$ but the values $\{nc_i\}_{i=0}^{k-1}$ are uniformly drawn from $[\text{PKE.Enc}]$.

Game $G_4$: the same as $G_3$ but the values $\{y'_i\}_{i=0}^{k-1}$ in the shares $h_i = (x_i, y'_i, r_i)$ sent by the providers in download are drawn uniformly.

Game $G_5$: the same as $G_4$ but $y_0$ is replaced by a random value.

*Claim.* We claim that $G_0$ and $G_1$ are indistinguishable, given that $\mathcal{F}$ is pseudorandom.

We create a sequence of $2k$ reductions $\mathcal{R}_1^0, \dots, \mathcal{R}_1^{2k-1}$. The first reduction $\mathcal{R}_1^0$ takes as input the tuple $(x, F_0(x))$ instead of $(x, F_{\text{rek}}(x))$ in $\text{com}_U$ and all other values are as $G_0$. Each reductions $\mathcal{R}_1^i$ for $i \in [1, 2k-1]$ takes as input $F_i(x)$ instead of $F_{a_i}(x)$ for $i \in [1, k-1]$ in $\text{com}_U$ and $F_{n_{i-k}}(x)$ in $\text{com}_D$ for $i \in [k, 2k-1]$ and all other values are as in $\mathcal{R}_1^{i-1}$. If all $F_i$ are random functions,
slightly more computations. Instead, it can send nonces for all the providers,
allowing the proxy to determine which shares to utilize for reconstruction.

# 5 Security Analysis

In KAPRE, all shares are re-encrypted under $pk_i$ using $rk_i$. It's important to highlight that the proxy does not possess any re-encryption key and must obtain its share in plaintext. Otherwise, this situation opens up a direct attack: if the client sends the proxy a re-encryption key $rk_0$, allowing it to decrypt its share, the proxy could re-encrypt all parts of rek using its own public key and subsequently decrypt it, thereby revealing the content of ct. This implies that only 0-collusion-secrecy can be achieved for KAPRE in addition to provider-secrecy. We give sketch proofs that KAPRE indeed achieves these two properties in addition to user-integrity and accountability, and that KAME has (k - 2)-collusion-secrecy, user-integrity and accountability. The full proofs are given in the long version [2]. Both schemes are correct, our implementation [2] demonstrate this.

## 5.1 Confidentiality

We assume that the designated parties participating in download are always the $k-1$ first CSPs and the proxy, up to a permutation (the proxy is essentially a CSP with additional knowledge).

**Theorem 1.** *Assume that PRE is PRE-IND, E is IND-CPA, $\mathcal{F}$ is pseudorandom and PKE is IND-CPA. Then KAPRE achieves 0-collusion-secrecy.*

*Proof.* We prove this theorem by a sequence of reductions.

Game $G_0$: the original game $\text{Exp}_{\mathcal{A},0}^{\text{Coll}}(\lambda)$ (Fig. 6) instantiated with KAPRE's algorithms.

Game $G_1$: the same game as $G_0$ except that the functions $\{F_{a_i}\}_{i=0}^{k-1}$ in $\text{com}_U$ and $\{F_{n_i}\}_{i=0}^{k-1}$ in $\text{com}_D$ are replaced by random functions.

Game $G_2$: the same game as $G_1$ except that $\{\tilde{a}_i\}_{i=0}^{k-1}$ are uniformly drawn in $[\text{PRE.Enc}]$.

Game $G_3$: the same as $G_2$ but the values $\{nc_i\}_{i=0}^{k-1}$ are uniformly drawn from $[\text{PKE.Enc}]$.

Game $G_4$: the same as $G_3$ but the values $\{y'_i\}_{i=0}^{k-1}$ in the shares $h_i = (x_i, y'_i, r_i)$ sent by the providers in download are drawn uniformly.

Game $G_5$: the same as $G_4$ but $y_0$ is replaced by a random value.

*Claim.* We claim that $G_0$ and $G_1$ are indistinguishable, given that $\mathcal{F}$ is pseudorandom.

We create a sequence of $2k$ reductions $\mathcal{R}_1^0, \dots, \mathcal{R}_1^{2k-1}$. The first reduction $\mathcal{R}_1^0$ takes as input the tuple $(x, F_0(x))$ instead of $(x, F_{\text{rek}}(x))$ in $\text{com}_U$ and all other values are as $G_0$. Each reductions $\mathcal{R}_1^i$ for $i \in [1, 2k-1]$ takes as input $F_i(x)$ instead of $F_{a_i}(x)$ for $i \in [1, k-1]$ in $\text{com}_U$ and $F_{n_{i-k}}(x)$ in $\text{com}_D$ for $i \in [k, 2k-1]$ and all other values are as in $\mathcal{R}_1^{i-1}$. If all $F_i$ are random functions,
$\mathcal{R}_1^{2k-1}$ simulates $G_1$ perfectly, and if $F_i \leftarrow F_{a_i}$, $F_{i+k} \leftarrow F_{n_i}$ for $i \in [0, k-1]$ it simulates $G_0$ perfectly. We have $|\text{Adv}(\mathcal{R}_1^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_1^{i+1}(\mathcal{A}))| \le \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A})$, hence

$$|\text{Adv}_0(\mathcal{A}) - \text{Adv}_1(\mathcal{A})| \le 2k \cdot \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A})$$

and the claim follows.

**Claim.** We claim that $G_1$ and $G_2$ are indistinguishable, given that PRE is PRE-IND.

By a similar argument, we make a sequence of $k$ reductions $\mathcal{R}_2^i$ where $\mathcal{R}_2^0$ takes as input the tuple $rk_1, \dots, rk_n, \tilde{a}_0$ and all other values are set as in $G_1$. Then, the reduction $\mathcal{R}_2^i$ takes as input $\tilde{a}_i$ and all other values are set as in $\mathcal{R}_2^{i-1}$. If all $\tilde{a}_i$ are random, $\mathcal{R}_2^{k-1}$ simulates $G_2$ perfectly, otherwise if $\tilde{a}_i \leftarrow \text{PRE.Enc}(a_i, \text{pk}^{\text{PR}})$ it simulates $G_1$ perfectly. We have $|\text{Adv}(\mathcal{R}_2^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_2^{i+1}(\mathcal{A}))| \le \text{Adv}_{\lambda}^{\text{PRE-IND}}(\mathcal{A})$, hence

$$|\text{Adv}_1(\mathcal{A}) - \text{Adv}_2(\mathcal{A})| \le k \cdot \text{Adv}_{\lambda}^{\text{PRE-IND}}(\mathcal{A})$$

which is negligible given that PRE is PRE-IND.

**Claim.** We claim that $G_2$ and $G_3$ are indistinguishable, given that PKE is IND-CPA.

We make the same argument as in the previous claim by creating a sequence of $k$ reductions $\mathcal{R}_3^i$, except that we replace the ciphertexts $nc_i$. It follows that

$$|\text{Adv}_2(\mathcal{A}) - \text{Adv}_3(\mathcal{A})| \le k \cdot \text{Adv}_{\lambda}^{\text{IND-CPA}}(\mathcal{A})$$

which is negligible given that PKE is IND-CPA.

**Claim.** We claim $\mathcal{A}$'s advantage is the same in $G_3$ and $G_4$.

Let $\mathcal{R}_4$ be the reduction such that $\text{Adv}(\mathcal{R}_4) = |\text{Adv}_4(\mathcal{A}) - \text{Adv}_3(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $y'_i$ from the shares $h_i \leftarrow (x_i, y'_i, r_i)$, and all other values are setup as in $G_3$. If $y'_i \leftarrow y_i + n_i$, $\mathcal{R}_4$ simulates perfectly $G_3$. However, as $n_i$ is drawn uniformly by the challenger and independent of all of $\mathcal{A}$'s others inputs, $y'_i$ also follows a uniform distribution and $\mathcal{R}_4$ also simulates perfectly $G_4$. Thus we have $\text{Adv}(\mathcal{R}_4) = 0$ and the claim follows.

**Claim.** We claim $\mathcal{A}$'s advantage is the same in $G_4$ and $G_5$.

Let $\mathcal{R}_5$ be the reduction such that $\text{Adv}(\mathcal{R}_5) = |\text{Adv}_5(\mathcal{A}) - \text{Adv}_4(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $y_0$, and all other values are setup as in $G_4$. If $y_0$ is a share from Shamir's secret sharing, $\mathcal{R}_5$ simulates $G_4$, otherwise if $y_0$ is sampled uniformly $\mathcal{R}_5$ simulates $G_5$. From Shamir's secret sharing perfect secrecy, we have $\text{Adv}(\mathcal{R}_5) = 0$ and the claim follows.

**Claim.** We claim that $\mathcal{A}$'s advantage in $G_5$ is negligible given that $E$ is IND-CPA.

Let $\mathcal{R}$ be the reduction such that $\text{Adv}_5(\mathcal{A}) = \text{Adv}_{\lambda}^{\text{IND-CPA}}(\mathcal{R}(\mathcal{A}))$. It uses the challenger's response $ct$ to answer $m_0, m_1$ the adversary's request. All of the others inputs are as in $G_5$, random and independent of $\text{rek}$. Finally, the reduction outputs the adversary's answer. The claim follows.

**Theorem 2.** Assume that $E$ is IND-CPA. Then KAPRE has provider-secrecy.
$\mathcal{R}_1^{2k-1}$ simulates $G_1$ perfectly, and if $F_i \leftarrow F_{a_i}$, $F_{i+k} \leftarrow F_{n_i}$ for $i \in [0, k-1]$ it simulates $G_0$ perfectly. We have $|\text{Adv}(\mathcal{R}_1^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_1^{i+1}(\mathcal{A}))| \le \text{Adv}_\lambda^{\text{PRF}}(\mathcal{A})$, hence

$$|\text{Adv}_0(\mathcal{A}) - \text{Adv}_1(\mathcal{A})| \le 2k \cdot \text{Adv}_\lambda^{\text{PRF}}(\mathcal{A})$$

and the claim follows.

**Claim.** We claim that $G_1$ and $G_2$ are indistinguishable, given that PRE is PRE-IND.

By a similar argument, we make a sequence of $k$ reductions $\mathcal{R}_2^i$ where $\mathcal{R}_2^0$ takes as input the tuple $rk_1, \dots, rk_n, \tilde{a}_0$ and all other values are set as in $G_1$. Then, the reduction $\mathcal{R}_2^i$ takes as input $\tilde{a}_i$ and all other values are set as in $\mathcal{R}_2^{i-1}$. If all $\tilde{a}_i$ are random, $\mathcal{R}_2^{k-1}$ simulates $G_2$ perfectly, otherwise if $\tilde{a}_i \leftarrow \text{PRE.Enc}(a_i, \text{pk}^{\text{PR}})$ it simulates $G_1$ perfectly. We have $|\text{Adv}(\mathcal{R}_2^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_2^{i+1}(\mathcal{A}))| \le \text{Adv}_\lambda^{\text{PRE-IND}}(\mathcal{A})$, hence

$$|\text{Adv}_1(\mathcal{A}) - \text{Adv}_2(\mathcal{A})| \le k \cdot \text{Adv}_\lambda^{\text{PRE-IND}}(\mathcal{A})$$

which is negligible given that PRE is PRE-IND.

**Claim.** We claim that $G_2$ and $G_3$ are indistinguishable, given that PKE is IND-CPA.

We make the same argument as in the previous claim by creating a sequence of $k$ reductions $\mathcal{R}_3^i$, except that we replace the ciphertexts $nc_i$. It follows that

$$|\text{Adv}_2(\mathcal{A}) - \text{Adv}_3(\mathcal{A})| \le k \cdot \text{Adv}_\lambda^{\text{IND-CPA}}(\mathcal{A})$$

which is negligible given that PKE is IND-CPA.

**Claim.** We claim $\mathcal{A}$'s advantage is the same in $G_3$ and $G_4$.

Let $\mathcal{R}_4$ be the reduction such that $\text{Adv}(\mathcal{R}_4) = |\text{Adv}_4(\mathcal{A}) - \text{Adv}_3(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $y'_i$ from the shares $h_i \leftarrow (x_i, y'_i, r_i)$, and all other values are setup as in $G_3$. If $y'_i \leftarrow y_i + n_i$, $\mathcal{R}_4$ simulates perfectly $G_3$. However, as $n_i$ is drawn uniformly by the challenger and independent of all of $\mathcal{A}$'s others inputs, $y'_i$ also follows a uniform distribution and $\mathcal{R}_4$ also simulates perfectly $G_4$. Thus we have $\text{Adv}(\mathcal{R}_4) = 0$ and the claim follows.

**Claim.** We claim $\mathcal{A}$'s advantage is the same in $G_4$ and $G_5$.

Let $\mathcal{R}_5$ be the reduction such that $\text{Adv}(\mathcal{R}_5) = |\text{Adv}_5(\mathcal{A}) - \text{Adv}_4(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $y_0$, and all other values are setup as in $G_4$. If $y_0$ is a share from Shamir's secret sharing, $\mathcal{R}_5$ simulates $G_4$, otherwise if $y_0$ is sampled uniformly $\mathcal{R}_5$ simulates $G_5$. From Shamir's secret sharing perfect secrecy, we have $\text{Adv}(\mathcal{R}_5) = 0$ and the claim follows.

**Claim.** We claim that $\mathcal{A}$'s advantage in $G_5$ is negligible given that $E$ is IND-CPA.

Let $\mathcal{R}$ be the reduction such that $\text{Adv}_5(\mathcal{A}) = \text{Adv}_\lambda^{\text{IND-CPA}}(\mathcal{R}(\mathcal{A}))$. It uses the challenger's response $ct$ to answer $m_0, m_1$ the adversary's request. All of the others inputs are as in $G_5$, random and independent of $\text{rek}$. Finally, the reduction outputs the adversary's answer. The claim follows.

**Theorem 2.** Assume that $E$ is IND-CPA. Then KAPRE has provider-secrecy.
*Proof.* We prove this theorem by a sequence of reductions.

**Game G<sub>0</sub>:** the original game $\text{Exp}_{\mathcal{A}}^{\text{CSP}}(\lambda)$ (Fig. 6) instantiated with KAPRE algorithms. In this game, $\mathcal{A}$ is input shares $(x_i, \tilde{y}_i, r_i)$ and nonces $\{\text{nc}_i\}_{i=1}^{k-1}$ (line 10), where $\tilde{y}_i = \text{PKE.Enc}(y_i, \text{pk}_i^{\text{PK}})$. The couples $(x_i, y_i)$ are shares from a Shamir's secret sharing of recK, and $r_i$ are shares of $ct := \text{E.Enc}(m_b, \text{recK})$ from Rabin's IDA, both with threshold $k$.

**Game G<sub>1</sub>:** the same as G<sub>0</sub>, but the values $y_i$ are sampled uniformly.

**Game G<sub>2</sub>:** the same as G<sub>1</sub>, but $ct$ is uniformly sampled of the same length as the messages chosen by the adversary in its first interaction.

*Claim.* We claim that $\mathcal{A}$'s advantage in G<sub>0</sub> and G<sub>1</sub> are the same.

Let $\mathcal{R}_1$ be the reduction such that $\text{Adv}(\mathcal{R}_1) = |\text{Adv}_1(\mathcal{A}) - \text{Adv}_0(\mathcal{A})|$. The reduction $\mathcal{R}_1$ takes as input the instance $(x_i, y_i)_{i=1}^{k-1}$, and all other values are setup as in G<sub>0</sub>. If $(x_i, y_i)_{i=1}^{k-1}$ are shares from Shamir's secret sharing, $\mathcal{R}_1$ simulates G<sub>0</sub>, otherwise if $y_i$ are sampled uniformly $\mathcal{R}_1$ simulates G<sub>1</sub>. From Shamir's secret sharing perfect secrecy, we have $\text{Adv}(\mathcal{R}_1) = 0$.

*Claim.* We claim G<sub>1</sub> and G<sub>2</sub> are indistinguishable, given that E is IND-CPA.

Let $\mathcal{R}_2$ be the reduction such that $\text{Adv}(\mathcal{R}_2) = |\text{Adv}_2(\mathcal{A}) - \text{Adv}_1(\mathcal{A})|$. The reduction $\mathcal{R}_2$ takes as input the shares $r_1, \dots, r_{k-1}$, and all other values are setup as in G<sub>1</sub>. If $r_1, \dots, r_{k-1}$ are shares of E.Enc($m$, recK) then $\mathcal{R}_2$ simulates G<sub>2</sub>, otherwise if they are shares of a uniformly sampled value $\mathcal{R}_2$ simulates G<sub>1</sub>. Under the assumption that E is IND-CPA, we have $\text{Adv}(\mathcal{R}_2) \le \text{Adv}_{\lambda}^{\text{IND}}$-CPA($\mathcal{A}$).

*Claim.* The adversary's advantage in G<sub>2</sub> is $\text{Adv}_2(\mathcal{A}) = 0$.

As all of $\mathcal{A}$'s inputs are random values independent of $m_b$, the only thing $\mathcal{A}$ can do is guess randomly.

**Theorem 3.** Assume that E is IND-CPA, MKE has internal security, $\mathcal{F}$ is pseudorandom and the encryption PKE is IND-CPA. Then KAME has $(k-2)$-collusion-secrecy for a Shamir threshold $k$.

*Proof.* We use a strategy very similar to the one used in Theorem 1.

**Game G<sub>0</sub>:** the original game $\text{Exp}_{\mathcal{A},k-2}^{\text{Coll}}(\lambda)$ (Fig. 6) instantiated with KAME's algorithms.

**Game G<sub>1</sub>:** the same game as G<sub>0</sub> except that the functions $\{F_{a_i}\}_{i=0}^{k-1}$ in $\text{com}_U$ and $F_{n_{k-1}}$ in $\text{com}_D$ are replaced by random functions.

**Game G<sub>2</sub>:** the same game as G<sub>1</sub> except that $\{\tilde{a}_i\}_{i=0}^{k-1}$ are uniformly drawn in $[\text{MKE.Enc}]$.

**Game G<sub>3</sub>:** the same as G<sub>2</sub> but $\text{nc}_{k-1}$ is uniformly drawn from $[\text{PKE.Enc}]$.

**Game G<sub>4</sub>:** the same as G<sub>3</sub> but the value $y'_{k-1}$ in the share $h_{k-1} \leftarrow (x_{k-1}, y'_{k-1}, r_{k-1})$ sent by the challenger is drawn uniformly.

**Game G<sub>5</sub>:** the same as G<sub>4</sub> but the challenger computes $\tilde{y}_i \leftarrow \text{MKE.Enc}(y_i, \{\text{pk}_i^{\text{MK}}\}_{i=0}^n)$ by drawing uniformly $y_i$ for $i \in [0, k-2]$.

*Claim.* We claim that G<sub>0</sub> and G<sub>1</sub> are indistinguishable, given that $\mathcal{F}$ is pseudorandom.
*Proof.* We prove this theorem by a sequence of reductions.

**Game G<sub>0</sub>:** the original game $\text{Exp}_{\mathcal{A}}^{\text{CSP}}(\lambda)$ (Fig. 6) instantiated with KAPRE algorithms. In this game, $\mathcal{A}$ is input shares $(x_i, \tilde{y}_i, r_i)$ and nonces $\{\text{nc}_i\}_{i=1}^{k-1}$ (line 10), where $\tilde{y}_i = \text{PKE.Enc}(y_i, \text{pk}_i^{\text{PK}})$. The couples $(x_i, y_i)$ are shares from a Shamir's secret sharing of recK, and $r_i$ are shares of $ct := \text{E.Enc}(m_b, \text{recK})$ from Rabin's IDA, both with threshold $k$.

**Game G<sub>1</sub>:** the same as G<sub>0</sub>, but the values $y_i$ are sampled uniformly.

**Game G<sub>2</sub>:** the same as G<sub>1</sub>, but $ct$ is uniformly sampled of the same length as the messages chosen by the adversary in its first interaction.

*Claim.* We claim that $\mathcal{A}$'s advantage in G<sub>0</sub> and G<sub>1</sub> are the same.

Let $\mathcal{R}_1$ be the reduction such that $\text{Adv}(\mathcal{R}_1) = |\text{Adv}_1(\mathcal{A}) - \text{Adv}_0(\mathcal{A})|$. The reduction $\mathcal{R}_1$ takes as input the instance $(x_i, y_i)_{i=1}^{k-1}$, and all other values are setup as in G<sub>0</sub>. If $(x_i, y_i)_{i=1}^{k-1}$ are shares from Shamir's secret sharing, $\mathcal{R}_1$ simulates G<sub>0</sub>, otherwise if $y_i$ are sampled uniformly $\mathcal{R}_1$ simulates G<sub>1</sub>. From Shamir's secret sharing perfect secrecy, we have $\text{Adv}(\mathcal{R}_1) = 0$.

*Claim.* We claim G<sub>1</sub> and G<sub>2</sub> are indistinguishable, given that E is IND-CPA.

Let $\mathcal{R}_2$ be the reduction such that $\text{Adv}(\mathcal{R}_2) = |\text{Adv}_2(\mathcal{A}) - \text{Adv}_1(\mathcal{A})|$. The reduction $\mathcal{R}_2$ takes as input the shares $r_1, \dots, r_{k-1}$, and all other values are setup as in G<sub>1</sub>. If $r_1, \dots, r_{k-1}$ are shares of E.Enc($m$, recK) then $\mathcal{R}_2$ simulates G<sub>2</sub>, otherwise if they are shares of a uniformly sampled value $\mathcal{R}_2$ simulates G<sub>1</sub>. Under the assumption that E is IND-CPA, we have $\text{Adv}(\mathcal{R}_2) \le \text{Adv}_{\lambda}^{\text{IND}}$-CPA($\mathcal{A}$).

*Claim.* The adversary's advantage in G<sub>2</sub> is $\text{Adv}_2(\mathcal{A}) = 0$.

As all of $\mathcal{A}$'s inputs are random values independent of $m_b$, the only thing $\mathcal{A}$ can do is guess randomly.

**Theorem 3.** Assume that E is IND-CPA, MKE has internal security, $\mathcal{F}$ is pseudorandom and the encryption PKE is IND-CPA. Then KAME has $(k-2)$-collusion-secrecy for a Shamir threshold $k$.

*Proof.* We use a strategy very similar to the one used in Theorem 1.

**Game G<sub>0</sub>:** the original game $\text{Exp}_{\mathcal{A},k-2}^{\text{Coll}}(\lambda)$ (Fig. 6) instantiated with KAME's algorithms.

**Game G<sub>1</sub>:** the same game as G<sub>0</sub> except that the functions $\{F_{a_i}\}_{i=0}^{k-1}$ in $\text{com}_U$ and $F_{n_{k-1}}$ in $\text{com}_D$ are replaced by random functions.

**Game G<sub>2</sub>:** the same game as G<sub>1</sub> except that $\{\tilde{a}_i\}_{i=0}^{k-1}$ are uniformly drawn in $[\text{MKE.Enc}]$.

**Game G<sub>3</sub>:** the same as G<sub>2</sub> but $\text{nc}_{k-1}$ is uniformly drawn from $[\text{PKE.Enc}]$.

**Game G<sub>4</sub>:** the same as G<sub>3</sub> but the value $y'_{k-1}$ in the share $h_{k-1} \leftarrow (x_{k-1}, y'_{k-1}, r_{k-1})$ sent by the challenger is drawn uniformly.

**Game G<sub>5</sub>:** the same as G<sub>4</sub> but the challenger computes $\tilde{y}_i \leftarrow \text{MKE.Enc}(y_i, \{\text{pk}_i^{\text{MK}}\}_{i=0}^n)$ by drawing uniformly $y_i$ for $i \in [0, k-2]$.

*Claim.* We claim that G<sub>0</sub> and G<sub>1</sub> are indistinguishable, given that $\mathcal{F}$ is pseudorandom.
We create a sequence of $k+1$ reductions $\mathcal{R}_1^0, \dots, \mathcal{R}_k^1$. The first reduction $\mathcal{R}_1^0$ takes as input the tuple $(x, F_0(x))$ instead of $(x, F_{\text{recK}}(x))$ in $\text{comU}$ and all other values are as $G_0$. Each reductions $\mathcal{R}_1^i$ for $i \in [1, k]$ takes as input $F_i(x)$ instead of $F_{a_i}(x)$ for $i \in [1, k-1]$ in $\text{comU}$ and $F_{n_{k-1}}(x)$ in $\text{comD}$ for $i=k$ and all other values are as in $\mathcal{R}_1^{i-1}$. If all $F_i$ are random functions, $\mathcal{R}_1^k$ simulates $G_1$ perfectly, and if $F_i \leftarrow F_{a_i}$ for $i \in [0, k-1]$, $F_k \leftarrow F_{n_{k-1}}$ it simulates $G_0$ perfectly. We have $|\text{Adv}(\mathcal{R}_1^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_1^{i+1}(\mathcal{A}))| \le \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A})$, hence

$$|\text{Adv}_0(\mathcal{A}) - \text{Adv}_1(\mathcal{A})| \le (k+1) \cdot \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A})$$

and the claim follows.

*Claim.* We claim that $G_1$ and $G_2$ are indistinguishable, given that MKE has internal security.

By a similar argument, we make a sequence of $k$ reductions $\mathcal{R}_2^i$ where $\mathcal{R}_2^0$ takes as input the tuple $rk_1, \dots, rk_n, \tilde{a}_0$ and all other values are set as in $G_1$. Then, the reduction $\mathcal{R}_2^i$ takes as input $\tilde{a}_i$ and all other values are set as in $\mathcal{R}_2^{i-1}$. If all $\tilde{a}_i$ are random, $\mathcal{R}_2^{k-1}$ simulates $G_2$ perfectly, otherwise if $\tilde{a}_i \leftarrow \text{MKE.Enc}(a_i, \{pk_i^{\text{MK}}\}_{i=0}^n)$ it simulates $G_1$ perfectly. We have $|\text{Adv}(\mathcal{R}_2^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_2^{i+1}(\mathcal{A}))| \le \text{Adv}_{\lambda}^{\text{INT}}(\mathcal{A})$, hence

$$|\text{Adv}_1(\mathcal{A}) - \text{Adv}_2(\mathcal{A})| \le k \cdot \text{Adv}_{\lambda}^{\text{INT}}(\mathcal{A})$$

which is negligible given that MKE has internal security.

*Claim.* We claim that $G_2$ and $G_3$ are indistinguishable, given that PKE is IND-CPA.

Let $\mathcal{R}_3$ be the reduction such that $\text{Adv}(\mathcal{R}_3) = |\text{Adv}_3(\mathcal{A}) - \text{Adv}_2(\mathcal{A})|$. The reduction $\mathcal{R}_3$ takes as input $\text{nc}_{k-1}$, and all other values are set as in $G_3$. If $\text{nc}_{k-1} \leftarrow \text{PKE.Enc}(n_{k-1}, pk_{k-1}^{\text{PK}})$, $\mathcal{R}_3$ simulates perfectly $G_3$, and if it as a random value it simulates perfectly $G_2$. Thus we have $\text{Adv}(\mathcal{R}_3) \le \text{Adv}_{\lambda}^{\text{IND}}$-CPA($\mathcal{A}$) and the claim follows.

*Claim.* We claim $\mathcal{A}$'s advantage is the same in $G_3$ and $G_4$.

Let $\mathcal{R}_4$ be the reduction such that $\text{Adv}(\mathcal{R}_4) = |\text{Adv}_4(\mathcal{A}) - \text{Adv}_3(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $y'_{k-1}$ from the shares $h_{k-1} = (x_{k-1}, y'_{k-1}, r_{k-1})$, and all other values are set as in $G_3$. If $y'_{k-1} \leftarrow y_{k-1} + n_{k-1}$, $\mathcal{R}_4$ simulates perfectly $G_3$. However, as $n_{k-1}$ is drawn uniformly by the challenger and independent of all of $\mathcal{A}$'s others inputs, $y'_{k-1}$ also follows a uniform distribution and $\mathcal{R}_4$ also simulates perfectly $G_4$. Thus we have $\text{Adv}(\mathcal{R}_4) = 0$ and the claim follows.

*Claim.* We claim $\mathcal{A}$'s advantage is the same in $G_4$ and $G_5$.

Let $\mathcal{R}_5$ be the reduction such that $\text{Adv}(\mathcal{R}_5) = |\text{Adv}_5(\mathcal{A}) - \text{Adv}_4(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $\{y_i\}_{i=0}^{k-2}$ (i.e., the result after the adversary decrypts its shares $\tilde{y}_i$), and all other values are set as in $G_4$. If $y_i$ are shares from a Shamir's secret sharing of threshold $k$, $\mathcal{R}_5$ simulates $G_4$, otherwise if they are sampled uniformly $\mathcal{R}_5$ simulates $G_5$. From Shamir's secret sharing perfect secrecy, we have $\text{Adv}(\mathcal{R}_5) = 0$ and the claim follows.
We create a sequence of $k+1$ reductions $\mathcal{R}_1^0, \dots, \mathcal{R}_1^k$. The first reduction $\mathcal{R}_1^0$ takes as input the tuple $(x, F_0(x))$ instead of $(x, F_{\text{recK}}(x))$ in $\text{comU}$ and all other values are as $G_0$. Each reductions $\mathcal{R}_1^i$ for $i \in [1, k]$ takes as input $F_i(x)$ instead of $F_{a_i}(x)$ for $i \in [1, k-1]$ in $\text{comU}$ and $F_{n_{k-1}}(x)$ in $\text{comD}$ for $i=k$ and all other values are as in $\mathcal{R}_1^{i-1}$. If all $F_i$ are random functions, $\mathcal{R}_1^k$ simulates $G_1$ perfectly, and if $F_i \leftarrow F_{a_i}$ for $i \in [0, k-1]$, $F_k \leftarrow F_{n_{k-1}}$ it simulates $G_0$ perfectly. We have $|\text{Adv}(\mathcal{R}_1^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_1^{i+1}(\mathcal{A}))| \le \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A})$, hence

$$|\text{Adv}_0(\mathcal{A}) - \text{Adv}_1(\mathcal{A})| \le (k+1) \cdot \text{Adv}_{\lambda}^{\text{PRF}}(\mathcal{A})$$

and the claim follows.

*Claim.* We claim that $G_1$ and $G_2$ are indistinguishable, given that MKE has internal security.

By a similar argument, we make a sequence of $k$ reductions $\mathcal{R}_2^i$ where $\mathcal{R}_2^0$ takes as input the tuple $rk_1, \dots, rk_n, \tilde{a}_0$ and all other values are set as in $G_1$. Then, the reduction $\mathcal{R}_2^i$ takes as input $\tilde{a}_i$ and all other values are set as in $\mathcal{R}_2^{i-1}$. If all $\tilde{a}_i$ are random, $\mathcal{R}_2^{k-1}$ simulates $G_2$ perfectly, otherwise if $\tilde{a}_i \leftarrow \text{MKE.Enc}(a_i, \{pk_i^{\text{MK}}\}_{i=0}^n)$ it simulates $G_1$ perfectly. We have $|\text{Adv}(\mathcal{R}_2^i(\mathcal{A})) - \text{Adv}(\mathcal{R}_2^{i+1}(\mathcal{A}))| \le \text{Adv}_{\lambda}^{\text{INT}}(\mathcal{A})$, hence

$$|\text{Adv}_1(\mathcal{A}) - \text{Adv}_2(\mathcal{A})| \le k \cdot \text{Adv}_{\lambda}^{\text{INT}}(\mathcal{A})$$

which is negligible given that MKE has internal security.

*Claim.* We claim that $G_2$ and $G_3$ are indistinguishable, given that PKE is IND-CPA.

Let $\mathcal{R}_3$ be the reduction such that $\text{Adv}(\mathcal{R}_3) = |\text{Adv}_3(\mathcal{A}) - \text{Adv}_2(\mathcal{A})|$. The reduction $\mathcal{R}_3$ takes as input $\text{nc}_{k-1}$, and all other values are set as in $G_3$. If $\text{nc}_{k-1} \leftarrow \text{PKE.Enc}(n_{k-1}, pk_{k-1}^{\text{PK}})$, $\mathcal{R}_3$ simulates perfectly $G_3$, and if it as a random value it simulates perfectly $G_2$. Thus we have $\text{Adv}(\mathcal{R}_3) \le \text{Adv}_{\lambda}^{\text{IND}}$-CPA($\mathcal{A}$) and the claim follows.

*Claim.* We claim $\mathcal{A}$'s advantage is the same in $G_3$ and $G_4$.

Let $\mathcal{R}_4$ be the reduction such that $\text{Adv}(\mathcal{R}_4) = |\text{Adv}_4(\mathcal{A}) - \text{Adv}_3(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $y'_{k-1}$ from the shares $h_{k-1} = (x_{k-1}, y'_{k-1}, r_{k-1})$, and all other values are set as in $G_3$. If $y'_{k-1} \leftarrow y_{k-1} + n_{k-1}$, $\mathcal{R}_4$ simulates perfectly $G_3$. However, as $n_{k-1}$ is drawn uniformly by the challenger and independent of all of $\mathcal{A}$'s others inputs, $y'_{k-1}$ also follows a uniform distribution and $\mathcal{R}_4$ also simulates perfectly $G_4$. Thus we have $\text{Adv}(\mathcal{R}_4) = 0$ and the claim follows.

*Claim.* We claim $\mathcal{A}$'s advantage is the same in $G_4$ and $G_5$.

Let $\mathcal{R}_5$ be the reduction such that $\text{Adv}(\mathcal{R}_5) = |\text{Adv}_5(\mathcal{A}) - \text{Adv}_4(\mathcal{A})|$. The reduction $\mathcal{R}_5$ takes as input $\{y_i\}_{i=0}^{k-2}$ (i.e., the result after the adversary decrypts its shares $\tilde{y}_i$), and all other values are set as in $G_4$. If $y_i$ are shares from a Shamir's secret sharing of threshold $k$, $\mathcal{R}_5$ simulates $G_4$, otherwise if they are sampled uniformly $\mathcal{R}_5$ simulates $G_5$. From Shamir's secret sharing perfect secrecy, we have $\text{Adv}(\mathcal{R}_5) = 0$ and the claim follows.
*Claim.* We claim that $\mathcal{A}$'s advantage in $G_5$ is negligible given that $E$ is IND-CPA.

Let $\mathcal{R}$ be the reduction such that $\text{Adv}_5(\mathcal{A}) = \text{Adv}_{\mathcal{A}}^{\text{IND-CPA}}(\mathcal{R}(\mathcal{A}))$. It uses the challenger's response $ct$ to answer $m_0, m_1$ the adversary's request. All of the others inputs are as in $G_5$, random and independent of recK. Finally, the reduction outputs the adversary's answer. The claim follows.

## 5.2 Integrity

As only the result of an upload is involved in the integrity and accountability games, we prove simultaneously that both schemes achieve these properties.

**Theorem 4.** *The schemes KAPRE and KAME achieve user-integrity under the assumption that $\mathcal{F}$ is pseudorandom, PKE is IND-CPA and $E$ has authenticity.*

*Proof.* We prove this theorem by a sequence of game reductions.

*Game $G_0$:* the original game $\text{Exp}_{\mathcal{A}}^{\text{INTG}}(\lambda)$ (Fig. 6) instantiated with the download algorithms, with $\text{com}_U, s_0, \dots, s_n$ the result from an upload.

*Game $G_1$:* the same as $G_0$ but the functions $F_{n_0}, \dots, F_{n_{k-1}}$ are replaced by random functions in *Designate*.

*Game $G_2$:* the same as $G_1$ but $\text{nc}_{k-1}$ is drawn uniformly from [PKE.Enc].

*Claim.* We claim that $G_0$ and $G_1$ are indistinguishable given that $\mathcal{F}$ is pseudorandom.

By a similar argument as in Theorem 1, this follows from a sequence of $k$ reductions on the pseudorandomness of $\mathcal{F}$.

*Claim.* We claim that $G_1$ and $G_2$ are indistinguishable given that PKE is IND-CPA.

We use the same argument as in Theorem 3.

*Claim.* We claim that $\text{Adv}_2(\mathcal{A})$ is negligible, given that $E$ has authenticity.

Let $\mathcal{R}_2$ be the reduction that takes as input $ct$ and all other values as in $G_2$, and outputs $\text{parts}_D$ whatever the adversary outputs. If it succeeds, the adversary managed to break the authenticity of $E$.

**Theorem 5.** *Both schemes have accountability given that $\mathcal{F}$ is pseudorandom.*

*Proof.* We prove this theorem by a sequence of game reductions.

*Game $G_0$:* the original game $\text{Exp}_{\mathcal{A}}^{\text{ACC}}(\lambda)$ (Fig. 6) instantiated with the download algorithms, where $\text{com}_U, s_0, \dots, s_n$ is the result from an upload.

*Game $G_1$:* the same as $G_0$ but the values $\{y_i\}_{i=1}^{k-1}$ are replaced by random values in the shares $s_i = (x_i, y_i, r_i)$.

*Claim.* We claim that $\mathcal{A}$'s advantage is the same in $G_0$ and $G_1$.

Let $\mathcal{R}_1$ be the reduction such that $\text{Adv}(\mathcal{R}_1) = |\text{Adv}_1(\mathcal{A}) - \text{Adv}_0(\mathcal{A})|$. The reduction $\mathcal{R}_1$ takes as input $(x_i, y_i)_{i=1}^{k-1}$, and all other values are setup as in $G_1$. If $(x_i, y_i)$ are shares from a Shamir's secret sharing of threshold $k$, $\mathcal{R}_1$ simulates $G_1$, otherwise if they are sampled uniformly it simulates $G_1$. From Shamir's secret sharing perfect secrecy (all of the other inputs are independent of recK and the coefficients used in the sharing), we have $\text{Adv}(\mathcal{R}_1) = 0$ and the claim follows.
*Claim.* We claim that $\mathcal{A}$'s advantage in $G_5$ is negligible given that $E$ is IND-CPA.

Let $\mathcal{R}$ be the reduction such that $\text{Adv}_5(\mathcal{A}) = \text{Adv}_{\mathcal{A}}^{\text{IND-CPA}}(\mathcal{R}(\mathcal{A}))$. It uses the challenger's response $ct$ to answer $m_0, m_1$ the adversary's request. All of the others inputs are as in $G_5$, random and independent of recK. Finally, the reduction outputs the adversary's answer. The claim follows.

## 5.2 Integrity

As only the result of an upload is involved in the integrity and accountability games, we prove simultaneously that both schemes achieve these properties.

**Theorem 4.** *The schemes KAPRE and KAME achieve user-integrity under the assumption that $\mathcal{F}$ is pseudorandom, PKE is IND-CPA and $E$ has authenticity.*

*Proof.* We prove this theorem by a sequence of game reductions.

*Game $G_0$:* the original game $\text{Exp}_{\mathcal{A}}^{\text{INTG}}(\lambda)$ (Fig. 6) instantiated with the download algorithms, with $\text{com}_U, s_0, \dots, s_n$ the result from an upload.

*Game $G_1$:* the same as $G_0$ but the functions $F_{n_0}, \dots, F_{n_{k-1}}$ are replaced by random functions in *Designate*.

*Game $G_2$:* the same as $G_1$ but $\text{nc}_{k-1}$ is drawn uniformly from [PKE.Enc].

*Claim.* We claim that $G_0$ and $G_1$ are indistinguishable given that $\mathcal{F}$ is pseudorandom.

By a similar argument as in Theorem 1, this follows from a sequence of $k$ reductions on the pseudorandomness of $\mathcal{F}$.

*Claim.* We claim that $G_1$ and $G_2$ are indistinguishable given that PKE is IND-CPA.

We use the same argument as in Theorem 3.

*Claim.* We claim that $\text{Adv}_2(\mathcal{A})$ is negligible, given that $E$ has authenticity.

Let $\mathcal{R}_2$ be the reduction that takes as input $ct$ and all other values as in $G_2$, and outputs $\text{parts}_D$ whatever the adversary outputs. If it succeeds, the adversary managed to break the authenticity of $E$.

**Theorem 5.** *Both schemes have accountability given that $\mathcal{F}$ is pseudorandom.*

*Proof.* We prove this theorem by a sequence of game reductions.

*Game $G_0$:* the original game $\text{Exp}_{\mathcal{A}}^{\text{ACC}}(\lambda)$ (Fig. 6) instantiated with the download algorithms, where $\text{com}_U, s_0, \dots, s_n$ is the result from an upload.

*Game $G_1$:* the same as $G_0$ but the values $\{y_i\}_{i=1}^{k-1}$ are replaced by random values in the shares $s_i = (x_i, y_i, r_i)$.

*Claim.* We claim that $\mathcal{A}$'s advantage is the same in $G_0$ and $G_1$.

Let $\mathcal{R}_1$ be the reduction such that $\text{Adv}(\mathcal{R}_1) = |\text{Adv}_1(\mathcal{A}) - \text{Adv}_0(\mathcal{A})|$. The reduction $\mathcal{R}_1$ takes as input $(x_i, y_i)_{i=1}^{k-1}$, and all other values are setup as in $G_1$. If $(x_i, y_i)$ are shares from a Shamir's secret sharing of threshold $k$, $\mathcal{R}_1$ simulates $G_1$, otherwise if they are sampled uniformly it simulates $G_1$. From Shamir's secret sharing perfect secrecy (all of the other inputs are independent of recK and the coefficients used in the sharing), we have $\text{Adv}(\mathcal{R}_1) = 0$ and the claim follows.
*Claim.* We claim that $Adv_1(\mathcal{A}) = 0$.

Now all of $\mathcal{A}$'s inputs are independent of *reck* randomly sampled, and the challenger's final answer depends on whether the adversary's outputs verifies a linear relation with $F_{\text{reck}}(x)$. Hence, the only thing $\mathcal{A}$ can do is guess randomly.

# 6 Instantiation and Experimental Results

We provide a proof-of-concept of both KAPRE and KAME in C++ available in [2]. We used this implementation to design benchmarks and evaluate the performance of our schemes.

<figure><img src="image_7.png" /><figcaption>**Fig. 9.** Average execution time comparison for KAPRE and KAME algorithms (over 500 trials) in function of the threshold $k$ for a number of providers $n = 15$. Open, Hide and Recover are not included as their times were negligible (< 0.05s).</figcaption></figure>

**Implementation details.** We use the OpenFHE [3] and Crypto++ [1] libraries to implement both schemes. We use the OpenFHE implementation of a proxy re-encryption scheme built from BGV [27]. We use the multiparty BGV encryption provided by OpenFHE for multikey encryption. We chose for symmetric encryption E the AES-128 implementation of Crypto++, and we use the Crypto++ implementation of Rabin's IDA. The asymmetric encryption scheme in download is done with the BGV encryption of OpenFHE. As for the PRF family, we implemented the key-homomorphic PRF family described in [4], which is highly parallelizable (we did not do it).

**Benchmark results.** Our tests were carried out on an Ubuntu 22.04.2 laptop equipped with an Intel i7-12800H processor of 4.8 GHz and 32 GB of RAM.
*Claim.* We claim that $Adv_1(\mathcal{A}) = 0$.

Now all of $\mathcal{A}$'s inputs are independent of *reck* randomly sampled, and the challenger's final answer depends on whether the adversary's outputs verifies a linear relation with $F_{\text{reck}}(x)$. Hence, the only thing $\mathcal{A}$ can do is guess randomly.

# 6 Instantiation and Experimental Results

We provide a proof-of-concept of both KAPRE and KAME in C++ available in [2]. We used this implementation to design benchmarks and evaluate the performance of our schemes.

<figure><img src="image_6.png" /><figcaption>**Fig. 9.** Average execution time comparison for KAPRE and KAME algorithms (over 500 trials) in function of the threshold $k$ for a number of providers $n = 15$. Open, Hide and Recover are not included as their times were negligible (< 0.05s).</figcaption></figure>

**Implementation details.** We use the OpenFHE [3] and Crypto++ [1] libraries to implement both schemes. We use the OpenFHE implementation of a proxy re-encryption scheme built from BGV [27]. We use the multiparty BGV encryption provided by OpenFHE for multikey encryption. We chose for symmetric encryption E the AES-128 implementation of Crypto++, and we use the Crypto++ implementation of Rabin's IDA. The asymmetric encryption scheme in download is done with the BGV encryption of OpenFHE. As for the PRF family, we implemented the key-homomorphic PRF family described in [4], which is highly parallelizable (we did not do it).

**Benchmark results.** Our tests were carried out on an Ubuntu 22.04.2 laptop equipped with an Intel i7-12800H processor of 4.8 GHz and 32 GB of RAM.
We upload and download messages of 1MB (to reflect the processing time of our algorithms instead of the encryption time of the data), for a threshold from $k = 2$ to 14 and a fixed number of providers $n = 15$ (only the complexity of Distrib depends on $n$, all the other algorithms have a constant time in $n$). We use the BGV parameters of OpenFHE that provide 128 bits of security.

**Upload.** We give in Fig. 9 the average times for the user to execute Transform and the proxy to execute Distrib, over 500 trials. We suppose the re-encryption keys $r_{k_i}$ are already known of the user in KAPRE, as the user does not have to change its PRE key everytime. The time taken by the user in Transform is linear in $k$ as it encrypts $k$ Shamir coefficients, and is constant in $n$. The complexity is the same in both KAPRE and KAME, as it only changes the kind of key used to encrypt the Shamir coefficients. In Distrib, the complexity of Shamir's secret sharing is linear both in $k$ and $n$ as computing one share costs $k$ scalar multiplications (plus a re-encryption in KAPRE). The parabolic shape comes from the IDA which complexity is in $O(nk - k^2)$ [29], hence the worst trade-off is for $k$ close to $n/2$. In Open, the time for each provider is constant in KAPRE, and linear in $n$ in KAME as each party computes $n + 1$ partial decryptions. We did not include these times in Fig. 9 as they are constant to 45ms per party in KAME and 1ms in KAPRE. However, even if Distrib takes more time in KAPRE as the proxy also computes $n$ re-encryptions, we stress that KAME is less efficient in the sense that it has an additional round of communications for decryption, which communication time is not taken into account in our experiments.

**Download.** We give in Fig. 9 the average times to execute Designate and Merge over 500 trials. The time for Designate is linear in $k$, as the user encrypts a nonce of each provider involved in recovery. The time for each provider to compute Hide its share is constant (about 1ms). The time for the proxy to check the shares is linear in $k$ as it computes a linear relation in the $k$ commitments to check integrity. Finally, the time for Recover is negligible (about 1ms) as it is essentially one AES decryption.

# 7 Conclusion

We propose an efficient and scalable KMPS scheme addressing collusion amongst providers, and collusion with a curious proxy. Our scheme also achieves data integrity on the user (*integrity*) and proxy (*accountability*) sides, while allowing *forgetful* users. We design two implementations: our first solution KAPRE involving proxy re-encryption and our second one KAME using multi-key encryption schemes. The first one is round optimal in the upload phase, but only provides security against a proxy not colluding with any providers. The second one offers confidentiality against a proxy colluding with up to $k-2$ malicious providers, but requires an additional round of communication.
We upload and download messages of 1MB (to reflect the processing time of our algorithms instead of the encryption time of the data), for a threshold from $k = 2$ to 14 and a fixed number of providers $n = 15$ (only the complexity of Distrib depends on $n$, all the other algorithms have a constant time in $n$). We use the BGV parameters of OpenFHE that provide 128 bits of security.

**Upload.** We give in Fig. 9 the average times for the user to execute Transform and the proxy to execute Distrib, over 500 trials. We suppose the re-encryption keys $r_{k_i}$ are already known of the user in KAPRE, as the user does not have to change its PRE key everytime. The time taken by the user in Transform is linear in $k$ as it encrypts $k$ Shamir coefficients, and is constant in $n$. The complexity is the same in both KAPRE and KAME, as it only changes the kind of key used to encrypt the Shamir coefficients. In Distrib, the complexity of Shamir's secret sharing is linear both in $k$ and $n$ as computing one share costs $k$ scalar multiplications (plus a re-encryption in KAPRE). The parabolic shape comes from the IDA which complexity is in $O(nk - k^2)$ [29], hence the worst trade-off is for $k$ close to $n/2$. In Open, the time for each provider is constant in KAPRE, and linear in $n$ in KAME as each party computes $n + 1$ partial decryptions. We did not include these times in Fig. 9 as they are constant to 45ms per party in KAME and 1ms in KAPRE. However, even if Distrib takes more time in KAPRE as the proxy also computes $n$ re-encryptions, we stress that KAME is less efficient in the sense that it has an additional round of communications for decryption, which communication time is not taken into account in our experiments.

**Download.** We give in Fig. 9 the average times to execute Designate and Merge over 500 trials. The time for Designate is linear in $k$, as the user encrypts a nonce of each provider involved in recovery. The time for each provider to compute Hide its share is constant (about 1ms). The time for the proxy to check the shares is linear in $k$ as it computes a linear relation in the $k$ commitments to check integrity. Finally, the time for Recover is negligible (about 1ms) as it is essentially one AES decryption.

# 7 Conclusion

We propose an efficient and scalable KMPS scheme addressing collusion amongst providers, and collusion with a curious proxy. Our scheme also achieves data integrity on the user (*integrity*) and proxy (*accountability*) sides, while allowing *forgetful* users. We design two implementations: our first solution KAPRE involving proxy re-encryption and our second one KAME using multi-key encryption schemes. The first one is round optimal in the upload phase, but only provides security against a proxy not colluding with any providers. The second one offers confidentiality against a proxy colluding with up to $k-2$ malicious providers, but requires an additional round of communication.
References

1. Crypto++ library, https://github.com/weidai11/cryptopp

2. Implementation, https://anonymous.4open.science/r/secureMPS-3031/

3. Al Badawi, A., Bates, J., Bergamaschi, F., Cousins, D.B., Erabelli, S., Genise, N., Halevi, S., Hunt, H., Kim, A., Lee, Y., et al.: Openfhe: Open-source fully homomorphic encryption library. In: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (2022)

4. Banerjee, A., Peikert, C.: New and improved key-homomorphic pseudorandom functions. In: CRYPTO 2014. pp. 353–370. Springer (2014)

5. Bauer, D.P.: Filecoin. Apress, Berkeley, CA (2022). https://doi.org/10.1007/978-1-4842-8045-4_8, https://doi.org/10.1007/978-1-4842-8045-4_8

6. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th Annual Symposium on Foundations of Computer Science. pp. 394–403. IEEE (1997)

7. Bellare, M., Namprempre, C.: Authenticated encryption: Relations among notions and analysis of the generic composition paradigm. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 531–545. Springer (2000)

8. Bellare, M., Rogaway, P., Wagner, D.: The eax mode of operation. In: Fast Software Encryption, 2004. pp. 389–407. Springer (2004)

9. Bessani, A.N., Correia, M., Quaresma, B., André, F., Sousa, P.: Depsky: Dependable and secure storage in a cloud-of-clouds. ACM Trans. Storage (2013)

10. Bessani, A.N., Mendes, R., Oliveira, T., Neves, N.F., Correia, M., Pasin, M., Veríssimo, P.: SCFS: A shared cloud-backed file system. In: Gibson, G., Zeldovich, N. (eds.) 2014 USENIX Annual Technical Conference. USENIX Association (2014)

11. Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. In: Nyberg, K. (ed.) EUROCRYPT '98. LNCS, Springer (1998)

12. Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic prfs and their applications. In: Annual Cryptology Conference. pp. 410–428. Springer (2013)

13. Chase, M., Davis, H., Ghosh, E., Laine, K.: Acesesor: A new framework for auditable custodial secret storage and recovery. Cryptology ePrint Archive (2022)

14. Chen, L., Zhang, Z., Wang, X.: Batched multi-hop multi-key fhe from ring-lwe with compact ciphertext extension. In: TCC 2017. pp. 597–627. Springer (2017)

15. Cohen, A.: What about bob? the inadequacy of CPA security for proxy reencryption. In: Lin, D., Sako, K. (eds.) PKC 2019 - 22nd IACR. LNCS, Springer (2019)

16. Kim, S.: Key-homomorphic pseudorandom functions from lwe with small modulus. In: EUROCRYPT 2020. pp. 576–607. Springer (2020)

17. Krawczyk, H.: Secret sharing made short. In: Annual international cryptology conference. pp. 136–146. Springer (1993)

18. Lee, H., Park, J.: On the security of multikey homomorphic encryption. In: Albrecht, M. (ed.) 17th IMA International Conference, IMACC 2019. LNCS, Springer (2019). https://doi.org/10.1007/978-3-030-35199-1\_12, https://doi.org/10.1007/978-3-030-35199-1\_12

19. Leila, M., Zitouni, A., Djoudi, M.: Ensuring user authentication and data integrity in multi-cloud environment. Hum. centric Comput. Inf. Sci. 10, 15 (2020). https://doi.org/10.1186/s13673-020-00224-y, https://doi.org/10.1186/s13673-020-00224-y
References

1. Crypto++ library, https://github.com/weidai11/cryptopp

2. Implementation, https://anonymous.4open.science/r/secureMPS-3031/

3. Al Badawi, A., Bates, J., Bergamaschi, F., Cousins, D.B., Erabelli, S., Genise, N., Halevi, S., Hunt, H., Kim, A., Lee, Y., et al.: Openfhe: Open-source fully homomorphic encryption library. In: Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (2022)

4. Banerjee, A., Peikert, C.: New and improved key-homomorphic pseudorandom functions. In: CRYPTO 2014. pp. 353–370. Springer (2014)

5. Bauer, D.P.: Filecoin. Apress, Berkeley, CA (2022). https://doi.org/10.1007/978-1-4842-8045-4_8, https://doi.org/10.1007/978-1-4842-8045-4_8

6. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th Annual Symposium on Foundations of Computer Science. pp. 394–403. IEEE (1997)

7. Bellare, M., Namprempre, C.: Authenticated encryption: Relations among notions and analysis of the generic composition paradigm. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 531–545. Springer (2000)

8. Bellare, M., Rogaway, P., Wagner, D.: The eax mode of operation. In: Fast Software Encryption, 2004. pp. 389–407. Springer (2004)

9. Bessani, A.N., Correia, M., Quaresma, B., André, F., Sousa, P.: Depsky: Dependable and secure storage in a cloud-of-clouds. ACM Trans. Storage (2013)

10. Bessani, A.N., Mendes, R., Oliveira, T., Neves, N.F., Correia, M., Pasin, M., Veríssimo, P.: SCFS: A shared cloud-backed file system. In: Gibson, G., Zeldovich, N. (eds.) 2014 USENIX Annual Technical Conference. USENIX Association (2014)

11. Blaze, M., Bleumer, G., Strauss, M.: Divertible protocols and atomic proxy cryptography. In: Nyberg, K. (ed.) EUROCRYPT '98. LNCS, Springer (1998)

12. Boneh, D., Lewi, K., Montgomery, H., Raghunathan, A.: Key homomorphic prfs and their applications. In: Annual Cryptology Conference. pp. 410–428. Springer (2013)

13. Chase, M., Davis, H., Ghosh, E., Laine, K.: Acesesor: A new framework for auditable custodial secret storage and recovery. Cryptology ePrint Archive (2022)

14. Chen, L., Zhang, Z., Wang, X.: Batched multi-hop multi-key fhe from ring-lwe with compact ciphertext extension. In: TCC 2017. pp. 597–627. Springer (2017)

15. Cohen, A.: What about bob? the inadequacy of CPA security for proxy reencryption. In: Lin, D., Sako, K. (eds.) PKC 2019 - 22nd IACR. LNCS, Springer (2019)

16. Kim, S.: Key-homomorphic pseudorandom functions from lwe with small modulus. In: EUROCRYPT 2020. pp. 576–607. Springer (2020)

17. Krawczyk, H.: Secret sharing made short. In: Annual international cryptology conference. pp. 136–146. Springer (1993)

18. Lee, H., Park, J.: On the security of multikey homomorphic encryption. In: Albrecht, M. (ed.) 17th IMA International Conference, IMACC 2019. LNCS, Springer (2019). https://doi.org/10.1007/978-3-030-35199-1\_12, https://doi.org/10.1007/978-3-030-35199-1\_12

19. Leila, M., Zitouni, A., Djoudi, M.: Ensuring user authentication and data integrity in multi-cloud environment. Hum. centric Comput. Inf. Sci. 10, 15 (2020). https://doi.org/10.1186/s13673-020-00224-y, https://doi.org/10.1186/s13673-020-00224-y
20. López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. IACR Cryptol. ePrint Arch. (2013), http://eprint.iacr.org/2013/094

21. Melki, R., Noura, H.N., Chehab, A.: Lightweight multi-factor mutual authenti-cation protocol for iot devices. International Journal of Information Security 19, 679-694 (2020)

22. Niknia, A., Correia, M., Karimpour, J.: Secure cloud-of-clouds storage with space-efficient secret sharing. J. Inf. Secur. Appl. (2021)

23. Orsini, C., Scafuro, A., Verber, T.: How to recover a cryptographic secret from the cloud. Cryptology ePrint Archive (2023)

24. Papaioannou, T.G., Bonvin, N., Aberer, K.: Scalia: an adaptive scheme for efficient multi-cloud storage. In: Hollingsworth, J.K. (ed.) SC 2012. IEEE/ACM (2012). https://doi.org/10.1109/SC.2012.101, https://doi.org/10.1109/SC.2012.101

25. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO '91. LNCS, Springer (1991)

26. Pietro, R.D., Scarpa, M., Giacobbe, M., Puliafito, A.: Secure storage as a service in multi-cloud environment. In: ADHOC-NOW 2017. LNCS, Springer (2017)

27. Polyakov, Y., Rohloff, K., Sahu, G., Vaikuntanathan, V.: Fast proxy re-encryption for publish/subscribe systems. ACM Transactions on Privacy and Security (TOPS) 20(4), 1-31 (2017)

28. Rabin, M.O.: Efficient dispersal of information for security, load balancing, and fault tolerance. J. ACM (1989)

29. Resch, J.K., Plank, J.S.: AONT-RS: blending security and performance in dis-persed storage systems. In: Ganger, G.R., Wilkes, J. (eds.) 9th USENIX Conference on File and Storage Technologies, 2011. USENIX (2011)

30. Rescorla, E.: RFC 8446: The transport layer security (TLS) protocol version 1.3 (2018)

31. Rocha, F., Correia, M.: Lucy in the sky without diamonds: Stealing confidential data in the cloud. In: IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W 2011) (2011)

32. Shamir, A.: How to share a secret. Commun. ACM (1979)

33. Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. IACR Cryptol. ePrint Arch. (2004)

34. Singh, Y., Kandah, F., Zhang, W.: A secured cost-effective multi-cloud storage in cloud computing. In: 2011 IEEE Conference (INFOCOM WKSHPS) (2011). https://doi.org/10.1109/INFCOMW.2011.5928887

35. Stefanov, E., Shi, E.: Multi-cloud oblivious storage. In: Sadeghi, A., Gligor, V.D., Yung, M. (eds.) ACM, CCS, 2013. ACM (2013)

36. Sulochana, M., Dubey, O.: Preserving data confidentiality using multi-cloud architecture. Procedia Computer Science 50, 357-362 (2015). https://doi.org/10.1016/j.procs.2015.04.035, https://www.sciencedirect.com/science/article/pii/S1877050915005360, big Data, Cloud and Computing Challenges

37. Wilcox-O'Hearn, Z., Warner, B.: Tahoe: the least-authority filesystem. In: ACM international workshop on Storage security and survivability. pp. 21-26 (2008)

38. Witanto, E.N., Stanley, B., Lee, S.: Distributed data integrity verification scheme in multi-cloud environment. Sensors 23(3), 1623 (2023). https://doi.org/10.3390/s23031623, https://doi.org/10.3390/s23031623
20. López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. IACR Cryptol. ePrint Arch. (2013), http://eprint.iacr.org/2013/094

21. Melki, R., Noura, H.N., Chehab, A.: Lightweight multi-factor mutual authentication protocol for iot devices. International Journal of Information Security 19, 679-694 (2020)

22. Niknia, A., Correia, M., Karimpour, J.: Secure cloud-of-clouds storage with space-efficient secret sharing. J. Inf. Secur. Appl. (2021)

23. Orsini, C., Scafuro, A., Verber, T.: How to recover a cryptographic secret from the cloud. Cryptology ePrint Archive (2023)

24. Papaioannou, T.G., Bonvin, N., Aberer, K.: Scalia: an adaptive scheme for efficient multi-cloud storage. In: Hollingsworth, J.K. (ed.) SC 2012. IEEE/ACM (2012). https://doi.org/10.1109/SC.2012.101, https://doi.org/10.1109/SC.2012.101

25. Pedersen, T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Feigenbaum, J. (ed.) CRYPTO '91. LNCS, Springer (1991)

26. Pietro, R.D., Scarpa, M., Giacobbe, M., Puliafito, A.: Secure storage as a service in multi-cloud environment. In: ADHOC-NOW 2017. LNCS, Springer (2017)

27. Polyakov, Y., Rohloff, K., Sahu, G., Vaikuntanathan, V.: Fast proxy re-encryption for publish/subscribe systems. ACM Transactions on Privacy and Security (TOPS) 20(4), 1-31 (2017)

28. Rabin, M.O.: Efficient dispersal of information for security, load balancing, and fault tolerance. J. ACM (1989)

29. Resch, J.K., Plank, J.S.: AONT-RS: blending security and performance in dispersed storage systems. In: Ganger, G.R., Wilkes, J. (eds.) 9th USENIX Conference on File and Storage Technologies, 2011. USENIX (2011)

30. Rescorla, E.: RFC 8446: The transport layer security (TLS) protocol version 1.3 (2018)

31. Rocha, F., Correia, M.: Lucy in the sky without diamonds: Stealing confidential data in the cloud. In: IEEE/IFIP International Conference on Dependable Systems and Networks Workshops (DSN-W 2011) (2011)

32. Shamir, A.: How to share a secret. Commun. ACM (1979)

33. Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. IACR Cryptol. ePrint Arch. (2004)

34. Singh, Y., Kandah, F., Zhang, W.: A secured cost-effective multi-cloud storage in cloud computing. In: 2011 IEEE Conference (INFOCOM WKSHPS) (2011). https://doi.org/10.1109/INFCOMW.2011.5928887

35. Stefanov, E., Shi, E.: Multi-cloud oblivious storage. In: Sadeghi, A., Gligor, V.D., Yung, M. (eds.) ACM, CCS, 2013. ACM (2013)

36. Sulochana, M., Dubey, O.: Preserving data confidentiality using multi-cloud architecture. Procedia Computer Science 50, 357-362 (2015). https://doi.org/10.1016/j.procs.2015.04.035, https://www.sciencedirect.com/science/article/pii/S1877050915005360, big Data, Cloud and Computing Challenges

37. Wilcox-O'Hearn, Z., Warner, B.: Tahoe: the least-authority filesystem. In: ACM international workshop on Storage security and survivability. pp. 21-26 (2008)

38. Witanto, E.N., Stanley, B., Lee, S.: Distributed data integrity verification scheme in multi-cloud environment. Sensors 23(3), 1623 (2023). https://doi.org/10.3390/s23031623, https://doi.org/10.3390/s23031623