NDLI: Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Please wait, while we are loading the content...

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Content Provider	Springer Nature Link
Author	Micciancio, Daniele
Copyright Year	2007
Abstract	We investigate the average-case complexity of a generalization of the compact knapsack problem to arbitrary rings: given m (random) ring elements a 1,..., a m ∈ R and a (random) target value b ∈ R, find coefficients x 1, ..., x m ∈ S (where S is an appropriately chosen subset of R) such that ∑ a i · x i = b. We consider compact versions of the generalized knapsack where the set S is large and the number of weights m is small. Most variants of this problem considered in the past (e.g., when $$R={\mathbb{Z}}$$ is the ring of the integers) can be easily solved in polynomial time even in the worst case. We propose a new choice of the ring R and subset S that yields generalized compact knapsacks that are seemingly very hard to solve on the average, even for very small values of m. Namely, we prove that for any unbounded function m = ω(1) with arbitrarily slow growth rate, solving our generalized compact knapsack problems on the average is at least as hard as the worst-case instance of various approximation problems over cyclic lattices. Specific worst-case lattice problems considered in this paper are the shortest independent vector problem SIVP and the guaranteed distance decoding problem GDD (a variant of the closest vector problem, CVP) for approximation factors n 1+∈ almost linear in the dimension of the lattice. Our results yield very efficient and provably secure one-way functions (based on worst-case complexity assumptions) with key size and time complexity almost linear in the security parameter n. Previous constructions with similar security guarantees required quadratic key size and computation time. Our results can also be formulated as a connection between the worst-case and average-case complexity of various lattice problems over cyclic and quasi-cyclic lattices.
Starting Page	365
Ending Page	411
Page Count	47
File Format	PDF
ISSN	10163328
Journal	Computational complexity
Volume Number	16
Issue Number	4
e-ISSN	14208954
Language	English
Publisher	SP Birkhäuser Verlag Basel
Publisher Date	2007-12-05
Publisher Place	Basel
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Knapsack problem cyclic lattices average-case complexity one-way functions Computational Mathematics and Numerical Analysis Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions (2007)

Pseudorandomness and Average-Case Complexity Via Uniform Reductions

Generalized compact knapsacks are collision resistant (2006)

Generalized compact knapsacks are collision resistant (2006)

Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword

Generalized compact knapsacks are collision resistant (2005).

Improved Approximation of Linear Threshold Functions

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Similar Documents

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

Generalized compact knapsacks, cyclic lattices, and efficient one-way functions (2007)

Pseudorandomness and Average-Case Complexity Via Uniform Reductions

Generalized compact knapsacks are collision resistant (2006)

Generalized compact knapsacks are collision resistant (2006)

Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword

Generalized compact knapsacks are collision resistant (2005).

Improved Approximation of Linear Threshold Functions

Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions