US-12627489-B2 - Post-quantum constant-time key rotation verification

US12627489B2US 12627489 B2US12627489 B2US 12627489B2US-12627489-B2

Abstract

Certain aspects of the disclosure provide a method for verifiable key rotation of an encryption key. The method includes generating a ciphertext by encrypting a plaintext with a homomorphic probabilistic encryption scheme based on a first key. The method further includes generating an updating token based on a difference between the homomorphic probabilistic encryption scheme based on a second key and generating a second ciphertext by encrypting the first ciphertext with the updating token. The method further includes validating the key rotation by selecting a set of second ciphertext blocks from the second ciphertext; reverting the set of second ciphertext blocks with the updating token to a set of third ciphertext blocks; and computing a Hamming distance between blocks of the set of second ciphertext blocks and the corresponding set of third ciphertext blocks.

Inventors

Vipin Singh SEHRAWAT

Assignees

CIRCLE INTERNET GROUP, INC.

Dates

Publication Date: 20260512
Application Date: 20230822

Claims (14)

1 . A method for key rotation of an encryption key, comprising: generating a first ciphertext by encrypting a plaintext with a homomorphic probabilistic encryption scheme based on a first key; generating an updating token based on a difference between the homomorphic probabilistic encryption scheme based on the first key and a homomorphic probabilistic encryption scheme based on a second key; generating a second ciphertext by encrypting the first ciphertext with the updating token; selecting a set of second ciphertext blocks from the second ciphertext; reverting the set of second ciphertext blocks with the updating token to a set of third ciphertext blocks; and computing a Hamming distance between blocks of the set of second ciphertext blocks and corresponding blocks of the set of third ciphertext blocks.
2 . The method of claim 1 , further comprising: in response to determining the Hamming distance is less than a threshold, validating the second ciphertext; and replacing the first key with the second key as the encryption key for the plaintext.
3 . The method of claim 1 , further comprising: in response to determining the Hamming distance is greater than a threshold, rejecting the second ciphertext; and retaining the first key as the encryption key for the plaintext.
4 . The method of claim 3 , further comprising: generating a second updating token based on a difference between the homomorphic probabilistic encryption scheme based on the first key and the homomorphic probabilistic encryption scheme based on a fourth key; and generating a fourth ciphertext by encrypting the first ciphertext with the second updating token.
5 . The method of claim 1 , wherein the set of third ciphertext blocks corresponds to a set of blocks selected from the first ciphertext.
6 . The method of claim 1 , wherein the homomorphic probabilistic encryption scheme is derived from a key-homomorphic pseudorandom function family.
7 . The method of claim 1 , wherein the homomorphic probabilistic encryption scheme is derived from a bi-homomorphic pseudorandom function family.
8 . A method for verifiable key rotation of an encryption key, comprising: generating a first ciphertext by encrypting a plaintext with a homomorphic probabilistic encryption scheme based on a first key, wherein the first key is the encryption key; generating an updating token based on a difference between the homomorphic probabilistic encryption scheme based on the first key and a homomorphic probabilistic encryption scheme based on a second key; generating a second ciphertext by encrypting the first ciphertext with the updating token; selecting a set of second ciphertext blocks from the second ciphertext; reverting the set of second ciphertext blocks with the updating token to a set of third ciphertext blocks; computing a Hamming distance between blocks of the set of second ciphertext blocks and corresponding blocks of the set of third ciphertext blocks; in response to determining the Hamming distance is less than a threshold, validating the second ciphertext; and replacing the first key with the second key as the encryption key for the plaintext.
9 . The method of claim 8 , wherein the set of third ciphertext blocks corresponds to a set of blocks selected from the first ciphertext.
10 . The method of claim 8 , wherein the homomorphic probabilistic encryption scheme is derived from a key-homomorphic pseudorandom function family.
11 . The method of claim 8 , wherein the homomorphic probabilistic encryption scheme is derived from a bi-homomorphic pseudorandom function family.
12 . A processing system, comprising: a memory comprising computer-executable instructions; and a processor configured to execute the computer-executable instructions and cause the processing system to: generate a first ciphertext by encrypting a plaintext with a homomorphic probabilistic encryption scheme based on a first key; generate an updating token based on a difference between the homomorphic probabilistic encryption scheme based on the first key and a homomorphic probabilistic encryption scheme based on a second key; and generate a second ciphertext by encrypting the first ciphertext with the updating token; select a set of second ciphertext blocks from the second ciphertext; revert the set of second ciphertext blocks with the updating token to a set of third ciphertext blocks; and compute a Hamming distance between blocks of the set of second ciphertext blocks and corresponding blocks of the set of third ciphertext blocks.
13 . The processing system of claim 12 , wherein the processor is further configured to: in response to determining the Hamming distance is less than a threshold, validate the second ciphertext; and replace the first key with the second key as an encryption key for the plaintext.
14 . The processing system of claim 12 , wherein the processor is further configured to: in response to determining the Hamming distance is greater than a threshold, reject the second ciphertext; and retain the first key as an encryption key for the plaintext.

