ECCC-Report TR98-010https://eccc.weizmann.ac.il/report/1998/010Comments and Revisions published for TR98-010en-usThu, 24 Jun 1999 00:00:00 +0300
Revision 1
| A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implic ations Revision of: TR98-010 |
Phong Nguyen,
Jacques Stern
https://eccc.weizmann.ac.il/report/1998/010#revision1
Recently, Ajtai discovered a fascinating connection
between the worst-case complexity and the average-case
complexity of some well-known lattice problems.
Later, Ajtai and Dwork proposed a cryptosystem inspired
by Ajtai's work, provably secure if a particular lattice
problem is difficult. We show that there is a converse
to the Ajtai-Dwork security result, by reducing the question
of distinguishing encryptions of one from encryptions
of zero to approximating some lattice problems.
This is especially interesting in view of a result of
Goldreich and Goldwasser, which seems to rule out any
form of NP-hardness for such approximation problems.
Thu, 24 Jun 1999 00:00:00 +0300https://eccc.weizmann.ac.il/report/1998/010#revision1
Paper TR98-010
| A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications |
Phong Nguyen,
Jacques Stern
https://eccc.weizmann.ac.il/report/1998/010
Recently, Ajtai discovered a fascinating connection
between the worst-case complexity and the average-case
complexity of some well-known lattice problems.
Later, Ajtai and Dwork proposed a cryptosystem inspired
by Ajtai's work, provably secure if a particular lattice
problem is difficult. We show that there is a converse
to the Ajtai-Dwork security result, by reducing the question
of distinguishing encryptions of one from encryptions
of zero to approximating some lattice problems.
This is especially interesting in view of a result of
Goldreich and Goldwasser, which seems to rule out any
form of NP-hardness for such approximation problems.
Wed, 18 Feb 1998 12:20:13 +0200https://eccc.weizmann.ac.il/report/1998/010