Revisiting Shared Data Protection Against Key Exposure

arXiv:1901.08083 · cs.CR · Submitted 2019-01-23 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: We're looking at the paper: "Revisiting Shared Data Protection Against Key Exposure".

Elias: The gist This paper introduces two novel schemes for computational secret sharing that match an all-or-nothing security level under key exposure in distributed storage environments,

Nadia: First, who's behind it and why it matters.

Title and authors: Nadia: We talked about the title and authors of "Revisiting Shared Data Protection Against Key Exposure," which points to how they are taking the security model and applying it to real distributed storage scenarios.

Elias: The authors are Katarzyna Kapusta, Matthieu Rambaud, and Gerard Memmi. Their work directly addresses how to protect data when keys could be exposed in cloud or multi-cloud environments.

Nadia: What this means for us is that they are moving away from older security models because they realized the old ones weren't efficient enough for the way data is actually stored today.

Elias: It suggests a shift in thinking where we don't look at compromised blocks, but rather how many storage sites an adversary can compromise, which changes the whole approach to sharing secrets.

The paper's summary: Nadia: So the paper summarizes its main point by saying they are proposing a new security model called SAKE where the parameter is the number of compromised servers or sites instead of just blocks.

Elias: They define this as SAKE, and it asks for indistinguishability under chosen plaintext attack and under key exposure for n-one shares in possession of the attacker.

Nadia: This new model is motivated by the idea that if you compromise one block at one site, you can get access to more data stored on that same site because of how storage systems work.

Elias: They also introduce a public randomized keyed invertible transformation called AON, which is what they call an n-SAKE transformation when it meets specific properties.

Nadia: The paper then proposes two schemes to achieve this SAKE security level, one based on standard block cipher encryption and another that uses something like a random oracle or an idealized block cipher.

The paper's improvements: Elias: The paper shows improvements by presenting two specific schemes. First is SSAKE, which uses standard block cipher encryption and it reduces the processing needed for data encryption by half compared to the fastest existing solutions.

Nadia: That means SSAKE is faster than what you'd normally see with AES in this context, which is a big deal for performance in real systems.

Elias: Then they have ROSSake, which ditches the extra processing entirely by switching to something based on random oracles or an idealized block cipher with a key twice as large as the security parameter.

Nadia: So ROSSake completely cuts out that extra post-processing overhead, which is what I was looking for when we talked about efficiency in distributed storage.

Elias: And they benchmarked these against each other, showing that SSAKE is faster than Bastion by reducing the linear overhead by half, while ROSSake is actually the fastest of all SAKE schemes tested.

Conclusion: Nadia: To wrap up, the paper presents SSAKE as a versatile scheme that verifies both security properties for this new model, and ROSSake as an alternative random-oracle based scheme that has no extra processing overhead on top of encryption.

Elias: The main implication is that we have two distinct ways to achieve the all-or-nothing property under key exposure in distributed storage, with one focusing on speed gains and the other on eliminating post-processing costs.

Nadia: For someone just listening to the show, this means there are now concrete technical paths forward for building more robust encryption schemes that can handle the realities of cloud storage.

Elias: We're leaving this discussion here with "Revisiting Shared Data Protection Against Key Exposure," which lays out SSAKE and ROSSake as leading candidates for these new security requirements.

cs.CR

Submitted: 2019-01-23

Updated: 2026-10-16

Comments: 19 pages, 3 figures

DOI: 10.1145/3320269.3372198

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 72/100

The gist: The gist This paper introduces two novel schemes for computational secret sharing that match an all-or-nothing security level under key exposure in distributed storage environments, offering faster

Key concepts

All-or-Nothing (AON) Security: This security level means an adversary learns nothing about the data unless they possess both the entire ciphertext and the secret encryption key. The paper aims to achieve this property efficiently in distributed storage settings where key exposure is a risk.
SAKE Security Model: This new model focuses on compromising servers or sites rather than blocks. It requires that an adversary who compromises one site cannot gain access to other data stored at the same site, ensuring security even with partial server compromise.
SSAKE Scheme: This scheme uses a standard block cipher in CTR mode and involves four steps: encrypting data, transforming the ciphertext with a linear function, splitting it into n fragments, and sharing the initialization vector (IV) using perfect secret sharing to create final shares.
ROSSake Scheme: This alternative scheme avoids extra processing by using a random oracle model. It involves sampling a secret key K, creating a one-time pad with this key and IV, splitting the resulting padded data into n fragments, and combining them with secret shares of the IV.

