Search

Lattice-based cryptography leverages Euclidean lattices (and carefully-applied "noise") to construct secure cryptographic primitives. In recent years, these primitives have become quite practical (and academically popular), yielding a large number of variant schemes that are mild variants on the same core construction(s).First, we introduce a relaxed notion of security for a cryptographic primitive that we call (c,s)-bit security. This parameterizes security with a (standard, computational) security parameter c, as well as a statistical security parameter s, and seems well-adapted for summarizing the concrete hardness of problems that contain both computationally-hard and statistically-hard components. We pair this with the notion of distinguishing advantage of aborting adversaries (Micciancio and Walter, Eurocrypt 2018), and characterize optimal adversaries in this setting.Next, we propose a framework for the design of lattice-based encryption, parameterized by two coding-theoretic objects. We show that one can instantiate many lattice-based cryptosystems with compact ciphertexts in our framework, and show there are fundamental limits on the ciphertext size for cryptosystems built within our framework.Finally, we show that one may harden the approximate FHE scheme of Cheon, Kim, Kim, and Song (Asiacrypt 2017) against the passive attacks of Li and Micciancio (Eurocrypt 2021), via applying an appropriate notion of differential privacy. Here, we find that to achieve (c,s)-bit security, the overhead of our countermeasure scales entirely with s (which may plausibly be set lower than c). We show that our countermeasure's overhead is nearly optimal, by arguing that instantiating it with smaller overhead yields an insecure scheme. Finally, we investigate another proposed countermeasure that lacked a proof of security, and show simple attacks against it.

ispartof: IEEE TRANSACTIONS ON COMPUTERS vol:72 issue:2 pages:321-332 status: published

Password-based authenticated key exchange (PAKE) protocol allows protocol participants to establish a high entropy session key by pre-sharing a low-entropy password. Katz and Vaikuntanathan (ASIACRYPT'09) used a one-round smooth projective hash function (SPHF) over lattices to design a three-round PAKE protocol. Zhang and Yu (AISACRYPT'17) improved Katz-Vaikuntanatha's scheme by proposing a two-round PAKE with NIZK proofs, but how to construct a lattice-based simulation-sound NIZK remains an open research question. Benhamouda et al. followed the framework of Katz and Vaikuntananthan (TCC'11) and proposed a one-round PAKE via trapdoor-SPHF, but their scheme was based on conventional DDH assumption. In other words, how to design a one-round PAKE via an efficient lattice-based SPHF still remains a challenge. In this paper, we attempt to fill this gap by first proposing a new IND-CCA-secure lattice-based SPHF based on the work of Benhamouda et al. (PKC'18), and then using the proposed SPHF to construct a one-round PAKE protocol. We then prove the security of the proposed protocol. We also explore the possibilities of constructing two-round PAKE, three-round PAKE and universal composable security from our SPHF, and show the potential application of our PAKE in the Internet of Things where communication cost is the main consideration.

Key exchange protocols and key encapsulation mechanisms establish secret keys to communicate digital information confidentially over public channels. Lattice-based cryptography variants of these protocols are promising alternatives given their quantum-cryptanalysis resistance and implementation efficiency. Although lattice cryptosystems can be mathematically secure, their implementations have shown side-channel vulnerabilities. But such attacks largely presume collecting multiple measurements under a fixed key, leaving the more dangerous single-trace attacks unexplored. This article demonstrates successful single-trace power side-channel attacks on lattice-based key exchange and encapsulation protocols. Our attack targets both hardware and software implementations of matrix multiplications used in lattice cryptosystems. The crux of our idea is to apply a horizontal attack that makes hypotheses on several intermediate values within a single execution all relating to the same secret, and to combine their correlations for accurately estimating the secret key. We illustrate that the design of protocols combined with the nature of lattice arithmetic enables our attack. Since a straightforward attack suffers from false positives, we demonstrate a novel extend-and-prune procedure to recover the key by following the sequence of intermediate updates during multiplication. We analyzed two protocols, Frodo and FrodoKEM , and reveal that they are vulnerable to our attack. We implement both stand-alone hardware and RISC-V based software realizations and test the effectiveness of the proposed attack by using concrete parameters of these protocols on physical platforms with real measurements. We show that the proposed attack can estimate secret keys from a single power measurement with over 99% success rate.

Discrete Gaussian distribution plays an essential role in lattice cryptography whereas naive implementations suffer from timing attacks. Unfortunately, conversion to secure constant-time variant incurs severe deterioration in performance. In Knuth-Yao sampling, we demonstrate several properties of the discrete distribution generation tree involving structural features and finite node height. Accordingly we propose a generic method independent of standard deviations, which focuses on minimizing the Boolean expressions for the mapping from input bit strings to output sample values, along with an in-depth efficiency analysis. Two optimization techniques are devised to further propel the minimization by replacing and adjusting nodes. To strike the balance of computational overhead and closeness to optimum, heuristic strategies are introduced. Finally, performance evaluation is conducted both in software and hardware. Running on a 3.4GHz Intel Core i7-6700 processor, our method improves sampling rate by up to 29.5 percent compared to the latest technique. Targeting hardware FPGA devices, our approach can be 2.7 times faster and achieves 57.3 percent resource reduction than the original constant-time Knuth-Yao sampling. Compared to the Cumulative Distribution Table algorithm with fixed step binary search, our sampler can be at least 12.6 times faster and gains 79/61 percent better area-time product than its counterpart without/with BRAM.

In this paper, we introduce a new construction of reusable fuzzy signature based remote user authentication that is secure against quantum computers. We investigate the reusability of fuzzy signature, and we prove that the fuzzy signature schemes provide biometrics reusability (aka. reusable fuzzy signature). We define formal security models for the proposed construction, and we prove that it achieves user authenticity and user privacy. The proposed construction ensures: 1) a user’s biometrics can be securely reused in remote user authentication; 2) a third party having access to the communication channel between a user and the authentication server cannot identify the user.

