# Questions tagged [lattice-crypto]

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

484 questions
Filter by
Sorted by
Tagged with
1 vote
33 views

### Why was A doubled in size

Why was the dimension of A doubled in kyber? LWE encryption uses a public matrix A of dimension K but kyber uses a double matrix A resulting in $A ^{ k * k * n }$ When deriving the results of the ...
130 views

### CRYSTALS-Dilithium - How do the supporting algorithms work?

I am studying the Dilithium signature from Ducas et al's CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. Wanting to understand how the supporting algorithms work together, I am trying ...
• 117
1 vote
21 views

### Hardness of LWE with Uniform Secrets and Error Distributions

I have seen various papers discussing the security of the Learning with Errors problem with very small uniform secrets and errors but I have not found any papers on the general LWE problem with ...
• 11
16 views

### Difference between Decryption-failure and Plaintext-checking oracles

I am reading this paper, which in the introduction, tells about two main types of key recovery SCAs : Reaction_type SCAs, which uses a decryption failure oracle Message-recovery-type SCAs, which uses ...
1 vote
33 views

### LWE Decryption: Generating errors for (c1, c2) that match binary message m

In the encryption process, the ciphertexts c1 and c2 are added to errors e1 and ...
32 views

### Learning with rounding: uniformity

Naively, when one applies rounding to a uniform random value one anticipates that the change is uniformly distributed. In lattice-based cryptography, is there a formal notion or proof of equivalence ...
• 18.2k
33 views

### Unable to retrieve the binary string using LWE and Lattice-based decryption

I am new to this encryption scheme, so I may not be exactly sure of its implementation. I have a list of (u, v) ciphertext pairs to decrypt, each of them are 1-bit. ...
1 vote
68 views

### LWE and Lattice-based cryptography: How to recover binary message $M$ from $(u, v)$ values?

I am given a set of $(u, v)$ values, matrix $A$, primary key vector, private key vector, error vector and prime $q$. I wanted to recover the binary value of each $(u, v)$ pairs using LWE decryption. ...
63 views

### Equivalence of lattice definitions

I have come across two supposedly identical definitions of lattices in the lattice crypto literature. There are mainly these two definitions of lattices, the first considers lattices as discrete ...
• 231
1 vote
40 views

### How & where is concepts of Good basis and bad basis used in Crystal kyber?

I've read the documentation of Crystal Kyber, but nowhere it is mentioned about good basis and bad basis. Please explain how and where is the good basis and bad basis is used in crystal kyber.
• 33
1 vote
84 views

### Are lattice-based cryptography and error-correcting codes mathematically unsound?

From Ronald de Wolf's The potential impact of quantum computers on society: The first is so-called post-quantum cryptography. This is classical cryptography, based on computational problems that are ...
36 views

### What is this parameter? in Lyubashevsky's ID-scheme

I am studying Lybashevsky's ID-scheme from the article Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures(https://www.iacr.org/archive/asiacrypt2009/59120596/59120596.pdf) ...
• 117
1 vote
34 views

### Public seed expansion for uniform reference strings

Many cryptographic protocols are parameterized by a uniformly random reference string (e.g. the commitment key for Pedersen commitments). Our goal is to publicly generate the random values of this ...
1 vote
81 views

### How "unorthogonal" can a LLL-reduced basis be?

I have been recently studying LLL-reduction. I get from the size condition and Lovasz condition that the basis are guaranteed to be somewhat orthogonal. But I couldn't figure out how orthogonal the ...
• 21
65 views

### The successive minima of a lattice

