SECURE KEY AGREEMENT WITH UNTRUSTED PARTIES
20210385079 · 2021-12-09
Assignee
Inventors
Cpc classification
H04L9/0838
ELECTRICITY
H04L9/0861
ELECTRICITY
H04L9/085
ELECTRICITY
H04L9/0858
ELECTRICITY
International classification
H04L9/08
ELECTRICITY
Abstract
Traditional key generation methods in a noisy network often assume trusted devices and are thus vulnerable to many attacks including covert channels. The present invention differs from previous key generation schemes in that it presents a mechanism which allows secure key generation with untrusted devices in a noisy network with a prescribed access structure.
Claims
1. A method for secure cryptographic keys generation in the presence of untrusted units in a cryptographic system, the system comprising a first and a second cryptographic stations (A,B), where each cryptographic station comprises n raw data generation units, KGU.sup.A.sub.i, KGU.sup.B.sub.i with i=1, 2, . . . , n, where n>1, and at least one post-processing unit CLPU.sup.A CLPU.sup.B, where the method comprises: Each pair of raw data generation units, KGU.sup.A.sub.i and KGU.sup.B.sub.i, with i=1, 2, . . . , n, generating a pair of data strings which are correlated to each other and sending the generated data string by KGU.sup.A.sub.i to the at least one post-processing unit of the first cryptographic station and sending the generated data string by KGU.sup.B.sub.i to the at least one post-processing unit of the second cryptographic station; The at least one post-processing units of the first and second cryptographic station, CLPU.sup.A, CLPU.sup.B: applying a post-processing procedure to each received data string for generating a cryptographic key, K.sup.A.sub.i, K.sup.B.sub.i or an error symbol for each raw data generation unit, where the post-processing procedure includes at least one information reconciliation operation between the post-processing units of both cryptographic stations via an authenticated communication channel and a first privacy amplification procedure to extract a shorter key; concatenating the generated cryptographic keys to form a first concatenated cryptographic key K.sup.A′=[K.sup.A.sub.1, K.sup.A.sub.2, . . . , K.sup.A.sub.M] and a second concatenated cryptographic key K.sup.B′=[K.sup.B.sub.1, K.sup.B.sub.2, . . . , K.sup.B.sub.M] where M is the number of pairs of generated cryptographic keys in both cryptographic stations which are different from the error symbol; applying an additional privacy amplification procedure operation to the first concatenated cryptographic key and to the second concatenated cryptographic key to extract a first and a second secure cryptographic keys respectively, K.sup.A and K.sup.B.
2. A method for secure cryptographic keys generation in the presence of untrusted units in a cryptographic system, the system comprising a first and a second cryptographic stations (A,B), where each cryptographic station comprises at least one raw data generation unit, KGU.sup.A, KGU.sup.B respectively and more than one post-processing units CLPU.sup.A.sub.l, CLPU.sup.B.sub.l′, l=1, 2, . . . , s, l′=1, 2, . . . s′, where the method comprises: KGU.sup.A generating s data strings and sending one generated data string to each CLPU.sup.A.sub.l and KGU.sup.B generating s′ data strings which are correlated to the data strings generated by KGU.sup.A and sending one generated data string to each CLPU.sup.B.sub.l′; Each post-processing unit of the first and second cryptographic stations: applying a post-processing procedure to each received data string generating a cryptographic key or an error symbol for each received data string, where the post-processing procedure includes at least one information reconciliation operation between the post-processing units of both cryptographic stations via an authenticated communication channel and a first privacy amplification procedure to extract a shorter key; dividing the generated cryptographic keys into two or more shares and distributing them among the rest of post-processing units of the first and second cryptographic stations respectively; generating a share of a secure cryptographic key by applying an error verification procedure and an additional privacy amplification procedure operation to the received cryptographic keys shares;
3. A method for secure cryptographic keys generation in the presence of untrusted units in a cryptographic system, the system comprising a first and a second cryptographic stations (A,B), where each cryptographic station comprises at least one raw data generation unit, KGU.sup.A, KGU.sup.B and more than one post-processing units CLPU.sup.A.sub.i, CLPU.sup.B.sub.i′, i=1, 2, . . . , s, i′=1, 2 . . . s′, where the method comprises: The at least one raw data generation units in the first and second cryptographic stations generating a data string, R.sup.A, R.sup.B respectively which are correlated to each other, dividing the generated data strings into two or more shares and distributing them among the post-processing units of the first and second cryptographic stations respectively where K′.sup.A.sub.ij is the j-th share of R.sup.A received by CLPU.sup.A.sub.i and K′.sup.B.sub.i′j′ is the j′-th share of R.sup.B received by CLPU.sup.B.sub.i′; Each post-processing unit of the first and second cryptographic stations: obtaining from each received share of the data strings a key generation sub-string share K′.sup.A.sub.ij,key, K′.sup.B.sub.i′j′,key; applying a post-processing procedure to the key generation sub-strings shares generating secure cryptographic key shares, where said post-processing procedure includes at least one information reconciliation operation between the post-processing units of both cryptographic stations via an authenticated communication channel and a privacy amplification procedure to extract a shorter key.
4. The method according to claim 3, wherein the information reconciliation operation includes an error correction procedure which comprises: applying certain predefined matrices M.sub.EC to the key generation sub-strings shares obtaining data strings s.sup.A.sub.ij=M.sub.EC*K′.sup.A.sub.ij,key, s.sup.B.sub.j′=M.sub.EC*K′.sup.B.sub.i′j′,key respectively; obtaining in each post-processing unit a reconstructed data string s.sup.A, s.sup.B defined S.sup.A=s.sup.A.sub.1⊕ . . . ⊕.sup.A.sub.q and s.sup.B=s.sup.B.sub.1⊕ . . . ⊕s.sup.B.sub.q′ respectively, where s.sup.A.sub.j is obtained from s.sup.A.sub.ij by using majority voting and s.sup.B.sub.j′ is obtained from s.sup.B.sub.i′j′ by using majority voting; modifying the value of the key generation sub-strings K′.sup.A.sub.ij,key, K′.sup.B.sub.i′j′,key depending on the actual values of s.sup.A and s.sup.B; repeat the three steps of the error correction procedure until the error is below a predefined threshold; where the information reconciliation operation includes an error verification procedure which comprises: The post-processing units of the first cryptographic station randomly selecting a two-universal hash function, hash, and applying it to the key generation sub-strings shares obtained after the error correction procedure, K.sup.A.sub.ij,key, obtaining h.sup.A.sub.ij=hash(K.sup.A.sub.ij,key), and each post-processing unit of the second cryptographic station obtaining h.sup.B.sub.i′j′=hash(K.sup.B.sub.i′j′,key) and each post-processing unit sending the shares h.sup.A.sub.ij and h.sup.B.sub.i′j′ to all the post-processing units in his own cryptographic unit and to all the post-processing units in the other cryptographic unit; obtaining in each post-processing unit a reconstructed data string h.sup.A, h.sup.B respectively as h.sup.A=h.sup.A.sub.1⊕ . . . ⊕h.sup.A.sub.q and h.sup.B=h.sup.B.sub.1⊕ . . . ⊕h.sup.B.sub.q′ respectively, where h.sup.A.sub.j is obtained from h.sup.A.sub.ij by using majority voting and h.sup.B.sub.j′ is obtained from h.sup.A.sub.i′j′ by using majority voting; Each of the post-processing units checking whether or not h.sup.A=h.sup.B and if they are equal they proceed to the privacy amplification procedure, otherwise outputting an abort symbol; Where the privacy amplification procedure comprises: The post-processing units of the first cryptographic station randomly selecting a two-universal hash function hashPA, and then obtaining shares of a secure cryptographic unit as K.sup.A.sub.ij=hashPA(K.sup.A.sub.ij,key) and each post-processing unit of the second cryptographic station obtaining shares of a secure cryptographic unit as K.sup.B.sub.i′,j′=hashPA(K.sup.B.sub.i′j′,key).
5. The method according to claim 3, wherein the method further includes: Each post-processing unit of the first and second cryptographic stations, obtaining from each received share of the data strings, a parameter estimation sub-string share K′.sup.A.sub.ij,est, K′.sup.B.sub.i′j′,est and sending said parameter estimation sub-strings shares to the rest of post-processing units of the cryptographic unit.
6. A method for secure cryptographic keys generation in the presence of untrusted units in a cryptographic system, the system comprising a first and a second cryptographic stations (A,B), where each cryptographic station comprises a plurality of raw data generation units, KGU.sup.A.sub.i, KGU.sup.B.sub.i with i=1, 2, . . . , n, n>1 and a plurality of post-processing units CLPU.sup.A.sub.l, CLPU.sup.B.sub.l′, l=1, 2, . . . , s, l′=1, 2 . . . s′, where the method comprises: Each raw data generation unit in the first and second cryptographic stations generating correlated data strings, R.sup.A.sub.i, R.sup.B.sub.i with i=1, 2, . . . , n, respectively, dividing the generated data strings into two or more shares and distributing them among the post-processing units of the first and second cryptographic stations respectively, Each post-processing unit applying a post-processing procedure to each received data string share, generating a first cryptographic key shares K′.sup.A.sub.lij, K′.sup.B.sub.l′ij′ or an error symbol for each received data string share, where the post-processing procedure includes at least an information reconciliation operation between the processing units of both cryptographic stations via an authenticated communication channel and a first privacy amplification procedure, where K′.sup.A.sub.lij is the j-th share of the cryptographic key for R.sup.A.sub.i obtained by CLPU.sup.A.sub.l, and K′.sup.B.sub.l′ij′ is the j′-th share of the cryptographic key for R.sup.B.sub.i obtained by CLPU.sup.B.sub.l′; Each post-processing unit obtaining shares of a secure cryptographic key by concatenating the obtained first cryptographic key shares and applying an additional privacy amplification procedure operation to the concatenated string.
7. The method according to claim 6, further comprises: Each CLPU.sup.A.sub.l, with l=1, . . . , s obtaining bit strings K″.sup.A.sub.lij=[0.sub.1, . . . , 0.sub.i−1, K′.sup.A.sub.lij, 0.sub.i+1, . . . , 0.sub.M], where 0.sub.i, with i=1, . . . , M, represents a zero vector, and M is the number of pairs of raw generation units which generate data strings different from an error symbol and each CLPU.sup.B.sub.l′, with l′=1, . . . , s′ obtaining bit strings K″.sup.B.sub.l′ij′=[0.sub.1, . . . , 0.sub.i−1, K′.sup.B.sub.l′ij′, 0.sub.i+1, . . . , 0.sub.M], with i=1, . . . , M; Each CLPU.sup.A.sub.l, with l=1, . . . , s, randomly selecting a two-universal hash function hashPA, and then obtaining shares of a secure cryptographic key as K.sup.A.sub.lij=hashPA(K″.sup.A.sub.lij) and each CLPU.sup.B.sub.l′, with l′=1, . . . , s′ obtaining shares of a secure cryptographic key as K.sup.B.sub.l′ij′=hashPA(K″.sup.B.sub.l′ij′).
8. The method according to claim 1 wherein the pair of data strings generated by each pair of raw data generation units, KGU.sup.A.sub.i and KGU.sup.B.sub.i, i=1, 2, . . . , n, of the first and second cryptographic stations respectively, are generated using a quantum key distribution mechanism.
9. The method according to claim 2 wherein each pair of data strings generated by each pair of raw data generation units KGU.sup.A and KGU.sup.B of the first and second cryptographic stations respectively are generated using a quantum key distribution mechanism.
10. A system for secure cryptographic keys generation in the presence of untrusted units, the system comprising: a first and a second cryptographic stations (A,B), where each cryptographic station comprises n raw data generation units, KGU.sup.A.sub.i, KGU.sup.B.sub.i with i=1, 2, . . . , n, where n>1, and at least one post-processing unit CLPU.sup.A CLPU.sup.B, wherein: Each pair of raw data generation units, KGU.sup.A.sub.i and KGU.sup.B.sub.i, comprising means for generating a pair of data strings which are correlated to each other and sending the generated data string by KGU.sup.A.sub.i to the at least one post-processing unit of the first cryptographic station and sending the generated data string by KGU.sup.B.sub.i to the at least one post-processing unit of the second cryptographic station; The at least one post-processing units of the first and second cryptographic station, CLPU.sup.A, CLPU.sup.B being configured for: applying a post-processing procedure to each received data string for generating a cryptographic key, K.sup.A.sub.i, K.sup.B.sub.i or an error symbol for each raw data generation unit, where the post-processing procedure includes at least one information reconciliation operation between the post-processing units of both cryptographic stations via an authenticated communication channel and a first privacy amplification procedure to extract a shorter key; concatenating the generated cryptographic keys to form a first concatenated cryptographic key K.sup.A′=[K.sup.A.sub.1, K.sup.A.sub.2, . . . , K.sup.A.sub.M] and a second concatenated cryptographic key K.sup.B′=[K.sup.B.sub.1, K.sup.B.sub.2, . . . , K.sup.B.sub.M] where M is the number of pairs of generated cryptographic keys in both cryptographic stations which are different from the error symbol; applying an additional privacy amplification procedure operation to the first concatenated cryptographic key and to the second concatenated cryptographic key to extract a first and a second secure cryptographic keys respectively, K.sup.A and K.sup.B.
11. A system for secure cryptographic keys generation in the presence of untrusted units, the system comprising: a first and a second cryptographic stations (A,B), wherein each cryptographic station comprises at least one raw data generation unit, KGU.sup.A, KGU.sup.B respectively and more than one post-processing units CLPU.sup.A.sub.l, CLPU.sup.B.sub.l′, l=1, 2, . . . , s, l′=1, 2, . . . s′, wherein: KGU.sup.A comprising means for generating s data strings and sending one generated data string to each CLPU.sup.A.sub.l and KGU.sup.B comprising means for generating s′ data strings which are correlated to the data strings generated by KGU.sup.A and sending one generated data string to each CLPU.sup.B.sub.l′; Each post-processing unit of the first and second cryptographic station being configured for: applying a post-processing procedure to each received data string generating a cryptographic key or an error symbol for each received data string, where the post-processing procedure includes at least one information reconciliation operation between the post-processing units of both cryptographic stations via an authenticated communication channel and a first privacy amplification procedure to extract a shorter key; dividing the generated cryptographic keys into two or more shares and distributing them among the rest of post-processing units of the first and second cryptographic stations respectively; generating a share of a secure cryptographic key by applying an error verification procedure and an additional privacy amplification procedure operation to the received cryptographic keys shares;
12. A system for secure cryptographic keys generation in the presence of untrusted units, the system comprising: a first and a second cryptographic stations (A,B), wherein each cryptographic station comprises at least one raw data generation unit, KGU.sup.A, KGU.sup.B and more than one post-processing units CLPU.sup.A.sub.i, CLPU.sup.B.sub.i′, i=1, 2, . . . , s, i′=1, 2, . . . s′, where: The at least one raw data generation units in the first and second cryptographic stations generating a data string, R.sup.A, R.sup.B respectively which are correlated to each other, comprising means for dividing the generated data strings into two or more shares and distributing them among the post-processing units of the first and second cryptographic stations respectively where K′.sup.A.sub.ij is the j-th share of R.sup.A received by CLPU.sup.A.sub.i and K′.sup.B.sub.i′j′ is the j′-th share of R.sup.B received by CLPU.sup.B.sub.i′; Each post-processing unit of the first and second cryptographic station being configured for: obtaining from each received share of the data strings a key generation sub-string share K′.sup.A.sub.ij,key, K′.sup.B.sub.i′j′,key; applying a post-processing procedure to the key generation sub-strings shares generating secure cryptographic key shares, where said post-processing procedure comprises an information reconciliation operation between the processing units of both cryptographic stations via an authenticated communication channel and a privacy amplification procedure.
13. A system for secure cryptographic key generation in the presence of untrusted units, the system comprising: a first and a second cryptographic stations (A,B), where each cryptographic station comprises a plurality of raw data generation units, KGU.sup.A.sub.i, KGU.sup.B.sub.i with i=1, 2, . . . , n, n>1, and a plurality of post-processing units CLPU.sup.A.sub.l, CLPU.sup.B.sub.l′, l=1, 2, . . . , s, l′=1, 2, . . . s′, where: Each raw data generation unit in the first and second cryptographic stations comprising means for generating correlated data strings, R.sup.A.sub.i, R.sup.B.sub.i with i=1, 2, . . . , n, respectively, dividing the generated data strings into two or more shares and distributing them among the post-processing units of the first and second cryptographic stations respectively, Each post-processing unit being configured for: applying a post-processing procedure to each received data string share, generating a first cryptographic key shares K′.sup.A.sub.lij, K′.sup.B.sub.l′ij′ or an error symbol for each received data string share, where the post-processing procedure includes at least an information reconciliation operation between the processing units of both cryptographic stations via an authenticated communication channel and a first privacy amplification procedure, where K′.sup.A.sub.lij is the j-th share of the cryptographic key for R.sup.A.sub.i obtained by CLPU.sup.A.sub.l, and K′.sup.B.sub.l′ij′ is the j′-th share of the cryptographic key for R.sup.B.sub.i obtained by CLPU.sup.B.sub.l′; obtaining shares of a secure cryptographic key by concatenating the obtained first cryptographic key shares and applying an additional privacy amplification procedure operation to the concatenated string.
14. (canceled)
Description
DESCRIPTION OF FIGURES
[0047] To complete the description that is being made and with the object of assisting in a better understanding of the characteristics of the invention, in accordance with preferred example of practical embodiments thereof, accompanying said description as an integral part thereof, is a set of drawings wherein, by way of illustration and not restrictively, the following has been represented:
[0048]
[0049]
[0050]
[0051]
[0052]
[0053]
DESCRIPTION OF THE INVENTION
[0054] The invention describes methods and systems for, in general terms, generating a secure shared key between two or more cryptographic stations (an station which is able to generate cryptographic keys for example for secure communication or authentication between two electronic devices). Said shared key is generated in the presence of a noisy channel in a communications network (communicating the cryptographic stations) and possibly un-trusted components inside cryptographic station(s).
[0055] Consider a communication network allowing communication between various cryptographic stations together with any intermediary or ancillary nodes. Each cryptographic station may represent, for example, an electronic node as a secure site such as a data center, or a co-location facility, a service provider or an end user electronic communications device such as a smart phone held by an end user or for example, a mobile phone, laptop, i-pad, tablet, PC . . . or generally speaking, any other type of electronic device which may generate cryptographic keys for communication or authentication with another party. To achieve either unconditional secure communication or authentication between, for example, two cryptographic stations, traditionally called, A and B or Alice and Bob (where Alice and Bob are supposed to be the parties or users controlling each cryptographic station respectively) in the presence of an adversary or eavesdropper, Eve, it is important for Alice and Bob to share a cryptographic key, K, that is random and secret.
[0056] A cryptographic station contains both key generation unit(s) (KGU) and classical post-processing unit(s) (CLPU). Key generation units (also called raw data generation units) generate correlated raw data (also known as primary data, that is, data obtained directly from a data source) between distant parties, which is afterwards processed by the CLPU to obtain the cryptographic key. For instance, in Maurer's scheme, key generation units could be antennas that are receiving signals from a common source in a distant radio galaxy. Classical post-processing units (also called just post-processing units) can be any conventional processing devices (also called processing units or processing modules) such as for example. Central Processing Units (CPUs), Graphical Processing Units (GPUs), and Field Programmable Gate Arrays (FPGAs)) or any other electronic unit with computation capabilities. A pair of KGUs distributed between the two cryptographic stations, A and B, use some physical means to generate correlated noisy (raw) data between the cryptographic stations. Such physical means for generating correlated data could be, for example, QKD. In the case of QKD, such raw data could be either prepared or measured polarization data of single photon signals. Each single photon has a polarization. For instance, in the rectilinear basis Z, a vertically polarized photon could represent a “0” whereas a horizontally polarized photon could represent a “1”. Similarly, in the diagonal basis X, a 45-degree polarized photon could represent a “0” whereas a 135-degree polarized photon could represent a “1”. Each KGU then passes the correlated noisy raw data to classical post-processing unit(s) to be processed, obtaining cryptographic key K. While this discussion is general, for ease of illustration, we take the example of QKD. In QKD, Alice and Bob are connected by two channels, one quantum and one classical. The quantum channel is used for the transmission of quantum signals such as polarization data of single photons. Such quantum signals can be used to generate raw key material. Eve is free to tamper with the quantum channel, which can be an optical fiber or free space or other media (e.g. water). The term “classical” channel simply means a conventional communication channel that can transmit conventional information. The classical channel may be of any form including a phone line, Internet, Ethernet, the known channels of a mobile communications network (GSM, UMTS, LTE, 3G, 4G or whatever) or a WI_FI network, even a direct wire or generally speaking any communications channel of any known conventional wired or wireless communications network. The classical channel may also be in the same medium as the quantum channel, for example, through spatial, time or frequency multiplexing. The classical channel is often assumed to be authenticated using any known authentication mechanism. CLPU(s) receive the correlated noisy raw key data and may apply various processing operations to it (which includes, for example, post-selection of data, adding noise, parameter estimation, information reconciliation, typically including an error correction step together with an error verification step, and privacy amplification). These operations will be described below in more detail.
[0057] A. A Prior Art Key Distribution Method and its Insecurity
[0058]
[0059] For instance, in a known QKD protocol (standard Bennett-Brassard BB84 protocol), two distant parties, Alice and Bob, would like to establish a secure cryptographic key between them. The cryptographic station A is controlled by one party, Alice (for example, the user of a first electronic communications device where the cryptographic station A is located), whereas cryptographic station B is controlled by another party, Bob (for example, the user of a second electronic communications device where the cryptographic station B is located). Now, KGU.sup.A prepares and sends via a quantum channel to the KGU.sup.B, a sequence of photons prepared in different polarisation states, which are chosen by KGU.sup.A from two possible conjugate bases, X and Z. For each photon, KGU.sup.B selects randomly one of the two conjugate bases and performs a measurement. KGU.sup.B records the outcome of the measurement and the basis choice. Then, KGU.sup.A passes the polarization data, R.sup.A, and other relevant ancillary information such as the basis information to CLPU.sup.A and KGU.sup.B passes the polarization data, R.sup.B, and other relevant ancillary information such as the basis information to CLPU.sup.B.
[0060] Through an authenticated channel (A.C. channel), CLPU.sup.A and CLPU.sup.B broadcast their preparation and measurement bases. They discard all polarisation data sent and received in different bases and use the remaining data to generate a sifted key. To test for tampering, CLPU.sup.A and CLPU.sup.B compute the quantum bit error rate (QBER) of a randomly selected subset of data and verify that the QBER is below a certain threshold value. By applying classical post-processing protocols such as for example, information reconciliation (which typically includes an error correction step together with an error verification step) and privacy amplification, CLPU.sup.A and CLPU.sup.B generate a secure key, K.sup.A and K.sup.B, where with high probability a) K.sup.A=K.sup.B and b) K.sup.A is secure against an eavesdropper.
[0061] In such a set-up, it is commonly assumed that all the KGUs (i.e., KGU.sup.A and KGU.sup.B) and all the CLPUs (i.e., CLPU.sup.A and CLPU.sup.B) are trusted. For instance, both device-independent and device-dependent settings of QKD are included in this framework.
[0062] Standard device-dependent QKD assumes that QKD devices function correctly by, for example, preparing the correct state and performing perfect measurements in accordance with some theoretical protocols. In contrast, device-independent QKD has the advantage of allowing QKD devices to function in an arbitrary manner as long as there is no information leakage (e.g. about the final key) from cryptographic stations, A, and, B, to an eavesdropper. Unfortunately, such a prior art set-up is highly vulnerable to malicious attacks in either software and/or hardware. For example, if the eavesdropper Eve plants a memory in say, for example, KGU.sup.A, then the security of such prior art key distribution method may be compromised. This is illustrated in
[0063] Hence, the way to perform secure key distribution when some of the KGUs or CLPUs are untrusted is an important non-solved challenge to prior art key distribution schemes.
[0064] B. Scenario 1: A Key Distribution Method with Untrusted Key Generation Units Inside a Cryptographic Station.
[0065] The key goal of the invention is to achieve security of key distribution in the presence of untrusted devices. These untrusted devices could be, for example, KGUs, CLPUs, or both of them together. In this section, it is considered the case when some KGUs might be untrusted but the CLPUs are assumed to be trusted.
[0066] In this case, we consider a new key distribution protocol with multiple KGUs, as shown in
[0067] That is, in this figure, the cryptographic station A has n (where n>1) units KGU.sup.A.sub.1, KGU.sup.A.sub.2, . . . KGU.sup.A.sub.n, and the cryptographic station B has n units KGU.sup.B.sub.1, KGU.sup.B.sub.2, . . . KGU.sup.B.sub.n. As a side remark, note that low-cost KGUs exist because of the development of chip-based QKD transmitters. Our invention can leverage such devices. Note that the various KGU pairs could be purchased from different vendors. Our invention allows us to increase trust and construct a secure key generation system with components from cheap untrusted vendors.
[0068] Of course, if all KGUs are compromised, then it is impossible to prove security so it is supposed that at least one of them is not compromised (that is, there is at least one trusted KGU). It is thus useful to define the access structure or adversary structure. By adversary structure, we mean what subsets of pairs of units KGU.sup.A.sub.i and KGU.sup.B.sub.i with i=1, . . . , n, might be dishonest (untrusted) without affecting the security of the final key (a pair of units KGU.sup.A.sub.i and KGU.sup.B.sub.i is dishonest if at least one of its units is dishonest). In the definition of the adversary structure one could distinguish between dishonest devices which are passively controlled by Eve and those that are actively controlled by Eve. For example, a device passively controlled by Eve can leak its information to her, but otherwise it follows all the indications of the protocol correctly. A device actively controlled by Eve, on the other hand, can leak its information to her and, moreover, it does not have to necessarily follow the prescriptions of the protocol but its behaviour is fully governed by Eve. An example of adversary structure could be that at most 3 out of 4 pairs of units KGU.sup.A.sub.i and KGU.sup.B.sub.i might be dishonest and actively controlled by Eve. This means that at least one of the 4 pairs of units KGU.sup.A.sub.i and KGU.sup.B.sub.i is honest.
[0069] In
[0070] Each unit KGU.sup.A.sub.i in cryptographic station A sends the generated raw key, R.sup.A.sub.i, to CLPU.sup.A via the “S.C. channel i.sup.A” shown in
[0071] The CLPUs may apply various classical post-processing steps to the raw keys received. Owing to environmental disturbances and potential eavesdropping attacks by Eve, the raw key R.sup.A.sub.i generated by KGU.sup.A.sub.i might be different from the raw key R.sup.B.sub.i generated by KGU.sup.B.sub.i. Therefore, these classical post-processing steps usually should include information reconciliation and privacy amplification to ensure that the final keys generated, K.sup.A and K.sup.B, in cryptographic stations A and B are secret and probably the same. In an information reconciliation step one or more of the CLPUs in cryptographic stations A and B may first interchange error correction information, which is then used to correct their data such that K.sup.A and K.sup.B are with high probability equal. This can be done using any known procedure (see, for example, Brassard G. and Salvail, L. Secret key reconciliation by public discussion. Université de Montreal Proc. of Advances in Cryptology (Eurocrypt 93), 410-23 (1993)). Next, cryptographic stations A and B might perform an error verification step to confirm that K.sup.A and K.sup.B are indeed equal to each other with high probability. The privacy amplification step is used to guarantee that the final key, K.sup.A and K.sup.B, is indeed probably secret (i.e., Eve has only negligible information about it). For this, privacy amplification removes the partial information that Eve could have obtained about say for instance the raw keys R.sup.A.sub.i, with i=1, . . . , n. Eve might have obtained information about these raw keys by eavesdropping the quantum channels that connect the units KGU.sup.A.sub.i and KGU.sup.B.sub.i for all i, as well as by listening to the contents of the authenticated classical channel that connects CLPU.sup.A and CLPU.sup.B. Also, all dishonest pairs KGU.sup.A.sub.i and KGU.sup.B.sub.i could directly leak R.sup.A.sub.i to Eve. As mentioned earlier, privacy amplification may be done by hashing a raw key by applying a two-universal hash function (for example, by multiplying a string with a random matrix of binary entries).
[0072] In addition, the classical post-processing steps may also include, for example, post-selection of data, adding noise, parameter estimation and error verification. In each of these classical post-processing steps one or more of the CLPUs in cryptographic stations A and B can use the authenticated classical channel between them to interchange information and post-process their data. For instance, in the step of data post-selection the CLPUs divide the raw data R.sup.A.sub.i and R.sup.B.sub.i into different data sets. Just as an example, the CLPUs may divide the raw data in three main data sets. The first data set contains the raw data that will be post-processed to obtain a secure key, K.sup.A and K.sup.B; the second data set (also denoted as parameter estimation data set) contains the raw data that will be used for parameter estimation in order to determine the parameters that are needed to generate K.sup.A and K.sup.B from the data in the first data set; and the third data set contains the raw data that is discarded. For instance, in the standard Bennett-Brassard BB84 protocol Alice and Bob usually discard the raw data associated to basis mismatched events. Also, the CLPUs may add noise to the raw data by flipping some of their bits (see, for example, Renner, R., Gisin, N. and Kraus B. An information-theoretic security proof for QKD protocols. Phys. Rev. A 72, 012332 (2005)) or any other known mechanism to add noise. In the parameter estimation step, on the other hand, the CLPUs use the data from the parameter estimation data set to determine bounds on the quantities that are needed to generate a secure key. These quantities may include, for example, the QBER, the phase error rate, the number of single-photon pulses emitted by Alice that contribute to the data set that is used to generate a secure key, etc. Finally, in the error verification step the CLPUs confirm that K.sup.A and K.sup.B are equal with certain probability. An information reconciliation process may consist of many steps and error verification may be the final step in the information reconciliation process. The purpose of error verification is to confirm that the information reconciliation process is successful. For this, they could use for example a two-universal hash function to compute a hash of both K.sup.A and K.sup.B and then they could check if both hashes are equal.
[0073] Below we describe, as an example, a protocol for key distillation that achieves security against dishonest KGUs. It can be decomposed in two main conceptual steps. In particular, suppose that all the units KGU.sup.A.sub.i in cryptographic station A have sent the raw key data R.sup.A.sub.i to CLPU.sup.A, and also suppose that all the units KGU.sup.B.sub.i in cryptographic station B have sent the raw key data R.sup.B.sub.i to CLPU.sup.B. Then, in a first step, the units CLPU.sup.A and CLPU.sup.B post-process the data R.sup.A.sub.i and R.sup.B.sub.i for all i to obtain a secret key, K.sup.A.sub.i and K.sup.B.sub.i, or the abort symbol ⊥.sub.i. In the case of using QKD for raw data generation, an abort symbol may be generated when the Quantum Bit Error Rate is higher than some prescribed value (e.g. 11% in the case of Shor-Preskill proof for the Bennett-Brassard BB84 protocol). For this, CLPU.sup.A and CLPU.sup.B may use some of the classical post-processing steps described above. These classical post-processing steps may include a privacy amplification step to remove Eve's partial information about K.sup.A.sub.i and K.sup.B.sub.i due to her eavesdropping on the “Q. channel i” (see
[0074] The protocol for secure key generation may comprise the following steps (this is only a possible embodiment, and not all the cited steps are essential and mandatory in all the embodiments of the present invention):
[0075] Protocol 1: [0076] 1. Distribution of the raw data: Each KGU.sup.A.sub.i sends to CLPU.sup.A the raw key R.sup.A.sub.i or the abort symbol ⊥.sub.i. Also, each KGU.sup.B.sub.i sends to CLPU.sup.B the raw key R.sup.B.sub.i or the abort symbol ⊥.sub.i. [0077] 2. Generation of an epsilon_cor-correct key K.sup.A′ and K.sup.B′: CLPU.sup.A and CLPU.sup.B use a key post-processing protocol to generate a (epsilon_cor/M)-correct and (epsilon_sec/M)-secret key (with epsilon_cor+epsilon_sec≤epsilon), K.sup.A.sub.i and K.sup.B.sub.i, from R.sup.A.sub.i and R.sup.B.sub.i, or they generate the symbol ⊥.sub.i to indicate abort (that is, to indicate that the post-processing procedure was not success and it was not possible to generate a valid key from the raw data) for all i=1, . . . , n. Afterward, CLPU.sup.A concatenates the M keys K.sup.A.sub.i which are different from ⊥.sub.i to form K.sup.A′=[K.sup.A.sub.1, K.sup.A.sub.2, . . . , K.sup.A.sub.M]. Also, CLPU.sup.B concatenates the keys K.sup.B.sub.i which are different from ⊥.sub.i to form K.sup.B′=[K.sup.B.sub.1, K.sup.B.sub.2, . . . , K.sup.B.sub.M]. [0078] 3. Generation of a epsilon-secure key K.sup.A and K.sup.B: CLPU.sup.A and CLPU.sup.B apply a privacy amplification step to extract from K.sup.A′ and K.sup.B′ a shorter key, K.sup.A and K.sup.B, of length of about (M-t)*N bits. This can be done by using random hashing with a random matrix as explained before or using any other known privacy amplification mechanism.
[0079] We remark that Protocol 1 is just a non-limitative example of an embodiment of the invention. For example, note that a naïve method for implementing the additional privacy amplification step which is applied to K.sup.A′ is simply for Alice to take the bit-wise XOR of the various keys, K.sup.A.sub.i (and similarly for Bob). Also, in general, there is no need to apply privacy amplification in two different steps (i.e., for generating first K.sup.A′ and K.sup.B′ and, afterwards, for generating K.sup.A and K.sup.B from K.sup.A′ and K.sup.B′) but it could be applied in one single step. That is, one could directly generate an epsilon-secure key, K.sup.A and K.sup.B, in one single step from all the raw keys, R.sup.A.sub.i and R.sup.B.sub.i, together. Importantly, Protocol 1 illustrates that privacy amplification can be used to guarantee the secrecy of the final key, K.sup.A and K.sup.B, in the presence of dishonest KGUs with a prescribed access structure.
[0080] C. Scenario 2: A Key Distribution Method with Untrusted Classical Post-Processing Units Inside a Cryptographic Station.
[0081] In this section, it is considered a scenario where some CLPUs in a cryptographic station may be untrusted but the KGUs are trusted. Once again, to improve security, it is considered using multiple CLPUs in a cryptographic station, as shown in
[0082] While the scope of the invention is general and applies to a general adversary structure with dishonest CLPUs which could be passively or actively controlled by Eve, for illustrative purposes, we will describe here the simple threshold case with a fixed number of dishonest CLPUs actively controlled by Eve (however, the invention can be applied to other more complex cases). More concretely, consider the situation where the cryptographic stations A and B have one trusted KGU each, and, moreover, the cryptographic station A has “s” classical post-processing units CLPU.sup.A.sub.1, CLPU.sup.A.sub.2, . . . , CLPU.sup.A.sub.s, and the cryptographic station B has “s′” classical post-processing units CLPU.sup.B.sub.1, CLPU.sup.B.sub.2, . . . , CLPU.sup.B.sub.s′. Also, suppose that up to t<s/3, CLPU.sup.A.sub.i and up to t′<s′/3 CLPU.sup.B.sub.j could be dishonest and actively controlled by Eve, with i=1, . . . , s, and j=1, . . . , s′. Note that the various CLPUs could be purchased from different vendors. The present invention allows to construct a secure key generation system with components from untrusted vendors.
[0083] Since some CLPUs are dishonest (untrusted), the present invention does not allow them to have the final key, K.sup.A and K.sup.B, instead, they are only allowed to produce some shares of the final key, K.sup.A and K.sup.B. For instance, in
[0084] KGU.sup.A is connected to each CLPU.sup.A.sub.i via a secure classical (conventional) channel (denoted as “S.C. channel i.sup.A” in
[0085] In this situation, it is considered a new key distribution protocol where KGU.sup.A sends shares of the generated raw key, R.sup.A, to one or more of the CLPU.sup.A.sub.i. Similarly, KGU.sup.B sends shares of the raw key, R.sup.B, to one or more of the CLPU.sup.B.sub.i. In
[0086] To split the raw key, R.sup.A and R.sup.B, into shares, the KGUs could use any known method, for instance, secret sharing schemes or verifiable secret sharing schemes. In a secret sharing scheme, the person/device that is splitting the secret is called the dealer. In the case where a dealer might be dishonest, it is important to verify that the values of shares sent by the dealer are consistent with each other. Also, in the presence of dishonest parties, it is important to be able to guarantee that all honest parties can reconstruct the same secret from the shares received, and, moreover, if the dealer is honest, the reconstructed secret should be equal to that originally distributed by the dealer. Such verification can be done by a verifiable secret sharing scheme. In a verifiable secret sharing scheme, a dealer further splits each share into “shares of share” and sends those shares of share to various participants. Those participants may then verify the consistency of the values of those shares of shares.
[0087] In the presence of dishonest CLPUs, the use of a verifiable secret sharing scheme can guarantee the consistency of the shares distributed. Therefore, the use of an information reconciliation step (which might include an error verification step) can guarantee the correctness of the final key, K.sup.A and K.sup.B.
[0088] Below we include the step by step implementation of an example of a verifiable secret sharing scheme from Maurer, U. Secure multi-party computation made simple. Discrete Appl. Math. 154, 370-381 (2006). It uses a (q,q) threshold secret sharing scheme, to distribute a message to n parties. This last scheme could be implemented, for instance, by splitting the message X, to be distributed, into a random sum of q shares X.sub.i, with i=1, . . . , q. This could be done, for example, by selecting the first q−1 shares X.sub.i of X at random, and then by choosing X.sub.q=X⊕X.sub.1⊕ . . . ⊕X.sub.q-1, where the symbol ⊕ denotes summation in modulo 2 algebra. A verifiable secret sharing scheme usually can be decomposed into two protocols: the share and the reconstruct protocols. The example of verifiable secret sharing scheme presented below allows to split a message X between n parties, and provides information-theoretic security against a threshold active adversary structure with at most t<n/3 dishonest parties. Again, by (general) adversary structure we mean a set of subsets that identifies which combinations of parties could be passively corrupted, and a set of subsets that identifies which combinations of parties could be actively corrupted. Note that verifiable secret sharing schemes that are secure against general adversary structures also exist. In order to simplify the explanation, it has been assumed here a threshold active adversary structure where at most t parties could be actively corrupted (however, the invention can be applied to other more complex cases). So the example of verifiable secret sharing scheme described above and whose share and reconstruct protocols are given below is secure against such threshold active adversary structure but it is not always secure against general adversary structures. However, if one wishes, one could modify it to make it secure against a general adversary structure. Actually such modification was introduced in the document cited before Maurer, U. Secure multi-party computation made simple. Discrete Appl. Math. 154, 370-381 (2006).
[0089] Share Protocol: [0090] 1. The dealer uses a (q,q) threshold secret sharing scheme to split the message X into q=n!/[(n−t)!t!] shares X.sub.i, with i=1, . . . , q. [0091] 2. Let {σ.sub.1, . . . , σ.sub.q} denote all (n−t)-combinations of the set of n parties. Then, for each i=1, . . . , q, the dealer sends X.sub.i over a secure channel to each party in the set σ.sub.i. If a party does not receive his share, he takes as default share, for example, a bit string with all its components equal to zero. [0092] 3. All pairs of parties in σ.sub.i send each other their shares X.sub.i over a secure channel to check that their shares are indeed equal. If an inconsistency is found, they complain using a broadcast channel. [0093] 4. If a complaint is raised in ci, the dealer broadcasts X.sub.i to all parties and they accept the share received. If the dealer refuses (or he is not able) to broadcast X.sub.i to all the parties when there is a complaint in ci, the protocol aborts.
[0094] Reconstruct Protocol: [0095] 1. All pairs of parties send each other their shares over an authenticated classical channel. [0096] 2. Each party uses majority voting to reconstruct the shares X.sub.i ∀i, and then they obtain X=X.sub.1 ⊕ . . . ⊕X.sub.q.
[0097]
[0098] In the case shown in the figure, the sets σ.sub.1={P.sub.2, P.sub.3, P.sub.4}, σ.sub.2={P.sub.1, P.sub.3, P.sub.4}, σ.sub.3={P.sub.1, P.sub.2, P.sub.4} and σ.sub.4={P.sub.1, P.sub.2, P.sub.3}, are defined. As q=n!/[(n−t)!t!=4, the message X has been splitted into 4 shares X.sub.1, X.sub.2, X.sub.3 and X.sub.4. Then the dealer sends X.sub.i over a secure channel to all parties in σ.sub.i. For example, he sends X.sub.1 to P.sub.2, P.sub.3 and P.sub.4, and similarly for the other shares.
[0099] We note that the broadcast channel which is required to perform steps 3 and 4 of the share protocol above does not have to be a physical channel but it could be a simulated channel.
[0100] The above presented verifiable secret sharing scheme is only a non-limitative example and any other known or yet to be developed verifiable secret sharing mechanisms could be used. For example, if the number n of parties is large, there exist other efficient verifiable secret sharing schemes or if a physical broadcast channel is actually available, there exist verifiable secret sharing schemes which can guarantee security given that there is a majority of honest parties (see, for example, Rabin, T. and Ben-Or, M. Verifiable secret sharing and multiparty protocols with honest majority. Proc. 21th Annual ACM Symposium on Theory of Computing (STOC'89) 73-85 (ACM, New York, N.Y., USA, 1989)).
[0101] To implement several of the classical post-processing steps which are required to distil a secure key, the CLPUs might need to generate random numbers between mutually untrusted parties. Next we present the step by step implementation of an example of a scheme which could be used to solve this task. It follows directly from verifiable secret sharing schemes and it can generate a common perfectly unbiased random I-bit string r between n parties when up to t<n/3 of them could be dishonest and actively controlled by Eve. For convenience, we denote it the Random Bit String (RBS) protocol.
[0102] RBS Protocol: [0103] 1. Say each of the first t+1 parties produces locally a random I-bit string r.sub.i and sends it to all the other parties using the share protocol of a verifiable secret sharing scheme. [0104] 2. Each party uses a broadcast channel to confirm that it has received the shares from the first t+1 parties. Otherwise, the protocol aborts. [0105] 3. All parties use the reconstruct protocol of a verifiable secret sharing scheme to obtain r.sub.i for all i=1, . . . , t+1. Afterward, each of them calculates locally r=r.sub.1⊕ . . . ⊕r.sub.t+1.
[0106] Like above, we note that the broadcast channel required in step 2 of the RBS protocol could be implemented with a simulated broadcast channel. Also, note that in order to generate random numbers between mutually untrusted parties which are secure against general adversary structures one could simply use in the RBS protocol above the share protocol (in step 1) and the reconstruct protocol (in step 3) of a verifiable secret sharing scheme that is secure against general adversary structures, like for instance that introduced in Maurer, U. Secure multi-party computation made simple. Discrete Appl. Math. 154, 370-381 (2006).
[0107] To illustrate the present invention in this scenario, next we describe two protocols (see Protocols 2 and 3 below) which could be used to achieve secure key distribution with untrusted CLPUs. They are two examples of embodiments of the present invention. For ease of illustration we will consider in these two examples that the number of CLPUs in cryptographic station A is equal to that of B, i.e., s=s′, but of course, this is not a required condition and the number of CLPUs in each cryptographic station can be different.
[0108] The first example (see Protocol 2 below) can be decomposed in two main conceptual steps. In a first step, KGU.sup.A and KGU.sup.B perform s independent key generation sessions, each of them is performed with a different pair of units CLPU.sup.A.sub.i and CLPU.sup.B.sub.i, with i=1, . . . , s. The goal of each session is to generate a say (epsilon/s)-secure key, K.sup.A.sub.i and K.sup.B.sub.i, or the abort symbol ⊥.sub.i. For easy of illustration, consider that the length of each K.sup.A.sub.i and K.sup.B.sub.i is N bits for all i. If say the pair CLPU.sup.A.sub.i and CLPU.sup.B.sub.i is dishonest then we have that K.sup.A.sub.i and K.sup.B.sub.i could be compromised and known to Eve. A pair CLPU.sup.A.sub.i and CLPU.sup.B.sub.i is dishonest if at least one of its units is dishonest. Then, in a second step, the keys K.sup.A.sub.i and K.sup.B.sub.i are concatenated to form K.sup.A′=[K.sup.A.sub.1, K.sup.A.sub.2, . . . , K.sup.A.sub.M] and K.sup.B′=[K.sup.B.sub.1, K.sup.B.sub.2, . . . , K.sup.B.sub.M], where M denotes the number of keys K.sup.A.sub.i and K.sup.B.sub.i which are different from the abort symbol, and the CLPUs apply an error verification step and a privacy amplification step to K.sup.A′ and K.sup.B′. Here comes a key contribution of this embodiment of the invention: this second step is performed in a distributed setting by acting only on shares of K.sup.A′ and K.sup.B′. We remark that this is possible because all these post-processing techniques are usually “linear” in nature (i.e., they typically involve simple functions in linear algebra such as bit-wise XOR and multiplications of matrices) and thus they can be easily implemented by acting only on shares of K.sup.A′ and K.sup.B′. In certain steps, the CLPUs might need information about shares which are in the hands of other CLPUs. To obtain such information, they could use for instance the reconstruct protocol of a verifiable secret sharing scheme. That is, all the units which have the information simply send it to the unit which requires it and the use of majority voting allows this unit to discriminate the information which is correct. Next we describe the protocol in more detail:
[0109] Protocol 2 (this is only a possible embodiment, and not all the cited steps are essential and mandatory in all the embodiments of the present invention): [0110] 1. Generation of K.sup.A.sub.i and K.sup.B.sub.i: KGU.sup.A and KGU.sup.B perform s independent key generation sessions, each of which with a different pair of units CLPU.sup.A.sub.i and CLPU.sup.A.sub.i, with i=1, . . . , s. For this they use the “Q. channel”, the “S.C. channel i.sup.A”, the “S.C. channel i.sup.B”, and the “A.C. channel ii.sup.AB” shown in
[0115] Given that t<M.sup.A.sub.i/3 and t<M.sup.B.sub.i/3 for all i=1, . . . , M, where M.sup.A.sub.i denotes the number of CLPU.sup.A.sub.l that do not produce the abort symbol but generate post-processed shares, K.sup.A.sub.lij, from K.sup.A.sub.i, and M.sup.B.sub.i denotes the number of CLPU.sup.B.sub.l′ that do not produce the abort symbol but generate post-processed shares, K.sup.B.sub.l′ij, from K.sup.B.sub.i, then the bit strings K.sup.A.sub.lij and K.sup.B.sub.l′ij produced by the units CLPU.sup.A.sub.l and CLPU.sup.B.sub.l′ in step 5 of Protocol 2 are shares of a final epsilon-secure key, K.sup.A and K.sup.B. As mentioned above, in this scenario the units CLPU.sup.A.sub.i and CLPU.sup.B.sub.i are only allowed to produce shares of K.sup.A and K.sup.B. Say a secure lab in cryptographic station A could use majority voting to obtain K.sup.A.sub.ij from K.sup.A.sub.lij. Similarly, say a secure lab in cryptographic station B could use majority voting to obtain K.sup.B.sub.ij from K.sup.B.sub.l′ij. Then, the final key could be obtained as K.sup.A K.sup.A.sub.11⊕ . . . ⊕K.sup.A.sub.Mq and K.sup.B K.sup.B.sub.11⊕ . . . ⊕K.sup.B.sub.Mq.
[0116] Next we present the second example of a protocol that can provide secure key distribution with untrusted classical post-processing units (see Protocol 3 below). This protocol has two main advantages with respect to Protocol 2. First, it does not require to run s independent key generation sessions but it can distil an epsilon-secure key from one single key generation run. And, second, it is more efficient in terms of the secret key rate, as it delivers a secret key rate that could be about s/(s−2*t) times higher than that provided by Protocol 2. While the scope of application of the present invention is general, for ease of illustration below we will consider that the key distillation procedure does not use random post-selection of data from the raw key (however, the invention can be applied to other more complex cases where random post-selection of data from the raw key is performed). Also, for ease of illustration it will be assumed that the classical post-processing protocol does not estimate the actual QBER but it uses a pre-fixed QBER value for the error correction step followed by an error verification step. Protocol 3 below can be decomposed in two main conceptual steps. In a first step, KGU.sup.A and KGU.sup.B generate a raw key, R.sup.A and R.sup.B respectively. Next comes a key step in this embodiment of the invention. KGU.sup.A splits R.sup.A in shares by using, for instance, the share protocol of a verifiable secret sharing scheme and then sends these shares to the units CLPU.sup.A.sub.i. This step is illustrated in
[0117] Protocol 3 (this is only a possible embodiment, and not all the cited steps are essential and mandatory in all the embodiments of the present invention): [0118] 1. Distribution of R.sup.A and R.sup.B: KGU.sup.A and KGU.sup.B first generate a raw key, R.sup.A and R.sup.B. Next, KGU.sup.A uses the share protocol of a verifiable secret sharing scheme to create q=s!/[(s−t)!t!] shares of R.sup.A and then distributes them among the CLPU.sup.A.sub.i, with i=1, . . . , s, by using the secure classical channels “S.C. channel i.sup.A” shown in
[0124] We note that if the number of dishonest units CLPU.sup.A.sub.i satisfies t<M.sub.A/3 and the number of dishonest units CLPU.sup.B.sub.i satisfies t<M.sub.B/3, where M.sub.A is the number of units CLPU.sup.A.sub.i that do not abort and M.sub.B is the number of units CLPU.sup.B.sub.i that do not abort, then from the bit strings K.sup.A.sub.ij and K.sup.B.sub.ij produced in step 6 of Protocol 3 it is possible to reconstruct an epsilon-secure key, K.sup.A and K.sup.B. For this, say a secure lab in cryptographic station A could use majority voting to obtain K.sup.A.sub.j from K.sup.A.sub.ij for all j=1, . . . , q. Similarly, say a secure lab in cryptographic station B could use majority voting to obtain K.sup.B.sub.j from K.sup.B.sub.ij for all j=1, . . . , q. Then, K.sup.A=K.sup.A.sub.1⊕ . . . ⊕K.sup.A.sub.q and K.sup.B=K.sup.B.sub.1 ⊕ . . . ⊕K.sup.B.sub.q.
[0125] We remark that Protocols 2 and 3 are just non-limitative examples of embodiments of the invention. Note that these protocols could be modified to guarantee security against general adversary structures. For this, one could basically replace the verifiable secret sharing scheme above which is secure against threshold active adversary structures with another known one robust against general adversary structures (see, for example, Maurer, U. Secure multi-party computation made simple. Discrete Appl. Math. 154, 370-381 (2006)), and, in addition, the method to announce the hash functions hash and hashPA may now depend on the adversary structure. Importantly, Protocols 2 and 3 highlight a key contribution of the present invention, which is that the use of secret sharing schemes could guarantee the security of key distribution in the presence of dishonest CLPUs.
[0126] D. Scenario 3: A Key Generation Method with Untrusted Key Generation Units and Untrusted Classical Post-Processing Units in a Cryptographic Station.
[0127] Here, it is considered the more general scenario (preferred embodiment of the invention), in which both the KGUs and the CLPUs in a cryptographic station may be untrusted. Again, to guarantee security multiple CLPUs and KGUs are used in each cryptographic station, as shown in
[0128] Once again, since some CLPUs are dishonest, it is not allowed for any of them to have the final cryptographic key, K.sup.A and K.sup.B, but they can only produce shares of it. For instance, in
[0129] In order to illustrate the invention, below it is described an example of a protocol (see Protocol 4) which could be used to achieve secure key distribution in this scenario according to the present invention. For ease of illustration, in this example we consider that the number of CLPUs in cryptographic station A is equal to that of B, i.e., s=s′ (this is only an example for illustration purposes and they may have a different number of CLPUs). Protocol 4 can be decomposed in two main conceptual steps. In a first step, each pair of units KGU.sup.A.sub.i and KGU.sup.B.sub.i generates a raw key and then they implement, together with the classical post-processing units CLPU.sup.A.sub.i and CLPU.sup.B.sub.l, the Protocol 3 described above. As a result, the units CLPU.sup.A.sub.l and CLPU.sup.B.sub.l, with l=1, . . . , s, obtain shares of an (epsilon/n)-secure key, K.sup.A.sub.i and K.sup.B.sub.i (i=1, . . . , n), or the abort symbol ⊥.sub.i. In particular, let K′.sup.A.sub.lij be the j-th share of K.sup.A.sub.i received by CLPU.sup.A.sub.l, and similarly let K′.sup.B.sub.lij be the j-th share of K.sup.B.sub.i received by CLPU.sup.B.sub.l. Moreover, to simplify the discussion (but not with limitative purposes), let us consider for instance that the length of all K.sup.A.sub.i and K.sup.B.sub.i is N bits for all i. Next the CLPUs proceed similarly to Protocol 2. That is, the keys K.sup.A.sub.i and K.sup.B.sub.i are concatenated to form K.sup.A′=[K.sup.A.sub.1, K.sup.A.sub.2, . . . , K.sup.A.sub.M] and K.sup.B′=[K.sup.B.sub.1, K.sup.B.sub.2, . . . , K.sup.B.sub.M], where M denotes the number of keys K.sup.A.sub.i and K.sup.A.sub.i which are different from the abort symbol, and the CLPUs apply a privacy amplification step to K.sup.A′ and K.sup.B′. This privacy amplification step removes the information that the dishonest pairs of KGUs could leak to Eve about say K.sup.A′. This second step is performed in a distributed setting by acting only on the shares K′.sup.A.sub.lij and K′.sup.B.sub.lij. Next the protocol is described in more detail:
[0130] Protocol 4 (this is only a possible embodiment, and not all the cited steps are essential and mandatory in all the embodiments of the present invention): [0131] 1. Generation and distribution of shares of K.sup.A.sub.i and K.sup.B.sub.i: Each pair KGU.sup.A.sub.i and KGU.sup.B.sub.i, with i=1, . . . , n, generates a raw key and then they implement, together with the classical post-processing units CLPU.sup.A.sub.l and CLPU.sup.B.sub.l, all the steps of the Protocol 3 described above. As a result, the units CLPU.sup.A.sub.l and CLPU.sup.B.sub.l, with l=1, . . . , s, obtain shares of a (epsilon/n)-secure key, K.sup.A.sub.i and K.sup.B.sub.i, or the symbol ⊥.sub.i to indicate abort. Let K′A.sub.lij be the j-th share of K.sup.A.sub.i received by CLPU.sup.A.sub.l, and similarly let K′.sup.B.sub.lij be the j-th share of K.sup.B.sub.i received by CLPU.sup.B.sub.l. [0132] 2. Generation of K″.sup.A.sub.lij and K″.sup.B.sub.lij: Each CLPU.sup.A.sub.l, with l=1, . . . , s, defines locally the bit strings K″.sup.A.sub.lij=[0.sub.1, . . . , 0.sub.i−1, K.sup.A.sub.lij, 0+.sub.i+1, . . . , 0.sub.M], where 0.sub.i, with i=1, . . . , M, represents the N-bit zero vector, and M is the number of keys K.sup.A.sub.i and K.sup.B.sub.i which are different from the abort symbol ⊥.sub.i. Likewise, the units CLPU.sup.B.sub.l act similarly and they obtain K″.sup.B.sub.lij. [0133] 3. Privacy amplification: The CLPU.sup.A.sub.l use the RBS scheme to randomly select a two-universal hash function, hashPA. They compute K.sup.A.sub.lij=hashPA(K″.sup.A.sub.lij), and say the first 2t+1 CLPU.sup.A.sub.l send hashPA to all CLPU.sup.B.sub.l′ through the authenticated classical channels “A.C. channel II′.sup.AB” shown in
[0134] Given that t<M.sup.A.sub.i/3 and t′<M.sup.B.sub.i/3 for all i=1, . . . , M, where M.sup.A.sub.i denotes the number of CLPU.sup.A.sub.l that do not produce the abort symbol but generate post-processed shares, K.sup.A.sub.lij, from K.sup.A.sub.i, and M.sup.B.sub.i denotes the number of CLPU.sup.B.sub.l′ that do not produce the abort symbol but generate post-processed shares, K.sup.B.sub.l′ij, from K.sup.B.sub.i, then a final epsilon-secure key, K.sup.A and K.sup.B, can be reconstructed from the shares K.sup.A.sub.lij and K.sup.B.sub.l′ij by following the same procedure that reconstructs the final key in Protocol 2. We remark that Protocol 4 is just an example of an embodiment of the invention. By following similar ideas, one could define alternative protocols that also allow secure key distribution in this scenario. For instance, one could replace the first step of Protocol 4 with an step where each group of units KGU.sup.A.sub.i, KGU.sup.B.sub.i, CLPU.sup.A.sub.i and CLPU.sup.B.sub.i, with i=1, . . . , n, first performs a key generation session to produce a epsilon-secure key, K.sup.A.sub.i and K.sup.B.sub.i, or the abort symbol ⊥.sub.i, followed by the distribution of K.sup.A.sub.i among all CLPU.sup.A.sub.l and the distribution of K.sup.B.sub.i among all CLPU.sup.B.sub.l′ by using the share protocol of a verifiable secret sharing scheme. In this last case, to guarantee the correctness of the final, one could include an error verification step implemented in a distributed setting by acting on shares. Also, we remark that Protocol 4, and similar protocols, could be modified to guarantee security against general adversary structures by following the techniques explained for the two previous cases. Importantly, the example given by Protocol 4 illustrates one key contribution of the invention, that is, the combination of secret sharing schemes and privacy amplification techniques could guarantee secure key distribution with dishonest KGUs and CLPUs.
[0135] Summarizing, it can be said that the main goal of the present invention is to obtain a secure key generation system with components purchased/made by various untrusted vendors. The invention can be used to defend against both untrusted key generation units (KGUs) and untrusted classical post-processing units (CLPUs). Moreover, the present invention has the advantage of being robust against a denial-of-service attack as trust is distributed across multiple KGUs that could be using entirely different channels.
[0136] For simplicity, the invention has so far been discussed for specific examples where there are only two users. It should be noted that it can be applied to a network setting where there are multiple users (and therefore multiple cryptographic stations). Also, it can be applied to a network setting where the multiple users are connected to each other through multiple paths, and it allows the users to combine the multiple keys generated from the multiple paths into a final key that is secure against untrusted devices and it is also secure against compromised paths that contain nodes which are controlled by the eavesdropper. In addition, for simplicity, we have assumed that each user is located physically in just one local cryptographic station. It should be noted that what we draw as a single cryptographic station in
[0137] The invention can be combined with both trusted relays and untrusted relays. Also, the invention may apply to a measurement-device-independent QKD set-up where an untrusted intermediate, Charles, performs some measurements (e.g. Bell state measurements) on quantum states sent by cryptographic stations of Alice and Bob. Moreover, the invention can be combined with quantum repeaters.
[0138] The invention can be combined with various classical post-processing protocols including post-selection protocols or, as already mentioned previously, adding noise protocols.
[0139] The invention is compatible with various QKD protocols including, for example, decoy state QKD, COW protocol, RR-DPS QKD protocol and entanglement-based QKD. It applies as well to various encoding schemes and to both discrete variable and continuous variable schemes for key generation.
[0140] Even though we have discussed our invention in the composable security framework (where a protocol can be combined with other protocols in an arbitrary manner), the present invention works also for other security frameworks including one that involves computational assumptions.
[0141] While the invention has been described with reference to the preferred and alternative embodiments thereof, it will be appreciated that various modifications can be made to the parts and methods that comprise the invention without departing from the spirit and scope thereof.
[0142] A person skilled in the art would readily recognize that steps of various above-described methods can be performed by programmed computers. Herein, some embodiments are also intended to cover program storage devices, e.g., digital data storage media, which are machine or computer readable and encode machine-executable or computer-executable programs of instructions, wherein said instructions perform some or all of the steps of said above-described methods. The program storage devices may be, e.g., digital memories, magnetic storage media such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. The embodiments are also intended to cover computers programmed to perform said steps of the above-described methods.
[0143] The description and drawings merely illustrate the principles of the invention. Although the present invention has been described with reference to specific embodiments, it should be understood by those skilled in the art that the foregoing and various other changes, omissions and additions in the form and detail thereof may be made therein without departing from the scope of the invention as defined by the following claims.
[0144] Furthermore, all examples recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass equivalents thereof.
[0145] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the invention. Similarly, it will be appreciated that any flow charts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer or processor, whether or not such computer or processor is explicitly shown.