Homomorphic encryption is an emerging form of encryption that provides the ability to compute on encrypted data without ever decrypting them. Potential applications include aggregating sensitive encrypted data on a cloud environment and computing on the data in the cloud without compromising data privacy. There have been several recent advances resulting in new homomorphic encryption schemes and optimized variants. We implement and evaluate the performance of two optimized variants, namely Bajard-Eynard-Hasan-Zucca (BEHZ) and Halevi-Polyakov-Shoup (HPS), of the most promising homomorphic encryption scheme in CPU and GPU. The most interesting (and also unexpected) result of our performance evaluation is that the HPS variant in practice scales significantly better (typically by 15-30 percent) with increase in multiplicative depth of the computation circuit than BEHZ, implying that the HPS variant will always outperform BEHZ for most practical applications. For the multiplicative depth of 98, our fastest GPU implementation performs homomorphic multiplication in 51 ms for 128-bit security settings, which is faster by two orders of magnitude than prior results and already practical for cloud environments supporting GPU computations. Large multiplicative depths supported by our implementations are required for applications involving deep neural networks, logistic regression learning, and other important machine learning problems.

Lattice-based cryptography is one of the emerging fields of cryptography in the post-quantum world. It is resistive to quantum attacks and has performance competitive to that of prevalent cryptosystem such as Rivest–Shamir–Adleman (RSA), Diffie Hellman etc. Till now, various basic cryptographic primitives like encryption and decryption, digital signature, hash-based functions, and key exchange are proposed in lattice-based cryptography. The key exchange primitive is one of the basic cryptographic primitives of the Public Key Infrastructure (PKI). Lattices are preferably used to design provably secure reconciliation based key exchange protocols against quantum attacks. However, the literature pertaining to the study of reconciliation based key exchange protocols is limited and often the schemes are studied independently. Therefore, in this work, we have reviewed the reconciliation based key exchange schemes and classify these schemes under two different categories depending on the reconciliation mechanism used by the scheme. We also point out the basic key exchange schemes upon which all other key exchange schemes are based. We conduct a complete review, security analysis, implementation and comparison of these basic key exchange schemes.

Quantum computers are imminent threat to secure signal processing because they can break the contemporary public-key cryptography schemes in polynomial time. Ring learning with error (RLWE) lattice-based cryptography (LBC) is considered as the most versatile and efficient family of post-quantum cryptography (PQC). Polynomial multiplication is the most compute-intensive routine in the RLWE schemes. Convolutions and Number Theoretic Transform (NTT) are two common methods to perform the polynomial multiplication. In this paper, we explore the energy efficiency of different polynomial multipliers, NTT-based and convolution-based, on GPU and FPGA. When synthesized on a Zynq UltraScale+ FPGA, our NTT-based and convolution-based designs achieve on average 5.1x and 22.5x speedup over state-of-the-art. Our convolution-based design, on a Zynq UltraScale+ FPGA, can generate more than 2x signatures per second by CRYSTALS-Dilithium. The designed NTT-based multiplier on NVIDIA Jetson TX2 is 1.2x and 2x faster than our baseline NTT-based multiplier on FPGA for polynomial degrees of 512 and 1024, respectively. Our explorations and guidelines can help designers choose proper implementations to realize quantum-resistant signal processing.

Due to the appearance of quantum computers, which will significantly reduce the time of solving certain problems, the security of many standardized cryptosystems is under threat. This prompted NIST to launch an open competition to create new post-quantum standards in 2016. In the summer of 2020, the NTRU algorithm, one of the fastest post-quantum algorithms based on lattices in Euclidean space (1996), was entered the seven finalists of this competition. However, only in 2017 was proposed an analog of this encryption scheme – symmetric encryption scheme NTRUCipher. Preliminary researches of this encryption scheme have been conducted but it’s security to chosen-plaintext attack, which consists of compiling a system of linear equations corrupted by noise (over a finite field of simple order) and solving it using a generalized BKW algorithm, have not been analyzed. For the first time, the NTRUCipher + cipher scheme is proposed in this article. Its main difference is the usage of an additional random polynomial when encrypting. The security of NTRUCipher cipher scheme and its modification NTRUCipher+ against BKW-attack is researched. Such an attack is possible for symmetric NTRU-like cipher schemes but it has not been considered before. Analytical (upper and lower) bounds of the BKW attack’s complexity on NTRUCipher and NTRUCipher + are obtained. The comparison of these cipher schemes on the encrypted messages’ length against BKW-attack at certain identical fixed parameters is carried out. It is shown that the security increase of the NTRUCipher cipher scheme against BKW-attack due to the usage of an additional additive in encryption is almost completely leveled by increasing the upper bound of the decryption failure probability. Research allows to compare these cipher schemes in terms of security and practicality and to conclude that it is inexpedient to use NTRUCipher+ to increase the security of the NTRUCipher cipher scheme to BKW attack. In the future, it is planned to develop methods for constructing symmetric analogs of the NTRU cryptosystem based on other general lattice-based structures.

