1
$\begingroup$

I am trying to design an algorithm. For now, I am trying to give myself a large overview.

Assume I have K (for example, K can equal 8) perfect slave machines, and one master machine. Each slave has a perfect HDD. I want to save the string "ABCDEFGHIJKLMNOP". My wished are

  1. I want to only save a fragment of the string to each HDD belonging to an unique slave
  2. I want to make sure, that an adversary can only recover the full string, if and only if he can access at least P fraction of the slaves (for example, P can be 50%).
  3. However, an authorized user can recover the complete string, even if a few slaves are offline, or not accessible. Let's call the number of offline slaves n, let's also assume that n < PK. For example, in this case n can be 2, which is less than 50% of 8 total slaves.

Note that I am differentiating between compromised and accessible. A prefect adversary compromises a slave without rendering it accessible. However, a slave can become inaccessible with or without the involvement of an adversary.

How should I go about designing an algorithm that can do it?

My attempt to solution was to experiment with Reed Solomon Encoding - but I can't find a way that would allow both the fault tolerance, and significant difficulty for an attacker.

As an answer, I would like a detailed pseudocode with explanation with step by step explanation. In this question, I have not set any limit on K or p because I don't know if that is necessary or not. However, if a fully general answer isn't possible, then may be you can set suitable limits on these, to develop a special solution.

Thank you.

$\endgroup$

1 Answer 1

1
$\begingroup$

Use secret sharing. With a $k$-out-of-$n$ secret sharing scheme, the string is distributed among $n$ "slaves". Access to any $k$ "slaves" is enough to recover the string; but with access to $k-1$ or fewer "slaves", an adversary cannot learn anything about the string.

There are many standard secret sharing schemes in the literature. For instance, you can use Shamir secret sharing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.