What a lovely hat

Let $N=pq$ be the product of two balanced prime numbers $p$ and $q$. In 2015, Roman'kov introduced an interesting RSA-like cryptosystem that, unlike the classical RSA key equation $ed - k (p-1)(q-1) = 1$, uses the key equation $ed - k r = 1$, where $r | p-1$ and is a large prime number. In this paper, we study if small private key attacks based on lattices can be applied to Roman'kov's cryptosystem. More precisely, we argue that such attacks do not appear to be applicable to this scheme.

NTRU-like constructions are among the most studied lattice-based schemes. The freedom of design of NTRU resulted in many variants in literature motivated by faster computations or more resistance against lattice attacks by changing the underlying algebra. To the best of our knowledge, BQTRU (DCC 2017), a noncommutative NTRU-like cryptosystem, is the fastest claimed variant of NTRU built over the quaternion algebra of the bivariate ring of polynomials. The key generation and the encryption of...

Lattice problems have many applications in various domains of computer science. There is currently a gap in the understanding of these problems with respect to their worst-case complexity and their average-case behaviour. For instance, the Shortest Vector problem (SVP) on an n-dimensional lattice has worst-case complexity $2^{n+o(n)}$ \cite{ADRS15}. However, in practice, people rely on heuristic (unproven) sieving algorithms of time complexity $2^{0.292n+o(n)}$ \cite{BeckerDGL16} to...

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

Falcon is a winner of NIST's six-year post-quantum cryptography standardisation competition. Based on the celebrated full-domain-hash framework of Gentry, Peikert and Vaikuntanathan (GPV) (STOC'08), Falcon leverages NTRU lattices to achieve the most compact signatures among lattice-based schemes. Its security hinges on a Rényi divergence-based argument for Gaussian samplers, a core element of the scheme. However, the GPV proof, which uses statistical distance to argue closeness of...

We present a new compact and tightly secure (anonymous) identity-based encryption (IBE) scheme based on structured lattices. This is the first IBE scheme that is (asymptotically) as compact as the most practical NTRU-based schemes and tightly secure under the module learning with errors (MLWE) assumption, known as the standard lattice assumption, in the (quantum) random oracle model. In particular, our IBE scheme is the most compact lattice-based scheme (except for NTRU-based schemes). We...

We construct the first multi-input functional encryption (MIFE) and indistinguishability obfuscation (iO) schemes for pseudorandom functionalities, where the output of the functionality is pseudorandom for every input seen by the adversary. Our MIFE scheme relies on LWE and evasive LWE (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) for constant arity functions, and a strengthening of evasive LWE for polynomial arity. Thus, we obtain the first MIFE and iO schemes for a nontrivial...

We provide the first construction of compact Functional Encryption (FE) for pseudorandom functionalities from the evasive LWE and LWE assumptions. Intuitively, a pseudorandom functionality means that the output of the circuit is indistinguishable from uniform for every input seen by the adversary. This yields the first compact FE for a nontrivial class of functions which does not rely on pairings. We demonstrate the power of our new tool by using it to achieve optimal parameters for both...

The Leftover Hash Lemma (LHL) is a powerful tool for extracting randomness from an entropic distribution, with numerous applications in cryptography. LHLs for discrete Gaussians have been explored in both integer settings by Gentry et al. (GPV, STOC'08) and algebraic ring settings by Lyubashevsky et al. (LPR, Eurocrypt'13). However, the existing LHLs for discrete Gaussians have two main limitations: they require the Gaussian parameter to be larger than certain smoothing parameters, and they...

In the Dilithium digital signature scheme, there is an inherent tradeoff between the length of the public key, and the length of the signature. The coefficients of the main part of the public-key, the vector $\mathbf{t}$, are compressed (in a lossy manner), or "quantized", during the key-generation procedure, in order to save on the public-key size. That is, the coefficients are divided by some fixed denominator, and only the quotients are published. However, this results in some "skew"...

Searchable encryption is a cryptographic primitive that allows us to perform searches on encrypted data. Searchable encryption schemes require that ciphertexts do not leak information about keywords. However, most of the existing schemes do not achieve the security notion that trapdoors do not leak information. Shen et al. (TCC 2009) proposed a security notion called full security, which includes both ciphertext privacy and trapdoor privacy, but there are few fully secure constructions. Full...