As one of the most efficient lattice-based signature schemes, and one of the only ones to have seen deployment beyond an academic setting (e.g., as part of the VPN software suite strongSwan), BLISS has attracted a significant amount of attention in terms of its implementation security, and side-channel vulnerabilities of several parts of its signing algorithm have been identified in previous works. In this paper, we present an even simpler timing attack against it. The bimodal Gaussian distribution that BLISS is named after is achieved using a random sign flip during signature generation, and neither the original implementation of BLISS nor strongSwan ensure that this sign flip is carried out in constant time. It is therefore possible to recover the corresponding sign through side-channel leakage (using, e.g., cache attacks or branch tracing). We show that obtaining this single bit of leakage (for a moderate number of signatures) is in fact sufficient for a full key recovery attack. The recovery is carried out using a maximum likelihood estimation on the space of parameters, which can be seen as a statistical manifold. The analysis of the attack thus reduces to the computation of the Fisher information metric.

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.

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.

Public key Encryption with Keyword Search (PEKS) aims in mitigating the impacts of data privacy versus utilization dilemma by allowing any user in the system to send encrypted files to the server to be searched by a receiver. The receiver can retrieve the encrypted files containing specific keywords by providing the corresponding trapdoors of these keywords to the server. Despite their merits, the existing PEKS schemes introduce a high end-to-end delay that may hinder their adoption in practice. Moreover, they do not scale well for large security parameters and provide no post-quantum security promises. In this paper, we propose two novel lattice-based PEKS schemes that offer a high computational efficiency along with better security assurances than that of the existing alternatives. Specifically, our NTRU-PEKS scheme achieves 18 times lower end-to-end delay than the most efficient pairing-based alternatives. Our LWE-PEKS offers provable security in the standard model with a reduction to the worst-case lattice problems. We fully implemented our NTRU-PEKS scheme and benchmarked its performance as deployed on Amazon Web Services cloud infrastructures.

Embedded processors have been widely used for building up Internet of Things (IoT) platforms, in which the security issue is becoming critical. This paper studies efficient techniques of lattice-based cryptography on these processors and presents the first implementation of ring-LWE encryption on ARM NEON and MSP430 architectures. For ARM NEON architecture, we propose a vectorized version of Iterative Number Theoretic Transform (NTT) for high-speed computation of polynomial multiplication on ARM NEON platforms and a 32-bit variant of SAMS2 technique for fast reduction. For MSP430 architecture, we propose an optimized SWAMS2 reduction technique, which consists of five different basic operations, including Shifting, Swapping, Addition, and two Multiplication-Subtractions. Regarding of the sampling from the discrete Gaussian distribution, we adopt Knuth-Yao sampler, accompanied with optimized methods such as Look-Up Table (LUT) and byte-scanning. Subsequently, a full-fledged implementation of Ring-LWE is presented by both taking advantage of our proposed method and previous optimization techniques re-designed for desired platforms. Our ring-LWE implementation of encryption/decryption at a classical security level of 128 bits requires only $149.4k/32.8k$ 149 . 4 k / 32 . 8 k clock cycles on ARM NEON, and $2126.3k/244.5k$ 2126 . 3 k / 244 . 5 k clock cycles on MSP430. These results are roughly 7 times faster than the fastest ECC implementation on desired platforms with same security level.

Learning With Errors (LWE) is one of the Non-Polynomial (NP)-hard problems applied in cryptographic primitives against quantum attacks. However, the security and efficiency of schemes based on LWE are closely affected by the error sampling algorithms. The existing pseudo-random sampling methods potentially have security leaks that can fundamentally influence the security levels of previous cryptographic primitives. Given that these primitives are proved semantically secure, directly deducing the influences caused by leaks of sampling algorithms may be difficult. Thus, we attempt to use the attack model based on automatic learning system to identify and evaluate the practical security level of a cryptographic primitive that is semantically proved secure in indistinguishable security models. In this paper, we first analyzed the existing major sampling algorithms in terms of their security and efficiency. Then, concentrating on the Indistinguishability under Chosen-Plaintext Attack (IND-CPA) security model, we realized the new attack model based on the automatic learning system. The experimental data demonstrates that the sampling algorithms perform a key role in LWE-based schemes with significant disturbance of the attack advantages, which may potentially compromise security considerably. Moreover, our attack model is achievable with acceptable time and memory costs.

Ring-Learning With Errors (Ring-LWE) based cryptographic schemes such as signature, key exchange, and encryption require polynomial multiplication. This multiplication operation is the most time consuming and computationally rigorous process in Ring-LWE. In order to improve the efficiency of the Ring-LWE based schemes, most of the existing schemes use Fast Fourier Transform (FFT) based polynomial multiplication algorithm. It is known that Discrete Sine Transformation (DST) and Discrete Cosine Transformation (DCT) are faster than the FFT. The combination of DCT and DST is Discrete Trigonometric Transform (DTT). When we generalize DTT in terms of FFT form, it becomes Generalized Discrete Fourier Transform (GDFT). In this paper, we propose two new polynomial multiplication techniques using DTT and GDFT. When we apply circular convolution and skew-circular convolution on DTT or GDFT for the polynomial multiplication, it gives us wrong results. To overcome this issue, we use symmetric convolution operation on DTT and GDFT. We implemented and compared the proposed polynomial multiplication schemes with the current state-of-the-art schemes in terms of computation and communication costs. The implementation results show that the proposed schemes DTT and GDFT perform more efficiently as compared to current state-of-the-art schemes in terms of computation and communication costs.

