# Questions tagged as ['lattice-crypto']

Lattice-cryptography is the study and use of lattice problems applied to cryptography.
Score: 1
The relationship between root hermite factor and bit-security?

The root hermite factor corresponding to an bit-security level, such as 1.0045 corresponding to 128-bit security. What is the root hermite factor corresponding to 100-bit, 160-bit, 180-bit security?

root hermite factor: 1.0045 ? ? ? bit-security : 128 100 160 180

Score: 3
What are Practical Primitives based on Lattices, LWE and FHE?

Lattice-based cryptography is being used for several primitives and applications.

I know there are newer works for PIR, PSI, ORAM that have seen tremendous improvements due to FHE. In some cases, FHE is the only tool that can be used for practical constructions of these primitives.

My question is which other such primitives have seen improvements (in performance or security)?

Score: 0
How to estimate the parameter of a lattice signature scheme with lossy reduction?

The parameter of a lattice signature scheme DAZ19 with tight reduction can be choosed to make the underlying hardness problem intractable. How to estimate the parameter of a lattice signature scheme ESLL19 with lossy reduction? is there any relation between the reduction and parameter?

Score: 1
Key Switching Error in CKKS

I believe I am misunderstanding something about the bounds derived for the key switching error in CKKS. I will refer to the initial paper, but similar bounds have been derived in all variants I have looked into.

My particular point of confusion is with $$B_{\mathsf{mult}}(\ell)$$ (on page 12, as part of lemma 3), which is defined to be $$P^{-1}q_\ell B_{\mathsf{ks}}$$, where $$B_{\mathsf{ks}} = O(N\sigma)$$

Score: 3
The decryption correctness of RLWE based Encryption

I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper.

And the decryption correctness proof of the scheme follows

In this proof , I can get the second last equation in decryption procedure , i.e. $$\mathbf{m} + (t/q)(\mathbf{v}-\epsilon \cdot \mathbf{m}) + t\cdot \mathbf{r} ...$$

Score: 1
Equivalence between search-LWE and decision-LWE

Are there any constraints when it comes to proving that search-LWE and decision-LWE are equivalent? Should we assume that the module $$q$$ is prime when switching from one version to another?

Please give a good reference where proof exists.

Score: 2
A newbie question about NTRUEncrypt: small r(x) and closest vector problem

In NTRUEncrypt with system-wide parameters $$(N, p, q)$$, let Bob's public key be $$h(x).$$

To encrypt plaintext $$m(x)$$ whose coefficients are small, Alice needs to generate a random $$r(x),$$ whose coefficients need to be small too, and calculates ciphertext $$c(x) = r(x) \times h(x) + m(x) \bmod q.$$

It is considered difficult to find $$m(x)$$ from $$c(x)$$ and this difficulty is presumably based on the clo ...

Score: 5
Why do Lattice-based Proof Systems not use the $\ell_2$ norm and canonical embedding?

I was recently reading the paper A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge. Among other things, it discusses an adaption of the "folding" technique (from Bulletproofs) to SIS-based proofs.

The paper measures distances in the $$\ell_\infty$$ norm (rather than $$\ell_2$$), and is vague on which choice of embedding it uses (although I imagine it is the coefficient embedding). These choices  ...

Score: 1
Why $q$ in LWE must be polynomial in $n$

I am wondering why the modulus $$q$$ in the LWE problem has to be polynomial in $$n$$.

Another question is whether one can take it to be an arbitrary integer instead of a prime number.

Score: 1
How to prove the inequalities of q-ary lattice determinant?