In Noncommutative Ring Learning With Errors From Cyclic Algebras, a variant of Learning with Errors from cyclic division algebras, dubbed ‘Cyclic LWE', was developed, and security reductions similar to those known for the ring and module case were given, as well as a Regev-style encryption scheme. In this work, we make a number of improvements to that work: namely, we describe methods to increase the number of cryptographically useful division algebras, demonstrate the hardness of CLWE from...

In this work, we introduce a more efficient post-quantum oblivious PRF (OPRF) design, called LeOPaRd. Our proposal is round-optimal and supports verifiability and partial obliviousness, all of which are important for practical applications. The main technical novelty of our work is a new method for computing samples of MLWE (module learning with errors) in a two-party setting. To do this, we introduce a new family of interactive lattice problems, called interactive MLWE and rounding with...

In this paper, we construct the first asymptotically efficient two-round $n$-out-of-$n$ and multi-signature schemes from lattices in the quantum random oracle model (QROM), using the Fiat-Shamir with Aborts (FSwA) paradigm. Our protocols can be viewed as the QROM~variants of the two-round protocols by Damgård et al. (JoC 2022). A notable feature of our protocol, compared to other counterparts in the classical random oracle model, is that each party performs an independent abort and still...

As an emerging primitive, Registered Functional Encryption (RFE) eliminates the key-escrow issue that threatens numerous works for functional encryption, by replacing the trusted authority with a transparent key curator and allowing each user to sample their decryption keys locally. In this work, we present a new black-box approach to construct RFE for all polynomial-sized circuits. It considers adaptive simulation-based security in the bounded collusion model (Gorbunov et al. - CRYPTO'12),...

In this paper, we introduce the notion of relaxed lattice-based programmable hash function (RPHF), which is a novel variant of lattice-based programmable hash functions (PHFs). Lattice-based PHFs, together with preimage trapdoor functions (TDFs), have been widely utilized (implicitly or explicitly) in the construction of adaptively secure identity-based encryption (IBE) schemes. The preimage length and the output length of the underlying PHF and TDF together determine the user secret key and...

In scenarios where a seller holds sensitive data $x$, like employee / patient records or ecological data, and a buyer seeks to obtain an evaluation of specific function $f$ on this data, solutions in trustless digital environments like blockchain-based Web3 systems typically fall into two categories: (1) Smart contract-powered solutions and (2) cryptographic solutions leveraging tools such as adaptor signatures. The former approach offers atomic transactions where the buyer learns the...

The Lattice Isomorphism Problem (LIP) was recently introduced as a new hardness assumption for post-quantum cryptography. The strongest known efficiently computable invariant for LIP is the genus of a lattice. To instantiate LIP-based schemes one often requires the existence of a lattice that (1) lies in some fixed genus, and (2) has some good geometric properties such as a high packing density or small smoothness parameter. In this work we show that such lattices exist. In particular,...

We revisit the lattice-based verifiable oblivious PRF construction from PKC'21 and remove or mitigate its central three sources of inefficiency. First, applying Rényi divergence arguments, we eliminate one superpolynomial factor from the ciphertext modulus \(q\), allowing us to reduce the overall bandwidth consumed by RLWE samples by about a factor of four. This necessitates us introducing intermediate unpredictability notions to argue PRF security of the final output in the Random Oracle...

A broadcast encryption scheme allows a user to encrypt a message to $N$ recipients with a ciphertext whose size scales sublinearly with $N$. While broadcast encryption enables succinct encrypted broadcasts, it also introduces a strong trust assumption and a single point of failure; namely, there is a central authority who generates the decryption keys for all users in the system. Distributed broadcast encryption offers an appealing alternative where there is a one-time (trusted) setup...

We present new lattice-based attribute-based encryption (ABE) and laconic function evaluation (LFE) schemes for circuits with *sublinear* ciphertext overhead. For depth $d$ circuits over $\ell$-bit inputs, we obtain * an ABE with ciphertext and secret key size $O(1)$; * a LFE with ciphertext size $\ell + O(1)$ and digest size $O(1)$; * an ABE with public key and ciphertext size $O(\ell^{2/3})$ and secret key size $O(1)$, where $O(\cdot)$ hides $\mbox{poly}(d,\lambda)$...

Recent constructions of vector commitments and non-interactive zero-knowledge (NIZK) proofs from LWE implicitly solve the following /shifted multi-preimage sampling problem/: given matrices $\mathbf{A}_1, \ldots, \mathbf{A}_\ell \in \mathbb{Z}_q^{n \times m}$ and targets $\mathbf{t}_1, \ldots, \mathbf{t}_\ell \in \mathbb{Z}_q^n$, sample a shift $\mathbf{c} \in \mathbb{Z}_q^n$ and short preimages $\boldsymbol{\pi}_1, \ldots, \boldsymbol{\pi}_\ell \in \mathbb{Z}_q^m$ such that $\mathbf{A}_i...

Lattice-based identity-based encryption having both efficiency and provable security in the standard model is currently still a challenging task and has drawn much attention. In this work, we introduce a new IBE construction from NTRU lattices in the standard model, based on the framework proposed by Agrawal, Boneh, and Boyen (EUROCRYPT 2010). Particularly, by introducing the NTRU trapdoor and the RingLWE computational assumption, we remove a crux restriction of the column number and obtain...

The recent works of Ananth et al. (ITCS 2022) and Bartusek et al. (Eurocrypt 2023) initiated the study of pre-constrained cryptography which achieves meaningful security even against the system authority. In this work we significantly expand this area by defining several new primitives and providing constructions from simple, standard assumptions as follows. - Pre-Constrained Encryption. We define a weaker notion of pre-constrained encryption (PCE), as compared to the work of Ananth et...

In this paper, we propose Greyhound, the first concretely efficient polynomial commitment scheme from standard lattice assumptions. At the core of our construction lies a simple three-round protocol for proving evaluations for polynomials of bounded degree $N$ with verifier time complexity $O(\sqrt{N})$. By composing it with the LaBRADOR proof system (CRYPTO 2023), we obtain a succinct proof of polynomial evaluation (i.e. polylogarithmic in $N$) that admits a sublinear verifier...

With the potential arrival of quantum computers, it is essential to build cryptosystems resistant to attackers with the computing power of a quantum computer. With Shor's algorithm, cryptosystems based on discrete logarithms and factorization become obsolete. Reason why NIST has launching two competitions in 2016 and 2023 to standardize post-quantum cryptosystems (such as KEM and signature ) based on problems supposed to resist attacks using quantum computers. EagleSign was prosed to NIT...

Lattice cryptography is currently a major research focus in public-key encryption, renowned for its ability to resist quantum attacks. The introduction of ideal lattices (ring lattices) has elevated the theoretical framework of lattice cryptography. Ideal lattice cryptography, compared to classical lattice cryptography, achieves more acceptable operational efficiency through fast Fourier transforms. However, to date, issues of impracticality or insecurity persist in ideal lattice problems....

At Eurocrypt'24, Mureau et al. formally defined the Lattice Isomorphism Problem for module lattices (module-LIP) in a number field $\mathbb{K}$, and proposed a heuristic randomized algorithm solving module-LIP for modules of rank 2 in $\mathbb{K}^2$ with a totally real number field $\mathbb{K}$, which runs in classical polynomial time for a large class of modules and a large class of totally real number field under some reasonable number theoretic assumptions. In this paper, by introducing a...

Private information retrieval (PIR) is a key building block in many privacy-preserving systems, and recent works have made significant progress on reducing the concrete computational costs of single-server PIR. However, existing constructions have high communication overhead, especially for databases with small records. In this work, we introduce Respire, a lattice-based PIR scheme tailored for databases of small records. To retrieve a single record from a database with over a million...

In this short note, we introduce a specific class of rank two lattices over CM fields endowed with additional symmetries, which are involved in the decomposition of algebraic integers in Hermitian squares. As an application, we show an elementary reduction from the module-LIP problem in rank 2 over a CM or totally real number field to the finding of a square basis in such lattices.

EagleSign is one of the 40 “Round 1 Additional Signatures” that is accepted for consideration in the supplementary round of the Post-Quantum Cryptography standardization process, organized by NIST. Its design is based on structured lattices, and it boasts greater simplicity and performance compared to the two lattice signatures already selected for standardization: Falcon and Dilithium. In this paper, we show that those claimed advantages come at the cost of security. More precisely, we...

Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as an ideal into infinitely...

This paper presents a novel reduction from the average-case hardness of the Module Inhomogeneous Short Integer Solution (M-ISIS) problem to the worst-case hardness of the Closest Vector Problem (CVP) by defining and leveraging “perfect” lattices for cryptographic purposes. Perfect lattices, previously only theoretical constructs, are characterized by their highly regular structure, optimal density, and a central void, which we term the “Origin Cell.” The simplest Origin Cell is a...

Proxy re-encryption is a cryptosystem that achieves efficient encrypted data sharing by allowing a proxy to transform a ciphertext encrypted under one key into another ciphertext under a different key. Homomorphic proxy re-encryption (HPRE) extends this concept by integrating homomorphic encryption, allowing not only the sharing of encrypted data but also the homomorphic computations on such data. The existing HPRE schemes, however, are limited to a single or bounded number of hops of...

The field of Fully Homomorphic Encryption (FHE) has seen many theoretical and computational advances in recent years, bringing the technology closer to practicality than ever before. For this reason, practitioners from neighbouring fields such as machine learning have sought to understand FHE to provide privacy to their work. Unfortunately, selecting secure and efficient parameters in FHE is a daunting task due to the many interdependencies between the parameters involved. In this work, we...

We propose a new framework based on random submersions — that is projection over a random subspace blinded by a small Gaussian noise — for constructing verifiable short secret sharing and showcase it to construct efficient threshold lattice-based signatures in the hash-and-sign paradigm, when based on noise flooding. This is, to our knowledge, the first hash-and-sign lattice-based threshold signature. Our threshold signature enjoys the very desirable property of robustness, including at key...

Fully homomorphic signatures are a significant strengthening of digital signatures, enabling computations on \emph{secretly} signed data. Today, we have multiple approaches to design fully homomorphic signatures such as from lattices, or succinct functional commitments, or indistinguishability obfuscation, or mutable batch arguments. Unfortunately, all existing constructions for homomorphic signatures suffer from one or more limitations. We do not have homomorphic signatures with features...

Direct Anonymous Attestation (DAA) allows a (host) device with a Trusted Platform Module (TPM) to prove that it has a certified configuration of hardware and software whilst preserving the privacy of the device. All deployed DAA schemes are based on classical security assumptions. Despite a long line of works proposing post-quantum designs, the vast majority give only theoretical schemes and where concrete parameters are computed, their efficiency is far from practical. Our first...

We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear groups together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence pseudorandom generators (PRGs) in $\mathsf{NC}^0$ with polynomial stretch from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an...

We prove an algebraic analogue of Pataki-Tural lemma (Pataki-Tural, arXiv:0804.4014, 2008) -- the main tool in analysing the so-called overstretched regime of NTRU. Our result generalizes this lemma from Euclidean lattices to modules over any number field enabling us to look at NTRU as rank-2 module over cyclotomic number fields with a rank-1 dense submodule generated by the NTRU secret key. For Euclidean lattices, this overstretched regime occurs for large moduli $q$ and...

The Learning with Errors (LWE) problem with its variants over structured lattices has been widely exploited in efficient post-quantum cryptosystems. Recently, May suggests the Meet-LWE attack, which poses a significant advancement in the line of work on the Meet-in-the-Middle approach to analyze LWE with ternary secrets. In this work, we generalize and extend the idea of Meet-LWE by introducing ternary trees, which result in diverse representations of the secrets. More precisely, we...

We present a general framework for constructing attribute-based encryption (ABE) schemes for arbitrary function class based on lattices from two ingredients, i) a noisy linear secret sharing scheme for the class and ii) a new type of inner-product functional encryption (IPFE) scheme, termed *evasive* IPFE, which we introduce in this work. We propose lattice-based evasive IPFE schemes and establish their security under simple conditions based on variants of evasive learning with errors (LWE)...

