ABSTRACT
Abstract
Some embodiments relate to an electronic network node (110) configured for a cryptographic operation. The network node obtains a shared matrix (A) by selecting integers, polynomials, and/or polynomial-coefficients from a shared pool, the shared pool being shared with the second network node, wherein the selecting is done according to one or more selection functions.
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/077823, filed on Oct. 12, 2018, which claims the benefit of EP Patent Application No. EP 17196926.4, 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. Cryptographic key-encapsulation (KEM) schemes use asymmetric cryptography to establish a shared secret among two parties, using a publicly known (e.g., public-key) and a secretly-owned (e.g., secret-key) value for each party.
KEX schemes involve the exchange of public-keys by each party, that is then independently used by the other party along with their own secret-key to calculate the common shared secret. A well-known example of a KEX scheme is the Diffie-Hellman key-exchange, mentioned above, 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 establish a shared secret between two entities or parties using asymmetric cryptography by one party, usually the initiator of the communication, to encrypt (using the other party's public-key) and transmit a shared secret to the other party, known as the responder, who can then decrypt it (using her secret-key) and then use it for securely communicating with the initiator party. KEM schemes can 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 (KEX), Key exchange (KEM), 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 share some common characteristics. Each of them requires a shared matrix A, that is at some point shared with another node. The shared matrix A may be filed with integers modulo a modulus q, or with polynomials modulo a modulus q and a reduction polynomial f. The inventors have realized that is advisable not to use the shared matrix too often. For example, in case of KEX protocols, a possible use-case would be to use a particular share matrix only once. However, as the size of matrix could, e.g., be 600 by 600, and the modulus q might be 14 bits, then amount of data in the shared matrix could be significant. Regardless whether the matrix is communicated or generated at both sides this is an important overhead. Especially for a server that maintains many connections, e.g., with multiple clients, this overhead could be very large. There is thus a need to replace a shared matrix without incurring a large overhead.
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,2967.
[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
A network node is proposed which implements a cryptographic operation which relies on the hardness of a lattice problem and which employs a shared matrix. As pointed out in the background, there are many such cryptographic operations. The inventors realized that overhead could be reduced by introducing a shared pool. Rather than generating the shared matrix directly, the first and second node first share a shared pool. The pool comprises multiple integers or polynomials, just as the shared matrix does, or the pool comprises multiple coefficients which may be used for polynomials. In an embodiment, the shared pool is not changed between the two nodes, and remains the same, or at least remains the same over multiple executions of the cryptographic operation. However, for each cryptographic operation a new shared matrix is constructed from the shared pool. This done by selecting functions that map elements of the shared pool to entries in the shared matrix, or that map coefficients of the shared pool to coefficient of the shared matrix. The selecting functions depend on the index in the shared pool or the index in the shared matrix, but interestingly also depend on a selection parameter. A selection parameter changes the way the entries of the shared matrix are selected from the shared pool. The inventors realized that varying selection functions requires relatively little overhead, and moreover such function can be easy to compute. For example, a selection functions may be a permutation which depends on the selection parameter which permutes the shared pool, or a part thereof and assigns it to a subset of the matrix, or to the coefficients. The matrix A can be partitioned in a number of such subsets. Each subset may be obtained from the same shared pool, or each subset may be obtained from a part of the shared pool. Yet, the parts of the shared pool that are mapped to the subsets of the shared matrix can overlap, even significantly.
As a result, the shared pool need contain significantly less data than the shared matrix. This means that fewer data needs to be kept in storage, but also that construction of the shared matrix can be significantly faster. For example, consider as a comparison a situation in which the shared matrix is generated from a seed by a (pseudo) random function. This requires a relatively large number of random function operations. However, by first generation a shared pool, which may also be done from a seed, much fewer random function applications are needed. As some of the random number function application are replaced by the selection functions, which may, e.g., be implemented with a less resource demanding permutations, the time to generate the shared matrix is reduced. This is even of advantage in cryptographic operations which do use a shared matrix but do not required that it is often replaced.
As pointed out above, there are quite a number of cryptographic operations which use a shared matrix. Some of these use polynomials, some of which use integers. The inventors realized that it is possible to describe many such schemes in a way which parametrizes large classes of lattice based cryptography. For example, such a description may use only a few input parameters, which change the nature of the underlying cryptography: 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 an 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, a cryptographic device as defined in the claims may even receive the difficulty parameter (d), and the structure parameter (n) which together suffice to specify the type of cryptography that is used. 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 is clearly not needed however, and an embodiment may select a fixed dimension of matrix, e.g., kÃk, and if polynomials are used a reduction polynomial of degree n
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 schematically shows an example of an embodiment of a shared matrix.
LIST OF REFERENCE NUMERALS IN FIGS. 1 - 2
100 a key agreement network
110 a network node of initiator type
120 a communication interface
130 a shared matrix unit
131 a shared pool
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
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/077823, filed on Oct. 12, 2018, which claims the benefit of EP Patent Application No. EP 17196926.4, 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. Cryptographic key-encapsulation (KEM) schemes use asymmetric cryptography to establish a shared secret among two parties, using a publicly known (e.g., public-key) and a secretly-owned (e.g., secret-key) value for each party.
KEX schemes involve the exchange of public-keys by each party, that is then independently used by the other party along with their own secret-key to calculate the common shared secret. A well-known example of a KEX scheme is the Diffie-Hellman key-exchange, mentioned above, 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 establish a shared secret between two entities or parties using asymmetric cryptography by one party, usually the initiator of the communication, to encrypt (using the other party's public-key) and transmit a shared secret to the other party, known as the responder, who can then decrypt it (using her secret-key) and then use it for securely communicating with the initiator party. KEM schemes can 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 (KEX), Key exchange (KEM), 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 share some common characteristics. Each of them requires a shared matrix A, that is at some point shared with another node. The shared matrix A may be filed with integers modulo a modulus q, or with polynomials modulo a modulus q and a reduction polynomial f. The inventors have realized that is advisable not to use the shared matrix too often. For example, in case of KEX protocols, a possible use-case would be to use a particular share matrix only once. However, as the size of matrix could, e.g., be 600 by 600, and the modulus q might be 14 bits, then amount of data in the shared matrix could be significant. Regardless whether the matrix is communicated or generated at both sides this is an important overhead. Especially for a server that maintains many connections, e.g., with multiple clients, this overhead could be very large. There is thus a need to replace a shared matrix without incurring a large overhead.
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,2967.
[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
A network node is proposed which implements a cryptographic operation which relies on the hardness of a lattice problem and which employs a shared matrix. As pointed out in the background, there are many such cryptographic operations. The inventors realized that overhead could be reduced by introducing a shared pool. Rather than generating the shared matrix directly, the first and second node first share a shared pool. The pool comprises multiple integers or polynomials, just as the shared matrix does, or the pool comprises multiple coefficients which may be used for polynomials. In an embodiment, the shared pool is not changed between the two nodes, and remains the same, or at least remains the same over multiple executions of the cryptographic operation. However, for each cryptographic operation a new shared matrix is constructed from the shared pool. This done by selecting functions that map elements of the shared pool to entries in the shared matrix, or that map coefficients of the shared pool to coefficient of the shared matrix. The selecting functions depend on the index in the shared pool or the index in the shared matrix, but interestingly also depend on a selection parameter. A selection parameter changes the way the entries of the shared matrix are selected from the shared pool. The inventors realized that varying selection functions requires relatively little overhead, and moreover such function can be easy to compute. For example, a selection functions may be a permutation which depends on the selection parameter which permutes the shared pool, or a part thereof and assigns it to a subset of the matrix, or to the coefficients. The matrix A can be partitioned in a number of such subsets. Each subset may be obtained from the same shared pool, or each subset may be obtained from a part of the shared pool. Yet, the parts of the shared pool that are mapped to the subsets of the shared matrix can overlap, even significantly.
As a result, the shared pool need contain significantly less data than the shared matrix. This means that fewer data needs to be kept in storage, but also that construction of the shared matrix can be significantly faster. For example, consider as a comparison a situation in which the shared matrix is generated from a seed by a (pseudo) random function. This requires a relatively large number of random function operations. However, by first generation a shared pool, which may also be done from a seed, much fewer random function applications are needed. As some of the random number function application are replaced by the selection functions, which may, e.g., be implemented with a less resource demanding permutations, the time to generate the shared matrix is reduced. This is even of advantage in cryptographic operations which do use a shared matrix but do not required that it is often replaced.
As pointed out above, there are quite a number of cryptographic operations which use a shared matrix. Some of these use polynomials, some of which use integers. The inventors realized that it is possible to describe many such schemes in a way which parametrizes large classes of lattice based cryptography. For example, such a description may use only a few input parameters, which change the nature of the underlying cryptography: 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 an 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, a cryptographic device as defined in the claims may even receive the difficulty parameter (d), and the structure parameter (n) which together suffice to specify the type of cryptography that is used. 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 is clearly not needed however, and an embodiment may select a fixed dimension of matrix, e.g., kÃk, and if polynomials are used a reduction polynomial of degree n
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 schematically shows an example of an embodiment of a shared matrix.
LIST OF REFERENCE NUMERALS IN FIGS. 1 - 2
100 a key agreement network
110 a network node of initiator type
120 a communication interface
130 a shared matrix unit
131 a shared pool
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 method (KEM), 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
1024
+
1
Kyber only relies on combining k modules, each module being polynomials in
z
q
â¡
[
x
]
x
256
+
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 kÃk 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, f(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 module 2.
The NTRU ring is f(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 n and d where n is prime
and n is a divisor of d
Create matrix A with d/n x 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 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
matrix A, computed modulo f(x) and
modulo q
Compute raw key rkr=(rAt b) (mod p)
containing d/n entries in Zp+x+/f(x),
where rAt b is the matrix product of
the transposed secret vector r and
matrix b, computed modulo f(x) and
modulo p
Compute helper 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.
LWR-based KEX (note that some
RLWR-based KEX (note that some
operations are missing to illustrate the
operations are missing to illustrate the
protocol)
protocol)
Initiator
Responder
Initiator
Responder
Create A with d x
Create a in
d elements in Z
Zq[x]/f(x)
Create secret s, an
Create secret s in
integer vector of
Z[x]/f(x)
length d (Z{circumflex over (â)}d)
Create public-key
Create public-key
b = round (a * s, p, q)
b = round (As, p, q)
in Zp[x]/f(x) where
in Z_p{circumflex over (â)}d where A
* is polynomial
s is the product of
multiplication,
matrix A and
computed modulo f
vector s, computed
and modulo q
modulo q
Send (b, a)
Send (b, A)
Create secret r in
Create secret r in
Z[x]/f(x)
Z{circumflex over (â)}d
Create public-key
Create public-key
u = round (a * r, p, q)
u = round (r{circumflex over (â)}t A, p,
in Zp[x]/f(x) where
q) in Z_p{circumflex over (â)}d where
a * r is computed
r{circumflex over (â)}t A is computed
modulo f and
modulo q.
modulo q.
Compute raw key
Compute raw key
rkr = (r{circumflex over (â)}t b) (mod p)
rkr = b * r in
in Z_p), where r{circumflex over (â)}t
Zp[x]/f(x), where *
b is the matrix
is polynomial
product of the
multiplication,
transposed secret
computed modulo f
vector r and matrix
and modulo p.
b, computed
Compute helper
modulo p,
data (h) from rkr
Compute helper
Send (u, h)
data (h) from rkr
Compute raw key
Send (u, h)
rki = u * s in
Compute raw key
Zp[x]/f(x), where *
rki = (u s) (mod p)
means polynomial
Compute final key
multiplication,
from h and rki,
computed modulo f
where u s is the
and modulo p
product of the
Compute final key
public key u and
from h and rki.
secret vector s,
computed modulo
p.
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 number so that the Number Theoretic Transform (NTT) can be used. These choices are not optimal for combining with non-ring versions since it requires q to be a prime that makes modular operations more complex when performing matrix operations.
The scheme in Table 1 is defined to work with similar parameters and routines. This is a particular reason for using the NTRU ring in this description since it relies on a q that is a power of two that is also a good choice for LWE/LWR schemes. This also allows us to use the same routine for the key reconciliation step that relies on the fact that both q and i powers of two [2]. These details are explained in detail in the further information below explaining the embodiment for CPA-PKE, CPA-KEM and CCA-KEM.
Note also that in the protocol explained in Table 1 we have references to round ( ) that is a function that performs rounding as defined in the LWR problem.
Reference Implementation (Part 1)
A reference implementation of the scheme in Table 1 would have the following routines for obtaining the public-key elements (b and u) and raw keys (rki and rkr):
Computation of Public-Keys:
Result[ ] = Computation of public-key(A[,],s[ ])
Result[ ] = 0
For (i=0 to d/n)
For (j=0 to d/n)
Result[i] = Add_elements(Result[i],
Multiply_elements[A[i,j],s[j])
C[ ]=Add_elements(A[ ],B[ ])
For(i=0 to n)
C[i]=(A[i]+B[i] (mod q))
C[ ]=Multiply_elements(A[ ],B[ ])
CLAIMS
Claims ( 24 )
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 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) comprises a plurality of shared matrix entries,
wherein at least a portion of the shared matrix entries are integers, and/or integer polynomials,
wherein obtaining the shared matrix (A) comprises:
obtaining one or more selection parameters shared with the second network node; and
selecting integers, polynomials, and/or polynomial-coefficients from a shared pool,
wherein the shared pool is shared with the second network node,
wherein the shared pool comprises a plurality of shared pool entries,
wherein the shared pool entries comprise integers and/or polynomials for use as an entry of the shared matrix (A),
wherein the selecting is done according to one or more selection functions,
wherein a selection function assigns an integer, polynomial, and/or polynomial-coefficient from the shared pool to an entry in the shared matrix (A),
wherein the particular integer, polynomial, or polynomial-coefficient assigned by a selection function is dependent on the selection parameter,
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 integers and/or integer polynomial,
wherein the processor circuit is arranged to generate a public key matrix (P I ) by computing a matrix product between the shared matrix (A) and the private key matrix (S I ) obtaining a matrix product,
wherein the matrix product has a plurality of matrix product entries,
wherein the processor circuit is arranged to add noise to the matrix product,
wherein the processor circuit is arranged to send the public key matrix of the first network node to the second network node.
2. The first electronic network node as in claim 1 ,
wherein at least a portion of the shared matrix entries are integers modulo a first modulus (q) and/or integer polynomials modulo a first modulus (q) and modulo a reduction polynomial (f),
wherein the private key entries are integers modulo the first modulus (q) and/or integer polynomials modulo the first modulus (q) and modulo the reduction polynomial (f),
wherein the private key matrix (S I ) is computed modulo the first modulus (q) and/or modulo the first modulus (q) and the reduction polynomial (f).
3. The first network node as in claim 1 , arranged to obtain a different shared matrix (A) for each new key exchange.
4. The first network node as in claim 1 ,
wherein the shared matrix (A) and shared pool comprise integers or polynomials,
wherein the selection polynomials select integers or polynomials from the shared pool,
wherein the shared pool comprises fewer shared pool entries than the shared matrix entries.
5. The first network node as in claim 1 ,
wherein the first network node is arranged to obtain the shared pool by generating a random seed and sending the random seed through the communication channel to the second node,
wherein the first network node and the second network node use the random seed to seed a deterministic pseudo random number generator,
wherein the deterministic pseudo random number generator generates the shared pool.
6. The first network node as in claim 1 ,
wherein at least a portion of the shared matrix entries and at least a portion of the shared pool are integers modulo a first modulus (q)
wherein at least a portion of the shared matrix entries are integer polynomials modulo a reduction polynomial (f) and at least a portion of the shared pool entries are integers modulo the first modulus (q),
wherein at least a portion of the shared matrix entries are integer polynomials and at least a portion of the shared pool entries are polynomials modulo the first modulus (q) and the reduction polynomial (f).
7. The first network node as in claim 1 ,
wherein at least a portion of the shared matrix entries are portioned into sets,
wherein each set a selection function maps at least part of the shared pool to the set in dependence on at least part of the selection parameter.
8. The first network node as in claim 7 ,
wherein the sets correspond to the rows or columns of the shared matrix (A), or
the sets correspond to blocks of the shared matrix (A), and/or
wherein the sets have equal size.
9. The first network node as in claim 1 ,
wherein a selection function takes as input a selection parameter and an index,
wherein the index indicates an entry or coefficient of an entry of the shared matrix (A),
wherein the selection function produces as output an index in the shared pool.
10. The first network node as in claim 1 , wherein a selection function maps a consecutive sequence of shared pool entries, to a consecutive sequence of elements in a row or column of the shared matrix (A).
11. The first network node as in claim 1 ,
wherein a selection function dependent on a selection parameter r maps shared pool entries with index r up to (r+kâ1) modulo the size of the shared pool to a row or column of the shared matrix (A),
wherein k is the dimension of the matrix.
12. The first electronic network node as in claim 1 ,
wherein the cryptographic operation is a key exchange (KEX) protocol,
wherein the processor circuit is configured to receive a public key matrix (P R ) of the second network node,
wherein the processor circuit is configured to compute a raw key as a matrix product between the received public key of the second node and the private key matrix (S I ) of the first network node,
wherein the first network node is configured to receive reconciliation data (h) of the second network node,
wherein the first network node is configured to compute a shared key by applying a reconciliation function (rec) to the received reconciliation data and the raw key, or
wherein the first network node is configured to obtain the shared key and reconciliation data from the raw key,
wherein the first network node is configured to send the reconciliation data to the second network node.
13. The first network node as in claim 1 ,
wherein at least a portion of the shared matrix entries are polynomials,
wherein the reduction polynomial (f) is x n +1, or x n â1, or
x
n
-
1
x
-
1
.
14. 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 polynomial entries of degree larger than 0, with a circulant matrix,
wherein the expanded shared matrix (A) has integers modulo the first modulus (q) as expanded shared matrix entries, and a number of columns and rows equal to the number of columns,
wherein rows of the shared matrix (A) times the degree of the reduction polynomial (f).
15. The first network node as in claim 1 ,
wherein adding noise to the matrix product comprises:
scaling at least a portion of the matrix product entries down to a second modulus (p),
wherein a scaled entry is equal to the unscaled entry multiplied with the second modulus (p), divided by the first modulus (q) and rounded to the nearest integer,
wherein the second modulus (p) is smaller than the first modulus (q),
wherein computing a raw key as a matrix product between the received public key of the second node and the private key matrix (S I ) of the first network node is modulo the second modulus.
16. The first network node as in claim 1 , wherein
the private key matrix (S I ) is chosen uniformly random from candidate private key matrices, and/or
coefficients of elements in the private key matrix are bounded in absolute value by a bound, and/or
columns and/or rows of the private key matrix (S I ) have a fixed or bounded hamming weight (h s ).
17. The first network node as in claim 1 ,
wherein the shared matrix (A) has at least one dimension equal to k,
wherein the private key of the first node has dimensions n and n ,
wherein the private key of the second node has dimensions m and n,
wherein n and m are smaller than n.
18. The first network node as in claim 1 ,
wherein the processor circuit is configured to select all integers, polynomials, and/or polynomial-coefficients in the shared matrix (A) from the shared pool, or
wherein the processor circuit is configured to select part of the integers, polynomials, and/or polynomial-coefficients in the shared matrix (A) from the shared pool, and to generate the remaining part of the shared matrix (A), or
all integers, polynomials, and/or polynomial-coefficients in the shared matrix (A) from the shared pool, and to replace part of the integers, polynomials, and/or polynomial-coefficients in the shared matrix (A) according to a substitution function.
19. The first network node as in claim 1 ,
wherein at least a portion of the shared matrix shared matrix entries comprises polynomials,
wherein at least a portion of the shared pool entries comprises integers,
wherein the selection polynomials select polynomial-coefficients from the shared pool,
wherein the shared pool comprising fewer entries than the number of entries in the shared matrix (A) times the degree of the reduction polynomial (f) minus 1.
20. The first network node as in claim 1 ,
wherein a selection function dependent on selection parameters r and s maps at least a portion of the shared pool entries with index (r+Prf(s,j)) modulo the size of the shared pool to an entry with index j of a row or column of the shared matrix (A),
wherein Prf denotes a Pseudo random function taking s as a seed and index j as input.
21. The first electronic network node as in claim 1 ,
wherein the cryptographic operation is a key exchange (KEX) protocol,
wherein the processor circuit is configured to receive a public key matrix (P R ) of the second network node,
wherein the first network node is configured to obtain the shared key and reconciliation data from the raw key,
wherein the first network node is configured to send the reconciliation data to the second network node.
22. The first network node as in claim 1 ,
wherein adding noise to the matrix product comprises:
selecting noise elements for one or more or all elements in the matrix product from a noise distribution; and
adding the noise elements to the one or more or all elements in the matrix product.
23. An electronic cryptographic operation method comprising:
arranging communication between a first network node and a second network node;
obtaining a shared matrix (A);
wherein the shared matrix is shared with the second network node through the communication interface circuit,
wherein at least a portion of the shared matrix entries are integers polynomials,
wherein obtaining the shared matrix (A) comprises:
obtaining one or more selection parameters, wherein the shared parameters are shared with the second network node; and
selecting integers, polynomials, and/or polynomial-coefficients from a shared pool,
wherein the shared pool is shared with the second network node,
wherein the shared pool comprises multiple integers and/or polynomials for use as an entry of the shared matrix (A),
wherein the selecting is done according to one or more selection functions,
wherein a selection function assigns an integer, polynomial, and/or polynomial-coefficient from the shared pool to an entry in the shared matrix (A),
wherein the particular integer, polynomial, or polynomial-coefficient assigned by a selection function is dependent on the selection parameter;
generating a private key matrix (S I ), wherein at least a portion of the private key entries in the private key matrix (S I ) are integers and/or integer polynomials; and
generating a public key matrix (P I ) by computing a matrix product between the shared matrix (A) and the private key matrix (S I ) obtaining a matrix product;
adding noise to at least a portion of the matrix product entries; and
sending the public key matrix of the first network node to the second network node.
24. A computer program stored on a non-transitory medium, wherein the computer program when executed on processor performs the method as claimed in claim 23 .
US16/756,137
2017-10-17
2018-10-12
Cryptographic device with updatable shared matrix
Active
2038-12-29
US11212099B2
( en )
Applications Claiming Priority (4)
Application Number
Priority Date
Filing Date
Title
EP17196926.4A
EP3474484A1
( en )
2017-10-17
2017-10-17
Cryptographic device with updatable shared matrix
EP17196926.4
2017-10-17
EP17196926
2017-10-17
PCT/EP2018/077823
WO2019076737A1
( en )
2017-10-17
2018-10-12
Cryptographic device with updatable shared matrix
Publications (2)
Publication Number
Publication Date
US20200304305A1
US20200304305A1 ( en )
2020-09-24
US11212099B2
true
US11212099B2 ( en )
2021-12-28
Family
ID=60138257
Family Applications (1)
Application Number
Title
Priority Date
Filing Date
US16/756,137
Active
2038-12-29
US11212099B2
( en )
2017-10-17
2018-10-12
Cryptographic device with updatable shared matrix
Country Status (8)
Country
Link
US
( 1 )
US11212099B2
( en )
EP
( 2 )
EP3474484A1
( en )
JP
( 1 )
JP7208987B2
( en )
CN
( 1 )
CN111492615B
( en )
BR
( 1 )
BR112020007373A2
( en )
MX
( 1 )
MX2020003689A
( en )
RU
( 1 )
RU2020115996A
( en )
WO
( 1 )
WO2019076737A1
( en )
Cited By (1)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20230370251A1
( en )
*
2020-10-16
2023-11-16
Nippon Telegraph And Telephone Corporation
Secure computation system, secure computation apparatus, secure computation method, and program
Families Citing this family (21)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
BR112020007456A2
( en )
*
2017-10-17
2020-10-27
Koninklijke Philips N.V.
first electronic network node, electronic cryptographic operation method and computer readable media
EP3754896A1
( en )
*
2019-06-18
2020-12-23
Koninklijke Philips N.V.
Authenticated key agreement
EP4035306A4
( en )
*
2019-09-26
2022-11-16
Visa International Service Association
NETWORK-BASED SIGNATURES PRESENTING UNIFORM SECRETS
US12143481B2
( en )
2019-09-30
2024-11-12
The Governing Council Of The University Of Toronto
Method and system for key generation
GB2587438A
( en )
*
2019-09-30
2021-03-31
Governing Council Univ Toronto
Key generation for use in secured communication
US11153080B1
( en )
*
2020-07-29
2021-10-19
John A. Nix
Network securing device data using two post-quantum cryptography key encapsulation mechanisms
KR20220055079A
( en )
*
2020-10-26
2022-05-03
ì¼ì±ìì¤ëìì¤ ì£¼ìíì¬
APPARATUS AND METHOD FOR PREVENTING SIDE CHANNEL ATTACK FOR NTRU LPRime ALGORITHM
US12301709B2
( en )
*
2020-11-24
2025-05-13
John A. Nix
Multiple post-quantum cryptography key encapsulations with authentication and forward secrecy
US12003629B2
( en )
2020-12-30
2024-06-04
John A. Nix
Secure server digital signature generation for post-quantum cryptography key encapsulations
US11632246B2
( en )
*
2020-12-30
2023-04-18
International Business Machines Corporation
Hybrid key derivation to secure data
CN112765551B
( en )
*
2021-01-21
2024-05-07
ä¸å½ç§å¦é¢éåºç»¿è²æºè½ææ¯ç 究é¢
A block parameter space optimization method for doubly reduced matrix multiplication
JP7402191B2
( en )
*
2021-03-03
2023-12-20
Kddiæ ªå¼ä¼ç¤¾
Multiplication device, multiplication method and multiplication program
CN112910933B
( en )
*
2021-05-07
2021-07-13
é¹åå®éªå®¤
Authentication method, authentication device, and verification device
EP4099609A1
( en )
*
2021-06-04
2022-12-07
Zama SAS
Computational network conversion for fully homomorphic evaluation
US12192184B2
( en )
2021-12-08
2025-01-07
John A. Nix
Secure session resumption using post-quantum cryptography
CN114462571B
( en )
*
2021-12-31
2024-12-06
ç§å¤§è®¯é£è¡ä»½æéå ¬å¸
Method for training deep learning model, data processing method and device
CN114630319A
( en )
*
2022-03-16
2022-06-14
é»æå
Power transmission and transformation monitoring data safety management system and method for smart power grid
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
US12413399B2
( en )
*
2022-10-06
2025-09-09
Nxp B.V.
Fault detection in post-quantum cyptography
JP2025542096A
( en )
2022-11-15
2025-12-25
ã¯ã©ã³ã¿ã ããªã㸠ãã¯ããã¸ã¼ãº ã¤ã³ã³ã¼ãã¬ã¤ããã
System and method for distribution of key generation data in a secure network
FR3147019A1
( en )
*
2023-03-24
2024-09-27
Stmicroelectronics International N.V.
Verifying a data
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
US20150067336A1
( en )
*
2012-04-12
2015-03-05
Jintai Ding
New Cryptographic Systems Using Pairing with Errors
WO2015184991A1
( en )
2014-06-04
2015-12-10
Jintai Ding
Improvements on cryptographic systems using pairing with errors
US9698986B1
( en )
*
2016-09-23
2017-07-04
ISARA Corporation
Generating shared secrets for lattice-based cryptographic protocols
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
US10097351B1
( en )
*
2016-09-15
2018-10-09
ISARA Corporation
Generating a lattice basis for lattice-based cryptography
Family Cites Families (8)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
JP4485175B2
( en )
2002-12-03
2010-06-16
ããã½ããã¯æ ªå¼ä¼ç¤¾
Key sharing system, shared key generating device, and shared key restoring device
EP3020157A1
( en )
*
2013-07-12
2016-05-18
Koninklijke Philips N.V.
System for sharing a cryptographic key
IN2013MU02907A
( en )
*
2013-09-06
2015-07-03
Tata Consultancy Services Ltd
CN103490901B
( en )
*
2013-09-30
2016-07-27
广ä¸åæ¹ä¿¡æ¯å®å ¨äº§ä¸åºå°æéå ¬å¸
Key based on combination key system generates and distribution method
US9223720B2
( en )
*
2013-12-13
2015-12-29
Oracle International Corporation
Systems and methods for rapidly generating suitable pairs of hash functions
US9577897B2
( en )
*
2015-02-20
2017-02-21
Adobe Systems Incorporated
Providing visualizations of event sequence data
CN105930916A
( en )
*
2016-04-07
2016-09-07
大è¿ç工大å¦
Parallel modular neural network-based byproduct gas real-time prediction method
CN106357410B
( en )
*
2016-10-10
2019-10-01
ä¸å±±å¤§å¦
A method of subliminal channel is constructed on the lattice signature of not unidirectional trapdoor
2017
2017-10-17
EP
EP17196926.4A
patent/EP3474484A1/en
not_active
Withdrawn
2018
2018-10-12
JP
JP2020521366A
patent/JP7208987B2/en
active
Active
2018-10-12
BR
BR112020007373-3A
patent/BR112020007373A2/en
not_active
IP Right Cessation
2018-10-12
US
US16/756,137
patent/US11212099B2/en
active
Active
2018-10-12
EP
EP18785618.2A
patent/EP3698513B1/en
active
Active
2018-10-12
RU
RU2020115996A
patent/RU2020115996A/en
unknown
2018-10-12
CN
CN201880081333.8A
patent/CN111492615B/en
active
Active
2018-10-12
WO
PCT/EP2018/077823
patent/WO2019076737A1/en
not_active
Ceased
2018-10-12
MX
MX2020003689A
patent/MX2020003689A/en
unknown
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
US20150067336A1
( en )
*
2012-04-12
2015-03-05
Jintai Ding
New Cryptographic Systems Using Pairing with Errors
WO2015184991A1
( en )
2014-06-04
2015-12-10
Jintai Ding
Improvements on cryptographic systems using pairing with errors
US10097351B1
( en )
*
2016-09-15
2018-10-09
ISARA Corporation
Generating a lattice basis for lattice-based cryptography
US9698986B1
( en )
*
2016-09-23
2017-07-04
ISARA Corporation
Generating shared secrets for lattice-based cryptographic protocols
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
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/077823 dated Jan. 17, 2019.
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), 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. 20170924: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 (1)
* Cited by examiner, â Cited by third party
Publication number
Priority date
Publication date
Assignee
Title
US20230370251A1
( en )
*
2020-10-16
2023-11-16
Nippon Telegraph And Telephone Corporation
Secure computation system, secure computation apparatus, secure computation method, and program
Also Published As
Publication number
Publication date
EP3698513B1
( en )
2021-12-08
MX2020003689A
( en )
2020-08-03
RU2020115996A3
( en )
2022-01-12
EP3474484A1
( en )
2019-04-24
US20200304305A1
( en )
2020-09-24
CN111492615B
( en )
2023-08-29
JP2020537191A
( en )
2020-12-17
WO2019076737A1
( en )
2019-04-25
CN111492615A
( en )
2020-08-04
JP7208987B2
( en )
2023-01-19
EP3698513A1
( en )
2020-08-26
BR112020007373A2
( en )
2020-09-29
RU2020115996A
( en )
2021-11-18
Similar Documents
Publication
Publication Date
Title
US11991285B2
( en )
2024-05-21
Configurable cryptographic device
EP3698513B1
( en )
2021-12-08
Cryptographic device with updatable shared matrix
CN110958112B
( en )
2022-06-28
Key generation method and system, encryption and decryption method, encrypted communication system
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
CN112997448B
( en )
2024-12-24
Public/private key system with reduced public key size
EP3547603A1
( en )
2019-10-02
Configurable device for lattice-based cryptography
EP3535925B1
( en )
2020-03-25
Reaching agreement on a secret value
US20080069346A1
( en )
2008-03-20
Device, System and Method for Cryptographic Key Exchange
CN110249334B
( en )
2023-07-18
System and method for efficient secure communication between devices
Partala
2017
Semantically secure symmetric encryption with error correction for distributed storage
Legal Events
Date
Code
Title
Description
2020-04-15
AS
Assignment
Owner name : KONINKLIJKE PHILIPS N.V., NETHERLANDS
Free format text : ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:GARCIA-MORCHON, OSCAR;TOLHUIZEN, LUDOVICUS MARINUS GERARDUS MARIA;REEL/FRAME:052399/0341
Effective date : 20181210
2020-04-15
FEPP
Fee payment procedure
Free format text : ENTITY STATUS SET TO UNDISCOUNTED (ORIGINAL EVENT CODE: BIG.); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY
2020-06-22
STPP
Information on status: patent application and granting procedure in general
Free format text : APPLICATION DISPATCHED FROM PREEXAM, NOT YET DOCKETED
2021-08-15
STPP
Information on status: patent application and granting procedure in general
Free format text : DOCKETED NEW CASE - READY FOR EXAMINATION
2021-09-01
STPP
Information on status: patent application and granting procedure in general
Free format text : NOTICE OF ALLOWANCE MAILED -- APPLICATION RECEIVED IN OFFICE OF PUBLICATIONS
2021-11-22
STPP
Information on status: patent application and granting procedure in general
Free format text : PUBLICATIONS -- ISSUE FEE PAYMENT RECEIVED
2021-11-30
STPP
Information on status: patent application and granting procedure in general
Free format text : PUBLICATIONS -- ISSUE FEE PAYMENT VERIFIED
2021-12-08
STCF
Information on status: patent grant
Free format text : PATENTED CASE
2025-01-14
MAFP
Maintenance fee payment
Free format text : PAYMENT OF MAINTENANCE FEE, 4TH YEAR, LARGE ENTITY (ORIGINAL EVENT CODE: M1551); ENTITY STATUS OF PATENT OWNER: LARGE ENTITY
Year of fee payment : 4