Empowering electronic devices to support Post-Quantum Cryptography (PQC) is a challenging task. PQC introduces new mathematical elements and operations which are usually not easy to implement on standard processors. Especially for low cost and resource constraint devices, hardware acceleration is usually required. In addition, as the standardization process of PQC is still ongoing, a focus on maintaining flexibility is mandatory. To cope with such requirements, hardware/software co-design techniques have been recently used for developing complex and highly customized PQC solutions. However, while most of the previous works have developed loosely coupled PQC accelerators, the design of tightly coupled accelerators and Instruction Set Architecture (ISA) extensions for PQC have been barely explored. To this end, we present RISQ-V, an enhanced RISC-V architecture that integrates a set of powerful tightly coupled accelerators to speed up lattice-based PQC. RISQ-V efficiently reuses processor resources and reduces the amount of memory accesses. This significantly increases the performance while keeping the silicon area overhead low. We present three contributions. First, we propose a set of powerful hardware accelerators deeply integrated into the RISC-V pipeline. Second, we extended the RISC-V ISA with 29 new instructions to efficiently perform operations for lattice-based cryptography. Third, we implemented our RISQ-V in ASIC technology and on FPGA. We evaluated the performance of NewHope, Kyber, and Saber on RISQ-V. Compared to the pure software implementation on RISC-V, our co-design implementations show a speedup factor of up to 11.4 for NewHope, 9.6 for Kyber, and 2.7 for Saber. For the ASIC implementation, the energy consumption was reduced by factors of up to 9.5 for NewHope, 7.7 for Kyber, and 2.1 for Saber. The cell count of the CPU was increased by a factor of 1.6 compared to the original RISC-V design, which can be considered as a moderate increase for the achieved performance gain., IACR Transactions on Cryptographic Hardware and Embedded Systems, Volume 2020, Issue 4

In this paper, we briefly describe the mathematical structure lattice and its cryptographic hard problems. The lattice based public key cryptosystem NTRU and its matrix variant Matrix NTRU are anal...

This paper presents an FPGA implementation of the most critical operations of Public Key Cryptography (PKC), namely the Modular Exponentiation (ME) and the Modular Multiplication (MM). Both operations are integrated in Hardware (HW) as Programmable System on Chip (PSoC). The processor Microblaze of Xilinx is used for flexibility. Our objective is to achieve a best trade-off between execution time, occupied area and flexibility. In order to satisfy this constraint, Montgomery Power Ladder and Montgomery Modular Multiplication (MMM) algorithms are utilized for the ME and for the MM implementations as HW accelerators, respectively. Our implementation approach is based on the digit-serial method for performing the basic arithmetic operations. Efficient parallel and pipeline strategies are developed at the digit level for the optimization of the execution time. The application for 1024-bits data length shows that the MMM run in 6.24 µs and requires 647 slices. The ME is executed in 6.75 ms, using 2881 slices.

Group signature is a cryptographic primitive where any member can anonymously sign a message on behalf of the population they belong to. Several group signatures were proposed based on number-theor...

Lattice based cryptography plays an important role in the construction of post-quantum cryptography, including key exchange, public key encryption as well as digital signature schemes. Dating back to 2016, a new key exchange scheme called NewHope was proposed by Alkim, Ducas, Poppelmann, and Schwabe that based security on the quantum hardness of Ring Learning with Errors (RLWE) problem, and was later submitted to the NIST public competition of standard post-quantum cryptography. The new scheme is attractive as it is designed to achieve high performance. In this work, we concentrate on its performance on hardware platforms and propose an efficient implementation of NewHope on Xilinx Artix-7 7020 FPGA platform that consumes 3158 slices, 10285 LUTs, 6623 registers in the server side, and 3042 slices, 10345 LUTs, 6704 registers in the client side, achieving a 45% reduction in LUT, 30% reduction in FF while the total time utilization also decreases by 16% compared with the up to date and directly related work. Specifically, we can accomplish three phases of the key exchange in 39.8/61.7/ $21.4~\mu \text{s}$ respectively, operating in 153/152 MHz in server/client side.

Lattice-based cryptography is an extraordinarily popular subfield of cryptography. But since it is also a very young field, practical proposals for lattice-based cryptographic primitives have only recently started to emerge. Turning a cryptographic scheme into an implementation poses a range of questions, the arguably most important one being its concrete security: how do we ensure that any practically conceivable adversary is unable to break the scheme? In this thesis, we address two issues that arise in this context.Part I is concerned with basing cryptanalytic tools on a sound theoretical foundation. The common approach to analyzing a concrete cryptographic primitive is to analyze the performance of known algorithms to estimate the attack complexity of a hypothetical adversary. This requires a thorough theoretical understanding of the best performing algorithms. Unfortunately, for many subclasses of lattice algorithms there is a gap in our understanding, which leads to problems in the cryptanalytic process. In this part of the thesis we address these issues in two closely related subclasses of such algorithms. We develop new algorithms and analyze existing ones and show that in both cases it is possible to obtain algorithms that are simultaneously well understood in theory and competitive in practice.In Part II we focus on an integral part of most lattice-based schemes: sampling from a specific distribution over the integers. Implementing such a sampler securely and efficiently can be challenging for distributions commonly used in lattice-based schemes. We introduce new tools and security proofs that reduce the precision requirements for samplers, allowing more efficient implementations in a wide range of settings while maintaining high levels of security. Finally, we propose a new sampling algorithms with a unique set of properties desirable for implementations of cryptographic primitives.

ispartof: pages:163-193 ispartof: PUBLIC-KEY CRYPTOGRAPHY, PKC 2022, PT II vol:13178 pages:163-193 ispartof: 25th IACR International Conference on Practice and Theory of Public Key Cryptography (PKC) location:ELECTR NETWORK date:8 Mar - 11 Mar 2022 status: published

