Questions tagged [lattice-crypto]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
60 views

Definition of Dual Lattice

1- Can someone explain why we have the definition of dual of a lattice like $\Lambda^*=\{\vec{v}\in span(\textbf{B}): \langle \vec{v},\vec{x} \rangle \in \mathbb{Z}, \forall \vec{x} \in \Lambda\} $. 2-...
user1035648's user avatar
2 votes
1 answer
77 views

Arithmetic in Cyclotomic Number Rings with Shoup's Number Theory Library (NTL)

I wish to do arithmetic on elements in an integer subring of a cyclotomic number field, i.e, in $\mathcal{O}_K = \mathbb{Z}(\zeta) \cong \mathbb{Z}[X] / <\phi_m(x)>$ where $\zeta$ is a root of ...
Rohit Khera's user avatar
1 vote
0 answers
69 views

Understanding Gentry's initial FHE construction based on ideal lattices

I am trying to understand the encryption procedure in Craig Gentry's initial construction for FHE described in Fully Homomorphic Encryption Using Ideal Lattices. Unfortunately after repeated attempts ...
Parham's user avatar
  • 111
6 votes
1 answer
265 views

NTRU Cryptosystem: Why "rotated" coefficients of key f work the same as f

In the NTRU cryptosystem, we can use a randomly generated polynomial f that is inversible under modulo p and q to encrypt and decrypt our plaintext. While studying this system, I attempted to ...
Ymi's user avatar
  • 175
1 vote
0 answers
25 views

Where do we put known bits of nonce when performing lattice attack on ECDSA?

I have read so many papers and posts about lattice attacks on ECDSA but none of them used an example of different MSB values for k but instead they all used fixed MSB. So here i am trying to ...
diviserbyzero's user avatar
0 votes
0 answers
34 views

Is BGV encryption using different secret keys indistinguishable?

