Privacy concern has been increasingly important in many machine learning (ML) problems. We study empirical risk minimization (ERM) problems under secure multi-party computation (MPC) frameworks. Main technical tools for MPC have been developed based on cryptography. One of limitations in current cryptographically priva…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “cryptographic assumptions”
Hard to estimate -accurate scores without strong assumptions.
problem Estimating the score of unknown data distributions accurately.
method Reduction to generating samples and leveraging lattice-based cryptography hardness.
result Score estimation is computationally hard even with polynomial sample complexity.
Reduces learning periodic neural networks to lattice problems, proving hardness under cryptographic assumptions.
problem Learning single periodic neurons in noisy environments.
method Reduction to worst-case lattice problems, using LLL algorithm.
result Polynomial-time algorithms for learning these functions are hard under cryptographic assumptions.
Quantum computers outperform classical methods in density modeling.
problem Density modeling with quantum computers.
method Quantum-classical separation for density modeling.
result Quantum computers offer a super-polynomial advantage over classical algorithms for density modeling.
In our recent work (Bubeck, Price, Razenshteyn, arXiv:1805.10204) we argued that adversarial examples in machine learning might be due to an inherent computational hardness of the problem. More precisely, we constructed a binary classification task for which (i) a robust classifier exists; yet no non-trivial accuracy c…
Boosting algorithm reduces error in noisy data.
problem Improving weak learners in the presence of Massart noise.
method First computationally efficient boosting algorithm for Massart noise.
result Achieves misclassification error arbitrarily close to Massart noise threshold.
We discuss some applications of 3-manifold topology to cryptography. In particular, we propose a public-key and a symmetric-key cryptographic scheme based on the Thurston norm on the first cohomology of hyperbolic manifolds.
Study learning from multiple thinkers providing step-by-step solutions to problems.
problem Learning from multiple, possibly different, thinkers providing step-by-step solutions to problems.
method Active learning algorithm that uses CoT data from multiple thinkers and end-result data.
result Learning can be hard from CoT supervision provided by two or a few different thinkers, but a generic algorithm can learn efficiently.
SOTERIA optimizes neural networks for secure inference with minimal overhead.
problem Protecting user privacy in ML-as-a-service models with low overhead.
method Neural architecture search with dual objectives of accuracy and cryptographic efficiency.
result SOTERIA constructs efficient models for secure inference.
New findings suggest minimax optimality doesn't guarantee distribution learning for GANs.
problem Understanding when GANs can truly learn the underlying distribution.
method Using cryptographic assumptions and ReLU network generators, the paper shows that achieving minimax optimality is insufficient for distribution learning.
result Achieving minimax optimality is insufficient for distribution learning in the usual statistical sense.
Paper tackles efficient HMM learning with conditional samples.
problem Cryptographic hardness in learning HMMs from i.i.d. samples.
method Interactive access model, polynomial-time algorithms for conditional probabilities and latent low rank structures.
result Efficient algorithms for HMM learning in both exact and approximate conditional settings.
PHAZE framework uses zkML and hashing for fast, verifiable LHC trigger decisions.
problem Inefficient inference on large machine learning models for LHC trigger performance.
method Cryptographic techniques like hashing and zkML for low latency, certifiable inference.
result Achieves nanosecond-order latency for LHC triggers, enabling dynamic low-level triggers.
This paper explores formal verification for autonomous systems, identifying limitations and proposing improvements.
problem Ensuring safety of autonomous systems like self-driving cars and drones.
method Formal verification techniques based on formal methods, analyzing three assumptions and their limitations.
result Preliminary work to improve the strength of evidence provided by formal verification.
Quantum crypto-economics: Blockchain prediction markets for the evolution of quantum technologyq-fin.PR
Quantum crypto-economics models price risks in blockchain technology.
problem Quantum technology's potential to undermine blockchain security.
method Building financial models to price quantum risk in blockchain scenarios.
result Quantum crypto-economics models can assess and price quantum risks in blockchain.
This work presents Origami, which provides privacy-preserving inference for large deep neural network (DNN) models through a combination of enclave execution, cryptographic blinding, interspersed with accelerator-based computation. Origami partitions the ML model into multiple partitions. The first partition receives t…
In the last decade, deep learning algorithms have become very popular thanks to the achieved performance in many machine learning and computer vision tasks. However, most of the deep learning architectures are vulnerable to so called adversarial examples. This questions the security of deep neural networks (DNN) for ma…
This paper strengthens the computational separation between multimodal and unimodal learning, showing unimodal learning is hard on typical instances.
problem Theoretical justification for empirical success of multimodal machine learning.
method Introduced a stronger average-case computational separation between unimodal and multimodal learning.
result For typical instances, unimodal learning is computationally hard, while multimodal learning is easy.
Paper proposes scalable privacy-preserving DNN for industrial applications.
problem Data isolation and scalability issues in deep neural networks.
method Split computation graph into private and neutral server parts; use cryptographic techniques for private data.
result Demonstrates practicality of the proposed scalable privacy-preserving DNN.
Hardness proven for learning neural networks with polynomial size and Gaussian inputs.
problem Learning one hidden layer ReLU neural networks with polynomial size and Gaussian inputs.
method Based on the hardness of the Continuous Learning with Errors (CLWE) problem.
result Hardness of learning neural networks is proven under standard cryptographic assumptions.
Over recent years, devising classification algorithms that are robust to adversarial perturbations has emerged as a challenging problem. In particular, deep neural nets (DNNs) seem to be susceptible to small imperceptible changes over test instances. However, the line of work in provable robustness, so far, has been fo…
Local regularization fails in transductive learning for some multiclass problems.
problem Whether local regularization can learn all transductive multiclass problems.
method Provided a negative answer by exhibiting a specific multiclass problem.
result Local regularization cannot learn all transductive multiclass problems.
Backdoors in deep neural networks are undetectable and enable invariance-based adversarial examples.
problem Statistically undetectable backdoors in deep neural networks.
method Adversarial model trainer method to plant backdoors, showing invariance-based adversarial examples.
result Backdoors are statistically undetectable and enable generation of adversarial examples for every input.
Approach to verify neural network training integrity.
problem Poisoning attacks during neural network training.
method Use of cryptographic mechanisms to verify training integrity.
result Provable verification of neural network training integrity.
Framework certifies fairness of machine learning models interactively and privately.
problem Certifying fairness of machine learning models in privacy-preserving scenarios.
method Interactive test with cryptographic techniques for fairness certification.
result Empirical evaluation of fairness for various models and definitions.
We consider the problem of Bayesian learning on sensitive datasets and present two simple but somewhat surprising results that connect Bayesian learning to "differential privacy:, a cryptographic approach to protect individual-level privacy while permiting database-level utility. Specifically, we show that that under s…
Federated learning platform for drug discovery without sharing data.
problem Lack of secure collaboration in drug discovery.
method Industry-scale federated learning platform using cryptographic aggregation.
result Generated new scientific discoveries in drug discovery.
CryptoNAS improves PI accuracy by 3.4% with 2.4x less latency.
problem Private inference on machine learning models with limited latency.
method Developed CryptoNAS, a novel NAS method for finding models that maximize accuracy within a ReLU budget.
result Improves accuracy by 3.4% and latency by 2.4x over state-of-the-art methods.
There are recent cryptographic protocols that are based on Multiple Simultaneous Conjugacy Problems in braid groups. We improve an algorithm, due to Sang Jin Lee and Eonkyung Lee, to solve these problems, by applying a method developed by the author and Nuno Franco, originally intended to solve the Conjugacy Search Pro…
Privacy is a major issue in learning from distributed data. Recently the cryptographic literature has provided several tools for this task. However, these tools either reduce the quality/accuracy of the learning algorithm---e.g., by adding noise---or they incur a high performance penalty and/or involve trusting externa…
Safe-House secures DeFi by limiting losses and enhancing security.
problem Ongoing hacks and security concerns in DeFi.
method Safe-House uses blockchain principles to secure asset movements.
result Safe-House limits maximum one-time loss to specified limits.
Paper investigates hardness of learning neural networks under manifold hypothesis.
problem Hardness of learning neural networks under the manifold hypothesis.
method Extending proofs of hardness in the SQ and cryptographic settings to the geometric setting.
result Learning is hard under input manifolds of bounded curvature but learnable with additional assumptions on manifold volume.
AriaNN enables private deep learning with minimal interaction and reduced key sizes.
problem Private deep learning with minimal interaction and reduced key sizes.
method Semi-honest 2-party computation protocol with function secret sharing, optimized primitives for neural network operations.
result Efficient private comparison for ReLU operations with reduced key size and improved performance.
We discuss several uses of blockchain (and, more generally, distributed ledger) technologies outside of cryptocurrencies with a pragmatic view. We mostly focus on three areas: the role of coin economies for what we refer to as data malls (specialized data marketplaces); data provenance (a historical record of data and …
How to train a machine learning model while keeping the data private and secure? We present CodedPrivateML, a fast and scalable approach to this critical problem. CodedPrivateML keeps both the data and the model information-theoretically private, while allowing efficient parallelization of training across distributed w…
Advances in fractional analysis suggest a new way for the physics understanding of Riemann's conjecture. It asserts that, if s is a complex number, the non trivial zeros of zeta function in the gap [0,1], is characterized by . This conjecture can be understood as a consequence of 1/2-order fractional differential chara…
New spoofing strategies show PoL verification is more vulnerable than previously thought.
problem Vulnerability of Proof-of-Learning verification mechanisms.
method Developed new spoofing strategies that can be reproduced across different configurations and are more cost-effective.
result Current PoL verification is not robust to adversaries and requires further understanding of optimization in deep learning.
Post-quantum cryptography needed for blockchain security.
problem Quantum computers threaten traditional blockchain cryptography.
method Review of theoretical cryptography and quantum information theory.
result Post-quantum cryptography is essential for blockchain security.
We propose a new randomized ensemble technique with a provable security guarantee against black-box transfer attacks. Our proof constructs a new security problem for random binary classifiers which is easier to empirically verify and a reduction from the security of this new model to the security of the ensemble classi…
This study calculates the maximum error of a famous estimation method.
problem Estimating rare items not seen in a sample.
method Characterizes the maximal mean-squared error of the Good-Turing estimator.
result Characterizes the maximal mean-squared error of the Good-Turing estimator.
Proposes measuring fairness through multiple stakeholder-curated stress tests.
problem Limited power of rigid fairness metrics and lack of stakeholder involvement in fairness discussions.
method Shift focus from fairness metrics to stress tests curated by stakeholders.
result Machine's performance under multiple stress tests reflects fairness.
As neural networks revolutionize many applications, significant privacy conflicts between model users and providers emerge. The cryptography community developed a variety of techniques for secure computation to address such privacy issues. As generic techniques for secure computation are typically prohibitively ineffec…
Study selective classification with halfspaces, achieving error bounds under Gaussian distributions.
problem Modeling relationships in subsets of data defined by selection rules.
method Sparse linear classifiers for subsets defined by halfspaces, focusing on Gaussian feature distributions.
result First PAC-learning algorithm for homogeneous halfspace selectors with error guarantee $\bigO*{\sqrt{\mathrm{opt}}}$.
Neural Networks (NN) have recently emerged as backbone of several sensitive applications like automobile, medical image, security, etc. NNs inherently offer Partial Fault Tolerance (PFT) in their architecture; however, the biased PFT of NNs can lead to severe consequences in applications like cryptography and security …
We continue the study of statistical/computational tradeoffs in learning robust classifiers, following the recent work of Bubeck, Lee, Price and Razenshteyn who showed examples of classification tasks where (a) an efficient robust classifier exists, in the small-perturbation regime; (b) a non-robust classifier can be l…
Study on computational aspects of replicable learning, bridging statistical and algorithmic perspectives.
problem Understanding the computational connections between replicability and various learning paradigms.
method Design of replicable learners, lifting framework, and transformation techniques.
result Efficient replicable learners for specific learning problems under various distributions.
We present two new statistical machine learning methods designed to learn on fully homomorphic encrypted (FHE) data. The introduction of FHE schemes following Gentry (2009) opens up the prospect of privacy preserving statistical machine learning analysis and modelling of encrypted data without compromising security con…
Novel algorithm for privacy-preserving distributed learning in analog domain.
problem Privacy-preserving distributed learning over analog data.
method Proposes a novel algorithm for analog data, leveraging real/complex number representation and information-theoretic security metrics.
result Demonstrates a fundamental trade-off between privacy and accuracy in analog domain distributed learning.
Paper introduces privacy-preserving few-shot learning for images.
problem Privacy risk in few-shot learning systems.
method Discrete embedding vectors and one-way hash functions.
result Achieves computational pan privacy without storing embeddings.