6
$\begingroup$

For RSA and El Gamal (and most other public key cryptosystems), one of the key ideas is that factoring and finding discrete logarithms are hard. There are other systems that rely on certain properties of lattices.

What are the other one-way-ish functions that have cryptosystems designed around them?

$\endgroup$

3 Answers 3

6
$\begingroup$

The Merkle–Hellman knapsack cryptosystem was based on a variation of the subset sum problem. (It was broken by Adi Shamir a few years after it was developed.)

Given a set of numbers $A$ and a number b, find a subset of $A$, which sums to b.

The cryptosystem relies on the fact that in this form of the subset sum problem if the set $A$ is superincreasing (each element of the set is greater than the sum of all the previous elements), the problem is solvable in polynomial time. Also, you can transform the superincreasing set $A$ into a non-superincreasing set $B$ using a multiplier $r$ and a modulus $q$.

Solving the subset sum problem with a non-superincreasing set ($B$) is NP-complete, so you can use $B$ as a public key to encrypt messages, then use $A$, $r$, and $q$ as a private key to decrypt them.

$\endgroup$
1
  • 1
    $\begingroup$ +1 for that answer. However broken cryptosystems are of less interest than the other kind, and knapsack-based cryptosystems have a bad reputation (since that episode, a perhaps some sequel). $\endgroup$
    – fgrieu
    Dec 10, 2011 at 17:02
5
$\begingroup$

Many lattice schemes are based on the shortest vector problem and it's variants. Elliptic curve crypto systems are based on something akin to discrete logarithms but it is different in its details. Some authentication schemes like HB are based on learning parity with noise and systems are based on the more general learning with errors. Subset sum was mentioned. Decoding information sets is the basis of McEliece. The conjugacy search problem is ostensibly the basis of some cryptography in braid groups.

$\endgroup$
1
  • 1
    $\begingroup$ Isn't braid crypto pretty much discredited now? I don't know details but I heard it was shown to be insecure a few years ago. $\endgroup$
    – pg1989
    May 28, 2013 at 2:55
3
$\begingroup$

I will just like to contribute in light of what has been told above. There are few cryptosystems (just signature schemes as far as my knowledge goes) that are based on the hardness of solving a system of multi-variate polynomial. Solving a system of multi-variate polynomial is proved to be $\mathsf{NP}$-hard and just like the "hard" problems on lattices, they have resisted serious quantum attacks. Constructing a secure encryption scheme based on multi-variate polynomials is still an open problem.

People have also used abstract concepts like Fractal to construct cryptosystem based on Mandelbrot sets, but for some reason, it never attracted too much attention though it is considered to be secure against quantum attack.

A recent work that constructed public key primitives that are as secure as subset sum was proved in TCC 2010 by Lyubashevsky et. al. It is a good paper to read as it gives a very good description of the relation between hardness of some lattice based problem and subset sum. So, in light of recent works, you can count subset-sum as another problem on which cryptographic primitives are based.

Frankly, this list can go on and on forever, but I think these are the few that are worth mentioning in addition to the one that are already been mentioned, especially if you are interested in post-quantum cryptography.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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