Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                



Dates are inconsistent

Dates are inconsistent

136 results sorted by ID

2024/1791 (PDF) Last updated: 2024-11-02
Discrete gaussian sampling for BKZ-reduced basis
Amaury Pouly, Yixin Shen
Public-key cryptography

Discrete Gaussian sampling on lattices is a fundamental problem in lattice-based cryptography. In this paper, we revisit the Markov chain Monte Carlo (MCMC)-based Metropolis-Hastings-Klein (MHK) algorithm proposed by Wang and Ling and study its complexity under the Geometric Series Assuption (GSA) when the given basis is BKZ-reduced. We give experimental evidence that the GSA is accurate in this context, and we give a very simple approximate formula for the complexity of the sampler that is...

2024/1709 (PDF) Last updated: 2024-10-19
Do Not Disturb a Sleeping Falcon: Floating-Point Error Sensitivity of the Falcon Sampler and Its Consequences
Xiuhan Lin, Mehdi Tibouchi, Yang Yu, Shiduo Zhang
Public-key cryptography

Falcon is one of the three postquantum signature schemes already selected by NIST for standardization. It is the most compact among them, and offers excellent efficiency and security. However, it is based on a complex algorithm for lattice discrete Gaussian sampling which presents a number of implementation challenges. In particular, it relies on (possibly emulated) floating-point arithmetic, which is often regarded as a cause for concern, and has been leveraged in, e.g., side-channel...

2024/1490 (PDF) Last updated: 2024-10-10
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\#\mathsf{P}$-Hardness
Dakshita Khurana, Kabir Tomer
Foundations

Recent oracle separations [Kretschmer, TQC'21, Kretschmer et. al., STOC'23] have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if the polynomial hierarchy collapses. We realize this possibility by building quantum bit commitments and secure computation from unrelativized, well-studied mathematical problems that are conjectured to be hard for $\mathsf{P}^{\#\mathsf{P}}$ -- such as approximating the permanents of complex Gaussian...

2024/1248 (PDF) Last updated: 2024-10-31
A Not So Discrete Sampler: Power Analysis Attacks on HAWK signature scheme
Morgane Guerreau, Mélissa Rossi
Attacks and cryptanalysis

HAWK is a lattice-based signature scheme candidate to the fourth call of the NIST's Post-Quantum standardization campaign. Considered as a cousin of Falcon (one of the future NIST post-quantum standards) one can wonder whether HAWK shares the same drawbacks as Falcon in terms of side-channel attacks. Indeed, Falcon signature algorithm and particularly its Gaussian sampler, has shown to be highly vulnerable to power-analysis attacks. Besides, efficiently protecting Falcon's signature...

2024/1065 (PDF) Last updated: 2024-06-30
AITIA: Efficient Secure Computation of Bivariate Causal Discovery
Truong Son Nguyen, Lun Wang, Evgenios M. Kornaropoulos, Ni Trieu
Cryptographic protocols

Researchers across various fields seek to understand causal relationships but often find controlled experiments impractical. To address this, statistical tools for causal discovery from naturally observed data have become crucial. Non-linear regression models, such as Gaussian process regression, are commonly used in causal inference but have limitations due to high costs when adapted for secure computation. Support vector regression (SVR) offers an alternative but remains costly in an...

2024/960 (PDF) Last updated: 2024-06-14
Designs for practical SHE schemes based on Ring-LWR
Madalina Bolboceanu, Anamaria Costache, Erin Hales, Rachel Player, Miruna Rosca, Radu Titiu
Public-key cryptography

The Learning with Errors problem (LWE) and its variants are among the most popular assumptions underlying lattice-based cryptography. The Learning with Rounding problem (LWR) can be thought of as a deterministic variant of LWE. While lattice-based cryptography is known to enable many advanced constructions, constructing Fully Homomorphic Encryption schemes based on LWR remains an under-explored part of the literature. In this work, we present a thorough study of Somewhat Homomorphic...

2024/411 (PDF) Last updated: 2024-07-08
Polytopes in the Fiat-Shamir with Aborts Paradigm
Henry Bambury, Hugo Beguinet, Thomas Ricosset, Eric Sageloli
Public-key cryptography

The Fiat-Shamir with Aborts paradigm (FSwA) uses rejection sampling to remove a secret’s dependency on a given source distribution. Recent results revealed that unlike the uniform distribution in the hypercube, both the continuous Gaussian and the uniform distribution within the hypersphere minimise the rejection rate and the size of the proof of knowledge. However, in practice both these distributions suffer from the complexity of their sampler. So far, those three distributions are the...

2024/026 (PDF) Last updated: 2024-01-08
Towards Compact Identity-based Encryption on Ideal Lattices
Huiwen Jia, Yupu Hu, Chunming Tang, Lin Wang
Public-key cryptography

Basic encryption and signature on lattices have comparable efficiency to their classical counterparts in terms of speed and key size. However, Identity-based Encryption (IBE) on lattices is much less efficient in terms of compactness, even when instantiated on ideal lattices and in the Random Oracle Model (ROM). This is because the underlying preimage sampling algorithm used to extract the users' secret keys requires huge public parameters. In this work, we specify a compact IBE...

2023/1654 (PDF) Last updated: 2023-10-25
On Gaussian sampling, smoothing parameter and application to signatures
Thomas Espitau, Alexandre Wallet, Yang Yu
Foundations

We present a general framework for polynomial-time lattice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of lattices; we first show that given lattices $\Lambda'\subset \Lambda$ we can sample efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of $\Lambda'$. As a direct application, we...

2023/1628 (PDF) Last updated: 2024-09-11
Cryptanalysis of the Peregrine Lattice-Based Signature Scheme
Xiuhan Lin, Moeto Suzuki, Shiduo Zhang, Thomas Espitau, Yang Yu, Mehdi Tibouchi, Masayuki Abe
Attacks and cryptanalysis

The Peregrine signature scheme is one of the candidates in the ongoing Korean post-quantum cryptography competition. It is proposed as a high-speed variant of Falcon, which is a hash-and-sign signature scheme over NTRU lattices and one of the schemes selected by NIST for standardization. To this end, Peregrine replaces the lattice Gaussian sampler in the Falcon signing procedure with a new sampler based on the centered binomial distribution. While this modification offers significant...

2023/1594 (PDF) Last updated: 2024-06-08
Secure Noise Sampling for DP in MPC with Finite Precision
Hannah Keller, Helen Möllering, Thomas Schneider, Oleksandr Tkachenko, Liang Zhao
Cryptographic protocols

While secure multi-party computation (MPC) protects the privacy of inputs and intermediate values of a computation, differential privacy (DP) ensures that the output itself does not reveal too much about individual inputs. For this purpose, MPC can be used to generate noise and add this noise to the output. However, securely generating and adding this noise is a challenge considering real-world implementations on finite-precision computers, since many DP mechanisms guarantee privacy only...

2023/1498 (PDF) Last updated: 2024-10-06
LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling
Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo, Yaxin Tu
Foundations

The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE. To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] defined S|LWE> and C|LWE> problems by encoding the error of LWE samples into quantum amplitudes, and showed efficient quantum algorithms for a few interesting amplitudes. However, algorithms or hardness results of the most...

