3
$\begingroup$

The idea is to share $n$ images among $n$ persons so that all images can be reconstructed by someone in possession of all shares.

However, there must not be any data overhead (which means the shares sent to the persons must not be bigger in size than the original images. In other terms: No data overhead).

The idea is to encode two images $A$ and $B$ like this:

$$Q = A + B + Secret\\ U = A - B + Secret$$

which allows for reconstruction of $B$ through

$$Q - U = A + B + Secret - A + B - Secret = 2B\\ B = (Q - U) / 2$$

after that $A$ can be reconstructed by

$$A = Q - B - Secret$$

$Secret$ is required because simply doing $A + B$ or $A - B$ visually leaks information about the images to the other persons. The trick is to calculate the secret through the image $B$. (For example by calculating a hash of B and then feed it to a PRNG and then use this PRNG to generate the secret numbers you add to each pixel (ask for a new number for every pixel)).

In Pseudo-Code:

seed = hash(B);
r = Random(seed);
for (x,y) to (WIDTH, HEIGHT):
  secret = r.nextInt(255);
  Q[x,y] = A[x,y] + B[x,y] + secret;
  U[x,y] = A[x,y] - B[x,y] + secret;

Arithmetic is $\mod(M)$ of course, where $M$ is a reasonable odd modulus for the required color depth etc. This method can be extended to more than two images. The odd modulus is what allows one to reconstruct the result uniquely.

The question now is: what fatal security flaws does this method have, if any?

$\endgroup$
  • $\begingroup$ How many secrets do you plan on having if you have $n$ images? (It should be more than one.) $\endgroup$ – Aleph Apr 25 '15 at 17:20
  • $\begingroup$ There is data overhead in your scheme. The integrals for q and u must be larger than a and b to handle rollover, and even then there are security issues. In other words, think about the information necessary for enabling division. $\endgroup$ – Thomas M. DuBuisson Apr 25 '15 at 19:10
  • $\begingroup$ crypto.stackexchange.com/q/17742/991 $\;$ $\endgroup$ – user991 Apr 25 '15 at 21:55
  • $\begingroup$ They don't need to be larger. (A + B + secret is mod M where M is an odd modulus). I've already implemented this scheme in code and tested it with various pictures (see mroman.ch/imgshare for an example) so I know it works (except that since M = 255 in my case you loose a tiny bit of colour depth but that's not really noticeable for simple photos). $\endgroup$ – mroman Apr 26 '15 at 12:27
  • $\begingroup$ > How many secrets do you plan on having if you have n images > (Itshould be more than one.) For n images I plan on having n shares. Essentially the constraint is to encode n images into n images in a way that all n images can be reconstructed by somebody in possession of all n shares. This is what I mean by "no data overhead". $\endgroup$ – mroman Apr 27 '15 at 8:51
1
$\begingroup$

A Flaw

If you try working through your example concretely then you should see at least one issue with decoding. Consider values mod $8$:

$ A = { 3 } \\ B = {7} \\ secret = {5 } $

Using your equations we have:

$ Q = 3 + 7 + 5 = 7 \\ U = 3 - 7 + 5 = 1 $

And for decoding:

$ B = (U - Q) / 2 \\ B = (1 - 7) / 2 \\ B = -6 / 2 ({\text mod} 8) $

But what is $\frac{-6}{2}$ modulo 8? How do we get a unique answer here?

Alternatives

Your constraints are a little unclear, but if you're OK with storing $(1 + {\text nrImages})*|{\text image}|$ (A, B, and secret) then use linear integer secret sharing in a traditional manner (below). Obviously this is a little silly seeing as you could use any symmetric encryption algorithm, given that you have a secret.

If you only want to store ${\text nrImages}|image|$ data, and not the secret, then that is harder as you'll have to derive the secret from the combined shares. For example we could have a small feistel network:

$ Q0 = A + PRF(B) \\ U = B + PRF(Q0) \\ Q = Q0 + PRF(U) $

Now $U$ and $Q$ are your secrets, protected ONLY by the entropy of A and B and the strength of your PRF. The entropy in the images could actually be increased without visually altering the typical image.

To decrypt:

$ Q0 = Q - PRF(U) \\ B = U - PRF(Q0) \\ A = Q0 - PRF(B) $

Basic application of LISS

For LISS just generate a random secret, $s$, and compute:

$ Q = A + B + S \\ U = B + S $

Then, once the shares and the secrets are collected, you can reverse the process via:

$ A = Q - U \\ B = U - S $

$\endgroup$
  • $\begingroup$ Modulus needs to be odd for it work. $\endgroup$ – mroman Apr 26 '15 at 12:23
  • $\begingroup$ @mroman For your scheme the modulus needs to be prime, not just odd. My point is that your scheme is under-defined. Beyond that you just have used a two-time pad (secret) in a non-traditional ring, so no one is going to suggest A or B can be recovered without both Q and U or some form of the value secret in their possession. I feel that the method I proposed would be better because it offers additional flexibility, avoids multiplicative inverses, and does not require retaining the secret (just the shares). $\endgroup$ – Thomas M. DuBuisson Apr 28 '15 at 22:09
  • $\begingroup$ Actually odd modulus is enough. The modulus must allow you to solve the equation '(B+B)/2' uniquely mod M which is possible if M is odd. (0, 0),(1, 2),(2, 4),(3, 6),(4, 8),(5, 10),(6, 12),(7, 14),(8, 1),(9, 3),(10, 5),(11, 7),(12, 9),(13, 11),(14, 13) for example are is using mod 15 and every (B+B) is unique. $\endgroup$ – mroman May 5 '15 at 9:17
  • $\begingroup$ Ah, point taken. You don't need arbitrary multiplicative inverses. $\endgroup$ – Thomas M. DuBuisson May 5 '15 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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