In this paper, we present a new attack against search-LWE instances with a small secret key. The method consists of lifting the public key to $\mathbb Z$ and finding a good Diophantine approximation of the public key divided by the modulus $a$. This is done using lattice reduction algorithms. The lattice considered, and the approximation quality needed is similar to known decision-LWE attacks for small keys. However, we do not require an in-depth analysis of the reduction algorithm (any...

We study the complexity of the Code Equivalence Problem on linear error-correcting codes by relating its variants to isomorphism problems on other discrete structures---graphs, lattices, and matroids. Our main results are a fine-grained reduction from the Graph Isomorphism Problem to the Linear Code Equivalence Problem over any field $\mathbb{F}$, and a reduction from the Linear Code Equivalence Problem over any field $\mathbb{F}_p$ of prime, polynomially bounded order $p$ to the Lattice...

Lattice sieves are algorithms for finding short vectors in lattices. We present an implementation of two such sieves – known as “BGJ1” and “BDGL” in the literature – that scales across multiple servers (with varying success). This class of algorithms requires exponential memory which had put into question their ability to scale across sieving nodes. We discuss our architecture and optimisations and report experimental evidence of the efficiency of our approach.

This paper presents a generalization of the Learning With Rounding (LWR) problem, initially introduced by Banerjee, Peikert, and Rosen, by applying the perspective of vector quantization. In LWR, noise is induced by scalar quantization. By considering a new variant termed Learning With Quantization (LWQ), we explore large-dimensional fast-decodable lattices with superior quantization properties, aiming to enhance the compression performance over scalar quantization. We identify polar...

In 1994, Shor introduced his famous quantum algorithm to factor integers and compute discrete logarithms in polynomial time. In 2023, Regev proposed a multi-dimensional version of Shor's algorithm that requires far fewer quantum gates. His algorithm relies on a number-theoretic conjecture on the elements in $(\mathbb{Z}/N\mathbb{Z})^{\times}$ that can be written as short products of very small prime numbers. We prove a version of this conjecture using tools from analytic number theory such...

Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Coincidentally, the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver. With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23)...

Lattice-based cryptography typically uses lattices with special properties to improve efficiency. We show how blockwise reduction can exploit lattices with special geometric properties, effectively reducing the required blocksize to solve the shortest vector problem to half of the lattice's rank, and in the case of the hypercubic lattice $\mathbb{Z}^n$, further relaxing the approximation factor of blocks to $\sqrt{2}$. We study both provable algorithms and the heuristic well-known primal...

In this work, we analyze the so-called Beyond UnForgeability Features (BUFF) security of the submissions to the current standardization process of additional signatures by NIST. The BUFF notions formalize security against maliciously generated keys and have various real-world use cases, where security can be guaranteed despite misuse potential on a protocol level. Consequently, NIST declared the security against the BUFF notions as desirable features. Despite NIST's interest, only $6$ out of...

We show a polynomial time quantum algorithm for solving the learning with errors problem (LWE) with certain polynomial modulus-noise ratios. Combining with the reductions from lattice problems to LWE shown by Regev [J.ACM 2009], we obtain polynomial time quantum algorithms for solving the decisional shortest vector problem (GapSVP) and the shortest independent vector problem (SIVP) for all $n$-dimensional lattices within approximation factors of $\tilde{\Omega}(n^{4.5})$. Previously, no...

At S$\&$P 2023, a family of secure three-party computing protocols called Bicoptor was proposed by Zhou et al., which is used to compute non-linear functions in privacy preserving machine learning. In these protocols, two parties $P_0, P_1$ respectively hold the corresponding shares of the secret, while a third party $P_2$ acts as an assistant. The authors claimed that neither party in the Bicoptor can independently compromise the confidentiality of the input, intermediate, or output. In...

Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019). Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...

Pseudo-random generators are deterministic algorithms that take in input a random secret seed and output a flow of random-looking numbers. The Knapsack generator, presented by Rueppel and Massey in 1985 is one of the many attempt at designing a pseudo-random generator that is cryptographically secure. It is based on the subset-sum problem, a variant of the Knapsack optimization problem, which is considered computationally hard. In 2011 Simon Knellwolf et Willi Meier found a way to go...

This paper gives the first lattice-based two-round threshold signature based on lattice assumptions for which the first message is independent of the message being signed without relying on fully-homomorphic encryption, and our construction supports arbitrary thresholds. Our construction provides a careful instantiation of a generic threshold signature construction by Tessaro and Zhu (EUROCRYPT ’23) based on specific linear hash functions, which in turns can be seen as a generalization of...

At Asiacrypt 2022, Ducas, Postlethwaite, Pulles, and van Woerden introduced the Lattice Isomorphism Problem for module lattices in a number field $K$ (module-LIP). In this article, we describe an algorithm solving module-LIP for modules of rank $2$ in $K^2$, when $K$ is a totally real number field. Our algorithm exploits the connection between this problem, relative norm equations and the decomposition of algebraic integers as sums of two squares. For a large class of modules (including...

Quantum computers at some future date might be able to factor large numbers, and this poses a threat to some public key and key exchange systems in use today. This overview of recent progress in devising quantum algorithms and building quantum computing devices is meant to help technologists understand the difficult problems that quantum engineers are working on, where advances have been made, and how those things affect estimates of if and when large scale quantum computation might happen.

Polynomial commitment scheme allows a prover to commit to a polynomial $f \in \mathcal{R}[X]$ of degree $L$, and later prove that the committed function was correctly evaluated at a specified point $x$; in other words $f(x)=u$ for public $x,u \in\mathcal{R}$. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree $L$) - with the...

