Ciphertext based quorum cryptosystem
Methods are described for constructing a secret key by multiple participants from multiple ciphertexts such that any quorum combination of participants can decrypt their respective ciphertexts and so generate a fixed number of key fragments that can be combined by a recipient to generate the secret key. Worked examples are described showing how the encryption keys for the ciphertexts may be key wrapped using a key encapsulation mechanism for which ciphers that are resistant to attack by a quantum computer may be used. In these cases, a post-quantum quorum system is realised. Methods are described by which the quorum key fragment ciphertexts may be updated so that the original key fragments become invalid without necessitating any change to the secret key.
1. A method of quorum-based information recovery, comprising:
receiving a plurality of ciphertexts, including 2k out of n key fragment ciphertexts, and at least one message ciphertext that is generated by encrypting information data using a session key whose value is equal to the value of a polynomial of predetermined degree, k−1 at a distinct point, and in which the value of the polynomial evaluated at each one of n other distinct points is encrypted to produce a respective key fragment ciphertext using an encryption key which has been encrypted into a ciphertext;
determining a reconstructed session key, wherein the step of determining the reconstructed session key comprises:
decrypting k of the key fragment ciphertexts using respective k private decryption keys to produce k decryption keys, and
using said k decryption keys to decrypt the k key ciphertexts which were not decrypted in the previous decryption step to produce k key fragments which are weighted and added together to reconstruct the session key; and
using said reconstructed session key to decrypt the message ciphertext.
2. The method according to claim 1 in which the reconstructed session key is checked for accuracy by using the reconstructed session key to reconstruct a key fragment which is compared to one of the key fragments obtained by decryption of a ciphertext.
3. The method according to claim 1 in which the ciphertexts are produced using symmetric key encryption.
4. The method according to claim 3 in which the symmetric key encryption is an authenticated symmetric key encryption method using a key derivation function which generates the initial vector and symmetric key.
5. The method according to claim 1 in which some of the ciphertexts are generated using public key encryption.
6. The method according to claim 3 in which an encryption or decryption key is encapsulated by an encryption system in a key encapsulation mechanism.
7. The method according to claim 1 in which some of the ciphertexts are generated using public key encryption which is resistant to attack by a quantum computer.
8. The method according to claim 1 in which the number of ciphertexts available to fragment holders is increased by forming a quorum by determining k key fragments from k ciphertexts and summing the key fragments after multiplying each one of these by a weighting factor which is a function of k polynomial evaluation points x i for i=1 to k and a new evaluation point x 0 to generate a new key fragment and then encrypting the new key fragment into a new key fragment ciphertext.
9. The method as in claim 8 in which the weighting factor used for generating the new key fragment is given by:
Π
i
=
1
k
-
1
(
x
0
-
x
i
)
Π
i
=
1
k
-
1
(
x
j
-
x
i
)
.
10. The method according to claim 1 in which as an intermediate step the session key used to produce a key fragment ciphertext is key wrapped using an administration encryption key.
11. The method according to claim 10 in which the key wrapped session key is rewrapped using a fragment holder's encryption key.
12. The method according to claim 10 in which the key wrapping is achieved by using a key encapsulation mechanism.
13. The method according to claim 1 in which the polynomial of degree k−1 initially has random coefficients and in which one or more coefficients are adjusted so that the value of the polynomial at the distinct point is equal to a given session encryption key.
14. The method according to claim 1 in which new quorum key fragments are produced without changing the session key by adding a new polynomial of degree k−1 which has a root at x 0 to the polynomial of predetermined degree used to generate the session key at the distinct point x 0 .
15. The method according to claim 14 in which the new quorum key fragments are produced without changing the session key by adding key fragment updates to the key fragments, the key fragment updates obtained by evaluating the polynomial of degree k−1 which has a root at x 0 at distinct points.
16. The method according to claim 14 in which the number of key fragments required to reconstruct the session key is increased to k′ without altering the session key by increasing the degree of the new polynomial which has a root at x 0 to degree k′−1.
17. The method according to claim 1 , wherein a new, ephemeral, session key is used for each instance of information data to be encrypted.
18. A system comprising a computer processor configured to carry out the steps of the method of claim 1 .
19. A non-transitory computer-readable medium comprising computer-executable instructions that, when executed, perform the method in accordance with claim 1 .