Optimized bit flipping key encapsulation post-quantum cryptographic method

Abstract

Optimized BIKE method comprising: setting system parameters and Hash functions; generating a public key ( ) and a private key ( ); encapsulating a message (m) into a ciphertext (c) using the public key, and computing a pseudo-message (K) using the message and the ciphertext; and, decapsulation the ciphertext using the private key to retrieve the pseudo-message. The method computes a product between first and second operands of a size n binary polynomial type by way of a pointwise product between first and second transformed operands resulting in an AFFT like function applied to the first and second operands respectively, so that at least one element among the first private element ({umlaut over (h)} 0 ) of the private key ( ) or the single public element ({umlaut over (h)}) of the public key ( ) is a vector in the AFFT domain.

1 . An optimized Bit Flipping Key Encapsulation post-quantum cryptographic method, implemented by first and second end points in order to share a message (m), the method comprising successively:
 setting system parameters and Hash functions;   generating, for the first end point, based on the system parameters and the Hash functions, a pair of keys, the pair of keys comprising a public key ( ) and a private key ( ), the public key being shared with the second end point;   encapsulating, by the second end-point, the message into a ciphertext (c) using the public key, computing a pseudo-message (K) using the message and the ciphertext, and transmitting the ciphertext (c) to the first end point; and,   decapsulation by the first end point the ciphertext using the private key to retrieve the pseudo-message;   the private key being made up of a first private element, a second private element and a third private element, and the public key being made up of a single public element,   the method involving at least one product between a first operand and a second operand, the first operand and the second operand each being a binary polynomial equivalent to a binary string of size n,   wherein the method computes the at least one product by way of a pointwise product between a first transformed operand and a second transformed operand, the first transformed operand resulting in an Additive Fast Fourier Transform—AFFT like function applied to the first operand and the second transformed operand resulting in the AFFT like function applied to the second operand, the first transformed operand and the second transformed operand each being a vector in an AFFT domain, said vector in the AFFT domain being equivalent to a binary string of size 2n, and in that at least one element among the first private element ({umlaut over (h)} 0 ) of the private key ( ) or the single public element ({umlaut over (h)}) of the public key ( ) is a vector in the AFFT domain.   
     
     
         2 . The optimized Bit Flipping Key Encapsulation post-quantum cryptographic method according to  claim 1 , wherein the AFFT like function is selected among a classical Additive Fast Fourier Transform, a Frobenius Fast Fourier Transform, a Truncated Additive Frobenius Fast Fourier Transform and the like. 
     
     
         3 . The optimized Bit Flipping Key Encapsulation post-quantum cryptographic method according to  claim 1 , wherein setting of global parameters consists in selecting a set of system parameters comprising the integers r, w, l and a set of Hash functions H, K, L; and wherein generating a pair of keys consists in generating (h 0 ,h 1 ) in the set  , and σ in the set  ={0,1} l , computing {umlaut over (h)} 1 =AFFT(h 1 ), 
       
         
           
             
               
                 
                   h 
                   0 
                   
                     
                       - 
                       
                         ¨ 
                       
                     
                     1 
                   
                 
                 = 
                 
                   AFFT 
                   ⁡ 
                   ( 
                   
                     h 
                     0 
                     
                       - 
                       1 
                     
                   
                   ) 
                 
               
               , 
             
           
         
       
       and {umlaut over (h)} 0 =AFFT(h 0 ), and setting the private key   as (({umlaut over (h)} 0 ,h 1 ),σ) and the public key   as 
       
         
           
             
               
                 
                   h 
                   ¨ 
                 
                 = 
                 
                   
                     
                       h 
                       
                         ¨ 
                       
                     
                     1 
                   
                      
                   ⊙ 
                      
                   
                     h 
                     0 
                     
                       
                         - 
                         
                           ¨ 
                         
                       
                       1 
                     
                   
                 
               
               ; 
             
           
         
       
       where ä=AFFT(a) is the transformed operand resulting in an Additive Fast Fourier Transform—AFFT like function applied to the operand a, ⊙ is the operator of the pointwise product,   is the set of the binary words having a size of n=2r bits, and   is the sub-set of   gathering the binary words having exactly w bits equal to 1. 
     
     
         4 . The optimized Bit Flipping Key Encapsulation post-quantum cryptographic method according to  claim 3 , wherein the encapsulation step consists in:
 computing (e 0 ,e 1 )=H(m), where m is the message, and ë 1 =AFFT(e 1 );   setting c 0 =e 0 +AFFT −1 (ë 1 ⊙{umlaut over (h)}) and c 1 =m⊕L(e 0 ,e 1 ), the ciphertext c being defined as (c 0 ,c 1 ); and,   defining a pseudo-message as K=K(m,c),   
       and wherein the decapsulation step consists in:
 computing {umlaut over (c)} 0 =AFFT(c 0 ); 
 generating e′=Decoder (AFFT −1 ({umlaut over (c)} 0 ⊙{umlaut over (h)} 0 ),h 0 ,h 1 ) and m′=c 1 ⊕L(e′); and, 
 if e′=H(m′), returning K=K(m′,c), otherwise returning K=K(σ,c). 
 
     
     
         5 . The system comprising a first end point ( 10 ) and a second end point, the system being adapted to realize an optimized Bit Flipping Key Encapsulation post-quantum cryptographic method according to  claim 1 . 
     
     
         6 . The smart card adapted to be used as the first end point in the system according to  claim 5  to realize the step of generating a pair of keys and the step of decrypting a ciphertext according to the optimized Bit Flipping Key Encapsulation post-quantum cryptographic method. 
     
     
         7 . The server adapted to be used as the second end point in the system according to  claim 5  to realize the step of encrypting a message to output a ciphertext according the optimized Bit Flipping Key Encapsulation post-quantum cryptographic method. 
     
     
         8 . A non-transient information recording medium, comprising programming providing instructions to instantiate all or any of the steps of an optimized Bit Flipping Key Encapsulation post-quantum cryptographic method according to  claim 1 , when those instructions are executed by a computing system.