6 ms·

Can anyone explain what makes an encryption algorithm quantum-resistant?

• deleted 11y ago
  [deleted]
  • lindig 11y ago
    Prime numbers can't be factored.
    • wolfgke 11y ago
      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.",
      • deleted 11y ago
        [deleted]
      • noobie 11y ago
        I'd go with "Prime numbers can't be prime-factored".
        • wolfgke 11y ago
          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).
    • fredgrott 11y ago
      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
      • _asummers 11y ago
        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".
  • fegu 11y ago
    Just to nitpick: you mean factor the product of two large prime numbers.
  • chucksmash 11y ago
    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).
• pbsd 11y ago
  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_Systems_and_Attacks/S07_Groves_Annex.pdf http://docbox.etsi.org/Workshop/2014/201410_CRYPTO/S07_Syste...