Description

BACKGROUND Field Aspects of the present disclosure relate to verifiable key rotation of an encryption key. Description of Related Art An encryption key is used to encrypt and/or decrypt data. Encryption keys may be generated with an algorithm to ensure it is unique, unpredictable, and properly encrypts/decrypts the data. In symmetric encryption, the same encryption key is used to encrypt and decrypt data (e.g., plaintext). A sender of encrypted data (e.g., ciphertext) must share the symmetrical key with the receiver to allow the receiver to decrypt the ciphertext, revealing the plaintext. If the symmetrical key is compromised, then the ciphertext is also compromised because anyone with the symmetrical key may decrypt the ciphertext with the key, revealing the plaintext. Additionally, the key may be used to encrypt other plaintext, rendering the ciphertext untrustworthy. In asymmetric encryption, two different, albeit related, encryption keys are used. A public key is distributed and a private key is kept secret. A sender encrypts the data with a public key and the receiver uses the corresponding secret private key to decrypt the encrypted data. The ciphertext remains secret even with a distributed public key because the encryption function is one-way such that only the receiver with the private key can decrypt the ciphertext. However, if the private key is compromised, the ciphertext may be decrypted and the plaintext revealed. Further, a private key may be used to sign verifiable messages. However, if the key is compromised, any signature is also compromised. Generally, it is best practice to periodically update an encryption key, regardless of whether it is used for symmetric or asymmetric encryption, through key rotation whereby the current encryption key is replaced with a new encryption key. Key rotation prevents compromise of data, such as through key exhaustion. An encryption key is exhausted and thus exposed when it is used more times than it should be used because overuse of an encryption key can result in revealing information about the underlying plaintext or the secret values in the encryption key itself. Furthermore, key rotation can be used to revoke old encryption keys, for example, that might have been compromised or to revoke data access, because once an encryption key has been replaced by a new encryption key, the older encryption key cannot access the data. Accordingly, there is a need in the art for methods of key rotation for encryption key materials. SUMMARY Certain aspects provide a method for key rotation of an encryption key, comprising: generating a first ciphertext by encrypting a plaintext with a homomorphic probabilistic encryption scheme based on a first key; generating an updating token based on a difference between the homomorphic probabilistic encryption scheme based on the first key and the homomorphic probabilistic encryption scheme based on a second key; and generating a second ciphertext by encrypting the first ciphertext with the updating token. Other aspects provide processing systems configured to perform the aforementioned methods as well as those described herein; non-transitory, computer-readable media comprising instructions that, when executed by a processor of a processing system, cause the processing system to perform the aforementioned methods as well as those described herein; a computer program product embodied on a computer-readable storage medium comprising code for performing the aforementioned methods as well as those further described herein; and a processing system comprising means for performing the aforementioned methods as well as those further described herein. The following description and the related drawings set forth in detail certain illustrative features of one or more aspects. DESCRIPTION OF THE DRAWINGS The appended figures depict certain aspects and are therefore not to be considered limiting of the scope of this disclosure. FIG. 1 depicts an example process flow for performing key rotation. FIG. 2 depicts an example data flow for performing key rotation. FIG. 3 depicts an example data flow for validating a key rotation. FIG. 4 depicts an example proof of validation of a key rotation. FIG. 5 depicts an example method for performing key rotation. FIG. 6 depicts an example processing system for performing various aspects described herein. To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the drawings. It is contemplated that elements and features of one embodiment may be beneficially incorporated in other embodiments without further recitation. DETAILED DESCRIPTION Aspects of the present disclosure provide apparatuses, methods, processing systems, and computer-readable mediums for performing computationally efficient, secure, and verifiable key rotation of an encryption key. As described above, key rotation is the process of periodically exchanging the