Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.


AONT: an essential gadget for Multi-Party Threshold Cryptography

September 28, 2023


Gilles Seghaier - Astran


Abstract. In this presentation, we will focus on a multi-cloud storage security use case. We present a multiparty threshold protocol that leverages multiple cloud service providers (CSPs). Our solution allows a client to store data by sending it to a proxy, which splits it before spreading the shares amongst a set of CSPs. We make use of a combination of primitives, including Secret Sharing Schemes (SSS), All-Or-Nothing Transform (AONT), and an additive Homomorphic Encryption (HE) scheme. This combination brings full confidentiality, integrity and availability without the need for long-term keys. At a high level, the client encrypts its data with an AONT and HE, before the proxy fragments it and spreads the shares over several CSPs using a Threshold SSS. An AONT is a keyless transformation, that makes it impossible to recover the original data unless the entirety of its output is known. To bring confidentiality w.r.t to the proxy, after passing its data through an AONT, the client homomorphically encrypts the first 256 bits of the output.

This HE encrypted part is homomorphically split by the proxy with a secure SSS (e.g. Shamir's), and the rest of the AONT is distributed with a memory-efficient threshold algorithm (e.g. Reed Solomon codes), as no information can leak from it. The AONT is the key to combine both the confidentiality of a secure SSS and the memory efficiency of Reed Solomon codes, even when one considers the proxy or any collusion of CSPs below the threshold might be adversaries. The keyless property of the AONT paired with homomorphic secret sharing removes the need for any long-term keys. Our solution enhances security compared to customers holding data on premise, and can be useful for compliance issues with holding data in the Cloud. Especially when appropriate technical measures are required, as in the California Consumer Privacy Act or the General Data Protection Regulation. This use case shows how AONT combined with other gadgets can be used as a building block for Multiparty Threshold Cryptography use case.

[Slides] [Video]

Presented at

MPTS 2023: NIST Workshop (virtual) on Multi-Party Threshold Schemes 2023

Event Details



Related Topics

Security and Privacy: cryptography

Created September 21, 2023, Updated November 02, 2023