Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
2
votes
0answers
93 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 ...
2
votes
1answer
74 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
37 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
76 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
64 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
30 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
50 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
45 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
60 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
47 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
65 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
53 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
56 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
31 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
76 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
71 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
85 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
39 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
45 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
34 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
72 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
86 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
72 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
700 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
50 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
59 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
128 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
80 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
169 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 ...
1
vote
1answer
103 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
47 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
72 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
21 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
38 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 ...
2
votes
1answer
103 views

Understanding Unique-SVP and Kannan's Embedding

I am trying to understand the Kannan embedding technique. But I am confused about the formation of the B' and the finding of the short vector inside that basis. How does this basis matrix in the ...
2
votes
0answers
34 views

Why could the error term be sampled coefficient wise?

In SEAL homomorphic encryption library, it implements the BFV and CKKS. We know the error $e\in R_q$ which is a Guassian distribution. When sampling an error term $e = \sum_{i=0}^{n-1} e_ix^i$, it ...
0
votes
0answers
50 views

Lattice based cryptography: How do negative coefficients in $Z_q[x]/(X^n+1)$ work? [duplicate]

I saw that in lattice-based cryptography schemes, for example Dilithium, coefficients in $Z_q$ are allowed to be negative. For example, in Dilithium the secret key is $s_1 \in R_q^{k \times l}$, where ...
0
votes
0answers
39 views

Why are the fully homomorphic encryption algorithms the commitment?

Is there some references about the commitment scheme based on FHE ? Why could the BFV, CKKS, BGV algorithm be convert to commitment? How ?
2
votes
0answers
52 views

How does the rejection sampling lemma work in the proof of HVZK?

In this protocol, Q1: how does the commitment work? What if the prover sends $\textbf{t}$ directly, and then sends $s_m,s_r,s_{\textbf{e}}$? Q2: How does the rejection sampling lemma work? refer to ...
6
votes
2answers
240 views

LWE: Round a continuous Gaussian to a true Discrete Gaussian

Short version: how is it possible to round a continuous Gaussian into a true discrete Gaussian (usually denoted $\mathcal{D}_{\mathbb{Z},\alpha q}$)? The goal is to obtain a reduction from continuous ...
3
votes
1answer
89 views

What is the largest parameter broken for NTRU?

The original secure parameters for NTRU shown below are from the original HPS98 paper. This is vastly different from the current secure suggested parameters in the NIST PQC round 3 submission. ...
2
votes
0answers
57 views

Why should the smudge noise be used?

Consider a threshold FHE scheme based on RLWE like this: Refer to this paper $\textbf{Initialization:}$ Every party generates his own secret key $s_i$, then uses the common polynomial $a$ to generate ...
4
votes
1answer
131 views

LWE with identity sub-matrix and reused sampled from [MP12]: why is it secure?

I studied this paper a while ago, but now I'm confused by the paper Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller by Micciancio and Peikert. Page 24 and 25, they present an algorithm that ...
0
votes
0answers
40 views

Is the BFV homomorphic encryption scheme a commitment scheme?

The BFV scheme can be described as: Public Key: $(p_0, p_1)$ To encrypt a plaintext $m$, the ciphertext is : $(c_0, c_1) , c_0= up_0+\Delta m + e_0, c_1=up_1 + e_1$
2
votes
1answer
78 views

Computational LWE-Trapdoor without tag

In the paper Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller, Micciancio and Peikert mention that it is possible to save an additive $n$ term in the dimension $\bar{m}$ in paragraph $\...
0
votes
0answers
52 views

Why is the proof on the commitment correct?

In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$...
0
votes
0answers
39 views

GSW and homomorphic addition on integers

Is it possible to use the GSW scheme (Gentry, Sahai, Waters) also on integer values and not just single bits? If not, are there any schemes that support integer arithmetic with the same nice property ...
0
votes
0answers
44 views

GSW13 scheme and integer arithmetic

I'm new to lattice-based cryptography and have trouble understanding if the GSW13 (Gentry, Sahai, Waters) scheme works only on single bits. But is it also possible to encrypt integers with this scheme ...
1
vote
1answer
67 views

Algebraic Variants of NTRU

There are a large number of algebraic NTRU variants: for example, in some (such as ETRU), the underlying ring has been changed to the ring of integers of a certain number field; there is GR-NTRU, ...
3
votes
1answer
104 views

Significance of parameter q in NTRU lattice attack

In NTRU (N,p,q,d), N is usually chosen to be prime and q be a power of 2. Why is it that if I increase the parameter q, the probability of finding a key or spurious key that can decrypt the message is ...

1
2 3 4 5
8