8 Search Results for "Nanashima, Mikito"

Document
DOI: 10.4230/LIPIcs.CCC.2024.29
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity

Authors: Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
A search-to-decision reduction is a procedure that allows one to find a solution to a problem from the mere ability to decide when a solution exists. The existence of a search-to-decision reduction for time-bounded Kolmogorov complexity, i.e., the problem of checking if a string x can be generated by a t-time bounded program of description length s, is a long-standing open problem that dates back to the 1960s. In this work, we obtain new average-case and worst-case search-to-decision reductions for the complexity measure 𝖪^t and its randomized analogue rK^t: 1) (Conditional Errorless and Error-Prone Reductions for 𝖪^t) Under the assumption that 𝖤 requires exponential size circuits, we design polynomial-time average-case search-to-decision reductions for 𝖪^t in both errorless and error-prone settings. In fact, under the easiness of deciding 𝖪^t under the uniform distribution, we obtain a search algorithm for any given polynomial-time samplable distribution. In the error-prone reduction, the search algorithm works in the more general setting of conditional 𝖪^t complexity, i.e., it finds a minimum length t-time bound program for generating x given a string y. 2) (Unconditional Errorless Reduction for rK^t) We obtain an unconditional polynomial-time average-case search-to-decision reduction for rK^t in the errorless setting. Similarly to the results described above, we obtain a search algorithm for each polynomial-time samplable distribution, assuming the existence of a decision algorithm under the uniform distribution. To our knowledge, this is the first unconditional sub-exponential time search-to-decision reduction among the measures 𝖪^t and rK^t that works with respect to any given polynomial-time samplable distribution. 3) (Worst-Case to Average-Case Reductions) Under the errorless average-case easiness of deciding rK^t, we design a worst-case search algorithm running in time 2^O(n/log n) that produces a minimum length randomized t-time program for every input string x ∈ {0,1}ⁿ, with the caveat that it only succeeds on some explicitly computed sub-exponential time bound t ≤ 2^{n^ε} that depends on x. A similar result holds for 𝖪^t, under the assumption that 𝖤 requires exponential size circuits. In these results, the corresponding search problem is solved exactly, i.e., a successful run of the search algorithm outputs a t-time bounded program for x of minimum length, as opposed to an approximately optimal program of slightly larger description length or running time.
Cite as

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 29:1-29:56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.CCC.2024.29,
  author =	{Hirahara, Shuichi and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{29:1--29:56},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.29},
  URN =		{urn:nbn:de:0030-drops-204256},
  doi =		{10.4230/LIPIcs.CCC.2024.29},
  annote =	{Keywords: average-case complexity, Kolmogorov complexity, search-to-decision reductions}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.110
Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity

Authors: Zhenjian Lu and Rahul Santhanam

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We develop new characterizations of Impagliazzo’s worlds Algorithmica, Heuristica and Pessiland by the intractability of conditional Kolmogorov complexity 𝖪 and conditional probabilistic time-bounded Kolmogorov complexity pK^t. In our first set of results, we show that NP ⊆ BPP iff pK^t(x ∣ y) can be computed efficiently in the worst case when t is sublinear in |x| + |y|; DistNP ⊆ HeurBPP iff pK^t(x ∣ y) can be computed efficiently over all polynomial-time samplable distributions when t is sublinear in |x| + |y|; and infinitely-often one-way functions fail to exist iff pK^t(x ∣ y) can be computed efficiently over all polynomial-time samplable distributions for t a sufficiently large polynomial in |x| + |y|. These results characterize Impagliazzo’s worlds Algorithmica, Heuristica and Pessiland purely in terms of the tractability of conditional pK^t. Notably, the results imply that Pessiland fails to exist iff the average-case intractability of conditional pK^t is insensitive to the difference between sublinear and polynomially bounded t. As a corollary, while we prove conditional pK^t to be NP-hard for sublinear t, showing NP-hardness for large enough polynomially bounded t would eliminate Pessiland as a possible world of average-case complexity. In our second set of results, we characterize Impagliazzo’s worlds Algorithmica, Heuristica and Pessiland by the distributional tractability of a natural problem, i.e., approximating the conditional Kolmogorov complexity, that is provably intractable in the worst case. We show that NP ⊆ BPP iff conditional Kolmogorov complexity can be approximated in the semi-worst case; and DistNP ⊆ HeurBPP iff conditional Kolmogorov complexity can be approximated on average over all independent polynomial-time samplable distributions. It follows from a result by Ilango, Ren, and Santhanam (STOC 2022) that infinitely-often one-way functions fail to exist iff conditional Kolmogorov complexity can be approximated on average over all polynomial-time samplable distributions. Together, these results yield the claimed characterizations. Our techniques, combined with previous work, also yield a characterization of auxiliary-input one-way functions and equivalences between different average-case tractability assumptions for conditional Kolmogorov complexity and its variants. Our results suggest that novel average-case tractability assumptions such as tractability in the semi-worst case and over independent polynomial-time samplable distributions might be worthy of further study.
Cite as

