New Constructions And Applications Of Post-Quantum Key Exchange Protocol From RLWE Problem

Large-scale quantum computer and efficient quantum algorithms are believed to break various current public key cryptography algorithms,e.g.the ones that built based on discrete logarithm problem,integer factorization problem,elliptic curve discrete logarithm problem etc.Moreover,such computer and algorithms are believed to reduce the security of symmetric cryptography algorithms as well.With the surge of research and development of quantum computers,current public key algorithms are under imminent threats.As we all know,various public key algorithms and symmetric algorithms are deployed in real world applications,protocols and devices.These public key algorithms including(but not limit to):public key encryption,key exchange,digital signature etc.Important security protocols and applications are at risk as well,including:HTTPS,SSH,system security,blockchain,Internet of Things(IoT)etc.Shor's algorithm and Grover's algorithms post significant threats to public and symmetric cryptography algorithm respectively.More importantly,Shor's algorithm is tricker since it posts great threat to public key cryptography algorithms.This demands cryptography researchers to propose countermeasures,namely the Post-quantum Cryptography,which focus on designing new algorithms that can resist attacks from classic and quantum computers.Major technical approaches to realize post-quantum cryptography are:hash-based,code-based,multivariate-based,lattice-based etc.Each of them has its own pros and cons.Most people believe that lattice-based schemes can achieve higher security level,smaller communication cost,faster computation speed and more versatile cryptography construc-tions.National Institute of Standards and Technology(NIST)is currently working on selecting new algorithms for the upcoming post-quantum world,which mainly focus on public key encryption,key establishment and digital signature.Ring Learning with Errors(RLWE)is a new lattice-based hard problem.This thesis focuses on the design,analysis,implementation and application of unauthenticated and augmented password-based authenticated key exchange protocols from RLWE problem.The first part is to design new unauthenticated key exchange protocols from RLWE problem.Real-world security protocols and applications require truly efficient unauthen-ticated key exchange protocols with high security and small communication cost,which are major technical challenges for cryptographers.An important technique to realize key exchange over RLWE problem is error reconciliation.This allows both parties to derive same shared key over approximately equal elements,therefore it is of great importance to understand what is the framework of key exchange schemes over RLWE problem and im?plement error reconciliation.Then,we choose practical parameters with security analysis and implement the protocol efficiently.Finally,we compare with related works.These are major research topics in this field.We start with a comprehensive comparison analysis on various primary RLWE-based key exchange protocols,including:details of protocol design,differences in error recon-ciliation mechanisms,error tolerance,parameters,security level,implementation etc.We present two different instantiations of the DING12 RLWE key exchange protocol that achieve more than 300 and 200-bit security respectively.The new efficient implementa-tion introduced in this thesis gives more than 10 times performance boost over similar works and the complete key exchange computation can be done around 0.1ms.We also compare RLWE-based key exchange protocols with classic key exchange protocols over various aspects.We show the computation and communication efficiency of these proto-col and security level.This paves the way for designing new RLWE-based key exchange protocols.Following the results from comparison analysis section,we construct new ephemeral-only Diffie-Hellman-like key exchange protocol from RLWE + Rounding.We also present parameters,new techniques to estimation security level of parameters,passive security proofs and practical implementation.The communication cost of our new protocol is at least 25%smaller than the protocols that only rely on RLWE problem.Compare with similar works that enjoys similar security level,communication cost of our protocol is at least 10%smaller.Our new protocol achieves a better tradeoff between security level,computation and communication cost.In addition,the new security estimation technique converts RLWE + Rounding instance to SIS instance,then evaluate the security/complex-ity using most efficient lattice reduction algorithms.Our new estimation technique also fill the gap where no existing work can precisely estimate the security level of only one RLWE+ Rounding sample.Next,we propose another new RLWE-based key exchange protocol to defend active attacks when public/private key pair is reused.We present protocol construction,parame-ters,security level estimation,results of NIST randomness test and efficient implementa-tion.With same attack and reused keys,transcripts of the new protocol is indistinguishable from uniform random.This clearly distinct from vulnerable protocols,therefore private key cannot be recovered.The new protocol has two modes:regular mode and key reuse mode.In fact,the performance of key reuse mode is at least multiple times faster than relat ed vulnerable works.This work fills the gap that no current RLWE-based ephemeral-only Diffie-Hellman-like key exchange protocol can resist to such active attackThe second part focuses on designing augmented password-based authenticated key exchange protocol,which is also very demanding towards the upcoming post-quantum world.The Secure Remote Password(SRP)protocol,which is an augmented password based authenticated key exchange protocol,is deployed in various internet services in cluding Apple iCloud,1 Password,ProtonMail,TLS etc.cannot resist to quantum attacks Therefore,it is of great importance to design post-quantum SRP variant.SRP makes the following novel security properties possible,including:server does not need to store us er password(or hash value),adversary cannot impersonate as legit user even if server database is leaked,user do not need to send actual password(or hash value)to server etcWe propose a RLWE-based SRP variant for the post-quantum world.We start by attempting to merge the benefits from both RLWE-based key exchange and SRP protocol The new RLWE-SRP protocol is resistant to quantum attacks,as well as inherits novel security properties from original SRP protocol.We present protocol construction,209-bit secure parameters,security analysis,efficient implementation and comparnson analysis between original SRP protocol,non-augmented classic/post-quantum password-based au thenticated key exchange protocols on their security,performance and communication cost.Compare with non-augmented PAKE protocol from RLWE problem,our new con struction gives better security and smaller communication cost.Moreover,computation speed is nearly 14 times faster.Compare with classic SRP protocol,our new protocol achieves better security level and more than 3 times faster computation speed.