3 Search Results for "Smith, Caleb"

Document
DOI: 10.4230/LIPIcs.CCC.2025.34
Witness Encryption and NP-Hardness of Learning

Authors: Halley Goldberg and Valentine Kabanets

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
We study connections between two fundamental questions from computer science theory. (1) Is witness encryption possible for NP [Sanjam Garg et al., 2013]? That is, given an instance x of an NP-complete language L, can one encrypt a secret message with security contingent on the ability to provide a witness for x ∈ L? (2) Is computational learning (in the sense of [Leslie G. Valiant, 1984; Michael J. Kearns et al., 1994]) hard for NP? That is, is there a polynomial-time reduction from instances of L to instances of learning? Our main contribution is that certain formulations of NP-hardness of learning characterize the existence of witness encryption for NP. More specifically, we show: - witness encryption for a language L ∈ NP is equivalent to a half-Levin reduction from L to the Computational Gap Learning problem (denoted CGL [Benny Applebaum et al., 2008]), where a half-Levin reduction is the same as a Levin reduction but only required to preserve witnesses in one direction, and CGL formalizes agnostic learning as a decision problem. We show versions of the statement above for witness encryption secure against non-uniform and uniform adversaries. We also show that witness encryption for NP with ciphertexts of logarithmic length, along with a circuit lower bound for E, are together equivalent to NP-hardness of a generalized promise version of MCSP. We complement the above with a number of unconditional NP-hardness results for agnostic PAC learning. Extending a result of [Shuichi Hirahara, 2022] to the standard setting of boolean circuits, we show NP-hardness of "semi-proper" learning. Namely: - for some polynomial s, it is NP-hard to agnostically learn circuits of size s(n) by circuits of size s(n)⋅ n^{1/(log log n)^O(1)}. Looking beyond the computational model of standard boolean circuits enables us to prove NP-hardness of improper learning (ie. without a restriction on the size of hypothesis returned by the learner). We obtain such results for: - learning circuits with oracle access to a given randomly sampled string, and - learning RAM programs. In particular, we show that a variant of MINLT [Ker-I Ko, 1991] for RAM programs is NP-hard with parameters corresponding to the setting of improper learning. We view these results as partial progress toward the ultimate goal of showing NP-hardness of learning boolean circuits in an improper setting. Lastly, we give some consequences of NP-hardness of learning for private- and public-key cryptography. Improving a main result of [Benny Applebaum et al., 2008], we show that if improper agnostic PAC learning is NP-hard under a randomized non-adaptive reduction (with some restrictions), then NP ⊈ BPP implies the existence of i.o. one-way functions. In contrast, if CGL is NP-hard under a half-Levin reduction, then NP ⊈ BPP implies the existence of i.o. public-key encryption.
Cite as

Halley Goldberg and Valentine Kabanets. Witness Encryption and NP-Hardness of Learning. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 34:1-34:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2025.34,
  author =	{Goldberg, Halley and Kabanets, Valentine},
  title =	{{Witness Encryption and NP-Hardness of Learning}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{34:1--34:43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.34},
  URN =		{urn:nbn:de:0030-drops-237281},
  doi =		{10.4230/LIPIcs.CCC.2025.34},
  annote =	{Keywords: agnostic PAC learning, witness encryption, NP-hardness}
}
Document
Introduction
DOI: 10.4230/LITES.8.1.0
Introduction to the Special Issue on Embedded Systems for Computer Vision

Authors: Samarjit Chakraborty and Qing Rao

Published in: LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1

Abstract
We provide a broad overview of some of the current research directions at the intersection of embedded systems and computer vision, in addition to introducing the papers appearing in this special issue. Work at this intersection is steadily growing in importance, especially in the context of autonomous and cyber-physical systems design. Vision-based perception is almost a mandatory component in any autonomous system, but also adds myriad challenges like, how to efficiently implement vision processing algorithms on resource-constrained embedded architectures, and how to verify the functional and timing correctness of these algorithms. Computer vision is also crucial in implementing various smart functionality like security, e.g., using facial recognition, or monitoring events or traffic patterns. Some of these applications are reviewed in this introductory article. The remaining articles featured in this special issue dive into more depth on a few of them.
Cite as

