CN-121997313-A - Low memory key generation for classical MCELIECE cryptographic systems

Abstract

A method of more efficiently utilizing limited computing resources in an embedded computing device is presented.

Inventors

• Arthur Folvarcini
• TOBIAS SCHNEIDER
• Olivier Brown Money

Assignees

• 恩智浦有限公司

Dates

Publication Date

20260508

Application Date

20251104

Priority Date

20241104

Claims (10)

1. 1. A computer-implemented method of generating a public key, wherein the public key comprises a matrix, wherein a number of rows and columns of the matrix are associated with security requirements, wherein the method is implemented by a processing resource, the method comprising: receiving a request for a public key; Generating a first key generation matrix in response to receiving the request; generating a second key generation matrix based on the first key generation matrix; Generating a portion of an inverse of the second key generation matrix, wherein the portion of the inverse of the second key generation matrix is not equal to a full inverse of the second key generation matrix; a portion of the public key is generated based on the portion of the second key generation matrix.
2. 2. The method of claim 1, wherein the inverse of the second key generation matrix is not stored entirely, wherein only the portion of the inverse of the second key generation matrix is stored.
3. 3. The method according to claim 1 or claim 2, wherein the generating of the portion of the inverse of the second key generation matrix is repeated until all of the portion of the second key generation matrix has been used to generate a corresponding portion of the public key.
4. 4. A method according to any of claims 1 to 3, wherein the portion of the inverse of the second key generation matrix is a row of the inverse of the second key generation matrix and the portion of the public key based on the portion of the second key generation matrix is a row of the public key.
5. 5. A method according to any of claims 1 to 3, wherein the portion of the inverse of the second key generation matrix is a plurality of rows of the inverse of the second key generation matrix and the portion of the public key based on the portion of the second key generation matrix is a plurality of rows of the public key.
6. 6. A method according to any preceding claim, wherein the first key generation matrix is generated temporarily without interrupting the method or is generated based on a random or pseudo-random seed.
7. 7. A method according to any preceding claim, wherein the portion of the public key is generated based on a product of the inverted portion of the second key generation matrix and the first key generation matrix.
8. 8. The method of any preceding claim, wherein the second key generation matrix is a square matrix equal to elements in a preceding mt row and a preceding mt column of the first key generation matrix.
9. 9. A system configured to implement the method of claims 1 to 12.
10. 10. A processing resource comprising a processor and a memory, the memory comprising executable instructions that, as a result of execution by the processor, cause the processor to perform the method of claims 1 to 8.

Description

Low memory key generation for classical MCELIECE cryptographic systems Technical Field The present invention relates to a method and system. In particular, but not exclusively, the invention relates to a computer implemented method for generating cryptographic keys. Background Classical McEliece cryptographic systems are code-based post quantum Key Encapsulation Mechanisms (KEMs). Such cryptographic systems are generally considered suitable for combating attacks from quantum computers. The requirements for devices with limited access to RAM that need to generate their own public or private keys are becoming increasingly higher. The computational requirements of key generation often conflict with limited access to RAM. Aspects and embodiments are contemplated in view of the foregoing. Disclosure of Invention Aspects relate to generating cryptographic keys. The cryptographic key may be generated according to McEliece cryptographic key generation methods. Aspects may be combined with a Key Encapsulation Mechanism (KEM). Viewed from a first aspect, a computer-implemented method of generating a public key may be provided. The public key may be generated according to the classical McEliece cryptographic system. The public key may comprise a matrix having a plurality of rows and columns. The number of rows and columns may be determined based on the security characteristics of the cryptographic system. The method may be implemented by a processing resource. The processing resource may be a secure computing resource, such as a trusted execution environment. The processing resources may be hosted within a computing device. The processing resources may be located within the embedded computing device. The method may include receiving a request for a public key. The request may be received from a host computing resource hosting the processing resource. The request may be in response to a request from a user. The method may generate a first key generation matrix in response to receiving the request. The generation of the elements of the first key generation matrix may be done 'temporarily', i.e. independently of the other elements in the matrix and without interrupting the rest of the method. The elements may be generated based on random or pseudo-random seeds. That is, a first key generation matrix may be generated in a first stage of a key generation process, and a second key generation matrix may be generated in a second stage. The method may generate a second key generation matrix based on the first key generation matrix, as elements of the first key generation matrix are used to generate the second key generation matrix. This may mean that elements of the first key generation matrix form part of the second generation matrix, or alternatively or optionally or additionally, the elements of the first key generation matrix are processed to generate the second key generation matrix. This may include setting the second key generation matrix equal to a portion of the first key generation matrix, where a portion may be understood not to mean the complete first key generation matrix. This may additionally or alternatively or optionally include setting a portion of the second key generation matrix equal to the first key generation matrix. The second key generation matrix may comprise, in part, an identity matrix. The method may include generating a portion of an inverse of the second key generation matrix, wherein the portion of the inverse of the second key generation matrix is not equal to a full inverse of the second key generation matrix. The portion of the inverse may comprise one or more rows or columns of the inverse of the second key generation matrix. The method may further comprise applying a procedure for making the second key generation matrix reversible in case the second key generation matrix is irreversible. The method may include generating a portion of the public key based on the inverted portion of the second key generation matrix and the first key generation matrix. The public key may depend on at least one of the one or more rows of the inverse of the second key generation matrix and/or the one or more rows of the first key generation matrix. The portion of the public key may include one or more rows of a matrix defining the public key. The method according to the first aspect enables the generation of keys using less memory resources on the processing resources. This enables keys to be generated on devices with lower memory resources (e.g., embedded computing devices with a small amount of RAM). Optionally, the inverse of the second key generation matrix is not stored, as a portion of the matrix that is less than the full matrix is stored (rather than the full matrix), and the full matrix is not stored. Optionally, the portion of the inverse of the second key generation matrix is stored in random access memory. Optionally, the generation of the portion of the inverse of the second key generation matrix ma