2023/1477 (PDF) Last updated: 2023-11-13
G+G: A Fiat-Shamir Lattice Signature Based on Convolved Gaussians
Julien Devevey, Alain Passelègue, Damien Stehlé
Public-key cryptography

We describe an adaptation of Schnorr's signature to the lattice setting, which relies on Gaussian convolution rather than flooding or rejection sampling as previous approaches. It does not involve any abort, can be proved secure in the ROM and QROM using existing analyses of the Fiat-Shamir transform, and enjoys smaller signature sizes (both asymptotically and for concrete security levels).

2023/1335 (PDF) Last updated: 2023-10-03
Antrag: Annular NTRU Trapdoor Generation
Thomas Espitau, Thi Thu Quyen Nguyen, Chao Sun, Mehdi Tibouchi, Alexandre Wallet
Public-key cryptography

In this paper, we introduce a novel trapdoor generation technique for Prest's hybrid sampler over NTRU lattices. Prest's sampler is used in particular in the recently proposed Mitaka signature scheme (Eurocrypt 2022), a variant of the Falcon signature scheme, one of the candidates selected by NIST for standardization. Mitaka was introduced to address Falcon's main drawback, namely the fact that the lattice Gaussian sampler used in its signature generation is highly...

2023/1288 (PDF) Last updated: 2023-08-28
An erf Analog for Discrete Gaussian Sampling
Nicolas Gama, Anand Kumar Narayanan, Ryder LiuLin, Dongze Yue
Foundations

Most of the current lattice-based cryptosystems rely on finding Gaussian Samples from a lattice that are close to a given target. To that end, two popular distributions have been historically defined and studied: the Rounded Gaussian distribution and the Discrete Gaussian distribution. The first one is nearly trivial to sample: simply round the coordinates of continuous Gaussian samples to their nearest integer. Unfortunately, the security of resulting cryptosystems are not as well...

2023/908 (PDF) Last updated: 2023-06-11
A Hardware-Software Co-Design for the Discrete Gaussian Sampling of FALCON Digital Signature
Emre Karabulut, Aydin Aysu
Implementation

Sampling random values from a discrete Gaussian distribution with high precision is a major and computationally intensive operation of upcoming or existing cryptographic standards. FALCON is one such algorithm that the National Institute of Standards and Technology chose to standardize as a next-generation, quantum-secure digital signature algorithm. The discrete Gaussian sampling of FALCON has both flexibility and efficiency needs—it constitutes 72% of total signature generation in...

2023/797 (PDF) Last updated: 2024-03-08
Entropy Suffices for Guessing Most Keys
Timo Glaser, Alexander May, Julian Nowakowski
Attacks and cryptanalysis

Historically, most cryptosystems chose their keys uniformly at random. This is in contrast to modern (lattice-based) schemes, which typically sample their keys from more complex distributions $\mathcal{D}$, such as the discrete Gaussian or centered binomial distribution. It is well-known that any key drawn from the uniform distribution $\mathcal{U}$ can be guessed using at most $2^{\operatorname{H}(\mathcal{U})}$ key guesses, where $\operatorname{H}(\mathcal{U})$ denotes the entropy of...

2023/729 (PDF) Last updated: 2023-05-21
Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures
Yang Yu, Huiwen Jia, Xiaoyun Wang
Public-key cryptography

Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions. For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based...

2023/699 (PDF) Last updated: 2024-04-19
Lattice-based, more general anti-leakage model and its application in decentralization
Xiaokang Dai, Jingwei Chen, Wenyuan Wu, Yong Feng
Cryptographic protocols

In the case of standard \LWE samples $(\mathbf{A},\mathbf{b = sA + e})$, $\mathbf{A}$ is typically uniformly over $\mathbb{Z}_q^{n \times m}$. Under the \DLWE assumption, the conditional distribution of $\mathbf{s}|(\mathbf{A}, \mathbf{b})$ and $\mathbf{s}$ is expected to be consistent. However, in the case where an adversary chooses $\mathbf{A}$ adaptively, the disparity between the two entities may be larger. In this work, our primary focus is on the quantification of the Average...

2023/479 (PDF) Last updated: 2023-04-03
Spherical Gaussian Leftover Hash Lemma via the Rényi Divergence
Hiroki Okada, Kazuhide Fukushima, Shinsaku Kiyomoto, Tsuyoshi Takagi
Foundations

Agrawal et al. (Asiacrypt 2013) proved the discrete Gaussian leftover hash lemma, which states that the linear transformation of the discrete spherical Gaussian is statistically close to the discrete ellipsoid Gaussian. Showing that it is statistically close to the discrete spherical Gaussian, which we call the discrete spherical Gaussian leftover hash lemma (SGLHL), is an open problem posed by Agrawal et al. In this paper, we solve the problem in a weak sense: we show that the distribution...

2023/446 (PDF) Last updated: 2024-06-17
Phoenix: Hash-and-Sign with Aborts from Lattice Gadgets
Corentin Jeudy, Adeline Roux-Langlois, Olivier Sanders
Public-key cryptography

Preimage sampling is a fundamental tool in lattice-based cryptography, and its performance directly impacts that of the cryptographic mechanisms relying on it. In 2012, Micciancio and Peikert proposed a new way of generating trapdoors (and an associated preimage sampling procedure) with very interesting features. Unfortunately, in some applications such as digital signatures, the performance may not be as competitive as other approaches like Fiat-Shamir with Aborts. In an effort to improve...

2023/372 (PDF) Last updated: 2023-03-15
Practically Solving LPN in High Noise Regimes Faster Using Neural Networks
Haozhe Jiang, Kaiyue Wen, Yilei Chen
Attacks and cryptanalysis

We conduct a systematic study of solving the learning parity with noise problem (LPN) using neural networks. Our main contribution is designing families of two-layer neural networks that practically outperform classical algorithms in high-noise, low-dimension regimes. We consider three settings where the numbers of LPN samples are abundant, very limited, and in between. In each setting we provide neural network models that solve LPN as fast as possible. For some settings we are also able to...

2023/224 (PDF) Last updated: 2023-02-19
Improved Power Analysis Attacks on Falcon
Shiduo Zhang, Xiuhan Lin, Yang Yu, Weijia Wang
Attacks and cryptanalysis

Falcon is one of the three post-quantum signature schemes selected for standardization by NIST. Due to its low bandwidth and high efficiency, Falcon is seen as an attractive option for quantum-safe embedded systems. In this work, we study Falcon's side-channel resistance by analysing its Gaussian samplers. Our results are mainly twofold. The first result is an improved key recovery exploiting the leakage within the base sampler investigated by Guerreau et al. (CHES 2022). Instead of...

2023/142 (PDF) Last updated: 2023-02-06
On the Feasibility of Single-Trace Attacks on the Gaussian Sampler using a CDT
Soundes Marzougui, Ievgan Kabin, Juliane Krämer, Thomas Aulbach, Jean-Pierre Seifert
Applications

We present a single-trace attack against lattice-based KEMs using the cumulative distribution table for Gaussian sampling and execute it in a real-world environment. Our analysis takes a single power trace of the decapsulation algorithm as input and exploits leakage of the Gaussian sampling subroutine to reveal the session key. We investigated the feasibility of the attack on different boards and proved that the power consumption traces become less informative with higher clock frequencies....

