Deterministic key generation

In a situation where it is required to generate n number of keys deterministically from a single piece of seed information can we assume that b breached number of keys, no matter what the quantity would not help an attacker discover the previous nor next key in the set without the original seed data?

My initial thought is that it wont be possible due to the generation of one provably secure key to another provably secure key wouldn't given an attacker leverage leverage. If someone can confirm my thoughts though (or how wrong I am) that would be brilliant. Thanks.

-
What key derivation algorithm are you using? – Paŭlo Ebermann Dec 7 '12 at 21:55
This is not implemented yet. So one which would not cause such a weakness to become apparent, if there are some which do. – MaxSan Dec 8 '12 at 19:32
This may be relevant: crypto.stackexchange.com/questions/5355/… – Thomas Dec 9 '12 at 2:07

What you want is a key derivation function (KDF). Here's a fairly thorough list of some standardized ones.

Ps. The suggestion given by user1852723 to use HMAC, with your "seed" as the key and a counter (or other non-repeating sequence) as the input, more or less corresponds to the "Counter mode KDF" construction described in NIST SP 800-108, with HMAC as the underlying PRF.

-

can we assume that b breached number of keys, no matter what the quantity would not help an attacker discover the previous nor next key in the set without the original seed data?

No, you cannot assume it. Whether that holds depends upon what key generation algorithm you use. For good key derivation algorithms it will be true; but if you choose an insecure key derivation algorithms, it won't. Any time you have a special requirement, you can never "assume" the requirement holds; instead, you need to choose a solution that meets the requirement.

Instead of asking whether you can assume it, you should be asking what key derivation function is suitable, given this requirement. Any good key derivation function should be suitable. For instance, PBKDF2 should be a reasonable choice.

-

The answer depends on what you mean by "provably secure". In a information theoretic setting (especially with unbounded computing power) this is probably impossible. For pratical applications you could for example use your seed as a key for HMAC where you sign elements of a fixed non repeating sequence.

-