What a lovely hat

One of the primary approaches used to construct lattice-based signature schemes is through the “Fiat-Shamir with aborts” methodology. Such a scheme may abort and restart during signing which corresponds to rejection sampling produced signatures to ensure that they follow a distribution that is independent of the secret key. This rejection sampling is only feasible when the output distribution is sufficiently wide, limiting how compact this type of signature schemes can be. In this work,...

Evaluating the security of LWE-based KEMs involves two crucial metrics: the hardness of the underlying LWE problem and resistance to decryption failure attacks, both significantly influenced by the secret key and error distributions. To mitigate the complexity and timing vulnerabilities of Gaussian sampling, modern LWE-based schemes often adopt either the uniform or centered binomial distribution (CBD). This work focuses on Kyber to evaluate its security under both distributions. Compared...

Proofs of partial knowledge, first considered by Cramer, Damgård and Schoenmakers (CRYPTO'94) and De Santis et al. (FOCS'94), allow for proving the validity of $k$ out of $n$ different statements without revealing which ones those are. In this work, we present a new approach for transforming certain proofs system into new ones that allows for proving partial knowledge. The communication complexity of the resulting proof system only depends logarithmically on the total number of statements...

We present a key-recovery attack on a variant of the Seasign signature scheme presented by [Kim24], which attempts to avoid rejection sampling by presampling vectors $\mathbf{f}$ such that the $\mathbf{f}-\mathbf{e}$ is contained in an acceptable bound, where $\mathbf{e}$ is the secret key. We show that this choice leads to a bias of these vectors such that, in a small number of signatures, the secret key can either be completely recovered or its keyspace substantially reduced. In...

In this work, we introduce enhanced high-order masking techniques tailored for Dilithium, the post-quantum signature scheme recently standardized by NIST. We improve the masked generation of the masking vector $\vec{y}$, based on a fast Boolean-to-arithmetic conversion modulo $q$. We also describe an optimized gadget for the high-order masked rejection sampling, with a complexity independent from the size of the modulus $q$. We prove the security of our gadgets in the classical ISW...

