Cryptographic primitives based on hard learning problems
From MaRDI portal
Modern cryptography has had considerable impact on the development of computational learning theory. Virtually every intractability result in \textit{L. G. Valiant's} model [Commun. ACM 27, 1134-1142 (1984; Zbl 0587.68077)] (which is representation-independent in the sense that it does not rely on an artificial syntactic restriction on the learning algorithm's hypotheses) has at its heart a cryptographic construction. In this paper, we give results in the reverse direction by showing how to construct several cryptographic primitives based on certain assumptions on the difficulty of learning. For the entire collection see [Zbl 0856.00053].
Recommendations
Cited in
(only showing first 100 items - show all)- Separating models of learning with faulty teachers
- Cryptography with constant input locality
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Exploring crypto dark matter: new simple PRF candidates and their applications
- On the nonlinearity of monotone Boolean functions
- Efficient authentication from hard learning problems
- CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN
- An improved algorithm for learning sparse parities in the presence of noise
- Breaking the circuit size barrier for secure computation under quasi-polynomial LPN
- Large scale, actively secure computation from LPN and free-XOR garbled circuits
- Efficient pseudorandom correlation generators from ring-LPN
- Towards efficient LPN-based symmetric encryption
- Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
- Silver: silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Making the BKW algorithm practical for LWE
- Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\)
- Permuted puzzles and cryptographic hardness
- Computational fuzzy extractors
- Cryptographic sensing
- An approach for stream ciphers design based on joint computing over random and secret data
- Solving the learning parity with noise's open question
- Cryptographic hardness for learning intersections of halfspaces
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- BKW meets Fourier new algorithms for LPN with sparse parities
- Covert learning: how to learn with an untrusted intermediary
- On solving LPN using BKW and variants, Implementation and analysis
- Two-round man-in-the-middle security from LPN
- Perfect structure on the edge of chaos. Trapdoor permutations from indistinguishability obfuscation
- Towards sound fresh re-keying with hard (physical) learning problems
- Circuit-ABE from LWE: Unbounded Attributes and Semi-adaptive Security
- Lattice-based fully dynamic multi-key FHE with short ciphertexts
- Cryptography with auxiliary input and trapdoor from constant-noise LPN
- Interactive clustering of linear classes and cryptographic lower bounds
- Cryptography from learning parity with noise
- FHEW with Efficient Multibit Bootstrapping
- Efficient Authentication from Hard Learning Problems
- New Algorithms for Learning in Presence of Errors
- Garbling XOR gates ``for free in the standard model
- Fast pseudorandom functions based on expander graphs
- Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems
- How to Encrypt with the LPN Problem
- Separating Models of Learning with Faulty Teachers
- Parallel and Concurrent Security of the HB and HB + Protocols
- Cryptographic limitations on learning Boolean formulae and finite automata
- scientific article; zbMATH DE number 697831 (Why is no real title available?)
- Computational learning theoretic cryptanalysis of language theoretic cryptosystems
- Multikey fully homomorphic encryption and applications
- Low-complexity cryptographic hash functions
- A family of trapdoor ciphers
- Cryptoschemes based on difficulty of simultaneous solving two different difficult problems
- Agnostic Learning from Tolerant Natural Proofs
- The Complexity of Public-Key Cryptography
- Pseudorandom functions: three decades later
- Homomorphic encryption
- scientific article; zbMATH DE number 7626788 (Why is no real title available?)
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- Oblivious Transfer Based on the McEliece Assumptions
- TinyKeys: a new approach to efficient multi-party computation
- Parallel and concurrent security of the HB and \(HB^{+}\) protocols
- Actively secure half-gates with minimum overhead under duplex networks
- Sublinear-communication secure multiparty computation does not require FHE
- Homomorphic encryption: a mathematical survey
- A non-heuristic approach to time-space tradeoffs and optimizations for BKW
- Computational wiretap coding from indistinguishability obfuscation
- Modeling and simulating the sample complexity of solving LWE using BKW-style algorithms
- Correlated pseudorandomness from expand-accumulate codes
- Statistically sender-private OT from LPN and derandomization
- Moz\(\mathbb{Z}_{2^k}\)arella: efficient vector-OLE and zero-knowledge proofs over \(\mathbb{Z}_{2^k}\)
- Expand-convolute codes for pseudorandom correlation generators from LPN
- Indistinguishability obfuscation
- Hardness of learning AES with gradient-based methods
- An iterative correction method for practically LPN solving
- Amortized NISC over \(\mathbb{Z}_{2^k}\) from RMFE
- Fast public-key silent OT and more from constrained Naor-Reingold
- The hardness of LPN over any integer ring and field for PCG applications
- Lossy cryptography from code-based assumptions
- Non-interactive zero-knowledge from LPN and MQ
- Multivariate exponential equations with unknown coefficients
- Efficient pseudorandom correlation generators over \(\mathbb{Z}/p^k\mathbb{Z} \)
- Stationary syndrome decoding for improved PCGs
- Sample efficient search to decision for kLIN
- A meta-complexity characterization of quantum cryptography
- Efficient pseudorandom correlation generators for any finite field
- Low-bandwidth mixed arithmetic in VOLE-based ZK from low-degree PRGs
- Somewhat homomorphic encryption from linear homomorphism and sparse LPN
- Distributional PAC-learning from Nisan's natural proofs
- Approximating the number of relevant variables in a parity implies proper learning
- Lossy cryptography from code-based assumptions dense-sparse LPN: a new subexponentially hard LPN variant in SZK
- Limitations of the decoding-to-LPN reduction via code smoothing
- Interactive line-point zero-knowledge with sublinear communication and linear computation
- Actively secure half-gates with minimum overhead under duplex networks
- Agnostic membership query learning with nontrivial savings: new results and techniques
- On the structure of learnability beyond \textsf{P/poly}
- Indistinguishability obfuscation from well-founded assumptions
- Bootstrappable fully homomorphic attribute-based encryption with unbounded circuit depth
- Pseudorandom correlation generators for multiparty Beaver triples over \(\mathbb{F}_2\)
- Practical secure delegated linear algebra with trapdoored matrices
- Slightly sublinear trapdoor hash functions and PIR from low-noise LPN
- \textsf{Justvengers}: batched VOLE ZK disjunctions in \(\mathcal{O}(R+B+C)\) communication
This page was built for publication: Cryptographic primitives based on hard learning problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4341754)
