scientific article; zbMATH DE number 1256724

Publication date: 18 May 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

basis lattices shortest vector probabilistic polynomial time algorithm randomized subset sum problem

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Quadratic forms (reduction theory, extreme forms, etc.) (11H55)

Related Items

On the possibility of basing cryptography on $\mathsf{EXP}\ne \mathsf{BPP} $, \textsf{Halo Infinite}: proof-carrying data from additive polynomial commitments, On random nonsingular Hermite normal form, Lattice-based key exchange on small integer solution problem, SoK: how (not) to design and implement post-quantum cryptography, A compressed $\varSigma $-protocol theory for lattices, Lattice reduction with approximate enumeration oracles. Practical algorithms and concrete performance, A trace map attack against special ring-LWE samples, The inapproximability of lattice and coding problems with preprocessing, Lattice-based linearly homomorphic signatures in the standard model, A sub-linear lattice-based submatrix commitment scheme, Magnifying computing gaps. Establishing encrypted communication over unidirectional channels, Attribute-based signatures from lattices: unbounded attributes and semi-adaptive security, On basing search SIVP on $\mathbf{NP}$-hardness, $\mathrm{SL}_2$ homomorphic hash functions: worst case to average case reduction and short collision search, Solving the search-LWE problem over projected lattices, Black-box accumulation based on lattices, The matrix reloaded: multiplication strategies in FrodoKEM, On the higher-bit version of approximate inhomogeneous short integer solution problem, Fiat-Shamir and correlation intractability from strong KDM-secure encryption, Post-quantum cryptography: lattice signatures, The Modular Subset-Sum Problem and the size of deletion correcting codes, Vandermonde meets Regev: public key encryption schemes based on partial Vandermonde problems, Approximate CVP in time $2^{0.802 n}$ -- now in any norm!, Efficient proof composition for verifiable computation, A Ring-LWE-based digital signature inspired by Lindner-Peikert scheme, Property-preserving hash functions for Hamming distance from standard assumptions, Quantum algorithms for variants of average-case lattice problems via filtering, Duplication free public keys based on SIS-type problems, Permuted puzzles and cryptographic hardness, A pseudorandom number generator based on worst-case lattice problems, Asymptotically efficient lattice-based digital signatures, New transference theorems on lattices possessing $n^\varepsilon$-unique shortest vectors, Improved analysis of the reduction from BDD to uSVP, Scalable zero knowledge via cycles of elliptic curves, Hardness of $k$-LWE and applications in traitor tracing, A polynomial time algorithm for GapCVPP in $l_1$ norm, Improved broadcast attacks against subset sum problems via lattice oracle, The hunting of the SNARK, Post-quantum key exchange for the Internet and the open quantum safe project, Hardness of approximating the closest vector problem with pre-processing, Quantum cryptography beyond quantum key distribution, Computational indistinguishability between quantum states and its cryptographic application, Group signature from lattices preserving forward security in dynamic setting, Improved combinatorial algorithms for the inhomogeneous short integer solution problem, Approximating the SVP to within a factor $(1+1/\dim^\varepsilon)$ is NP-hard under randomized reductions, A lattice-based identity-based proxy blind signature scheme in the standard model, STP-LWE: A variant of learning with error for a flexible encryption, An efficient and batch verifiable conditional privacy-preserving authentication scheme for VANETs using lattice, Reductions in \textbf{PPP}, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Strongly secure authenticated key exchange from factoring, codes, and lattices, Minimal condition for shortest vectors in lattices of low dimension, An improved lower bound for approximating the minimum integral solution problem with preprocessing over $\ell_\infty$ norm, The projection games conjecture and the hardness of approximation of Super-SAT and related problems, Solving systems of diagonal polynomial equations over finite fields, A lattice-based group signature scheme with verifier-local revocation, FPT-algorithms for some problems related to integer programming, Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance, A multi-key SMC protocol and multi-key FHE based on some-are-errorless LWE, A more efficient leveled strongly-unforgeable fully homomorphic signature scheme, Enhancing Goldreich, Goldwasser and Halevi's scheme with intersecting lattices, A framework for cryptographic problems from linear algebra, Collusion-resistant identity-based proxy re-encryption: lattice-based constructions in standard model, Traceable ring signatures: general framework and post-quantum security, Lattice-based unidirectional infinite-use proxy re-signatures with private re-signature key, Lattice-based weak-key analysis on single-server outsourcing protocols of modular exponentiations and basic countermeasures, CCA-security from adaptive all-but-one lossy trapdoor functions, An efficient anti-quantum lattice-based blind signature for blockchain-enabled systems, Verifiable single-server private information retrieval from LWE with binary errors, Sigma protocols for MQ, PKP and SIS, and fishy signature schemes, Tweaking the asymmetry of asymmetric-key cryptography on lattices: KEMs and signatures of smaller sizes, On the ideal shortest vector problem over random rational primes, Multiparty reusable non-interactive secure computation from LWE, Candidate obfuscation via oblivious LWE sampling, Bifurcated signatures: folding the accountability vs. anonymity dilemma into a single private signing scheme, Single-to-multi-theorem transformations for non-interactive statistical zero-knowledge, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, LWE from non-commutative group rings, Lattice-based group signatures: achieving full dynamicity (and deniability) with ease, Chosen-ciphertext lattice-based public key encryption with equality test in standard model, On the limits of nonapproximability of lattice problems, Lattice-based revocable certificateless signature, Sharing privacy protected and statistically sound clinical research data using outsourced data storage, A note on the non-NP-hardness of approximate lattice problems under general Cook reductions., Incompressible encodings, Fast reduction of algebraic lattices over cyclotomic fields, Lattice reduction for modules, or how to reduce ModuleSVP to ModuleSVP, Slide reduction, revisited -- filling the gaps in SVP approximation, A non-PCP approach to succinct quantum-safe zero-knowledge, Revocable hierarchical attribute-based signatures from lattices, Covert authentication from lattices, A lattice-based public-key cryptosystem, Worst-case to average-case reductions for module lattices, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Approximating $SVP_{\infty}$ to within almost-polynomial factors is NP-hard, On the distribution of the Diffie-Hellman pairs, Short identity-based signatures with tight security from lattices, On removing rejection conditions in practical lattice-based signatures, Hardness of LWE on general entropic distributions, Attribute-Based Keyword Search from Lattices, Untraceability of Partial Blind and Blind Signature Schemes, Almost Tight Security in Lattices with Polynomial Moduli – PRF, IBE, All-but-many LTF, and More, Efficient lattice assessment for LCG and GLP parameter searches, On Solving Systems of Diagonal Polynomial Equations Over Finite Fields, Targeted Homomorphic Attribute-Based Encryption, Effective lattice point counting in rational convex polytopes, On ideal lattices, Gröbner bases and generalized hash functions, Unnamed Item, Sampling from Arbitrary Centered Discrete Gaussians for Lattice-Based Cryptography, A Fast Phase-based Enumeration Algorithm for SVP Challenge Through $$y$$-Sparse Representations of Short Lattice Vectors, Post-quantum online voting scheme, Ring Trapdoor Redactable Signatures from Lattice, Lattice-based secret handshakes with reusable credentials, Predicting the concrete security of LWE against the dual attack using binary search, Augmented Learning with Errors: The Untapped Potential of the Error Term, A Systematic Approach and Analysis of Key Mismatch Attacks on Lattice-Based NIST Candidate KEMs, Lattice Sieving via Quantum Random Walks, A novel identity-based multi-signature scheme over NTRU lattices, The Phase Transition of Discrepancy in Random Hypergraphs, Efficient lattice-based traceable ring signature scheme with its application in blockchain, Lattice-based accumulator with constant time list update and constant time verification, Succinct vector, polynomial, and functional commitments from lattices, Efficient laconic cryptography from learning with errors, Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings, Towards Tightly Secure Lattice Short Signature and Id-Based Encryption, Multi-key Homomorphic Authenticators, Oblivious message retrieval, The linear transformation that relates the canonical and coefficient embeddings of ideals in cyclotomic integer rings, Lattice-based zero-knowledge proofs and applications: shorter, simpler, and more general, Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable (extended abstract), Some easy instances of ideal-SVP and implications on the partial Vandermonde knapsack problem, Multimodal private signatures, Achieving Almost-Full Security for Lattice-Based Fully Dynamic Group Signatures with Verifier-Local Revocation, Fiat-Shamir signatures based on module-NTRU, Nearly optimal property preserving hashing, The gap is sensitive to size of preimages: collapsing property doesn't go beyond quantum collision-resistance for preimages bounded hash functions, Efficient unique ring signatures from lattices, Puncturable signature: a generic construction and instantiations, Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors, More efficient adaptively secure lattice-based IBE with equality test in the standard model, Multi-authority ABE from lattices without random oracles, Homomorphic encryption: a mathematical survey, MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity, Fully collusion resistant trace-and-revoke functional encryption for arbitrary identities, BLOOM: bimodal lattice one-out-of-many proofs and applications, Subfield attacks on HSVP in ideal lattices, Preimage sampling in the higher-bit approximate setting with a non-spherical Gaussian sampler, Improving convergence and practicality of slide-type reductions, Finding collisions in a quantum world: quantum black-box separation of collision-resistance and one-wayness, Collusion resistant trace-and-revoke for arbitrary identities from standard assumptions, On the (M)iNTRU assumption in the integer case, Secret handshakes: full dynamicity, deniability and lattice-based design, Unnamed Item, Unnamed Item, Explicit Hard Instances of the Shortest Vector Problem, Reduced Gröbner bases and Macaulay-Buchberger basis theorem over Noetherian rings, A Practical Post-Quantum Public-Key Cryptosystem Based on $$\textsf {spLWE}$$, Analysis of Error Terms of Signatures Based on Learning with Errors, Drawing Bobbin Lace Graphs, or, Fundamental Cycles for a Subclass of Periodic Graphs, Security and Trust in Sensor Networks, Compact Inner Product Encryption from LWE, Lattice-Based Group Signatures with Verifier-Local Revocation: Achieving Shorter Key-Sizes and Explicit Traceability with Ease, Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH, Constructing concrete hard instances of the maximum independent set problem, Algorithms for the Shortest and Closest Lattice Vector Problems, New Algorithms for Learning in Presence of Errors, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, Improved Zero-Knowledge Proofs of Knowledge for the ISIS Problem, and Applications, Private Puncturable PRFs from Standard Lattice Assumptions, On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL, Counting Co-Cyclic Lattices, Hardness of approximating the shortest vector problem in high $\ell_{p}$ norms, Improved Zero-Knowledge Identification with Lattices, Unnamed Item, Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures, Concurrently Secure Identification Schemes Based on the Worst-Case Hardness of Lattice Problems, Lattice-Based Identification Schemes Secure Under Active Attacks, Watermarking cryptographic functionalities from standard lattice assumptions, On the Correlation Intractability of Obfuscated Pseudorandom Functions, Cryptographic Assumptions: A Position Paper, Multi-theorem preprocessing NIZKs from lattices, Identity-based proxy re-signatures from lattices, Post-Quantum Cryptography: State of the Art, Predicting Lattice Reduction, An Average Case NP-complete Graph Colouring Problem, A Survey of Solving SVP Algorithms and Recent Strategies for Solving the SVP Challenge, An LWE-based verifiable threshold secret sharing scheme, Minicrypt primitives with algebraic structure and applications, Approximating the Closest Vector Problem Using an Approximate Shortest Vector Oracle, Collision-Free Hashing from Lattice Problems, Generalized Learning Problems and Applications to Non-commutative Cryptography, Programmable Hash Functions from Lattices: Short Signatures and IBEs with Small Key Sizes, Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security, Three Problems on Exponential Bases, Unnamed Item, Survey of Lattice-Based Group Signature, The Complexity of Public-Key Cryptography, Deciding Orthogonality in Construction-A Lattices, The state of the union: union-only signatures for data aggregation, Full quantum equivalence of group action DLog and CDH, and more, Development and analysis of massive parallelization of a lattice basis reduction algorithm, Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$, Lattice signature with efficient protocols, application to anonymous credentials, A framework for practical anonymous credentials from lattices, Finding short integer solutions when the modulus is small, Generic constructions of master-key KDM secure attribute-based encryption, Candidate witness encryption from lattice techniques, A new lattice-based online/offline signatures framework for low-power devices, A New Design of Online/Offline Signatures Based on Lattice, A New Insight—Proxy Re-encryption Under LWE with Strong Anti-collusion, Forward-secure revocable secret handshakes from lattices, Efficient lattice-based inner-product functional encryption, Simplified server-aided revocable identity-based encryption from lattices, Zero-knowledge range arguments for signed fractional numbers from lattices, Spatial encryption revisited: from delegatable multiple inner product encryption and more, Lattice-based programmable hash functions and applications, Lattice-based cryptography: a survey, Lattice-based succinct arguments from vanishing polynomials (extended abstract), \textsf{Orbweaver}: succinct linear functional commitments from lattices, Publicly-verifiable deletion via target-collapsing functions, Compact lattice gadget and its applications to hash-and-sign signatures, Toward practical lattice-based proof of knowledge from Hint-MLWE, Almost tight multi-user security under adaptive corruptions from LWE in the standard model, Lattice-based timed cryptography, Traceable policy-based signatures and instantiation from lattices, Genus distribution of random $q$-ary lattices, Subfield algorithms for ideal- and module-SVP based on the decomposition group, Mathematics of computation through the lens of linear equations and lattices, Interactions of computational complexity theory and mathematics