2022/1690 (PDF) Last updated: 2024-06-05
LUNA: Quasi-Optimally Succinct Designated-Verifier Zero-Knowledge Arguments from Lattices
Ron Steinfeld, Amin Sakzad, Muhammed F. Esgin, Veronika Kuchta, Mert Yassi, Raymond K. Zhao
Cryptographic protocols

We introduce the first candidate Lattice-based designated verifier (DV) zero knowledge sUccinct Non-interactive Argument (ZK-SNARG) protocol, LUNA, with quasi-optimal proof length (quasi-linear in the security/privacy parameter). By simply relying on mildly stronger security assumptions, LUNA is also a candidate ZK-SNARK (i.e. argument of knowledge). LUNA achieves significant improvements in concrete proof sizes, reaching below 6 KB (compared to >32 KB in prior work) for 128-bit...

2022/1631 (PDF) Last updated: 2023-06-11
Enhancing Ring-LWE Hardness using Dedekind Index Theorem
Charanjit S Jutla, Chengyu Lin
Foundations

In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the...

2022/1495 (PDF) Last updated: 2022-10-31
Peregrine: Toward Fastest FALCON Based on GPV Framework
Eun-Young Seo, Young-Sik Kim, Joon-Woo Lee, Jong-Seon No
Public-key cryptography

FALCON and Crystals-Dilithium are the digital signatures algorithms selected as NIST PQC standards at the end of the third round. FALCON has the advantage of the shortest size of the combined public key and signature but has the disadvantage of the relatively long signing time. Since FALCON algorithm is faithfully designed based on theoretical security analysis, the implementation of the algorithms is quite complex and needs considerable complexity. In order to implement the FALCON...

2022/1490 (PDF) Last updated: 2022-10-30
Efficient Gaussian sampling for RLWE-based cryptography through a fast Fourier transform
Marcio Barbado Junior
Applications

Quantum computing threatens classical cryptography, leading to the search for stronger alternatives. The cryptographic approach based on lattices is considered as a viable option. Schemes with that approach use Gaussian sampling, a design which brings along two concerns: efficiency and information leakage. This work addresses those concerns in the RLWE formulation, for digital signatures. Efficiency mitigation uses the central limit theorem, and the Walsh–Hadamard transform, whereas the...

2022/1459 (PDF) Last updated: 2024-03-08
Circuit Privacy for FHEW/TFHE-Style Fully Homomorphic Encryption in Practice
Kamil Kluczniak
Public-key cryptography

A fully homomorphic encryption (FHE) scheme allows a client to encrypt and delegate its data to a server that performs computation on the encrypted data that the client can then decrypt. While FHE gives confidentiality to clients' data, it does not protect the server's input and computation. Nevertheless, FHE schemes are still helpful in building delegation protocols that reduce communication complexity, as the ciphertext's size is independent of the size of the computation performed on...

2022/1438 (PDF) Last updated: 2024-03-12
Plug-and-play sanitization for TFHE
Florian Bourse, Malika Izabachène
Public-key cryptography

Fully Homomorphic encryption allows the evaluation of any circuits over encrypted data while preserving the privacy of the data. However, without any additional properties, no guarantee is provided for the privacy of the circuits which are evaluated. A sanitization algorithm allows to destroy all previous information about how a ciphertext was obtained, ensuring that the circuit which was evaluated remains secret. In this paper, we present two techniques to randomize RLWE ciphertexts, and...

2022/1227 (PDF) Last updated: 2022-09-16
How to Sample a Discrete Gaussian (and more) from a Random Oracle
George Lu, Brent Waters
Foundations

The random oracle methodology is central to the design of many practical cryptosystems. A common challenge faced in several systems is the need to have a random oracle that outputs from a structured distribution $\mathcal{D}$, even though most heuristic implementations such as SHA-3 are best suited for outputting bitstrings. Our work explores the problem of sampling from discrete Gaussian (and related) distributions in a manner that they can be programmed into random oracles. We...

2022/903 (PDF) Last updated: 2022-09-23
Cycle-Accurate Power Side-Channel Analysis Using the ChipWhisperer: a Case Study on Gaussian Sampling
Nils Wisiol, Patrick Gersch, Jean-Pierre Seifert
Attacks and cryptanalysis

This paper presents an approach to uncover and analyze power side-channel leakages on a processor cycle level precision. By carefully designing and evaluating the measurement setup, accurate trace timing is enabled, which is used to overlay the trace with the corresponding assembly code. This methodology allows to expose the sources of leakage on a processor cycle scale, which allows for evaluating new implementations. It also exposes that the default ChipWhisperer configuration for STM32F4...

2022/785 (PDF) Last updated: 2023-07-04
Shorter Hash-and-Sign Lattice-Based Signatures
Thomas Espitau, Mehdi Tibouchi, Alexandre Wallet, Yang Yu
Public-key cryptography

Lattice-based digital signature schemes following the hash-and-sign design paradigm of Gentry, Peikert and Vaikuntanathan (GPV) tend to offer an attractive level of efficiency, particularly when instantiated with structured compact trapdoors. In particular, NIST postquantum finalist Falcon is both quite fast for signing and verification and quite compact: NIST notes that it has the smallest bandwidth (as measured in combined size of public key and signature) of all round 2 digital signature...

2022/482 (PDF) Last updated: 2022-04-23
cuFE: High Performance Privacy Preserving Support Vector Machine with Inner-Product Functional Encryption
KyungHyun Han, Wai-Kong Lee, Angshuman Karmakar, Jose Maria Bermudo Mera, Seong Oun Hwang
Public-key cryptography

Privacy preservation is a sensitive issue in our modern society. It is becoming increasingly important in many applications in this ever-growing and highly connected digital era. Functional encryption is a computation on encrypted data paradigm that allows users to retrieve the evaluation of a function on encrypted data without revealing the data, thus effectively protecting users' privacy. However, existing functional encryption implementations are still very time-consuming for practical...

2022/472 (PDF) Last updated: 2022-12-01
On the Hardness of Module Learning With Errors with Short Distributions
Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen
Foundations

