Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
4
votes
1answer
78 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
19 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
36 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
36 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
26 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
36 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
52 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
68 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
21 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
35 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
29 views

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

Why following constraints on $||z||$ are required $||z||<=B, B<q$
1
vote
3answers
204 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
54 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
26 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
54 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
18 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
21 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
66 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
62 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
23 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
55 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
0answers
45 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
109 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 ...
7
votes
1answer
408 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
138 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
103 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
174 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
vote
1answer
32 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
0
votes
1answer
48 views

Voronoi regions of lattices with dimensions $\leq 16$

Is there any idea about calculating the exact Voronoi regions of lattices with dimensions $\leq 16$? Thank you!
4
votes
1answer
55 views

Proving LWE inversion in Micciancio-Peikert-2012 lattice trapdoors

I'm looking through the lattice trapdoor construction in https://eprint.iacr.org/2011/501. To summarize, assume we have a matrix $G$ where, on input $b$, we can efficiently find $(s,e)$ such that $s^...
3
votes
2answers
451 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
1
vote
0answers
75 views

What are the prerequisites for understanding Lattice based Cryptography, LWE or RLWE based on SVP?

I'm new to Quantum Resistant Cryptography, so, I thought of diving into Lattice based crypto, LWE and ring LWE. I realise that the hard problem involving them is the "shortest vector problem"...
2
votes
1answer
56 views

Dual of a complex lattice

We know that for a real full-ranked lattice $\Lambda$, with real square matrix $\mathbf{B}$, the dual lattice $\Lambda^{\vee}$ has matrix $(\mathbf{B}^{-1})^T$. Now If we have a complex lattice with $...
8
votes
2answers
254 views

Error-correcting Code VS Lattice-based Crypto

I'm not an expert in PQ-crypto, but as I understand error-correcting code and lattice-based crypto, the cryptographic assumptions are very similar. The key difference for me is the nature of the noise....
1
vote
2answers
81 views

Verify that a point is inside a lattice

I am wondering if there's a polynomial time algorithm that, given a lattice $\Lambda$ with basis $\mathbf{B}$ and a point $x$ in space, it tells you whether $x$ is in $\Lambda$ or not!
3
votes
1answer
80 views

iO from Matrix Branching Programs

Recently I'm learning about constructing iO from Matrix Branching Programs via Multi-linear Maps (to be exact, [GGH+13] and [GGH15]). However, I have a small question that I couldn't figure out. It ...
1
vote
1answer
73 views

Solving modular matrix equations via Gaussian elimination or System of linear equations (SIS assumption?)

Suppose $S \in \mathbb{Z}_q^{m \times m}$, and the norm of $S$ is less than an upper-bound $\beta$. Additionally, $A_1, \cdots, A_k, C_1, \cdots, C_k \in \mathbb{Z}_q^{m \times n}$. Here, $k \geq m>...
1
vote
0answers
67 views

Code implementation of NTRU lattice attack

As mentioned here, BKZ is one way to break the NTRU lattice What is the most efficient attack on NTRU? I was wondering if there are any source codes which actually implemented this on the weaker NTRU ...
3
votes
0answers
51 views

It is possible to prove this in zero knowledge?

Let $\mathcal{R}_q = \mathbb{Z}_q/\langle x^n + 1 \rangle$, with $n$ a power of $2$. Suppose that we sample $\mathbf{r} \leftarrow \mathcal{R}_q^m$ uniformly at random with the property that $0 < ||...
4
votes
0answers
47 views

LWR parameter estimation

I am trying to estimate parameters for LWR $(n,q,p)$ instance using the LWE estimator. My $q,p$ are $283,256$-bit prime numbers and I am trying to find required $n$ for 128 bit security. For this, I ...
1
vote
0answers
47 views

Proof for, Vectors sampled from $D_{(L,r)}$ have Euclidean norm at most $r\sqrt{n}$ with a high probability

For any $n$-dimensional lattice $L$ and $r > 0$, a point sampled from $D_{L,r}$ has Euclidean norm at most $r\sqrt{n}$ except with probability at most $2^{-2n}$ (where $r$ refers to the standard ...
2
votes
2answers
69 views

LWE versus neural nets

It seems like that the construction of the LWE problem: $As + e = b$ resembles how neural nets work: $Ax + b = y$. In LWE, we are given the problem instance $A$, and the product with errors $b$ and ...
1
vote
0answers
84 views

Which are the most Promising Post-quantum Public Crypto Primitives in the Face of a Quantum Apocalypse?

I'm fairly new to the fundamentals of post-quantum cryptography. So, please forgive me for such a direct question. Searching Google opened up a whole lot of amazing ideas that are thought to be ...
2
votes
0answers
20 views

Probability that length of shortest nonzero vector is less than a number

Let $\Lambda\subset \mathbb{Z}^n$ be an $n-$ dimensional lattice with determinant $d$. We know that the probability that a uniformly random integer vector $x$ is a point in $\Lambda$ is given by $\...
0
votes
1answer
59 views

Why do we add error in the definition of LWE?

One of the various equivalent definitions of the LWE problem is the following: Let $n,q$ be integers ($q$ usually is a prime number), $\chi$ a discrete probability distribution over $\mathbb{Z}$ (...
2
votes
0answers
45 views

Why ideal lattices?

An ideal lattice is a lattice $\mathcal{L}(A)$ generated by a block matrix $A = \left[ A^{(1)} \mid \dots \mid A^{(m/n)} \right]$ whose blocks $A^{(i)}$ are constructed from a vector $a^{(i)}$ and a ...
2
votes
0answers
62 views

How to construct a set in which the elements in $\mathbb{Z}[x]/(x^n+1)$ and their differences are invertible and with coefficients in $\{-1,0,1\}$?

I know that in IACR - Better Zero-Knowledge Proofs for Lattice Encryption and Their Application to Group Signatures it constructs such a challenge set: {$ x^i $}. But the inverse of the difference of ...
0
votes
0answers
41 views

What is the code when looking at the LPN problem?

We are given the problem in this question. We know that we have to use the algorithm $A_D$ in order to get $e_i$. Our idea is that we construct a vector $l$ of $l_i$'s by getting $n$ samples from the $...
1
vote
0answers
37 views

Key-Privacy in Postquantum Public-key Encryption

is there any post-quantum public-key encryption that achieves "key-privacy" (IK-CPA, IK-CCA) as described in this paper? I saw one code-based public-key encryption construction, but I wonder if ...
0
votes
0answers
59 views

Hash chain based secret revealing using homorphic princples?

I have recently been looking into Homomorphic encryption and I am looking for a specific hash-based encryption/decryption scheme. I don't need a full implementation but I am not sure if what I want ...

1
2 3 4 5
7