Search

With the rapid advances in quantum computing, quantum security is now an indispensable property for any cryptographic system. In this paper, we study how to prove the security of a complex cryptographic system in the quantum random oracle model. We first give a variant of Zhandry's compressed random oracle (CStO), called a compressed quantum random oracle with adaptive special points (CStOs). Then, we extend the on-line extraction technique of Don et al. (EUROCRYPT'22) from CStO to CStO s . We also extend the random experiment technique of Liu and Zhandry (CRYPTO'19) for extracting the CStO query that witnesses the future adversarial output. With these preparations, a systematic security proof in the quantum random oracle model can start with a random CStO experiment (that extracts the witness for the future adversarial output) and then converts this game to one involving CStO s . Next, the online extraction technique for CStO s can be applied to extract the witness for any online commitment. With this strategy, we give a security proof of our recent compact multi-signature framework that is converted from any weakly secure linear ID scheme. We also prove the quantum security of our recent lattice realization of this linear ID scheme by iteratively applying the weakly collapsing protocol technique of Liu and Zhandry (CRYPTO 2019). Combining these two results, we obtain the first quantum security proof for a compact multi-signature. [ABSTRACT FROM AUTHOR]

Lattice-based cryptography is centered around the hardness of problems on lattices. A lattice is a grid of points that stretches to infinity. With the development of quantum computers, existing cryptographic schemes are at risk because the underlying mathematical problems can, in theory, be easily solved by quantum computers. Since lattice-based mathematical problems are hard to be solved even by quantum computers, lattice-based cryptography is a promising foundation for future cryptographic schemes. In this paper, we focus on lattice-based public-key encryption schemes. This survey presents the current status of the lattice-based public-key encryption schemes and discusses the existing implementations. Our main focus is the learning with errors problem (LWE problem) and its implementations. In this paper, the plain lattice implementations and variants with special algebraic structures such as ring-based variants are discussed. Additionally, we describe a class of lattice-based functions called lattice trapdoors and their applications. [ABSTRACT FROM AUTHOR]

The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt ’13) proved a “regularity lemma,” which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the “regularity lemma” of Lyubashevsky et al. to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions.

A statistical framework applicable to Ring-LWE was outlined by Murphy and Player (IACR eprint 2019/452). Its applicability was demonstrated with an analysis of the decryption failure probability for degree-1 and degree-2 ciphertexts in the homomorphic encryption scheme of Lyubashevsky, Peikert and Regev (IACR eprint 2013/293). In this paper, we clarify and extend results presented by Murphy and Player. Firstly, we make precise the approximation of the discretisation of a Normal random variable as a Normal random variable, as used in the encryption process of Lyubashevsky, Peikert and Regev. Secondly, we show how to extend the analysis given by Murphy and Player to degree-k ciphertexts, by precisely characterising the distribution of the noise in these ciphertexts.

