Research On Lattice-based Digital Signatures Without Trapdoors

With the development of science and quantum information technology,the problem of information security has become increasingly prominent.How to protect the security of information systems has become a concern of the whole society and the core technology of these problems is cryptography.Cryptography can effectively protect the confidentiality,integrity and availability of information.A secure digital signature system can provide verifiability,unforgeability,non-repudiation,and integrity.With the development of electronic computers and networks,a variety of electronic applications have appeared,such as e-commerce,electronic money,electronic contracts,electronic voting,and so on.For these special application scenarios,basic digital signatures can no longer meet their needs.With the development of quantum algorithms and quantum computers,the security of traditional public key cryptography has suffered from huge flaws.Lattice is one of the leading research hotspots in post-quantum cryptography.Compared with other post-quantum cryptography,lattice has strong anti-quantum properties.Most of the lattice-based digital signature schemes are implemented by using Gaussian sampling or trapdoor technology.However,their computational efficiency and computational complexity need to be further improved.Focus on this problem,based on Lyubashevsky's rejection sampling technology,this thesis proposes several types of digital signature schemes without trapdoors.The main results are as follows:1.In order to overcome the problem that sampling technology has an impact on comput-ing efficiency,by using Lyubashevsky's rejection sampling technology,we construct an identity-based signature scheme without trapdoors on the lattice.Our scheme is based on the shortest vector problem on lattices,which neither Gaussian sampling nor trapdoor techniques are used.In the random oracle model,our scheme can be proved that it is strong existencially unforgeable on adaptive chosen messages and adaptive chosen identity attacks.The security level of our scheme is strong existencially un-forgeable,which is more secure than the existencially unforgery of other schemes.Compared with other effective schemes,our scheme has advantages in terms of com-putational complexity and security.2.Certificate-based public key cryptosystem is a reliable cryptosystem.Different from the traditional certificate-based cryptosystem,it does not exist the problem of certifi-cate management.It has neither the issue of key escrow in identity-based cryptpsys-tems nor the trust of certificateless cryptpsystems.With the development of quantum computation,it is of great significance to construct a certificate-based post-quantum public key cryptosystem.In Eurocrypt2012,Lyubashevsky proposed a lattice digi-tal signature scheme based on trapdoors.Based on the work of Lyubashevsky,we construct a certificate-based signature scheme without trapdoors on lattices.In the random oracle model,we prove that our scheme is strong unforgeable for adaptive chosen messages and chosen identity attacks.3.Threshold ring signatures are significant for ad-hoc groups such as mobile ad-hoc networks.Based on the lattice-based ring signature proposed by Melchor et al.at AFRICRYPT'13,employing the technique of message block sharing proposed by Choi and Kim,a lattice-based threshold ring signature scheme is proposed.In order to avoid the system parameter setup problems,we propose a message processing tech-nique called “pad-then-permute”.The message is pre-processed before blocking the message,so it makes the threshold ring signature scheme more flexible.Our threshold ring signature scheme inherits the quantum immunity from the lattice structure,has a considerably short signature and almost no signature size increase with the threshold value.We have also proven that the scheme is correct,effective,indistinguishable source hiding,and unforgeable.4.GVW13's Attribute-Based Encryption(ABE)scheme is one of major candidates for ABE.The scheme is compact and provably secure.However,it has security risks in practical applications.When Alice and Bob collude to share the decryption ability,Al-ice can gradually take Bob's private key and obtain Bob's equivalent private key.We use the method of chosen-ciphertext attack of Jaulmes and Joux against NTRU to con-struct a collusion trap attack on the GVW13 attribute encryption scheme.GVW13's attribute-based encryption can be divided into two scenarios: naked encryption and calibrated encryption.In the case of naked encryption,Alice can obtain Bob's equiv-alent secret key in polynomial time.In the case of calibrated encryption,although the size of the attack for calibrated encryption is much larger,Alice can still obtain Bob's equivalent secret key in polynomial time.