WO2018213875A1

WO2018213875A1 - Asymmetric cryptography and authentication

Info

Publication number: WO2018213875A1
Application number: PCT/AU2018/050490
Authority: WO
Inventors: Dongxi Liu; Nan Li; Surya Nepal; Jongkil KIM
Original assignee: Commonwealth Scientific And Industrial Research Organisation
Priority date: 2017-05-22
Filing date: 2018-05-22
Publication date: 2018-11-29

Abstract

This disclosure relates to asymmetric cryptography based on key pairs comprising a public key and a private key using a modulus value (q). A computer generates m public key vectors of dimension n+1 for encryption of a message having a message value v. The encryption uses w selected public key vectors selected from the generated m public key vectors as an encryption key. Generating the m public key vectors of dimension of n+1 comprises randomly sampling n elements of each of the m public key vectors, and determining a further element of each of the m public key vectors based on an n dimensional private key vector, a first secret number (sk), a second secret number (p), and randomly sampled error numbers (e j ) up to a secret maximum error value (r). The message value v is at most a public maximum message value t, and t < p and the following condition holds: sk*t + w * r * p < q.

Description

"Asymmetric Cryptography and Authentication"

Cross-Reference to Related Applications

[0001] The present application claims priority from Australian Provisional Patent Application No 2017901941 filed on 22 May 2017, the content of which is

incorporated herein by reference.

Technical Field

[0002] This disclosure relates to asymmetric cryptography based on key pairs comprising a public key and a private key.

Background

[0003] The emergence of Internet of Things (IoT) will see a large number of lightweight devices (referred to as things) connected over the Internet. Lightweight in this context means that the devices have limited processing power and limited energy available. In particular in comparison to user devices, such as PCs, laptops, tablet computers and mobile phones, the lightweight devices have less powerful processors that are slower, less expensive and consume less power.

[0004] Some lightweight devices are deployed to monitor a physical environment and transmit the collected data to a back-end server to store and analyse the data. For example, in a building, lightweight devices can measure temperature and detect smoke in every room. Based on the collected data, the server can determine the exact locations a fire spreading across some of the rooms. A large number of applications are emerging in the area ranging from smart health, smart cities to smart grids.

[0005] When lightweight devices communicate with servers, it is important to determine the authenticity of devices and servers because their communication is over the open Internet. If a server receives data from a fake device (adversary), it may make wrong decisions. For example, an intruder could artificially trigger a fire alarm by sending fake smoke detector data and then use the resulting chaos to break into the building. On the other hand, if a device communicates with a fake server, the privacy of the collected data is no longer protected.

[0006] One way of authenticating devices is based on public-key encryption schemes, such as RSA (Rivest-Shamir-Adleman) and ECC (Elliptic curve cryptography).

However, these schemes are too costly for lightweight devices because they consume too much computation and memory resources.

[0007] Any discussion of documents, acts, materials, devices, articles or the like which has been included in the present specification is not to be taken as an admission that any or all of these matters form part of the prior art base or were common general knowledge in the field relevant to the present disclosure as it existed before the priority date of each claim of this application.

[0008] Throughout this specification the word "comprise", or variations such as "comprises" or "comprising", will be understood to imply the inclusion of a stated element, integer or step, or group of elements, integers or steps, but not the exclusion of any other element, integer or step, or group of elements, integers or steps.

Summary

[0009] A method for asymmetric cryptography using a modulus value (q) comprises: generating m public key vectors of dimension n+l for encryption of a message having a message value v, the encryption using w selected public key vectors selected from the generated m public key vectors as an encryption key, wherein

generating the m public key vectors of dimension of n+l comprises randomly sampling n elements of each of the m public key vectors, and determining a further element of each of the m public key vectors based on an n dimensional private key vector, a first secret number (sk), a second secret number ( ?), and randomly sampled error numbers {ej) up to a secret maximum error value (r), the message value v is at most a public maximum message value t, and t <p and the following condition holds: sk*t + w * r *p < q.

[0010] It is an advantage that some parameters of the method can be adjusted while keeping other parameters constant to meet external requirements, such as security level. In particular, where an application uses only small message values, such as

temperatures, the remaining parameters can be adjusted to reduce the computational complexity and ciphertext sizes. For example, a security level increases with an increase in the dimension of the private key vector, with an increase in the maximum error value r, and with an increase in the number of samples m. At the same time, using a first secret number and a second secret number allows decryption of the encrypted message.

[0011] The n elements in each of the public vectors may be bounded by a public bound b.

[0012] Determining the further element of each of the m public key vectors may comprise scaling the error number by the first secret number and the second secret number.

[0013] The security level of the encryption may comprise a security level of a private key corresponding to the public key and the security level increases with an increase in the secret maximum error value (r).

[0014] The security level of the encryption may comprise a security level of a private key corresponding to the public key and the security level of the private key increases with the increase in the dimension of the private key vector.

[0015] The security level of the encryption may comprise a security level of a private key corresponding to the public key and the security level of the private key increases with the increase of the size of domains of the secret numbers sk and p. [0016] Determining the further element of each of the m public key vectors may be based on a multiplicative inverse ( sk^¹) of the private integer sk.

[0017] The multiple sampled random errors (ef) may be sampled uniformly.

[0018] Determining the further element of each of the m public key vectors may comprise sampling a secret value bs and adding the sampled secret value bs to the further element.

[0019] Encrypting the message may comprise determining a ciphertext vector having a ciphertext vector length (n+ l).

[0020] Encrypting the message may comprise determining a cipher number (c₍„+i₎) that is based on the public key and independent of the message.

[0021] One element (v- C(_{n+1 )} mod q) of the ciphertext vector may be based on the message value and the cipher number.

[0022] A method for cryptographic authentication using a modulus value (q) comprises:

receiving at a first device from a second device a first message {A, Nai} ¾ which is encrypted according to the method of any one of the preceding claims based on a first public key PKb associated with the first device;

decrypting the first message to determine a part of session key that is included in the first message value (Nai);

determining a second message value (Nbi, Nai*B), where Nbi is a nonce generated by the first device;

encrypting the second message value according to the method of any one of the preceding claims based on a second public key associated with the second device to create a second message ({Nbi, Nai*B}P&2);

sending the second message to the second device; and repeating the steps of receiving, decrypting, determining, encrypting and sending for multiple sent nonces and multiple received part keys until the sent nonces together with the received part keys form a shared key.

[0023] Wherein repeating the steps may comprise repeating the steps until reaching a predefined authentication level according to the total length of sent nonces and received part keys.

[0024] A computer system for asymmetric cryptography using a modulus value (q) comprises:

a datastore to store m public key vectors, an n-dimensional private key vector, a first secret number (sk) and a second secret number (p);

a processor to

generate a public key for encrypting a message having a message value

(v), by:

generating the m public key vectors of dimension of n+l by randomly sampling n elements of each of the m public key vectors, and

determining a further element of each of the m public key vectors based on the n dimensional private key vector, the first secret number (sk), the second secret number (p), and randomly sampled error numbers (ej) up to a secret maximum error value (r), wherein the message value v is at most a public maximum message value t, and t < p and the following condition holds: sk*t + w * r * p < q; and

an output port to send the public key to a communication device.

[0025] A method for determining parameters for cryptography comprises:

receiving values for a security level and maximum message value; and determining a modulus value based on the security level and maximum message value to encrypt a message having a message value (v) less than the maximum message value (t) using a public key having m public key vectors of dimension of n+l that each comprise randomly sampled n elements and a further element based on an n dimensional private key vector, a first secret number (sk), a second secret number (p), and randomly sampled error numbers (ef) up to a secret maximum error value (r), wherein the message value v is at most a public maximum message value t, and t < p and the following condition holds: sk*t + w * r * p < q.

[0026] Software, when executed by a computer, causes the computer to perform the above methods.

[0027] A computer system for determining parameters for cryptography comprises: an input port to receive values for a security level and maximum message value; and

a processor to determine a modulus value based on the security level and maximum message value to encrypt a message having a message value (v) less than the maximum message value (t) using a public key having m public key vectors of dimension of n+l that each comprise randomly sampled n elements and a further element based on an n dimensional private key vector, a first secret number (sk), a second secret number (p), and randomly sampled error numbers (ef) up to a secret maximum error value (r),

wherein the message value v is at most a public maximum message value t, and t < p and the following condition holds: sk*t + w * r * p < q.

[0028] Optional features described of any aspect of method, computer readable medium or computer system, where appropriate, similarly apply to the other aspects also described here.

Brief Description of Drawings

[0029] An example will now be described with reference to:

Fig. 1 illustrates a computer system for performing asymmetric cryptography.

Fig. 2 illustrates a method for asymmetric cryptography.

Fig. 3 graphically illustrates the relationship between the parameters used in the method in Fig. 2. Fig. 4 illustrates a method for authentication.

Fig. 5 illustrates testing results for an implemented with two Cooja sky motes for different authentication levels.

Fig. 6 illustrates a method for determining parameters for cryptography.

Fig. 7 illustrates a network of lightweight devices, such as an internet of things.

Description of Embodiments

[0030] This disclosure provides a secure lightweight authentication protocol for lightweight internet of things (IoT) devices. It may be implemented on devices with 8MHz CPU and 10KB RAM.

[0031] The proposed authentication protocol comprises two parts: (a) the underlying part is a lightweight public-key encryption method, and (b) above the encryption method, a sequence of messages exchanged between two parties being authenticated. In use, each lightweight device and server would have a pair of public key and private key. The public key can then be distributed to other parties.

[0032] When a device and a server (or two devices) know each other's public keys, they exchange a sequence of messages specified by the proposed protocol. If all messages are correct, then the device and the server are mutually authenticated with each other. The number of messages in the sequence determines the strength level of authentication. After the authentication, the device and the server share a nonce, with its length determined by the number of messages exchanged or the authentication level. The nonce can be used as the session key for a symmetric encryption method to encrypt the rest of communication between the lightweight device and the server.

[0033] The underlying public-key encryption method comprises three methods: the key generation algorithm, the encryption and decryption algorithms. The authentication protocol has a balanced combination of three features: secure, efficient, and relatively short ciphertexts. [0034] The security of the proposed method can be reduced to the hardness of the Learning with Secretly-Scaled Errors in Dense Lattice (referred to as Compact-LWE) problem, which a variant of Learning with Errors (LWE) problem. In addition, the proposed method allows each IoT device to generate its own key pair independently without a need for a Trusted Third Party. Further, at a security level above 128 bits for both keys and messages, the ciphertext can be as small as 176 bits for 16-bit message space.

[0035] The proposed protocol takes about 148ms for the initiating party to complete 1^st -level authentication (with 3 messages exchanged by both parties) under the Cooja simulation environment, while taking 2s for the initiating party to complete 16^th -level authentication (with 33 messages exchanged by both parties). This shows that lightweight devices can choose suitable authentication levels based on the sensitivity of communication contents. The proposed method can encrypt large integers, and in one example implementation 16-bit integers are encrypted and decrypted. The methods herein are designed for authenticating resource-constrained IoT devices and generating shared session keys between two authenticated parties. It can be used in all applications of IoT or IoE (Internet of Everything). For example, smart home, smart city, smart health, smart manufacturing, etc. Further example applications include smoke sensors, smart meters, such as gas or electricity, wearable devices, such as pulse watches and medical data collectors and controllers in implanted medical devices.

[0036] Fig. 1 illustrates a computer system 100 for performing asymmetric cryptography. The computer system 100 comprises a processor 102 connected to a program memory 104, a data memory 106, a communication port 108 and a user port 110. The program memory 104 is a non-transitory computer readable medium, such as a hard drive, a solid state disk or CD-ROM. The data memory 106 stores a message and multiple public key vectors that form a public key associated with the device 100. Software, that is, an executable program stored on program memory 104 causes the processor 102 to perform the method in Fig. 2, that is, processor 102 generates a public key as described with reference to Fig. 2. [0037] After generation, the processor 102 may store the public key on data store 106, which may comprise RAM or a processor register. Processor 102 may also send the public key via communication port 108 to a server or another device, such as second IoT device 120, that can then send an encrypted message back to the computer system 100. As will be described in detail below, one of the public key vectors is based on an n dimensional private key vector, two secret numbers (sk and p) and multiple sampled random errors up to a maximum error value (r). When reference is made to secret numbers, this is to be understood in the sense that those numbers or other values are not known to the other communication parties. For example, the secret numbers may be stored on data memory 106 alongside the private key such that they are not accessible by other devices, such as by setting file access rights accordingly, by encrypting this data locally or simply by blocking all access to data memory 106 from outside the computer system 100.

[0038] The processor 102 may receive data, such as encrypted messages, from data memory 106 as well as from the communications port 108. In one example, the processor 102 receives an encrypted message from the second IoT device 120 via communications port 108, such as by using a Wi-Fi network according to IEEE 802.1 1, or IPv6 over Low-power Wireless Personal Area Networks (6L0WPAN) according to IEEE 802.15.4. The Wi-Fi network may be a decentralised ad-hoc network, such that no dedicated management infrastructure, such as a router, is required or a centralised network with a router or access point managing the network.

[0039] In one example, the processor 102 receives and processes the encrypted message in real time. This means that the processor 102 determines the clear text every time a message is received from second IoT device and completes this decryption before the second IoT device 120 sends the next encrypted message. This can be useful in high frequency sensor application where second IoT device 120 is a smart sensor that sends sensor data at regular intervals, such as every 100ms. In this particular application it is a technical advantage that the proposed method requires less computer resources (memory and/or CPU time) than other methods, which allows high-frequency real-time encryption and decryption on lightweight devices. [0040] Although communications port 108 and user port 110 are shown as distinct entities, it is to be understood that any kind of data port may be used to receive data, such as a network connection, a memory interface, a pin of the chip package of processor 102, or logical ports, such as IP sockets or parameters of functions stored on program memory 104 and executed by processor 102. These parameters may be stored on data memory 106 and may be handled by-value or by-reference, that is, as a pointer, in the source code.

[0041] The processor 102 may receive data through all these interfaces, which includes memory access of volatile memory, such as cache or RAM, or non-volatile memory, such as an optical disk drive, hard disk drive, storage server or cloud storage. The computer system 100 may further be implemented within a cloud computing environment, such as a managed group of interconnected servers hosting a dynamic number of virtual machines.

[0042] It is to be understood that any receiving step may be preceded by the processor 102 determining or computing the data that is later received. For example, the processor 102 decrypts a message and stores the plain text in data memory 106, such as RAM or a processor register. The processor 102 then requests the data from the data memory 106, such as by providing a read signal together with a memory address. The data memory 106 provides the data as a voltage signal on a physical bit line and the processor 102 receives the plain text via a memory interface.

[0043] It is to be understood that throughout this disclosure unless stated otherwise, sets, solutions, variables, keys, plain text, ciphertext, message and the like refer to data structures, which are physically stored on data memory 106 or processed by processor 102. Further, for the sake of brevity when reference is made to particular variable names, such as "message" or "key" this is to be understood to refer to values of variables stored as physical data in computer system 100.

[0044] Fig. 2 illustrates a method 200 as performed by processor 102 for asymmetric cryptography. Fig. 2 is to be understood as a blueprint for the software program and may be implemented step-by-step, such that each step in Fig. 2 is represented by a function in a programming language, such as C++ or Java. The resulting source code is then compiled and stored as computer executable instructions on program memory 104.

[0045] The asymmetric cryptography method 200 uses a modulus value q, which means that for encryption and decryption processor 102 performs a modulo operation on q ("mod q") which results in the integer remainder of a division by q.

[0046] Method 200 comprises the step of generating 202 m public key vectors of dimension n+l for encryption of a message. Generally, the message has a message value v. This particular encryption uses w selected public key vectors selected from the generated m public key vectors as an encryption key. Encrypting means the calculation of a value or string, referred to as ciphertext, that contains practically no information content unless being decrypted by a recipient. For example, AES encryption may calculate for the message text "mysecretpassword" a ciphertext of

"e8da47acc08bc751745ef8fbfF44el07". The message value is an integer that represents the message text. For example, letter 'a' in ascii encoding has a binary value of Ί 1 0001 ', which is a decimal value of 97. A two letter word 'ab' has the binary value of 'a' concatenated with the binary value for 'b', that is ' 1 100 01 1 1 0010', which is a decimal value of "3, 186".

[0047] Each of the public key vectors has the form (ΡΚ , . . . PK_j„, PK_j(n+1)).

Together, w vectors of the public key vectors form a public key as will be described in more detail below. Generating the m public key vectors comprises randomly sampling 204 n elements of each of the m public key vectors up to the parameter b. This means generating n random numbers for each public key vector, such as by calling a rand() function n times and scaling the random numbers to be within {0, . . . , b) . In total, processor 102 generates mxn random numbers. Processor 102 generates 206 the (n+l) ^t element of each of the m public key vectors based on an n dimensional private key vector, a first secret number (sk), a second secret number ( ?), and randomly sampled error numbers (ef) up to a secret maximum error value (r). In other words, processor 102 samples errors e, from the set {0, r-1 } . [0048] In order to make the method 200 efficient, the message value v is at most the public integer t as indicated at 204. Further, a security level increases with an increase in the dimension of the private key vector, an increase in the maximum error value r and with an increase in the number of samples m as indicated at 206. Finally, the condition sk*t + w * r * p < q is satisfied as indicated at 208.

[0049] The above conditions basically describe a multiple parameter trade off where ultimately it is the computational complexity that is the cost for increasing message length and security. Fig. 3 graphically illustrates the above relationship. Fig. 3 shows the modulus value q 302, the secret number p 304, the maximum message value t 306, the number of samples w selected from the m public key vectors in encryption, maximum error value r and the secret number p, w*r*p 308 and the result of sk*t+w*r*p 310. The secret number p 304 also directly influences the value of the product w*r*p 308, which is indicated by a dotted line 312. The '<' sign indicates that the upper values remains above the lower value. In particular, q 302 remains above sk*t+w*r*p 310 and p 304 remains above t 306. The value of q 302 directly influences the computational complexity (CPU load or computation time) as a larger modulo value leads to more calculations and higher memory usage. The values of w and r directly influence the key security level and message security level, respectively.

Increasing the payload would increase the data rate which is generally desired.

Increasing the payload 306 means increasing the secret number p 307, since p>t.

However, this would also increase sk*t+w*r*p 310 due to the direct relationship 312. In turn, to keep q 302 above sk*t+w*r*p 310, q 302 is increased resulting in a higher computational complexity to achieve the higher payload.

[0050] Similarly, in order to increase security 310, the modulus value q 302 would increase unless the payload 304 is decreased at the same time. In some applications, the message length is predefined. For example, a sensor sends a temperature in a fixed message format of 2 bytes which provides 65,536 different values, so /=65,535 and setting /?>65,535. [0051] It is noted that processor 102 may calculate the above values in any combination of given and unknown values including:

calculating t to be just smaller than (q - w*r*p)lsk

calculating w to be just smaller than (q - sk*t)l{r*p)

calculating r to be just smaller than (q - sk*t)l{w*p)

calculating p to be just smaller than (q - sk*t)l{w*r)

calculating q to be just greater than sk*t + w*r*p.

[0052] The security parameters of the proposed method include the following five public positive integers:

q : Modulus and max value for private key elements

w : number of repetitions of calculating cipher and number of public key vectors sampled from the m generated public key vectors

n : length of private key vector

m : number of generated public key vectors

b : the maximum value of the first n elements in public key vectors

t : the maximum message value

[0053] and the three private integers:

\p\ : an integer indicating the size of the domain from which p is randomly sampled \sk\: an integer indicating the size of the domain from which sk is randomly sampled r: the maximum error value for sampling errors in public key generation

[0054] q, p and sk are mutually co-prime, and ri>\ . To ensure the correctness of the proposed method, it is ensured that t < p and sk*t + w*r*p < q.

[0055] The proposed method consists of three algorithms: key generation, encryption and decryption.

[0056] Private Keys [0057] A private key consists of an n-dimensional vector (Kj, K_n), where each K_t (1≤ i≤ n) is uniformly sampled from the set {0, . . . , -l } . The three secret integers sk, r, and p as defined above, satisfy the conditions t < p and sk*t + w*r*p < q.

[0058] Public Keys

[0059] A public key is derived from a private key, and the ciphertext generated with a public key can only be decrypted by the corresponding private key.

[0060] As outlined above, processor 102 generates m public key vectors, each of which is a (n+1 J-dimensional vector (PKji, PKj_(n+1)) for 1< j < m. Processor 102 samples the first n elements ΡΚβ (1 < i < n) of each of the m public key vectors uniformly from the set { l, . . . ,b-l } . Processor 102 determines the last element PKj_(n+1) by the following steps:

PKj_(n+i₎ = Ki * PKji + . . . + K_n* PKja + e_j mod q, where e is uniformly sampled from the set {0, . . . ,r-l } and sk_q ¹ satisfies sk*sk_q ¹⁼-\ mod q, where sk_q ³ denotes the multiplicative invers with respect to modulus q.

[0061] The equation shows how the public key vectors PKj_(n+1) are based on elements Kj to K_n and three private integers sk, p, r. The term e, *sk_q ¹*p illustrates how sk and p scale the error value e_j. It is noted that the notation sk_q ¹ used herein denotes the invers with respect to modulus q.

[0062] Encryption

[0063] Suppose a plaintext value v < t will be encrypted. The addition of two vectors is denoted by ®. The ciphertext of encrypting v is represented by C, which is a (n+1)- dimensional vector. The encryption algorithm consists of the following steps to generate C.

Step 1 : sample an integer j uniformly from the set { 1, . . . ,m} and let C = (PKji, PKj_(n+1)) be the corresponding sample in the public key.

Step 2: sample w-l integers uniformly from the set { 1, . . . ,m}; for each sampled integer j, do the update C = C ® (PK_jh PK_j(n+1}).

Step 3 : let C = (ci, . . . , C(„+i)) and then generate C=(c;, ... , v - C(_n+i)).

[0064] Step 1 combined with the repetition of Step 2 together represent an encryption based on a number of samples w from m public key vectors. Step 3 : calculate the final ciphertext.

[0065] In the above steps, the additions, subtractions and multiplications of two integers are implicitly followed by the modulo operation with q. For example, v - C(_n+i) means v - C(_n+1) mod q.

[0066] The method is probabilistic since two encryptions of the same plaintext value lead to different ciphertexts due to the random selection of public key vectors.

[0067] Decryption

[0068] Suppose a ciphertext is C = (ci, . . . ,C(„+i)). With the private key (Kj, ... , K_n), the decryption algorithm recovers the plaintext value v by three steps.

Step 1 : calculate C = Ki*ci+...+K_n*c„ + C(„₊;) inod q.

Step 2: calculate skv = sk*C mod q.

Step 3 : calculate v = skp ¹ *skv mod p, where sk*sk_p ¹⁼\ mod p, where sk and p are the secret numbers that are used to scale the random error values e, during the generation of the public key as described above.

[0069] An Optimised Method

[0070] The above method may be optimised as follows. This optimised method generates the same size of ciphertexts, with the same size of public keys, but has an extra secret value to further increase the security of the proposed scheme. Let bs be a new secret value in the private key, which is uniformly sampled from the set { 1 , ... ,q- 1 }. The following is the new definition of public key. [0071] A public key still consists of m vectors, each of which is a (n+1 J-dimensional vector {PK_ji, PK_j(n+1)) for \<j < m. The first n elements ΡΚ_β (1 < i < n) are uniformly sampled from the set { 1, . . . ,b-l }, while the last element PK_j(n+1) is determined by the following steps:

PK_j(n+1) = Ki* PK_ji + . . . + K_n* PK_ja + bs + e_j *sk_q '*p mod q, where e, is uniformly sampled from the set {0, . . . ,r-l } and sk_q ¹ satisfies sk_q *sk_q ¹⁼-l mod q.

[0072] There is no change to the encryption algorithm. However, the decryption algorithm is revised to consider the extra secret.

[0073] Suppose the cipherext to be decrypted is (ci, . . . ,c„, c„₊i). Then, the optimised method uses the following steps to recover the plaintext v.

Step 1 : calculate C = Ki*ci+. . . +K_n*c„ + w*bs+ „₊ij mod q.

Step 2: calculate skv = sk*C mod q.

Step 3 : calculate v = sk_p ³ *skv mod p, where sk*sk_p ¹⁼\ mod p. [0074] Reduction of Public Keys Size

[0075] What follows is a method for reducing the size of public keys. For a public key vector {ΡΚμ, . . . , PK_j(n+1)), processor 102 reuses the elements ΡΚμ, PK_jn in other public key vectors. Since these elements are randomly sampled, this reuse is feasible. With this method, a public vector only needs to store its last element, if its first n elements can be derived from other public vectors.

[0076] Security Analysis

[0077] Due to secretly-scaled errors (i.e., e, *sk_q ¹*p) and the dense lattice induced from PK_ji, PK_ja (since they are bounded by b instead of q), the proposed scheme can resist well-known lattice-based attacks to the LWE problem. In addition, due to the limited number of public key vectors, the proposed scheme is also resistant to the algebraic and combination attacks to LWE. [0078] We consider the security from two aspects. In a first aspect the security level comprises a security level of a private key corresponding to the public key, meaning that whether a private key can be recovered from its corresponding public key. The security of the private key is based on the assumption of a hardness problem LWE and a reduction from LWE to Compact-LWE. According to this assumption, from a public key, the adversary cannot learn the corresponding private key, because m equations in the definition of the public key contain unknown errors e,.

[0079] The security level of the private key is defined as the minimal value between l°g2 (∑[l'_i∑ J',¾i ^γΐ1) ^and log₂ rⁿ⁺¹, where r < ^{q 1 sk} * J^l)^* j^ sk is the z^'th value in the domain of sk, and p_j is the y^'th value in the domain of p.

[0080] In a second aspect the security level comprises a security level of a message, that is, the hardness of recover a plaintext message from the ciphertext without knowing the private key. In the above encryption method, w vectors in the public key are randomly selected in Step 1 and Step 2. If these w vectors are correctly guessed by the adversary, it can recover the plaintext. The number of combinations of w vectors randomly sampled from m public key vectors determines the security level of messages, which is defined as log₂ where

_n i w! fm-n\^k ( _Λ m-n\^w~k

Pr(fc) = — - * ( * 1

J k\(w-k)\ V m ) \ m ) [0081] An Example

[0082] In this example, the public parameters used in this example is listed in the following Table. q t b m w n

4294967296 65535 16 74 86 13 [0083] For the above public parameters, we use the following two sets of private

parameters, respectively, for Alice (A) and Bob (B).

[0084] With the above parameters, the security level of private keys is about 138 bits, and the security level of messages is 129 bits for both Alice and Bob. If only the last element PK_j(n+1) in a public key vector needs to be published, then the size of a public key is 74*32 = 2368 bits for the above configuration. The ciphertext size can be 176 bits.

[0085] We evaluated the performance of the proposed scheme in Cooja using the sky mote, which has 8MHz CPU and 10KB ram. In one second, the mote can perform 50 encryptions, and 500 decryptions.

[0086] A Mutual Levelled Authentication Protocol [0087] The above light-weight public key encryption method can be used to implement a protocol adjusted from the Needham-Schroeder-Lowe Public-Key protocol, which has been formally analysed for its security.

[0088] Let A denote a user number allocated to Alice, with the public key PKa, and B denote a user number allocated to Bob, with the public key PKb. The Needham- Schroeder-Lowe Public-Key protocol proceeds by exchanging the following three messages, where Na and Nb are nonces.

A -> B : {A, Na}P ¾

B -> A : {B, Na, Nb}P&z

A -> B : {Nb}P ¾

[0089] To achieve levelled authentication, the above protocol is revised to an iterative style. In each iteration, Alice and Bob exchange two nonces. After a number of iterations, processor 102 can achieve the security level expected by a particular situation. Let L be the authentication level, and let Na_{, and Nbi (1< i< L) be nonces. Then, the levelled authentication protocol is defined as follows.

B -> A : { Nb₂, Na₂*B}P&¾

A -> B : {Nb₂*A, Na₃}P ¾

B -> A : { Nb₃, Na₃*B}P&¾

A -> B : {Nb_t* A, 0x00}PKb

[0090] For the above parameter configuration, we let Na_{, and Nbi be one-byte nonces; note that a multiplication above, such as Nai*B and Nbi*A, may produce a 2- byte value. Processor 102 can change this 2-byte value into a 1-byte value by calculating the exclusive or of its two bytes.

[0091] It is noted that processor 102 can perform the above methods without performing an exponential calculation, which is often considered a complex operation. As a result, the required computational resources are reduced.

[0092] Fig. 4 illustrates the above method for authentication as performed by the device 100. Similar to method 200 in Fig. 2, method 400 may be stored as program code on program memory 104 and executed by processor 102. As above, the individual steps are based on a modulus value P. Method 400 commences by processor 102 receiving 402 at first device 100 from a second device 120 a first message. The first message is encrypted according to method 200 and the above description. That is, the encryption is based on a first public key associated with the first device 100.

[0093] Processor 102 then decrypts 404 the first message to determine a first part key Nai that is included in the first message value. Processor 102 further determines 406 a second message value based on the first part key and a nonce Nbi: (Nbi, Nai*B). In one example, processor 102 concatenates these items to determine the second message value. Processor 102 then encrypts 408 the second message value according to the above encryption method based on a second public key associated with the second device 120 to create a second message ({Nbi, Nai*B}P&2).

[0094] It is noted that this disclosure uses "first part key" to refer to the value that processor 102 receives from second device 120. It is to be noted, however, that this is also a nonce but generated by second device 120. The distinction between 'nonce' and 'part key' is simply to clarify that the nonce is generated by processor 102 while the 'part key' is generated by second device 120. As an equivalent, both parameters may be referred to as nonces or part keys because the nonces together ultimately form the key. [0095] Finally, processor 102 sends 410 the second message to the second device 120. Processor 102 then repeats 412 the steps of receiving 402, decrypting 404, determining 406, encrypting 408 and sending 410 for multiple sent nonces Nb_x and multiple received part keys Na_x until the sent part keys Nb_x together with the received part keys Na_x form a shared key. Processor 102 stores the multiple part keys Nb_x on data store 106 as a public key associated with the second device 120. For example, processor 102 stores the public key in first column of a row in a database table and a device identifier in a second column of the same row.

[0096] We implemented the protocol and evaluated its performance with two Cooja sky motes, one as Alice, and the other as Bob. In our evaluation, we test the time needed for Alice to complete the protocol for different authentication levels. Fig. 5 illustrates the testing results.

[0097] Fig. 6 illustrates a method 600 for determining parameters for cryptography as performed by processor 102. Similar to method 200 in Fig. 2, method 600 may be stored as program code on program memory 104 and executed by processor 102. In particular, processor 102 starts method 600 by receiving 602 values for a security level and maximum message value. Processor 102 then determines 604 a modulus value based on the security level and maximum message value to encrypt a message having a message value (v) less than the maximum message value (t). As described above, encrypting the message is based on a number of samples (w) from m public key vectors that form a public key. One of the public vectors is based on an n dimensional private key vector, two secret numbers (sk and p) and multiple sampled errors up to a maximum error value (r).

[0098] As also described above, processor 102 may determine the modulus value q based on the equation sk*t + w*r*p < q, where t is the maximum message value, w is the number of samples selected in an encryption, r is the maximum error value and p > t is mutually co-prime with q and sk. [0099] Processor 102 may further determine the modulus value based on a private key security level, which is determined by the minimal value between

^rTL) and log_{7 r} ⁿ , ^ q-l-ski* t-l)

σ where r < W_*P_j .

[0100] It is noted that since processor 102 performs method 600 computer system 100 described in Fig. 1 may serve as a computer system for determining parameters for cryptography. In particular, the computer system 100 comprises input port 110 to receive values for a security level and maximum message value. Processor 102 may receive these values from a system design engineer through a user input or from a configuration file stored on data store 106 through a memory interface data port.

[0101] Processor 102 determines a modulus value based on the security level and maximum message value such that sk*t + w*r*p < q is satisfied. For example, processor 102 calculates q = sk*t + w*r*p + 1. As above, the maximum message value t is less than p, a security level increases with an increase in a maximum sample value r for errors and with an increase in the number of samples. Ports 108 and 110 can be used as output ports to send the modulus value to a cryptographic device. For example, processor 102 may send the modulus value to multiple devices in an IoT network, store the value on a configuration file or may display the modulo value on screen 112. In one example, processor 102 writes the modulo value as part of firmware into the IoT devices, which means the method 600 of determining the cryptographic parameters becomes an important step in the fabrication of IoT devices as without the output of method 600, the IoT devices would not be able to perform as well because their cryptographic systems would be inferior.

[0102] Fig. 7 illustrates a network 700 of lightweight devices, such as an internet of things. Network 700 comprises lightweight devices 701, 702, 703and 704. Devices 701, 702 and 703 are connected by a wireless communication network, such as Wifi, or an ad-hoc wireless network. Device 704 is connected to the other devices 701, 702 and 703 through the internet 705 or any other third-party operated network. Connected to the internet 705 is also a server 706. Server 706 may collect data from the devices 701, 702, 703 and 704, in which case the devices 701, 702, 703 and 704 encrypt their data using a public key associated with the server 706 as described above. Server 706 may also generate multiple pairs of public and private keys (potentially re-using vector elements) and distribute them to the devices 701, 702, 703 and 704. In other examples, each of the devices 701, 702, 703 and 704 perform the methods described herein to generate their own public/private key pair and communicate with each other using the corresponding keys as needed. In particular, devices 701, 702, 703 and 704 and server 706 perform method 400 in Fig. 4 to authenticate each other and generate a shared secret key for more efficient communication.

[0103] It will be appreciated by persons skilled in the art that numerous variations and/or modifications may be made to the specific embodiments without departing from the scope as defined in the claims.

[0104] It should be understood that the techniques of the present disclosure might be implemented using a variety of technologies. For example, the methods described herein may be implemented by a series of computer executable instructions residing on a suitable computer readable medium. Suitable computer readable media may include volatile (e.g. RAM) and/or non-volatile (e.g. ROM, disk) memory, carrier waves and transmission media. Exemplary carrier waves may take the form of electrical, electromagnetic or optical signals conveying digital data steams along a local network or a publically accessible network such as the internet.

[0105] It should also be understood that, unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the

description, discussions utilizing terms such as "estimating" or "processing" or

"computing" or "calculating", "optimizing" or "determining" or "displaying" or "maximising" or the like, refer to the action and processes of a computer system, or similar electronic computing device, that processes and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

[0106] The present embodiments are, therefore, to be considered in all respects as illustrative and not restrictive.

Claims

CLAIMS:

1. A method for asymmetric cryptography using a modulus value (q), the method comprising:

generating m public key vectors of dimension n+l for encryption of a message having a message value v, the encryption using w selected public key vectors selected from the generated m public key vectors as an encryption key, wherein

generating the m public key vectors of dimension of n+l comprises randomly sampling n elements of each of the m public key vectors, and determining a further element of each of the m public key vectors based on an n dimensional private key vector, a first secret number (sk), a second secret number ( ?), and randomly sampled error numbers (ef) up to a secret maximum error value (r),

the message value v is at most a public maximum message value t, and t < p and the following condition holds: sk*t + w * r * p < q.

2. The method of claim 1, wherein the n elements in each of the public vectors are bounded by a public bound b.

3. The method of claim 1 or 2, wherein determining the further element of each of the m public key vectors comprises scaling the error number by the first secret number and the second secret number.

4. The method of any one of the preceding claims, wherein a security level of the encryption comprises a security level of a private key corresponding to the public key and the security level increases with an increase in the secret maximum error value (r).

5. The method of any one of the preceding claims, wherein a security level of the encryption comprises a security level of a private key corresponding to the public key and the security level of the private key increases with the increase in the dimension of the private key vector.

6. The method of any one of the preceding claims, wherein a security level of the encryption comprises a security level of a private key corresponding to the public key and the security level of the private key increases with the increase of the size of domains of the secret numbers sk and p.

7. The method of any one of the preceding claims, wherein determining the further element of each of the m public key vectors is based on a multiplicative inverse ( sk_q ^'1) of the private integer sk.

8. The method of any one of the preceding claims, wherein thee multiple sampled random errors {ej) are sampled uniformly.

9. The method of any one of the preceding claims, wherein determining the further element of each of the m public key vectors comprises sampling a secret value bs and adding the sampled secret value bs to the further element.

10. The method of any one of the preceding claims, wherein encrypting the message comprises determining a ciphertext vector having a ciphertext vector length (n+ l).

1 1. The method of claim 10, wherein encrypting the message comprises determining a cipher number {c_(n+1 } that is based on the public key and independent of the message.

12. The method of claim 1 1, wherein one element (v- C(„+i) mod q) of the ciphertext vector is based on the message value and the cipher number.

13. A method for cryptographic authentication using a modulus value (q), the method comprising:

receiving at a first device from a second device a first message {A, Nai} ¾ which is encrypted according to the method of any one of the preceding claims based on a first public key PKb associated with the first device; decrypting the first message to determine a part of session key that is included in the first message value (Nai);

sending the second message to the second device; and

repeating the steps of receiving, decrypting, determining, encrypting and sending for multiple sent nonces and multiple received part keys until the sent nonces together with the received part keys form a shared key.

14. The method of claim 13, wherein repeating the steps comprises repeating the steps until reaching a predefined authentication level according to the total length of sent nonces and received part keys.

15. A computer system for asymmetric cryptography using a modulus value (q), the computer system comprising:

a processor to

generate a public key for encrypting a message having a message value

(v), by:

generating the m public key vectors of dimension of n+l by randomly sampling n elements of each of the m public key vectors, and determining a further element of each of the m public key vectors based on the n dimensional private key vector, the first secret number (sk), the second secret number (p), and randomly sampled error numbers (ej) up to a secret maximum error value (r), wherein the message value v is at most a public maximum message value t, and t < p and the following condition holds: sk*t + w * r * p < q; and

an output port to send the public key to a communication device.

16. A method for determining parameters for cryptography comprises:

17. Software that, when executed by a computer, causes the computer to perform the method of any one of claims 1 to 14 and 16.

18. A computer system for determining parameters for cryptography, the computer system comprising:

an input port to receive values for a security level and maximum message value; and