Terminology

Computational overhead — 1× in this paper · explained in 2 episodes

Summary

The gist This paper introduces two novel schemes for computational secret sharing that match an all-or-nothing security level under key exposure in distributed storage environments, offering faster and more efficient solutions than existing state-of-the-art proposals.

Motivation and Problem Context

The research revisits the security model for encrypted data protection against key exposure to design faster schemes that leverage the characteristics of distributed storage, aiming for the same security properties as existing ones in this context of distributed storage<ref:1901.08083#pg6>. The problem addresses how to efficiently protect encrypted data against key exposure since the risk of key exposure is believed to be impossible to completely eradicate<ref:1901.08083#pg3>. A classical way of reinforcing data confidentiality against key exposure consists in encrypting the data in such a way that an adversary obtains no information unless she has the totality of the ciphertext, plus a secret encryption key: this property is denoted as all-or-nothing (AON)<ref:1901.08083#pg3>. The paper observes that former all-or-nothing works are not efficient because they require two rounds of encryption<ref:1901.08083#pg3>.

New Security Model and Threat Model

The authors propose a new model taking as parameter the number of compromised servers or sites instead of the amount of compromised blocks, motivated by the fact that an adversary able to compromise one ciphertext block in a given storage site has necessarily been able to acquire enough access rights to also be able to compromise other data stored in the same site by the same user<ref:1901.08083#pg4>. This new model is denoted as SAKE, where the security property (2) asks for the indistinguishability under chosen plaintext attack and under key exposure of the n − 1 shares in possession of the attacker<ref:1901.08083#pg5>. The authors define a public randomized keyed invertible transformation ”AON” that maps a plaintext P to n bit strings, which is called an n-SAKE transformation if it satisfies properties (1) and (2)<ref:1901.08083#pg6>.

Proposed Schemes

The paper introduces two novel schemes to achieve the SAKE security level<ref:1901.08083#pg6>. The first one is based on standard block cipher encryption, which reduces by half the amount of the processing required to be done in addition to data encryption with regard to the fastest state-of-the-art solution<ref:1901.08083#pg3>. The second one fits both in the random oracle model or in the idealized blockcipher model with twice larger key than the security parameter, and completely eradicates additional processing<ref:1901.08083#pg3>.

The first scheme is denoted as SSAKE, which is a fast block-cipher based CSS protecting against key exposure<ref:1901.08083#pg6>. The SSAKE algorithm involves four steps: 1) Encryption of the plaintext into a ciphertext using a blockcipher in the CTR mode; 2) Transformation of the ciphertext using a linear transform creating dependencies between the blocks; 3) Splitting the transformed ciphertext into n fragments Fi composed of consecutive blocks; and 4) Applying a perfect secret sharing scheme to the initialization vector IV used during the encryption to produce n shares IV i, and attaching these shares to the fragments: an output share Si is then the concatenation of the transformed ciphertext fragments Fi and the IV’s share IV i<ref:1901.08083#pg6>.

The second scheme is denoted as ROSSake, which totally gets rid of the additional post-processing overhead by switching to a scheme based on less mainstream encryption with random oracles<ref:1901.08083#pg6>. The ROSSake scheme involves sampling a fixed secret key K at random, generating a one-timepad using Oc−1(KIV), splitting the padding P + Oc−1(KIV) into n disjoint fragments Fi, and concatenating each fragment Fi with a share IV i of IV under a (n, n − 1) secret sharing to obtain a complete share Si<ref:1901.08083#pg6>.

Security Analysis and Performance

The security analysis confirms that SSAKE satisfies n-SAKE security in the ideal blockcipher model with respect to the key parameter K used for the blockcipher encryption<ref:1901.08083#pg7>. The proof of Main Theorem 1, property (2), relies on a cascade of games where the permutation oracle checks again for collisions, introducing a negligible difference of views for the adversary compared to the previous game<ref:1901.08083#pg7>.

The performance evaluation shows that SSAKE is the fastest among schemes protecting encrypted data against key exposure based on mainstream symmetric encryption with AES, achieving an overhead of only 7% against a simple data encryption<ref:1901.08083#pg6>. ROSSake, implemented with the less conventional Keccak-based encryption, turns out to be the fastest of all SAKE schemes<ref:1901.08083#pg7>. Both SSAKE and ROSSake require an additional storage space of n or n − 1 additional blocks, which is a constant with regard to the size of the original data<ref:1901.08083#pg7>.

