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
0answers
17 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
29 views

Does the error distribution in LWE is 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
72 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
57 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
672 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
39 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
51 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
101 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
76 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
152 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 ...
0
votes
1answer
65 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
38 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
66 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
18 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
35 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
81 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
30 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
48 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
35 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
44 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
177 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
74 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
52 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
116 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
33 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
60 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
44 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
33 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
40 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
61 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
87 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 ...
0
votes
0answers
27 views

How GGH/HNF public key cryptosystem encryption process works

I'm reading paper Lattice based cryptography which at section 5 page 14 it describes GGH\HNF scheme that i can not quite get it and i need help. The private key is a “good” lattice basis $B$. ...
1
vote
0answers
37 views

Attacks on LWE when q is a power of 2

I am working on an LWE instance where q is a power of 2 and I'm wondering if there is any literature about attacks in this context, especially if there are any attacks which work significantly better. ...
0
votes
0answers
32 views

Short Integer Solution Problem with ||z||<=B

Why following constraints on $||z||$ are required $||z||<=B, B<q$
1
vote
3answers
242 views

I need a pathway for studying Lattice-Based Cryptography

I realize that I need a study pathway for post-quantum cryptography. I started to study post-quantum crypto by reading NIST PQC 3rd-round submissions of the lattice-based schemes (let's start with the ...
2
votes
1answer
72 views

The equivalence of SIS and ISIS(Inhomogeneous SIS)

I would like to know whether these two problems are equivalent or not, namely: $SIS_\alpha$: Given $A \in \mathbb{Z}_q^{n\times m}$ find $ e \in \mathbb{Z}_q^{m}$ such that $ Ae = 0$ and and $\|e\| \...
1
vote
0answers
29 views

How to prove to recipient that we are using public parameters correctly in lattice IBE

Many lattice IBE scheme follow the scheme outlined in ABB10. In ABB10, the ciphertext is $c_0 = u^\top s + x$, where $u$ is a public parameter. (No consider message here.) I want to ask: Is it ...
1
vote
0answers
61 views

Solving RLWE modulo a prime ideal

Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
0
votes
0answers
28 views

Is there decisional version of module-SIS problem?

We have a challenger who computes and gives the adversary the following: random matrix A sampled from the ring $R^{k \times l}_q$ random vector b from the ring $R^{l}_q$ random vector x from the ring ...
0
votes
0answers
25 views

How solving apprCVP solves NTRU key recovery problem?

I have studied the security analysis of NTRU PKC. It is known that if $(f, g)$ is the pair of private keys, which are ternary polynomials, then $$\|(f, g)\|\approx \sqrt{4d}$$ where $f, g$ have d ...
2
votes
0answers
71 views

How to use Rényi divergence for noise flooding

Let $\chi_\sigma$ be a discrete (or continuous) Gaussian distribution with standard deviation $\sigma$. Then, it is known that for $y \in \mathbb{Z}$, a statistical distance between $\chi$ and $\chi + ...
3
votes
0answers
63 views

Gram-Schmidt coefficients in LLL algorithm

To my understanding the LLL lattice reduction algorithm starts with a set of integer vectors $\{b_1, \dots, b_2\}$, which span a lattice, and tries to generate a new basis of shorter vectors of the ...
1
vote
0answers
29 views

Artificial abort in Adaptively-secure Lattice IBE in [ABB10]

I have read the paper [ABB10] several times but I still cannot understand thoroughly the "artificial abort" in the security proof of the adaptively-secure IBE in the paper. So my questions ...
0
votes
1answer
74 views

CKKS security estimation for Palisade

My question is rather practical and specific. I am trying to setup an efficient CKKS scheme in Palisade. To this end, the automatic choice for secure parameters has to be turned off and I rely on the ...
2
votes
1answer
70 views

Rounding function used in Saber Key Exchange

In Saber: Module-LWR based key exchange, the authors use a rounding function called $\textit{bits}$, defined (in page 3) as follows: $bits(x, i, j)$, with $j \leq i$, gives $j$ consecutive bits of a ...
3
votes
1answer
120 views

Famous ideal lattices

I am wondering if there exist some special rings $R$ that gives us, under the canonical embedding, some special lattices, like the root lattices, Barnes-Wall lattices, Leech lattices, ... In more ...
8
votes
1answer
428 views

NewHope and NIST's Post-quantum standardization

Where can I find NIST's reasoning to eliminate NewHope from the 3rd round of the post-quantum competition? I see all the lattice KEMs finalists are based on modules. Is being a ring-based KEM ...
2
votes
1answer
153 views

Are all homomorphic encryption schemes based on latticed-based schemes?

PALISADE offers a pool of Homomorphic Encryption schemes and it is stated that "PALISADE is a general lattice cryptography library ...". My question is rather simple: are all homomorphic ...
3
votes
1answer
128 views

Lattice reduction question regarding the capability of LLL and BKZ

I've been reading How to estimate the hardness of SIS instances? and following some of its sources, and I want to confirm a few things. LLL algorithm runs in polynomial time, but isn't capable of ...
5
votes
2answers
217 views

MLWE (and RLWE) to LWE reductions proof

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?

1
2 3 4 5
7