Re: A very general question relating to Cryptography

On 2006-11-08 09:04:15 -0500, PaulHjelmstad <phjelmstad@xxxxxxx> said:

Cryptography is based on both the study of prime numbers
(and the Riemann Zeta Hypothesis). It is also very much
based on Group Theory, Finite Fields, Modular arithmetic
etc.

In my experience with cryptography, it has a large part of its theory based on its own concepts of *computational complexity*, *IND* (Indistinguishability), *semantic security*, etc., and then defines basic objects like *OWF* (one way functions), *PRG* (pseudo-random number generators), etc., from which encryption systems with provable security such as *PKS* (public key system), *SKS* (shared key systems), *KEM* (key encapsulation systems) are established.

The thing to note is that all these things are abstract and independent of any particular underlying mathematics in number theory.

However, of course, to have actual implementations of these systems, number theory is used, for example, the apparent difficulty of factoring. But the point is that even if someday someone figures out how to efficiently factor integers, it does not imply that the theory of cryptography is in trouble because it is *not* based on factoring but rather based on OWF's and PRG's, of which factorization of integers is only one type of them.

--

-kira

.

Relevant Pages

  • A very general question relating to Cryptography
    ... (and the Riemann Zeta Hypothesis). ... based on Group Theory, Finite Fields, Modular arithmetic ... General question: Does Cryptography relate Groups ...
    (sci.math)
  • Re: Speculative, but at least interesting
    ... >With the proviso that my knowledge of cryptography is limited to ... Certainly factoring experts have no such fear. ... >in factoring techniques. ... I know of no factoring methods which ...
    (sci.math)
  • Re: Prime Decomposition
    ... > large enough that the naieve algorithm is too slow. ... fact in the world of cryptography: ... RSA public-key cryptosystem) relies on the "impossibility" ... of factoring large numbers in a reasonable amount of time. ...
    (sci.math)
  • Prime Factors
    ... I probaby dont need to tell about importance of factoring into primes ... for cryptography, so ill just ask the question: ... Although there is no published algorithm for efficient factorization ...
    (sci.math.num-analysis)
  • Re: The factoring problem
    ... It's not a stupid question, it's a very important question indeed. ... A lot of people to talk about whether factoring in the NP complexity ... class as being important to cryptography. ... the problem at infinity. ...
    (sci.crypt)