New answers tagged

1

Bruteforce appears to work well enough. The following Sage script finds an instance quickly: from sage.libs.fplll.fplll import FP_LLL from sage.libs.fplll.fplll import gen_uniform n = 5 # dimension q = 16 # size of matrix entries while True: M = gen_uniform(n, n, q) L = M.LLL(delta=0.999) S = FP_LLL(L).shortest_vector(algorithm='proved') ...


1

I think your proof of correctness may be hampered by the fact that you are setting the ciphertext to $(c_0, c_1) = (a, as + 2e + m)$ when in fact the paper you cite sets the ciphertext to $(c_0, c_1) = (as + 2e + m, -a)$. You correctly state that decryption is then computed as $c_0 + c_1s \text{ (mod } 2)$. This reduces to $(as + 2e + m) + (-a)s \text{ (mod }...


1

I am a cryptographic researcher at Security Innovation, which acquired NTRU Cryptosystems. Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one? The most efficient attack (the terminology "best known attack" is often used here) is the hybrid attack of lattice reduction and meet-...


7

Thanks for the question! You are correct that there is a bug here. Indeed, the sentence "choose $\mathbf{b}_i$ s.t. $\ldots$" makes no sense: the LHS is in $H$, but the RHS may not be. Fortunately, there is a simple fix which guarantees $\mathbf{y}'_i \in H$. (This must have been what we intended in the first place, based on how the rest of the proof goes;...



Top 50 recent answers are included