Abstract:
A method for reconciling bit strings over a communications network. A first subscriber ascertains error correction information for each one of a plurality of different blocks, which each include a predetermined number of bits from a first bit string, and transmits the same over the communications network. Each of the blocks having at least one bit in common with at least one other one of the blocks.

Description:
CROSS REFERENCE 
       [0001]    The present application claims the benefit under 35 U.S.C. §119 of German Patent Application No. DE 102015211817.7 filed on Jun. 25, 2015, which is expressly incorporated herein by reference in its entirety. 
       FIELD 
       [0002]    The present invention relates to a method for reconciling bit strings over a communications network, as well as to a processing unit and a computer program for implementation thereof. 
       BACKGROUND INFORMATION 
       [0003]    What is generally referred to as the Internet of Things, i.e., an internetworking of various devices, is becoming increasingly widespread. One of the main applications of the Internet of Things is commonly referred to as the smart home, where many devices are battery-powered and are connected via a wireless link to a central station with which they can communicate. 
         [0004]    For a secure communication over the generally unsecured wireless links, the subscribers can use conventional keys, for example. One option for generating a key shared by two subscribers is generally referred to as a physical layer key generation (PHYSEC), for example. A shared key is generated from physical properties of a channel in the wireless link between the two subscribers. Such a method is described, for example, in German Patent Application No. DE 10 2014 212 224. 
         [0005]    Such a key must be reconciled between the subscribers in order to rectify any potential errors created during generation thereof. 
       SUMMARY 
       [0006]    The present invention provides a method for reconciling bit strings over a communications network, as well as a processing unit and a computer program for the implementation thereof. Advantageous embodiments are described below. 
         [0007]    An example method according to the present invention relates to the reconciliation of bit strings over a communications network. A first subscriber thereby ascertains error correction information for each one of a plurality of different blocks, which each include a predetermined number of, in particular, successive bits from a first bit string, and transmits the same over the communications network. Each of the blocks has at least one bit in common with at least one other one of the blocks. 
         [0008]    This leads to a low energy consumption which is especially desirable in battery-powered devices. Also, as little as possible information is thereby divulged to a third party via the key. 
         [0009]    Such a bit string may, in fact, also be subdivided into successive blocks of a predetermined number of bits, for example, i.e., the bit string is subdivided into blocks having bits  0  through  7 ,  8  through  15 , etc., a parity bit then being transmitted for each of the blocks to be able to identify errors in the bit string. In response to detection of an error in a block, the block in question may then be divided again, for example, and parity bits may be transmitted, in turn, for these two, then smaller blocks. The blocks may continue to be subdivided in this manner. However, a great deal of information must be thereby exchanged between two subscribers since the transmitter must know in which block the receiver still currently has an error. In addition, the blocks must also be permuted many times, for example, by omitting another bit of a block with every permutation. This is because only an odd number of bit errors may be detected when just one parity bit is used. This requires a pseudo-random number generator, for example. The result is a very high transmission volume, where, on the other hand, a great deal of energy is expended and, on the other hand, a great deal of information on the bit string is divulged. Thus, a back computation to a possible bit string could be performed from the parity bits. Such a method for reconciling a bit string is described, for example, in Gilles Brassard and Louis Salvail, “Secret-Key Reconciliation by Public Discussion” in  Advances in Cryptology —EUROCRYPT &#39;93, pp. 410-423, Springer, 1994. 
         [0010]    On the other hand, the method according to the present invention now eliminates the need for such permutations because the at least one common bit of two different blocks provides for an overlapping, so that these two blocks do, in fact, have bits in common, but not all of the bits thereof are in common. Thus, when checking the particular blocks using the corresponding error correction information, errors may even be detected, which, for example, are not possible to detect in the case of only one block, without permutations, using one parity information bit (for example, parity or syndrome). The volume of data to be altogether transmitted is thereby very small, in particular significantly smaller than in the case of the previously mentioned method. For example, there is also no need for two subscribers to agree on a scheme for such permutations since both subscribers must perform identically. There is also no need for a pseudo-random number generator, for example, that would consume energy unnecessarily. This has the advantage, on the one hand, that little energy is consumed, which is particularly advantageous for battery-powered devices, and, on the other hand, that little information is divulged about the bit string, which may be used as a secret key shared by two subscribers, for example. 
         [0011]    It is advantageous if the different blocks each have a predetermined number of successive bits from the first bit string. This allows an especially simple and rapid selection of bits for the respective blocks, since, for example, successive bits in a memory may be selected, and there is no need to consider or compute any pattern or selection method. 
         [0012]    Preferably, all bits included altogether in all of the blocks include all of the bits of the first bit string. This makes it possible to ensure that the bit string of another subscriber may be completely checked, respectively corrected by the same. 
         [0013]    The blocks advantageously have start bits (i.e., the first bit of a block), which each correspond to bits of the first bit string that differ from one another. This allows the entire first bit string to be covered by a small number of blocks. Thus, the data volume to be transmitted is also reduced. 
         [0014]    It is advantageous if the start bits of two blocks, which are successive in accordance with the respective start bits thereof, are shifted in each case by a predetermined number of bits of the first bit string. On the one hand, this allows the overlap between two such blocks to be as small as possible; on the other hand, it allows sufficient overlap to still be present to enable the individual bits to be checked often enough. The number of blocks may be thereby further reduced. 
         [0015]    Preferably, the number of bits by which the start bits of two successive blocks is shifted, is individually specified for each pair of successive blocks in accordance with a predefined scheme or is the same for each pair. Thus, for example, a scheme that two subscribers, between which the bit strings are reconciled, know right from the start or, however, agree to before the start of the reconciliation, for example, may specify a number sequence indicating the spacing between the start bits of two successive blocks. Thus, the block may be alternately shifted by three and five bits. Because a shift is agreed upon in advance, no further communication effort ensues during the actual reconciliation. The parameters for the reconciliation may be easily negotiated among the subscribers beforehand. On the other hand, if a fixed number is specified, for example, three, then less computational effort is needed, and, in some instances, even less information needs to be divulged. 
         [0016]    The error correction information items are advantageously transmitted over the communications network in accordance with a predetermined sequence, which, in particular, is defined by the start bits of the particular blocks. Thus, for example, the individual error correction information items may be transmitted one after another, i.e., for example, initially for the first block, then for the second block, then for the third block, etc. This makes it possible to simply assign the error correction information of a receiver to the blocks of the bit string thereof. 
         [0017]    It is advantageous when the number of bits that each of the blocks includes is specified for each block in accordance with a predefined scheme or is the same for each block. Thus, for example, a scheme that two subscribers, between which the bit strings are reconciled, know right from the start or, however, agree to before the start of the reconciliation, for example, may specify a number sequence indicating the length of the blocks. Thus, the block may alternately be eight and twelve bits long, for example. On the other hand, if a fixed number is specified, for example, eight, then less computational effort is needed, and, in some instances, even less information needs to be divulged. In the case of a bit string of a 256 bit length, a block length of eight bits, and blocks spaced apart by three bits, a number of 83 correction information items to be transmitted results (one block, for example, the first or the last, then only having a length of seven bits). 
         [0018]    The error correction information items transmitted over the communications network are preferably received by a second subscriber, and the second subscriber checks and/or corrects a second bit string on the basis of the error correction information. As already mentioned, a simple, rapid and energy efficient reconciliation of bit strings between two subscribers may be performed in this manner in a communications network. The bit strings of the two subscribers, i.e., the first and the second bit string, normally have the same number of bits in this context. However, individual bits of the particular bit strings may deviate from one another. This must be corrected. 
         [0019]    The error correction information items advantageously include parity bits, check bits, forward error correction bits and/or syndrome bits. In the case of parity bits, it maybe recognized, for example, whether there is an odd number of incorrect bits. The overlapping of individual blocks, however, makes it possible to also recognize errors that are not possible to detect when working with only one block and parity bit. In the case of check bits in the form of a check sum, forward error correction bits or syndrome bits, for example, a suitable checking and correction may likewise ensue. A syndrome is constituted of a multiplication of a code by a check or control matrix, for example, whose result is only dependent on a possible error in the code and not on the code itself. It is, therefore, used for checking the code. 
         [0020]    It is advantageous if a radio communications network, such as a WLAN network, Bluetooth etc., is used as a communications network. It is at this point, in particular, that the present method is advantageous since radio communications networks are generally very unreliable and, in addition, are often used for networking many mobile, battery-powered devices where a low-energy communication is advantageous. For example, the communications network may be used in the context of the Internet of Things, in particular of what is generally referred to as a smart home. It is understood, however, that, in the use thereof, the present method is not limited to such communications networks, rather may be used for all possible types of networks, for example, also for wired networks or networks in vehicles or the like. 
         [0021]    At least a portion of the bits of the first bit string may preferably be used as the shared key for secure communication in the communications network. If reconciliation is successful, the second bit string corresponds to the first bit string. The present method is especially advantageous for generating a shared secret key since very little information is divulged during the normally necessary reconciliation. It is true that the entire bit string may thereby be used as a key, however, one or a plurality of start and end bits of the bit string may also be omitted when the key is used. This is useful, for example, when the start and end bits are less likely to be properly corrected than are the remaining bits, because the blocks are not able to overlap with other blocks there for checking. 
         [0022]    The bit strings are advantageously ascertained from the physical properties of the communications network, in particular of a channel of the communications network existing between a first and a second subscriber. For this purpose, a bit string may be generated by each subscriber from a physical property, such as from a transmit/receive power in a channel of a radio communications network between two subscribers, for example. For that purpose, the transmit/receive power may be simultaneously ascertained by each of the two subscribers at certain time intervals, for example, and, depending on the strength, i.e., whether it is above or below a threshold value, for example, associated with a bit  1  or  0 . However, since such a channel between two subscribers is generally not exactly identical in both directions with respect to the physical properties thereof, the bit strings, ascertained by the two subscribers, may differ from one another. It is exactly in such a situation that the present reconciliation method is especially rapid, simple and energy efficient. 
         [0023]    A processing unit according to the present invention, for example a (radio) transmitter and receiver unit, is adapted, in particular in terms of software engineering, for carrying out a method according to the present invention. Accordingly, the first subscriber or the second subscriber may, in particular, also be configured as such a processing unit. 
         [0024]    It is advantageous to implement the method as a computer program, since this entails especially low costs, particularly when an executing control unit is also used for other tasks and is, therefore, present anyway. Suitable storage media for providing the computer program include, in particular, magnetic, optical and electrical memories, for example, such as hard disks, flash memories, EEPROMs, DVDs, inter alia. A program may also be downloaded over computer networks (Internet, intranet, etc.). 
         [0025]    Other advantages and embodiments of the present invention are derived from the description and the appended drawing. 
         [0026]    The present invention is schematically illustrated in the FIGS. with reference to an exemplary embodiment and is described below with reference to the figures. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0027]      FIG. 1  schematically shows a communications network for implementing a method according to the present invention. 
           [0028]      FIG. 2  schematically shows a functional sequence of a method according to the present invention in a preferred specific embodiment. 
       
    
    
     DETAILED DESCRIPTION 
       [0029]      FIG. 1  schematically shows a communications network suited for implementation of a method according to the present invention. Communications network  100  may be a radio communications network, for example, a WLAN network. 
         [0030]    Communications network  100  thereby includes a first subscriber  200  and a second subscriber  300  that are able to communicate with one another via a channel  110  of communications network  100 . First subscriber  200  may thereby be a base station of a smart home network, which, accordingly, has a transmitter and receiver unit. 
         [0031]    Second subscriber  300  may be a subscriber in the smart home network, for example, that is supposed to fulfill a predetermined function, such as temperature measurement or the like. Second subscriber  300  may thereby be battery-powered, in particular, and, accordingly, also have a transmitter and receiver unit. 
         [0032]      FIG. 2  schematically shows a functional sequence of a method according to the present invention in a preferred specific embodiment. First subscriber  200  has a first bit string  201 . Second subscriber  300  has a second bit string  301 . These two bit strings  201  and  301  may thereby have been generated from physical properties of channel  110  of communications network  100 . The generation of such bit strings from physical properties of the channel was briefly described at the outset and is generally known. It is, therefore, not explained further in the following. 
         [0033]    The two bit strings  201  and  301  may thereby be preferably used as the shared secret key for a secure communication between first subscriber  200  and second subscriber  300  in communications network  100 . To this end, however, it is necessary to reconcile the two bit strings and, in some instances, to also correct one of the two bit strings. It is noted in this regard that bit string  301  differs exemplarily from bit string  201  in the fourth bit from the left. 
         [0034]    In a step S 1 , first subscriber  200  now selects a block  211  having a number of exemplarily eight bits, beginning with the first bit (from the left) of bit string  201 . 
         [0035]    Error correction information  221  is now ascertained for this block  211 , respectively for the bits of bit string  201  included in this block  211 . For example, this error correction information may be constituted of forward error correction bits, i.e., a code which makes it possible to correct the underlying bits of block  211 . 
         [0036]    This error correction information  221  is now transmitted to second subscriber  300  via communications network  100 . From second bit string  301  thereof, second subscriber  300  may select a block  311  exemplarily having a number of likewise eight bits, beginning with the first bit (from the left) of bit string  301 . 
         [0037]    The number of bits of block  311  and the start bit thereof with respect to bit string  301  thereby correspond to the corresponding values of block  211 . This number and the start bit may thereby be known to the two subscribers from the beginning, for example. 
         [0038]    Second subscriber  300  may now check block  311  thereof on the basis of error correction information  221 . For this purpose, it is possible to use what is generally referred to as a Hamming code having a length of eight and a distance of three, what is commonly referred to as a (8,3) Hamming code. Using such a code, it is possible to correct up to one error. 
         [0039]    For this, first subscriber  200  may generate a syndrome from the 8-bit code word thereof and send it to second subscriber  300 . In this case, the syndrome would be four bits long. It includes the information about the position where the one bit error is, allowing second subscriber  300  to use this error correction information to correct block  311  thereof at the fourth position, i.e., the fourth bit. 
         [0040]    In a step S 2 , first subscriber  200  now selects a block  212 , again having a number of exemplarily eight bits, from bit string  201 . The start bit of block  212  is thereby shifted exemplarily by three bits to the right relative to the start bit of the preceding block, i.e., block  211 , along the bit string. 
         [0041]    Error correction information  222  is now ascertained for this block  212 , respectively for the bits of bit string  201  included in this block  212 , as was already implemented for preceding block  211 . 
         [0042]    This error correction information  222  is now likewise transmitted to second subscriber  300  over communications network  100 . From second bit string  301  thereof, second subscriber  300  may now select a block  312  exemplarily having a number of likewise eight bits, beginning now with the fourth bit (from the left) of bit string  301 . 
         [0043]    The number of bits that the start bit of block  312  is shifted by relative to the start bit of the preceding block, i.e., block  311 , thereby corresponds to the number of bits that block  212  is also shifted by relative to block  211 . This number, by which the start bits of two successive blocks are shifted by may thereby be known from the beginning, for example, to the two subscribers. 
         [0044]    Second subscriber  300  may now check and correct block  312  thereof on the basis of error correction information  222 . 
         [0045]    In a step S 3 , first subscriber  200  selects a block  213 , again having a number of exemplarily eight bits, from bit string  201 . The start bit of block  213  is thereby again shifted to the right exemplarily by three bits relative to the start bit of the preceding block, i.e., block  212 , along the bit string. 
         [0046]    Error correction information  223  is now ascertained for this block  213 , respectively for the bits of bit string  201  included in this block  212 , as was already implemented for preceding block  211 . 
         [0047]    This error correction information  223  is now likewise transmitted to second subscriber  300  over communications network  100 . As also implemented in step S 2 , subscriber  300  may now select a current block, in the present case, block  313 , and, on the basis of current error correction information, in the present case, error correction information  223 , perform a check and correction. 
         [0048]    This method may now be continued until entire bit string  301  is checked and corrected. Both subscribers  200  and  300  then have the same bit string and may use it as a shared key. 
         [0049]    If the number of errors in block  311  does not exceed a specific limit for the selected error correction information, a correction is possible after only one single error correction information item. In some instances, a plurality of bit errors may occur, however, making a correction using a single error correction information item no longer possible. 
         [0050]    If, in the method presented here, the subsequent bits, i.e., bits  6 ,  7 ,  8  of block  312  are correct, then subscriber  300  may correct the errors in the leading bits (for example, in the two first bits of  312 ). If, on the other hand, successive blocks without any overlap were shifted, entire block  311 , respectively  211  would then have to be rejected after the reconciliation (due to the lack of agreement). 
         [0051]    In contrast, in the presented method, only the first three bits would have to be rejected or, alternatively, a repeated correction of block  311  following correction of block  312  may be attempted, after a portion of the erroneous bits in block  311  are replaced by the corresponding, already corrected bits from block  312 . 
         [0052]    It is also possible in this context that only a portion of the bit string is used as a key. For example, the first and last three bits, which each form the basis of an error correction information item only once and, therefore, are less trustworthy, may remain disregarded when the bit string is used as a key. 
         [0053]    It is understood that the numbers in the example for the length and the spacing apart of the blocks may also be differently selected and even also individually for individual blocks, respectively pairs of blocks. 
         [0054]    It should be noted that the roles of the two subscribers may also be interchanged, i.e., the second subscriber, for example, which checks and corrects the bit string thereof, may be a base station.