for $$A\in{Z_q^{n*m}}$$ and $$A^{'}\in{Z_q^{m*n}}$$,we have

• $$det{({\land}_q^{\bot}(A))}{\le}q^n$$ and $$det{({\land}_q(A^{'}))}{\ge}q^{m-n}$$
• if q is prime,and A,A' are non-singular in the finite field $$Z_q$$,the above inequality are equalities.

where $${\land}_q^{\bot}(A) = \{x{\in}Z^m|Ax=0{\bmod}q\}$$ and $${\land}_q(A)=\{y{\in}Z^m|y=As{\bmod}q\}$$

The above content comes from D. Dadush's lecture note( ...

Score: 3
How to decide if an element is a public key in NTRU encryption scheme?

First, I'm using the settings of https://en.wikipedia.org/wiki/NTRUEncrypt, with $$L_f$$ set of polynomials with $$d_f+1$$ coefficients equal to 1, $$d_f$$ equal to $$-1$$ and the remaining $$N-2d_f-1$$ equal to 0; and $$L_g$$ the set of polynomials with $$d_g$$ coefficients equal to 1, $$d_g$$ equal to $$-1$$ and the remaining $$N-2d_g$$ equal to 0. The natural numbers $$d_f$$ and $$d_g$$ are just fixed parameters of the sche ...

Score: 0
Volume $q^n$ of a dual q-ary lattice in MR09

Given a matrix $$\mathbf{A} \in \mathbb{Z}^{n \times m}$$, $$m$$ sufficiently large with respect to $$n$$ and prime $$q$$. The rows of $$\mathbf{A}$$ are linearly independent with high probability. In MR09 the authors state that the number of vectors in $$\mathbb{Z}_q^m$$ belonging to the $$q$$-ary lattice $$\Lambda_q^\intercal(\mathbf{A})$$ is $$q^{m-n}$$ and therefore it follows that $$\text{det}(\Lambda_q^\intercal ...$$

Score: 0
NTL: Solve the closest vector problem for non-square matrix using LLL/Nearest Plane Algorithm

Assume I have a matrix $$A \in \mathbb{Z}^{m \times n}$$, $$m > n$$, which forms a basis of a lattice. Given a vector target vector $$t = Ax + e$$, $$t,e \in \mathbb{Z}^m$$,$$x \in \mathbb{Z}^n$$, I want to find the (approximate) closest vector in the lattice $$\mathcal{L}(A)$$ to $$t$$.

I wanted to use Babai's nearest plane algorithm, in particular the NTL implementation NTL::NearVector to solve this problem (a ...

Score: 24
What does the work "An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor" mean?

In An Efficient Quantum Algorithm for Lattice Problems Achieving Subexponential Approximation Factor, the author claims they give a polynomial-time quantum algorithm for solving the Bounded Distance Decoding problem with a subexponential approximation factor on a class of integer lattices. What does this result mean? Will it imply the insecurity of lattice cryptography? Is it as important as quan ...

Score: 0
Bit-security of ISIS based cryptosystem

I am currently working on an ISIS based signature scheme cryptosystem. I am trying to evaluate the bit-security of my construction. To do so, I try to calculate the number of operations needed in BKZ reduction.

I think I was able to find the right formula to calculate the total time complexity of BKZ. However, how do I get the bit-security from this result? This might be a silly question, but I a ...

Score: 3
Lattice-based cryptography: secret from Gaussian distribution chi

In a lecture, by Chris Peikert (link 40:20), he showed more efficient cryptosystems that have the secret be drawn from the Gaussian error distribution $$\chi$$. In the lecture he said "some applications which really really need secrets to come from the error distribution and they don't really work so well if they come from uniform distribution" and he adds "for some strange reason this is the form i ...

Score: 0
Finding a basis for q-ary lattices

For $$A\in \mathbb{Z_q}^{n\times m}$$, where $$m \geq n$$, consider the given two q-ary lattices \begin{align} \Lambda_q^{\bot}{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: A\mathbf{x} = \mathbf{0}\text{ mod }q\} \\ \Lambda_q{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\}. \end{align}

Compute a basis for the above ...

Score: 2
SIS vs LWE Problem

The Ajtai one way function is defined by

$$f_A(x)= Ax \; mod\; q$$ where the x $$\in \{0,1\}^m$$ and A $$\in \mathbb{Z_q}^{n \times m}$$. $$f_A(x)$$ is one way function ( Ajtai 96)

While the Regev One way function(Regev 05) is defined over x $$\in \mathbb{Z_q}^k$$ and $$e \in \mathscr{E}^m$$ and A $$\in \mathbb{Z_q}^{m \times k}$$ .The one way function is defined as

$$g_A(x,e) =Ax +e \; mod\; q \; (LWE)$$

Score: 2
Constraints on q for q-ary lattices?

In lattice cryptography, people often work with q-ary lattices so that we can use the hardness of short integer solution (SIS) and learning with errors (LWE). I saw in some notes that sometimes we want $$q$$ to be prime or a prime power. However there wasn't any explanation to why that is the case. So I have a couple of questions about the choice of $$q$$:

1. Is there any issues with taking q to be any po ...
Score: 1
Sentinel ("trick") values for lattice attack on DSA with biased k (MSB)

I'm studying lattice attack using this sage script. There are 2 options in script: LSB and MSB. The most interesting option for me is MSB. It recovers private key with less then 100 signatures provided with script. When I run it with my PQG generated by openssl and my own signatures with zeroed 8-bit MSB I was able to recover private key with 800 signatures in one case and unable to recover even wi ...

Score: 2
Question about coefficient of ECDSA in lattice attack

Update: I made my lattice attack worked finally. As the actual reason is quite complicated I decide to write an answer below to describe how it worked so anyone with similar question might get inspiration from my work. The Question is not modified.

I was studying lattice attack recently. I tried to use data from TPM-FAIL to help me understand this attack and try to implement an attack using "textbook meth ...

Score: 4
Prove that a small Ring-LWE secret is unique

I just want to know whether my proof is correct, which is about proving that if the Ring-LWE secret is small, then it is unique. Before giving my proof, here is a fact:

Fact 1: $$\Pr [\Vert r \Vert_\infty \leq \beta: r\xleftarrow{\\\} R_q]\leq \left(\dfrac{2\beta+1}{q}\right)^n$$, where $$R_q=\mathbb{Z}_q[X]/(X^n+1)$$, where $$n$$ is a power of two, $$q$$ is a prime and $$\beta$$ is some positive real number ...

Score: 2
q-ary lattices - proof of dual upto scale

Two lattices are defined as following: \begin{align} \Lambda_q^{\bot}{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: A\mathbf{x} = \mathbf{0}\text{ mod }q\} \\ \Lambda_q{(A)} & = \{\mathbf{x} \in \mathbb{Z}^m: \mathbf{x} = A^T\mathbf{s} \text{ mod }q \text{ for some } \mathbf{s} \in \mathbb{Z}^n_q\}. \end{align} T.S.T.

1. $$\Lambda_q{(A)} = q \cdot \Lambda_q^{\bot}{(A)}^*$$, where $$\Lambda_q^{\bot}{(A ...$$
Score: 2
Schnorr RSA factoring (round 2)

## Introduction

Earlier this year Claus Peter Schnorr claimed to have "broken RSA". The original paper was discussed in Does Schnorr's 2021 factoring method show that the RSA cryptosystem is not secure?. A revised version of his paper was posted on the iacr about a week ago and as per @fgrieu's comment, someone attempted to start a discussion around it: Is “Fast Factoring Integers by SVP Algorithms, cor ...

Score: 3
SIS without the modulus

Consider the following modification to the Short Integer Solution (SIS) problem:

Let $$n$$ be an integer and $$\alpha=\alpha(n),\beta=\beta(n),m=m(n)>\Omega(n\log \alpha)$$ be functions of $$n$$. Sample a uniform $$A\gets[-\alpha,\alpha]^{n\times m}$$. The task is to compute "short" vector $$e\in\mathbb{Z}^m$$ in the kernel of $$A$$. That is:

1. $$|e| < \beta$$.
2. $$A.e=0^n$$. Here, equality holds over the integers
Score: 0
Is my proof about uniqueness of ring-LWE secret correct?

Suppose that $$n$$ is a power of two, $$q=3\pmod 8$$, prime and $$R=\mathbb{Z}[X]/(X^n+1)$$. Denote $$\Vert\cdot\Vert$$ as the infinity norm in $$R_q=R/qR$$ on the coefficients of elements in $$R_q$$. The coefficients are assumed to be in $$[-\frac{q-1}{2},\frac{q-1}{2}]$$. I'll just cite some facts that I will use in my proof:

1. $$X^n+1$$ factors into two irreducible factors modulo $$q$$, where each factor is of de ...
Score: 1
Lattice in Sage: Generate matrix A from a basis S such that AS = 0 (mod q)

In Sage, there is a function: gen_lattice() that can generate a basis $$S \in \mathbb{Z}^{m \times m}_q$$ of a lattice $$\Lambda^\bot_q(A)$$, where $$A \in \mathbb{Z}^{n \times m}_q$$ is a random.

Therefore, $$AS = 0 \pmod q.$$

The question is: is there any method that can further obtain a matrix $$A \in \mathbb{Z}^{n \times m}_q.$$

(i.e., the TrapGen algorithm in AP09.)

Score: 3
Why define the dual of an ideal lattice with "Tr" rather than inner product?

In the paper [LPR12], I've learned that ideal lattices are ideals in algebraic number fields. However, I can't understand why we define the dual lattice of an ideal lattice with $$\operatorname{Tr}$$: $${L}^{\vee}=\{x \in K: \operatorname{Tr}(x {L}) \subseteq \mathbb{Z}\}$$

In detail, I mean, for any algebraic number field $$K$$, there's an embedding that embed it into space $$H$$. For $$K=\mathbb Q[\zeta] ...$$

Score: 0
What's the performance of the HElib and SEAL?

HElib contains the CKKS and BGV, SEAL contains the BFV and CKKS, is there some concrete performance data about these two lib?

Score: 2
Volume of an NTRU lattice

Let $$K$$ be a number field of degree $$n$$ and $$\Lambda^q_h=\{(f,g)\in\mathcal{O}_K\text{ : }fh-g = 0\bmod q\mathcal{O}_K\}$$, where $$h$$ is an NTRU public key. Then $$\{(1,h),(0,q)\}$$ generates a lattice. I've found it stated in the literature that $$Vol(\Lambda^q_h) = Vol(\mathcal{O}_K)^2q^n$$ (e.g. here), but how does the proof of this statement run? Or where can I find a proof?