New cryptographic hardness for learning intersections of halfspaces over Boolean cubes with membership queries

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

zbMATH Keywords

computational learning theory cryptography Boolean function learning intersections of halfspaces differing-inputs obfuscation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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