Advanced bitflip: threat-adjusted, quantum-ready, battery-friendly, application-rich cipher

• US 10,541,808 B2
• Filed: 01/22/2019
• Issued: 01/21/2020
• Est. Priority Date: 01/21/2018
• Status: Active Grant

• Current Assignee: Gideon Samid
• Original Assignee: Gideon Samid
• Inventors: Samid, Gideon
• Primary Examiner(s): Siddiqi, Mohammad A
• Application Number:
  US16/253,911
• Publication Number:
  US 20190229894A1
• Time in Patent Office: 364 Days
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• 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/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0852 Quantum cryptography transmission systems employing electromagnetic waves other than radio waves, e.g. light, infrared H04B10/00; wavelength-division multiplex systems H04J14/02; WDM arrangements H04J14/03
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

Generally ciphers project a fixed measure of security, defined by the complexity of their algorithms. Alas, threat is variable, and should be met with matching security. It is useless to project insufficient security, and it is wasteful and burdensome to over-secure data. Advanced BitFlip comes with threat-adjustable flexibility, established via: (i) smart decoy strategy, (ii) parallel encryption, (iii) uniform letter frequency adjustment—tools which enable the BitFlip user to (a) adjust its ciphertexts to match the appraised threat, and (b) sustain security levels for aging keys. The use of these threat-adjusting tools may be automated to allow (1) AI engines to enhance the security service of the cipher, and (2) to enable remote hard-to-access IoT devices to keep aging keys useful, and preserve precious energy by matching security to the ad-hoc threat level. BitFlip may also be operated in a zero-leakage mode where no attributes of a conversation are disclosed, up to full steganographic levels. BitFlip security is two-dimensional: intractability and equivocation, both may be conveniently increased to meet quantum cryptanalytic attacks.

Claims

1. A method for secret communication and for mutual authentication among transmitting parties belonging to a secret-sharing group, wherein a secret communication of a message M written in an alphabet A comprised of t letters:

{a₁, a₂, . . . a_t} where transmitting party and recipient party share a secret key K comprised of t bit strings k₁, k₂, . . . k_t each comprised of n bits, and t positive integers f₁, f₂, . . . f_t where 0≤

f_i≤

n, for i=1, 2, . . . t, and where the transmitting party transmits the q letters in M in sequence m₁, m₂, . . . m_j, . . . m_q letter by letter such that letter m_j (j=1, 2, . . . q) written as letter a_i of the alphabet A is communicated to the recipient by the transmitter sending to the recipient string c_j which is generated by a flip action defined as flipping f_i bits in k_i, then conducting a no equivocation test where one tests that for all l≠

i the Hamming distance between c_j and k_i is not equal to f_l;

if the test fails the transmitting party repeats the flip action with different choice of f_i bits to flip, then conducting the “

no equivocation test”

on the new output string of the flip action, c_j,

and repeating this loop until the no equivocation test does not fail, in which case c_j is transmitted to the recipient party;

repeating the same for j=1, 2 . . . q the entire message M is transmitted to the recipient party,

and where the recipient party, receiving the sequence c₁, c₂, . . . c_j, . . . c_q, is extracting the corresponding value of a_i for each c_j by finding for each c_j for j=1, 2, . . . q the letter a_i where the corresponding string k_i has a Hamming distance f_i with c_j, while for all l≠

i the Hamming distance between c_j and k_l is not equal to f_l,

and where any party in the secret-sharing group will authenticate itself to any other party in the secret-sharing group, regarded as an authenticator, where the party to be authenticated is regarded as an authentication-candidate, and where all parties in the secret-sharing group share a secret comprised of an n-bits long string K_a and a secret integer s≤

n, and whereby the authentication candidate will randomly flip s bits in K_a to generate an authentication candidate string R, and then send the R candidate string to the authenticator to evaluate (i) that the Hamming distance between R and K_a is s, H(R,K_a)=s, and (ii) that the Hamming distance between R and each and every authentication string used previously, is larger than a threshold distance d;

failing either test the authenticator will reject R as a proof of the identity of the authentication candidate, and then the authenticator will instruct the authentication candidate to try with another, candidate string, R′

, and try again, until both tests (i, ii) for authentication are satisfied.

2. The method of claim 1, to immerse a message M in a larger bit stream L by the transmitting party sending to the recipient party a false letters comprised of n bits strings, x, where the Hamming distance between x and k_i for i=1, 2, . . . t is not equal to f_i, or there are at least two letters a_i and a_j in A for which the Hamming distance between x and k_i is equal to f_i, and the Hamming distance between x and k_j is equal to f_j;

the recipient party, following the protocol in claim 1, will not be able to evaluate x to any letter in A, and conclude x to be the false letters;

any party outside the secret-sharing group will regard that string as representing some letter from the A alphabet.