We initiate the study of partial key exposure in Ring-LWE (RLWE)-based cryptosystems. Specifically, we (1) Introduce the search and decision Leaky R-LWE assumptions (Leaky R-SLWE, Leaky R-DLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret. (2) Present and implement an efficient key exposure attack that, given certain 1/4-fraction of the coordinates of the NTT transform of the RLWE secret, along with samples from the RLWE distribution, recovers the full RLWE secret for standard parameter settings. (3) Present a search-to-decision reduction for Leaky R-LWE for certain types of key exposure. (4) Propose applications to the security analysis of RLWE-based cryptosystems under partial key exposure.

This paper proposes a practical hybrid solution for combining and switching between three popular Ring-LWE-based FHE schemes: TFHE, B/FV and HEAAN. This is achieved by first mapping the different plaintext spaces to a common algebraic structure and then by applying efficient switching algorithms. This approach has many practical applications. First and foremost, it becomes an integral tool for the recent standardization initiatives of homomorphic schemes and common APIs. Then, it can be used in many real-life scenarios where operations of different nature and not achievable within a single FHE scheme have to be performed and where it is important to efficiently switch from one scheme to another. Finally, as a byproduct of our analysis we introduce the notion of a FHE module structure, that generalizes the notion of the external product, but can certainly be of independent interest in future research in FHE.

The Learning-With-Errors (LWE) problem (and its variants including Ring-LWE and Module-LWE), whose security are based on hard ideal lattice problems, has proven to be a promising primitive with diverse applications in cryptography. For the sake of expanding sources for constructing LWE, we study the LWE problem on group rings in this work. One can regard the Ring-LWE on cyclotomic integers as a special case when the underlying group is cyclic, while our proposal utilizes non-commutative groups. In particular, we show how to build public key encryption schemes from dihedral group rings, while maintaining the efficiency of the Ring-LWE. We prove that the PKC system is semantically secure, by providing a reduction from the SIVP problem of group ring ideal lattice to the decisional group ring LWE problem. It turns out that irreducible representations of groups play important roles here. We believe that the introduction of the representation view point enriches the tool set for studying the Ring-LWE problem. [ABSTRACT FROM AUTHOR]

Fully homomorphic encryption (FHE) allows arbitrary computation on encrypted data and has great potential in privacy-preserving cloud computing and securely outsource computational tasks. However, the excessive computation complexity is the key limitation that restricting the practical application of FHE. In this paper we proposed a FPGA-based high parallelism architecture to accelerate the FHE schemes based on the ring learning with errors (RLWE) problem, specifically, we presented a fast implementation of leveled fully homomorphic encryption scheme BGV. In order to reduce the computation latency and improve the performance, we applied both circuit-level and block-level pipeline strategies to improve clock frequency, and as a result, enhance the processing speed of polynomial multipliers and homomorphic evaluation functions. At the same time, multiple polynomial multipliers and modular reduction units were deployed in parallel to further improve the hardware performance. Finally, we implemented and tested our architecture on a Virtex UltraScale FPGA platform. Runing at 150MHz, our implementation achieved $4.60\times \sim 9.49\times $ speedup with respect to the optimized software implementation on Intel i7 processor running at 3.1GHz for homomorphic encryption and decryption, and the throughput was increased by $1.03\times \sim 4.64\times $ compared to the hardware implementation of BGV. While compared to the hardware implementation of FV, the throughput of our accelerator also achieved $5.05\times $ and $167.3\times $ speedup for homomorphic addition and homomorphic multiplication operation respectively.

Abstract The group signature scheme is an important primitive in cryptography, it allows members in a group to generate signatures anonymously on behalf of the whole group. In view of the practical application of such schemes, it is necessary to allow users’ registration and revocation when necessary, which makes the construction of dynamic group signature schemes become a significant direction. On the basis of (Ling et al., Lattice-based group signatures: achieving full dynamicity with ease, 2017), we present the first full dynamic group signature scheme over ring, and under the premise of ensuring security, the efficiency of the scheme is improved mainly from the following three aspects: the size of keys, the dynamic construction of a Merkle hash tree that used to record the information of registered users, and the reuse of the leaves in this tree. In addition, the public and secret keys of both group manager and trace manager are generated by a trusted third party, which prevents the situation that the two managers generate their respective public key and secret key maliciously. Compared with the counterpart of the scheme in (Ling et al., Lattice-based group signatures: achieving full dynamicity with ease, 2017) over ring, the expected space complexity of the Merkle tree used in our work down almost by half, and the computational complexity of its update has been reduced by a notch because of the dynamic construction of the hash tree.

Identity-based proxy re-encryption (IB-PRE) is a kind of public key cryptography that allows a proxy to convert the ciphertext based on Alice's identity into another ciphertext of the same message for Bob. It has important applications in cloud computing, distributed systems and secure e-mail forwarding. So far, the existing lattice-based IB-PRE schemes are designed on the general lattice and their security is based on the learning with errors (LWE) assumption. In this paper, we propose an IB-PRE scheme over NTRU lattices with the desirable properties of anonymity, unidirectionality, backward collusion safeness and multi-hop. Our IB-PRE scheme is provable secure under adaptive chosen-plaintext and adaptive chosen-identity attacks. And, in the random oracle model, the security of our scheme is based on the decisional Ring-LWE assumption. Besides, the key and ciphertext sizes of our IB-PRE scheme are short, only one or two ring elements, and our scheme could encrypt n bits in each encryption process. [ABSTRACT FROM AUTHOR]

This paper presents a high-secure fingerprint authentication system using ring learning with errors (ring-LWE) cryptography to protect users' fingerprint data more securely. A delay-optimized high-accuracy scheme for a fingerprint-features extraction approach is proposed to collect necessary features' information from fingerprint images. In addition, a ring-LWE cryptography scheme using low-latency number theoretic transform (NTT) polynomial multiplications is deployed to speed up the ring-LWE encryption and decryption times. As a result, the processing time of the fingerprint authentication system is significantly reduced, and the fingerprint data are effectively protected. The simulation results show that the proposed NTT multiplication-based ring-LWE cryptography scheme for fingerprint features outperforms the existing works up to 46% and 44% in terms of encryption time and decryption time, respectively. The latency of the whole fingerprint authentication system is less than 160 ms, which makes it suitable for practical applications. Furthermore, performance analysis on entropy and similarity of the encrypted fingerprint features proves the domination of the proposed system compared with the previous systems in terms of confidentiality.

The leftover hash lemma (LHL) is used in the analysis of various lattice-based cryptosystems, such as the Regev and Dual-Regev encryption schemes as well as their leakage-resilient counterparts. The LHL does not hold in the ring setting, when the ring is far from a field, which is typical for efficient cryptosystems. Lyubashevsky et al. (Eurocrypt '13) proved a "regularity lemma," which can be used instead of the LHL, but applies only for Gaussian inputs. This is in contrast to the LHL, which applies when the input is drawn from any high min-entropy distribution. Our work presents an approach for generalizing the "regularity lemma" of Lyubashevsky et al. to certain conditional distributions. We assume the input was sampled from a discrete Gaussian distribution and consider the induced distribution, given side-channel leakage on the input. We present three instantiations of our approach, proving that the regularity lemma holds for three natural conditional distributions. [ABSTRACT FROM AUTHOR]

We initiate the study of partial key exposure in Ring-LWE (RLWE)-based cryptosystems. Specifically, we (1) Introduce the search and decision Leaky R-LWE assumptions (Leaky R-SLWE, Leaky R-DLWE), to formalize the hardness of search/decision RLWE under leakage of some fraction of coordinates of the NTT transform of the RLWE secret. (2) Present and implement an efficient key exposure attack that, given certain 1/4-fraction of the coordinates of the NTT transform of the RLWE secret, along with samples from the RLWE distribution, recovers the full RLWE secret for standard parameter settings. (3) Present a search-to-decision reduction for Leaky R-LWE for certain types of key exposure. (4) Propose applications to the security analysis of RLWE-based cryptosystems under partial key exposure. [ABSTRACT FROM AUTHOR]

A statistical framework applicable to Ring-LWE was outlined by Murphy and Player (IACR eprint 2019/452). Its applicability was demonstrated with an analysis of the decryption failure probability for degree-1 and degree-2 ciphertexts in the homomorphic encryption scheme of Lyubashevsky, Peikert and Regev (IACR eprint 2013/293). In this paper, we clarify and extend results presented by Murphy and Player. Firstly, we make precise the approximation of the discretisation of a Normal random variable as a Normal random variable, as used in the encryption process of Lyubashevsky, Peikert and Regev. Secondly, we show how to extend the analysis given by Murphy and Player to degree-k ciphertexts, by precisely characterising the distribution of the noise in these ciphertexts. [ABSTRACT FROM AUTHOR]

Public key cryptography protocols, such as RSA and elliptic curve cryptography, will be rendered insecure by Shor’s algorithm when large-scale quantum computers are built. Cryptographers are working on quantum-resistant algorithms, and lattice-based cryptography has emerged as a prime candidate. However, high computational complexity of these algorithms makes it challenging to implement lattice-based protocols on low-power embedded devices. To address this challenge, we present Sapphire – a lattice cryptography processor with configurable parameters. Efficient sampling, with a SHA-3-based PRNG, provides two orders of magnitude energy savings; a single-port RAM-based number theoretic transform memory architecture is proposed, which provides 124k-gate area savings; while a low-power modular arithmetic unit accelerates polynomial computations. Our test chip was fabricated in TSMC 40nm low-power CMOS process, with the Sapphire cryptographic core occupying 0.28 mm2 area consisting of 106k logic gates and 40.25 KB SRAM. Sapphire can be programmed with custom instructions for polynomial arithmetic and sampling, and it is coupled with a low-power RISC-V micro-processor to demonstrate NIST Round 2 lattice-based CCA-secure key encapsulation and signature protocols Frodo, NewHope, qTESLA, CRYSTALS-Kyber and CRYSTALS-Dilithium, achieving up to an order of magnitude improvement in performance and energy-efficiency compared to state-of-the-art hardware implementations. All key building blocks of Sapphire are constant-time and secure against timing and simple power analysis side-channel attacks. We also discuss how masking-based DPA countermeasures can be implemented on the Sapphire core without any changes to the hardware.

The advent of quantum computing threatens to break many classical cryptographic schemes, leading to innovations in public key cryptography that focus on post-quantum cryptography primitives and protocols resistant to quantum computing threats. Lattice-based cryptography is a promising post-quantum cryptography family, both in terms of foundational properties as well as in its application to both traditional and emerging security problems such as encryption, digital signature, key exchange, and homomorphic encryption. While such techniques provide guarantees, in theory, their realization on contemporary computing platforms requires careful design choices and tradeoffs to manage both the diversity of computing platforms (e.g., high-performance to resource constrained), as well as the agility for deployment in the face of emerging and changing standards. In this work, we survey trends in lattice-based cryptographic schemes, some recent fundamental proposals for the use of lattices in computer security, challenges for their implementation in software and hardware, and emerging needs for their adoption. The survey means to be informative about the math to allow the reader to focus on the mechanics of the computation ultimately needed for mapping schemes on existing hardware or synthesizing part or all of a scheme on special-purpose har dware. [ABSTRACT FROM AUTHOR]

Smooth Projective Hash Functions (SPHFs) as a specific pattern of zero knowledge proof system are fundamental tools to build many efficient cryptographic schemes and protocols. As an application of SPHFs, Password-Based Authenticated Key Exchange (PAKE) protocol is well-studied area in the last few years. In 2009, Katz and Vaikuntanathan described the first lattice-based PAKE using the Learning With Errors (LWE) problem. In this work, we present a new efficient ring-based smooth projective hash function \(Ring-SPHF)" using Lyubashevsky, Peikert, and Regev's dual-style cryptosystem based on the Learning With Errors over Rings (Ring-LWE) problem. Then, using our ring-SPHF, we propose an efficient password-based authenticated key exchange \(Ring-PAKE)" protocol over rings whose security relies on ideal lattice assumptions. [ABSTRACT FROM AUTHOR]

In this paper, we present an FPGA based hardware accelerator ‘ $\mathsf{HEPCloud}$ ’ for homomorphic evaluations of medium depth functions which has applications in cloud computing. Our $\mathsf{HEPCloud}$ architecture supports the polynomial ring based homomorphic encryption scheme FV for a ring-LWE parameter set of dimension $2^{15}$ , modulus size 1,228-bit, and a standard deviation 50. This parameter-set offers a multiplicative depth 36 and at least 85 bit security. The processor of $\mathsf{HEPCloud}$ is composed of multiple parallel cores. To achieve fast computation time for such a large parameter-set, various optimizations in both algorithm and architecture levels are performed. For fast polynomial multiplications, we use CRT with NTT and achieve two dimensional parallelism in $\mathsf{HEPCloud}$ . We optimize the BRAM access, use a fast Barrett like polynomial reduction method, optimize the cost of CRT, and design a fast divide-and-round unit. Beside parallel processing, we apply pipelining strategy in several of the sequential building blocks to reduce the impact of sequential computations. Finally, we implement $\mathsf{HEPCloud}$ on a medium-size Xilinx Virtex 6 FPGA board ML605 board and measure its on-board performance. To store the ciphertexts during a homomorphic function evaluation, we use the large DDR3 memory of the ML605 board. Our FPGA-based implementation of $\mathsf{HEPCloud}$ computes a homomorphic multiplication in 26.67 s, of which the actual computation takes only 3.36 s and the rest is spent for off-chip memory access. It requires about 37,551 s to evaluate the SIMON-64/128 block cipher, but the per-block timing is only about 18 s because $\mathsf{HEPCloud}$ processes 2,048 blocks simultaneously. The results show that FPGA-based acceleration of homomorphic function evaluations is feasible, but fast memory interface is crucial for the performance. [ABSTRACT FROM AUTHOR]

The era of the Internet of Things (IoT) has arrived and much information is transmitted through various small IoT devices. Public key cryptography can be used in the present internet environment to avoid eavesdropping. The well-known public key cryptography, Rivest–Shamir–Adleman cryptography and Elliptic Curve Cryptography are apt to be broken when quantum computing is introduced. Therefore, lattice-based cryptography has been proposed as a new public key cryptography to replace them. The Ring-LWE scheme has been proposed to implement lattice-based cryptography. To apply the scheme to IoT devices using 8-bit, 32-bit, or 64-bit microcontrollers, optimization is inevitable. Further, the 8-bit environment is more important for small IoT devices. However, Ring-LWE may be vulnerable to side-channel attacks. This paper analyzes the attack scenario and tenders a countermeasure through bit checking for IoT applications using 8-bit microcontrollers. [ABSTRACT FROM AUTHOR]

During the last years public-key encryption schemes based on the hardness of ring-LWE have gained significant popularity. For real-world security applications assuming strong adversary models, a number of practical issues still need to be addressed. In this work we thus present an instance of ring-LWE encryption that is protected against active attacks (i.e., adaptive chosen-ciphertext attacks) and equipped with countermeasures against side-channel analysis. Our solution is based on a postquantum variant of the Fujisaki-Okamoto (FO) transform combined with provably secure first-order masking. To protect the key and message during decryption, we developed a masked binomial sampler that secures the re-encryption process required by FO. Our work shows that CCA2-secured RLWE-based encryption can be achieved with reasonable performance on constrained devices but also stresses that the required transformation and handling of decryption errors implies a performance overhead that has been overlooked by the community so far. With parameters providing 233 bits of quantum security, our implementation requires 4,176,684 cycles for encryption and 25,640,380 cycles for decryption with masking and hiding countermeasures on a Cortex-M4F. The first-order security of our masked implementation is also practically verified using the non-specific t-test evaluation methodology.

Since its introduction more than a decade ago the homomorphic properties of the NTRU encryption scheme have gone largely ignored. A variant of NTRU proposed by Stehlé and Steinfeld was recently extended into a full fledged multi-key fully homomorphic encryption scheme by López-Alt, Tromer and Vaikuntanathan (LTV). This NTRU based FHE presents a viable alternative to the currently dominant BGV style FHE schemes. While the scheme appears to be more efficient, a full implementation and comparison to BGV style implementations has been missing in the literature. In this work, we develop a customized implementation of the LTV. First parameters are selected to yield an efficient and yet secure LTV instantiation. We present an analysis of the noise growth that allows us to formulate a modulus cutting strategy for arbitrary circuits. Furthermore, we introduce a specialization of the ring structure that allows us to drastically reduce the public key size making evaluation of deep circuits such as the AES block cipher viable on a standard computer with a reasonable amount of memory. Moreover, with the modulus specialization the need for key switching is eliminated. Finally, we present a generic bit-sliced implementation of the LTV scheme that embodies a number of optimizations. To assess the performance of the scheme we homomorphically evaluate the full 10 round AES circuit in 29 h with 2048 message slots resulting in 51 s per AES block evaluation time. [ABSTRACT FROM AUTHOR]

A high efficiency architecture for ring learning with errors (ring-LWE) cryptoprocessor using shared arithmetic components is presented in this paper. By applying a novel approach for sharing number theoretic transform (NTT) polynomial multiplier and polynomial adder in encryption and decryption operations, the total number of polynomial multipliers and polynomial adders used in the proposed ring-LWE cryptoprocessor are reduced. In addition, the processing time of NTT polynomial multiplier is speeded up by employing multiple-path delay feedback (MDF) architecture and deploying pipelined technique between all stages of NTT processes. As a result, the proposed architecture offers a great reduction in terms of the hardware complexity and computation latency compared with existing works. The implementation result for the proposed ring-LWE cryptoprocessor on Virtex-7 FPGA board using Xilinx VIVADO shows a significant decrease in the number of slices and LUTs compared with previous works. Moreover, the proposed ring-LWE cryptoprocessor offers higher throughput and efficiency than its predecessors. [ABSTRACT FROM AUTHOR]

The group signature scheme is an important primitive in cryptography, it allows members in a group to generate signatures anonymously on behalf of the whole group. In view of the practical application of such schemes, it is necessary to allow users' registration and revocation when necessary, which makes the construction of dynamic group signature schemes become a significant direction. On the basis of (Ling et al., Lattice-based group signatures: achieving full dynamicity with ease, 2017), we present the first full dynamic group signature scheme over ring, and under the premise of ensuring security, the efficiency of the scheme is improved mainly from the following three aspects: the size of keys, the dynamic construction of a Merkle hash tree that used to record the information of registered users, and the reuse of the leaves in this tree. In addition, the public and secret keys of both group manager and trace manager are generated by a trusted third party, which prevents the situation that the two managers generate their respective public key and secret key maliciously. Compared with the counterpart of the scheme in (Ling et al., Lattice-based group signatures: achieving full dynamicity with ease, 2017) over ring, the expected space complexity of the Merkle tree used in our work down almost by half, and the computational complexity of its update has been reduced by a notch because of the dynamic construction of the hash tree. [ABSTRACT FROM AUTHOR]