Saber is one of the four finalists in the ongoing NIST post-quantum cryptography standardization project. A significant portion of Saber's computation time is spent on computing polynomial multiplications in polynomial rings with powers-of-two moduli. We propose several optimization strategies for improving the performance of polynomial multiplier architectures for Saber, targeting different hardware platforms and diverse application goals. We propose two high-speed architectures that exploit the smallness of operand polynomials in Saber and can achieve great performance with a moderate area consumption. We also propose a lightweight multiplier that consumes only 541 LUTs and 301 FFs on a small Artix-7 FPGA.

Lattice based cryptography can be considered a candidate alternative for post-quantum cryptosystems offering key exchange, digital signature and encryption functionality. Number Theoretic Transform (NTT) can be utilized to achieve better performance for these functionalities, where polynomials are needed to be multiplied. NTT simplifies the multiplication overhead allowing point-wise multiplication by transforming the polynomials into the spectral domain and then inversing the result to the original domain. It is important to optimize this technique that is used in a wide range of computing systems. In this paper we study the feasibility of using OpenCL, a portable framework, to implement a parallelized version of NTT which allows deployment on heterogeneous platforms, such as Graphic Processing Units (GPUs) and Field Programmable Gate Arrays (FPGAs). We measure the performance of our implementation on a GPU and evaluate when and where such a deployment is beneficial. Our results showed that the proposed parallel implementation is a viable acceleration approach for these algorithms for lattice-based cryptography solutions.

The impending threat of large-scale quantum computers to classical RSA and ECC-based public-key cryptographic schemes prompted NIST to initiate a global level standardization process for post-quantum cryptography. This process which started in 2017 with 69 submissions is currently in its third and final round with seven main candidates and eight alternate candidates, out of which seven (7) out of the fifteen (15) candidates are schemes based on hard problems over structured lattices, known as lattice-based cryptographic schemes. Among the various parameters such as theoretical post-quantum (PQ) security guarantees, implementation cost and performance, resistance against physical attacks such as Side-Channel Analysis (SCA) and Fault Injection Analysis (FIA) has also emerged as an important criterion for standardization in the final round [1]. This is especially relevant for adoption of PQC in embedded devices, which are most likely used in environments where an attacker can have unimpeded physical access to the device.

Message authentication is crucial because it encourages participants to accept countermeasures and further transmit messages to legitimate users in a network while maintaining the legitimacy of the identity of network members. An unauthorized user cannot transmit false messages to a given network. Although traditional public key cryptography is suitable for message authentication, it is also easy to manage and generate keys, and, with the expansion of an entire network, the system needs a lot of computing power, which creates additional risks to network security. A more effective method, such as ring signature, can realize this function and guarantee more security. In this paper, we propose an anti-quantum ring signature scheme based on lattice, functionality analysis, and performance evaluation to demonstrate that this scheme supports unconditional anonymity and unforgeability. After efficiency analysis, our scheme proved more effective than the existing ring signature schemes in processing signature generation and verification. The proposed scheme was applied to VANETs that support strong security and unconditional anonymity to vehicles.

Several works have characterized weak instances of the Ring-LWE problem by exploring vulnerabilities arising from the use of algebraic structures. Although these weak instances are not addressed by worst-case hardness theorems, enabling other ring instantiations enlarges the scope of possible applications and favors the diversification of security assumptions. In this work, we extend the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. By doing so, we allow the Ring-LWE problem to be used over maximal real subfields of cyclotomic number fields. We prove that Twisted Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the twist factor does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. As a result, sampling from a spherical Gaussian distribution can be done directly in the respective number field while maintaining its format and standard deviation when seen in Zn via twisted embeddings.

In this paper, we present a GPU-based parallel algorithm for the Learning With Errors (LWE) problem using a lattice-based Bounded Distance Decoding (BDD) approach. To the best of our knowledge, this is the first GPU-based implementation for the LWE problem. Compared to the sequential BDD implementation of Lindner-Peikert and pruned-enumeration strategies by Kirshanova [1] , our GPU-based implementation is almost faster by a factor 6 and 9 respectively. The used GPU is NVIDIA GeForce GTX 1060 6G. We also provided a parallel implementation using two GPUs. The results showed that our algorithm is scalable and faster than the sequential version (Lindner-Peikert and pruned-enumeration) by a factor of almost 13 and 16 respectively. Moreover, the results showed that our parallel implementation using two GPUs is more efficient than Kirshanova et al. ’s parallel implementation using 20 CPU-cores.

As a category of algorithms to solve the shortest lattice vector problem, sieve algorithms have drawn more and more attention due to the prominent performance in recent years. Enumeration algorithms used to perform better in practice even though sieve algorithms are asymptotically faster. Combined with techniques like locality-sensitive hashing and rank reduction, sieve algorithms now are capable of competing with enumeration algorithms. In this work, we study sieve algorithms in solving the shortest vector problem on lattices by categorizing various sieve algorithms and elaborating on ideas and techniques used to improve sieve algorithms. In addition, we present several prospective directions worth future research.

