Generalized Compact Knapsacks Are Collision Resistant
From MaRDI portal
Publication:3591445
DOI10.1007/11787006_13zbMath1133.68353OpenAlexW1546634390MaRDI QIDQ3591445
Vadim Lyubashevsky, Daniele Micciancio
Publication date: 11 September 2007
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11787006_13
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (71)
Cyclic and well-rounded lattices ⋮ Compact Privacy Protocols from Post-quantum and Timed Classical Assumptions ⋮ Subtractive sets over cyclotomic rings. Limits of Schnorr-like arguments over lattices ⋮ An efficient CCA-secure cryptosystem over ideal lattices from identity-based encryption ⋮ Universal product learning with errors: a new variant of \textsf{LWE} for lattice-based cryptography ⋮ Tightly secure signatures from lossy identification schemes ⋮ Parallel Hashing via List Recoverability ⋮ Gadget-based iNTRU lattice trapdoors ⋮ Memory lower bounds of reductions revisited ⋮ Short, invertible elements in partially splitting cyclotomic rings and applications to lattice-based zero-knowledge proofs ⋮ Post-quantum cryptography: lattice signatures ⋮ Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems ⋮ On ideal lattices, Gröbner bases and generalized hash functions ⋮ Asymptotically quasi-optimal cryptography ⋮ Lattice trapdoors and IBE from middle-product LWE ⋮ On the complexity of collision resistant hash functions: new and old black-box separations ⋮ A pseudorandom number generator based on worst-case lattice problems ⋮ Post-quantum online voting scheme ⋮ Asymptotically efficient lattice-based digital signatures ⋮ Bonsai trees, or how to delegate a lattice basis ⋮ Functional commitments for all functions, with transparent setup and from SIS ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings ⋮ Optimisations and tradeoffs for HElib ⋮ A thorough treatment of highly-efficient NTRU instantiations ⋮ The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings ⋮ Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract) ⋮ Practical sublinear proofs for R1CS from lattices ⋮ Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem ⋮ Fiat-Shamir signatures based on module-NTRU ⋮ Verifiable Decryption for Fully Homomorphic Encryption ⋮ Lattices from Hermitian function fields ⋮ Roadmap of post-quantum cryptography standardization: side-channel attacks and countermeasures ⋮ A new lattice-based online/offline signatures framework for low-power devices ⋮ Reductions from module lattices to free module lattices, and application to dequantizing module-LLL ⋮ On the tightness of forward-secure signature reductions ⋮ On the geometry of cyclic lattices ⋮ A verifiable threshold secret sharing scheme based on lattices ⋮ A characterization of chameleon hash functions and new, efficient designs ⋮ Trapdoor delegation and HIBE from middle-product LWE in standard model ⋮ Strongly secure authenticated key exchange from factoring, codes, and lattices ⋮ Tighter Reductions for Forward-Secure Signature Schemes ⋮ Security analysis of cryptosystems using short generators over ideal lattices ⋮ One-Shot Verifiable Encryption from Lattices ⋮ Short Stickelberger Class Relations and Application to Ideal-SVP ⋮ Short Bases of Lattices over Number Fields ⋮ Improved Zero-Knowledge Identification with Lattices ⋮ Interpreting Hash Function Security Proofs ⋮ Cryptographic Functions from Worst-Case Complexity Assumptions ⋮ A framework for cryptographic problems from linear algebra ⋮ Hash Functions from Sigma Protocols and Improvements to VSH ⋮ Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems ⋮ Lattice-Based Identification Schemes Secure Under Active Attacks ⋮ Asymptotically Efficient Lattice-Based Digital Signatures ⋮ Post-Quantum Cryptography: State of the Art ⋮ Integer Version of Ring-LWE and Its Applications ⋮ MPSign: a signature from small-secret middle-product learning with errors ⋮ On the ideal shortest vector problem over random rational primes ⋮ On the security of homomorphic encryption on approximate numbers ⋮ The Geometry of Lattice Cryptography ⋮ On the integer polynomial learning with errors problem ⋮ Chosen-ciphertext lattice-based public key encryption with equality test in standard model ⋮ Practical \(\mathsf{MP} \text{- }\mathsf{LWE}\)-based encryption balancing security-risk versus efficiency ⋮ On Lattices Generated by Finite Abelian Groups ⋮ Random self-reducibility of ideal-SVP via Arakelov random walks ⋮ Practical product proofs for lattice commitments ⋮ Lattice-based blind signatures, revisited ⋮ A Parallel GPU Implementation of SWIFFTX ⋮ Unnamed Item ⋮ Worst-case to average-case reductions for module lattices ⋮ On ideal class group computation of imaginary multiquadratic fields
Uses Software
This page was built for publication: Generalized Compact Knapsacks Are Collision Resistant