Fun with Linearity: How Encryption and Erasure Codes are Intimately Related

Erasure codes are a common means to achieve availability within storage systems. Encryption, on the other hand, is used to achieve security for that same data. Despite the widespread use of both methods together, it remains little known that both of these functions are linear transformations of the data. This relation allows for them to be combined in useful ways. Ways that are seemingly unknown and unused in practice. This presentation presents novel techniques built on this observation, including: rebuilding lost erasure code fragments without exposing any information, decrypting fragments produced from encrypted source data, and verifying consistency and integrity of erasure coded fragments without exposing any information about the fragments or the data.

Learning Objectives

What are linear functions?
Examples of linear functions
Combining encryption and erasure codes
Exploiting the linearity of erasure codes to securely rebuild
Using the linearity of CRCs to securely verify erasure coded data