I am new to lattice theory. I hope(will be grateful) that one could explain to me this claim 7 in REGEV course(this claim appears in this file page 6 : https://cims.nyu.edu/~regev/teaching/...
• 31
1 vote
61 views

### Hardness of a modified version of NTRU

Let the modified NTRU be $h=f/g$ such that $f$ is not necessarily a short polynomial, is the NTRU problem still hard in this case?
• 376
86 views

### NTRUEncrypt proof that there are plenty of keys

In NTRU algorithm one is supposed generate a vector which is invertible as a polynomial in both $(\mathbb{Z}/p\mathbb{Z})[x]/(x^n-1)$ and $(\mathbb{Z}/q\mathbb{Z})[x]/(x^n-1)$. But is there a ...
98 views

### How to show additive subgroup of $R^n$ is not discrete? [closed]

Suppose we have the additive subgroup of reals generated by $\sqrt{3}$ and $\sqrt{5}$. How would you show you that this subgroup does not form a lattice?
129 views

### Hardness of LWE

I was reading "TFHE Deep Dive" from Ilaria Chillotti, and I am a bit confused over the sample given in 31:08 In the above toy sample, isn't it possible to directly eliminate noise by ...
• 51
99 views

### Which lattice-based encryption scheme/signatures is fundamental?

If I would like to focus on only one signature scheme, and only one encryption based on lattices in a pedagogical context (to introduce the concept of lattice-based crypto to people familiar with ...
• 2,523
84 views

### Avoid CKKS Bootstraping

CKKS is a levelled scheme, because the rescale $\lfloor\frac{x}{\Delta}\rceil$ operation requires truncating a modulus to be efficiently evaluated, and rescale is (usually) needed after every ...
• 51
162 views

### CRYSTALS-KYBER versus FrodoKEM, what makes each of them different than the other?

NIST's main recommendation for encryption/decryption mechanism is CRYSTALS-KYBER. Whereas, the BSI (German equivalent) chooses FrodoKEM. As far as my knowledge goes both these mechanisms use LWE ...
5k views

### Kyber and Dilithium explained to primary school students?

Kyber and Dilithium are post-quantum cryptographic designs, but the resources are hard to understand. Is it possible to explain those ciphers to children?
• 181
123 views

### ISIS problem in the case of $m=n$

The Inhomogeneous Short Integer Solution (ISIS) problem is as follows: given an integer $q$, a matrix $A\in \mathbb{Z}^{n\times m}_q$, a vector $b\in \mathbb{Z}^{n}_q$, and a real $\beta$, find an ...
• 376
83 views

• 171
248 views

### NTRUEncrypt fails on sedonion algebra

This question is a direct follow-up (hopefully - the last) of my previous one; please see it for full information. I would like to further generalise NTRU cryptosystem on higher-order algebras. ...
• 189
110 views

### NTRUEncrypt fails on quaternion algebra

This is a follow-up of my previous two questions (1 and 2), might be relevant to check them out first for a full context. I am trying to re-create results from this paper. The basic algorithm is ...
• 189
78 views

### "Shifting" a dual-Regev keypair away from a trapdoored instance

This question pertains to identity-based key encapsulation mechanisms (IB-KEMs). To recap the functionality: $\mathsf{KeyGen}(1^\lambda) \to (\mathsf{msk}, \mathsf{mpk})$ Generates the master keypair ...
• 124
108 views

### Why is the best way to solve LWE (and Cryptographic related Systems) with SVP (approx)?

Community, I'm new into lattice based cryptography, and I'm interested about the security of cryptography schemata like Kyber and why the focus of solving this problem lead into solving approx. SVP. ...
1 vote
79 views

### Choice of Polynomial Quotient Ring

In (lattice-based) cryptography, the quotient ring $\mathbb{Z}[X]/(X^n+1)$ where $n = 2^e$ is a power of 2 is used in various cryptographic schemes (e.g., CRYSTALS-Kyber). It is my understanding that ...
• 13
1 vote
53 views

### Good libraries for lattice-crypto [closed]

I'm searching good libraries to manipulate lattice tools to do cryptography. I'm mainly interested by C/C++. But I'm also interested if it is in python.
• 2,523
313 views

### Break Lattice-Based Cryptography with Variational Quantum Algorithm (only 25 k. Qbits for Kyber1024)?

I am currently writing a seminar paper on Kyber and other lattice-based methods. I was so excited about the lattice-based methods that I also currently searched quantum algorithms to solve the methods....
132 views

### Question about Theorem 2 in CRYSTALS-Kyber Paper

I have some questions about the Kyber paper, especially about Theorem 2 on page 6, which I would like to ask here. First of all I quote the following theorem from the paper and ask my questions ...
• 231
1 vote
26 views

### Why the output of G-lattice sampling is spherical in the paper GM18?

In the paper GM18, they say that the sampling algorithm, SampleG, is shown in Figure 2. It takes as input a modulus $q$, an integer variance $s$, a coset $u$ of $\Lambda^{\perp}(g^T )$, and outputs a ...
1 vote
124 views

### NTRUEncrypt fails on complex algebra

I am following the NTRUEncrypt cryptosystem as described on the wikipedia. I have implemented it in Sage Math engine (with small problems along the way, but in the end - succesfully resolved) and the ...
• 189
124 views

### Why does NTRUEncrypt fail on different values for large modulus?

I am trying to closely follow the algorithm here (keeping the same variable names) and reconstruct the cryptosystem in Sage Math engine. It seems to work on parameters ...
• 189
1 vote
54 views

### Decryption analysis for Regev's Public Key Cryptosystem

Regev's Public Key Cryptosystem is defined as follows: I want to proof the correctness. For this it must be shown that a 0 is decoded correctly and equally that a 1 is decoded correctly. I would ...
• 231
76 views

### Do ideal non-cyclotomic lattices provide better compression in lattice-based cryptography?

Let $f \in \mathbb{Z}[x]$ be an irreducible polynomial of degree $N$ and $q \in \mathbb{N}$. Consider the rings $R := \mathbb{Z}[x]/f$ and $R_q := R/q$. Obviously, an element of $R_q$ can be ...
124 views

### Question on the proof of correctness in CRYSTALS-Kyber

I am currently trying to follow the proof of correctness in the CRYSTALS-Kyber paper. The following is an excerpt of the proof: On the one hand, I am interested in how exactly one justifies/argues ...
• 231
185 views

### Compression and Decompression in CRYSTALS-Kyber

I am currently studying the Kyber Paper. I have a question about section 2.2 Compression and Decompression, but first I would like to quote the statement: Compression and Decompression. We now define ...
• 231
69 views

### How does the SWIFFT algorithm relate finding hash collisions to a lattice problem?

I've been messing around with lattice based cryptography and came across the SWIFFT algorithm, a provably secure cryptographic hash function which has a security proof stating that finding collisions ...
• 25
1 vote
100 views

### How are public and private keys generated and used for encryption and decryption in a lattice based cryptosystem?

I've recently become quite interested in lattice based cryptosystems, and I wish to understand them more deeply. I have only a rudimentary understanding of the shortest vector problem (SVP), and its ...
• 265
1 vote
63 views

### Basis matrix of NTRU lattice

In NTRUEncrypt, we choose polynomials $\mathbf f,\mathbf g$ (with suitably small coefficients) such that $\mathbf f$ admits inverses $\mathbf f_p, \mathbf f_q$ with respect to the moduli $p,q$. The ...
50 views

### How do lattice-based proofs with Reed-Solomon codes simultaneously avoid aborts and multiple repeats?

I'm trying to understand how lattice-based schemes with the Reed-Solomon proximity testing work and why the scheme in Bootle's et. al. Fig 3 has no aborts at all (nor big number of repetitions). TLDR:...
• 474
96 views

### Dense sphere packings and lattice-based cryptography

It is known that there are two popular applications of lattices: dense sphere packings and lattice-based cryptography. I didn't find any information on the Internet about possible interaction of these ...
55 views

### Lattice-based Signatures and Hashes

Although many different lattice-based signature schemes exist, Hash and Sign signatures schemes, like [GPV08], are prevalent. On the other hand, it is well known that collision-resistant hash ...
49 views

### Question about the definition of the CVP as an approximation variant

I have a question about the definition of the (Closest Vector Problem) CVP. In the literature you can find for example this definition of the approximation variant of CVP: $CVP_\gamma$, Search: Given ...
• 231
In MITM attacks against the NTRU cryptosystem, we exploit the fact that in the ring of truncated polynomials of degree $n-1$ it holds that $$fg=h\mod q$$ for our secret and public keys $f,h$. The ...