New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
From MaRDI portal
Publication:2051795
DOI10.1016/j.ic.2021.104771OpenAlexW3175971210WikidataQ114848479 ScholiaQ114848479MaRDI QIDQ2051795
Publication date: 25 November 2021
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2021.104771
computational learning theorycryptographyBoolean function learningintersections of halfspacesdiffering-inputs obfuscation
Uses Software
Cites Work
- Learning intersections and thresholds of halfspaces
- On the complexity of polyhedral separability
- PAC learning intersections of halfspaces with membership queries
- Learning an intersection of a constant number of halfspaces over a uniform distribution
- Indistinguishability obfuscation from SXDH on 5-linear maps and locality-5 PRGs
- Indistinguishability obfuscation from trilinear maps and block-wise local PRGs
- Indistinguishability obfuscation for Turing machines: constant overhead and amortization
- When won't membership queries help?
- Advances in cryptology -- CRYPTO 2014. 34th annual cryptology conference, Santa Barbara, CA, USA, August 17--21, 2014. Proceedings, Part I
- Theory of cryptography. 12th theory of cryptography conference, TCC 2015, Warsaw, Poland, March 23--25, 2015. Proceedings, Part II
- Theory of cryptography. 4th theory of cryptography conference, TCC 2007, Amsterdam, The Netherlands, February 21--24, 2007. Proceedings.
- Advances in cryptology -- CRYPTO 2017. 37th annual international cryptology conference, Santa Barbara, CA, USA, August 20--24, 2017. Proceedings. Part I
- Theory of cryptography. 11th theory of cryptography conference, TCC 2014, San Diego, CA, USA, February 24--26, 2014. Proceedings
- Learning intersections of halfspaces with a margin
- Cryptographic hardness for learning intersections of halfspaces
- Impossibility of VBB Obfuscation with Ideal Constant-Degree Graded Encodings
- Indistinguishability Obfuscation: From Approximate to Exact
- Indistinguishability Obfuscation from Constant-Degree Graded Encoding Schemes
- Cryptanalysis of GGH Map
- Practical Multilinear Maps over the Integers
- Security Analysis of Multilinear Maps over the Integers
- Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings
- On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input
- The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator
- An invariance principle for polytopes
- Faster Algorithms for Approximate Common Divisors: Breaking Fully-Homomorphic-Encryption Challenges over the Integers
- Cryptanalysis of the Multilinear Map over the Integers
- How to Obfuscate Programs Directly
- Black-box obfuscation for d-CNFs
- Obfuscation of Hyperplane Membership
- New Multilinear Maps Over the Integers
- Indistinguishability Obfuscation from Compact Functional Encryption
- Fully Homomorphic Encryption over the Integers
- Secure Obfuscation for Encrypted Signatures
- On obfuscating point functions
- Correcting errors without leaking partial information
- Perfect NIZK with Adaptive Soundness
- Securely Obfuscating Re-encryption
- How to Shuffle in Public
- A theory of the learnable
- Indistinguishability Obfuscation from Functional Encryption
- Foundations of Cryptography
- Candidate Multilinear Maps from Ideal Lattices
- Fully homomorphic encryption using ideal lattices
- Fully Homomorphic Encryption over the Integers with Shorter Public Keys
- On Obfuscation with Random Oracles
- Graph-Induced Multilinear Maps from Lattices
- Obfuscating Circuits via Composite-Order Graded Encoding
- Patchable Indistinguishability Obfuscation: $$i\mathcal {O}$$ for Evolving Software
- On the (im)possibility of obfuscating programs
- Protecting Obfuscation against Algebraic Attacks
- Advances in Cryptology - CRYPTO 2003
- Obfuscating Point Functions with Multibit Output
- New Negative Results on Differing-Inputs Obfuscation
- Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding
- On Extractability Obfuscation
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries
