Questions tagged as ['lattice-crypto']

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

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

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?

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

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

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.

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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?