# US 10,484,171 B2 · Method for efficient and practical key distribution in network coding systems > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,484,171 B2 - Document ID: US10484171B2 - Status: Granted - Kind: B2 - Application number: 15/185,743 - Filed: 2016-06-17 - Published: 2017-12-21 - Granted: 2019-11-19 - Earliest claimed: 2016-06-17 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Xin Hu; Wentao Huang; Jiyong Jang; Theodoros Salonidis; Marc Ph Stoecklin; Ting Wang - Web page: https://patentgrep.com/patent/US10484171B2 ## CPC - H04L 9/083: {involving central third party, e.g. key distribution center [KDC] or trusted third party [TTP]} - H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords} - H04L 9/304: {based on error correction codes, e.g. McEliece} - H04L 63/062: {for key distribution, e.g. centrally by trusted party (cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819)} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract An encoder including a computer readable storage medium storing program instructions, and a processor executing the program instructions, the processor configured to generate a k-bit key, where k is a positive integer, estimate an upper bound of a number of eavesdropped links, encode each bit of the k-bit key using a random matrix of a selected rank, and transmit the encoded k-bit key through a network that performs linear operations on packets. ## Claims ### Claim 1 An encoder comprising: a non-transitory computer readable storage medium storing program instructions; and a processor executing the program instructions, the processor configured to: generate a k-bit key, where k is a positive integer; estimate a network capacity; encode each bit of the k-bit key using a random matrix of a selected rank and the estimated network capacity; and transmit the encoded k-bit key through a network that performs linear operations on packets including network coding operations or store and forward routing operations, such that the k-bit key is protected against adversaries within the network, wherein the estimate of the network capacity includes estimating an upper bound of a number of eavesdropped links. ### Claim 2 (depends on 1) The encoder according to claim 1, wherein the processor is further configured to: use a universal secure network code to generate the encoded key, wherein the estimate of the network capacity includes estimating the upper bound of the number of eavesdropped links including determining a number of out-going edges of a source as an upper bound of the network capacity. ### Claim 3 (depends on 1) The encoder according to claim 1, wherein the processor is further configured to generate the random matrix from a first matrix generated from the k-bit key and a second matrix generated without the k-bit key. ### Claim 4 (depends on 1) The encoder according to claim 1, wherein one bit of information of the k-bit key is represented by a rank of a matrix of the encoded k-bit key that is transmitted. ### Claim 5 (depends on 1) The encoder according to claim 1, wherein depending on a state of a bit of the k-bit key, the bit is sent by the processor to either a random matrix generator or a zero matrix generator, wherein the transmitting of the encoded k-bit key through a network is such that the k-bit key is protected within the network. ### Claim 6 (depends on 1) The encoder according to claim 1, wherein the processor is further configured to: generate a parity check matrix of a maximum rank distance code; and perform a product of an output of a random matrix generator and a zero matrix generator. ### Claim 7 (depends on 1) A system comprising the encoder according to claim 1, further comprising a decoder deployed in one or more terminals, the decoder comprising: a second processor executing the program instructions, wherein the second processor is configured to: decode the encoded key from a received matrix from the network using a rank metric. ### Claim 8 (depends on 7) The system according to claim 7, wherein the second processor is configured to generate an estimate using a rank metric from the matrix received from the network. ### Claim 9 (depends on 7) The system according to claim 7, wherein the second processor is configured to test a rank of a second matrix from a reduction of the matrix from the network in order to output the decoded key. ### Claim 10 A method, comprising: generating a k-bit key, where k is a positive integer; estimating a network capacity; encoding each bit of the k-bit key using a random matrix of a selected rank and the estimated network capacity; and transmitting the encoded k-bit key through a network that performs linear operations on packets, such that the k-bit key is protected against adversaries within the network, wherein the estimating of the network capacity includes estimating an upper bound of a number of eavesdropped links. ### Claim 11 (depends on 10) The method according to claim 10, further comprising: using a universal secure network code to generate the encoded key, wherein the estimate of network capacity includes estimating the upper bound of the number of eavesdropped links including determining a number of out-going edges of a source as an upper bound of the network capacity. ### Claim 12 (depends on 10) The method according to claim 10, wherein one bit of information of the k-bit key is represented by a rank of a matrix of the encoded k-bit key that is transmitted. ### Claim 13 (depends on 10) The method according to claim 10, wherein depending on a state of a bit of the k-bit key, the bit is sent to either a random matrix generator or a zero matrix generator. ### Claim 14 (depends on 10) The method according to claim 10, further comprising: generating a parity check matrix of a maximum rank distance code; and performing a product of an output of a random matrix generator and a zero matrix generator. ### Claim 15 (depends on 10) The method according to claim 10, further comprising: decoding the encoded key from received matrix from the network using a rank metric. ### Claim 16 (depends on 15) The method according to claim 15, the method further comprising: generating an estimate using a rank metric from the matrix received from the network; and testing a rank of a second matrix from a reduction of the matrix from the network in order to output the decoded key. ### Claim 17 A computer program product for encoding and decoding, the computer program product comprising a non-transitory computer readable storage medium having program instructions embodied therewith, the program instructions readable and executable by a computer to cause the computer to: generate a k-bit key, where k is a positive integer; estimate a network capacity; encode each bit of the k-bit key using a random matrix of a selected rank and the estimated network capacity; and transmit the encoded k-bit key through a network that performs linear operations on packets, such that the k-bit key is protected against adversaries within the network, wherein the estimate of the network capacity includes estimating an upper bound of a number of eavesdropped links. ### Claim 18 (depends on 17) The computer program product according to claim 17, the program instructions further causing the computer to use a universal secure network code to generate the encoded key, wherein the estimate of network capacity includes estimating the upper bound of the number of eavesdropped links including determining a number of out-going edges of a source as an upper bound of the network capacity. ### Claim 19 (depends on 17) The computer program product according to claim 17, wherein one bit of information of the k-bit key is represented by a rank of a matrix of the encoded k-bit key that is transmitted, wherein depending on a state of a bit of the k-bit key, the bit is sent to either a random matrix generator or a zero matrix generator, and wherein, the program instructions further causing the computer to decode the encoded key from received matrix from the network by using a rank metric.