Conventional RSA algorithm, being a basis for several proposed cryptosystems, has remarkable security laps with respect to confidentiality and integrity over the internet which can be compromised by state-of-the-art attacks, especially, for different types of data generation, transmission, and analysis by IoT applications. This security threat hindrance is considered to be a hard problem to solve on classical computers. However, bringing quantum mechanics into account, the concept no longer holds true. So, this calls out for the modification of the conventional pre-quantum RSA algorithm into a secure post-quantum cryptographic-based RSA technique. In this research, we propose a post-quantum lattice-based RSA (LB-RSA) for IoT-based cloud applications to secure the shared data and information. The proposed work is validated by implementing it in 60-dimensions. The key size is about 1.152×105-bits and generation time is 0.8 hours. Furthermore, it has been tested with AVISPA, which confirms security in the presence of an intruder. Moreover, the proposed LB-RSA technique is compared with the existing state-of-the-art techniques. The empirical results advocate that the proposed lattice-based variant is not only safe but beats counterparts in terms of secured data sharing.

In this article, we propose single-trace side-channel attacks against lattice-based key encapsulation mechanisms (KEMs) that are the third-round candidates of the national institute of standards and technology (NIST) standardization project. Specifically, we analyze the message encoding operation in the encapsulation phase of lattice-based KEMs to obtain an ephemeral session key. We conclude that a single-trace leakage implies a whole key recovery: the experimental results realized on a ChipWhisperer UFO STM32F3 target board achieve a success rate of 100% for $\mathsf {CRYSTALS-KYBER}$ and $\mathsf {SABER}$ regardless of an optimization level and those greater than 79% for $\mathsf {FrodoKEM}$ . We further demonstrate that the proposed attack methodologies are not restricted to the above algorithms but are widely applicable to other NIST post-quantum cryptography (PQC) candidates, including $\mathsf {NTRU Prime}$ and $\mathsf {NTRU}$ .

To efficiently authenticate the updated data in fog computing, this paper proposed a lattice-based incremental digital signature scheme. The proposed scheme is provable secure in the standard model whose security is based on the hardness of the shortest integer solution (SIS) problem. There are several characters of the proposed scheme that are suitable for the application in. Such as, most of the time-consuming computing operations in the proposed scheme can be finished by the parallel computing. As a result, the computing speed of the proposed scheme can be improved efficiently. On the other hand, compared with a known lattice-based incremental digital signature, both the public key size and the signature length are shorter. Then the store resource and the bandwidth of the fog device can be saved efficiently when it is used in fog computing. Furthermore, a simulated experiment is given to check the functions of the proposed scheme by Java language on PC. The result shows that the computing cost to update a signature is much less than that to resign a message. At the same time, the parallel computing and pre-computing can really efficiently improve the computing speed of the proposed scheme. Since the SIS problem is hard even on quantum computers, the proposed scheme also gives a post-quantum secure solution to authenticate the updated data in fog computing.

Number representation systems establish ways in which numbers are mapped to computer architectures, and how operations over the numbers are translated into computer instructions. The efficiency of public-key cryptography is strongly affected by the used number representations, as these systems are constructed from mathematically inspired problems to ensure security, and thus rely on operations over large integers. In this paper, unconventional representations systems, including the Residue Number System (RNS) and stochastic number representations, are systematically reviewed. Homomorphic representations, which allow for parties to operate on data without having access to their plaintext representation, are also considered. The main goal of this survey is to introduce the reader to key aspects of non-traditional number representations that may be exploited for public-key cryptography, without delving too much into the details. Examples of the methods and algorithms herein surveyed include subquadratic modular multiplication for isogeny-based cryptography, the acceleration of Goldreich-Goldwasser-Halevi (GGH) decryption by an order of magnitude, the improvement of the Direct Anonymous Attestation (DAA) protocol both in terms of storage requirements and the time taken to execute it, and efficient algorithm-hiding Fully Homomorphic Encryption (FHE). The implementation of this type of systems in both sequential and parallel platforms is analysed, and their performance is compared with traditional approaches. We hope this work sows the seed of further research on the application of non-positional number arithmetic to other cryptographic use-cases.

Group Key Exchange (GKE) is required for secure group communication with high confidentiality. In particular, a trusted authority can handle issues that happen by the malicious actions of group members, but it is expensive to deploy and not suitable in a dynamic setting where the network requires frequent membership status changes. To overcome these issues, we designed yet another quantum-resistant constant-round GKE based on lattice without a trusted authority based on Apon et al.'s protocol (PQCrypto 2019) by modifying their key computation phase. Then, we describe the novel dynamic authenticated GKE (called DRAG) with membership addition/deletion procedures in Ring Learning with Errors (RLWE) setting, while the former ones are built from Diffie-Hellman problem. Under the specific adversary who can leak the long-term secret key from the party, we suggest a rigorous proof of DRAG in the random oracle model based on the hardness assumption of RLWE problem and the property of Rényi divergence. As a proof of concept, implementation details are described to meet level 1 NIST security. Our implementation is reasonable for practical use since the total runtime to get a group secret key takes about 3 msec and it can be considered as a reference implementation of other quantum-resistant GKEs.

In this chapter, a secure digital remote patient monitoring solution is introduced. With this solution, a patient could be monitored and served remotely; health services could be provided to people far away from hospitals and by experts not necessarily available in the nearest hospital. In addition, the proposed solution applies eHealth concept to increase information sharing on the disease and patient awareness regarding their risk factors to improve self‐care.

