Just use regular Reed-Solomon for the data and Shamir's Secret Sharing for the key (an implementation is for example http://point-at-infinity.org/ssss/ http://p

Just use regular Reed-Solomon for the data and Shamir's Secret Sharing for the key (an implementation is for example http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/). If you choose the same parameters for both algorithms, you can freely assign any key with any data shard and store those.