Since hash proof system (HPS) can be utilized to build versatilely cryptographic schemes, the study on realizing this cryptographic primitive has been a very active research area. With the increasing concerns on the huge progress in quantum computing, it urges cryptographers to explore the existence of quantum-resistant HPS schemes, such as the one relying on some lattice-based assumptions. However, most lattice-based HPS proposals are relatively inefficient (e.g., simply outputting one-bit key), even though lattice-based schemes can enjoy many advantageous features: worst-case to average-case reduction, resistance so far to quantum algorithms, and good asymptotic efficiency. Therefore, efficient HPS schemes based on lattice problems are deeply in demand. Through a comprehensive analysis, we found that some lattice-based HPS schemes can be rephrased as their corresponding key encapsulation mechanism (KEM) forms, which generally rely on diverse reconciliation mechanisms and directly imply key exchange protocols under lattice-based assumptions. In this paper, inspired by a novel reconciliation mechanism based on the learning with errors (LWE) problem, we first properly adapt this LWE-based reconciliation mechanism for arbitrary modulus. Then using this improved reconciliation mechanism, we propose an efficient LWE-based HPS scheme which can generate multiple encapsulated key bits and perform better in both computation and storage costs than other related results. Moreover, our proposed lattice-based HPS scheme can be also extended to identity-based and updatable settings for demonstrating its diverse applications.
Since hash proof system (HPS) can be utilized to build versatilely cryptographic schemes, the study on realizing this cryptographic primitive has been a very active research area. With the increasing concerns on the huge progress in quantum computing, it urges cryptographers to explore the existence of quantum-resistant HPS schemes, such as the one relying on some lattice-based assumptions. However, most lattice-based HPS proposals are relatively inefficient (e.g., simply outputting one-bit key), even though lattice-based schemes can enjoy many advantageous features: worst-case to average-case reduction, resistance so far to quantum algorithms, and good asymptotic efficiency. Therefore, efficient HPS schemes based on lattice problems are deeply in demand. Through a comprehensive analysis, we found that some lattice-based HPS schemes can be rephrased as their corresponding key encapsulation mechanism (KEM) forms, which generally rely on diverse reconciliation mechanisms and directly imply key exchange protocols under lattice-based assumptions. In this paper, inspired by a novel reconciliation mechanism based on the learning with errors (LWE) problem, we first properly adapt this LWE-based reconciliation mechanism for arbitrary modulus. Then using this improved reconciliation mechanism, we propose an efficient LWE-based HPS scheme which can generate multiple encapsulated key bits and perform better in both computation and storage costs than other related results. Moreover, our proposed lattice-based HPS scheme can be also extended to identity-based and updatable settings for demonstrating its diverse applications.
As a basic and important primitive, hash proof system can be used to construct many cryptographic schemes and protocols. Therefore, it is significant to instantiate more efficient hash proof systems from various assumptions. Although there are many hash proof systems based on various classical assumptions, only a handful of efficient hash proof systems are known based on post-quantum assumptions. In this paper, we present several new hash proof systems based on the standard learning with errors (LWE) problem, which is at least as hard as standard worst-case lattice problems. Comparing with other existing constructions based on lattices, our main advantages are 2-fold: much simpler and more efficient. And our constructions can be easily extended to be identity-based ones and updatable ones. Throughout the paper, our main idea is to base hash proof systems on a new subset indistinguishability problem related to LWE, and employ the property of smooth parameter of q-ary orthogonal lattices to ensure smoothness.
As the progress of quantum computers, it is desired to propose many more efficient cryptographic constructions with post-quantum security. In the literatures, almost all cryptographic schemes and protocols can be explained and constructed modularly from certain cryptographic primitives, among which an Identity-Based Hash Proof System (IB-HPS) is one of the most basic and important primitives. Therefore, we can utilize IB-HPSs with post-quantum security to present several types of post-quantum secure schemes and protocols. Up until now, all known IB-HPSs with post-quantum security are instantiated based on latticed-based assumptions. However, all these lattice-based IB-HPSs are either in the random oracle model or not efficient enough in the standard model. Hence, it should be of great significance to construct more efficient IB-HPSs from lattices in the standard model. In this paper, we propose a new smooth IB-HPS with anonymity based on the Learning with Errors (LWE) assumption in the standard model. This new construction is mainly inspired by a classical identity-based encryption scheme based on LWE due to Agreawal et al. in Eurocrypt 2010. And our innovation is to employ the algorithm SampleGaussian introduced by Gentry et al. and the property of random lattice to simulate the identity secret key with respect to the challenge identity. Compared with other existing IB-HPSs in the standard model, our master public key is quite compact. As a result, our construction has much lower overheads on computation and storage.
We present a hash proof systems (HPS)based on hard lattice problems including learning with error (LWE) and inhomogeneous small integer solution (ISIS). Different from the HPS in past, ours is with error. That is to say, the deterministic private evaluation algorithm is not always equivalent to the deterministic public evaluation algorithm. The difference between them is one or zero. We also show how to construct a public-key encryption scheme which is semantically secure against key-leakage attacks in the standard model using our HPS based on lattice. Compared with previous cryptosystem based on lattice, our construction needs bigger public key space but fewer operations during encryption, and can resist quantum attacks because of the assumption on lattice problem.
In the last decade, there has been significant progress in the development of quantum computers, with massive investments by major tech companies. It is assumed that once large-scale quantum computers are built, many commonly used public key cryptosystems will no longer be secure. To prevent quantum attacks, researchers are already working on the design of post-quantum cryptographic protocols, and the US National Institute of Standards and Technology (NIST) is holding an international competition to select new cryptographic standards.Lattice-based cryptographic constructions are promising candidates because they offer strong theoretical security guarantees and can be implemented efficiently. One of the most widely used cryptographic primitives based on lattices is the Learning With Errors (LWE) problem introduced by Regev. Later works have proposed structured variants of LWE such as Ring-LWE and Module-LWE, which allow for a more compact representation.In this thesis, we consider two lattice-based NIST candidates for Key Encapsulation Mechanisms (KEMs) and propose new error correction and reconciliation techniques in order to improve their efficiency, their security, as well as their reliability.Unlike some previous works on error correction for lattice-based protocols, we provide rigorous error probability bounds.We first consider FrodoKEM, a lattice-based cryptosystem based on LWE, and introduce a modified error correction mechanism to improve its performance. Our encoder maps the secret key block-wise into a scaled version of the 8-dimensional Gosset lattice E_8. We propose three sets of parameters for our modified implementation. The first implementation outperforms FrodoKEM in terms of plausible security; the second allows to reduce the bandwidth by halving the modulus, and the third allows to increase key sizes.The second KEM we are considering is KyberKEM, which is based on Module-LWE. We propose a reconciliation technique using the lattice E_8, and show that our scheme can outperform KyberKEM in terms of security with comparable error probability and similar bandwidth requirements. We also investigate the use of higher dimensional lattices for reconciliation.
Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. \nIn this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. \nFirst, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. \nIn the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. \nIn the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.
Due to the threat of future quantum computers, it is necessary to develop cryptographic schemes that are resistant to quantum attacks. Lattice based cryptographic schemes have resistance to quantum attacks and security under worst-case assumptions that are difficult to solve. To solve the problems of large size of public and private keys, low encryption efficiency, and large noise growth in identity based encryption schemes, an adaptive secure identity based all homomorphic encryption scheme based on Learning with Errors (LWE) is constructed. This scheme uses {0,1} matrices to store plaintext, significantly improving encryption efficiency compared to single bit encryption schemes. It uses key conversion technology to achieve homomorphic operations and modulus conversion technology to reduce noise. It also converts IDs into bit sequences to construct an encryption scheme for adaptive security. Compared to selective security that only provides security guarantees for specific types of attacks, adaptive security is suitable for general scenarios, providing higher security guarantees and being able to cope with more challenging attack situations. It has been proven through the LWE problem that the security of our proposed scheme satisfies IND-ID-CPA. Finally, the experimental results indicate that this scheme introduces less noise, and has higher encryption efficiency and performance.