Worst-case complexity, average-case complexity and lattice problems

MaRDI QIDQ1126836zbMATH OpenFDO

Authors Miklós Ajtai

Publication date 5 August 1998

Published in Documenta Mathematica (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/227634, http://www.emis.de/journals/DMJDMV/xvol-icm/14/Ajtai.MAN.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

average-casebasiscomplexitylatticepublic-key cryptosystemshortest vectorworst-case

Mathematics Subject Classification ID

Quadratic forms (reduction theory, extreme forms, etc.) (11H55) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Review text

The author presents a public-key cryptosystem based on the difficulty of a problem essentially similar to finding the shortest vector in a lattice. As part of the introduction, the author discusses the need for a problem that is hard in the average case; traditional complexity theory has focused on the worst-case complexity of problems.

Recommendations

• scientific article; zbMATH DE number 1559544
• scientific article; zbMATH DE number 1643917
• scientific article; zbMATH DE number 1304121
• A lattice-based public-key cryptosystem

Cited in

(6)

• A note on the concrete hardness of the shortest independent vector in lattices
• scientific article; zbMATH DE number 1643917 (Why is no real title available?)
• scientific article; zbMATH DE number 1094170 (Why is no real title available?)
• scientific article; zbMATH DE number 1180007 (Why is no real title available?)
• scientific article; zbMATH DE number 1512702 (Why is no real title available?)
• scientific article; zbMATH DE number 1559544 (Why is no real title available?)

This page was built for publication: Worst-case complexity, average-case complexity and lattice problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1126836)