Multi-party threshold authenticated encryption

1. A method for encrypting a message performed at an encrypting device, the method comprising:

generating a random nonce;

generating a commitment message based upon the message and the random nonce;

transmitting the commitment message to a plurality of cryptographic devices or a proxy device such that the plurality of cryptographic devices receive the commitment message, the plurality of cryptographic devices respectively storing a plurality of secret shares that are generated from a secret value;

receiving, from each of the plurality of cryptographic devices or the proxy device, a plurality of partial computations corresponding to a key generation seed, the partial computations being generated using the secret shares and the commitment message;

generating an additional partial computation corresponding to the key generation seed, the additional partial computation being generated using the commitment message and a secret share stored on the encrypting device;

generating the key generation seed based on the plurality of partial computations and the additional partial computation;

generating a cryptographic key comprising a random number by using the key generation seed as an input value to a random number generator;

encrypting, using the cryptographic key, the message and the random nonce to produce a ciphertext message; and

generating a ciphertext payload comprising the commitment message and the ciphertext message.

2. The method of claim 1 , wherein a number of cryptographic devices included in the plurality of cryptographic devices is equal to at least a predetermined threshold number of devices, and wherein the predetermined threshold number of devices is less than a total number of cryptographic devices in a network of cryptographic devices that store secret shares.

3. The method of claim 1 , wherein each of the plurality of partial computations received from the plurality of cryptographic devices are generated by encrypting the commitment message using a respective one of the plurality of secret shares as a symmetric encryption key or to derive the symmetric encryption key.

4. The method of claim 1 , further comprising:

receiving, from each of the plurality of cryptographic devices, a plurality of verification values indicating that the partial computations were computed correctly; and

verifying the verification values to confirm that the partial computations were computed correctly; and

when any verification value fails to verify, outputting an error message to indicate that encryption was unsuccessful.

5. The method of claim 1 , wherein the commitment message is a hash value generated by hashing the message and the random nonce using a hashing function.

6. The method of claim 1 , further comprising:

transmitting a device identifier to the plurality of cryptographic devices, the device identifier uniquely identifying the encrypting device, wherein the ciphertext payload further comprises the device identifier.

7. The method of claim 1 , wherein generating the key generation seed includes:

calculating a plurality of Lagrange coefficients corresponding to each of the plurality of partial computations;

generating a plurality of intermediate calculations by exponentiating the plurality of partial computations using a respective one of the plurality of Lagrange coefficients; and

generating the key generation seed as a product of each of the plurality of intermediate calculations.

8. The method of claim 1 , wherein the key generation seed is generated by calculating a binary exclusive-OR of the plurality of partial computations.

9. The method of claim 1 , wherein the plurality of partial computations are encrypted using a symmetric key, the method further comprising:

decrypting the plurality of partial computations.

10. A method for decrypting a ciphertext message performed at a decrypting device, the method comprising:

parsing a ciphertext payload to produce a first commitment message and the ciphertext message;

transmitting the first commitment message to a proxy device or a plurality of cryptographic devices, the plurality of cryptographic devices respectively storing a plurality of secret shares that are generated from a secret value;

receiving, from each of the plurality of cryptographic devices or the proxy device, a plurality of partial computations corresponding to a key generation seed, the partial computations being generated using the secret shares and the first commitment message;

generating the key generation seed based upon the plurality of partial computations;

generating a cryptographic key comprising a random number by using the key generation seed as an input value to a random number generator; and

decrypting, using the cryptographic key, the ciphertext message to produce a message and a random nonce, wherein the key generation seed is generated by calculating a plurality of Lagrange coefficients corresponding to each of the plurality of partial computations, generating a plurality of intermediate calculations by exponentiating the plurality of partial computations using a respective one of the plurality of Lagrange coefficients, and generating the key generation seed as a product of each of the plurality of intermediate calculations.

11. The method of claim 10 , wherein a number of cryptographic devices included in the plurality of cryptographic devices is equal to at least a predetermined threshold number of devices, and wherein the predetermined threshold number of devices is less than a total number of cryptographic devices in a network of cryptographic devices that store secret shares.

12. The method of claim 10 , wherein each of the plurality of partial computations received from the plurality of cryptographic devices are generated by encrypting the first commitment message using a respective one of the plurality of secret shares as a symmetric encryption key or to derive the symmetric encryption key.

13. The method of claim 10 , further comprising:

receiving, from each of the plurality of cryptographic devices, a plurality of verification values indicating that the partial computations were computed correctly;

verifying the verification values to confirm that the partial computations were computed correctly; and

when any verification value fails to verify, outputting an error message to indicate that decryption was unsuccessful.

14. The method of claim 10 , further comprising:

generating a second commitment message using the message and the random nonce;

comparing the first commitment message to the second commitment message; and

when the first commitment message and the second commitment message are not identical, outputting an error message to indicate that decryption was unsuccessful.

15. The method of claim 10 , further comprising:

parsing the ciphertext payload to produce a device identifier, the device identifier uniquely identifying an encrypting device; and