The Module Learning With Errors problem (M-LWE) is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE, i.e., uniform secret modulo $q$ and Gaussian error) and practical schemes (small...

2022/437 (PDF) Last updated: 2022-11-02
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
Foundations

We show direct and conceptually simple reductions between the classical learning with errors (LWE) problem and its continuous analog, CLWE (Bruna, Regev, Song and Tang, STOC 2021). This allows us to bring to bear the powerful machinery of LWE-based cryptography to the applications of CLWE. For example, we obtain the hardness of CLWE under the classical worst-case hardness of the gap shortest vector problem. Previously, this was known only under quantum worst-case hardness of lattice...

2022/295 (PDF) Last updated: 2023-01-07
Quantum Proofs of Deletion for Learning with Errors
Alexander Poremba
Cryptographic protocols

Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mutually incompatible observables cannot be measured at the same time. Recent work by Broadbent and Islam (TCC 2020) builds on this aspect of quantum mechanics to realize a cryptographic notion called certified deletion. While this remarkable notion enables a classical verifier to be convinced that a (private-key)...

2022/204 (PDF) Last updated: 2022-02-20
RevEAL: Single-Trace Side-Channel Leakage of the SEAL Homomorphic Encryption Library
Furkan Aydin, Emre Karabulut, Seetal Potluri, Erdem Alkim, Aydin Aysu

This paper demonstrates the first side-channel attack on homomorphic encryption (HE), which allows computing on encrypted data. We reveal a power-based side-channel leakage of Microsoft SEAL prior to v3.6 that implements the Brakerski/Fan-Vercauteren (BFV) protocol. Our proposed attack targets the Gaussian sampling in the SEAL’s encryption phase and can extract the entire message with a single power measurement. Our attack works by (1) identifying each coefficient index being sampled, (2)...

2022/093 (PDF) Last updated: 2022-11-07
Public-Key Encryption from Homogeneous CLWE
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen
Public-key cryptography

The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known. We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time...

2021/1664 (PDF) Last updated: 2021-12-20
Towards a Simpler Lattice Gadget Toolkit
Shiduo Zhang, Yang Yu
Public-key cryptography

As a building block, gadgets and associated algorithms are widely used in advanced lattice cryptosystems. The gadget algorithms for power-of-base moduli are very efficient and simple, however the current algorithms for arbitrary moduli are still complicated and practically more costly despite several efforts. Considering the necessity of arbitrary moduli, developing simpler and more practical gadget algorithms for arbitrary moduli is crucial to improving the practical performance of lattice...

2021/1486 (PDF) Last updated: 2022-05-28
Mitaka: a simpler, parallelizable, maskable variant of Falcon
Thomas Espitau, Pierre-Alain Fouque, François Gérard, Mélissa Rossi, Akira Takahashi, Mehdi Tibouchi, Alexandre Wallet, Yang Yu
Public-key cryptography

This work describes the Mitaka signature scheme: a new hash-and-sign signature scheme over NTRU lattices which can be seen as a variant of NIST finalist Falcon. It achieves comparable efficiency but is considerably simpler, online/offline, and easier to parallelize and protect against side-channels, thus offering significant advantages from an implementation standpoint. It is also much more versatile in terms of parameter selection. We obtain this signature scheme by replacing the FFO...

2021/1415 (PDF) Last updated: 2021-10-24
A Note on the Pseudorandomness of Low-Degree Polynomials over the Integers
Aayush Jain, Alexis Korb, Paul Lou, Amit Sahai
Foundations

We initiate the study of a problem called the Polynomial Independence Distinguishing Problem (PIDP). The problem is parameterized by a set of polynomials $\mathcal{Q}=(q_1,\ldots, q_m)$ where each $q_i:\mathbb{R}^n\rightarrow \mathbb{R}$ and an input distribution $\mathcal{D}$ over the reals. The goal of the problem is to distinguish a tuple of the form $\{ q_i,q_i(\mathbf{x})\}_{i\in [m]} $ from $\{ q_i,q_i(\mathbf{x}_i)\}_{i\in [m]} $ where $\mathbf{x}, \mathbf{x}_1,\ldots ,...

2021/752 (PDF) Last updated: 2023-06-02
Quantum Reduction of Finding Short Code Vectors to the Decoding Problem
Thomas Debris-Alazard, Maxime Remaud, Jean-Pierre Tillich
Public-key cryptography

We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehlé-Steinfield-Tanaka-Xagawa’ re-interpretation of Regev's quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed...

2021/585 (PDF) Last updated: 2021-06-01
Exact Lattice Sampling from Non-Gaussian Distributions
Maxime Plançon, Thomas Prest
Public-key cryptography

We propose a new framework for trapdoor sampling over lattices. Our framework can be instantiated in a number of ways. In a departure from classical samplers, it allows for example to sample from uniform, affine, ``product affine'' and exponential distributions. It allows for example to sample from uniform, affine and ``product affine'' distributions. Another salient point of our framework is that the output distributions of our samplers are perfectly indistinguishable from ideal ones, in...

2021/523 (PDF) Last updated: 2022-03-17
No Time to Hash: On Super Efficient Entropy Accumulation
Yevgeniy Dodis, Siyao Guo, Noah Stephens-Davidowitz, Zhiye Xie
Foundations

Real-world random number generators (RNGs) cannot afford to use (slow) cryptographic hashing every time they refresh their state $R$ with a new entropic input $X$. Instead, they use ``superefficient'' simple entropy-accumulation procedures, such as $$R \leftarrow \mathsf{rot}_{\alpha, n}(R) \oplus X,$$ where $\mathsf{rot}_{\alpha,n}$ rotates an $n$-bit state $R$ by some fixed number $\alpha$. For example, Microsoft's RNG uses $\alpha=5$ for $n=32$ and $\alpha=19$ for $n=64$. Where do these...

2021/265 (PDF) Last updated: 2021-03-03
On the Hardness of Module-LWE with Binary Secret
Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen
Foundations

We prove that the Module Learning With Errors (M-LWE) problem with binary secrets and rank $d$ is at least as hard as the standard version of M-LWE with uniform secret and rank $k$, where the rank increases from $k$ to $d \geq (k+1)\log_2 q + \omega(\log_2 n)$, and the Gaussian noise from $\alpha$ to $\beta = \alpha \cdot \Theta(n^2\sqrt{d})$, where $n$ is the ring degree and $q$ the modulus. Our work improves on the recent work by Boudgoust et al. in 2020 by a factor of $\sqrt{md}$ in the...

2021/222 (PDF) Last updated: 2023-12-27
Quantum-safe HIBE: does it cost a Latte?
Raymond K. Zhao, Sarah McCarthy, Ron Steinfeld, Amin Sakzad, Máire O’Neill
Implementation

The United Kingdom (UK) government is considering advanced primitives such as identity-based encryption (IBE) for adoption as they transition their public-safety communications network from TETRA to an LTE-based service. However, the current LTE standard relies on elliptic-curve-based IBE, which will be vulnerable to quantum computing attacks, expected within the next 20-30 years. Lattices can provide quantum-safe alternatives for IBE. These schemes have shown promising results in terms of...

2021/199 (PDF) Last updated: 2021-12-09
Generic, Efficient and Isochronous Gaussian Sampling over the Integers
Shuo Sun, Yongbin Zhou, Yunfeng Ji, Rui Zhang, Yang Tao
Public-key cryptography

Gaussian sampling over the integers is one of the fundamental building blocks of lattice-based cryptography. Among the extensively used trapdoor sampling algorithms, it's ineluctable until now. Under the influence of numerous side-channel attacks, it's still challenging to construct a Gaussian sampler that is generic, efficient, and resistant to timing attacks. In this paper, our contribution is three-fold. First, we propose a secure, efficient exponential Bernoulli sampling algorithm. It...

2021/048 (PDF) Last updated: 2022-09-08
Efficient Lattice Gadget Decomposition Algorithm with Bounded Uniform Distribution
Sohyun Jeon, Hyang-Sook Lee, Jeongeun Park
Foundations

A gadget decomposition algorithm is commonly used in many advanced lattice cryptography applications which support homomorphic operation over ciphertexts to control the noise growth. For a special structure of a gadget, the algorithm is digit decomposition. If such algorithm samples from a subgaussian distribution, that is, the output is randomized, it gives more benefits on output quality. One of important advantages is Pythagorean additivity which makes resulting noise contained in a...

2020/1250 (PDF) Last updated: 2020-10-09
A New Code Based Signature Scheme without Trapdoors
Zhe Li, Chaoping Xing, Sze Ling Yeo
Public-key cryptography

We present a signature scheme for Hamming metric random linear codes via the Schnorr-Lyubashevsky framework that employs the rejection sampling on appropriate probability distributions instead of using trapdoors. Such an approach has been widely believed to be more challenging for linear codes as compared to lattices with Gaussian distributions. We prove that our signature scheme achieves EUF-CMA security under the assumption of the decoding one out of many problem or achieves strong EUF-CMA...

2020/337 (PDF) Last updated: 2020-03-18
Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography
Nicholas Genise, Daniele Micciancio, Chris Peikert, Michael Walter
Foundations

Discrete Gaussian distributions over lattices are central to lattice-based cryptography, and to the computational and mathematical aspects of lattices more broadly. The literature contains a wealth of useful theorems about the behavior of discrete Gaussians under convolutions and related operations. Yet despite their structural similarities, most of these theorems are formally incomparable, and their proofs tend to be monolithic and written nearly "from scratch,'' making them unnecessarily...

2020/260 (PDF) Last updated: 2020-02-25
Lattice-based (Partially) Blind Signature without Restart
Samuel Bouaziz-Ermann, Sébastien Canard, Gautier Eberhart, Guillaume Kaim, Adeline Roux-Langlois, Jacques Traoré
Public-key cryptography

We present in this paper a blind signature and its partially blind variant based on lattices assumptions. Blind signature is a cornerstone in privacy-oriented cryptography and we propose the first lattice based scheme without restart. Compare to related work, the key idea of our construction is to provide a trapdoor to the signer in order to let him perform some gaussian pre-sampling during the signature generation process, preventing this way to restart from scratch the whole protocol. We...

2020/119 (PDF) Last updated: 2020-06-23
Hardness of LWE on General Entropic Distributions
Zvika Brakerski, Nico Döttling
Foundations

The hardness of the Learning with Errors (LWE) problem is by now a cornerstone of the cryptographic landscape. In many of its applications the so called ``LWE secret'' is not sampled uniformly, but comes from a distribution with some min-entropy. This variant, known as ``Entropic LWE'', has been studied in a number of works, starting with Goldwasser et al. (ICS 2010). However, so far it was only known how to prove the hardness of Entropic LWE for secret distributions supported inside a ball...

2019/1411 (PDF) Last updated: 2020-08-25
Isochronous Gaussian Sampling: From Inception to Implementation
James Howe, Thomas Prest, Thomas Ricosset, Mélissa Rossi
Public-key cryptography

Gaussian sampling over the integers is a crucial tool in lattice-based cryptography, but has proven over the recent years to be surprisingly challenging to perform in a generic, efficient and provable secure manner. In this work, we present a modular framework for generating discrete Gaussians with arbitrary center and standard deviation. Our framework is extremely simple, and it is precisely this simplicity that allowed us to make it easy to implement, provably secure, portable, efficient,...

2019/1301 (PDF) Last updated: 2019-11-12
Modular lattice signatures, revisited
Dipayan Das, Jeffrey Hoffstein, Jill Pipher, William Whyte, Zhenfei Zhang
Public-key cryptography

In this paper we revisit the modular lattice signature scheme and its efficient instantiation known as pqNTRUSign. First, we show that a modular lattice signature scheme can be based on a standard lattice problem. The fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits. We show that this problem is equivalent to the short integer solution (SIS) problem over the corresponding...

2019/1287 (PDF) Last updated: 2020-05-05
MatRiCT: Efficient, Scalable and Post-Quantum Blockchain Confidential Transactions Protocol
Muhammed F. Esgin, Raymond K. Zhao, Ron Steinfeld, Joseph K. Liu, Dongxi Liu
Cryptographic protocols

We introduce MatRiCT, an efficient RingCT protocol for blockchain confidential transactions, whose security is based on ``post-quantum'' (module) lattice assumptions. The proof length of the protocol is around two orders of magnitude shorter than the existing post-quantum proposal, and scales efficiently to large anonymity sets, unlike the existing proposal. Further, we provide the first full implementation of a post-quantum RingCT, demonstrating the practicality of our scheme. In...

2019/1231 (PDF) Last updated: 2019-10-21
Distinguishing LWE Instances Using Fourier Transform: A Refined Framework and its Applications
Zhao Chunhuan, Zheng Zhongxiang, Wang Xiaoyun, Xu Guangwu
Public-key cryptography

As a fundamental tool in lattice-based cryptosystems, discrete Gaussian samplers play important roles in both efficiency and security of lattice-based schemes. Approximate discrete rounded Gaussian sampler, central binomial sampler and bounded uniform sampler are three types of error samplers that are commonly used in the designs of various schemes. However, known cryptanalytics about error samplers concentrate on their standard deviations and no analysis about distinct structures of...

2019/1180 (PDF) Last updated: 2020-03-26
Key Recovery from Gram-Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices
Pierre-Alain Fouque, Paul Kirchner, Mehdi Tibouchi, Alexandre Wallet, Yang Yu
Public-key cryptography

In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold. First, we identify a...

2019/1029 (PDF) Last updated: 2019-09-11
Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures
Yilei Chen, Nicholas Genise, Pratyay Mukherjee
Public-key cryptography

We study a relaxed notion of lattice trapdoor called approximate trapdoor, which is defined to be able to invert Ajtai's one-way function approximately instead of exactly. The primary motivation of our study is to improve the efficiency of the cryptosystems built from lattice trapdoors, including the hash-and-sign signatures. Our main contribution is to construct an approximate trapdoor by modifying the gadget trapdoor proposed by Micciancio and Peikert. In particular, we show how to use...

2019/1011 (PDF) Last updated: 2020-09-25
COSAC: COmpact and Scalable Arbitrary-Centered Discrete Gaussian Sampling over Integers
Raymond K. Zhao, Ron Steinfeld, Amin Sakzad
Implementation

The arbitrary-centered discrete Gaussian sampler is a fundamental subroutine in implementing lattice trapdoor sampling algorithms. However, existing approaches typically rely on either a fast implementation of another discrete Gaussian sampler or pre-computations with regards to some specific discrete Gaussian distributions with fixed centers and standard deviations. These approaches may only support sampling from standard deviations within a limited range, or cannot efficiently sample from...

2019/1001 (PDF) Last updated: 2020-08-24
Middle-Product Learning with Rounding Problem and its Applications
Shi Bai, Katharina Boudgoust, Dipayan Das, Adeline Roux-Langlois, Weiqiang Wen, Zhenfei Zhang
Foundations

At CRYPTO 2017, Rosca et al. introduce a new variant of the Learning With Errors (LWE) problem, called the Middle-Product LWE (MP-LWE). The hardness of this new assumption is based on the hardness of the Polynomial LWE (P-LWE) problem parameterized by a set of polynomials, making it more secure against the possible weakness of a single defining polynomial. As a cryptographic application, they also provide an encryption scheme based on the MP-LWE problem. In this paper, we propose a...

2019/910 (PDF) Last updated: 2019-08-08
Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto
Tobias Schneider, Clara Paglialonga, Tobias Oder, Tim Güneysu
Implementation

With the rising popularity of lattice-based cryptography, the Learning with Errors (LWE) problem has emerged as a fundamental core of numerous encryption and key exchange schemes. Many LWE-based schemes have in common that they require sampling from a discrete Gaussian distribution which comes with a number of challenges for the practical instantiation of those schemes. One of these is the inclusion of countermeasures against a physical side-channel adversary. While several works discuss the...

2019/728 (PDF) Last updated: 2019-11-08
Verifying Solutions to LWE with Implications for Concrete Security
Palash Sarkar, Subhadip Singha
Public-key cryptography

A key step in Regev's (2009) reduction of the Discrete Gaussian Sampling (DGS) problem to that of solving the Learning With Errors (LWE) problem is a statistical test required for verifying possible solutions to the LWE problem. In this work, we work out a concrete lower bound on the success probability and its effect in determining an upper bound on the tightness gap of the reduction. The success probability is determined by the value of the rejection threshold $t$ of the statistical test....

2019/674 (PDF) Last updated: 2022-01-10
Polar Sampler: A Novel Bernoulli Sampler Using Polar Codes with Application to Integer Gaussian Sampling
Jiabo Wang, Cong Ling
Applications

Cryptographic constructions based on hard lattice problems have emerged as a front runner for the standardization of post quantum public key cryptography. As the standardization process takes place, optimizing specific parts of proposed schemes, e.g., Bernoulli sampling and integer Gaussian sampling, becomes a worthwhile endeavor. In this work, we propose a novel Bernoulli sampler based on polar codes, dubbed ``polar sampler". The polar sampler is information theoretically optimum in the...

2019/666 (PDF) Last updated: 2019-06-06
On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian Sampling
Zheng Wang, Cong Ling
Foundations

Sampling from the lattice Gaussian distribution has emerged as an important problem in coding, decoding and cryptography. In this paper, the classic Metropolis-Hastings (MH) algorithm in Markov chain Monte Carlo (MCMC) methods is adopted for lattice Gaussian sampling. Two MH-based algorithms are proposed, which overcome the limitation of Klein's algorithm. The first one, referred to as the independent Metropolis-Hastings-Klein (MHK) algorithm, establishes a Markov chain via an independent...

2019/665 (PDF) Last updated: 2019-06-06
Key Exchange and Authenticated Key Exchange with Reusable Keys Based on RLWE Assumption
Jintai Ding, Pedro Branco, Kevin Schmitt
Public-key cryptography

Key Exchange (KE) is, undoubtedly, one of the most used cryptographic primitives in practice. Its authenticated version, Authenticated Key Exchange (AKE), avoids man-in-the-middle-based attacks by providing authentication for both parties involved. It is widely used on the Internet, in protocols such as TLS or SSH. In this work, we provide new constructions for KE and AKE based on ideal lattices in the Random Oracle Model (ROM). The contributions of this work can be summarized as...

2019/660 (PDF) Last updated: 2019-06-05
Lattice Gaussian Sampling by Markov Chain Monte Carlo: Bounded Distance Decoding and Trapdoor Sampling
Zheng Wang, Cong Ling
Foundations

Sampling from the lattice Gaussian distribution plays an important role in various research fields. In this paper, the Markov chain Monte Carlo (MCMC)-based sampling technique is advanced in several fronts. Firstly, the spectral gap for the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, which is then extended to Peikert's algorithm and rejection sampling; we show that independent MHK exhibits faster convergence. Then, the performance of bounded distance decoding using MCMC...

2019/578 (PDF) Last updated: 2019-05-28
Deep Learning based Side Channel Attacks in Practice
Houssem Maghrebi
Implementation

A recent line of research has investigated a new profiling technique based on deep learning as an alternative to the well-known template attack. The advantage of this new profiling approach is twofold: $(1)$ the approximation of the information leakage by a multivariate Gaussian distribution is relaxed (leading to a more generic approach) and $(2)$ the pre-processing phases such as the traces realignment or the selection of the Points of Interest (PoI) are no longer mandatory, in some cases,...

2019/511 (PDF) Last updated: 2020-08-19
GALACTICS: Gaussian Sampling for Lattice-Based Constant-Time Implementation of Cryptographic Signatures, Revisited
Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Mélissa Rossi, Mehdi Tibouchi
Implementation

In this paper, we propose a constant-time implementation of the BLISS lattice-based signature scheme. BLISS is possibly the most efficient lattice-based signature scheme proposed so far, with a level of performance on par with widely used pre-quantum primitives like ECDSA. It is only one of the few postquantum signatures to have seen real-world deployment, as part of the strongSwan VPN software suite. The outstanding performance of the BLISS signature scheme stems in large part from its...

2019/389 (PDF) Last updated: 2019-05-03
Achieving secure and efficient lattice-based public-key encryption: the impact of the secret-key distribution
Sauvik Bhattacharya, Oscar Garcia-Morchon, Rachel Player, Ludo Tolhuizen
Public-key cryptography

Lattice-based public-key encryption has a large number of design choices that can be combined in diverse ways to obtain different tradeoffs. One of these choices is the distribution from which secret keys are sampled. Numerous secret-key distributions exist in the state of the art, including (discrete) Gaussian, binomial, ternary, and fixed-weight ternary. Although the secret-key distribution impacts both the concrete security and the performance of the schemes, it has not been compared in a...

2019/320 (PDF) Last updated: 2020-05-30
Integral Matrix Gram Root and Lattice Gaussian Sampling without Floats
Léo Ducas, Steven Galbraith, Thomas Prest, Yang Yu
Public-key cryptography

Many advanced lattice based cryptosystems require to sample lattice points from Gaussian distributions. One challenge for this task is that all current algorithms resort to floating-point arithmetic (FPA) at some point, which has numerous drawbacks in practice: it requires numerical stability analysis, extra storage for high-precision, lazy/backtracking techniques for efficiency, and may suffer from weak determinism which can completely break certain schemes. In this paper, we give...

2019/267 (PDF) Last updated: 2019-05-02
Pushing the speed limit of constant-time discrete Gaussian sampling. A case study on Falcon.
Angshuman Karmakar, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid Verbauwhede
Public-key cryptography

Sampling from discrete Gaussian distribution has applications in lattice-based post-quantum cryptography. Several efficient solutions have been proposed in recent years. However, making a Gaussian sampler secure against timing attacks turned out to be a challenging research problem. In this work, we observed an important property of the input random bit strings that generate samples in Knuth-Yao sampling. We delineate a generic step-by-step method to instantiate a discrete Gaussian sampler...

2019/206 (PDF) Last updated: 2019-02-27
Fault Attack Countermeasures for Error Samplers in Lattice-Based Cryptography
James Howe, Ayesha Khalid, Marco Martinoli, Francesco Regazzoni, Elisabeth Oswald
Implementation

Lattice-based cryptography is one of the leading candidates for NIST's post-quantum standardisation effort, providing efficient key encapsulation and signature schemes. Most of these schemes base their hardness on variants of LWE, and thus rely heavily on error samplers to provide necessary uncertainty by obfuscating computations on secret information. Because of this it is a clear and obvious target for side-channel analysis, with numerous types of attacks targeting this component to gain...

2019/068 (PDF) Last updated: 2019-05-10
Sampling the Integers with Low Relative Error
Michael Walter
Implementation

Randomness is an essential part of any secure cryptosystem, but many constructions rely on distributions that are not uniform. This is particularly true for lattice based cryptosystems, which more often than not make use of discrete Gaussian distributions over the integers. For practical purposes it is crucial to evaluate the impact that approximation errors have on the security of a scheme to provide the best possible trade-off between security and performance. Recent years have seen...

2019/050 (PDF) Last updated: 2019-01-25
Improved Security Evaluation Techniques for Imperfect Randomness from Arbitrary Distributions
Takahiro Matsuda, Kenta Takahashi, Takao Murakami, Goichiro Hanaoka

Dodis and Yu (TCC 2013) studied how the security of cryptographic primitives that are secure in the "ideal" model in which the distribution of a randomness is the uniform distribution, is degraded when the ideal distribution of a randomness is switched to a "real-world" (possibly biased) distribution that has some lowerbound on its min-entropy or collision-entropy. However, in many constructions, their security is guaranteed only when a randomness is sampled from some non-uniform...

2018/1238 (PDF) Last updated: 2018-12-31
Memory-Constrained Implementation of Lattice-based Encryption Scheme on the Standard Java Card Platform
Ye Yuan, Kazuhide Fukushima, Junting Xiao, Shinsaku Kiyomoto, Tsuyoshi Takagi
Implementation

Memory-constrained devices, including widely used smart cards, require resisting attacks by the quantum computers. Lattice-based encryption scheme possesses high efficiency and reliability which could run on small devices with limited storage capacity and computation resources such as IoT sensor nodes or smart cards. We present the first implementation of a lattice-based encryption scheme on the standard Java Card platform by combining number theoretic transform and improved Montgomery...

2018/1234 (PDF) Last updated: 2020-09-25
FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers
Raymond K. Zhao, Ron Steinfeld, Amin Sakzad
Implementation

The discrete Gaussian sampler is one of the fundamental tools in implementing lattice-based cryptosystems. However, a naive discrete Gaussian sampling implementation suffers from side-channel vulnerabilities, and the existing countermeasures usually introduce significant overhead in either the running speed or the memory consumption. In this paper, we propose a fast, compact, and constant-time implementation of the binary sampling algorithm, originally introduced in the BLISS signature...

2018/1205 (PDF) Last updated: 2019-03-20
Cryptanalysis of a code-based one-time signature
Jean-Christophe Deneuville, Philippe Gaborit
Public-key cryptography

In 2012, Lyubashevsky introduced a new framework for building lattice-based signature schemes without resorting to any trapdoor (such as GPV [6] or NTRU [7]). The idea is to sample a set of short lattice elements and construct the public key as a Short Integer Solution (SIS for short) instance. Signatures are obtained using a small subset sum of the secret key, hidden by a (large) Gaussian mask. (Information leakage is dealt with using rejection sampling.) Recently, Persichetti proposed an...

2018/1141 (PDF) Last updated: 2018-11-29
Fast Authentication from Aggregate Signatures with Improved Security
Muslum Ozgur Ozmen, Rouzbeh Behnia, Attila A. Yavuz
Public-key cryptography

An attempt to derive signer-efficient digital signatures from aggregate signatures was made in a signature scheme referred to as Structure-free Compact Rapid Authentication (SCRA) (IEEE TIFS 2017). In this paper, we first mount a practical universal forgery attack against the NTRU instantiation of SCRA by observing only 8161 signatures. Second, we propose a new signature scheme (FAAS), which transforms any single-signer aggregate signature scheme into a signer-efficient scheme. We show two...

2018/946 (PDF) Last updated: 2019-03-12
Building an Efficient Lattice Gadget Toolkit: Subgaussian Sampling and More
Nicholas Genise, Daniele Micciancio, Yuriy Polyakov

Many advanced lattice cryptography applications require efficient algorithms for inverting the so-called "gadget" matrices, which are used to formally describe a digit decomposition problem that produces an output with specific (statistical) properties. The common gadget inversion problems are the classical (often binary) digit decomposition, subgaussian decomposition, Learning with Errors (LWE) decoding, and discrete Gaussian sampling. In this work, we build and implement an efficient...

2018/873 (PDF) Last updated: 2018-12-12
TACHYON: Fast Signatures from Compact Knapsack
Rouzbeh Behnia, Muslum Ozgur Ozmen, Attila A. Yavuz, Mike Rosulek
Public-key cryptography

We introduce a simple, yet efficient digital signature scheme which offers post-quantum security promise. Our scheme, named $\texttt{TACHYON}$, is based on a novel approach for extending one-time hash-based signatures to (polynomially bounded) many-time signatures, using the additively homomorphic properties of generalized compact knapsack functions. Our design permits $\texttt{TACHYON}$ to achieve several key properties. First, its signing and verification algorithms are the fastest...

2018/381 (PDF) Last updated: 2020-08-19
Masking the GLP Lattice-Based Signature Scheme at Any Order
Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, Mélissa Rossi, Mehdi Tibouchi

Recently, numerous physical attacks have been demonstrated against lattice-based schemes, often exploiting their unique properties such as the reliance on Gaussian distributions, rejection sampling and FFT-based polynomial multiplication. As the call for concrete implementations and deployment of postquantum cryptography becomes more pressing, protecting against those attacks is an important problem. However, few countermeasures have been proposed so far. In particular, masking has been...

2018/356 (PDF) Last updated: 2021-03-30
In Praise of Twisted Embeddings
Jheyne N. Ortiz, Robson R. de Araujo, Diego F. Aranha, Sueli I. R. Costa, Ricardo Dahab
Foundations

Our main result in this work is the extension of 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. We prove that our generalization for 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 addition of a new parameter, the...

2018/309 Last updated: 2019-02-01
Error Estimation of Practical Convolution Discrete Gaussian Sampling with Rejection Sampling
Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu, Chunhuan Zhao

Discrete Gaussian Sampling is a fundamental tool in lattice cryptography which has been used in digital signatures, identify-based encryption, attribute-based encryption, zero-knowledge proof and fully homomorphic cryptosystem. As a subroutine of lattice-based scheme, a high precision sampling usually leads to a high security level and also brings large time and space complexity. In order to optimize security and efficiency, how to achieve a higher security level with a lower precision...

2018/265 (PDF) Last updated: 2018-03-13
Compact, Scalable, and Efficient Discrete Gaussian Samplers for Lattice-Based Cryptography
Ayesha Khalid, James Howe, Ciara Rafferty, Francesco Regazzoni, Maire O’Neill
Public-key cryptography

Lattice-based cryptography, one of the leading candidates for post-quantum security, relies heavily on discrete Gaussian samplers to provide necessary uncertainty, obfuscating computations on secret information. For reconfigurable hardware, the cumulative distribution table (CDT) scheme has previously been shown to achieve the highest throughput and the smallest resource utilisation, easily outperforming other existing samplers. However, the CDT sampler does not scale well. In fact, for...

2017/1254 (PDF) Last updated: 2019-03-06
Practical Applications of Improved Gaussian Sampling for Trapdoor Lattices
Kamil Doruk Gür, Yuriy Polyakov, Kurt Rohloff, Gerard W. Ryan, Hadi Sajjadpour, Erkay Savaş
Implementation

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...

2017/1025 (PDF) Last updated: 2017-10-25
Rounded Gaussians -- Fast and Secure Constant-Time Sampling for Lattice-Based Crypto
Andreas Hülsing, Tanja Lange, Kit Smeets
Public-key cryptography

This paper suggests to use rounded Gaussians in place of dis- crete Gaussians in rejection-sampling-based lattice signature schemes like BLISS. We show that this distribution can efficiently be sampled from while additionally making it easy to sample in constant time, systematically avoiding recent timing-based side-channel attacks on lattice-based signatures. We show the effectiveness of the new sampler by applying it to BLISS, prove analogues of the security proofs for BLISS, and present...

2017/995 (PDF) Last updated: 2017-10-30
A signature scheme from Learning with Truncation
Jeffrey Hoffstein, Jill Pipher, William Whyte, Zhenfei Zhang

In this paper we revisit the modular lattice signature scheme and its efficient instantiation known as pqNTRUSign. First, we show that a modular lattice signature scheme can be based on a standard lattice problem. As the fundamental problem that needs to be solved by the signer or a potential forger is recovering a lattice vector with a restricted norm, given the least significant bits, we refer to this general class of problems as the “learning with truncation” problem. We show that by...

2017/988 (PDF) Last updated: 2017-10-11
On Rejection Sampling Algorithms for Centered Discrete Gaussian Distribution over Integers
Yusong Du, Baodian Wei

Lattice-based cryptography has been accepted as a promising candidate for public key cryptography in the age of quantum computing. Discrete Gaussian sampling is one of fundamental operations in many lattice-based cryptosystems. In this paper, we discuss a sub-problem of discrete Gaussian sampling, which is to sample from a centered discrete Gaussian distribution over the integers with positive standard deviation and zero center. We propose three alternative rejection sampling algorithms for...

2017/583 Last updated: 2017-08-28
Side-Channel Attacks on BLISS Lattice-Based Signatures -- Exploiting Branch Tracing Against strongSwan and Electromagnetic Emanations in Microcontrollers
Thomas Espitau, Pierre-Alain Fouque, Benoit Gerard, Mehdi Tibouchi
Implementation

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to micro-controllers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more...

2017/563 (PDF) Last updated: 2017-06-14
Weak is Better: Tightly Secure Short Signatures from Weak PRFs
Jacob Alperin-Sheriff, Daniel Apon

The Boyen-Li signature scheme [Asiacrypt'16] is a major theoretical breakthrough. Via a clever homomorphic evaluation of a pseudorandom function over their verification key, they achieve a reduction loss in security linear in the underlying security parameter and entirely independent of the number of message queries made, while still maintaining short signatures (consisting of a single short lattice vector). All previous schemes with such an independent reduction loss in security required a...

2017/505 (PDF) Last updated: 2018-07-13
Side-Channel Attacks on BLISS Lattice-Based Signatures -- Exploiting Branch Tracing Against strongSwan and Electromagnetic Emanations in Microcontrollers
Thomas Espitau, Pierre-Alain Fouque, Benoit Gerard, Mehdi Tibouchi
Implementation

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to micro-controllers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more...

2017/480 (PDF) Last updated: 2017-09-07
Sharper Bounds in Lattice-Based Cryptography using the Rényi Divergence
Thomas Prest
Public-key cryptography

The Rényi divergence is a measure of divergence between distributions. It has recently found several applications in lattice-based cryptography. The contribution of this paper is twofold. First, we give theoretic results which renders it more efficient and easier to use. This is done by providing two lemmas, which give tight bounds in very common situations { for distributions that are tailcut or have a bounded relative error. We then connect the Rényi divergence to the max-log distance....

2017/438 (PDF) Last updated: 2017-05-22
GLITCH: A Discrete Gaussian Testing Suite For Lattice-Based Cryptography
James Howe, Máire O'Neill
Public-key cryptography

Lattice-based cryptography is one of the most promising areas within post-quantum cryptography, and offers versatile, efficient, and high performance security services. The aim of this paper is to verify the correctness of the discrete Gaussian sampling component, one of the most important modules within lattice-based cryptography. In this paper, the GLITCH software test suite is proposed, which performs statistical tests on discrete Gaussian sampler outputs. An incorrectly operating...

2017/312 (PDF) Last updated: 2019-05-23
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh K. Kothari

Consider a pseudorandom generator $G$ with $m$ outputs, whose seed contains $n$ blocks of $b$ bits each. Further, assume that this PRG has block-locality $\ell$, i.e. each output bit depends on at most $\ell$ out of the $n$ blocks. The question of the maximum stretch $m$ that such PRGs can have, as a function of $n,b,\ell$ recently emerged in the context of constructing provably secure program obfuscation. It also relates to the question of refuting constraint satisfaction problems on...

2017/308 (PDF) Last updated: 2022-04-25
Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus
Nicholas Genise, Daniele Micciancio
Implementation

We present improved algorithms for gaussian preimage sampling using the lattice trapdoors of (Micciancio and Peikert, CRYPTO 2012). The MP12 work only offered a highly optimized algorithm for the on-line stage of the computation in the special case when the lattice modulus $q$ is a power of two. For arbitrary modulus $q$, the MP12 preimage sampling procedure resorted to general lattice algorithms with complexity cubic in the bitsize of the modulus (or quadratic, but with substantial...

2017/298 (PDF) Last updated: 2017-04-25
An Investigation of Sources of Randomness Within Discrete Gaussian Sampling
Séamus Brannigan, Neil Smyth, Tobias Oder, Felipe Valencia, Elizabeth O’Sullivan, Tim Güneysu, Francesco Regazzoni
Implementation

This paper presents a performance and statistical analysis of random number generators and discrete Gaussian samplers implemented in software. Most Lattice-based cryptographic schemes utilise discrete Gaussian sampling and will require a quality random source. We examine a range of candidates for this purpose, including NIST DRBGs, stream ciphers and well-known PRNGs. The performance of these random sources is analysed within 64-bit implementations of Bernoulli, CDT and Ziggurat sampling. In...

2017/285 (PDF) Last updated: 2018-10-03
Implementation and Evaluation of Improved Gaussian Sampling for Lattice Trapdoors
Kamil Doruk Gür, Yuriy Polyakov, Kurt Rohloff, Gerard W. Ryan, Erkay Savaş
Implementation

We report on our implementation of a new Gaussian sampling algorithm for lattice trapdoors. Lattice trapdoors are used in a wide array of lattice-based cryptographic schemes including digital signatures, attributed-based encryption, program obfuscation and others. Our implementation provides Gaussian sampling for trapdoor lattices with prime moduli, and supports both single- and multi-threaded execution. We experimentally evaluate our implementation through its use in the GPV hash-and-sign...

2017/259 (PDF) Last updated: 2018-02-06
Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time
Daniele Micciancio, Michael Walter
Implementation

Sampling integers with Gaussian distribution is a fundamental problem that arises in almost every application of lattice cryptography, and it can be both time consuming and challenging to implement. Most previous work has focused on the optimization and implementation of integer Gaussian sampling in the context of specific applications, with fixed sets of parameters. We present new algorithms for discrete Gaussian sampling that are both generic (application independent), efficient, and more...

2017/163 (PDF) Last updated: 2017-02-23
Homomorphic Encryption without Gaussian Noise
Anamaria Costache, Nigel P. Smart

We propose a Somewhat Homomorphic Encryption (SHE) scheme based on the Learning With Rounding (LWR) problem. The LWR problem is somewhat similar to the more classical Learning With Errors (LWE) and was proposed as a deterministic variant of it and setting up an LWR instance does not require the generation of gaussian noise. Thus our SHE scheme can be instantiated without the need for expensive Gaussian noise sampling. Our initial scheme provides lower ciphertext sizes for small plaintext...

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.