GROUP-WISE SECRET KEY GENERATION

• US 20080075280A1
• Filed: 09/21/2007
• Published: 03/27/2008
• Est. Priority Date: 09/21/2006
• Status: Abandoned Application

• Current Assignee: Interdigital Technology Corporation (InterDigital, Inc.)
• Original Assignee: Interdigital Technology Corporation (InterDigital, Inc.)
• Inventors: Reznik, Alexander, Ye, Chunxuan
• Application Number:
  US11/859,503
• Publication Number:
  US 20080075280A1
• 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 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/0471 Key exchange

Abstract

The present invention relates to a method for constructing a perfectly secret key within a group of nodes. In a group of m nodes, pair-wise secret keys are assigned. Based on pair-wise secret keys, these m nodes generate a group-wise perfectly secret key. In a preferred embodiment, each node communicates with every other node through public noiseless broadcasts.

Claims

1. A method for generating a group-wise perfectly secret key in a wireless communication system having a plurality of wireless transmit/receive units (WTRU) utilizing symmetric key encryption, the method comprising:

a) generating a pair-wise perfectly secret key between at least two WTRUs; and

b) selecting a group-wise perfectly secret key K using the pair-wise secret keys.

2. The method as in claim 1, further comprising:

c) transmitting the group-wise perfectly secret key on a public broadcast channel to another WTRU using an XOR combination with a pair-wise perfectly secret key.

3. The method as in claim 1, further comprising:

c) determining a spanning tree from the plurality of WTRUs, the spanning tree having an edge weight between each WTRU pair equal to a length of a pair-wise perfectly secret key;

d) generating a group-wise perfectly secret key among m WTRUs according to a key from m−

1 pair-wise secret keys; and

e) reducing an edge weight by a key length on the spanning tree.

4. The method as in claim 3, wherein the spanning tree is a maximum spanning tree.

5. The method as in claim 1, further comprising:

c) selecting an edge for a spanning tree having a corresponding pair-wise secret bit that is to be the group-wise perfectly secret key;

d) determining at a first WTRU that a neighboring WTRU lacks knowledge of the selected edge'"'"'s secret bit;

e) transmitting the selected edge'"'"'s secret bit from the first WTRU to a neighboring WTRU with the pair-wise secret key shared by the first WTRU and the neighboring WTRU using an XOR combination;

f) decoding the selected edge'"'"'s secret key bit at the neighboring WTRU; and

g) repeating steps c) through f) until all WTRUs share the secret bit.

6. The method as in claim 5, further comprising:

h) determining a maximum spanning tree from the plurality of WTRUs, the maximum spanning tree having edge weights between each WTRU equal to the length of a pair-wise secret key;

i) reducing an edge weight by one bit on the maximum spanning tree following step e); and

j) removing an edge from the spanning tree when its edge weight becomes zero.

7. The method as in claim 6, wherein determining the maximum spanning tree is accomplished using a greedy algorithm.

8. The method as in claim 7, wherein the greedy algorithm is selected from the group consisting of a Kruskal algorithm and a Prim algorithm.

9. The method as in claim 3, wherein determining a maximum spanning tree includes selecting a WTRU such that the sum of all edges connecting to this WTRU is maximum.

10. The method as in claim 1, wherein the pair-wise perfectly secret key is generated based on joint randomness of the pair-wise channel.

11. The method as in claim 1, wherein the pair-wise perfectly secret key is generated based on a quantum entanglement.

12. A wireless transmit/receive unit (WTRU) capable of generating a group-wise perfectly secret key in a wireless communication system having a plurality of WTRUs utilizing symmetric key encryption, the WTRU comprising:

a processor configured to generate a pair-wise perfectly secret key with a connected WTRU;

a receiver for receiving a secret key on a public broadcast channel; and

a processor for determining a group-wise perfectly secret key K based on the pair-wise secret keys.

13. The WTRU as in claim 12, further comprising a transmitter for transmitting on a public broadcast the group-wise perfectly secret key channel that is XOR combined with the pair-wise perfectly secret key.

14. The WTRU as in claim 12, wherein the processor is configured to select a secret bit from an edge, further comprising a transmitter configured to transmit a selected edge'"'"'s secret bit to a neighboring WTRU combined with the pair-wise secret key shared by the WTRU and the neighboring WTRU.

15. A method for generating a group-wise perfectly secret key in a fiber optic communication network having a plurality of nodes utilizing symmetric key encryption, the method comprising:

a) generating a pair-wise perfectly secret key between at least two nodes using quantum cryptography; and

b) selecting a group-wise perfectly secret key K using the pair-wise secret keys.

16. The method as in claim 15, further comprising:

c) transmitting the group-wise perfectly secret key on a public broadcast channel to another node using an XOR combination with a pair-wise perfectly secret key.

17. The method as in claim 15, further comprising:

c) determining a spanning tree from the plurality of nodes, the spanning tree having an edge weight between each node pair equal to a length of a pair-wise perfectly secret key;

d) generating a group-wise perfectly secret key among m nodes according to a key from m−

1 pair-wise secret keys; and

e) reducing an edge weight by a key length on the spanning tree.

18. The method as in claim 17, wherein the spanning tree is a maximum spanning tree.

19. The method as in claim 15, further comprising:

c) selecting an edge for a spanning tree having a corresponding pair-wise secret bit that is to be the group-wise perfectly secret key;

d) determining at a first node that a neighboring node lacks knowledge of the selected edge'"'"'s secret bit;

e) transmitting the selected edge'"'"'s secret bit from the first node to a neighboring node with the pair-wise secret key shared by the first node and the neighboring node using an XOR combination;

f) decoding the selected edge'"'"'s secret key bit at the neighboring node; and

g) repeating steps c) through f) until all nodes share the secret bit.

20. The method as in claim 15, further comprising:

h) determining a maximum spanning tree from the plurality of node, the maximum spanning tree having edge weights between each node equal to the length of a pair-wise secret key;

i) reducing an edge weight by one bit on the maximum spanning tree following step e); and

j) removing an edge from the spanning tree when its edge weight becomes zero.

21. The method as in claim 20, wherein determining the maximum spanning tree is accomplished using a greedy algorithm.

22. The method as in claim 21, wherein the greedy algorithm is selected from the group consisting of a Kruskal algorithm and a Prim algorithm.

23. The method as in claim 17, wherein determining a maximum spanning tree includes selecting a node such that the sum of all edges connecting to this node is maximum.