Generation of perfectly secret keys in wireless communication networks

• US 20070177729A1
• Filed: 01/26/2006
• Published: 08/02/2007
• Est. Priority Date: 01/27/2005
• Status: Active Grant

• Current Assignee: Interdigital Technology Corporation (InterDigital, Inc.)
• Original Assignee: Interdigital Technology Corporation (InterDigital, Inc.)
• Inventors: Reznik, Alexander, Zhang, Guodong, Shah, Yogendra, Ye, Chunxuan, Kumoluyi, Akinlolu, Chitrapu, Prabhakar, Sternberg, Gregory, Briancon, Alain Charles
• Granted Patent: US 8,238,551 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04K 1/00 Secret communication
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 25/0202 Channel estimation
• CPC Class Codes: H04L 25/0224 using sounding signals
• CPC Class Codes: H04L 9/0858 Details about key distillation or coding, e.g. reconciliation, error correction, privacy amplification, polarisation coding or phase coding
• CPC Class Codes: H04L 9/0875 based on channel impulse response [CIR]
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/0431 Key distribution or pre-distribution; Key agreement
• CPC Class Codes: Y04S 40/20 Information technology specific aspects, e.g. CAD, simulation, modelling, system security

Abstract

A method and apparatus is used for generating a perfectly random secret key between two or more transceivers in a wireless communication network. In a point-to-point system, both transceivers produce an estimate of the channel impulse response (CIR) based on the received radio signal. The CIR estimation is synchronized and may include error correction and detection. A long secret key of bits is generated from a digitized version of the CIR estimate, from which a perfectly secret encryption key is derived by privacy amplification.

Claims

1. A method for generating a perfectly secret encryption key for wireless communication between a first transceiver and a second transceiver, comprising:

estimating at each transceiver a channel impulse response (CIR) based on a received radio signal according to a CIR representation common to each transceiver;

generating a long secret key from a digitized version of the CIR estimate;

synchronizing a starting point for the estimating of the CIR estimate at the first transceiver and the second transceiver; and

generating a perfectly secret encryption key from the long secret key by privacy amplification.

2. The method of claim 1, in which the privacy amplification includes:

mapping the long secret key according to a universal hash function which extracts entropy from the CIR estimate and removes any bits publicly exchanged between the first transceiver and the second transceiver.

3. The method of claim 1, in which the privacy amplification includes:

entropy encoding using a Burrows-Wheeler Transform.

4. The method of claim 1, in which the privacy amplification includes:

generating a non-systematic code for the long secret key.

5. The method of claim 1, in which the synchronizing includes:

recording a starting point used by the first transceiver for estimating the CIR estimate; and

encoding the starting point for transmission to the second transceiver.

6. The method of claim 1, in which the synchronizing is according to a synchronization code encoded at the first transceiver and decoded at the second transceiver.

7. The method of claim 1, further comprising:

synchronizing a starting point for the estimating of the CIR estimate at the first transceiver and the second transceiver by generation of a synchronization signal related to a common timing source.

8. The method of claim 7, wherein the common timing source includes GPS or a common system time of a communication system in which the first transceiver and the second transceiver reside.

9. The method of claim 1, further comprising:

deriving syndrome bits for error correcting code at the first transceiver;

transmitting the syndrome bits of the error correcting code to the second transceiver; and

. correcting the CIR estimate derived at the second transceiver using the received syndrome bits.

10. The method of claim 9, wherein the error correcting code is non-systematic.

11. The method of claim 9, wherein the error correcting code is based on low density parity check (LDPC) codes.

12. The method of claim 1, further comprising:

deriving a block error correcting code having parity bits at the first transceiver;

transmitting the parity bits of the error correcting code to the second transceiver; and

.

correcting the CIR estimate derived at the second transceiver using the received parity bits.

13. The method of claim 12, wherein the error correcting code is systematic.

14. The method of claim 12, further comprising:

selecting an error correction code from a family of codes based on one or more channel conditions; and

establishing agreement of the selected code by public communication between the first transceiver and the second transceiver.

15. The method of claim 14, wherein the error correction codes are differentiated by means of a puncturing or repetition pattern.

16. The method of claim 14, wherein the channel conditions include interference level.

17. The method of claim 14, wherein the channel conditions include Doppler spread.

18. The method of claim 14, wherein the channel conditions include Doppler spread or a direction of travel or a combination thereof.

19. The method of claim 14, wherein the channel conditions are measured by the bit error rate or block error rate at the receiver.

20. The method of claim 12, further comprising:

counting errors of the CIR estimate derived at the second transceiver while using the parity bits; and

synchronizing a starting point for the CIR estimation based on the CIR estimate having the fewest counted errors.

21. The method of claim 12, further comprising:

deriving error detection bits at each transceiver according to a commonly selected code;

appending the error detection bits to the CIR estimate derived by the first transceiver; and

encoding the error correction code including the error detection bits.

22. The method of claim 21, wherein the error detection code comprises a plurality of cyclic redundancy check (CRC) bits.

23. The method of claim 1, wherein the received radio signal includes a pilot signal.

24. The method of claim 1, wherein the received radio signal includes a training sequence within a communication signal frame.

25. The method of claim 1, further comprising:

performing a weak key analysis, such that the long secret key is rejected if it possesses extrinsic characteristics that prevent secrecy according to predefined criteria.

26. The method of claim 25, where the predefined criteria includes a repetitive string of all ones or all zeros within a defined period.

27. A method for generating a perfectly secret encryption key between a first transceiver and a second transceiver during a wireless communication, comprising:

performing information reconciliation according to multiple common channel impulse response (CIR) estimates of an information string;

filtering the CIR estimates to produce a predicted set of values;

generating a difference vector between a current set of estimates and the predicted values to produce a secret key;

continuously updating the secret key with generated difference vectors;

performing error correction of the key according to an error correcting code; and

performing privacy amplification.

28. The method of claim 27, further comprising:

generating at least one parity stream from the difference vector;

performing puncturing or repetition on the parity stream at a rate according to a desired transmit rate.

29. The method of claim 28, further comprising:

adapting the puncturing rate or the repetition rate according to one or more channel conditions.

30. The method of claim 29, wherein the channel conditions include interference level.

31. The method of claim 29, wherein the channel conditions include Doppler spread.

32. The method of claim 29, wherein the channel conditions include Doppler spread or a direction of travel or a combination thereof.

33. The method of claim 29, wherein the channel conditions are measured by the bit error rate or block error rate at the receiver.

34. A method for generating a perfectly secret encryption key between a first transceiver and a second transceiver during a wireless communication, comprising:

performing information reconciliation according to multiple common channel impulse response (CIR) estimates of a received information string, including;

sampling the CIR estimates; and

using the samples on a first-in first-out basis to generate a key;

performing error correction according to a systematic convolutional code;

updating the key by repeating the performing of information reconciliation; and

performing privacy amplification.

35. A method for generating a perfectly secret encryption key for wireless communication between a first transceiver and a second transceiver, comprising:

estimating at each transceiver a channel impulse response (CIR) based on a received radio signal according to a CIR representation common to each transceiver;

generating a long secret key from a digitized version of the CIR estimate;

synchronizing a starting point for the estimating of the CIR estimate at the first transceiver and the second transceiver; and

using a non-systematic block code for error correction of the long secret key.

36. The method of claim 35, in which the block code is an LDPC code.

37. A method for generating a perfectly secret encryption key between a network of a plurality of transceivers during a wireless communication, comprising:

establishing a respective temporary key between each pair of transceivers, comprising;

estimating at each transceiver a channel impulse response (CIR) based on a received radio signal according to a CIR representation common to each transceiver;

generating a long secret key of bits from a digitized version of the CIR estimate;

synchronizing a starting point for the estimating of the CIR estimate at the first transceiver and the second transceiver; and

generating the temporary key from the long secret key by privacy amplification;

selecting one temporary key as a permanent key;

communicating the permanent key to each transceiver while using the respective temporary key.

38. The method of claim 37 where the communication is performed by connecting the nodes of a network in a tree-graph configuration for the purposes of key distribution.

39. The method of claim 38 where the tree contains only two levels, with the root node broadcasting the permanent key to all the leaf nodes using the respective temporary keys.

40. The method of claim 39 where the permanent key is the shortest of the temporary keys and does not need to be broadcast to the node with which it was established.

41. The method of claim 39 where the root node is a base station in a cellular network and the leaf nodes are wireless transmit treceive units.

42. The method of claim 39 where the root node is an access point in a WLAN and the leaf nodes are network nodes.

43. The method of claim 37, in the first transceiver, the second transceiver and a third transceiver establish the perfectly secret encryption key during a wireless communication, further comprising:

establishing a first joint key S₁₂ between the first transceiver and the second transceiver and a second joint key S₁₃ between the first transceiver and the third transceiver;

comparing a temporary key S₂₃between the second transceiver and the third transceiver to a difference between the joint keys; and

generating a shared key with a length equal to the minimum of either the bit length of S₁₂or S₁₃+S₂₃.

44. The method of claim 43, further comprising:

sharing the shared key with a fourth transceiver by using an unused portion of a third joint key between the fourth transceiver and any of the first through third transceivers, such that the third joint key is of a length that is shortest of all joint keys.

45. A transceiver for generating a perfectly secret encryption key in a wireless communication as a lead transceiver with another transceiver, comprising:

a channel estimator configured to estimate a channel impulse response (CIR) based on a received radio signal;

an encoder configured to generate a block code for error correction;

a post processor for producing a digitized version of the CIR estimate as a long secret key; and

a privacy amplification processor configured to generate a perfectly secret encryption key from the long secret key by privacy amplification.

46. The transceiver of claim 45, in which the privacy amplification processor is further configured to map the long secret key according to a universal hash function which extracts entropy from the CIR estimate and removes any bits publicly exchanged between the lead transceiver another transceiver.

47. The transceiver of claim 45, in which the privacy amplification processor comprises an entropy encoder that performs a Burrows-Wheeler Transform.

48. The transceiver of claim 45, further comprising:

a synchronizer configured to synchronize a common starting point for the CIR estimating at the lead transceiver with CIR estimating at the other transceiver by recording a starting point used by the lead transceiver for the CIR estimating and to encode the starting point for transmission to the other transceiver.

49. The transceiver of claim 45, further comprising:

a synchronizer configured to synchronize a common starting point for the CIR estimating at the lead transceiver and at the second transceiver according to a synchronization code encoded at the lead transceiver and decoded at the other transceiver.

50. The transceiver of claim 45, further comprising:

a synchronizer configured to synchronize a common starting point for CIR estimating at the lead transceiver and at the other transceiver by generation of a synchronization signal related to a common timing source.

51. The transceiver of claim 50, wherein the common timing source is GPS.

52. The transceiver of claim 45, further comprising:

an error detection encoder configured to compute cyclic redundancy check (CRC) bits according to an error detection code and to append the CRC bits to the CIR estimate prior to the error correction by the encoder.

53. The transceiver of claim 45, in which the block code encoder uses a non-systematic code.

54. The transceiver of claim 45, further comprising:

a weak key analyzer configured to reject the long secret key if it possesses extrinsic characteristics that prevent secrecy according to predefined criteria.

55. A transceiver for generating a perfectly secret encryption key in a wireless communication with a lead transceiver, comprising:

a channel estimator configured to estimate a channel impulse response (CIR) based on a received radio signal;

a decoder configured to decode parity bits received from the lead transceiver for error correction and for synchronization of the CIR estimation with a correlated CIR estimation by the lead transceiver;

a post processor for producing a digitized version of the CIR estimation by the transceiver as a long secret key; and

a privacy amplification processor configured to generate a perfectly secret encryption key by mapping the long secret key according to a universal hash function which extracts entropy from the CIR estimate and removes any bits publicly exchanged between the lead transceiver another transceiver.

56. The transceiver of claim 55, further comprising:

counting errors during the CIR estimation while using the parity bits; and

synchronizing a starting point for the CIR estimation based on the CIR estimate having the fewest counted errors.

57. The transceiver of claim 55, further comprising:

a CRC processor configured to compute CRC bits according to an error detection code used by the lead transceiver and to append the CRC bits to the CIR estimation prior to the error correction by the decoder.

58. A transceiver for generating a perfectly secret encryption key in a wireless communication as a lead transceiver with another transceiver, comprising:

a channel estimator configured to estimate a channel impulse response (CIR) based on a received radio signal;

an encoder configured to generate a non-systematic block code for error correction and to extract entropy from the CIR estimate; and

a post processor for producing a digitized version of the CIR estimate as a long secret key.