Is it possible to have an encryption scheme that could be encrypted with a particular key, then decrypted with a large amount of keys without massively inflating the size of the final result?

I am looking for an encryption scheme that would allow me to encrypt a block of data, then be able to decrypt it with a highly specific set of variables. As an example, take two integers, where the first one must be in a particular range (say, within 1000-3000) while the second one is an 8 bit int and must have its 4th and 6th byte set to 1 (i.e. 00101000-00101111, 00111000-00111111). Both integers must fall within these predefined ranges, which themselves may not be public information, to produce a key that will be able to decrypt the data.

I have researched single encryption key - multiple decryption key schemes before posting this question. I have learned that GPG accomplishes this by encrypting the actual key with every single private key, then inserting this information into the header. This is unviable for my intended use case, as it would require me to include every single permutation of the variables that are supposed to make up the keys and thus does not scale (if my math is correct, the conditions above alone would result in over 30 thousand copies of the key encrypted with each permutation).

Another approach I've investigated is the Shamir's Secret Sharing algorithm. It would allow me to encrypt a symmetric key (for, say, AES-256) and receive from it a number of shares that I could then split between the different variables (k=2 in the example case above). I could then map valid shares (n>=2) to entries that match the desired ranges/conditions and reconstruct the same key with a variety of combinations. This does mean that I am no longer limited by permutations. While I would still have to store every single share (plus junk random data) in a binary blob to access based on these values, I would be able to store variable 1 and variable 2 in the example above as separate blobs, thus adding the number of values for each instead of multiplying them. I'm however unsure of the cryptographic implications of mapping SSS shares in this fashion.

I'm unsure if what I'm asking for is simply impossible, if I am missing something very obvious or if the above long-winded method of using Shamir's Secret Sharing is the best I can get.

  • $\begingroup$ "Both integers must fall within these predefined ranges, which themselves may not be public information, to produce a key that will be able to decrypt the data."; does that mean that someone looking at the ciphertext cannot deduce who can decrypt it? If you don't mind that, I can see how it could be done using $O(\log n)$ keys/ciphertext expansion... $\endgroup$ – poncho Aug 11 '20 at 18:51
  • $\begingroup$ @poncho It should not be possible to narrow down the range of that fragment any further than the size of the integer, although it is obviously fine if the size of the total key block (i.e. all of the variables that make up the key) as well as how it's divided is easily discoverable. $\endgroup$ – Zatherz Aug 12 '20 at 15:33

Your Answer

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

Browse other questions tagged or ask your own question.