Zhenjian Lu and Rahul Santhanam. Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 110:1-110:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ICALP.2024.110,
  author =	{Lu, Zhenjian and Santhanam, Rahul},
  title =	{{Impagliazzo’s Worlds Through the Lens of Conditional Kolmogorov Complexity}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{110:1--110:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.110},
  URN =		{urn:nbn:de:0030-drops-202538},
  doi =		{10.4230/LIPIcs.ICALP.2024.110},
  annote =	{Keywords: meta-complexity, Kolmogorov complexity, one-way functions, average-case complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.70
Learning Versus Pseudorandom Generators in Constant Parallel Time

Authors: Shuichi Hirahara and Mikito Nanashima

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
A polynomial-stretch pseudorandom generator (PPRG) in NC⁰ (i.e., constant parallel time) is one of the most important cryptographic primitives, especially for constructing highly efficient cryptography and indistinguishability obfuscation. The celebrated work (Applebaum, Ishai, and Kushilevitz, SIAM Journal on Computing, 2006) on randomized encodings yields the characterization of sublinear-stretch pseudorandom generators in NC⁰ by the existence of logspace-computable one-way functions, but characterizing PPRGs in NC⁰ seems out of reach at present. Therefore, it is natural to ask which sort of hardness notion is essential for constructing PPRGs in NC⁰. Particularly, to the best of our knowledge, all the previously known candidates for PPRGs in NC⁰ follow only one framework based on Goldreich’s one-way function. In this paper, we present a new learning-theoretic characterization for PPRGs in NC⁰ and related classes. Specifically, we consider the average-case hardness of learning for well-studied classes in parameterized settings, where the number of samples is restricted to fixed-parameter tractable (FPT), and show that the following are equivalent: - The existence of (a collection of) PPRGs in NC⁰. - The average-case hardness of learning sparse 𝔽₂-polynomials on a sparse example distribution and an NC⁰-samplable target distribution (i.e., a distribution on target functions). - The average-case hardness of learning Fourier-sparse functions on a sparse example distribution and an NC⁰-samplable target distribution. - The average-case hardness of learning constant-depth parity decision trees on a sparse example distribution and an NC⁰-samplable target distribution. Furthermore, we characterize a (single) PPRG in parity-NC⁰ by the average-case hardness of learning constant-degree 𝔽₂-polynomials on a uniform example distribution with FPT samples. Based on our results, we propose new candidates for PPRGs in NC⁰ and related classes under a hardness assumption on a natural learning problem. An important property of PPRGs in NC⁰ constructed in our framework is that the output bits are computed by various predicates; thus, it seems to resist an attack that depends on a specific property of one fixed predicate. Conceptually, the main contribution of this study is to formalize a theory of FPT dualization of concept classes, which yields a meta-theorem for the first result. For the second result on PPRGs in parity-NC⁰, we use a different technique of pseudorandom 𝔽₂-polynomials.
Cite as

Shuichi Hirahara and Mikito Nanashima. Learning Versus Pseudorandom Generators in Constant Parallel Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ITCS.2023.70,
  author =	{Hirahara, Shuichi and Nanashima, Mikito},
  title =	{{Learning Versus Pseudorandom Generators in Constant Parallel Time}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{70:1--70:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.70},
  URN =		{urn:nbn:de:0030-drops-175736},
  doi =		{10.4230/LIPIcs.ITCS.2023.70},
  annote =	{Keywords: Parallel cryptography, polynomial-stretch pseudorandom generators in NC⁰, PAC learning, average-case complexity, fixed-parameter tractability}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.16
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Authors: Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Understanding the relationship between the worst-case and average-case complexities of NP and of other subclasses of PH is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its time-bounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from meta-complexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (time-bounded Kolmogorov complexity) of different objects is crucial in recent applications of meta-complexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of average-case complexity [Russell Impagliazzo and Leonid A. Levin, 1990]. In this work, we develop a probabilistic theory of meta-complexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of time-bounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from meta-complexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worst-case and average-case complexity in the important setting of probabilistic computations: - If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)]. - If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)]. - In the fine-grained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger average-case assumptions. - If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any 𝓁 ≥ 0, if DistΣ_{𝓁+2}^P ⊆ AvgBPP then Σ_𝓁^{P} ⊆ BPTIME[2^O(n/log n)]. - Strengthening a result from [Shuichi Hirahara and Mikito Nanashima, 2021], we show that if DistNP ⊆ AvgBPP then polynomial size Boolean circuits can be agnostically PAC learned under any unknown 𝖯/poly-samplable distribution in polynomial time. In some cases, our framework allows us to significantly simplify existing proofs, or to extend results to the more challenging probabilistic setting with little to no extra effort.
Cite as

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goldberg_et_al:LIPIcs.CCC.2022.16,
  author =	{Goldberg, Halley and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.},
  title =	{{Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{16:1--16:60},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.16},
  URN =		{urn:nbn:de:0030-drops-165785},
  doi =		{10.4230/LIPIcs.CCC.2022.16},
  annote =	{Keywords: average-case complexity, Kolmogorov complexity, meta-complexity, worst-case to average-case reductions, learning}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.25
Finding Errorless Pessiland in Error-Prone Heuristica

Authors: Shuichi Hirahara and Mikito Nanashima

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Average-case complexity has two standard formulations, i.e., errorless complexity and error-prone complexity. In average-case complexity, a critical topic of research is to show the equivalence between these formulations, especially on the average-case complexity of NP. In this study, we present a relativization barrier for such an equivalence. Specifically, we construct an oracle relative to which NP is easy on average in the error-prone setting (i.e., DistNP ⊆ HeurP) but hard on average in the errorless setting even by 2^o(n/log n)-size circuits (i.e., DistNP ⊈ AvgSIZE[2^o(n/log n)]), which provides an answer to the open question posed by Impagliazzo (CCC 2011). Additionally, we show the following in the same relativized world: - Lower bound of meta-complexity: GapMINKT^𝒪 ∉ prSIZE^𝒪[2^o(n/log n)] and GapMCSP^𝒪 ∉ prSIZE^𝒪[2^(n^ε)] for some ε > 0. - Worst-case hardness of learning on uniform distributions: P/poly is not weakly PAC learnable with membership queries on the uniform distribution by nonuniform 2ⁿ/n^ω(1)-time algorithms. - Average-case hardness of distribution-free learning: P/poly is not weakly PAC learnable on average by nonuniform 2^o(n/log n)-time algorithms. - Weak cryptographic primitives: There exist a hitting set generator, an auxiliary-input one-way function, an auxiliary-input pseudorandom generator, and an auxiliary-input pseudorandom function against SIZE^𝒪[2^o(n/log n)]. This provides considerable insights into Pessiland (i.e., the world in which no one-way function exists, and NP is hard on average), such as the relativized separation of the error-prone average-case hardness of NP and auxiliary-input cryptography. At the core of our oracle construction is a new notion of random restriction with masks.
Cite as

Shuichi Hirahara and Mikito Nanashima. Finding Errorless Pessiland in Error-Prone Heuristica. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 25:1-25:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.CCC.2022.25,
  author =	{Hirahara, Shuichi and Nanashima, Mikito},
  title =	{{Finding Errorless Pessiland in Error-Prone Heuristica}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{25:1--25:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.25},
  URN =		{urn:nbn:de:0030-drops-165875},
  doi =		{10.4230/LIPIcs.CCC.2022.25},
  annote =	{Keywords: average-case complexity, oracle separation, relativization barrier, meta-complexity, learning, auxiliary-input cryptography}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.26
Symmetry of Information from Meta-Complexity

Authors: Shuichi Hirahara

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Symmetry of information for time-bounded Kolmogorov complexity is a hypothetical inequality that relates time-bounded Kolmogorov complexity and its conditional analogue. In 1992, Longpré and Watanabe showed that symmetry of information holds if NP is easy in the worst case, which has been the state of the art over the last three decades. In this paper, we significantly improve this result by showing that symmetry of information holds under the weaker assumption that NP is easy on average. In fact, our proof techniques are applicable to any resource-bounded Kolmogorov complexity and enable proving symmetry of information from an efficient algorithm that computes resource-bounded Kolmogorov complexity. We demonstrate the significance of our proof techniques by presenting two applications. First, using that symmetry of information does not hold for Levin’s Kt-complexity, we prove that randomized Kt-complexity cannot be computed in time 2^o(n) on inputs of length n, which improves the previous quasi-polynomial lower bound of Oliveira (ICALP 2019). Our proof implements Kolmogorov’s insightful approach to the P versus NP problem in the case of randomized Kt-complexity. Second, we consider the question of excluding Heuristica, i.e., a world in which NP is easy on average but NP ≠ P, from Impagliazzo’s five worlds: Using symmetry of information, we prove that Heuristica is excluded if the problem of approximating time-bounded conditional Kolmogorov complexity K^t(x∣y) up to some additive error is NP-hard for t ≫ |y|. We complement this result by proving NP-hardness of approximating sublinear-time-bounded conditional Kolmogorov complexity up to a multiplicative factor of |x|^{1/(log log |x|)^O(1)} for t ≪ |y|. Our NP-hardness proof presents a new connection between sublinear-time-bounded conditional Kolmogorov complexity and a secret sharing scheme.
Cite as

Shuichi Hirahara. Symmetry of Information from Meta-Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 26:1-26:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hirahara:LIPIcs.CCC.2022.26,
  author =	{Hirahara, Shuichi},
  title =	{{Symmetry of Information from Meta-Complexity}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{26:1--26:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.26},
  URN =		{urn:nbn:de:0030-drops-165880},
  doi =		{10.4230/LIPIcs.CCC.2022.26},
  annote =	{Keywords: resource-bounded Kolmogorov complexity, average-case complexity, pseudorandomness, hardness of approximation, unconditional lower bound}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2021.7
One-Way Functions and a Conditional Variant of MKTP

Authors: Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
One-way functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the average-case hardness of computing time-bounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the average-case hardness of some natural NP-complete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KT-complexity Problem (MKTP), which we call McKTP, as follows. 1) First, we prove that if McKTP is average-case hard on a polynomial fraction of its instances, then there exist OWFs. 2) Then, we observe that McKTP is NP-complete under polynomial-time randomized reductions. 3) Finally, we prove that the existence of OWFs implies the nontrivial average-case hardness of McKTP. Thus the existence of OWFs is inextricably linked to the average-case hardness of this NP-complete problem. In fact, building on recently-announced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hard-on-average if and only if there are logspace-computable OWFs.
Cite as

