Designs And Analyses Of Post Quantum Cryptography Over Lattices

With the continuous development of quantum information technology and quan-tum computer,some classical mathematical difficult problems,such as factoriza-tion problem,discrete logarithm problem,exist quantum algorithm with poly-nomial time to solve,so the security of traditional public key cryptography al-gorithm is also greatly challenged.The analysis and design of cryptosystem which can resist the attack of quantum computer has become a hot research field in cryptography.At present,the cryptographic system which can resist the attack of quantum computer is divided into two categories:one is the crypto-graphic system based on the difficult problem of mathematics,the other is the cryptographic system based on quantum mechanics.We call the cryptosystem designed to resist quantum computer attacks based on mathematical difficul-ties as post-quantum cryptosystem.At present,the mathematical dificulties used in the post-quantum cryptosystem mainly include:lattice-based difficult problems,multivariable-based difficult problems,coding-based difficult problem-s,super-singular homologous elliptic curve problems,and one-way(Hash)func-tions.We mainly study the lattice-based post-quantum cryptosystem and quan-tum mechanics-based cryptosystem.In this paper,the following three kinds of problems are considered:1.Lattice-based homomorphic signature scheme;2.Lattice-based watermarking pseudo-random function scheme;3.A signature scheme based on quantum mechanics.Lattice-based homomorphic signature scheme:In recent years,with the rapid development of cloud computing,more people are willing to let the data storage and computing in cloud servers.Because of the powerful computing power of cloud,this method greatly improves production efficiency and saves computing resources,but it also brings a series of security and privacy protection problems.When the data is uploaded directly to the cloud,the user will appear powerless in the face of a malicious cloud.When the data is encrypted and uploaded to the cloud,the cloud can not complete the calculation process required by the user.In order to solve this series of problems,homomorphic cryptographic scheme was born.The cryptographic scheme with homomorphic property allows the user to upload his encrypted/signed data to the remote server,and then use the computing power of the server to help him process the data without worrying about data disclosure.Gorbunov,Vaikuntanathan and Wichs proposed the first leveled FHS schemes based on SIS problem in standard lattices.They put forward a new primi-tive:HTDF.They required that HTDF functions have claw-freeness property,which is necessary for the security of their FHS schemes.Their FHS schemes are existentially unforgeable in the static chosen-message-attack(EU-sCMA)mod-el.Recently,Boyen,Fan and Shi also brought up a EU-aCMA secure FHS schemes using vanishing trapdoor technique.In the meantime,Xie and Xue showed that leveled FHS schemes can be constructed if indistinguishability ob-fuscation and injective one way funnction exist.Wang et al.proposed the first leveled strongly-unforgeable IBFHS schemes.They construct an IBHTDF which is not only claw-free,but also collision-resistant.They use Barrington's theo-rem to reduce the parameters as done in field of FHE.The maximum noise-level comparing to Gorbunov,Vaikuntanathan and Wichs' FHS roughly reduces from O(md?p)to O(4dm?),which will result in polynomial modulus q=poly(?)when d=O(log?),where A is the security parameter and d is the maximum depth of admissible circuit.In this paper,we provide a new IBHTDF and construct a leveled IBFHS based on our IBHTDF.Our new IBFHS scheme is existentially unforgeable in the stat-ic chosen-message-attack(EU-sCMA).To evaluate a circuit g of depth d for our new HTDF,the maximum noise level of our algorithm is O(2d?).The homo-morphic operation algorithm for the original HTDF require the invert operation of G which makes the the nose level increasing m multiples.A permutation branching program is used in[73]for evaluating a circuit g of depth d for a new HTDF,that reduce the maximum noise level from O(md?)to O(4dm?).While,the multiplication operation for our new HTDF does not need invert operation of any matrix.The noise level for our new HTDF of multiplication gate is the same as that of addition gate.So,our noise level should be optimal.We use a special trapdoor generator which can generates a public matrix with trapdoor for any identity and the function f to construct a new IBHTDF.The new IBHTDF could satisfy claw-free and collision-resistant.Finally,we construct a new lev-eled strongly-unforgeable identity-based fully homomorphic signature(IBFHS)schemes based on our IBHTDF.The maximum noise-level comparing to Wang's FHS roughly reduces from O(4dmp)to O(2d?).Watermarking PRFs from Lattices:A software watermarking scheme en-ables a user or an authority to embed a "mark" within a program in a way that the marked program behaves almost identically to the original program.It should be difficult to remove the watermark from a marked program without significant-ly altering the program's behavior,and moreover,it should be difficult to create new(or malformed)programs that are considered to be watermarked.The first property of unremovability is useful for proving ownership of software(e.g.,in applications to digital rights management)while the second property of unforge-ability is useful for authenticating software(e.g.,for proving that the software comes from a trusted distributor).Barak et al.and Hopper et al.proposed the first rigorous mathematical frame-work of watermarking schemes.These works are difficult to adapt to stronger security requirements.Early works in this area gave very partial results showing that certain cryptographic functions can be watermarked,but security only held against restricted adversaries with limited ability to modify the program.The first watermarkable PRF scheme was constructed by Cohen et al.Their construction are based on IO an d can be achieved secret marking and public ex-traction,where the unremovability property holds even if the adversary has access to the marking oracle.Later,Yang et al.improve the scheme to achieve collusion resistance.The first watermarkable PRF scheme from standard assumptions was constructed by Kim and Wu.In their scheme,both the marking and the extrac-tion procedures are secret,but the unremovability security property only holds if the adversary has access to the marking oracle.Subsequently,watermarkable PRFs with public marking and extraction queries have been constructed.None of the above-mentioned schemes(from standard assumption)meets the desirable security requirements such as public extraction and collusion resistance.Yang et al.provide a generic construction that upgrades a watermarkable PRF with-out collusion resistance to a collusion resistant one.In addition,the security properties of the original scheme can be preserved.In this paper,we construct a watermarkable pseudorandom function scheme based on standard assumptions.For the first time,our scheme can meet the secu-rity requirements of both public extraction and collusion resistant.We creatively delimit the output of the function as two parts,the first part as a pseudorandom function,the latter part as an auxiliary function,used for auxiliary watermarking,extraction and other operations.Based on this special output structure,we define the feature of functionality preserving so that the function after watermark is no longer required to be almost the same as the function output before watermark on the premise of satisfying the security requirements.We only require that the first part of the output should satisfy functionality preserving,the latter part of the auxiliary function is not required.Not only that,we give a new watermark extraction procerss,our process does not need additional auxiliary information,so our scheme can achieve public extraction.For the security requirement of col-lusion resistant,we take advantage of the feature that the constrained signature can not be forged by combining it with the previous output.Compared with the Yang scheme,our implementation is more concise and efficient.Quantum Digital Signature:The security of classical digital signature are based on difficult mathematical problems.With the development of quantum al-gorithms,these difficult mathematical problems may become easy to solve.For-tunately,Gottesman and Chuang put forward quantum digital signature(QDS),whose security is based on the fundamental principles of quantum mechanics.The early schemes require that complex quantum states be prepared in advance,and these states need to be stored in quantum memory,which make these schemes impractical.Then,many new QDS schemes without quantum memory are pro-posed in succession.With the update of quantum technology,some QDS schemes can be implemented on QKD systems.The security of signing a single-bit mes-sage is unconditionally secure against most existing methods of attack.However,it is not secure to use these schemes directly for multi-bit messages without any preprocessing.A malicious participant can forge a new signature by intercepting part of the legitimate signature.For example,Alice sends a message-signature pair(Don't pay Bob 10$ Sig(Don't)Sig(pay)Sig(Bob)Sig(10$))to Bob.When Bob receives this message-signature pair,he can get a new valid message-signature pair(Pay bob 10$ Sig(pay)Sig(Bob)Sig(10$)),then sends to Charlie.It is clear.that Charlie will accept the signature,which means that Bob successfully forged a valid signature.Recently,T.Y.Wang et al.has given a solution to the above problems,which is to set a predetermined label for signature and put all the signatures in a sequence.In addition,a special kind of coding of the message is carried out,which makes the truncation attack impossible to implement.However,their scheme requires more than twice as many bits to sign a multi-bit message,which has a great impact on practical eficiency.Based on the construction framework,we propose a new coding scheme,which increase the efficiency of our scheme by 25%compared with the previous scheme.In our scheme,we encode 0 to 0 and 1 to 01.And then we add a special codeword 11 to the start and 10111 to the end of the codeword sequence.For example,we will encode a message 1010 to 11||01||0||01||0||10111.In T.Y.Wang et al.,they encode 0 to 00 and 1 to 01,and add a special codeword 11 at the beginning and end.For example,they will encode a message 1010 to 11|01||00||01||00||11.Obviously,the signature keys needed for a n bit message are 2n+4.But in our scheme,if the message is all 0 bits,then we just need n+7 signature keys for a n bit message which is 50%more efficient than T.Y.Wang's work.Generally speaking,the number of 0 bits and 1 bits in the message is roughly the same,and our scheme needs 1.5n+7 signature keys,which is 25%more efficient than the previous scheme.