Questions tagged [lattice-crypto]

Lattice-cryptography is the study and use of lattice problems applied to cryptography.

Filter by
Sorted by
Tagged with
0
votes
1answer
57 views

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.
1
vote
0answers
26 views

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 $...
3
votes
1answer
297 views

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 ...
0
votes
0answers
9 views

Lattice based cryptography as Ph.D [migrated]

I have experienced a little with lattice in my master thesis, but I didn't had time to get the perspectives about it nor any open problem, does lattice based cryptography has open problems or ...
0
votes
1answer
39 views

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 ...
0
votes
1answer
40 views

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 ...
21
votes
2answers
4k views

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 ...
0
votes
0answers
27 views

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 ...
3
votes
1answer
69 views

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 ...
0
votes
0answers
57 views

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{ ...
1
vote
1answer
35 views

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 ...
2
votes
2answers
47 views

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 ...
1
vote
0answers
42 views

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 ...
2
votes
2answers
161 views

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 ...
4
votes
1answer
126 views

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_\...
1
vote
0answers
38 views

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 \...
2
votes
0answers
158 views

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 ...
3
votes
1answer
99 views

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 ...
0
votes
0answers
46 views

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 ...
1
vote
1answer
108 views

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. ...
3
votes
1answer
83 views

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}$: $$...
0
votes
0answers
46 views

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?
2
votes
1answer
62 views

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. ...
2
votes
1answer
60 views

The error distribution in LWE

$\textbf{Continuous LWE}$ : $(\overrightarrow{a}, b)\in \mathbb{Z}_q^n\times \mathbb{T}$, where $\mathbb{T}=\mathbb{R}/\mathbb{Z}$, $b = \langle \overrightarrow{a},\overrightarrow{s}\rangle/q + e\mod ...
2
votes
0answers
65 views

Howgrave-Graham lattice attack on NTRU

I am lookin for a good example to illustrate this attack on NTRU using low parameters but I failed to do that, The attack consist to use LLL reduction on A basis of NTRU Lattice, let us use the column ...
1
vote
1answer
51 views

Euclidean norms do not need full rank lattices

There is a sentence in Micciancio's Lattice lectures that says when we bound the minimum distance of a lattice using the convex body theorem for norms other than the Euclidean norm we need to assume ...
4
votes
1answer
71 views

Is NTRU still hard if $G$ is set to 1?

I'm looking at the description of NTRUEncrypt given on page 21 of http://archive.dimacs.rutgers.edu/Workshops/Post-Quantum/Slides/Silverman.pdf and using its notation. So in NTRU there are always two ...
3
votes
0answers
76 views

Which parts of CRYSTALS-Kyber and CRYSTALS-Dilithium are compatible?

The papers CRYSTALS-Kyber and CRYSTALS-Dilithium both have been written by quite different authors. It seems that at least the key generation is very different from each other. CRYSTALS mainly seems ...
1
vote
1answer
64 views

Why does orthogonal basises makes it easier to solve SVP in lattices?

I've been looking through https://courses.maths.ox.ac.uk/node/view_material/12662 and it mentions that: Some bases make SVP easier: A “good” basis has shorter vector norms A “good” basis has nearly ...
1
vote
0answers
32 views

The Primal and Dual attack security estimates in Kyber round 3 specification

In Kyber round 3 specification, the table 4 gave the security estimates of Primal and Dual attack with respect to Kyber 512, 768 and 1024 (see the figure below). However, using the python script given ...
4
votes
0answers
82 views

How did Kyber's authors compute the error probability $\delta$?

I'm studying the specification of Kyber that was submitted to NIST PQC Round 3. However, I cannot figure out how they compute the error probability $\delta$ for Kyber 512, 768 and 1024. I have read ...
1
vote
1answer
80 views

Security of the Goldreich–Goldwasser– Halevi (GGH) Scheme

There is a statement in the article of "Public-Key Cryptosystems from Lattice Reduction Problems" that presents GGH encryption scheme: "The cryptanalytic problem underlying our scheme ...
3
votes
0answers
96 views

Is there a source(book, thesis, paper) that explains Lattice basis reduction algorithms (LLL, HKZ) and provides an in depth analysis of the same?

I want to give a slight background about me: I've Bachelors in Computer Engineering and I've been interested in Cryptography since my college days and have been following the field ever since. I'm ...
2
votes
1answer
43 views

Choosing rings for PLWE

In [ELOS15], the authors give an attack on RLWE, and claim that "the hardness of Ring-LWE is... dependent on special properties of the number field" chosen; whereas, responding to prior ...
0
votes
0answers
46 views