Keyed homomorphic public key encryption (KHPKE) is a variant of homomorphic public key encryption, where only users who have a homomorphic evaluation key can perform a homomorphic evaluation. Then, KHPKE satisfies the CCA2 security against users who do not have a homomorphic evaluation key, while it satisfies the CCA1 security against users who have the key. Thus far, several KHPKE schemes have been proposed under the standard Diffie-Hellman-type assumptions and keyed fully homomorphic...

A functional commitment allows a user to commit to an input $\mathbf{x} \in \{0,1\}^\ell$ and later open up the commitment to a value $y = f(\mathbf{x})$ with respect to some function $f$. In this work, we focus on schemes that support fast verification. Specifically, after a preprocessing step that depends only on $f$, the verification time as well as the size of the commitment and opening should be sublinear in the input length $\ell$, We also consider the dual setting where the user...

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

In order to provide access control on encrypted data, Attribute-based encryption (ABE) defines each user using a set of attributes. Fuzzy identity-based encryption (FIBE) is a variant of ABE that allows for a threshold access structure for users. To address the potential threat posed by future quantum computers, this paper presents a post-quantum fuzzy IBE scheme based on lattices. However, current lattice-based ABE schemes face challenges related to computational complexity and the length...

An accountable subgroup multi-signature (ASM) is a multi-signature that allows any subgroup of potential signers to jointly sign a message such that the subgroup of co-signers are accountable for the resulting signature and their identities are identifiable to any verifier. In this paper, we pro- pose a novel lattice-based accountable subgroup multi-signature scheme, i.e., vMS2, by combining the group setup method of recently proposed vASM scheme and Damgard et al.’s lattice-based MS2...

Universal thresholdizer (UT) was proposed by Boneh et al. in CRYPTO'18 as a general framework for thresholdizing non-threshold cryptographic primitives where a set of $N$ servers, each gets a share such that any set of $k$ servers, each produces a partial result, which can be combined to generate the final result. In many applications of threshold cryptography such as the protection of private keys in a digital wallet, the combining operation of partial results must be protected. In this...

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have...

This work *completely breaks* the sequentiality assumption (and broad generalizations thereof) underlying the candidate lattice-based proof of sequential work (PoSW) recently proposed by Lai and Malavolta at CRYPTO 2023. In addition, it breaks an essentially identical variant of the PoSW, which differs from the original in only an arbitrary choice that is immaterial to the design and security proof (under the falsified assumption). This suggests that whatever security the original PoSW may...

The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders ($\mathsf{ISD}$). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly $\mathsf{ISD}$ decoders for a rather large range of rates. This RLPN decoder relies on...

