Effective concealment of communication pattern (BitGrey, BitLoop)

• US 10,673,822 B2
• Filed: 11/19/2019
• Issued: 06/02/2020
• Est. Priority Date: 06/22/2018
• Status: Active Grant

• Current Assignee: Gideon Samid
• Original Assignee: Gideon Samid
• Inventors: Samid, Gideon
• Primary Examiner(s): Holder, Bradley W
• Application Number:
  US16/687,690
• Publication Number:
  US 20200112548A1
• Time in Patent Office: 196 Days
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: H04L 63/0407 wherein the identity of one or more communicating identities is hidden cryptographic mechanisms or cryptographic arrangements for anonymous credentials or for identity based cryptographic systems H04L9/00
• CPC Class Codes: H04L 63/0471 applying encryption by an intermediary, e.g. receiving clear information at the intermediary and encrypting the received information at the intermediary before forwarding
• CPC Class Codes: H04L 9/0656 Pseudorandom key sequence combined element-for-element with data sequence, e.g. one-time-pad [OTP] or Vernam's cipher
• CPC Class Codes: H04L 9/0836 using tree structure or hierarchical structure
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/0897 involving additional devices, e.g. trusted platform module [TPM], smartcard or USB
• CPC Class Codes: H04L 9/12 Transmitting and receiving encryption devices synchronised or initially set up in a particular manner
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

This invention establishes a protocol designed to mask the communication pattern that prevails within a group or a community, such that an outside observer has no knowledge as to who talks to whom within the protocol protected group, not how often, nor how much, or whether any communication takes place. Thereby an external observer is denied the intelligence borne in the very pattern of group communication.

Claims

1. A method utilizing a combination of encrypted message data and additional randomized bits to both secure and conceal communications between communication stations, comprising;

organizing a plurality of communication stations in a distributed configuration;

transmitting, by a communication station of the plurality of communication stations to another targeted communication station of the plurality of communication stations, an encrypted meaningful message, this transmitted encrypted meaningful message appearing as random bits to an outside observer or eavesdropper;

actively preventing an outside observer or eavesdropper from identifying the transmitting communication station of the encrypted meaningful message by preventing an outside observer or eavesdropper from distinguishing between this transmitted encrypted meaningful message appearing as random bits, and additional transmitted random bits that are transmitted in the same interval of time between the remaining communication stations out of the plurality of communication stations, by having all the remaining communication stations out of the plurality of communication stations transmit random bit strings to randomly selected communication stations out of the plurality of communication stations, these random bit string transmissions occurring at random points of time; and

actively preventing an outside observer or eavesdropper from identifying the targeted communication station of the plurality of communication stations that receives the encrypted meaningful message appearing as random bits to an outside observer or eavesdropper, by having the encrypted meaningful message appearing as random bits also transmitted to all the remaining communication stations out of the plurality of communication stations in addition to targeted communication stations, with the remaining communication stations out of the plurality of communication stations determining that the encrypted meaningful message is not intended for them based on content of the encrypted meaningful message, and additionally having all the communication stations out of the plurality of communication stations transmit random bit strings at the same interval of time to randomly selected communication stations out of the plurality of communication stations, these random bit string transmissions occurring at random points of time.

2. The method of claim 1, wherein a cipher utilized for encryption and decryption is a decoy tolerant cipher, in which a recipient of a ciphertext stream can distinguish between bits that represent encrypted plaintext and bits that are random and carry no message.

3. The method of claim 1, wherein a cipher utilized for encryption and decryption is a composite cipher, in which a ciphertext C* may be decrypted to an arbitrary number t of corresponding plaintexts P₁, P₂, . . . P_t, with each plaintext P_i, i=1, 2, . . . t computed via a respective key K_i:

P_i=Decryption(C*, K_i).

4. The method of claim 1, wherein an encrypted message in a form of a bit string is passed from one communication station to other communication stations, but only intended target communication stations of the encrypted message decrypt the encrypted message, while non-targeted communication stations treat the encrypted message as a random stream of bits.

5. The method of claim 1, wherein messages are posted on a public ledger, all communication stations download contents of the public ledger, with each communications station identifying public ledger messages intended for itself, and decrypting an identified message intended for itself.

6. A communications system configured to utilize a combination of encrypted message data and additional randomized bits to both secure and conceal communications between communication stations, comprising;

a plurality of s communication stations, each comprising a hardware processor and memory;

wherein the plurality of s communication stations are organized in a fixed circular configuration of −

1,2,3, . . . s,1−

;

each communication station configured to;

transmit messages to the next communication station in the circular configuration, in a fixed order, at a fixed circular flow rate of a bit package of C bits per round around the circular configuration, comprised of R random bits per round plus M message bits per round around the circular configuration, the M message bits per round also appearing as random bits that are indistinguishable to an outside observer or eavesdropper from the R random bits per round;

wherein each communication station'"'"'s transmitted M message bits per round are comprised of messages to any other of the plurality of communication stations;

each communication station further configured to;

actively prevent an outside observer or eavesdropper that sees the overall flow of the bit package of C bits per round, from being able to identify how many of these C bits per round are meaningless, randomized, or represent a meaningful message, by configuring the transmitted messages between communication stations, to comprise R random bits plus M message bits, where these M message bits also appear as random bits to an outside observer or eavesdropper,

actively prevent an outside observer or eavesdropper that sees the overall flow of the bit package of C bits per round, from being able to identify a communication station that transmits data to another communication station, a communication station that receives data from another communication station, the frequency of when data is transmitted between communication stations, and/or the amount of data that is transmitted between communication stations, by configuring the transmitted messages between communication stations, to comprise R=C−

M random bits plus M message bits and to keep a fixed flow rate of C bits per round, where these M message bits also appear as random bits to an outside observer or eavesdropper; and

pass each bit package to the next communication station in the circular order, until each bit package returns to the communication station that submitted the returned bit package for circulation, at which time the communication station that submitted the returned bit package for circulation, replaces the returned bit package with a replacement bit package comprised of a different combination of M bits and R bits;

wherein each communication station is configured to detect any message intended for it, and to properly decrypt it.

7. The system of claim 6, wherein every communication station contributes C bits per round to the circular flow, and replaces the C bits per round sent in a previous cycle with new C bits per round, and where in case a communication station wishes to send no message to another communication station, the sending communication station uses a source for random bits to construct its refreshed flow of C bits per round;

and if the sending communication station wishes to send a message m to another communication station, the sending communication station encrypts m to a ciphertext of size |m|, and constructs the next round of C bits per round from m plus C−

|m| random bits.

8. A method utilizing a combination of encrypted message data and additional randomized bits to both secure and conceal communications between communication stations, comprising;

organizing a plurality of s communication stations in a fixed circular configuration of −

1,2,3, . . . s,1−

;

transmitting messages from a communication station to the next communication station in the circular configuration, in a fixed order, at a fixed circular flow rate of a bit package of C bits per round around the circular configuration, comprised of R random bits per round plus M message bits per round around the circular configuration, the M message bits per round also appearing as random bits that are indistinguishable to an outside observer or eavesdropper from the R random bits per round;

wherein each communication station'"'"'s transmitted M message bits per round are comprised of messages to any other of the plurality of communication stations;

actively preventing an outside observer or eavesdropper that sees the overall flow of the bit package of C bits per round, from being able to identify how many of these C bits per round are meaningless, randomized, or represent a meaningful message, by transmitting messages between communication stations that comprise R random bits plus M message bits, these M message bits also appearing as random bits to an outside observer or eavesdropper,

actively preventing an outside observer or eavesdropper that sees the overall flow of the bit package of C bits per round, from being able to identify a communication station that transmits data to another communication station, a communication station that receives data from another communication station, the frequency of when data is transmitted between communication stations, and/or the amount of data that is transmitted between communication stations, by transmitting messages between communication stations that comprise R=C−

M random bits plus M message bits and by keeping a fixed flow rate of C bits per round, these M message bits also appearing as random bits to an outside observer or eavesdropper; and

passing each bit package from a communication station to the next communication station in the circular order, until each bit package returns to the communication station that submitted the returned bit package for circulation, at which time the communication station that submitted the returned bit package for circulation, replaces the returned bit package with a replacement bit package comprised of a different combination of M bits and R bits;

wherein each communication station detects any message intended for it, and properly decrypts it.

9. The method of claim 8, wherein the number of bits transmitted per second in the circular flow is kept constant regardless of the ratio between message bits as compared to random bits.

10. The method of claim 8, wherein a cipher utilized for encryption and decryption is a decoy tolerant cipher, in which a recipient of a ciphertext stream can distinguish between bits that represent encrypted plaintext and bits that are random and carry no message.

11. The method of claim 8, wherein a cipher utilized for encryption and decryption is a composite cipher, in which a ciphertext C* may be decrypted to an arbitrary number t of corresponding plaintexts P₁, P₂, . . . P_t, with each plaintext P_i, i=1, 2, . . . t computed via a respective key K_i:

P_i=Decryption(C*, K_i).

12. The method of claim 8, wherein an encrypted message in a form of a bit string is passed from one communication station to other communication stations, but only intended target communication stations of the encrypted message decrypt the encrypted message, while non-targeted communication stations treat the encrypted message as a random stream of bits.

13. The system of claim 8, wherein every communication station contributes C bits per round to the circular flow, and replaces the C bits per round sent in a previous cycle with new C bits per round, and where in case a communication station wishes to send no message to another communication station, the sending communication station uses a source for random bits to construct its refreshed flow of C bits per round;

and if the sending communication station wishes to send a message m to another communication station, the sending communication station encrypts m to a ciphertext of size |m|, and constructs the next round of C bits per round from m plus C−

|m| random bits.