All Questions
Tagged with homomorphic-encryption lattice-crypto
58 questions
0
votes
0
answers
28
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 ...
0
votes
0
answers
21
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 ...
- 371
0
votes
0
answers
84
views
CKKS encoding. Why not just use fft
I am studying the ckks scheme from this blog post. In the vanilla encoding part we want to encode a complex vector of size N to a complex polynomial of degree N-1. This of course is possible if we ...
1
vote
0
answers
38
views
Understanding FHE bootstrapping: value of $q$ fed to lattice estimator
I am implementing OpenFHE. In the implementation I'm generating the modulus chain as shown in the example here. I am trying to run Lattice estimator for the same parameters in this example.
I wanted ...
- 19
0
votes
0
answers
26
views
Urgent help with R-LWE Parameters Choice
I am trying to understand CKKS bootstrap algorithm and wanted to understand how is p (plaintext modulo) and q (ciphertext modulo) related in determining the size of the modulus chain. Suppose my ring ...
- 19
-1
votes
1
answer
154
views
Urgent help with LWE Estimator
I am trying to estimate LWE parameters. I know of the GitHub library for LWE estimator but it has no instructions for installation and also provides no guidance for running simple examples. I have ...
- 19
1
vote
0
answers
77
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
0
votes
0
answers
24
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 (...
- 19
1
vote
1
answer
68
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 ...
- 49
2
votes
1
answer
70
views
Initial approximation in CKKS Bootstrapping
In this CKKS bootstrapping paper https://eprint.iacr.org/2018/153 the authors use a Taylor expansion to approximate the complex exponential function within a small range. More precisely, for the input ...
- 63
1
vote
0
answers
113
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 ...
- 111
1
vote
1
answer
124
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 ...
- 371
0
votes
0
answers
94
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 ...
- 371
1
vote
2
answers
166
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 ...
- 371
1
vote
1
answer
119
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+...
- 11
0
votes
1
answer
45
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 ...
- 371
0
votes
1
answer
94
views
Two problem about noise management of BFV
I have stuck in two problems when understanding the noise management of BFV scheme, and I don't have any idea about the two problem, help me please.
Problem 1:
In the ...
3
votes
1
answer
296
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
2
votes
1
answer
319
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
2
votes
1
answer
215
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 ...
- 425
2
votes
1
answer
599
views
How to choose the large noise when using noise flooding technique in FHE?
In LWE based multi party FHE schemes, the parties should choose a much larger noise when perform joint decryption. In this paper, the author just said that using noise flooding technique to avoid the ...
- 519
1
vote
0
answers
129
views
Why there is so high computational cost of multiplication in Microsoft Seal?
I was doing some Microsoft Seal testing on my macbook pro (i7) and got following results
Coefficient mod $q = 100$ bits and Polynomial degree $n= 8192$
Ciphertext-Plaintext multiplication takes 0.211 ...
- 251
1
vote
1
answer
427
views
What are limits of Modulus Switching in BFV encryption?
I want to understand the limits of modulus switching in BFV.
Lets assume $q$ represents ciphertext modulus and $t$ represents plaintext modulus.
$q$ is set to a $60$ bit value and $t$ is set to $20$ ...
- 251
2
votes
1
answer
283
views
How can CPA-secure LWE cryptosystem be broken by an active attacker?
The LWE-cryptosystem is only CPA-secure as for example stated in A Decade of Lattice-Based Cryptography. Consider the following system described there (Section 5.2)
The secret key is a uniform LWE ...
- 357
3
votes
1
answer
493
views
Why are the parameters (such as modulus and dimension) of homomorphic encryption so large?
Compared with the common lattice-based PQC schemes, the modulus $q$ and dimension $n$ of homomorphic encryption are so large. For example, in Kyber, $n=256, n \times k = \{512,768,1024\}$, $q = 12289$...
- 31
3
votes
1
answer
121
views
What are Practical Primitives based on Lattices, LWE and FHE?
Lattice-based cryptography is being used for several primitives and applications.
I know there are newer works for PIR, PSI, ORAM that have seen tremendous improvements due to FHE. In some cases, FHE ...
- 251
1
vote
0
answers
402
views
Key Switching Error in CKKS
I believe I am misunderstanding something about the bounds derived for the key switching error in CKKS. I will refer to the initial paper, but similar bounds have been derived in all variants I have ...
- 14.6k
3
votes
0
answers
275
views
The decryption correctness of RLWE based Encryption
I get stuck in the proof of decryption correctness in RLWE based Cryptosystem. To state where I am , let me show the full scheme first. The image is from chapter 3.2 of this paper.
And the decryption ...
- 75
2
votes
1
answer
460
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 ...
2
votes
0
answers
48
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 ...
- 519
2
votes
0
answers
157
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 ...
- 519
0
votes
0
answers
62
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 ...
- 1
0
votes
0
answers
72
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
0
votes
1
answer
244
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 ...
- 63
4
votes
1
answer
497
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 ...
- 775
5
votes
1
answer
124
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^...
- 1,614
0
votes
0
answers
76
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 ...
- 155
0
votes
1
answer
99
views
Is the "decapsulate" function from lattice based cryptography homomorphic?
Observing the code example from pqcrypto-kyber, is the decapsulate function $d$ homomorphic?
If $d(ct, sk_i) = ss_i$, is it true that $d(ct, \sum_i sk_i) = \sum_i ss_i$ ?
- 418
3
votes
1
answer
86
views
Security of somewhat homomorphic encryption via LSB encoding?
I'm reading this paper
https://eprint.iacr.org/2011/344.pdf
It says that
"The secret-key encryption scheme whose security is based on the LWE assumption is rather straightforward.
To encrypt a bit, $...
- 257
3
votes
1
answer
174
views
Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor
In section 7.2, page 18 in Chen-Nguyen paper regarding BKZ 2.0, they point out different Hermite factors related to Gentry-Halevi FHE.
More precisely, it is said that the critical Hermite factor for ...
- 41
2
votes
0
answers
186
views
Can binomial distribution be used to sample noise for Ring-LWE-based homomorphic encryption?
Homomorphic encryption schemes based on Ring-LWE need to sample the noise terms from a discrete probability distribution $\chi$ over the integers with support $[-B,B]$. For example, the Fan-...
- 438
3
votes
1
answer
136
views
How does the 'Flatten' function reduce the coefficients of a vector/matrix?
Seen here, at the bottom of page 5, $\operatorname{Flatten}(\vec{a})$ is defined as:
$\operatorname{Flatten}(\vec{a})=\operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1}(\vec{a}))$
For an n-...
- 93
1
vote
1
answer
433
views
What is the security model of the FHE system introduced in Fully Homomorphic Encryption Using Ideal Lattices?
How would one construct a security model to play against the adversary, and define the security of the overall scheme? This is in reference to the scheme introduced in "Fully Homomorphic Encryption ...
- 93
0
votes
1
answer
170
views
Refreshing Procedure in FHEW: membership test
I am facing an issue regarding the paper FHEW: Bootstrapping Homomorphic Encryption in less than a second. It concerns the MSBextract algorithm during the refresh procedure.
Especially, they ...
- 438
18
votes
2
answers
2k
views
Why is Approximate GCD a hard problem?
There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem.
The paper Algorithms for the Approximate ...
- 448
2
votes
1
answer
59
views
Dividing elements in $R_q$ by $z$ in Grag-Gentry-Halevi (GGH) Graded Encoding Scheme
I'm trying to understand the GGH graded encoding scheme, but something there leaves me very confused and I can not figure out how to explain it:
Let $R := \mathbb{Z}[X]/(X^n+1)$, where $n$ is a power ...
- 23
2
votes
1
answer
332
views
Is it secure using LWE-based cryptosystem under RLWE-based parameters?
I'm computer guy having trouble with cryptography.
I recently read the BGV Homomorphic encryption paper which was constructed under both LWE and RLWE assumptions.
I was implementing Threshold ...
- 509
5
votes
0
answers
491
views
ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc
While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
- 678
0
votes
0
answers
115
views
How is the security of a plaintext of Ring-LWE without an error term?
I think until public key $\mathsf{pk}=(b=-[as + e]_q,a) $ is broken, Ring-LWE is secure where $a$ is uniformaly random polynomial, $e$ is an error sampled from gaussian distribution with std=$\sigma$ ...
- 1,685
1
vote
1
answer
1k
views
What is the intuition of canonical-embedding in homomorphic encryption based on RingLWE?
In the cryptosystem based on Ring-LWE, the noise amount is measured by canonical-embedding norm.
What is the intuition behind canonical-embedding?
- 1,685