All-or-nothing transform

Add links
Source: Wikipedia, the free encyclopedia.

In

encryption mode which allows the data to be understood only if all of it is known. AONTs are not encryption, but frequently make use of symmetric ciphers and may be applied before encryption. In exact terms, "an AONT is an unkeyed, invertible, randomized transformation, with the property that it is hard to invert unless all of the output is known."[1]

Algorithms

The original AONT, the package transform, was described by

XORing
each plaintext block with that block's index encrypted by a randomly chosen key, then appending one extra block computed by XORing that random key and the hashes of all the preprocessed blocks. The result of this preprocessing is called the pseudomessage, and it serves as the input to the encryption algorithm. Undoing the package transform requires hashing every block of the pseudomessage except the last, XORing all the hashes with the last block to recover the random key, and then using the random key to convert each preprocessed block back into its original plaintext block. In this way, it's impossible to recover the original plaintext without first having access to every single block of the pseudomessage.

Although Rivest's paper only gave a detailed description of the package transform as it applies to

ECB
transform, package CBC transform, etc.

In 1999 Victor Boyko proposed another AONT, provably secure under the

random oracle model.[1]

Apparently at about the same time, D. R. Stinson proposed a different implementation of AONT, without any cryptographic assumptions.[3] This implementation is a linear transform, perhaps highlighting some security weakness of the original definition.

Applications

AONTs can be used to increase the strength of encryption without increasing the key size. This may be useful to, for example, secure secrets while complying with government cryptography export regulations. AONTs help prevent several attacks.

One of the ways AONTs improve the strength of encryption is by preventing attacks which reveal only part of the information from revealing anything, as the partial information is not enough to recover any of the original message.

Another application, suggested in the original papers is to reduce the cost of security: for example, a file can be processed by AONT, and then only a small portion of it can be encrypted (e.g., on a smart-card). AONT will assure that as a result the whole file is protected. It is important to use the stronger version of the transform (such as the one by Boyko above).

AONT may be combined with

forward error correction to yield a computationally secure secret sharing scheme.[4]

Other uses of AONT can be found in optimal asymmetric encryption padding (OAEP).

References

  1. ^
    ISBN 978-3-540-66347-8
    .
  2. ISBN 978-3-540-63247-4
    .
  3. S2CID 10118200
    .
  4. ^ Resch, Jason; Plank, James (February 15, 2011). AONT-RS: Blending Security and Performance in Dispersed Storage Systems (PDF). Usenix FAST'11.
  • Staple, an open-source prototype All-or-nothing transform implementation.
Retrieved from "https://en.wikipedia.org/w/index.php?title=All-or-nothing_transform&oldid=1173786158"