The notion of Anamorphic Encryption (Persiano et al. Eurocrypt 2022) aims at establishing private communication against an adversary who can access secret decryption keys and influence the chosen messages. Persiano et al. gave a simple, black-box, rejection sampling-based technique to send anamorphic bits using any IND-CPA secure scheme as underlying PKE. In this paper however we provide evidence that their solution is not as general as claimed: indeed there exists a (contrived yet...

Anticipating the advent of large quantum computers, NIST started a worldwide competition in 2016 aiming to define the next cryptographic standards. HQC is one of these post-quantum schemes still in contention, with three others already standardized. In 2022, Guo et al. introduced a timing attack that exploited an inconsistency in HQC rejection sampling function to recover its secret key in 866,000 calls to an oracle. The authors of HQC updated its specification by applying an algorithm to...

A threshold signature scheme distributes the ability to generate signatures through distributed key generation and signing protocols. A threshold signature scheme should be functionally interchangeable, meaning that a signature produced by a threshold scheme should be verifiable by the same algorithm used for non-threshold signatures. To resist future attacks from quantum adversaries, lattice-based threshold signatures are desirable. However, the performance of existing lattice-based...

We analyse a two password-authenticated key exchange protocols, a variant of CPace and a protocol related to the well-known SRP protocol. Our security results are tight. The first result gives us some information about trade-offs for design choices in CPace. The second result provides information about the security of SRP. Our analysis is done in a new game-based security definition for password-authenticated key exchange. Our definition accomodates arbitrary password sampling...

For security issue, data in cloud is encrypted. Searching encrypted data (without decryption) is a practical and important problem. Public key authenticated encryption with keyword search (PAEKS) enables the retrieval of encrypted data, while resisting the insider keyword guessing attacks (IKGAs). Most PAEKS schemes only work with single-receiver model, exhibiting very limited applicability. To address this concern, there have been researches on broadcast authenticated encryption with...

Fault attacks that exploit the propagation of effective/ineffective faults present a richer attack surface than Differential Fault Attacks, in the sense that the adversary depends on a single bit of information to eventually leak secret cryptographic material. In the recent past, a number of propagation-based fault attacks on Lattice-based Key Encapsulation Mechanisms have been proposed; many of which have no known countermeasures. In this work, we propose an orthogonal countermeasure...

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

Driven by the NIST's post-quantum standardization efforts and the selection of Kyber as a lattice-based Key-Encapsulation Mechanism (KEM), several Password Authenticated Key Exchange (PAKE) protocols have been recently proposed that leverage a KEM to create an efficient, easy-to-implement and secure PAKE. In two recent works, Beguinet et al. (ACNS 2023) and Pan and Zeng (ASIACRYPT 2023) proposed generic compilers that transform KEM into PAKE, relying on an Ideal Cipher (IC) defined over a...

Zero-knowledge circuits are frequently required to prove gadgets that are not optimised for the constraint system in question. A particularly daunting task is to embed foreign arithmetic such as Boolean operations, field arithmetic, or public-key cryptography. We construct techniques for offloading foreign arithmetic from a zero-knowledge circuit including: (i) equality of discrete logarithms across different groups; (ii) scalar multiplication without requiring elliptic curve...

We present a highly detectable, trustless watermarking scheme for LLMs: the detection algorithm contains no secret information, and it is executable by anyone. We embed a publicly-verifiable cryptographic signature into LLM output using rejection sampling. We prove that our scheme is cryptographically correct, sound, and distortion-free. We make novel uses of error-correction techniques to overcome periods of low entropy, a barrier for all prior watermarking schemes. We implement our scheme...

We propose a new lattice-based sublinear argument for R1CS that not only achieves efficiency in concrete proof size but also demonstrates practical performance in both proof generation and verification. To reduce the proof size, we employ a new encoding method for large prime fields, resulting in a compact proof for R1CS over such fields. We also devise a new proof technique that randomizes the input message. This results in fast proof generation performance, eliminating rejection...

The threat posed by quantum computing has precipitated an urgent need for post-quantum cryptography. Recently, the post-quantum digital signature draft FIPS 204 has been published, delineating the details of the ML-DSA, which is derived from the CRYSTALS-Dilithium. Despite these advancements, server environments, especially those equipped with GPU devices necessitating high-throughput signing, remain entrenched in classical schemes. A conspicuous void exists in the realm of GPU...

We give a semantic characterization of leakage-freeness through timing side-channels for Jasmin programs. Our characterization also covers probabilistic Jasmin programs that are not constant-time. In addition, we provide a characterization in terms of probabilistic relational Hoare logic and prove equivalence of both definitions. We also prove that our new characterizations are compositional. Finally, we relate new definitions to the existing ones from prior work which only apply to...

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

The use of random seeds to a deterministic random bit generator to generate uniform random sampling has been applied multiple times in post-quantum algorithms. The finalists Dilithium and Kyber use SHAKE and AES to generate the random sequence at multiple stages of the algorithm. Here we characterize one of the sampleing techniques available in Dilithium for a random sequence of length 256 with the help of the neutrosophic Boolean function. The idea of the neutrosophic Boolean function came...

Correlated secret randomness is a useful resource for secure computation protocols, often enabling dramatic speedups compared to protocols in the plain model. This has motivated a line of work on identifying and securely generating useful correlations. Different kinds of correlations can vary greatly in terms of usefulness and ease of generation. While there has been major progress on efficiently generating oblivious transfer (OT) correlations, other useful kinds of correlations are...

This paper studies the hardness of decision Module Learning with Errors (\MLWE) under linear leakage, which has been used as a foundation to derive more efficient lattice-based zero-knowledge proofs in a recent paradigm of Lyubashevsky, Nguyen, and Seiler (PKC 21). Unlike in the plain \LWE~setting, it was unknown whether this problem remains provably hard in the module/ring setting. This work shows a reduction from the search \MLWE~to decision \MLWE~with linear leakage. Thus, the main...

We implement the Schnorr protocol in assembler via the Jasmin toolchain, and prove the security (proof-of-knowledge and zero-knowledge properties) and the absence of leakage through timing side-channels of that implementation in EasyCrypt. In order to do so, we provide a semantic characterization of leakage-freeness for probabilistic Jasmin programs (that are not constant-time). We design a library for multiple-precision integer arithmetic in Jasmin -- the "libjbn'' library. Among others,...

The key generation of the lattice-based key-encapsulation mechanism CRYSTALS-Kyber (or short, just Kyber) involves a rejection-sampling routine to produce coefficients modulo $q=3329$ that look uniformly random. The input to this rejection sampling is output of the SHAKE-128 extendable output function (XOF). If this XOF is modelled as a random oracle with infinite output length, it is easy to see that Kyber terminates with probability 1; also, in this model, for any upper bound on the...

In the last decade, zero-knowledge proof of knowledge protocols have been extensively studied to achieve active security of various cryptographic protocols. However, the existing solutions simply seek zero-knowledge for both message and randomness, which is an overkill in many applications since protocols may remain secure even if some information about randomness is leaked to the adversary. We develop this idea to improve the state-of-the-art proof of knowledge protocols for RLWE-based...

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

Preimage Sampling is a fundamental process in lattice-based cryptography whose performance directly affects the one of the cryptographic mechanisms that rely 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 this work we...

In this work we present a lightweight lattice-based identification protocol based on the CPA-secured public key encryption scheme Kyber. It is designed as a replacement for existing classical ECC- or RSA-based identification protocols in IoT, smart card applications, or for device authentication. The proposed protocol is simple, efficient, and implementations are supposed to be easy to harden against side-channel attacks. Compared to standard constructions for identification protocols based...

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the...

Lyubashevsky’s signatures are based on the Fiat-Shamir with aborts paradigm, whose central ingredient is the use of rejection sampling to transform secret-dependent signature samples into samples from (or close to) a secret-independent target distribution. Several choices for the underlying distributions and for the rejection sampling strategy can be considered. In this work, we study Lyubashevsky’s signatures through the lens of rejection sampling, and aim to minimize signature size...

We propose the signature scheme Hawk, a concrete instantiation of proposals to use the Lattice Isomorphism Problem (LIP) as a foundation for cryptography that focuses on simplicity. This simplicity stems from LIP, which allows the use of lattices such as $\mathbb{Z}^n$ , leading to signature algorithms with no floats, no rejection sampling, and compact precomputed distributions. Such design features are desirable for constrained devices, and when computing signatures inside FHE or MPC. The...

Interactive zero-knowledge systems are a very important cryptographic primitive, used in many applications, especially when deniability (also known as non-transferability) is desired. In the lattice-based setting, the currently most efficient interactive zero-knowledge systems employ the technique of rejection sampling, which implies that the interaction does not always finish correctly in the first execution; the whole interaction must be re-run until abort does not happen. While...

This paper proposes a new single-trace side-channel attack on lattice-based post-quantum protocols. We target the ω-small polynomial sampling of NTRU, NTRU Prime, and CRYSTALS-DILITHIUM algorithm implementations (which are NIST Round-3 finalists and alternative candidates), and we demonstrate the vulnerabilities of their sub-routines to a power-based side-channel attack. Specifically, we reveal that the sorting implementation in NTRU/NTRU Prime and the shuffling in CRYSTALS-DILITHIUM's...

Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a new construction which avoids rejection sampling by using temporary public keys and structured secrets in a Bliss type scheme. Structured secrets also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signing algorithm is comparative with this optimized encryption efficiency. Our signature scheme allows the same key pair...

Well before large-scale quantum computers will be available, traditional cryptosystems must be transitioned to post-quantum (PQ) secure schemes. The NIST PQC competition aims to standardize suitable cryptographic schemes. Candidates are evaluated not only on their formal security strengths, but are also judged based on the security with regard to resistance against side-channel attacks. Although round 3 candidates have already been intensively vetted with regard to such attacks, one...

Digital signatures following the methodology of “Fiat-Shamir with Aborts”, proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice signature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been proposed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardization. This method...

The Schnorr-Lyubashevsky approach has been shown able to produce secure and efficient signature schemes without trapdoors in the lattice-based setting, exploiting small vectors in the Euclidean metric and rejection sampling in the signature generation. Translating such an approach to the code-based setting has revealed to be challenging, especially for codes in the Hamming metric. In this paper, we propose a novel adaptation of the Schnorr-Lyubashevsky framework to the code-based setting, by...

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

We propose an attack on the recent attempt by Li, Xing and Yeo to produce a code-based signature scheme using the Schnorr-Lyubashevsky approach in the Hamming metric, and verify its effectiveness through numerical simulations. Differently from other (unsuccessful) proposals, this new scheme exploits rejection sampling along with dense noise vectors to hide the secret key structure in produced signatures. We show that these measures, besides yielding very slow signing times and rather long...

Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a construction of comparable efficiency with lattice encryption that avoids sampling using structured secrets together with temporary keys. Structured secrets (and randoms) also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signature scheme allows the same parameters of any encryption schemes (a variation of the basic form...

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

We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring. Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the...

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

A canonical identification (CID) scheme is a 3-move protocol consisting of a commitment, challenge, and response. It constitutes the core design of many cryptographic constructions such as zero-knowledge proof systems and various types of signature schemes. Unlike number-theoretic constructions, CID in the lattice setting usually forces provers to abort and repeat the whole authentication process once the distribution of the computed response does not follow a target distribution independent...

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

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

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

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

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

We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree $k\ge 2$, where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree $k\ge 2$ have been crucial ingredients for...

Dilithium is a round 2 candidate for digital signature schemes in NIST initiative for post-quantum cryptographic schemes. Since Dilithium is built upon the “Fiat Shamir with Aborts” framework, its signing procedure performs rejection sampling of its signatures to ensure they do not leak information about the secret key. Thus, the signing procedure is iterative in nature with a number of rejected iterations, which serve as unnecessary overheads hampering its overall performance. As a first...

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

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

We speed up the isogeny-based ``SeaSign'' signature scheme recently proposed by De Feo and Galbraith. The core idea in SeaSign is to apply the ``Fiat–Shamir with aborts'' transform to the parallel repeated execution of an identification scheme based on CSIDH. We optimize this general transform by allowing the prover to not answer a limited number of said parallel executions, thereby lowering the overall probability of rejection. The performance improvement ranges between factors of...

We present here a new family of trapdoor one-way functions that are Preimage Sampleable on Average (PSA) based on codes, the Wave-PSA family. The trapdoor function is one-way under two computational assumptions: the hardness of generic decoding for high weights and the indistinguishability of generalized $(U,U+V)$-codes. Our proof follows the GPV strategy [GPV08]. By including rejection sampling, we ensure the proper distribution for the trapdoor inverse output. The domain sampling property...

This paper is devoted to analyzing the variant of Regev's learning with errors (LWE) problem in which modular reduction is omitted: namely, the problem (ILWE) of recovering a vector $\vec s\in\mathbb{Z}^n$ given polynomially many samples of the form $(\vec a,\langle\vec a,\vec s\rangle + e)\in\mathbb{Z}^{n+1}$ where $\vec a$ and $e$ follow fixed distributions. Unsurprisingly, this problem is much easier than LWE: under mild conditions on the distributions, we show that the problem can be...

After the concept of a Fuzzy Extractor (FE) was rst introduced by Dodis et al. , it has been regarded as one of the candidate solutions for key management utilizing biometric data. With a noisy input such as biometrics, FE generates a public helper value and a random secret key which is reproducible given another input similar to the original input. However, "helper values" may cause some leakage of information when generated repeatedly by correlated inputs, thus reusability should be...

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

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

In this paper, we introduce Saber, a package of cryptographic primitives whose security relies on the hardness of the Module Learning With Rounding problem (Mod-LWR). We first describe a secure Diffie-Hellman type key exchange protocol, which is then transformed into an IND-CPA encryption scheme and finally into an IND-CCA secure key encapsulation mechanism using a post-quantum version of the Fujisaki-Okamoto transform. The design goals of this package were simplicity, efficiency and...

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

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

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

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

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

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

This paper presents an architecture for a discrete, high-entropy hardware random number generator. Because it is constructed out of simple hardware components, its operation is transparent and auditable. Using avalanche noise, a nondeterministic physical phenomenon, the circuit is inherently probabilistic and resists adversarial control. Furthermore, because it compares the outputs from two matched noise sources, it rejects environmental disturbances like power supply ripple. The resulting...

We propose a new zero-knowledge protocol applicable to additively homomorphic functions that map integer vectors to an Abelian group. The protocol demonstrates knowledge of a short preimage and achieves amortised efficiency comparable to the approach of Cramer and Damgård from Crypto 2010, but gives a much tighter bound on what we can extract from a dishonest prover. Towards achieving this result, we develop an analysis for bins-and-balls games that might be of independent interest. We...

In this work we show how to use Graphics Processing Units (GPUs) with Compute Unified Device Architecture (CUDA) to accelerate a lattice based signature scheme, namely, the NTRU modular lattice signature (NTRU-MLS) scheme. Lattice based schemes require operations on large vectors that are perfect candidates for GPU implementations. In addition, similar to most lattice based signature schemes, NTRU-MLS provides transcript security with a rejection sampling technique. With a GPU...

Post-quantum cryptography has attracted increased attention in the last couple of years, due to the threat of quantum computers breaking current cryptosystems. In particular, the key size and performance of post-quantum algorithms became a significant target for optimization. In this spirit, Alkim \etal have recently proposed a significant optimization for a key exchange scheme that is based on the R-LWE problem. In this paper, we build on the implementation of Alkim \etal, and focus on...

We present the first side-channel attack on a lattice-based signature scheme, using the FLUSH+RELOAD cache-attack. The attack is targeted at the discrete Gaussian sampler, an important step in the Bimodal Lattice Signature Schemes (BLISS). After observing only 450 signatures with a perfect side-channel, an attacker is able to extract the secret BLISS-key in less than 2 minutes, with a success probability of 0.96. Similar results are achieved in a proof-of-concept implementation using the...

We design an efficient commitment scheme, and companion zero-knowledge proofs of knowledge, based on the learning with errors over rings (RLWE) problem. In particular, for rings in which almost all elements have inverses, we construct a perfectly binding commitment scheme whose hiding property relies on the RLWE assumption. Our scheme maps elements from the ring (or equivalently, n elements from F_q) to a small constant number of ring elements. We then construct Sigma-protocols for...

We introduce a class of lattice-based digital signature schemes based on modular properties of the coordinates of lattice vectors. We also suggest a method of making such schemes transcript secure via a rejection sampling technique of Lyubashevsky (2009). A particular instantiation of this approach is given, using NTRU lattices. Although the scheme is not supported by a formal security reduction, we present arguments for its security and derive concrete parameters (first version) based on...

Abstract. We present PASSSign, a variant of the prior PASS and PASS-2 proposals, as a candidate for a practical post-quantum signature scheme. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. For our particular instantiation, this corresponds to the recovery of a signal with small infinity norm from a limited set of its Fourier coefficients. The key improvement over previous versions of...

Our main result is a construction of a lattice-based digital signature scheme that represents an improvement, both in theory and in practice, over today's most efficient lattice schemes. The novel scheme is obtained as a result of a modification of the rejection sampling algorithm that is at the heart of Lyubashevsky's signature scheme (Eurocrypt, 2012) and several other lattice primitives. Our new rejection sampling algorithm which samples from a bimodal Gaussian distribution, combined...

We provide an alternative method for constructing lattice-based digital signatures which does not use the ``hash-and-sign'' methodology of Gentry, Peikert, and Vaikuntanathan (STOC 2008). Our resulting signature scheme is secure, in the random oracle model, based on the worst-case hardness of the $\tilde{O}(n^{1.5})-SIVP$ problem in general lattices. The secret key, public key, and the signature size of our scheme are smaller than in all previous instantiations of the hash-and-sign...

We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for...

We address the problem of testing the hypothesis H_0 that the letters from some alphabet A= {a_1,a_2,..., a_k }, are distributed uniformly against the alternative hypothesis H_1 that the true distribution is not uniform, in case k is large. (It is typical for random number testing and some cryptographic problems where k= 2^{10} - 2^{30} and more). In such a case it is difficult to use the chi-square test because the sample size must be greater than k. We suggest the adaptive chi-square...