2
$\begingroup$

I was just wondering, is there a type of deterministic number generator that allows me to share some (not all) numbers I've generated using a smallish seed?

I have pairs of random numbers and need to make one number from each pair public. The point of sharing with a type of seed is, that my application needs to do hundreds and thousands of these and any space saving will result in massively decreased storage and transmission costs. Which one of the pair I want to make public is not known during key generation.

A really basic insecure example would be to use sha256(seed + n) where n starts at 0 and increases for each number. You would share the seed plus all the n values you want to share. Obviously this means people could generate the numbers I don't want them to by filling in the missing n values.

I'm not sure if such a thing exists, but I figured the folks at Crypto.SE would know if it did, or be able to invent it. Oh, and half of the pairs of numbers is about 2048 bytes, so any solution would have to be smaller than that to be worth it.

|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by "Which one of the pair I want to make public is not known during key generation."? Do you need to reveal one item from each pair one-at-a-time, or need to reveal a set of N/2 random numbers all at once? Have the numbers already been allocated a purpose or used making it impossible to simply have two interleaved sequences? $\endgroup$ – Neil Slater Jun 22 '14 at 7:49
  • $\begingroup$ @NeilSlater, I need to reveal N/2 numbers all at once. I'm not sure what you mean by interleaved sequences (the Wiki article is confusing). The only requirement is that they come out intact and in order at the other end. $\endgroup$ – Bardi Harborow Jun 22 '14 at 8:04
  • $\begingroup$ I mean just have two sequences $S_0$ and $S_1$, and use them alternating $( S_0^{(0)}, S_1^{(0)}, S_0^{(1)}, S_1^{(1)}, S_0^{(2)}, S_1^{(2)} ... )$ Then you can reveal all of $S_0$ using a single key. But that may not work for your purpose, it is not clear. A simpler way of putting it, is would your system work if you revealed values for either all odd or all even n? $\endgroup$ – Neil Slater Jun 22 '14 at 8:23
  • $\begingroup$ @NeilSlater, the purpose of my idea is to vastly compress the 2048 bytes. I'm not completely getting the mathematical syntax, but your idea just seems to be num1 + num2 + ...? $\endgroup$ – Bardi Harborow Jun 22 '14 at 8:26
  • $\begingroup$ I think I understand that, but I am still focusing on "need to make one number from each pair public" : Which one of the pair, does it make a difference to you, and can it always be the same one of the pair? This has an impact, because one simple option is to pair up numbers from two sequences and publish the seed for one of them. $\endgroup$ – Neil Slater Jun 22 '14 at 8:31
1
$\begingroup$

A really basic insecure example would be to use sha256(seed + n) where n starts at 0 and increases for each number. You would share the seed plus all the n values you want to share. Obviously this means people could generate the numbers I don't want them to by filling in the missing n values.

  1. You could extend that idea and use $\operatorname{sha256}(seed || n || r_i)$, where $r_i$ are smaller random numbers. By using 32-bit seeds to produce 256-bit random numbers, you would save almost 90% of the transmission and storage costs.

    However, anyone could tell an unrevealed number was one of the $2^{32}$ that could be created with that seed and n.

  2. If that's not acceptable, you could build hash trees, where you start from one seed and at each level derive two seeds from one, eventually ending in the random numbers desired. (There would be one hash tree for "left" and one for "right" values in the pairs.)

    Then you could reveal any seeds for which the whole subtree should be revealed. On average this could save almost a third of the data.

  3. As a special case of the above, if you just used a new seed every other left/right value (i.e. left of the first two pairs would be derived from a single seed), you could save exactly 25% of the data on average with simpler logic than a whole hash tree requires.

|improve this answer
$\endgroup$

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.