The Dual-Sieve Attack on Learning with Errors (LWE), or more generally Bounded Distance Decoding (BDD), has seen many improvements in the recent years, and ultimately led to claims that it outperforms the primal attack against certain lattice-based schemes in the PQC standardization process organised by NIST. However, the work of Ducas--Pulles (Crypto '23) revealed that the so-called "Independence Heuristic", which all recent dual attacks used, leads to wrong predictions in a contradictory...

Driven by the open problem raised by Hofheinz and Kiltz (Journal of Cryptology, 2012), we study the formalization of lattice-based programmable hash function (PHF), and give three types of concrete constructions by using several techniques such as a novel combination of cover-free sets and lattice trapdoors. Under the Inhomogeneous Small Integer Solution (ISIS) assumption, we show that any (non-trivial) lattice-based PHF is a collision-resistant hash function, which gives a direct...

We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. 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...

The Learning with Errors (LWE) problem has been widely utilized as a foundation for numerous cryptographic tools over the years. In this study, we focus on an algebraic variant of the LWE problem called Group ring LWE (GR-LWE). We select group rings (or their direct summands) that underlie specific families of finite groups constructed by taking the semi-direct product of two cyclic groups. Unlike the Ring-LWE problem described in \cite{lyubashevsky2010ideal}, the multiplication operation in...

Multi-signatures allow for compressing many signatures for the same message that were generated under independent keys into one small aggregated signature. This primitive is particularly useful for proof-of-stake blockchains, like Ethereum, where the same block is signed by many signers, who vouch for the block's validity. Being able to compress all signatures for the same block into a short string significantly reduces the on-chain storage costs, which is an important efficiency metric...

Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first practical construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under...

CRYSTALS-Kyber is a key-encapsulation mechanism, whose security is based on the hardness of solving the learning-with-errors (LWE) problem over module lattices. As in its specification, Kyber prescribes the usage of the Number Theoretic Transform (NTT) for efficient polynomial multiplication. Side-channel assisted attacks against Post-Quantum Cryptography (PQC) algorithms like Kyber remain a concern in the ongoing standardization process of quantum-computer-resistant cryptosystems. Among the...

As various industries and government agencies increasingly seek to build quantum computers, the development of post-quantum constructions for different primitives becomes crucial. Lattice-based cryptography is one of the top candidates for constructing quantum-resistant primitives. In this paper, we propose a decentralized Private Stream Aggregation (PSA) protocol based on the Learning with Errors (LWE) problem. PSA allows secure aggregation of time-series data over multiple users without...

$\mathbb{Z}^n$ is one of the simplest types of lattices, but the computational problems on its rotations, such as $\mathbb{Z}$SVP and $\mathbb{Z}$LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of $\mathbb{Z}$SVP and $\mathbb{Z}$LIP are still not well understood. In this work, we study the problems on...

We show an explicit construction of an efficiently decodable family of $n$-dimensional lattices whose minimum distances achieve $\Omega(\sqrt{n} / (\log n)^{\varepsilon+o(1)})$ for $\varepsilon>0$. It improves upon the state-of-the-art construction due to Mook-Peikert (IEEE Trans.\ Inf.\ Theory, no. 68(2), 2022) that provides lattices with minimum distances $\Omega(\sqrt{n/ \log n})$. These lattices are construction-D lattices built from a sequence of BCH codes. We show that replacing BCH...

Although we have known about fully homomorphic encryption (FHE) from circular security assumptions for over a decade [Gentry, STOC '09; Brakerski–Vaikuntanathan, FOCS '11], there is still a significant gap in understanding related homomorphic primitives supporting all *unrestricted* polynomial-size computations. One prominent example is attribute-based encryption (ABE). The state-of-the-art constructions, relying on the hardness of learning with errors (LWE) [Gorbunov–Vaikuntanathan–Wee,...

We demonstrate that a passive network attacker can opportunistically obtain private RSA host keys from an SSH server that experiences a naturally arising fault during signature computation. In prior work, this was not believed to be possible for the SSH protocol because the signature included information like the shared Diffie-Hellman secret that would not be available to a passive network observer. We show that for the signature parameters commonly in use for SSH, there is an efficient...

In the design of an identity-based encryption (IBE) scheme, the primary security assumptions center around quadratic residues, bilinear mappings, and lattices. Among these approaches, one of the most intriguing is introduced by Clifford Cocks and is based on quadratic residues. However, this scheme has a significant drawback: a large ciphertext to plaintext ratio. A different approach is taken by Zhao et al., who design an IBE still based on quadratic residues, but with an encryption process...

An $(n, t)$-Verifiable Secret Sharing (VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we present $\Pi$, as a unified framework for building VSS schemes in the honest majority setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a random oracle and any commitment scheme that extra to its core attributes...

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

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

Lattice reduction algorithms such as BKZ (Block-Korkine-Zolotarev) play a central role in estimating the security of lattice-based cryptography. The subroutine in BKZ which finds the shortest vector in a projected sublattice can be instantiated with enumeration algorithms. The enumeration procedure can be seen as a depth-first search on some ``enumeration tree'' whose nodes denote a partial assignment of the coefficients, corresponding to lattice points as a linear combination of the lattice...

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

A recent work by Guo, Johansson, and Nguyen (Eprint'23) proposes a promising adaptation of Sieving techniques from lattices to codes, in particular, by claiming concrete cryptanalytic improvements on various schemes. The core of their algorithm reduces to a Near Neighbor Search (NNS) problem, for which they devise an ad-hoc approach. In this work, we aim for a better theoretical understanding of this approach. First, we provide an asymptotic analysis which is not present in the original...

Blind rotation is one of the key techniques to construct fully homomorphic encryptions with the best known bootstrapping algorithms running in less than one second. Currently, the two main approaches, namely, AP and GINX, for realizing blind rotation are first introduced by Alperin-Sheriff and Peikert (CRYPTO 2014) and Gama, Izabachene, Nguyen and Xie (EUROCRYPT 2016), respectively. \qquad In this paper, we propose a new blind rotation algorithm based on a GSW-like encryption from the...

This paper explores the challenges and potential solutions of implementing the recommended upcoming post-quantum cryptography standards (the CRYSTALS-Dilithium and CRYSTALS-Kyber algorithms) on resource constrained devices. The high computational cost of polynomial operations, fundamental to cryptography based on ideal lattices, presents significant challenges in an efficient implementation. This paper proposes a hardware/software co-design strategy using RISC-V extensions to optimize...

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

The Hybrid Public Key Encryption (HPKE) standard was recently published as RFC 9180 by the Crypto Forum Research Group (CFRG) of the Internet Research Task Force (IRTF). The RFC specifies an efficient public key encryption scheme, combining asymmetric and symmetric cryptographic building blocks. Out of HPKE’s four modes, two have already been formally analyzed by Alwen et al. (EUROCRYPT 2021). This work considers the remaining two modes: HPKE_PSK and HPKE_AuthPSK . Both of them are...

The NTRU assumption provides one of the most prominent problems on which to base post-quantum cryptography. Because of the efficiency and security of NTRU-style schemes, structured variants have been proposed, using modules. In this work, we create a structured form of NTRU using lattices obtained from orders in cyclic division algebras of index 2, that is, from quaternion algebras. We present a public-key encryption scheme, and show that its public keys are statistically close to uniform....

Recent works on lattice-based extractable polynomial commitments can be grouped into two classes: (i) non-interactive constructions that stem from the functional commitment by Albrecht, Cini, Lai, Malavolta and Thyagarajan (CRYPTO 2022), and (ii) lattice adaptations of the Bulletproofs protocol (S&P 2018). The former class enjoys security in the standard model, albeit a knowledge assumption is desired. In contrast, Bulletproof-like protocols can be made secure under falsifiable assumptions,...

Identity-based matchmaking encryption (IB-ME) [Ateniese et al. Crypto 2019] allows users to communicate privately in an anonymous and authenticated manner. After the seminal paper by Ateniese et al., a lot of work has been done on the security and construction of IB-ME. In this work, we revisit the security definitions of IB-ME and provide improved constructions of it. First, we classify the existing security notions of IB-ME, systematically categorizing privacy into three categories (CPA,...

This paper mainly studies an open problem in modern cryptography, namely the Ring-SIS reduction problem. In order to prove the hardness of the Ring-SIS problem, this paper introduces the concepts of the one-dimensional SIS problem, the Ring-SIS$|_{x=0}$ problem, and the variant knapsack problem. The equivalence relations between the three are first established, on which the connection between the Ring-SIS$|_{x=0}$ problem and the Ring-SIS problem is built. This proves that the hardness of...

Succinct arguments allow a prover to convince a verifier of the validity of any statement in a language, with minimal communication and verifier's work. Among other approaches, lattice-based protocols offer solid theoretical foundations, post-quantum security, and a rich algebraic structure. In this work, we present some new approaches to constructing efficient lattice-based succinct arguments. Our main technical ingredient is a new commitment scheme based on vanishing polynomials, a notion...

Updatable public key encryption has recently been introduced as a solution to achieve forward-security in the context of secure group messaging without hurting efficiency, but so far, no efficient lattice-based instantiation of this primitive is known. In this work, we construct the first LWE-based UPKE scheme with polynomial modulus-to-noise rate, which is CPA-secure in the standard model. At the core of our security analysis is a generalized reduction from the standard LWE problem to (a...

This article aims to speed up (the precomputation stage of) multi-scalar multiplication (MSM) on ordinary elliptic curves of $j$-invariant $0$ with respect to specific ''independent'' (a.k.a. ''basis'') points. For this purpose, so-called Mordell--Weil lattices (up to rank $8$) with large kissing numbers (up to $240$) are employed. In a nutshell, the new approach consists in obtaining more efficiently a considerable number (up to $240$) of certain elementary linear combinations of the...

We give a tighter security proof for authenticated key exchange (AKE) protocols that are generically constructed from key encapsulation mechanisms (KEMs) in the quantum random oracle model (QROM). Previous works (Hövelmanns et al., PKC 2020) gave reductions for such a KEM-based AKE protocol in the QROM to the underlying primitives with square-root loss and a security loss in the number of users and total sessions. Our proof is much tighter and does not have square-root loss. Namely, it only...

The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO'10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below $d^{O(d)}$ for cyclotomic fields, here $d$ refers to...

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