Gram-Schmidt upper triangular basis

I'm trying to understand the Gram-Schmidt Orthogonalization process. Below, there is an explanation that a lattice basis can be described by an upper triangular vector. It is often convenient to ...
0
votes
0answers
41 views

Why is noise growth from relinearisation ignored in the FV crypto scheme?

I'm going through the FV scheme and SEAL and there are a couple of things I'm not understanding with respect to noise growth of relinearisation. On page 8 they say to choose T so that the noise ...
0
votes
0answers
117 views

Is the error distribution in Learning with Errors (LWE), the discrete Gaussian distribution?

In $\mathbb{Z}$, the discrete Gaussian distribution is defined as $D_{Z,s}(x) = \frac{\rho_s(x)}{\rho_s(\mathbb{Z})}, x\in \mathbb{Z}$. In LWE, $(\overrightarrow{a}, b = \langle \overrightarrow{a}, \...
0
votes
1answer
90 views

Error Correcting Codes Post Quantum Finalists

I have been looking into error-correcting codes in lattice, I am specifically hoping to find some information on hardware implementations for the NIST PQ PKE/KEM finalists (Saber, CRYSTALS-Kyber, NTRU)...
3
votes
0answers
76 views

Coppersmith attack on NTRU and non-commutativity

In this paper, Coppersmith and Shamir used lattice reduction to attack NTRU. At the very end of the paper, they note that developing non-commutative variants of NTRU would be wise, in light of their ...
3
votes
3answers
738 views

Why do Problems for Post-Quantum algorithms have to be NP-Hard?

The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g. Solving quadratic equations over finite fields short lattice vectors and close lattice ...
1
vote
1answer
59 views

Is the discretization of the Guassian distribution on torus still a discrete Gaussian distribution?

Let $\rho_s(x) = e^{-\pi x^2/s^2}$ be the Gaussian measures, then the discrete Gaussian distribution on $\mathbb{Z}$ could be defined as $D_{\mathbb{Z},s}(x) = \rho_s(x)/\sum_{n\in \mathbb{Z}}\rho_s(n)...
2
votes
1answer
60 views

Error Check in Lattice PQC

I am by no means an expert in the PQC field and am just trying to self teach myself about it. I was hoping to look into error correcting in lattice. I want learn about error or fault detection as it ...
1
vote
1answer
142 views

How is R-LWE related to lattice cryptography and homomorphic encryption?

Can someone tie everything together for me? I'm interested in H.E and I have some background in AES, DES, RSA and the like. While reading around I stumbled on Shai Halevi's course on lattice ...
1
vote
0answers
82 views

References on lattice-based cryptography [duplicate]

I need earlier references (books, articles, etc) on lattice-based cryptography, and any advice will be helpful to me. I am reading Stinson & Paterson's Cryptography: theory and practice. Thanks in ...
1
vote
1answer
184 views

SVP algorithms and complexity

I took image from Simons Institute's presentation. Complexity classes of Approximate SVP problem according to approximation factors are given in the table. My question is, What is the meaning of blue ...
2
votes
1answer
132 views

Worst-Case hardness of lattice problems

I just started work on lattice-based cryptography and I could not understand the concept of worst-case to average-case reduction. We generally say, Average Case Hardness: Random instance of a problem ...
0
votes
0answers
63 views

Software package to create a basis of the q-ary lattice $\Lambda_q(A)$

Consider a matrix $A \in \mathbb{Z}_q^{m \times n}$ and its respective lattice $$\Lambda_q(A) = \{x \in \mathbb{Z}^m : \exists z \in \mathbb{Z}_q^n, x = Az \mod q\}$$ The basis for such a lattice is ...
2
votes
1answer
76 views

A function $H(x)$ is given. If there is an algorithm $B(H(x))$ that get part of $x$, is $H(x)$ a one-way function?

I came up with this question while I was reading this paper: Pilaram, Hossein, and Taraneh Eghlidos. "An efficient lattice based multi-stage secret sharing scheme." IEEE Transactions on ...
0
votes
0answers
22 views

What does the "scale invariant" mean in some FHE schemes?

In some paper about FHE, the term "scale invariant" often appears. What does it means?
0
votes
1answer
39 views

Trapdoor committement using ring lattices involving three parties

Assume there are three parties say A, B, C. A commits to a message $m$ say $c(m)$ and sends tuple $(m,c(m))$ to B. B has to prove to C that he possesses commitment $c(m)$. There is no interaction ...

1
2 3 4 5
8