Eric Allender, Mahdi Cheraghchi, Dimitrios Myrisiotis, Harsha Tirumala, and Ilya Volkovich. One-Way Functions and a Conditional Variant of MKTP. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.FSTTCS.2021.7,
  author =	{Allender, Eric and Cheraghchi, Mahdi and Myrisiotis, Dimitrios and Tirumala, Harsha and Volkovich, Ilya},
  title =	{{One-Way Functions and a Conditional Variant of MKTP}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.7},
  URN =		{urn:nbn:de:0030-drops-155181},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.7},
  annote =	{Keywords: Kolmogorov complexity, KT Complexity, Minimum KT-complexity Problem, MKTP, Conditional KT Complexity, Minimum Conditional KT-complexity Problem, McKTP, one-way functions, OWFs, average-case hardness, pseudorandom generators, PRGs, pseudorandom functions, PRFs, distinguishers, learning algorithms, NP-completeness, reductions}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.29
On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions

Authors: Mikito Nanashima

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Constructing one-way functions based on NP-hardness is a central challenge in theoretical computer science. Unfortunately, Akavia et al. [Akavia et al., 2006] presented strong evidence that a nonadaptive black-box (BB) reduction is insufficient to solve this challenge. However, should we give up such a central proof technique even for an intermediate step? In this paper, we turn our eyes from standard cryptographic primitives to weaker cryptographic primitives allowed to take auxiliary-input and continue to explore the capability of nonadaptive BB reductions to base auxiliary-input primitives on NP-hardness. Specifically, we prove the followings: - if we base an auxiliary-input pseudorandom generator (AIPRG) on NP-hardness via a nonadaptive BB reduction, then the polynomial hierarchy collapses; - if we base an auxiliary-input one-way function (AIOWF) or auxiliary-input hitting set generator (AIHSG) on NP-hardness via a nonadaptive BB reduction, then an (i.o.-)one-way function also exists based on NP-hardness (via an adaptive BB reduction). These theorems extend our knowledge on nonadaptive BB reductions out of the current worst-to-average framework. The first result provides new evidence that nonadaptive BB reductions are insufficient to base AIPRG on NP-hardness. The second result also yields a weaker but still surprising consequence of nonadaptive BB reductions, i.e., a one-way function based on NP-hardness. In fact, the second result is interpreted in the following two opposite ways. Pessimistically, it shows that basing AIOWF or AIHSG on NP-hardness via nonadaptive BB reductions is harder than constructing a one-way function based on NP-hardness, which can be regarded as a negative result. Note that AIHSG is a weak primitive implied even by the hardness of learning; thus, this pessimistic view provides conceptually stronger limitations than the currently known limitations on nonadaptive BB reductions. Optimistically, it offers a new hope: breakthrough construction of auxiliary-input primitives might also provide construction standard cryptographic primitives. This optimistic view enhances the significance of further investigation on constructing auxiliary-input or other intermediate cryptographic primitives instead of standard cryptographic primitives.
Cite as

Mikito Nanashima. On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{nanashima:LIPIcs.ITCS.2021.29,
  author =	{Nanashima, Mikito},
  title =	{{On Basing Auxiliary-Input Cryptography on NP-Hardness via Nonadaptive Black-Box Reductions}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.29},
  URN =		{urn:nbn:de:0030-drops-135686},
  doi =		{10.4230/LIPIcs.ITCS.2021.29},
  annote =	{Keywords: Auxiliary-input cryptographic primitives, nonadaptive black-box reductions}
}
  • Refine by Author
  • 4 Hirahara, Shuichi
  • 3 Lu, Zhenjian
  • 3 Nanashima, Mikito
  • 2 Kabanets, Valentine
  • 2 Oliveira, Igor C.
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Computational complexity and cryptography
  • 2 Theory of computation → Cryptographic primitives
  • 1 Theory of computation → Boolean function learning
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 6 average-case complexity
  • 4 Kolmogorov complexity
  • 3 meta-complexity
  • 2 learning
  • 2 one-way functions
  • Show More...

  • Refine by Type
  • 8 document

  • Refine by Publication Year
  • 3 2022
  • 2 2021
  • 2 2024
  • 1 2023

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact