Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Some of the most effective cryptography methods and algorithms are based of factoring large prime numbers (e.g. RSA). I'm curious whether there are some other cryptography methods. Somethings that is very mathematical or physical based. Of course, I know about quantum cryptography, but I'm interested in other things also. For example, braid groups which have connection to knot theory can have application in cryptography. What I am asking is for a similar thing. I mean, is there any branch or equations in mathematics or physics that can lead to a cryptography methods.

share|improve this question
    
Elliptic curves and chaos theory are among the answers IMHO. –  Mok-Kong Shen Feb 3 '13 at 16:20
1  
Lattice assumption became very cool recently. cs.ut.ee/~lipmaa/crypto/link/public/lattice –  AntonioFa Feb 3 '13 at 17:08
add comment

1 Answer

All mathematical groups can be used to perform an ElGamal encryption, so that is a first kind of math. That's where elliptic curves are useful: they have a group structure. If you find a group, you can build a cryptosystem out of it. However, as @poncho pointed out, different groups have different properties with regards to security. For instance, elliptic curves are better than modular groups because they do not have a specific structure which can be leveraged to solve the discrete logarithm problem (see http://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm for an example of algorithm working only in modular groups).

You also have cryptosystems based on lattice related problems. In particular, lattices have been used to create the first fully homomorphic cryptosystem (see the references in http://en.wikipedia.org/wiki/Homomorphic_encryption).

A system which turned out to be very bad was built from the knap sack problem (see the Naccache–Stern knapsack cryptosystem on wikipedia).

For symmetric crypto, the theory of boolean functions can explain how the functions inside Feistel Networks or substitution permutation network are chosen. This yields connexions with coding theory and of course with finite fields of size $2^n$.

share|improve this answer
3  
Yes, you can use a arbitrary group in an ElGamal structure; however, that doesn't mean that such an encryption is even slightly secure. –  poncho Feb 6 '13 at 1:58
    
Very true, I'm updating my answer to mention this. –  picarresursix Feb 6 '13 at 17:08
    
Pedantically, the cryptographic hardness comes from the representation of group elements, not the structure of the group. For example, all cyclic groups have the same structure (that of addition mod $n$). The natural representation of $(\mathbb{Z}_{p-1}, +)$ and the natural representation of $(\mathbb{Z}_p^*, \times)$ have very different cryptographic properties though they are isomorphic groups. –  Mikero Mar 9 '13 at 3:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.