Tag Info

9

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.

8

I work for Security Innovation, which owns the NTRU patents. All NTRU-related patents are freely usable under GPL 2.0 and 3.0 -- in other words, they should fit in with your license requirement as given above. If you have specific license requirements beyond GPL please let me know and we'll accommodate them if we can. There's an open-source C and Java ...

8

Grover's algorithm treats the function it is evaluating as a black box and finds, with high probability, an input to the black box such that it outputs a specified value in $O(N^{1/2})$ evaluations of the function. Since Grover's algorithm works on the function as a black box, your modification does not hinder Grover's algorithm at all in finding the ...

7

I see two problems with this idea. The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs). In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the ...

7

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 ...

7

Post-quantum crypto is a very young field and is still changing quite rapidly. If you just want a reading list to introduce you to the topics, I would recommend the March 2015 report released by the EU's PQCrypto Project, and the April 2016 report from NIST. As of today, here's an (incomplete) list of candidate algorithms for post-quantum cryptography ...

7

Actually, if RSA is being used in a deterministic way (and the public exponent $e$ is relatively small), someone could recover the value $N$. We know that $P^e = C \bmod N$; that's equivalent to $P^e - C = kN$ for some integer $k$; if $e$ is small, then Shor's algorithm might be able to factor $P^e - C$; allowing you to recover $N$. Alternatively, if you ...

6

Why is 128-bit encryption considered good enough for medium term security only? Because in the long term it is expected that mankind will be able to carry out $2^{128}$ operations because it's not physically as impossible as $2^{256}$ operations. Quantum computing or brute force attack? Assuming quantum computers work at a speed comparable to ...

6

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.

6

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP. ...

5

You could be able to reduce the space required for a meet-in-the-middle attack, if you follow a similar idea as the application of Grover's algorithm on collisions. Suppose you have two layers of $n$-bit encryption: Partition the inner keyspace into $2^{n/4}$ parts of size $2^{3n/4}$. For each partition generate the inner encryption table. Run Grover's on ...

5

How many qubits are required for breaking RSA 2048 and RSA 4096 in real-time with a quantum computer? Like the answer you linked to shows, about $\log(N^2) = 2 \log(N)$. So 4096 for 2048-bit RSA, double that for 4096-bit. This paper (pdf) has an algorithm using $2n+3$ qubits, where $n=\log N$. How many qubits are required to break Curve25519? ...

4

That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency? Not really; or at least, that's not an inefficiency we care about. A length of 1024 means, in this context, 1024 bits (or 128 bytes). This compares favorably to RSA (for which a key with a 1024 bit ciphertext has ...

4

The expression $c' = \lfloor w^{-i} c \rfloor$ is a slight abuse of notation. What it technically means is to interpret each coefficient of $c$ as real number, divide by $w^i$, round the result to the nearest integer, and then interpret it as an element of $\mathbb{Z}_q$ again. This is equivalent to expressing each $\mathbb{Z}_q$ coefficient of the ...

4

The best generic attack against a PRG (i.e. an attack that does not use any internal structure of a construction and hence works for any PRG) is exhaustive search for a seed. I think this was not done yet but it is very likely that the optimality of Grover's algorithm carries over to this setting. This would mean that for $n$ bit seeds, the best attack ...

4

If he gets the signature for the message 00000..00000, then the checksum will be $t_1 2^w$. For any other message, the checksum will be smaller, and hence the there will be at least one digit $i$ within the checksum for which the $c_i$ digit with value $v$ for the signed message will be larger than the corresponding digit for the new message. The attacker ...

4

What we traditionally call Elliptic Curve Cryptography (working in the group of points on an elliptic curve over a finite field) is vulnerable to an attack by a quantum computer running Shor's algorithm and is thus not considered a Quantum-Safe or Post Quantum Cryptographic algorithm. However there is an true Post Quantum Key Exchange algorithm which uses ...

4

Yes the Bernstein attack is applicable but the impact of the attack is reduced because the party generating the parameter is also going to be a legitimate participant of the key exchange. Here is why the attack does indeed apply. Consider a case where Bob and Alice wish to conduct a key exchange using the New Hope Lattice-Based Key Exchange. Bob will be ...

3

There is a variant of the Neiderreiter system by Courtois, Finiasz, and Sendrier found in their paper: "How to achieve a McEliece-based Digital Signature Scheme" from Asiacrypt 2001. The Wikipedia article on the Neiderreiter Cryptosystem provides a brief introduction to this signature. There is an element of trial and error in the signing process that is ...

3

The combination of Grover algorithm and man in the middle attack is the main subject of a paper (arXiv:1410.1434) published last year by Marc Kaplan (Full disclosure: Marc is a friend of mine.) In this paper beyond applying Grover to MITM to reduce the time needed to analyse double-encryption, he also looks at the time-space gain, which is different, and ...

3

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.

3

Douglas Stebila published: We demonstrate the practicality of post-quantum key exchange by constructing ciphersuites for the Transport Layer Security (TLS) protocol that provide key exchange based on the ring learning with errors (R-LWE) problem There is also a patch implementing it for OpenSSL 1.0.1f.

3

As @Raoul722 pointed out the polynomial should be irreducible. One should also add the fact that in the original Ring-LWE article security proofs hold by sampling the error with a spherical distribution and the poly $f=x^{2^n}+1$. In How (Not) to Instantiate Ring-LWE, from Invulnerability instantiations subsection it's specified that you could in fact ...

3

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') ...

3

Yes, these are public parameters of the system. Note that NTRU is not implemented exactly this way any more. The most up-to-date current spec is EESS#1, which can be obtained from https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf.

2

I do not believe that braid based cryptography is dead since new ways of applying braid groups to cryptography are currently being investigated and have recently been proposed. In fact, recently researchers have observed how braids could be used for reversible circuit obfuscation. A recent paper on braid-based obfuscation The 2014 paper, Partial-...

2

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.

2

It is easy to find preimages for the hash function you designed. Remember, to break the scheme it is enough to find any preimage. It is not necessary to find the one used to compute the image. Now, you got public integers $a,b,c,d,$ and $f,g$ as well as a modulo $M$. An $n$-th image is $$P(n) = a*x(n) + c*y(n) \mod M$$ $$Q(n) = b*x(n) + d*y(n) \mod M$$ ...

2

Random oracles are used in cryptographic proofs as a way to abstract away a complex function, making the analysis easier (ie "ignore the actual function, and model it as a random oracle instead"). In the paragraphs before the sentence you highlighted, they propose to measure the "complexity" of an equation / function by the degree of its multivariate ...

2

While there is a sub-exponential attack to compute isogenies on ORDINARY elliptic curves (the basis for the Rostovev and Stulbunov paper that you reference) there is not (yet at least) a sub-exponential attack to compute isogenies on SUPERSINGULAR elliptic curves. The cryptosystem proposed by DeFeo, Jao, and Plut back in 2011 is based on Supersingular ...

Only top voted, non community-wiki answers of a minimum length are eligible