Article

Free access

Generating hard instances of lattice problems (extended abstract)

Author:

M. AjtaiAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 99 - 108

https://doi.org/10.1145/237814.237838

Published: 01 July 1996 Publication History

PDF eReader

References

[1]

L. Adleman, "On breaking the iterated Merkle- Hellman public key cryptosystem", in: Advances in Cryptology, Proceedings of CRYPTO 82, Plenum Press, New York, 1983, 303-308.

Google Scholar

[2]

M. Ajtai, "Generating Hard instances of Lattice Problems" Electronic Colloquium on Computational Complexity, 1996. TR96-007, http://www.eccc.unitrier.de/eccc/

Google Scholar

[3]

E.F. Brickell, "Breaking iterated knapsacks", in: Advances in Cryptology, Proceedings of CRYPTO 84, Springer, Berlin, 1985

Digital Library

Google Scholar

[4]

J.W.S. Cassels, "An Introduction to the Geometry of Numbers", Springer, 1959.

Crossref

Google Scholar

[5]

P.M. Gruber, C.G.Lekkerkerker, "Geometry of Numbers", North-Holland, 1987

Google Scholar

[6]

M. GrStschel, L. LovAsz, A. Schrijver, "Geometric Algorithms and Combinatorial Optimization", Springer, Algorithms and Combinatorics, 1988

Google Scholar

[7]

R. Implagliazzo, M. Naor, "Efficient Cryptographic Schemes Provably as Secure as Subset Sum", STOC, 1989, pp. 236-241

Google Scholar

[8]

J.C. Lagarias, A.M. Odlyzko (1983), "Solving low-density subset sum problems", Journal of the Association for Computing Machinery 32 (1985) 229-246.

Digital Library

Google Scholar

[9]

A.K. Lenstra, H.W. Lenstra, L. Lov~sz "Factoring polynomials with rational coefficients", Math. Ann. 261, 515-534 (1982)

Crossref

Google Scholar

Cited By

View all

Filho DSilva TLópez J(2024)Efficient isochronous fixed-weight sampling with applications to NTRUIACR Communications in Cryptology10.62056/a6n59qgxqOnline publication date: 8-Jul-2024
https://doi.org/10.62056/a6n59qgxq
Das SDas A(2024)Pre-Quantum to Post-Quantum Cryptography TransitionIntegration of AI, Quantum Computing, and Semiconductor Technology10.4018/979-8-3693-7076-6.ch012(253-276)Online publication date: 11-Oct-2024
https://doi.org/10.4018/979-8-3693-7076-6.ch012
Chauhan SSrivastava SSingh RSharma AOjha D(2024)Quantum CryptographyApplications and Principles of Quantum Computing10.4018/979-8-3693-1168-4.ch019(378-398)Online publication date: 31-Jan-2024
https://doi.org/10.4018/979-8-3693-1168-4.ch019
Show More Cited By

Index Terms

Generating hard instances of lattice problems (extended abstract)
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Generating Hard Instances of the Short Basis Problem
ICAL '99: Proceedings of the 26th International Colloquium on Automata, Languages and Programming

A class of random lattices is given, in [1] so that (a) a random lattice can be generated in polynomial time together with a short vector in it, and (b) assuming that certain worst-case lattice problems have no polynomial time solutions, there is no ...
Hard Instances of Hard Problems
STACS '00: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science

This paper investigates the instance complexities of problems that are hard or weakly hard for exponential time under polynomial time, many-one reductions. It is shown that almost every instance of almost every problem in exponential time has ...
Lattice implication ordered semigroups

From the viewpoint of semantics, lattice implication algebras provide a basis to establish lattice-valued logic with truth value in a relatively general lattice. In this paper, we first introduce two notions of lattice implication n-ordered semigroup ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

923
Total Citations
View Citations
10,650
Total Downloads

Downloads (Last 12 months)2,975
Downloads (Last 6 weeks)479

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Filho DSilva TLópez J(2024)Efficient isochronous fixed-weight sampling with applications to NTRUIACR Communications in Cryptology10.62056/a6n59qgxqOnline publication date: 8-Jul-2024
https://doi.org/10.62056/a6n59qgxq
Das SDas A(2024)Pre-Quantum to Post-Quantum Cryptography TransitionIntegration of AI, Quantum Computing, and Semiconductor Technology10.4018/979-8-3693-7076-6.ch012(253-276)Online publication date: 11-Oct-2024
https://doi.org/10.4018/979-8-3693-7076-6.ch012
Chauhan SSrivastava SSingh RSharma AOjha D(2024)Quantum CryptographyApplications and Principles of Quantum Computing10.4018/979-8-3693-1168-4.ch019(378-398)Online publication date: 31-Jan-2024
https://doi.org/10.4018/979-8-3693-1168-4.ch019
Sabani MSavvas IGarani G(2024)Learning with Errors: A Lattice-Based Keystone of Post-Quantum CryptographySignals10.3390/signals50200125:2(216-243)Online publication date: 13-Apr-2024
https://doi.org/10.3390/signals5020012
Park HSon SPark YPark Y(2024)Provably Quantum Secure Three-Party Mutual Authentication and Key Exchange Protocol Based on Modular Learning with ErrorElectronics10.3390/electronics1319393013:19(3930)Online publication date: 4-Oct-2024
https://doi.org/10.3390/electronics13193930
Yuan QYuan HZhao JZhou MShao YWang YZhao S(2024)Distributed Identity Authentication with Lenstra–Lenstra–Lovász Algorithm–Ciphertext Policy Attribute-Based Encryption from Lattices: An Efficient Approach Based on Ring Learning with Errors ProblemEntropy10.3390/e2609072926:9(729)Online publication date: 27-Aug-2024
https://doi.org/10.3390/e26090729
Amirkhanova DIavich MMamyrbayev O(2024)Lattice-Based Post-Quantum Public Key Encryption Scheme Using ElGamal’s PrinciplesCryptography10.3390/cryptography80300318:3(31)Online publication date: 8-Jul-2024
https://doi.org/10.3390/cryptography8030031
Fitzgibbon GOttaviani C(2024)Constrained Device Performance Benchmarking with the Implementation of Post-Quantum CryptographyCryptography10.3390/cryptography80200218:2(21)Online publication date: 23-May-2024
https://doi.org/10.3390/cryptography8020021
Li YLiu S(2024)Identity-based chameleon hash from latticesJournal of Computer Security10.3233/JCS-22012132:6(509-531)Online publication date: 20-Nov-2024
https://doi.org/10.3233/JCS-220121
Jurkiewicz M(2024)Quantum-Resistant Forward-Secure Digital Signature Scheme Based on q-ary LatticesJournal of Telecommunications and Information Technology10.26636/jtit.2024.2.1581(90-103)Online publication date: 10-Jun-2024
https://doi.org/10.26636/jtit.2024.2.1581
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Generating Hard Instances of the Short Basis Problem

Hard Instances of Hard Problems

Lattice implication ordered semigroups