Assume that the same message is encrypted using two different keys within the BGV encryption scheme. Can we assume that the resulting ciphertext are indistinguishable? I.e., given $c_1 = \text{Enc}(...
js wang's user avatar
  • 327
0 votes
0 answers
15 views

[error reducing techinique in lattice based commitment]

I am aware there are many techniques to reduce the error of lattice-based homomorphic encryption. But is there any technique to deal with lattice-based homomorphic commitment, e.g., More Efficient ...
js wang's user avatar
  • 327
1 vote
1 answer
124 views

Is there an efficient way to check if a lattice has a point with all non-zero components?

Given a basis $\{v_1,\dots,v_k\}$ for a $q$-ary lattice $L$ in ${\mathbb Z}_q^n$, is there an efficient (deterministic/randomized) way to find a point in $L$ with all non-zero components, or decide ...
LatticePoint's user avatar
1 vote
1 answer
124 views

True Lovàsz condition and definition of a LLL-reduced basis

I am studying the Shortest Vector Problem and I have some troubles understanding the actual Lovàsz condition used in the LLL algorithm. On the one hand, the original LLL article, the Springer book &...
Hurb27110582's user avatar
3 votes
1 answer
92 views

Differences between the theory and implementation of a lattice attack against ECDSA

I know the theory of lattice attacks against ECDSA from Minerva. So, as far as I can understand, the lattice that they build is $$ L_M = \begin{bmatrix} 2^ln & 0 & 0 & \cdots & 0 & ...
Hurb27110582's user avatar
0 votes
0 answers
34 views

Non-lattice NIST candidates affected by SVP problems

I would like to know if there are non-lattice based NIST submissions that are affected by a polynomial time algorithm to Shortest Vector Problem. Are there known reduction from (e.g.) code based ...
asdf's user avatar
  • 304
1 vote
1 answer
45 views

Why the refresh (modulus and key switching) is required in BGV after addition?

I am reading the BGV paper. On page 18, after addition, the protocol will also refresh (modulus and key switching), may I ask why is this required? It seems to me that I can still use the same secret ...
js wang's user avatar
  • 327
1 vote
0 answers
31 views

Is there a many-to-one reduction from GapSVP to GapCVP?

I was wondering if by now any poly-time Karp reduction between GapSVP and GapCVP (exact or approximate) exist. I know of the Cook reduction between these problems, but I couldn't find anything about ...
kerf's user avatar
  • 33
0 votes
0 answers
39 views

[About choosing params in BGV like ciphertexts]

I am new to lattice-based cryptography, so sorry that this question might seems stupid May I ask that how can I choose the BGV parameter of ciphertext with plain text in mod 128, and error in ...
js wang's user avatar
  • 327
1 vote
0 answers
73 views

Estimating BKZ block size in Kyber

In Section 5.2.1 of the Kyber documentation, it states that the BKZ block size of 413 was chosen using the tool from this paper, i.e., this tool. How was the block size derived from this? Currently, ...
Sam Jaques's user avatar
  • 1,095
0 votes
0 answers
34 views

Approximate-GCD problem in polynomials

I am trying to understand the two main hard problems that have been explored in the context of homomorphic encryption: Learning with Errors Problem (LWE) and the Approximate-GCD (AGCD) problem. I have ...
Anisha's user avatar
  • 11
1 vote
1 answer
40 views

How to set the variance of LWE when using the lwe estimator

based crypto And I would like to use the lwe estimator to calculate bound for ring LWE Found in this issue It seems to me I can set up parameters like params = LWE.Parameters(n=2^14, q=2^438, Xs = ...
js wang's user avatar
  • 327
1 vote
2 answers
112 views

About multiply by constant of LWE

I am new to lattice-based cryptography May I ask that for a lattice-based encryption $$enc(m) = A^{T}R+m \bmod q$$ If I set the $q$ to be able to decrypt to $m$ (and suppose the bound of $q$ is tight ...
js wang's user avatar
  • 327
2 votes
1 answer
79 views

in NTRU, can g be recovered given f and h?

The NTRU key generation involves polynomials and their arithmetic in polynomial rings, which is a bit different from arithmetic in modular integers. In the NTRU cryptosystem, the public key $h$ is ...
Tobsec's user avatar
  • 23
0 votes
0 answers
35 views

question for lemma 4 of the BGV paper

I would like to ask a question that arose when reading the proof of lemma 4 on page 10 of this BGV paper: The assumption is: And the inequality: So it seems that $$ \sum_{j=1}^{n} \parallel c'[j]-(p/...
js wang's user avatar
  • 327
1 vote
0 answers
51 views

Can lattice attack work MSB or LSB are unkown but 16 bytes of private key are known?

I have been reading about lattice attack on ECDSA when partial bits of nonce are known for amount of signatures, So i went through some source code trying to understand how it works. First of all, ...
Alexio puk2sefu's user avatar
8 votes
2 answers
2k views

Is lattice encryption susceptible to Grover's algorithm?

So Grover's algorithm, also known as the quantum search algorithm, can find an entry, with a high probability, in an unstructured database. Well can't we consider the basis of a lattice problem an ...
Steve Mucci's user avatar
0 votes
0 answers
38 views

What are the implications for the proof when we substitute matrix multiplication with a bitwise XOR operation in Definition 5.1 (LWE degree-k PRF)?

In the paper located at https://eprint.iacr.org/2011/401.pdf, suppose we replace matrix multiplication with bitwise XOR operations in Definition 5.1 to create an LWE degree-k PRF. I'm seeking ...
DP2040's user avatar
  • 63
1 vote
1 answer
88 views

Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
bd55's user avatar
  • 33
2 votes
1 answer
84 views

Computing the intersection of two lattices

Given two lattices $L_1$ and $L_2$ represented by bases $B_1$ and $B_2$, is there an efficient algorithm to compute $L_1\cap L_2$? I can show, I think, that if $\gcd(\det(B_1),\det(B_2))=1$, then $...
Sam Jaques's user avatar
  • 1,095
0 votes
1 answer
65 views

Discrete Gaussian distribution on a lattice vs. the periodic Gaussian function on a lattice

Gaussian distribution on lattices generally seems esoteric (at least for me, for now). My question is: Does Gaussian distribution on a lattice mean to add a Gaussian noise on a single point of a ...
user1035648's user avatar
0 votes
0 answers
61 views

Sagemath help: Introduction to Lattices

Hi im doing a problem from the Chapter Lightweight Introduction to Lattices in "Learning and Experiencing Cryptography with CrypTool and SageMath" I'm curious if my implementation is wrong ...
mandoo's user avatar
  • 1
1 vote
2 answers
50 views

[Questions about a proof in the prelim of paper "Lattice-Based Zero-Knowledge Proofs and Applications"]

May I ask that in section 2.7 challenge space in the paper Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General What is rot(c), why does rot(c) $\in Z^{d*d}$, and ...
js wang's user avatar
  • 327
2 votes
1 answer
78 views

$\epsilon$ parameter choice in lattice-based schemes

I am trying to implement Pei10 and BB13, but I am confused about what concrete parameters to use. In Pei10, Algorithm 1 takes a rounding parameter $r = \omega(\sqrt{\log n})$ as parameter, but it does ...
Gareth Ma's user avatar
  • 350
1 vote
0 answers
35 views

[About parameters effect LWE and SIS to be computation or perfect secure]

Hello I am new to lattice cryptography I am reading the paper More Efficient Commitments from Structured Lattice Assumptions They define bound B in page 3 Then In figure 1 in page 9 Can ...
js wang's user avatar
  • 327
2 votes
1 answer
97 views

Question about the description from ring SIS to SIS in the survey paper: A Decade of Lattice Cryptography

I am currently reading "A Decade of Lattice Cryptography" At page 30, section 4.3.2, it descrip left multiplication by any fixed ring element a It mention something about curcilant matrix ...
js wang's user avatar
  • 327
3 votes
1 answer
175 views

Kyber-CCA-KEM - Deterministic implicit rejection

In Kyber-CCA-KEM, there's a step in the Fujisaki-Okamoto transformation, where decryption failure results in a random shared secret returned from the decapsulation call. I have a C language project ...
DannyNiu's user avatar
  • 9,001
0 votes
0 answers
29 views

The asymptotic form of Hermite's constant in lattice

The are some linearly upper bounds on Hermite's constant $\gamma_d$, such as $\gamma_d \leq 2d/3$, $\gamma_d \leq d/4+1$. So we can claim that $\gamma_d=O(d)$. There is also a rather tight ...
kangli's user avatar
  • 65
1 vote
0 answers
67 views

Literature on (concrete) hardness of Short Integer Solution (SIS)

I am interested in what the state of the art results on the hardness of the Short Integer Solution (SIS) instances are. The one I am the most familiar with (and the most discussed) is to use lattice ...
Gareth Ma's user avatar
  • 350
1 vote
1 answer
101 views

learning with errors

If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
user479610's user avatar
1 vote
1 answer
67 views

Can you instantiate Ring-LWE with coefficients from a prime-power field?

Generally, we instantiate Ring-LWE with the polynomial ring $R = \mathbb{F}_q\ /\ (X^N+1)$ for prime $q$ and some power-of-two $N$. Can we instead do Ring-LWE over the ring $R = \mathbb{F}_q\ /\ (X^N+...
S. M.'s user avatar
  • 11
2 votes
1 answer
136 views

Why use small error vectors in LWE instead of big ones?

In LWE systems, why is it recommended to add only small error vectors to the system of equations and not big error vectors? Can someone come up with an example?
user479610's user avatar
1 vote
0 answers
57 views

Misuse Attacks on Lattice Crypto

I've been reading "Misuse Attacks on Post-Quantum Cryptosystems" (https://eprint.iacr.org/2019/525). In what scenarios are the attacks described in the paper applicable? Is it specifically ...
Lev Knoblock's user avatar
4 votes
2 answers
114 views

LWE and distributions

In LWE, the error term $e$ is "classically" obtained from the discrete normal distribution. Why is it so often found that this distribution is used? Are there other possibilities for ...
Zpeed78's user avatar
  • 95
0 votes
0 answers
45 views

Does randomization make a big difference in the output of the BKZ algorithm?

We all know that block Korkine-Zolotarev (BKZ) algorithm is essentially a deterministic lattice reduction algorithm. However, in the actual implementation, the BKZ algorithm contains some ...
constantine's user avatar
2 votes
1 answer
107 views

Trapdoor Quality for Lattice Crypto

In these two papers the authors mention the "quality" of a trapdoor [GPV] https://eprint.iacr.org/2007/432 [MP] https://eprint.iacr.org/2011/501 But the best detail on this matter I could ...
Cristian Baeza's user avatar
1 vote
1 answer
92 views

Matrix multiplication circuit

I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector ...
Mjf T's user avatar
  • 21
2 votes
3 answers
275 views

Why Module-LWE and not Ring-LWE?

I am trying to understand the NIST-submissions for post-quantum cryptography a bit better, and I noticed that the submissions from the CRYSTALS-family in particular is based on Module-LWE. I ...
user110127's user avatar
1 vote
1 answer
61 views

Sigma parameter from Trapdoors for Lattices

In the document Trapdoors for Lattices, section 5.4 Gaussian Sampling, they introduce the parameter $\sqrt{\Sigma_{\bf G}}$, which is related to the lattice $\Lambda^\perp(\bf G)$. They use it as a ...
Cristian Baeza's user avatar
0 votes
1 answer
48 views

Finite index quotient group, lattice crypto

A $m$-dimentional full-rank integer lattice $\Lambda\in\mathbb{Z}^{m}$ can be defined as the set of all integer linear combinations of $m$ linearly independent over $\mathbb{R}$ basis vectors $\textbf{...
user1035648's user avatar
1 vote
1 answer
102 views

Post-quantum secure trapdoor function

I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.
Mjf T's user avatar
  • 21
3 votes
1 answer
197 views

KYBER.CPAPKE: IND-CCA Security of Lyubashevsky, Peikert, Regev (LPR) Encryption

The NIST Kyber KEM spec. defines an encryption scheme, KYBER.CPAPKE, that's a variant of the so called Lyubashevsky, Peikert, Regev ("LPR") encryption scheme [1]. While LPR encryption is ...
Rohit Khera's user avatar
0 votes
1 answer
42 views

About learning with error rings with only constant coefficient

I am new to RLWE, would like to ask whether what I am thinking make sense Suppose I have a message e.g.: x=5 And I have a lattice based encryption scheme, e.g.: BGV could I encrypt x with BGV by ...
js wang's user avatar
  • 327
1 vote
1 answer
86 views

How does big Galois groups yield better security in NTRU Prime?

I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people. Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
faust's user avatar
  • 13
2 votes
1 answer
96 views

LLL on Knapsack-eque problem

Given integers $s_1, \dots , s_n$ and target integer $t$, I'm trying to find small integer coefficients $x_1, \dots , x_n$ such that: $$ t \approx x_1 s_1 + \dots +x_ns_n $$ Taking inspiration from ...
user348382's user avatar

1
2 3 4 5
11