transmitting the device identifier to the plurality of cryptographic devices.

16. The method of claim 10 , further comprising:

generating an additional partial computation corresponding to the key generation seed, the additional partial computation being generated using the first commitment message and a secret share stored on the decrypting device, and wherein the key generation seed is generated based upon the plurality of partial computations and the additional partial computation.

17. The method of claim 1 , further comprising:

receiving, from a new cryptographic device, an identification value corresponding to the new cryptographic device;

selecting a subsequent plurality of other cryptographic devices from a network of cryptographic devices;

transmitting the identification value to each cryptographic device of the subsequent plurality of other cryptographic devices;

receiving, from each cryptographic device of the subsequent plurality of other cryptographic devices, a plurality of subsequent partial computation corresponding to a new secret share;

generating, the new secret share using the plurality of subsequent partial computations; and

transmitting the new secret share to the new cryptographic device.

18. An encrypting device comprising:

one or more processors; and

a computer readable medium storing a plurality of instructions that, when executed, control the one or more processors to perform a method for encrypting a message, the method comprising:

generating a random nonce;

generating a commitment message based upon the message and the random nonce;

transmitting the commitment message to a plurality of cryptographic devices or a proxy device such that the plurality of cryptographic devices receive the commitment message, the plurality of cryptographic devices respectively storing a plurality of secret shares that are generated from a secret value;

receiving, from each of the plurality of cryptographic devices or the proxy device, a plurality of partial computations corresponding to a key generation seed, the partial computations being generated using the secret shares and the commitment message;

generating the key generation seed based on the plurality of partial computations;

generating a cryptographic key comprising a random number by using the key generation seed as an input value to a random number generator;

encrypting, using the cryptographic key, the message and the random nonce to produce a ciphertext message; and

generating a ciphertext payload comprising the commitment message and the ciphertext message, wherein generating the key generation seed includes:

calculating a plurality of Lagrange coefficients corresponding to each of the plurality of partial computations;

generating a plurality of intermediate calculations by exponentiating the plurality of partial computations using a respective one of the plurality of Lagrange coefficients; and

generating the key generation seed as a product of each of the plurality of intermediate calculations.

19. The encrypting device of claim 18 , wherein a number of cryptographic devices included in the plurality of cryptographic devices is equal to at least a predetermined threshold number of devices, and wherein the predetermined threshold number of devices is less than a total number of cryptographic devices in a network of cryptographic devices that store secret shares.

20. The encrypting device of claim 18 , wherein each of the plurality of partial computations received from the plurality of cryptographic devices are generated by encrypting the commitment message using a respective one of the plurality of secret shares as a symmetric encryption key or to derive the symmetric encryption key.

21. The encrypting device of claim 18 , wherein the method further comprises:

receiving, from each of the plurality of cryptographic devices, a plurality of verification values indicating that the partial computations were computed correctly; and

verifying the verification values to confirm that the partial computations were computed correctly; and

when any verification value fails to verify, outputting an error message to indicate that encryption was unsuccessful.

22. A decrypting device comprising:

one or more processors; and

a computer readable medium storing a plurality of instructions that, when executed, control the one or more processors to perform a method for decrypting a ciphertext message, the method comprising:

parsing a ciphertext payload to produce a first commitment message and the ciphertext message;

transmitting the first commitment message to a proxy device or a plurality of cryptographic devices, the plurality of cryptographic devices respectively storing a plurality of secret shares that are generated from a secret value;

receiving, from each of the plurality of cryptographic devices or the proxy device, a plurality of partial computations corresponding to a key generation seed, the partial computations being generated using the secret shares and the first commitment message;

generating an additional partial computation corresponding to the key generation seed, the additional partial computation being generated using the first commitment message and a secret share stored on the decrypting device;

generating the key generation seed based upon the plurality of partial computations and the additional partial computation;

generating a cryptographic key comprising a random number by using the key generation seed as an input value to a random number generator; and

decrypting, using the cryptographic key, the ciphertext message to produce a message and a random nonce.

23. The decrypting device of claim 22 , wherein each of the plurality of partial computations received from the plurality of cryptographic devices are generated by encrypting the first commitment message using a respective one of the plurality of secret shares as a symmetric encryption key or to derive the symmetric encryption key.

24. The decrypting device of claim 22 , wherein the method further comprises:

generating a second commitment message using the message and the random nonce;

comparing the first commitment message to the second commitment message; and

when the first commitment message and the second commitment message are not identical, outputting an error message to indicate that decryption was unsuccessful.

25. The decrypting device of claim 22 , wherein the method further comprises:

receiving, from a new cryptographic device, an identification value corresponding to the new cryptographic device;

selecting a subsequent plurality of other cryptographic devices from a network of cryptographic devices;

transmitting the identification value to each cryptographic device of the subsequent plurality of other cryptographic devices;

receiving, from each cryptographic device of the subsequent plurality of other cryptographic devices, a plurality of subsequent partial computation corresponding to a new secret share;

generating, the new secret share using the plurality of subsequent partial computations; and

transmitting the new secret share to the new cryptographic device.