News for hackers. Stuff that matters.
Re:NSA announces plans for transitioning to quantum resistan... by biot on Saturday August 15, 2015 @07:49AM (#10065138)
Can anyone explain what makes an encryption algorithm quantum-resistant?
Re:NSA announces plans for transitioning to quantum resistan... by pbsd on Saturday August 15, 2015 @10:38AM (#10065476)
This is hard to answer because many quantum algorithms useful for cryptanalysis have probably not been discovered yet. See, for example, the debacle surrounding Soliloquoy [1], an algorithm that despite being based on the hardness of lattice reduction has a fast quantum algorithm.

Anyway, a quantum-resistant algorithm is usually meant to be one that resists the exponential speedup given by Shor's algorithm and its variants. In other words, a quantum-resistant algorithm can't be based on the hardness of integer factorization, discrete logarithms on any abelian group, class groups, and so on (i.e. all instances of the Abelian hidden subgroup problem).

The leading candidates for such hard problems are decoding a random linear code (McEliece), shortest/closest vector finding in a lattice (NTRU, GGH, [R]LWE, ...), multivariate equation system solving (HFE and friends), and in the specific case of digital signatures one-way functions (Merkle Tree signatures).

[1] http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Syste...

[deleted]
Re:NSA announces plans for transitioning to quantum resistan... by chucksmash on Saturday August 15, 2015 @08:54AM (#10065250)
Couple of corrections:

1) Public key cryptography relies on difficulty of factoring products of large primes.

2) Non-quantum computers can factor these numbers, it is just that the nature of the problem seems to require an expensive (non-polynomial to size of input) algorithm on classical computers. With quantum computers a polynomial time algorithm exists (Shor's algorithm).

Re:NSA announces plans for transitioning to quantum resistan... by lindig on Saturday August 15, 2015 @08:33AM (#10065216)
Prime numbers can't be factored.
Re:NSA announces plans for transitioning to quantum resistan... by wolfgke on Saturday August 15, 2015 @08:48AM (#10065237)
For every prime p, we have p = 1 * p (clearly a factoring of p, though a trivial one). So rather "Prime numbers can't be factored in a nontrivial way.",
Re:NSA announces plans for transitioning to quantum resistan... by noobie on Saturday August 15, 2015 @11:34AM (#10065635)
I'd go with "Prime numbers can't be prime-factored".
Re:NSA announces plans for transitioning to quantum resistan... by wolfgke on Saturday August 15, 2015 @02:14PM (#10066236)
Even if we ignore units (i.e. 1, -1 in the ring Z), the prime number is a factorization of itself (one factor).

Otherwise the famous theorem that any integer >= 1 can be factored uniquely (up to order of the factors) into prime numbers would not hold (it even holds for 1, since 1 is defined as the product of zero factors).

Re:NSA announces plans for transitioning to quantum resistan... by fredgrott on Saturday August 15, 2015 @11:57AM (#10065714)
not entirely true..

Prime number guesses cannot be fully determined as prime fast and easily...however WE CAN brute force guess big prime numbers easily..for example 1/4 to 15 RSA keys can be brute forced guessed..not full brute force break as you still have the session keys to brute force but you get the idea

Re:NSA announces plans for transitioning to quantum resistan... by _asummers on Saturday August 15, 2015 @12:05PM (#10065731)
Prime numbers, not semi primes. A prime number by definition has only two factors, one and itself. The deleted post said something to the effect of "factoring prime numbers".
Re:NSA announces plans for transitioning to quantum resistan... by fegu on Saturday August 15, 2015 @08:44AM (#10065233)
Just to nitpick: you mean factor the product of two large prime numbers.