LITES, Volume 8, Issue 1: Special Issue on Embedded Systems for Computer Vision, pp. 0:i-0:viii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{chakraborty_et_al:LITES.8.1.0,
  author =	{Chakraborty, Samarjit and Rao, Qing},
  title =	{{Introduction to the Special Issue on Embedded Systems for Computer Vision}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{00:1--00:8},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.1.0},
  URN =		{urn:nbn:de:0030-drops-192871},
  doi =		{10.4230/LITES.8.1.0},
  annote =	{Keywords: Embedded systems, Computer vision, Cyber-physical systems, Computer architecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.83
Can Verifiable Delay Functions Be Based on Random Oracles?

Authors: Mohammad Mahmoody, Caleb Smith, and David J. Wu

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Boneh, Bonneau, Bünz, and Fisch (CRYPTO 2018) recently introduced the notion of a verifiable delay function (VDF). VDFs are functions that take a long sequential time T to compute, but whose outputs y := Eval(x) can be efficiently verified (possibly given a proof π) in time t ≪ T (e.g., t = poly(λ, log T) where λ is the security parameter). The first security requirement on a VDF, called uniqueness, is that no polynomial-time algorithm can find a convincing proof π' that verifies for an input x and a different output y' ≠ y. The second security requirement, called sequentiality, is that no polynomial-time algorithm running in time σ < T for some parameter σ (e.g., σ = T^{1/10}) can compute y, even with poly(T,λ) many parallel processors. Starting from the work of Boneh et al., there are now multiple constructions of VDFs from various algebraic assumptions. In this work, we study whether VDFs can be constructed from ideal hash functions in a black-box way, as modeled in the random oracle model (ROM). In the ROM, we measure the running time by the number of oracle queries and the sequentiality by the number of rounds of oracle queries. We rule out two classes of constructions of VDFs in the ROM: - We show that VDFs satisfying perfect uniqueness (i.e., VDFs where no different convincing solution y' ≠ y exists) cannot be constructed in the ROM. More formally, we give an attacker that finds the solution y in ≈ t rounds of queries, asking only poly(T) queries in total. - We also rule out tight verifiable delay functions in the ROM. Tight verifiable delay functions, recently studied by Döttling, Garg, Malavolta, and Vasudevan (ePrint Report 2019), require sequentiality for σ ≈ T-T^ρ for some constant 0 < ρ < 1. More generally, our lower bound also applies to proofs of sequential work (i.e., VDFs without the uniqueness property), even in the private verification setting, and sequentiality σ > T-(T)/(2t) for a concrete verification time t.
Cite as

Mohammad Mahmoody, Caleb Smith, and David J. Wu. Can Verifiable Delay Functions Be Based on Random Oracles?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 83:1-83:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mahmoody_et_al:LIPIcs.ICALP.2020.83,
  author =	{Mahmoody, Mohammad and Smith, Caleb and Wu, David J.},
  title =	{{Can Verifiable Delay Functions Be Based on Random Oracles?}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{83:1--83:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.83},
  URN =		{urn:nbn:de:0030-drops-124907},
  doi =		{10.4230/LIPIcs.ICALP.2020.83},
  annote =	{Keywords: verifiable delay function, lower bound, random oracle model}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 1 2020

  • Refine by Author
  • 1 Chakraborty, Samarjit
  • 1 Goldberg, Halley
  • 1 Kabanets, Valentine
  • 1 Mahmoody, Mohammad
  • 1 Rao, Qing
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs
  • 1 LITES

  • Refine by Classification
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Cryptographic primitives

  • Refine by Keyword
  • 1 Computer architecture
  • 1 Computer vision
  • 1 Cyber-physical systems
  • 1 Embedded systems
  • 1 NP-hardness
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact