ABSTRACT
Abstract
Some embodiments relate to a first electronic network node is provided ( 110 ) configured for a cryptographic operation. The first network node is configured to receive as input a difficulty parameter (d), and a structure parameter (n), and to obtain a shared matrix (A), the shared matrix being shared a second network node through a communication interface, entries in the shared matrix (A) being selected modulo a first modulus (q), the shared matrix (A) being a square matrix (kÃk) of dimension (k) equal to the difficulty parameter (d) divided by the structure parameter (n), the entries in the shared matrix (A) being polynomials modulo a reduction polynomial (Æ) of degree equal to the structure parameter (n), said cryptographic operation using the shared matrix.
Description
CROSS-REFERENCE TO PRIOR APPLICATIONS
This application is the U.S. National Phase application under 35 U.S.C. § 371 of International Application No. PCT/EP2018/077639, filed on Oct. 10, 2018, which claims the benefit of EP Patent Application No. EP 18165330.4, filed on Mar. 30, 2018 and EP Patent Application No. EP 17196812.6, filed on Oct. 17, 2017. These applications are hereby incorporated by reference herein.
FIELD OF THE INVENTION
The invention relates to a network node configured for a cryptographic operation, a cryptographic operation method, and a computer readable medium.
BACKGROUND OF THE INVENTION
In cryptography, a key-agreement protocol is a protocol whereby two or more parties that may not yet share a common key can agree on such a key. Preferably, both parties can influence the outcome so that neither party can force the choice of key. An attacker who eavesdrops on all communication between the two parties should learn nothing about the key. Yet, while the attacker who sees the same communication learns nothing or little, the parties themselves can derive a shared key. Key agreement protocols are useful, e.g., to secure communication, e.g., to encrypt and/or authenticate messages between the parties.
In order to facilitate secure communication among parties, key agreement protocols are sometimes further subdivided into cryptographic key-exchange (KEX) and cryptographic key-encapsulation (KEM) schemes.
KEX schemes may involve the exchange of public-keys by each party, that are then independently used by the other party along with their own secret-key to calculate the common shared secret. A well-known example of such a KEX scheme is the Diffie-Hellman key-exchange, whose security is based on solving the discrete logarithm problem. An interesting feature of some KEX schemes is that the actual final, shared secret is never exchanged between the parties, not even in encrypted form, but is calculated independently by the two parties at each end. This results in a desirable feature known as forward-secrecy, which ensures that even the compromise of a party's long-term secret-key by an attacker in the future would not compromise the secrecy of encrypted message exchanged in the past.
KEM schemes may establish a shared secret between two entities or parties using asymmetric cryptography by one party, usually the initiator of the communication, to encrypt or encapsulate (using the other party's public-key) and transmit a shared secret to the other party, known as the responder, who can then decrypt or decapsulate it (using her secret-key) and then use it for securely communicating with the initiator party. Such KEM schemes may only achieve forward-secrecy if it is ephemeral. Otherwise, any attacker that compromises a party's secret-key for a past session and has recorded all messages exchanged between the parties in that session can recover the shared secret for that particular session.
Due to increasing security needs in the Internet of Things, key-exchange schemes need to also achieve high efficiency (i.e., minimal amount of communication or bandwidth requirements) while also remaining secure, against classical as well as quantum-capable adversaries.
Recent advances indicate that quantum-computers may be feasible in a few years. Perhaps as soon as within some 5-10 years. As soon as a quantum-computer is available, most existing public-key cryptographic schemes will become unsecure since the underlying problems, on which they are based, can efficiently be solved with a quantum computer. Therefore, it is very important to design quantum-resistant public-key algorithms, i.e., public-key algorithms that cannot be broken by means of a quantum-computer.
There are several classes of quantum-resistant algorithms: lattice-based, code-based, isogeny-based, etc. In this document, we deal with quantum-resistant algorithms based on lattices. Lattice based cryptographic systems are an active area of research in which many different types of systems have been proposed. For example, the lattice may be defined in terms of a matrix of numbers, e.g., elements of some finite field, or using a polynomial, etc. The type of cryptographic operation can also vary. For example, lattice based cryptography is available for: Key encapsulation (KEM), Key exchange (KEX), Public key encryption (PKE), digital signatures, etc. Examples of those schemes are:
LWE-based KEX such as Frodo RLWE-based KEX and CPA-KEM Newhope and NewHopeSimple. Module-lattice-based CPA-PKE, CPA-KEM and CCA-KEM as Kyber LWR-based KEX as spKEX Each of the above schemes implements a cryptographic protocol (e.g., a KEX, a KEM, or PKE) relying on a single underlying problem, e.g., either Learning-with-errors (LWE), or Learning-with-rounding (LWR), or module-lattices with modules, e.g., RLWE for a fixed ring, or LWR. For example: NewHope only relies on RLWE, Kyber only relies on combining k=3 modules, each module being a polynomial in Zq[x]/x{circumflex over (â)}256+1, spKEX only relies on LWR, Frodo only relies on LWE. The R in schemes such as RLWE refers to âringâ, or polynomial type implementations.
This poses several problems. First of all, implementing each of these systems would be a large investment. Not only would each of the schemes have to be coded, they would also each have to be debugged, to ensure that they do not contain critical bugs that could impair their security. On the other hand, not implementing all schemes, or at least the majority also implies certain risks. If one of the above problems is broken, e.g., RLWE or Module lattice, then the corresponding schemes are fully broken. It is desirable that there is some upgrade path, so that in case of a break, one can change from one type of scheme to another.
REFERENCES
[1] âDevice and method sharing a matrix for use in a cryptographic protocolâ, European filing op 6 Mar. 2017, application Ser. No. 17/159,296.7.
[2] Ludo Tolhuizen, Ronald Rietman and Oscar Garcia-Morchon, âImproved key reconciliation methodâ, Cryptology ePrint Archive, Report 2017/295, https://eprint.iacr.org/2017/295
[3](Frodo): J. Bos et al, âFrodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWEâ, Cryptology ePrint Archive, Report 2016/659, https://eprint.iacr.org/2016/659
[4] (New Hope): E. Alkim et al, âPost-quantum key exchangeâa new hopeâ, Cryptology ePrint Archive, Report 2015/192, https://eprint.iacr.org/2015/1092
[5] (New Hope Simple): E. Alim et al, âNewHope without reconciliationâ, Cryptology ePrint Archive, Report 2016/1157, https://eprint.iacr.org/2016/1157
[6] (Kyber): J. Bos et al, âCRYSTALS-Kyber: a CCA-secure module-lattice-based KEMâ, Cryptology ePrint Archive, Report 2017/634, https://eprint.iacr.org/2017/634
[7] (spKEX): S. Bhattacharya et al, âspKEX: an optimized lattice-based key exchangeâ, Cryptology ePrint Archive, Report 2017/709, https://eprint.iacr.org/2017/709
Each one of references [1] to [7] is included herein by reference.
SUMMARY OF THE INVENTION
The inventors realized that it is possible to define a single scheme which parametrizes large classes of lattice based cryptography. Taking only a few input parameters, which change the nature of the underlying cryptography. For example, a cryptographic device as defined in the claims may receive a difficulty parameter (d), and a structure parameter (n) which together suffice to specify the type of cryptography that is used. Both the difficulty parameter (d), and a structure parameter (n) are positive integers. By increasing the difficulty parameter, the structure of the problem stays the same, but larger, and thus harder instantiations are used. A difficulty parameter is sometimes referred to as a security parameter. In embodiment, the difficulty parameter is related to the dimension of the underlying lattice. A larger value of the difficulty parameter leads to a higher dimension of the underlying lattice, and thus to a harder problem for an attacker to solve. The structure parameter is related to the amount of algebraic structure in the system. A higher value of the structure parameter implies more algebraic structure. It is conjectured that higher values of the structure parameter may be easier to attack, since the lattice has more regularity. For example, in case of advancing research finding an incrementally better way to solve lattice problems, then a user may respond by increasing the difficulty parameter. On the other hand, if advancing research find a radically better way to solve a particular type of lattice problem, then the user may respond with decreasing the structure parameter.
For example, in an embodiment a scheme is defined that can efficiently instantiate multiple underlying problems, namely RLWE, RLWR, module RLWE, module RLWR, and LWE and LWR. This does not mean that the scheme relies on two different specifications, one for Problem 1 and another for Problem 2, but that the same algorithm can be used for instantiate both problems, the only difference being the input parameters. Advantages include:
Coverage of many potential applications with a same scheme.
Minimization of implementation cost
Reduction of code size.
Preparation for a potential transition scenario in which relying on a âweakerâ problem is no longer secure and new algorithms relying on a âstrongerâ problem is required.
The cryptographic device is an electronic device. For example, the cryptographic device may be a mobile electronic device, e.g., a mobile phone. For example, the cryptographic device may be set-top box, smart-card, computer, etc. The method of performing a cryptographic operation described herein may be applied in a wide range of practical applications. Such practical applications include financial applications, confidential or authenticated communication, etc.
A method according to the invention may be implemented on a computer as a computer implemented method, or in dedicated hardware, or in a combination of both. Executable code for a method according to the invention may be stored on a computer program product. Examples of computer program products include memory devices, optical storage devices, integrated circuits, servers, online software, etc. Preferably, the computer program product comprises non-transitory program code stored on a computer readable medium for performing a method according to the invention when said program product is executed on a computer.
In a preferred embodiment, the computer program comprises computer program code adapted to perform all the steps of a method according to the invention when the computer program is run on a computer. Preferably, the computer program is embodied on a computer readable medium.
Another aspect of the invention provides a method of making the computer program available for downloading. This aspect is used when the computer program is uploaded into, e.g., Apple's App Store, Google's Play Store, or Microsoft's Windows Store, and when the computer program is available for downloading from such a store.
BRIEF DESCRIPTION OF THE DRAWINGS
Further details, aspects, and embodiments of the invention will be described, by way of example only, with reference to the drawings. Elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. In the Figures, elements which correspond to elements already described may have the same reference numerals. In the drawings,
FIG. 1 schematically shows an example of an embodiment of a key agreement network,
FIG. 2 schematically shows an example of an embodiment of an electronic key exchange method,
FIG. 3 a schematically shows a computer readable medium having a writable part comprising a computer program according to an embodiment,
FIG. 3 b schematically shows a representation of a processor system according to an embodiment,
FIG. 4 a schematically shows an example of an embodiment of a public key decryption node,
FIG. 4 b schematically shows an example of an embodiment of a public key encryption node.
LIST OF REFERENCE NUMERALS IN FIG. 1 AND FIG. 3
100 a key agreement network
110 a network node of initiator type
120 a communication interface
130 a shared matrix unit
131 a difficulty parameter and a structure parameter
140 a private key matrix unit
150 a public key matrix unit
160 a shared key unit
162 a raw key
164 reconciliation data (h)
166 a shared key
210 a network node of responder type
220 a communication interface
230 a shared matrix unit
240 a private key matrix unit
250 a public key matrix unit
260 a shared key unit
262 a raw key
264 reconciliation data (h)
266 a shared key
1000 a computer readable medium
1010 a writable part
1020 a computer program
1110 integrated circuit(s)
1120 a processing unit
1122 a memory
1124 a dedicated integrated circuit
1126 a communication element
1130 an interconnect
1140 a processor system
DETAILED DESCRIPTION OF THE EMBODIMENTS
While this invention is susceptible of embodiment in many different forms, there are shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described. In the following, for the sake of understanding, elements of embodiments are described in operation. However, it will be apparent that the respective elements are arranged to perform the functions being described as performed by them. Further, the invention is not limited to the embodiments, and the invention lies in each and every novel feature or combination of features described herein or recited in mutually different dependent claims.
<
CROSS-REFERENCE TO PRIOR APPLICATIONS
This application is the U.S. National Phase application under 35 U.S.C. § 371 of International Application No. PCT/EP2018/077639, filed on Oct. 10, 2018, which claims the benefit of EP Patent Application No. EP 18165330.4, filed on Mar. 30, 2018 and EP Patent Application No. EP 17196812.6, filed on Oct. 17, 2017. These applications are hereby incorporated by reference herein.
FIELD OF THE INVENTION
The invention relates to a network node configured for a cryptographic operation, a cryptographic operation method, and a computer readable medium.
BACKGROUND OF THE INVENTION
In cryptography, a key-agreement protocol is a protocol whereby two or more parties that may not yet share a common key can agree on such a key. Preferably, both parties can influence the outcome so that neither party can force the choice of key. An attacker who eavesdrops on all communication between the two parties should learn nothing about the key. Yet, while the attacker who sees the same communication learns nothing or little, the parties themselves can derive a shared key. Key agreement protocols are useful, e.g., to secure communication, e.g., to encrypt and/or authenticate messages between the parties.
In order to facilitate secure communication among parties, key agreement protocols are sometimes further subdivided into cryptographic key-exchange (KEX) and cryptographic key-encapsulation (KEM) schemes.
KEX schemes may involve the exchange of public-keys by each party, that are then independently used by the other party along with their own secret-key to calculate the common shared secret. A well-known example of such a KEX scheme is the Diffie-Hellman key-exchange, whose security is based on solving the discrete logarithm problem. An interesting feature of some KEX schemes is that the actual final, shared secret is never exchanged between the parties, not even in encrypted form, but is calculated independently by the two parties at each end. This results in a desirable feature known as forward-secrecy, which ensures that even the compromise of a party's long-term secret-key by an attacker in the future would not compromise the secrecy of encrypted message exchanged in the past.
KEM schemes may establish a shared secret between two entities or parties using asymmetric cryptography by one party, usually the initiator of the communication, to encrypt or encapsulate (using the other party's public-key) and transmit a shared secret to the other party, known as the responder, who can then decrypt or decapsulate it (using her secret-key) and then use it for securely communicating with the initiator party. Such KEM schemes may only achieve forward-secrecy if it is ephemeral. Otherwise, any attacker that compromises a party's secret-key for a past session and has recorded all messages exchanged between the parties in that session can recover the shared secret for that particular session.
Due to increasing security needs in the Internet of Things, key-exchange schemes need to also achieve high efficiency (i.e., minimal amount of communication or bandwidth requirements) while also remaining secure, against classical as well as quantum-capable adversaries.
Recent advances indicate that quantum-computers may be feasible in a few years. Perhaps as soon as within some 5-10 years. As soon as a quantum-computer is available, most existing public-key cryptographic schemes will become unsecure since the underlying problems, on which they are based, can efficiently be solved with a quantum computer. Therefore, it is very important to design quantum-resistant public-key algorithms, i.e., public-key algorithms that cannot be broken by means of a quantum-computer.
There are several classes of quantum-resistant algorithms: lattice-based, code-based, isogeny-based, etc. In this document, we deal with quantum-resistant algorithms based on lattices. Lattice based cryptographic systems are an active area of research in which many different types of systems have been proposed. For example, the lattice may be defined in terms of a matrix of numbers, e.g., elements of some finite field, or using a polynomial, etc. The type of cryptographic operation can also vary. For example, lattice based cryptography is available for: Key encapsulation (KEM), Key exchange (KEX), Public key encryption (PKE), digital signatures, etc. Examples of those schemes are:
LWE-based KEX such as Frodo RLWE-based KEX and CPA-KEM Newhope and NewHopeSimple. Module-lattice-based CPA-PKE, CPA-KEM and CCA-KEM as Kyber LWR-based KEX as spKEX Each of the above schemes implements a cryptographic protocol (e.g., a KEX, a KEM, or PKE) relying on a single underlying problem, e.g., either Learning-with-errors (LWE), or Learning-with-rounding (LWR), or module-lattices with modules, e.g., RLWE for a fixed ring, or LWR. For example: NewHope only relies on RLWE, Kyber only relies on combining k=3 modules, each module being a polynomial in Zq[x]/x{circumflex over (â)}256+1, spKEX only relies on LWR, Frodo only relies on LWE. The R in schemes such as RLWE refers to âringâ, or polynomial type implementations.
This poses several problems. First of all, implementing each of these systems would be a large investment. Not only would each of the schemes have to be coded, they would also each have to be debugged, to ensure that they do not contain critical bugs that could impair their security. On the other hand, not implementing all schemes, or at least the majority also implies certain risks. If one of the above problems is broken, e.g., RLWE or Module lattice, then the corresponding schemes are fully broken. It is desirable that there is some upgrade path, so that in case of a break, one can change from one type of scheme to another.
REFERENCES
[1] âDevice and method sharing a matrix for use in a cryptographic protocolâ, European filing op 6 Mar. 2017, application Ser. No. 17/159,296.7.
[2] Ludo Tolhuizen, Ronald Rietman and Oscar Garcia-Morchon, âImproved key reconciliation methodâ, Cryptology ePrint Archive, Report 2017/295, https://eprint.iacr.org/2017/295
[3](Frodo): J. Bos et al, âFrodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWEâ, Cryptology ePrint Archive, Report 2016/659, https://eprint.iacr.org/2016/659
[4] (New Hope): E. Alkim et al, âPost-quantum key exchangeâa new hopeâ, Cryptology ePrint Archive, Report 2015/192, https://eprint.iacr.org/2015/1092
[5] (New Hope Simple): E. Alim et al, âNewHope without reconciliationâ, Cryptology ePrint Archive, Report 2016/1157, https://eprint.iacr.org/2016/1157
[6] (Kyber): J. Bos et al, âCRYSTALS-Kyber: a CCA-secure module-lattice-based KEMâ, Cryptology ePrint Archive, Report 2017/634, https://eprint.iacr.org/2017/634
[7] (spKEX): S. Bhattacharya et al, âspKEX: an optimized lattice-based key exchangeâ, Cryptology ePrint Archive, Report 2017/709, https://eprint.iacr.org/2017/709
Each one of references [1] to [7] is included herein by reference.
SUMMARY OF THE INVENTION
The inventors realized that it is possible to define a single scheme which parametrizes large classes of lattice based cryptography. Taking only a few input parameters, which change the nature of the underlying cryptography. For example, a cryptographic device as defined in the claims may receive a difficulty parameter (d), and a structure parameter (n) which together suffice to specify the type of cryptography that is used. Both the difficulty parameter (d), and a structure parameter (n) are positive integers. By increasing the difficulty parameter, the structure of the problem stays the same, but larger, and thus harder instantiations are used. A difficulty parameter is sometimes referred to as a security parameter. In embodiment, the difficulty parameter is related to the dimension of the underlying lattice. A larger value of the difficulty parameter leads to a higher dimension of the underlying lattice, and thus to a harder problem for an attacker to solve. The structure parameter is related to the amount of algebraic structure in the system. A higher value of the structure parameter implies more algebraic structure. It is conjectured that higher values of the structure parameter may be easier to attack, since the lattice has more regularity. For example, in case of advancing research finding an incrementally better way to solve lattice problems, then a user may respond by increasing the difficulty parameter. On the other hand, if advancing research find a radically better way to solve a particular type of lattice problem, then the user may respond with decreasing the structure parameter.
For example, in an embodiment a scheme is defined that can efficiently instantiate multiple underlying problems, namely RLWE, RLWR, module RLWE, module RLWR, and LWE and LWR. This does not mean that the scheme relies on two different specifications, one for Problem 1 and another for Problem 2, but that the same algorithm can be used for instantiate both problems, the only difference being the input parameters. Advantages include:
Coverage of many potential applications with a same scheme.
Minimization of implementation cost
Reduction of code size.
Preparation for a potential transition scenario in which relying on a âweakerâ problem is no longer secure and new algorithms relying on a âstrongerâ problem is required.
The cryptographic device is an electronic device. For example, the cryptographic device may be a mobile electronic device, e.g., a mobile phone. For example, the cryptographic device may be set-top box, smart-card, computer, etc. The method of performing a cryptographic operation described herein may be applied in a wide range of practical applications. Such practical applications include financial applications, confidential or authenticated communication, etc.
A method according to the invention may be implemented on a computer as a computer implemented method, or in dedicated hardware, or in a combination of both. Executable code for a method according to the invention may be stored on a computer program product. Examples of computer program products include memory devices, optical storage devices, integrated circuits, servers, online software, etc. Preferably, the computer program product comprises non-transitory program code stored on a computer readable medium for performing a method according to the invention when said program product is executed on a computer.
In a preferred embodiment, the computer program comprises computer program code adapted to perform all the steps of a method according to the invention when the computer program is run on a computer. Preferably, the computer program is embodied on a computer readable medium.
Another aspect of the invention provides a method of making the computer program available for downloading. This aspect is used when the computer program is uploaded into, e.g., Apple's App Store, Google's Play Store, or Microsoft's Windows Store, and when the computer program is available for downloading from such a store.
BRIEF DESCRIPTION OF THE DRAWINGS
Further details, aspects, and embodiments of the invention will be described, by way of example only, with reference to the drawings. Elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. In the Figures, elements which correspond to elements already described may have the same reference numerals. In the drawings,
FIG. 1 schematically shows an example of an embodiment of a key agreement network,
FIG. 2 schematically shows an example of an embodiment of an electronic key exchange method,
FIG. 3 a schematically shows a computer readable medium having a writable part comprising a computer program according to an embodiment,
FIG. 3 b schematically shows a representation of a processor system according to an embodiment,
FIG. 4 a schematically shows an example of an embodiment of a public key decryption node,
FIG. 4 b schematically shows an example of an embodiment of a public key encryption node.
LIST OF REFERENCE NUMERALS IN FIG. 1 AND FIG. 3
100 a key agreement network
110 a network node of initiator type
120 a communication interface
130 a shared matrix unit
131 a difficulty parameter and a structure parameter
140 a private key matrix unit
150 a public key matrix unit
160 a shared key unit
162 a raw key
164 reconciliation data (h)
166 a shared key
210 a network node of responder type
220 a communication interface
230 a shared matrix unit
240 a private key matrix unit
250 a public key matrix unit
260 a shared key unit
262 a raw key
264 reconciliation data (h)
266 a shared key
1000 a computer readable medium
1010 a writable part
1020 a computer program
1110 integrated circuit(s)
1120 a processing unit
1122 a memory
1124 a dedicated integrated circuit
1126 a communication element
1130 an interconnect
1140 a processor system
DETAILED DESCRIPTION OF THE EMBODIMENTS
While this invention is susceptible of embodiment in many different forms, there are shown in the drawings and will herein be described in detail one or more specific embodiments, with the understanding that the present disclosure is to be considered as exemplary of the principles of the invention and not intended to limit the invention to the specific embodiments shown and described. In the following, for the sake of understanding, elements of embodiments are described in operation. However, it will be apparent that the respective elements are arranged to perform the functions being described as performed by them. Further, the invention is not limited to the embodiments, and the invention lies in each and every novel feature or combination of features described herein or recited in mutually different dependent claims.
Recall, that there are several schemes based on lattices for the design of a key exchange (KEX) protocol, a key encapsulation mechanism (KEM; sometimes also referred to as a key encapsulation method), public-key encryption (PKE), digital signatures, etc. Examples of those schemes are:
Frodo that is a KEX based on the Learning with Errors (LWE) problem.
NewHope that is a KEX based on the Ring Learning with Errors (RLWE) problem.
NewHopeSimple that is a KEM designed for chosen plaintext attack (CPA) based on RLWE.
Kyber that is a CPA-KEM and CCA-KEM based on the module LWE problem.
spKEX that is a KEX based on the Learning with Rounding (LWR) problem.
Each of the above schemes implements a cryptographic protocol (e.g., a KEX, a KEM, PKE, digital signature) relying on a single underlying lattice problem: either LWE, or RLWE, or module-LWE for a fixed ring, or LWR.
NewHope and NewHopeSimple only rely on RLWE using ring
Z
q
â¡
[
x
]
x
1
â¢
0
â¢
2
â¢
4
+
1
Kyber only relies on combining k modules, each module being polynomials in
Z
q
â¡
[
x
]
x
2
â¢
5
â¢
6
+
1
spKEX only relies on LWR
Frodo only relies on LWE
Although all the problems above are related, some of them are considered riskier in that they rely on special structures. On the other hand, the usage of a ring structure allows for smaller messages. Even though at present attacks employing such structures are unknown, such attacks might become known in future. All schemes based on those specific problems (e.g., RLWE or module LWE) would then be broken. There is thus a need for a fallback position. Thus, multiple schemes need to be implemented and tested, some based on more risky problems yet with better performance properties and some based on well-understood problems yet with a less good performance.
The inventors realized that the above lattice problems are related, and found a scheme that can instantiate all such problems, including: RLWE, RLWR, moduleLWE, moduleLWR, and LWE and LWR. Below several examples are described of a cryptographic in which different lattices are created based on a difficulty parameter d, and a structure parameter n.
By changing parameters in this scheme, we can, thus, instantiate protocols (KEX, KEM, PKE, etc.) based on different underlying problems and exhibiting different performance properties.
This scheme can be applied to multiple applications with different security/performance demands. For instance, top-secret documents can be encrypted by using the scheme settings for LWE while key agreement over a resource-constrained wireless communication can be based on Ring LWR parameters. The scheme has additional advantages: first, it reduces the of code size so that less memory is required. Second, effort for code review is minimized since a single algorithm needs to be reviewed and verified. Finally, such a scheme prepares for a potential transition scenario in which relying on a âweakerâ problem (e.g. RLWE) is no longer secure and new algorithms relying on a âstrongerâ problem (e.g., based on LWE) are required. The scheme does not rely on two different specifications, one for Problem 1 and another for Problem 2, etc., but that the same algorithm is used to instantiate different problems, the only difference being the input parameters.
The core invention uses a lattice problem of dimension dâwhere d is an input parameter. The lattice dimension can be the one corresponding to RLWE, RLWR, Module-LWE, Module-LWR, LWE, LWR. The scheme relies on a matrix containing kxk entries, where each entry is an element in Zq[x]/f[x] where f[x] is a reduction polynomial of degree n and n is an input parameter. k is defined to be d/n and it is not an input parameter, in embodiments it is assumed that d is a multiple of n.
Thus, given a fixed lattice dimension d and the degree of the reduction polynomial n, we can obtain the number of entries (k 2 ) of the matrix. Note that this is a key difference with module lattices. For example, in such lattices some authors optimize the ring operations in a polynomial ring (namely, Æ(x)=x 256 +1) and they use the number of modules to âincreaseâ the lattice dimension as d=256*k. This scheme can only be instantiated as module RLWE or RLWE that is too small for security purposes.
If n=1, then this represents a matrix for LWE or LWR.
If n=d, then this represents a matrix for RLWE or RLWR.
If 1<n<d, then this represents a matrix for module-LWE or module-LWR.
Without loss of generality, we note that in the following sections we often focus on two cases only, namely n=1 and n=d.
KEX based on LWR and NTRU-RING LWR
In the following, we will use the NTRU ring to illustrate our embodiments. In practice, other rings can be used as well such as (prime) cyclotomic polynomials taking q to be a prime ensuring that n=1 (mod p). Alternatively, we can also take (prime) cyclotomic polynomials with q being a power of two. An additional restriction is that the (prime) cyclotomic polynomial is irreducible modulo 2.
The NTRU ring is Æ(x)=x n â1 where n is a prime number. Then for a given lattice dimension problem d, we can instantiate the systemâfor instanceâwith n=d or n=1. If n=d, then we have a NTRU-RING LWR and if n=1, then we have a LWR scheme. We can also take an input parameter d>n and d being a multiple of prime n such that we have a module-LWR using NTRU-Ring.
TABLE 1
high level KEX protocol description. Note that round(vector,
p, q) indicates performing rounding using modules p and
q. Note that we ignore details on how key reconciliation
is done since they are not fundamental for this description.
The further information below contains PKE, CPA-KEM and
CCA-KEM protocols including all required details.
Initiator
Responder
Input structure parameter n
and difficulty parameter d
where n + 1 is prime and n
is a divisor of d
Create shared matrix A with
d/n à d/n entries in Z [x]/f[x]
Create secret s containing
d/n entries in Z[x]/f(x)
Create public key b = round
(A s, p, q) with d/n elements
in Zp[x]/f(x), where A s is
the product of the matrix A
and secret vector s, computed
modulo f(x) and modulo q
Send (b, A)
Create secret r containing
d/n elements in Z[x]/f(x)
Create public key matrix
u = round (r{circumflex over (â)}t A, p, q)
with d/n entries in Zp[x]/
f(x) where r{circumflex over (â)}t A is the
matrix product of the
transposed secret vector
r and shared matrix A,
computed modulo f(x) and
modulo q
Compute raw key rkr =
(r{circumflex over (â)}t b) (mod p) containing
d/n entries in Zp[x]/f(x),
where r{circumflex over (â)}t b is the matrix
product of the transposed
secret vector r and matrix
b, computed modulo f(x)
and modulo p
Compute reconciliation
data (h) from rkr
Send (u, h)
Compute raw key rki = u s
(mod p) containing d/n
elements in Zp[x]/f(x),
where u s is the product of
the public key u and secret
vector s, computed modulo f(x)
and modulo p
Compute final key from h and
rki.
From the above, we can see that depending on the choice of n, the underlying problem is RLWR (if n=d) or LWR (n=1). In both cases, the underlying lattice problem has dimension d. Note that the state of the art would have two different implementations of the above algorithm, namely:
TABLE 2
Note that we ignore rounding required in LWR when the
public keys b and u are computed since it is not essential
for the description. We also ignore details on how key
reconciliation may be done, see the references.
Initiator
Responder
LWR-based KEX (note that some operations
are missing to illustrate the protocol)
Create A with d à d
elements in Z
Create secret s, an
integer vector of
length d (Z{circumflex over (â)}d)
Create public-key
b = round (As, p, q)
in Z_p{circumflex over (â)}d where A s is
the product of matrix
A and vector s,
computed modulo q
Send (b, A)
Create secret r in Z{circumflex over (â)}d
Create public-key u =
round (r{circumflex over (â)}t A, p, q) in
Z_p{circumflex over (â)}d where r{circumflex over (â)}t A is
computed modulo q.
Compute raw key rkr =
(r{circumflex over (â)}t b) (mod p) in Z_p),
where r{circumflex over (â)}t b is the
matrix product of the
transposed secret
vector r and matrix b,
computed modulo p.
Computere conciliation
data (h) from rkr
Send (u, h)
Compute raw key rki =
(u s) (mod p)
Compute final key from
h and rki, where u s is
the product of the
public key u and
secret vector s,
computed modulo p.
RLWR-based KEX (note that some operations
are missing to illustrate the protocol)
Create a in Zq[x]/f(x)
Create secret s in Z[x]/f(x)
Create public-key b =
round (a*s, p, q) in
Zp[x]/f(x) where * is
polynomial multiplication,
computed modulo f and
modulo q
Send (b, a)
Create secret r in Z[x]/f(x)
Create public-key u = round
(a*r, p, q) in Zp[x]/f(x)
where a*r is computed modulo
f and modulo q.
Compute raw key rkr = b*r
in Zp[x]/f(x), where * is
polynomial multiplication,
computed modulo f and
modulo p.
Compute reconciliation data
(h) from rkr
Send (u, h)
Compute raw key rki = u*s
in Zp[x]/f(x), where *
means polynomial
multiplication, computed
modulo f and modulo p
Compute final key from h
and rki.
Note that: rki, and rkr are the raw keys of the initiator and responder respectively.
As described in the background and problem statement, current schemes in Table 2 rely on a single problem and thus are optimized with slightly different parameters and algorithms. For instance, RLWE problems usually rely on ring Zq[x]/x{circumflex over (â)}n+1 where n is a power of two and q is a prime numbe
CLAIMS
Claims ( 21 )
The invention claimed is:
1. A first network node comprising:
a communication interface circuit, wherein the communication interface circuit is arranged to communicate with a second network node; and
a processor circuit,
wherein the processor circuit is arranged to receive a difficulty parameter (d), and a structure parameter (n),
wherein the processor circuit is arranged to obtain a shared matrix (A),
wherein the shared matrix (A) is shared with the second network node through the communication interface circuit,
wherein the shared matrix (A) is a square matrix of dimension (k),
wherein dimension (k) is equal to the difficulty parameter (d) divided by the structure parameter (n),
wherein the shared matrix (A) comprises a plurality of shared matrix entries,
wherein at least a portion of the shared matrix entries are integer polynomials of degree less than the structure parameter (n),
wherein coefficients of the polynomials are selected modulo a first modulus (q),
wherein the processor circuit is arranged to generate a private key matrix (S I ),
wherein the private key matrix (S I ) comprises a plurality of private key entries,
wherein at least a portion of the private key entries are integer polynomial of degree less than the structure parameter (n),
wherein the processor circuit is arranged to generate a public key matrix (P I ) of the first network node,
wherein the generation of the public key matrix (P I ) comprises computing a matrix product between the shared matrix (A) and the private key matrix (S I ) modulo the first modulus (q) and modulo a reduction polynomial (f) with degree equal to the structure parameter (n), obtaining a matrix product,
wherein the matrix product comprises a plurality of matrix product entries,
wherein the processor circuit is arranged to add noise to at least a portion of the matrix product entries, and
wherein the processor circuit is arranged to send the public key matrix (P I ) of the first network node to the second network node.
2. The first network node as in claim 1 ,
wherein the processor circuit is arranged to receive a public key matrix (P R ) of the second network node,
wherein the processor circuit is arranged to compute a raw key as a matrix product between the received public key matrix (P R ) of the second node and the private key matrix (S I ) of the first network node,
wherein the first network node is arranged to receive reconciliation data (h) of the second network node,
wherein the processor circuit is arranged to compute a shared key or message by applying a reconciliation function (rec) to the received reconciliation data and the raw key.
3. The first network node as in claim 2 ,
wherein the reconciliation data is obtained from the raw key and from the shared key or message.
4. The first network node as in claim 1 , wherein the cryptographic operation is selected from the group consisting of a key exchange protocol, a key encapsulation mechanism, public-key encryption, a digital signature.
5. The first network node as in claim 1 , wherein the processor circuit is configured to receive a selector, selecting a cryptographic operation from multiple different cryptographic operations.
6. The first network node as in claim 1 , wherein the reduction polynomial is x n +1 or
x
n
-
1
x
-
1
.
7. The first network node as in claim 1 ,
wherein the first network node is configured to receive different difficulty parameters (d), and/or different structure parameters (n),
wherein the first network node is configured to call a common matrix multiplication part for different values of the structure parameter (n) and/or difficulty parameter (d).
8. The first network node as in claim 1 ,
wherein the structure parameter is an integer,
wherein the integer is at least 1, and at most the difficulty parameter (d), and/or
wherein the structure parameter is equal to 1 or to the difficulty parameter (d),
wherein the structure parameter plus one is restricted to be a prime number,
wherein the first modulus is a prime number,
wherein the structure parameter plus one divides the first modulus minus one, and/or
wherein the structure parameter plus one is restricted to be a prime number,
wherein the first modulus is a power of two,
wherein the reduction polynomial is irreducible modulo two.
9. The first network node as in claim 1 ,
wherein the processor circuit is configured to compute an expanded shared matrix for shared matrix (A), by replacing at least a portion of the polynomial entries of degree larger than 0, with a circulant matrix,
wherein the expanded shared matrix having a number of columns and rows equal to the difficulty parameter (d).
10. The first network node as in claim 1 ,
wherein the cryptographic operation is public key encryption or public key generation,
wherein the public key comprises the public key matrix (P I ) of the first network node and the shared matrix (A) or a seed from which it is obtained, or the public key matrix (P R ) of the second network node and the shared matrix (A) or a seed from which it is obtained
wherein the private key comprises the private key matrix (S I ) or.
11. The first network node as in claim 1 ,
wherein adding noise to at least a portion of the matrix product entries comprises multiplying the unscaled entry with the second modulus, dividing by the first modulus, rounding to an integer, and taking the rounded entry modulo the second modulus, computing a raw key as a matrix product between the received public key of the second node,
wherein the private key matrix (S I ) of the first network node is modulo the second modulus (p).
12. The first network node as in claim 1 ,
wherein coefficients of elements in the private key matrix (S I ) are bounded in absolute value by one,
wherein columns and/or rows have a fixed total number of nonzero coefficients.
13. The first network node as in claim 1 , wherein the private key matrix (S I ) is chosen uniformly random from candidate private key matrices.
14. The first network node as in claim 1 , wherein the first network node is arranged to obtain a different shared matrix (A) and/or generate a different private key matrix for each new cryptographic operation.
15. The first network node as in claim 1 ,
wherein the first network node is arranged to obtain the shared matrix (A) by generating the matrix (A) from output of a deterministic pseudo random number generator seeded by a seed,
wherein the shared matrix (A) is shared with the second network node by sending the random seed through the communication interface circuit.
16. A first network node comprising
a communication interface circuit, wherein the communication interface circuit is arranged to communicate with a second network node; and
a processor circuit,
wherein the processor circuit is arranged to receive a difficulty parameter (d), and a structure parameter (n),
wherein the processor circuit is arranged to obtain a shared matrix (A),
wherein the shared matrix (A) is shared with the second network node through the communication interface circuit,
wherein the shared matrix (A) is a square matrix of dimension (k),
wherein dimension (k) is equal to the difficulty parameter (d) divided by the structure parameter (n),
wherein at least a portion of the shared matrix entries are integer polynomial of degree less than the structure parameter (n),
wherein coefficients of the polynomials preferably is selected modulo a first modulus (q),
wherein the processor circuit is arranged to generate a private matrix (S I),
wherein the private key matrix (S I) comprises a plurality of private key entries,
wherein at least a portion of the private matrix entries are integer polynomial of degree less than the structure parameter (n),
wherein at least a portion of the private matrix entries generate a first ciphertext part (P I) by
wherein the generation of the first ciphertext part (P I) comprises computing a matrix product between the shared matrix (A) and the private matrix (S I) modulo the first modulus (q) and modulo a reduction polynomial (f) with degree equal to the structure parameter (n), obtaining a matrix product,
wherein the matrix product comprises a plurality of matrix product entries,
wherein the processor circuit is arranged to add noise to at least a portion of the matrix product entries,
wherein the processor circuit is arranged to receive a public key matrix (P R) of the second network node,
wherein the processor circuit is arranged to compute a raw key as a matrix product between the received public key matrix (P R) of the second node and the private matrix of the first network node,
wherein the processor circuit is arranged to compute a second ciphertext part from the raw key and from a message,
wherein the processor circuit is arranged to send the first ciphertext part and the second ciphertext part to the second network node.
17. A first network node comprising
a communication interface circuit, wherein the communication interface circuit is arranged to communicate with a second network node; and
a processor circuit,
wherein the processor circuit is arranged to receive a difficulty parameter (d) and a structure parameter (n),
wherein the processor circuit is arranged to obtain a private key matrix (S I ),
wherein the private key matrix (S I ) comprises a plurality of private key entries,
wherein at least a portion of the private matrix entries are integer polynomial of degree less than the structure parameter (n),
wherein the processor circuit is arranged to receive a first ciphertext part (P R ) and a second ciphertext part from the second network node,
wherein the first ciphertext part is generated by computing a matrix product between a shared matrix (A) and a private matrix (S I ) modulo a first modulus (q) and modulo a reduction polynomial (f) with degree equal to the structure parameter (n), obtaining a matrix product,
wherein the matrix product comprises a plurality of matrix product entries,
wherein the processor circuit is arranged to add noise to the entries in at least a portion of the matrix product entries,
wherein the shared matrix (A) is shared with the second network node through the communication interface circuit,
wherein the shared matrix (A) is a square matrix of dimension (k),
wherein dimension (k) is equal to the difficulty parameter (d) divided by the structure parameter (n),
wherein the shared matrix (A) comprises a plurality of shared matrix entries,
wherein at least a portion of the shared matrix entries are integer polynomial of degree less than the structure parameter (n),
wherein each coefficient of the polynomials are selected modulo the first modulus (q),
wherein at least a portion of the private key entries are integer polynomials of degree less than the structure parameter (n),
wherein the processor circuit is arranged to compute a raw key as a matrix product between the first ciphertext part and the private key matrix (S I ),
wherein the processor circuit is arranged to compute a message from the raw key and the second ciphertext part.
18. An cryptographic operation method comprising
arranging communication between the first network node and a second network node;
receiving a difficulty parameter (d), and a structure parameter (n);
obtaining a shared matrix (A),
wherein the shared matrix (A) is shared with the second network node through the circuit,
wherein the shared matrix (A) is a square matrix of dimension (k),
wherein dimension (k) is equal to the difficulty parameter (d) divided by the structure parameter (n),
wherein the shared matrix (A) comprises a plurality of shared matrix entries,
wherein at least a portion of the shared matrix entries are integer polynomial of degree less than the structure parameter (n),
wherein coefficients of the polynomials preferably is selected modulo a first modulus (q);
generating a private key matrix (S I ),
wherein the private key matrix (S I ) comprises a plurality of private key entries,
wherein at least a portion of the private key entries are integer polynomial of degree less than the structure parameter (n);
generating a public key matrix (P I ) of the first network node by computing a matrix product between the shared matrix (A) and the private key matrix (S I ) modulo the first modulus (q) and modulo a reduction polynomial (f) with degree equal to the structure parameter (n);
obtaining a matrix product, wherein the matrix product comprises a plurality of matrix product entries;
adding noise to at least a portion of the matrix product entries;
sending the public key matrix (P I ) of the first network node to the second network node.
19. A computer program stored on a non-transitory medium, wherein the computer program when executed on processor performs the method as claimed in claim 18 .
20. The first network node as in claim 1 ,
wherein the first network node is arranged to obtain a shared key or a message and obtain reconciliation data from the raw key,
wherein the first network node is arranged to send the reconciliation data to the second network node.
21. The first network node as in claim 2 , wherein the shared key and reconciliation data are obtained from the raw key.
US16/755,899
2017-10-17
2018-10-10
Configurable device for lattice-based cryptography
Active
2040-01-23
US11569993B2
( en )
Applications Claiming Priority (7)
Application Number
Priority Date
Filing Date
Title
EP17196812.6
2017-10-17
EP17196812
2017-10-17
EP17196812
2017-10-17
EP18165330.4
2018-03-30
EP18165330
2018-03-30
EP18165330.4A
EP3547603A1
( en )
2018-03-30
2018-03-30
Configurable device for lattice-based cryptography
PCT/EP2018/077639
WO2019076706A1
( en )
2017-10-17
2018-10-10
Configurable device for lattice-based cryptography
Related Parent Applications (1)
Application Number
Title
Priority Date
Filing Date
PCT/EP2018/077639
A-371-Of-International
WO2019076706A1
( en )
2017-10-17
2018-10-10
Configurable device for lattice-based cryptography
Related Child Applications (1)
Application Number
Title
Priority Date
Filing Date
US18/096,040
Continuation
US11991285B2
( en )
2017-10-17
2023-01-12
Configurable cryptographic device
Publications (2)
Publication Number
Publication Date
US20200259649A1
US20200259649A1 ( en )
2020-08-13
US11569993B2
true
US11569993B2 ( en )
2023-01-31
Family
ID=63834029
Family Applications (2)
Application Number
Title
Priority Date
Filing Date
US16/755,899
Active
2040-01-23
US11569993B2
( en )
2017-10-17
2018-10-10
Configurable device for lattice-based cryptography
US18/096,040
Active
US11991285B2
( en )
2017-10-17
2023-01-12
Configurable cryptographic device
Family Applications After (1)
Application Number
Title
Priority Date
Filing Date
US18/096,040
Active
US11991285B2
( en )
2017-10-17
2023-01-12
Configurable cryptographic device
Country Status (7)
Country
Link
US
( 2 )
US11569993B2
( en )
EP
( 1 )
EP3698515B1
( en )
JP
( 1 )
JP6849860B2
( en )
CN
( 1 )
CN111492616B
( en )
BR
( 1 )
BR112020007456A2
( en )
RU
( 1 )
RU2752697C1
( en )
WO
( 1 )
WO2019076706A1
( en )
Cited By (2)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20230130882A1
( en )
*
2021-10-27
2023-04-27
Samsung Sds Co., Ltd.
Method and apparatus for managing lwe instance
US20230403261A1
( en )
*
2022-06-13
2023-12-14
Avarok Corporation
Recursive cryptography protocol
Families Citing this family (23)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
WO2019157503A1
( en )
2018-02-12
2019-08-15
Massachusetts Institute Of Technology
Systems and methods for providing secure communications using a protocol engine
US11005656B2
( en )
*
2018-12-07
2021-05-11
Arris Enterprises Llc
Embedding information in elliptic curve base point
EP3903300A4
( en )
*
2019-02-19
2022-09-07
Massachusetts Institute Of Technology
Configurable lattice cryptography processor for the quantum-secure internet of things and related techniques
TWI729508B
( en )
*
2019-09-26
2021-06-01
åç«å°ç£å¤§å¸
Cloud secured storage system
US11522718B2
( en )
*
2019-11-28
2022-12-06
Crypto Lab Inc.
Methods of generating encryption key and digital signature based on lattices
WO2021107515A1
( en )
*
2019-11-28
2021-06-03
Seoul National University R&Db Foundation
Identity-based encryption method based on lattices
CN111064570B
( en )
*
2019-12-17
2023-01-31
èªå¤©ä¿¡æ¯è¡ä»½æéå ¬å¸
Shared key processing method, device, storage medium and electronic equipment
EP3843320A1
( en )
*
2019-12-24
2021-06-30
Koninklijke Philips N.V.
Public/private key system with increased security
GB2597333B
( en )
*
2020-07-20
2022-08-10
Arqit Ltd
Key exchange protocol
EP3993310A1
( en )
*
2020-10-28
2022-05-04
Koninklijke Philips N.V.
Middlebox with decapsulation
CN112511170B
( en )
*
2020-11-10
2024-04-16
å京èªç©ºèªå¤©å¤§å¦
A parallel implementation method for polynomial compression in lattice cipher
JP7609698B2
( en )
2021-04-28
2025-01-07
Kddiæ ªå¼ä¼ç¤¾
Design device, design method, and design program
US11496297B1
( en )
*
2021-06-10
2022-11-08
Pqsecure Technologies, Llc
Low footprint resource sharing hardware architecture for CRYSTALS-Dilithium and CRYSTALS-Kyber
US11569994B2
( en )
*
2021-06-24
2023-01-31
Intel Corporation
Accelerating multiple post-quantum cryptograhy key encapsulation mechanisms
US11909893B2
( en )
*
2021-06-25
2024-02-20
Entrust Corporation
Composite encryption across cryptographic algorithms
US12567946B2
( en )
2022-06-03
2026-03-03
Kioxia Corporation
Encryption device, decryption device, storage system, information processing device, encryption method, decryption method, decompression device, and decompression method
US12341889B2
( en )
*
2022-08-25
2025-06-24
Pqsecure Technologies, Llc
Computer architecture and method for performing lattice-based cryptographic primitives with resistance to side-channel attacks
KR102474891B1
( en )
*
2022-09-01
2022-12-06
(주)ë ¸ë¥´ë§
A virtual private network generating method providing the virtual private network by using key generated by post quantum cryptography algorithm and a virtual private network operating system performing the same
US20240110975A1
( en )
*
2022-09-30
2024-04-04
Intel Corporation
Secure Remote Debugging
US20240267212A1
( en )
*
2023-02-03
2024-08-08
Intel Corporation
Post-Quantum Cryptography Key Encapsulation Mechanism System
JPWO2024195416A1
( en )
2023-03-23
2024-09-26
US12229285B1
( en )
*
2023-07-28
2025-02-18
Gideon Samid
Polar lattice cryptography
WO2025053485A1
( en )
*
2023-09-05
2025-03-13
ì¼ì±ì ì 주ìíì¬
Electronic device for providing security function, and operation method thereof
Citations (6)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20120166809A1
( en )
2010-12-28
2012-06-28
Authernative, Inc.
System and method for cryptographic key exchange using matrices
CN104396184A
( en )
*
2012-04-12
2015-03-04
ä¸æ´¥æ³°
A New Cryptosystem Based on Mismatched Pairs
EP3364596A1
( en )
*
2017-02-15
2018-08-22
Koninklijke Philips N.V.
Key exchange devices and method
EP3373505A1
( en )
*
2017-03-06
2018-09-12
Koninklijke Philips N.V.
Device and method for sharing a matrix for use in a cryptographic protocol
EP3474484A1
( en )
*
2017-10-17
2019-04-24
Koninklijke Philips N.V.
Cryptographic device with updatable shared matrix
EP3889764A1
( en )
*
2020-03-31
2021-10-06
Koninklijke Philips N.V.
Parallel generation of a random matrix
Family Cites Families (10)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
CN1043961A
( en )
1989-08-21
1990-07-18
æºæ¢°çµåå·¥ä¸é¨å京æºæ¢°å·¥ä¸èªå¨åç 究æ
Magnetic control arc ion plating method
JP2007151073A
( en )
*
2005-10-25
2007-06-14
Chiba Univ
Key generator
RU2528078C2
( en )
*
2008-09-19
2014-09-10
Ðонинклейке Ð¤Ð¸Ð»Ð¸Ð¿Ñ ÐлекÑÑÐ¾Ð½Ð¸ÐºÑ Ð.Ð.
Method for secure communication in network, communication device, network and computer programme therefor
RU2452111C1
( en )
*
2010-11-17
2012-05-27
ÐÐÐ ÐнÑÑиÑÑÑ Ð¸Ð½ÑокоммÑникаÑионнÑÑ ÑÐµÑ Ð½Ð¾Ð»Ð¾Ð³Ð¸Ð¹
Method for threshold key generating for protection system based on identity data
US8634563B2
( en )
*
2010-12-17
2014-01-21
Microsoft Corporation
Attribute based encryption using lattices
JP5693206B2
( en )
*
2010-12-22
2015-04-01
ä¸è±é»æ©æ ªå¼ä¼ç¤¾
Cryptographic processing system, key generation device, encryption device, decryption device, cryptographic processing method, and cryptographic processing program
CN104854814A
( en )
*
2012-12-21
2015-08-19
ç家é£å©æµ¦æéå ¬å¸
Key sharing network device and configuration thereof
EP2962420B1
( en )
*
2013-02-28
2018-08-08
Koninklijke Philips N.V.
Network device configured to derive a shared key
CN107454975B
( en )
*
2015-04-07
2020-11-27
ä¸è±çµæºæ ªå¼ä¼ç¤¾
Encryption system and key generation device
US9673977B1
( en )
*
2016-09-15
2017-06-06
ISARA Corporation
Refreshing public parameters in lattice-based cryptographic protocols
2018
2018-10-10
BR
BR112020007456-0A
patent/BR112020007456A2/en
unknown
2018-10-10
EP
EP18785600.0A
patent/EP3698515B1/en
active
Active
2018-10-10
JP
JP2020521409A
patent/JP6849860B2/en
active
Active
2018-10-10
CN
CN201880081395.9A
patent/CN111492616B/en
active
Active
2018-10-10
WO
PCT/EP2018/077639
patent/WO2019076706A1/en
not_active
Ceased
2018-10-10
US
US16/755,899
patent/US11569993B2/en
active
Active
2018-10-10
RU
RU2020116256A
patent/RU2752697C1/en
active
2023
2023-01-12
US
US18/096,040
patent/US11991285B2/en
active
Active
Patent Citations (7)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20120166809A1
( en )
2010-12-28
2012-06-28
Authernative, Inc.
System and method for cryptographic key exchange using matrices
CN104396184A
( en )
*
2012-04-12
2015-03-04
ä¸æ´¥æ³°
A New Cryptosystem Based on Mismatched Pairs
EP3364596A1
( en )
*
2017-02-15
2018-08-22
Koninklijke Philips N.V.
Key exchange devices and method
EP3373505A1
( en )
*
2017-03-06
2018-09-12
Koninklijke Philips N.V.
Device and method for sharing a matrix for use in a cryptographic protocol
US20190386828A1
( en )
2017-03-06
2019-12-19
Koninklijke Philips N.V.
Device and method sharing a matrix for use in a cryptographic protocol
EP3474484A1
( en )
*
2017-10-17
2019-04-24
Koninklijke Philips N.V.
Cryptographic device with updatable shared matrix
EP3889764A1
( en )
*
2020-03-31
2021-10-06
Koninklijke Philips N.V.
Parallel generation of a random matrix
Non-Patent Citations (12)
* Cited by examiner, â Cited by third party
Title
E. Alim et al, " NewHope without reconciliation ", Cryptology ePrint Archive, Report (2016).
E. Alkim et al, " Post-quantum key exchangeâa new hope ", Cryptology ePrint Archive, Report (2015).
Garcia Morchon " NIST Submission Framework for Lattice-Based KEM and PKE " Nov. 30, 2017.
Hayo Baan et al: " Round2: KEM and PKE based on GLWR ", International Association for Cryptologie Research, Dec. 5, 2017.
International Search Report from PCT/EP2018/077639 dated Nov. 14, 2018.
J. Bos et al, " CrystalsâKyber: a CCA-secure module-lattice-based KEM ", Cryptology ePrint Archive, Report (2017).
J. Bos et al, " Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE ", Cryptology ePrint Archive, Report (2016).
Joppe Bos et al: " Frodo Take off the Ring . . . ", Computer and Communications Security, ACM, 2 Penn Plaza, Suite 701 New York NY 10121-0701 USA, Oct. 24, 2016 (Oct. 24, 2016-10-24), pp. 1006-1018.
Ludo Tolhuizen et al " Improved key reconciliation method ", Cryptology ePrint Archive, Report (2017).
Ludo Tolhuizen et al: " Improved key-reconciliation method ", International Association for Cryptologic Research,, vol. 2 May 2, 2017 (May 2, 2017), pp. 1-5.
Markku-Juhani 0 Saarinen: " HILA5: On Reliability, Reconciliation, and Error Correction for Ring-LWE Encryption ", IACR, International Association for Cryptologic Research vol. Sep. 24, 2017:195235 Jul. 5, 2017 (Jul. 5, 2017), pp. 1-22.
S. Bhattacharya et al, " spKEX: an optimized lattice-based key exchange ", Cryptology ePrint Archive, Report (2017).
Cited By (4)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20230130882A1
( en )
*
2021-10-27
2023-04-27
Samsung Sds Co., Ltd.
Method and apparatus for managing lwe instance
US12169572B2
( en )
*
2021-10-27
2024-12-17
Samsung Sds Co., Ltd.
Method and apparatus for managing LWE instance
US20230403261A1
( en )
*
2022-06-13
2023-12-14
Avarok Corporation
Recursive cryptography protocol
US12224993B2
( en )
*
2022-06-13
2025-02-11
Avarok Corporation
Recursive cryptography protocol
Also Published As
Publication number
Publication date
WO2019076706A1
( en )
2019-04-25
EP3698515A1
( en )
2020-08-26
EP3698515B1
( en )
2021-02-17
US20230163966A1
( en )
2023-05-25
US11991285B2
( en )
2024-05-21
JP6849860B2
( en )
2021-03-31
CN111492616A
( en )
2020-08-04
US20200259649A1
( en )
2020-08-13
JP2020537450A
( en )
2020-12-17
RU2752697C1
( en )
2021-07-30
BR112020007456A2
( en )
2020-10-27
CN111492616B
( en )
2024-04-16
Similar Documents
Publication
Publication Date
Title
US11991285B2
( en )
2024-05-21
Configurable cryptographic device
US11212099B2
( en )
2021-12-28
Cryptographic device with updatable shared matrix
CN110870250B
( en )
2022-12-13
Key agreement device and method
EP3583739B1
( en )
2020-12-02
Key exchange devices and method
JP7607599B2
( en )
2024-12-27
Authenticated Key Exchange
EP3547603A1
( en )
2019-10-02
Configurable device for lattice-based cryptography
CN112997448B
( en )
2024-12-24
Public/private key system with reduced public key size
KR20200036727A
( en )
2020-04-07
Post-quantum asymmetric key cryptosystem with one-to-many distributed key management based on prime modulo double encapsulation
CN104854814A
( en )
2015-08-19
Key sharing network device and configuration thereof
CN110249334B
( en )
2023-07-18
System and method for efficient secure communication between devices
Legal Events
Date
Code
Title
Description
2020-04-14
FEPP
Fee payment procedure
Free format text : ENTITY STATUS SET TO UNDISCOUNTED (ORIGINAL EVENT CODE: BIG.); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY
2020-04-14
STPP
Information on status: patent application and granting procedure in general
Free format text : APPLICATION UNDERGOING PREEXAM PROCESSING
2022-04-01
STPP
Information on status: patent application and granting procedure in general
Free format text : DOCKETED NEW CASE - READY FOR EXAMINATION
2022-09-28
STPP
Information on status: patent application and granting procedure in general
Free format text : NOTICE OF ALLOWANCE MAILED -- APPLICATION RECEIVED IN OFFICE OF PUBLICATIONS
2022-12-28
STPP
Information on status: patent application and granting procedure in general
Free format text : PUBLICATIONS -- ISSUE FEE PAYMENT VERIFIED
2023-01-11
STCF
Information on status: patent grant
Free format text : PATENTED CASE