All Questions
Tagged with lattice-crypto homomorphic-encryption
58 questions
1
vote
0
answers
52
views
Effect of small secret attacks on non homomorphic encryption schemes
The new paper by Albrecht describes a new attack on "unusually" small secrets that are used in homomorphic encryption schemes.
In the paper the talk about binary secrets or LWE Normal form i.e $\...
- 1,295
6
votes
2
answers
2k
views
What is the direct connection between LWE and GapSVP?
Learning with Errors Problem (LWE): Given a polynomial number of random noisy linear equations $b_i$ in the form of pairs
$$
(a_i, \quad b_i = \langle s, a_i \rangle + e_i)
$$
where $a_i \in \mathbb{...
- 101
1
vote
1
answer
86
views
Dimension of secret key vector tensor with itself?
In the algorithm FHE.KeyGen on page 18 of BGV, the dimension of the secret key $\textbf{s}_j$ is $n_j+1$. Why would the dimension of the long secret key $\textbf{s}_j' \leftarrow \textbf{s}_j \otimes \...
- 85
5
votes
1
answer
291
views
Noise of ciphertexts in LWE/RLWE based FHE
Often times $[\langle \textbf{c}, \textbf{s} \rangle]_q$ is referred to as the noise associated to the ciphertext $\textbf{c}$, and that decryption is correct when the norm of the noise is $< q/2$. ...
- 85
2
votes
1
answer
614
views
Bit decomposing a polynomial in BGV cryptosystem
I'm having trouble with the BitDecomp subroutine on page 9 of the BGV cryptosystem. I'm focusing on the RLWE instantiation so $R_q = \mathbb{Z}[x]/(x^d+1,q)$. I can't see how BitDecomp works for a ...
- 85
2
votes
2
answers
2k
views
GSW Homomorphic Encryption
In GSW homomorphic encryption scheme proposed here. The integers are over $Z_q$ where $q$ is a modulus parameter of the scheme. It is not clearly mentioned in paper if the ordinary representation of $...
- 315
3
votes
1
answer
312
views
proof of correctness Ring-LWE cryptosystem
I've been studying Ring-LWE based crytposystems such as the one in this paper, but I can't seem to find/come up with a proof of correctness for this particular scheme.
The encryption goes as follows:
...
- 31
7
votes
2
answers
2k
views
How to find the value of a vector modulo a basis in lattice-based cryptography
In Gentry's paper on fully homomorphic encryption using ideal lattices, he finds the values of vectors modulo a certain basis. For instance:
$\psi \leftarrow \psi' \mod B$
Taken from page 69 of ...
- 683