Tag Info

New answers tagged


Also, the algorithm given in the mentioned paper has a complexity os $\tilde{O}(p^{\frac{1}{4}})$. The best known attack (As mentioned by de Feo, Jao and Plut) on the SSIKE is based on the claw finding problem (see below) and has a complexity of $\theta(p^{\frac{1}{6}})$. Very interesting paper btw ;): Claw finding algorithm using quantum walk


Sorry I will have to answer my own question. I received a mail from Luca De Feo a moment ago. "Nope, I discussed this at length with Jean-François Biasse, and we couldn't find a way to apply this kind of attack to SSIKE." I'll leave this question around for reference for the next person who wonders.


Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations. I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.


There should be plenty of them. Off the top of my head, I'm thinking of the provable secure version of NTRU by Stehlé and Steinfeld [1], which is IND-CPA secure. In this scheme, ciphertexts are of the form: \begin{equation} c = pk \cdot s + p\cdot e + \operatorname{encode}(m) \end{equation} where $s$ and $e$ are random polynomials, $p$ is a small prime, ...


Actually, most of the primitives that are currently believed to be secure FHE methods would appear to be quantum resistant; a partial list would include Craig Gentry's original scheme based on ideal lattices, BGV (based on ring-LWE), and this NTRU-based approach. All three are based on hard problems that are not susceptible to Shor's algorithm.


The statement a 15360-bit RSA key is the equivalent to a 256-bit symmetric key does not take into account quantum algorithms. In fact, it is based on a specific computation model. It is just based on the fact that there exist sub-exponential algorithms for factoring and therefore you need longer keys than when using symmetric-key crypto where it is ...

Top 50 recent answers are included