EP-4738760-A1 - LOW MEMORY KEY GENERATION FOR CLASSIC MCELIECE CRYPTOSYSTEM

Abstract

A method is proposed to make more efficient use of limited computing resources in embedded computing devices.

Inventors

• FOLWARCZNY, Artur
• SCHNEIDER, TOBIAS
• BRONCHAIN, OLIVIER

Assignees

• NXP B.V.

Dates

Publication Date

20260506

Application Date

20241104

Claims (15)

1. A computer-implemented method of generating a public key, wherein the public key comprises a matrix wherein the number of rows and columns of the matrix are associated with a security requirement, wherein the method is implemented by a processing resource, the method comprising: receiving a request for a public key; responsive to receiving the request, generating a first key generation matrix; generating a second key generation matrix based on the first key generation matrix; generating part of an inverse of the second key generation matrix, wherein part of the inverse of the second key generation matrix is not equal to the full inverse of the second key generation matrix; generating a part of the public key based on the part of the second key generation matrix.
2. A method according to Claim 2, wherein the inverse of the second key generation matrix is not stored in full, wherein only the part of the inverse of the second key generation matrix is stored.
3. A method according to Claim 1 or Claim 2, wherein the generation of the part of the inverse of the second key generation matrix is repeated until all of the parts of the second key generation matrix have been used to generate a corresponding part of the public key.
4. A method according to any one of Claims 1 to 3, wherein the part of the inverse of the second key generation matrix is a row of the inverse of the second key generation matrix and the part of the public key based on the part of the second key generation matrix is a row of the public key.
5. A method according to any one of Claims 1 to 3 wherein the part 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 part of the public key based on the part of the second key generation matrix is a plurality of rows of the public key.
6. A method according to any preceding claim, wherein the first key generation matrix is generated ad hoc, without interrupting the method.
7. A method according to any preceding claim, wherein the first key generation matrix is generated based on a random or pseudo-random seed.
8. A method according to any preceding claim, wherein the part of the public key is generated based on a product of a part of the inverse of the second key generation matrix and the first key generation matrix.
9. A method according to any preceding claim, wherein the processing resource is an embedded computing device.
10. A method according to Claim 9, wherein the request for the public key is received from any computing device which can communicate, directly or indirect connection with the embedded computing device..
11. A method according to any preceding claim, wherein the second key generation matrix is a square matrix equal to the elements in the first mt rows and first mt columns of the first key generation matrix.
12. A method according to any preceding claim, wherein generating part of an inverse of the second key generation matrix comprises (wherein all elements of S and Tare in and wherein all elements of D are integers) one or more of the following steps: a) Initialising a permutation vector D of mt elements to the integers 0, 1, 2 ... mt-1 b) Initialising the matrix T ∈ F 2 mt × mt to the identity matrix; c) Loop 1: iteratively, for c=0 up to mt-1 : d) Generating the elements c to mt-1 of column c of the second key generation matrix S ∈ F 2 mt × mt and storing them as elements c to mt-1 of the vector S c ∈ F 2 mt e) Setting the elements 0 to c -1 of the vector S c to 0; f) Applying the permutation stored in D to the elements of S c g) Multiplying TS c = S c ′ . h) If element c of S' c ≠ 1 i) Finding the next element j in S' c which is 1 j) Swapping element c and element j of S' c k) Swapping element c and element j of D l) Swapping row c and row j of T m) Swapping column c and column j of T End if n) Loop 2: For d = c+1 up to mt-1 o) If element d of S' c == 1 p) Computing the bitwise XOR of row d of T and row c of T and storing the result in row d of T End if End loop 2 q) Discarding row c of T End loop 1 r) Inverting the permutation vector D as D -1 s) Applying the inverted permutation D -1 to columns of T
13. A non-transitory computer readable storage medium having stored thereon executable instructions that, as a result of being executed by a processor of a computer system, cause the computer system to at least perform the method of any one of claims 1 to 12.
14. A system configured to implement the method of Claims 1 to 12.
15. A processing resource comprising a processor and memory including executable instructions that, as a result of execution by the processor, causes the reader to perform the method of Claims 1 to 12.

Description

FIELD The invention relates to a method and system. Particularly, but not exclusively, the invention relates to a computer-implemented method for generating a cryptographic key. BACKGROUND Classic McEliece cryptosystems is a post-quantum key encapsulation mechanism (KEM) which is based on codes. This cryptosystem is often discussed as being suitable for resisting attacks from Quantum Computers. It is becoming an increasing requirement for devices with limited access to RAM to need to generate their own public or private keys. The computing requirements of the key generation often conflict with the limited access to RAM. Aspects and embodiments were conceived with the foregoing in mind. SUMMARY Aspects relate to generating a cryptographic key. The cryptographic key may be generated in accordance with a McEliece cryptographic key generation approach. Aspects may be combined with a key encapsulation mechanism (KEM). Viewed from a first aspect, there may be provided a computer-implemented method of generating a public key. The public key may be generated in accordance with the Classic McEliece cryptosystem. The public key may comprise a matrix of a plurality of rows and columns. The number of rows and columns may be determined based on the security properties of the cryptosystem. The method may be implemented by a processing resource. The processing resource may be a secure computing resource such as, for example, a trusted execution environment. The processing resource may be hosted within a computing device. The processing resource may be located within an embedded computing device. The method may comprise receiving a request for a public key. The request may be received from a host computing resource which is hosting the processing resource. The request may be responsive to a request from a user. The method may, responsive to receiving the request, generate a first key generation matrix. The generation of the elements of the first key generation matrix may be done 'ad hoc', that is, independently of other elements in the matrix and without interrupting the rest of the method. The elements may be generated based on a random or pseudorandom seed. That is to say, the first key generation matrix may be generated in a first stage of the key generation process and the 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 in that the elements of the first key generation matrix are used in the generation of the second key generation matrix. This may mean the elements of the first key generation matrix form a part of the second generation matrix or, alternatively or optionally or additionally, that elements of the first key generation matrix are processed to generate the second key generation matrix. This may comprise setting the second key generation matrix equal to a part of the first key generation matrix where a part may be understood not to mean the full first key generation matrix. This may additionally or alternatively or optionally comprise setting a part 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 comprise generating part of an inverse of the second key generation matrix, wherein part of the inverse of the second key generation matrix is not equal to the full inverse of the second key generation matrix. The part 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, where the second key generation matrix is non-invertible, applying a process to make the second key generation matrix invertible. The method may comprise generating a part of the public key based on a part of the inverse of the second key generation matrix and the first key generation matrix. The public key may be dependent on at least one of one or more rows of the inverse of the second key generation matrix and/or one or more rows of the first key generation matrix. The part of the public key may comprise one or more rows of the matrix used to define the public key. A method in accordance with the first aspect enables a key to be generated using fewer memory resources on the processing resource. This enables keys to be generated on devices with lower memory resources (for example an embedded computing device which has low amounts of RAM). Optionally, the inverse of the second key generation matrix is not stored, in that a part of the matrix which is less than the full matrix (and not the full matrix) is stored and the full matrix is not stored. Optionally, the part of the inverse of the second key generation matrix is stored in random access memory. Optionally, the generation of the part of the inverse of the second key generation matrix may be repeated until all of the parts of the second key generation matrix have been used to gen