Miklos Ajtai, Cynthia Dwork

We present a probabilistic public key cryptosystem which is

secure unless the following worst-case lattice problem can be solved in

polynomial time:

"Find the shortest nonzero vector in an n dimensional lattice

L where the shortest vector v is unique in the sense that any other

vector whose ...
more >>>

Dima Grigoriev

Public-key crypto

Contact: dima@maths.univ-rennes1.fr

Author: Dima Grigoriev

Title: Public-key cryptography and invariant theory

Abstract: Public-key cryptosystems are suggested based on invariants of group

representations

Miklos Ajtai, Cynthia Dwork

We describe a public-key cryptosystem with worst-case/average case

equivalence. The cryptosystem has an amortized plaintext to

ciphertext expansion of $O(n)$, relies on the hardness of the

$\tilde O(n^2)$-unique shortest vector problem for lattices, and

requires a public key of size at most $O(n^4)$ bits. The new

cryptosystem generalizes a conceptually ...
more >>>