Internet of Things (IoT) has proved to be one of a success subset of cyber-physical systems, and it is receiving much attention among end-users associated with various applications. However, with the popularization of the IoT technologies, network attacks on the IoT environment are also increasing. To mitigate these security attacks, one of the candidates’ choice is quantum-resistant authentication, but the widely used authentication schemes are inadequate because they cannot prevent the quantum computer attacks. Lattices serving as an extremely promising foundation for post-quantum cryptography have emerged, and hash proof systems (HPS) over lattices have attracted the attention in the quantum-resistant authentication. Most existing HPS schemes over lattices can be used for authentications, but most of HPSs constructions depend on the strong security scheme that can prevent the indistinguishable chosen-ciphertext attacks (CCA) and focus on single-bit encryption, which seems unpractical in the IoT environments. An open problem is how to Integrate the vector (or multi-bit) versions of HPS over lattices into IoT environment for authentication with high efficiency. In this paper, to instantiate HPS over lattices and make it more practical for IoT, we follow the methodology from foremost schemes and introduce the smooth projective hash function (SPHF) which is a special of HPS. Then we relax the CCA-secure requirement and give two elegant instantiations of SPHF with rigorous INDCPA security for the open problem by optimizing two classic encryptions over lattices. The key point of the optimization is that we use a diverse public key which cascades multiple learning with errors (LWE) instances instead of a matrix of LWE insurance while we can bypass the coarse straightforward composition.

Lattice-based cryptography (LBC) is one of the most promising classes of post-quantum cryptography (PQC) that is being considered for standardization. This brief proposes an optimized schoolbook polynomial multiplication (SPM) for compact LBC. We exploit the symmetric nature of Gaussian noise for bit reduction. Additionally, a single field-programmable gate array (FPGA) DSP block is used for two parallel multiplication operations per clock cycle. These optimizations enable a significant $2.2\times $ speedup along with reduced resources for dimension $n=256$ . The overall efficiency (throughput per slice) is $1.28\times $ higher than the conventional SPM, as well as contributing to a more compact LBC system compared to previously reported designs. The results targeting the FPGA platform show that the proposed design can achieve high hardware efficiency with reduced hardware area costs.

Routing and secure communication are important concerns in Delay Tolerant Networks (DTNs). Previously designed security schemes utilize traditional public key cryptosystems for entity and data security that provide security under some hard problems like integer factorization and discrete logarithmic problems. These algorithms are vulnerable to Quantum attacks. In this paper lattice based cryptosystem has been used first time for DTN security. Lattice based cryptosystems utilize post-quantum cryptographic algorithms which are unbreakable by quantum attacks. First we present a novel Hierarchical structure for DTN having intracluster and intercluster communications. Then, we propose a security design to provide end-to-end security to DTN application data using lattice based cryptographic signature and encryption algorithms, secure under LWE hard problem over lattices. For securing intracluster and intercluster communication, three new schemes have been proposed: (i) Lattice based hierarchical identity-based key agreement scheme, based on lattice based Diffie-Hellman key agreement protocol, secure under LWE assumption but adapted to hierarchical structure. (ii) To derive new session keys, i.e. keys for new joining nodes and for key refreshment, a new lattice based hierarchical identity-based key update scheme has been proposed, which is based on Singh et al.’s lattice based forward secure identity-based encryption algorithm, (iii) A lattice based non-interactive key agreement scheme, based on schemes proposed by Agrawal et al. and Singh et al., has been proposed for generating a secret key for two communicating nodes in different clusters. This design can effectively resist man-in-the-middle attack, replay attack, dictionary attack, and parallel session attack and maintains forward and backward secrecy.

Lattice-based cryptography is a promising candidate for post-quantum cryptosystems, and a large amount of research has been conducted on learning with errors (LWE) problems, which are believed to be resistant against quantum attacks. In this paper, we propose two new key encapsulation mechanisms (KEMs), called EMBLEM and R.EMBLEM, based on (ring) LWE problems. The new KEMs have two main features: (1) Their security is based on the (ring) LWE problem with small secrets, which leads to both a secret key of constant size (regardless of the LWE parameters) and a relatively large standard deviation of the discrete Gaussian distributions. (2) They rely on a new multi-bit encoding method that is suitable for (ring) LWE-based encryption schemes. Compared to Regev’s encoding method, the proposed method does not require any rounding operation for decoding, and in this sense, it is conceptually simpler and easier to understand. Concrete parameters of the KEMs targeting 128-bit security level (against classical attacks) are provided, and their performance is compared with that of previous (ring) LWE-based KEMs in the literature.

This paper evaluates the current cybersecurity vulnerability of the prolific use of Elliptical Curve Digital Signature Algorithm (ECDSA) cryptography in use by the Bitcoin Core, Ethereum, Bitcoin Cash, and enterprise blockchains such as Multi-Chain and Hyperledger projects Fabric, and Sawtooth Lake. These blockchains are being usedin media, health, finance, transportation and government with little understanding, acknowledgment of the risk and no known plans for mitigation and migration to safer public-key cryptography. The second aim is to evaluate ECDSA against the threat of Quantum Computing and propose the most practical National Institute of Standards and Technology (NIST) Post-Quantum Cryptography candidate algorithm lattice-based cryptography countermeasure that can be implemented near-term and provide a basis for a coordinated industry-wide lattice-based public-key implementation. Commercial quantum computing research and development is rapid and unpredictable, and it is difficult to predict the arrival of fault-tolerant quantum computing. The current state of covert and classified quantum computing research andadvancement is unknown and therefore, it would be a significant risk to blockchain and Internet technologies to delay or wait for the publication of draft standards. Since there are many hurdles Post-Quantum Cryptography (PQC) must overcome for standardisation, coordinated large-scale testing and evaluation should commence promptly.

