The data-dispersal package

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain]

Warnings:

Given a ByteString of length D, we encode the ByteString as a list of n Fragments, each containing a ByteString of length O(D/m). Then, each fragment could be stored on a separate machine to obtain fault-tolerance: Even if all but m of these machines crash, we can still reconstruct the original ByteString out of the remaining m fragments. Note that the total space requirement of the m fragments is m * O(D/m)=O(D), which is clearly space-optimal. The total space required for the n fragments is O((n/m)*D). Note that m and n can be chosen to be of the same order, so the asymptotic storage overhead for getting good fault-tolerance increases only by a constant factor.

GHCi Example:

> :m + Data.IDA
> let msg = Data.ByteString.Char8.pack "my really important data"
> let fragments = encode 5 15 msg
-- Now we could distributed the fragments on different sites to add some
-- fault-tolerance.
> let frags' = drop 5 $ take 10 fragments -- let's pretend that 10 machines crashed
-- Let's look at the 5 fragments that we have left:
> mapM_ (Prelude.putStrLn . show)  frags'
(6,[273,771,899,737,285])
(7,[289,939,612,285,936])
(8,[424,781,1001,322,788])
(9,[143,657,790,157,423])
(10,[314,674,418,888,423])
-- Space-efficiency: Note that the length of each of the 5 fragments is 5
-- and our original message has length 24.
> decode frags'
"my really important data"

Encrypted Fragments:

The module Data.IDA contains an information dispersal algorithm that produces space-optimal fragments. However, the knowledge of 1 or more fragments might allow an adversary to deduce some information about the original data. The module Crypto.IDA combines information dispersal with secret sharing: the knowledge of up to m-1 fragments does not leak any information about the original data.

This could be useful in scenarios where we need to store data at untrusted storage sites: To this end, we store one encrypted fragment at each site. If at most m-1 of these untrusted sites collude, they will still be unable to obtain any information about the original data. The added security comes at the price of a slightly increased fragment size (by an additional constant 32 bytes) and an additional overhead in the running time of the encoding/decoding process. The algorithm is fully described in module Crypto.IDA.

Fault-Tolerance:

Suppose that we have N machines and encode our data as 2log(N) fragments with reconstruction threshold m = log(N). Let's assume that we store each fragment on a separate machine and each machine fails (independently) with probability at most 0.5.

This library is based on the following works:

Properties

Versions1.0.0.0, 1.0.0.1, 1.0.0.1, 1.0.0.2
Change logNone available
DependenciesAES (>=0.2.9), array (>=0.4.0.1), base (==4.6.*), binary (>=0.7.2.1), bytestring (>=0.10.0.2), entropy (>=0.3.2), finite-field (>=0.8.0), matrix (>=0.3.4.0), secret-sharing (>=1.0.0.0), syb (>=0.4.0), vector (>=0.10.11.0) [details]
LicenseLGPL-2.1
CopyrightPeter Robinson 2014
AuthorPeter Robinson <peter.robinson@monoid.at>
Maintainerpeter.robinson@monoid.at
CategoryData, Cryptography
Home pagehttp://monoid.at/code
UploadedSat Sep 20 17:55:41 UTC 2014 by PeterRobinson

Modules

Downloads

Maintainers' corner

For package maintainers and hackage trustees