# Questions tagged [lattice-crypto]

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

614 questions
Filter by
Sorted by
Tagged with
29 views

### Smaller module ranks of MLWE imply more algebraic structure?

In CRYSTALS-Kyber, they mentioned that the module rank $k$ should not be too small, they argued "having a smaller $k$ implies more algebraic structure, making the scheme potentially susceptible ...
• 75
305 views

1 vote
29 views

### What is the difference between PLWE (Polynomial Learning with Errors) and RLWE (Ring Learning with Errors)？ [closed]

Recently, I have been studying lattice-related concepts, and I want to understand the differences between PLWE and RLWE, such as how their security compares, as well as their structure and value ...
• 11
23 views

### Issue building RLWE based program

I've successfully built a LWE based program now moving onto building a RLWE based python program using: https://blog.openmined.org/build-an-homomorphic-encryption-scheme-from-scratch-with-python/ as a ...
13 views

### Tutorial of lattice estimator to compute a specific function with BGV

I recently try to go into lattice estimator https://github.com/malb/lattice-estimator I did find the document of it, but unfortunately, can not follow. May I ask how to run the lattice estimator to ...
• 361
77 views

### About the notion of "full rank" in lattices

I'm a newer to the lattice theory, so there is a basic notion about "full rank" confusing me. In some papers focusing on the lattice theory, they always use the full rank lattice (the number ...
• 434
57 views

### How do lattice based LWE protocols match their keys after generating them?

I am trying to implement a cryptographic protocol based on the following paper explaining the creation of the Swoosh lattice-based NIKE. They also provide a Rust and Jasmine implementation which I ...
54 views

• 520
181 views

### Trapdoor for SIS

I am new to lattice cryptography. May I ask why, if one has a trapdoor for SIS, i.e., can compute a short $x$ that satisfies $Ax=0$, then one can have a trapdoor for $Ax_{2}=y$? TIA
• 361
1 vote
61 views

### Difference between TFHE and CKKS?

What are the differences in parameters while implementing CKKS vs TFHE? For example modulus size, ring dimensions, bit security. Any pointers to literature would be appreciated
19 views

### Is there any bound on the size of ring dimension for Torus FHE?

I see that all implementations of TFHE in opensource supports 2^10 to 2^12 size of ring dimensions. Is there any specific reason (crypto) behind choosing the value or can we choose higher dimensions (...
1 vote
71 views

### Reject sampling of lattice ZKP, why need factor of M

I am watching the video https://www.youtube.com/live/N5nKGtugxYY?si=ejLqW8Pk0jD9lVMn&t=2098 Or particularly this slide: May I ask why does the reject sampling output by $f(x)/g(x)*M$ probability? ...
• 361
1 vote
55 views

### Decryption of LWE-based Inner-Product Fuctional Encryption of Agrawal-Libert-Stehle Crypto 2016

In below image, we have LWE-based inner-product functional encryption for short integers [ALS'Crypto2016]. Is the encryption correct? Why do they get $\mu\in\{\color{red}{-K+1},\ldots,0,K+1\}$? When ...
• 520
1 vote
64 views

### lattice RLWE encryption and decryption process

I am here trying to solve an issue that I face a lot during solving RLWE. The issue is that I am not able to retrieve the original message after the decryption process. I use the following encryption ...
• 33
1 vote
98 views

### ECDSA biased nonce with biased middle bits

The paper "Biased nonce sense" (https://eprint.iacr.org/2019/023.pdf) covers key recovery for MSB and LSB, the latter case being handled by doing modular inverse of 2 to the power of the ...
• 11
1 vote
56 views

### Question of section 1.3 Intuition for Aborting in "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures"

When I'm reading this paper "Fiat-Shamir With Aborts: Applications to Lattice and Factoring-Based Signatures" by Lyubashevsky. I have trouble understanding section 1.3 Intuition for Aborting....
• 15
1 vote
110 views

The general construction of a LWE-based PKE looks like the following: KeyGen : Secret vector, sk :$s \leftarrow \chi_s^m$ Public Key, pk: ($A \leftarrow \mathbb{Z}_q^{m \times m}, t = As + e)$ where $... 3 votes 1 answer 38 views ### How to determine approximate factor (i.e. modulus-to-(bound of)noise ratio) of LWE in advaned primitives is sub-exponential or polynomial? In advanced primitives like circuit (policy) ABE [BGG+'Eurocrypt2014] or IPFE [ACGU'Asiacrypt2020, appedix A] based on lattices, parameters setting is quite puzzling and vague (for me). (Parameter ... • 520 1 vote 1 answer 60 views ### Literature on Batching in FHE From what I understand, the folklore way to batch Ring-LWE style cipher texts is to use the Chinese remainder theorem. I am wondering if there are any different approaches/optimizations to this style ... • 27 2 votes 0 answers 116 views ### Can this problem reduce to the SIS problem or LWE problem? The description of the graceless problem is as below. Given a full rank square matrix$A=(R\cdot S+E)\in\mathbb{Z}_q^{n\times n}$,where:$q>2^\lambda$is a prime;$R\leftarrow\mathbb{Z}_q^{n\times ...
• 434
45 views

What would be the analogue of the gadget matrix in the ring setting? Would it be the same matrix? Do the trapdoor algorithms work exactly the same way? Thanks
• 27
78 views

### Questions about SIS hard problem

The definition of $\mathrm{SIS}_{q,n,m,\beta}$ problem is as below. Let $A\in\mathbb{Z}_q^{n\times m}$ be an $n\times m$ matrix with entries in $\mathbb{Z}_q$ that consists of $m$ uniformly random ...
• 434
202 views

### Shortest Vector Problem as Dihedral Hidden Subgroup Problem

I’m a mathematician trying to get into cryptography. I have a somewhat silly question, but I can’t seem to find a proper answer anywhere. I am interested in whether or not there is a way to directly ...
• 101
1 vote
119 views

### Math of Hint usage in Dilithium

For Dilithium, I understand that $$\text{HighBits}(\mathbf{Ay}) = \text{HighBits}(\mathbf{Ay} - c\mathbf{s_2}) = \text{HighBits}(A_z - c\mathbf{t})$$ The first term of the equation is performed on the ...
• 81
689 views

### Is NTRU broken?

Today a new paper appeared on ePrint, "Improved Provable Reduction of NTRU and Hypercubic Lattices". It claims that: this is the first provable result showing that breaking NTRU lattices ...
• 880