Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence
Security Accomplishment | 1997
IBM researchers: Miklós Ajtai, Cynthia Dwork
Where the work was done: IBM Almaden Research Center
What we accomplished: The paper represents an early use of lattices in cryptography and presents a "probabilistic public key cryptosystem which is secure unless the worst case of a particular lattice problem can be solved in polynomial time," with such polynomial-time solutions being very unlikely.
Related links:
- A Public-Key Cryptosystem with Worst-Case / Average-Case Equivalence, STOC '97 - 29th Annual ACM Symposium on the Theory of Computing
- 500+ Citations
BACK TO IBM RESEARCH ACCOMPLISHMENTS