Conclusion

The work concludes by presenting SSAKE as a versatile computational secret sharing scheme that verifies both security properties (1) and (2) of this new model, and ROSSake as an alternative random-oracle based scheme that requires no processing overhead on top of encryption<ref:1901.08083#pg7>. The comparison demonstrates that SSAKE performs faster than the fastest known relevant scheme - Bastion - since the linear overhead is reduced by half, achieving the point (3) above<ref:1901.08083#pg6>. ROSSake is presented as the fastest of all SAKE schemes<ref:1901.08083#pg7>. The paper provides a detailed security analysis of not only the presented scheme but also of previous relevant work<ref:1901.08083#pg7>.

How it works

The SSAKE transformation is composed of four steps<ref:1901.08083#pg6>: 1) Encryption of the plaintext into a ciphertext using a blockcipher like AES in CTR mode; 2) Transformation of the ciphertext using a linear transform creating dependencies between the blocks; 3) Splitting the transformed ciphertext into n fragments Fi composed of consecutive blocks; and 4) Applying a perfect secret sharing scheme to the initialization vector IV used during the encryption to produce n shares IV i, and attaching these shares to the fragments: an output share Si is then the concatenation of the transformed ciphertext fragments Fi and the IV’s share IV i<ref:1901.08083#pg6>.

The ROSSake scheme involves sampling a fixed secret key K at random, generating a one-timepad using Oc−1(KIV), splitting the padding P + Oc−1(KIV) into n disjoint fragments Fi, and concatenating each fragment Fi with a share IV i of IV under a (n, n − 1) secret sharing to obtain a complete share Si<ref:1901.08083#pg6>.

The proof of Main Theorem 2 shows that the ind-CPA game (2) of the definition of n-SAKE with multiple queries on the same public key K consists exactly in the following one-query encryption game ”ind1” with the following encryption challenger oracle<ref:1901.08083#pg7>. The oracle selects a random oracle Oc−1(K∗) once for all and gives it to the adversary<ref:1901.08083#pg7>.

The proof of Proposition 2 demonstrates that Bastion satisfies (c − 2) CAKE security under a certain pseudorandomness hypothesis, which is defined by a specific output vector involving BC(C0 + s) and BC(C0 + t)<ref:1901.08083#pg7>.

The proof of Main Theorem 1, property (2), relies on the indistinguishability property derived from Proposition 1 in the ideal permutation model, which shows that the output of a specific procedure is indistinguishable from a generator of random strings<ref:1901.08083#pg7>. The core idea is that if an adversary has access to all shares and to the decryption key K, she can recover information about the plaintext by observing the structure of the transformed ciphertext<ref:1901.08083#pg7>.

The proof for Proposition 2 shows that an adversary in Game3 receives exactly DiffIV + P(b)1,..., P(b)c−1, which is assumed indistinguishable from a random uniform vector by Proposition 1<ref:1901.08083#pg7>. This allows the adversary to have negligible advantage in distinguishing what she receives from random<ref:1901.08083#pg7>.

The performance comparison indicates that SSAKE reduces by half the performance overhead in comparison to Bastion<ref:1901.08083#pg7>.

Improvements for AI systems

For distributed storage environments, implement key leakage resistant schemes that match all-or-nothing (AON) security level of secret sharing under key exposure by using a scheme based on standard block cipher encryption that reduces by half the amount of the processing required to be done in addition to data encryption with regard to the fastest state-of-the-art solution.
Develop an alternative scheme that completely eradicates additional processing by fitting into the random oracle model (e.g., Keccak) or an idealized blockcipher model with twice larger keys, achieving security levels such as an idealized AES256 would achieve 128 bits security.
Design a system utilizing the SSAKE scheme to provide n-SAKE security in a threat model where an adversary can compromise all but one of the storage sites, ensuring that the scheme satisfies both property (1) and property (2) of this new model.
Implement the ROSSake scheme for data protection, which is characterized by requiring only n XORs more in addition to data encryption compared to other methods, making it suitable for high-throughput distributed storage systems where n is no more than 20-30.
Leverage the performance evaluation results showing that ROSSake is the fastest of all SAKE schemes, specifically noting its speed when implemented with Keccak, which can be instantiated with parameters such as |IV | = |K| = c = 128.