Lattice trapdoors are an important primitive used in a wide range of cryptographic protocols, such as identity-based encryption (IBE), attribute-based encryption, functional encryption, and program obfuscation. In this paper, we present software implementations of the Gentry-Peikert-Vaikuntanathan (GPV) digital signature, IBE and ciphertext-policy attribute-based encryption (CP-ABE) schemes based on an efficient Gaussian sampling algorithm for trapdoor lattices, and demonstrate that these three important cryptographic protocols are practical. One important aspect of our implementation is that it supports prime moduli, which are required in many cryptographic schemes. Also, our implementation uses bases larger than two for the gadget matrix whereas most previous implementations use the binary base. We show that the use of higher bases significantly decreases execution times and storage requirements. We adapt IBE and CP-ABE schemes originally based on learning with errors (LWE) hardness assumptions to a more efficient Ring LWE (RLWE) construction. To the best of our knowledge, ours are the first implementations employing the Gaussian sampling for non-binary bases of the gadget matrix. The experimental results demonstrate that our lattice-based signature, IBE and CP-ABE implementations, which are based on standard assumptions with post-quantum security, provide a performance comparable to the recent state-of-the-art implementation works based on stronger/non-post-quantum assumptions.

Among post-quantum alternatives, latticebased cryptography is the most promising one, due to its simple operations, reduction from aver-age-case to worstcase hardness, and supporting of rich functionalities. Ring signature enables a user to sign anonymously on behalf of an adaptively chosen group, and has multiple applications in anonymous e-voting, anonymous authentication, whistle blowing etc. However, most lattice-based ring signature schemes were constructed in the random oracle model from lattice basis delegation and they suffer large verification key sizes as a common disadvantage. This work proposes an efficient ring signature scheme from lattice basis delegation without random oracle based on the extended split-SIS problem, whose security is approximately as hard as the worst-case SIVP problem. Our scheme is proved to be anonymous and existentially unforgeable under latticebased assumptions. Finally, the verification key size is significantly reduced to a small constant, instead of increasing linearly with the number of ring members.

Over the past decade, the hybrid lattice-reduction and meet-in-the middle attack (called hybrid attack) has been used to evaluate the security of many lattice-based cryptographic schemes such as NTRU, NTRU Prime, BLISS and more. However, unfortunately, none of the previous analyses of the hybrid attack is entirely satisfactory: They are based on simplifying assumptions that may distort the security estimates. Such simplifying assumptions include setting probabilities equal to 1, which, for the parameter sets we analyze in this work, are in fact as small as 2 - 80 2^{-80} . Many of these assumptions lead to underestimating the scheme’s security. However, some lead to security overestimates, and without further analysis, it is not clear which is the case. Therefore, the current security estimates against the hybrid attack are not reliable, and the actual security levels of many lattice-based schemes are unclear. In this work, we present an improved runtime analysis of the hybrid attack that is based on more reasonable assumptions. In addition, we reevaluate the security against the hybrid attack for the NTRU, NTRU Prime and R-BinLWEEnc encryption schemes as well as for the BLISS and GLP signature schemes. Our results show that there exist both security over- and underestimates in the literature.

In this paper, we provide a mathematical background and analysis of Lattice Based Cryptography for the less mathematically mature reader. Discussing the benefits and constraints of Lattice Based Crypto, we compare and contrast with Elliptic Curve Cryptography to provide an understanding of what the limitations of Lattice Based Cryptography are, and what needs to be achieved for the quantum resistant protocols to be deploy-able to any and all devices.

The security of lattice-based cryptosystems is based on solving hard lattice problems such as the shortest vector problem (SVP) and the closest vector problem (CVP). Various cryptanalysis algorithms such as (Pro)GaussSieve, HashSieve, ENUM, and BKZ have been proposed to solve these hard problems. Several implementations of these algorithms have been developed. On the other hand, the implementations of these algorithms are expected to be efficient in terms of run time and memory space. In this paper, a modular software package/library containing efficient implementations of GaussSieve, ProGaussSieve, HashSieve, and BKZ algorithms is developed. These implementations are considered efficient in terms of run time. While constructing this software library, some modifications to the algorithms are made to increase the performance. Then, the run times of these implementations are compared with the others. According to the experimental results, the proposed GaussSieve, ProGaussSieve, and HashSieve implementations are at least 70%, 75%, and 49% more efficient than previous ones, respectively.

The lattice-based cryptography (LBC) has been widely used recently in many compute-intensive applications, such as the post-quantum cryptography (PQC) and privacy-preserving deep learning, where the main task for such applications is to improve the computational efficiency. The modular multiplication operations, mainly involved in the number theoretic transform (NTT), comprise a large proportion of the whole computations required by an LBC. This paper presents a novel "decompose-and-reduce" modular multiplication algorithm (DARM), considering primes with the form of q = 22N −δ and δ 2 q⌉ = 60 and n = 4096, the NTT implementation with DARM achieves up to 41.2% and 61.2% reductions in LUTs and DSPs, respectively.

In this work, we are concerned with the hardening of post-quantum key encapsulation mechanisms (KEM) against side-channel attacks, with a focus on the comparison operation required for the Fujisaki-Okamoto (FO) transform. We identify critical vulnerabilities in two proposals for masked comparison and successfully attack the masked comparison algorithms from TCHES 2018 and TCHES 2020. To do so, we use first-order side-channel attacks and show that the advertised security properties do not hold. Additionally, we break the higher-order secured masked comparison from TCHES 2020 using a collision attack, which does not require side-channel information. To enable implementers to spot such flaws in the implementation or underlying algorithms, we propose a framework that is designed to test the re-encryption step of the FO transform for information leakage. Our framework relies on a specifically parametrized t-test and would have identified the previously mentioned flaws in the masked comparison. Our framework can be used to test both the comparison itself and the full decapsulation implementation.