12 Search Results for "Cheraghchi, Mahdi"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.55
High-Probability List-Recovery, and Applications to Heavy Hitters

Authors: Dean Doron and Mary Wootters

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
An error correcting code 𝒞 : Σ^k → Σⁿ is efficiently list-recoverable from input list size 𝓁 if for any sets ℒ₁, …, ℒ_n ⊆ Σ of size at most 𝓁, one can efficiently recover the list ℒ = {x ∈ Σ^k : ∀ j ∈ [n], 𝒞(x)_j ∈ ℒ_j}. While list-recovery has been well-studied in error correcting codes, all known constructions with "efficient" algorithms are not efficient in the parameter 𝓁. In this work, motivated by applications in algorithm design and pseudorandomness, we study list-recovery with the goal of obtaining a good dependence on 𝓁. We make a step towards this goal by obtaining it in the weaker case where we allow a randomized encoding map and a small failure probability, and where the input lists are derived from unions of codewords. As an application of our construction, we give a data structure for the heavy hitters problem in the strict turnstile model that, for some parameter regimes, obtains stronger guarantees than known constructions.
Cite as

Dean Doron and Mary Wootters. High-Probability List-Recovery, and Applications to Heavy Hitters. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{doron_et_al:LIPIcs.ICALP.2022.55,
  author =	{Doron, Dean and Wootters, Mary},
  title =	{{High-Probability List-Recovery, and Applications to Heavy Hitters}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.55},
  URN =		{urn:nbn:de:0030-drops-163961},
  doi =		{10.4230/LIPIcs.ICALP.2022.55},
  annote =	{Keywords: List recoverable codes, Heavy Hitters, high-dimensional expanders}
}
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-dev.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.CCC.2021.35
Hardness of KT Characterizes Parallel Cryptography

Authors: Hanlin Ren and Rahul Santhanam

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
A recent breakthrough of Liu and Pass (FOCS'20) shows that one-way functions exist if and only if the (polynomial-)time-bounded Kolmogorov complexity, K^t, is bounded-error hard on average to compute. In this paper, we strengthen this result and extend it to other complexity measures: - We show, perhaps surprisingly, that the KT complexity is bounded-error average-case hard if and only if there exist one-way functions in constant parallel time (i.e. NC⁰). This result crucially relies on the idea of randomized encodings. Previously, a seminal work of Applebaum, Ishai, and Kushilevitz (FOCS'04; SICOMP'06) used the same idea to show that NC⁰-computable one-way functions exist if and only if logspace-computable one-way functions exist. - Inspired by the above result, we present randomized average-case reductions among the NC¹-versions and logspace-versions of K^t complexity, and the KT complexity. Our reductions preserve both bounded-error average-case hardness and zero-error average-case hardness. To the best of our knowledge, this is the first reduction between the KT complexity and a variant of K^t complexity. - We prove tight connections between the hardness of K^t complexity and the hardness of (the hardest) one-way functions. In analogy with the Exponential-Time Hypothesis and its variants, we define and motivate the Perebor Hypotheses for complexity measures such as K^t and KT. We show that a Strong Perebor Hypothesis for K^t implies the existence of (weak) one-way functions of near-optimal hardness 2^{n-o(n)}. To the best of our knowledge, this is the first construction of one-way functions of near-optimal hardness based on a natural complexity assumption about a search problem. - We show that a Weak Perebor Hypothesis for MCSP implies the existence of one-way functions, and establish a partial converse. This is the first unconditional construction of one-way functions from the hardness of MCSP over a natural distribution. - Finally, we study the average-case hardness of MKtP. We show that it characterizes cryptographic pseudorandomness in one natural regime of parameters, and complexity-theoretic pseudorandomness in another natural regime.
Cite as

Hanlin Ren and Rahul Santhanam. Hardness of KT Characterizes Parallel Cryptography. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 35:1-35:58, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ren_et_al:LIPIcs.CCC.2021.35,
  author =	{Ren, Hanlin and Santhanam, Rahul},
  title =	{{Hardness of KT Characterizes Parallel Cryptography}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{35:1--35:58},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.35},
  URN =		{urn:nbn:de:0030-drops-143091},
  doi =		{10.4230/LIPIcs.CCC.2021.35},
  annote =	{Keywords: one-way function, meta-complexity, KT complexity, parallel cryptography, randomized encodings}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.23
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

Authors: Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
For a size parameter s: ℕ → ℕ, the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}ⁿ → {0,1} (represented by a string of length N : = 2ⁿ) is at most a threshold s(n). A recent line of work exhibited "hardness magnification" phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μ₁ > 0, if MCSP[2^{μ₁⋅ n}] cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time N^{1.01}, then P≠NP. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: 1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute MCSP[2^{μ₂⋅n}] in time N^{1.99}, for some constant μ₂ > μ₁. 2) A non-deterministic (or parity) branching program of size o(N^{1.5}/log N) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. 3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least N^{1.5-o(1)}. These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola 2019). En route, we obtain several related results: 1) There exists a (local) hitting set generator with seed length Õ(√N) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. 2) Any read-once co-non-deterministic branching program computing MCSP must have size at least 2^Ω̃(N).
Cite as

Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2021.23,
  author =	{Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi},
  title =	{{One-Tape Turing Machine and Branching Program Lower Bounds for MCSP}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.23},
  URN =		{urn:nbn:de:0030-drops-136681},
  doi =		{10.4230/LIPIcs.STACS.2021.23},
  annote =	{Keywords: Minimum Circuit Size Problem, Kolmogorov Complexity, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.48
Pseudobinomiality of the Sticky Random Walk

Authors: Venkatesan Guruswami and Vinayak M. Kumar

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

Abstract
Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number M of marked vertices visited in a long n-step random walk strongly concentrates around the expected n/2 value. Surprisingly, it was recently shown that the parity of M also has exponentially small bias. Is there a common unification of these results? What other statistics about M resemble the binomial distribution (the Hamming weight of a random n-bit string)? To gain insight into such questions, we analyze a simpler model called the sticky random walk. This model is a natural stepping stone towards understanding expander random walks, and we also show that it is a necessary step. The sticky random walk starts with a random bit and then each subsequent bit independently equals the previous bit with probability (1+λ)/2. Here λ is the proxy for the expander’s (second largest) eigenvalue. Using Krawtchouk expansion of functions, we derive several probabilistic results about the sticky random walk. We show an asymptotically tight Θ(λ) bound on the total variation distance between the (Hamming weight of the) sticky walk and the binomial distribution. We prove that the correlation between the majority and parity bit of the sticky walk is bounded by O(n^{-1/4}). This lends hope to unifying Chernoff bounds and parity concentration, as well as establishing other interesting statistical properties, of expander random walks.
Cite as

Venkatesan Guruswami and Vinayak M. Kumar. Pseudobinomiality of the Sticky Random Walk. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.48,
  author =	{Guruswami, Venkatesan and Kumar, Vinayak M.},
  title =	{{Pseudobinomiality of the Sticky Random Walk}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{48:1--48:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.48},
  URN =		{urn:nbn:de:0030-drops-135870},
  doi =		{10.4230/LIPIcs.ITCS.2021.48},
  annote =	{Keywords: Expander Graphs, Fourier analysis, Markov Chains, Pseudorandomness, Random Walks}
}
Document
DOI: 10.4230/LIPIcs.CCC.2020.15
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates

Authors: Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira

Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)

Abstract
The class 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢 consists of Boolean functions computable by size-s de Morgan formulas whose leaves are any Boolean functions from a class 𝒢. We give lower bounds and (SAT, Learning, and PRG) algorithms for FORMULA[n^{1.99}]∘𝒢, for classes 𝒢 of functions with low communication complexity. Let R^(k)(𝒢) be the maximum k-party number-on-forehead randomized communication complexity of a function in 𝒢. Among other results, we show that: - The Generalized Inner Product function 𝖦𝖨𝖯^k_n cannot be computed in 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢 on more than 1/2+ε fraction of inputs for s = o(n²/{(k⋅4^k⋅R^(k)(𝒢)⋅log (n/ε)⋅log(1/ε))²}). This significantly extends the lower bounds against bipartite formulas obtained by [Avishay Tal, 2017]. As a corollary, we get an average-case lower bound for 𝖦𝖨𝖯^k_n against 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^{1.99}]∘𝖯𝖳𝖥^{k-1}, i.e., sub-quadratic-size de Morgan formulas with degree-(k-1) PTF (polynomial threshold function) gates at the bottom. - There is a PRG of seed length n/2 + O(√s⋅R^(2)(𝒢)⋅log(s/ε)⋅log(1/ε)) that ε-fools FORMULA[s]∘𝒢. For the special case of FORMULA[s]∘𝖫𝖳𝖥, i.e., size-s formulas with LTF (linear threshold function) gates at the bottom, we get the better seed length O(n^{1/2}⋅s^{1/4}⋅log(n)⋅log(n/ε)). In particular, this provides the first non-trivial PRG (with seed length o(n)) for intersections of n half-spaces in the regime where ε ≤ 1/n, complementing a recent result of [Ryan O'Donnell et al., 2019]. - There exists a randomized 2^{n-t}-time #SAT algorithm for 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[s]∘𝒢, where t = Ω(n/{√s⋅log²(s)⋅R^(2)(𝒢)})^{1/2}. In particular, this implies a nontrivial #SAT algorithm for 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖫𝖳𝖥. - The Minimum Circuit Size Problem is not in 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖷𝖮𝖱; thereby making progress on hardness magnification, in connection with results from [Igor Carboni Oliveira et al., 2019; Lijie Chen et al., 2019]. On the algorithmic side, we show that the concept class 𝖥𝖮𝖱𝖬𝖴𝖫𝖠[n^1.99]∘𝖷𝖮𝖱 can be PAC-learned in time 2^O(n/log n).
Cite as

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, and Igor C. Oliveira. Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 15:1-15:41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kabanets_et_al:LIPIcs.CCC.2020.15,
  author =	{Kabanets, Valentine and Koroth, Sajin and Lu, Zhenjian and Myrisiotis, Dimitrios and Oliveira, Igor C.},
  title =	{{Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{15:1--15:41},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.15},
  URN =		{urn:nbn:de:0030-drops-125673},
  doi =		{10.4230/LIPIcs.CCC.2020.15},
  annote =	{Keywords: de Morgan formulas, circuit lower bounds, satisfiability (SAT), pseudorandom generators (PRGs), learning, communication complexity, polynomial threshold functions (PTFs), parities}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.7
Leakage-Resilient Secret Sharing in Non-Compartmentalized Models

Authors: Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
Leakage-resilient secret sharing has mostly been studied in the compartmentalized models, where a leakage oracle can arbitrarily leak bounded number of bits from all shares, provided that the oracle only has access to a bounded number of shares when the leakage is taking place. We start a systematic study of leakage-resilient secret sharing against global leakage, where the leakage oracle can access the full set of shares simultaneously, but the access is restricted to a special class of leakage functions. More concretely, the adversary can corrupt several players and obtain their shares, as well as applying a leakage function from a specific class to the full share vector. We explicitly construct such leakage-resilient secret sharing with respect to affine leakage functions and low-degree multi-variate polynomial leakage functions, respectively. For affine leakage functions, we obtain schemes with threshold access structure that are leakage-resilient as long as there is a substantial difference between the total amount of information obtained by the adversary, through corrupting individual players and leaking from the full share vector, and the amount that the reconstruction algorithm requires for reconstructing the secret. Furthermore, if we assume the adversary is non-adaptive, we can even make the secret length asymptotically equal to the difference, as the share length grows. Specifically, we have a threshold scheme with parameters similar to Shamir’s scheme and is leakage-resilient against affine leakage. For multi-variate polynomial leakage functions with degree bigger than one, our constructions here only yield ramp schemes that are leakage-resilient against such leakage. Finally, as a result of independent interest, we show that our approach to leakage-resilient secret sharing also yields a competitive scheme compared with the state-of-the-art construction in the compartmentalized models.
Cite as

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Leakage-Resilient Secret Sharing in Non-Compartmentalized Models. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITC.2020.7,
  author =	{Lin, Fuchun and Cheraghchi, Mahdi and Guruswami, Venkatesan and Safavi-Naini, Reihaneh and Wang, Huaxiong},
  title =	{{Leakage-Resilient Secret Sharing in Non-Compartmentalized Models}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.7},
  URN =		{urn:nbn:de:0030-drops-121124},
  doi =		{10.4230/LIPIcs.ITC.2020.7},
  annote =	{Keywords: Leakage-resilient cryptography, Secret sharing scheme, Randomness extractor}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.39
Circuit Lower Bounds for MCSP from Local Pseudorandom Generators

Authors: Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The Minimum Circuit Size Problem (MCSP) asks if a given truth table of a Boolean function f can be computed by a Boolean circuit of size at most theta, for a given parameter theta. We improve several circuit lower bounds for MCSP, using pseudorandom generators (PRGs) that are local; a PRG is called local if its output bit strings, when viewed as the truth table of a Boolean function, can be computed by a Boolean circuit of small size. We get new and improved lower bounds for MCSP that almost match the best-known lower bounds against several circuit models. Specifically, we show that computing MCSP, on functions with a truth table of length N, requires - N^{3-o(1)}-size de Morgan formulas, improving the recent N^{2-o(1)} lower bound by Hirahara and Santhanam (CCC, 2017), - N^{2-o(1)}-size formulas over an arbitrary basis or general branching programs (no non-trivial lower bound was known for MCSP against these models), and - 2^{Omega (N^{1/(d+2.01)})}-size depth-d AC^0 circuits, improving the superpolynomial lower bound by Allender et al. (SICOMP, 2006). The AC^0 lower bound stated above matches the best-known AC^0 lower bound (for PARITY) up to a small additive constant in the depth. Also, for the special case of depth-2 circuits (i.e., CNFs or DNFs), we get an almost optimal lower bound of 2^{N^{1-o(1)}} for MCSP.
Cite as

Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, and Dimitrios Myrisiotis. Circuit Lower Bounds for MCSP from Local Pseudorandom Generators. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cheraghchi_et_al:LIPIcs.ICALP.2019.39,
  author =	{Cheraghchi, Mahdi and Kabanets, Valentine and Lu, Zhenjian and Myrisiotis, Dimitrios},
  title =	{{Circuit Lower Bounds for MCSP from Local Pseudorandom Generators}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.39},
  URN =		{urn:nbn:de:0030-drops-106156},
  doi =		{10.4230/LIPIcs.ICALP.2019.39},
  annote =	{Keywords: minimum circuit size problem (MCSP), circuit lower bounds, pseudorandom generators (PRGs), local PRGs, de Morgan formulas, branching programs, constant depth circuits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.53
Secret Sharing with Binary Shares

Authors: Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length l among any N <= 2^l players such that for a threshold parameter t, (i) the knowledge of any t shares does not reveal any information about the secret and, (ii) any choice of t+1 shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length l, and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any t+g shares, for a positive integer gap parameter g. Ramp secret sharing scheme necessarily requires shares of length l/g. Other than the bound related to secret length l, the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio g/N. In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio g/N, where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any tau fraction of observed shares, and reconstruction from any rho fraction of shares, for any choices of 0 <= tau < rho <= 1. Our construction achieves secret length N(rho-tau-o(1)), which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length Omega(N(rho-tau)). We discuss our results and open questions.
Cite as

Fuchun Lin, Mahdi Cheraghchi, Venkatesan Guruswami, Reihaneh Safavi-Naini, and Huaxiong Wang. Secret Sharing with Binary Shares. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ITCS.2019.53,
  author =	{Lin, Fuchun and Cheraghchi, Mahdi and Guruswami, Venkatesan and Safavi-Naini, Reihaneh and Wang, Huaxiong},
  title =	{{Secret Sharing with Binary Shares}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{53:1--53:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.53},
  URN =		{urn:nbn:de:0030-drops-101461},
  doi =		{10.4230/LIPIcs.ITCS.2019.53},
  annote =	{Keywords: Secret sharing scheme, Wiretap channel}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2016.46
Local Testing for Membership in Lattices

Authors: Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Abstract
Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in lattice-based communication and cryptography. In this work, we initiate a systematic study of local testing for membership in lattices, complementing and building upon the extensive body of work on locally testable codes. In particular, we formally define the notion of local tests for lattices and present the following: 1. We show that in order to achieve low query complexity, it is sufficient to design one-sided non-adaptive canonical tests. This result is akin to, and based on an analogous result for error-correcting codes due to Ben-Sasson et al. (SIAM J. Computing, 35(1):1-21). 2. We demonstrate upper and lower bounds on the query complexity of local testing for membership in code formula lattices. We instantiate our results for code formula lattices constructed from Reed-Muller codes to obtain nearly-matching upper and lower bounds on the query complexity of testing such lattices. 3. We contrast lattice testing from code testing by showing lower bounds on the query complexity of testing low-dimensional lattices. This illustrates large lower bounds on the query complexity of testing membership in knapsack lattices. On the other hand, we show that knapsack lattices with bounded coefficients have low-query testers if the inputs are promised to lie in the span of the lattice.
Cite as

Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu. Local Testing for Membership in Lattices. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chandrasekaran_et_al:LIPIcs.FSTTCS.2016.46,
  author =	{Chandrasekaran, Karthekeyan and Cheraghchi, Mahdi and Gandikota, Venkata and Grigorescu, Elena},
  title =	{{Local Testing for Membership in Lattices}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{46:1--46:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.46},
  URN =		{urn:nbn:de:0030-drops-68818},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.46},
  annote =	{Keywords: Lattices, Property Testing, Locally Testable Codes, Complexity Theory}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.35
AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product

Authors: Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
AC^0 o MOD_2 circuits are AC^0 circuits augmented with a layer of parity gates just above the input layer. We study AC^0 o MOD2 circuit lower bounds for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have highlighted this problem as a frontier problem in circuit complexity that arose both as a first step towards solving natural special cases of the matrix rigidity problem and as a candidate for constructing pseudorandom generators of minimal complexity. We give the first superlinear lower bound for the Boolean Inner Product function against AC^0 o MOD2 of depth four or greater. Specifically, we prove a superlinear lower bound for circuits of arbitrary constant depth, and an ~Omega(n^2) lower bound for the special case of depth-4 AC^0 o MOD_2. Our proof of the depth-4 lower bound employs a new "moment-matching" inequality for bounded, nonnegative integer-valued random variables that may be of independent interest: we prove an optimal bound on the maximum difference between two discrete distributions’ values at 0, given that their first d moments match.
Cite as

Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{cheraghchi_et_al:LIPIcs.ICALP.2016.35,
  author =	{Cheraghchi, Mahdi and Grigorescu, Elena and Juba, Brendan and Wimmer, Karl and Xie, Ning},
  title =	{{AC^0 o MOD\underline2 Lower Bounds for the Boolean Inner Product}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.35},
  URN =		{urn:nbn:de:0030-drops-63150},
  doi =		{10.4230/LIPIcs.ICALP.2016.35},
  annote =	{Keywords: Boolean analysis, circuit complexity, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2009.1817
Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties

Authors: Mahdi Cheraghchi and Amin Shokrollahi

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract
We consider the problem of uniform sampling of points on an algebraic variety. Specifically, we develop a randomized algorithm that, given a small set of multivariate polynomials over a sufficiently large finite field, produces a common zero of the polynomials almost uniformly at random. The statistical distance between the output distribution of the algorithm and the uniform distribution on the set of common zeros is polynomially small in the field size, and the running time of the algorithm is polynomial in the description of the polynomials and their degrees provided that the number of the polynomials is a constant.
Cite as

Mahdi Cheraghchi and Amin Shokrollahi. Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 277-288, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2009.1817,
  author =	{Cheraghchi, Mahdi and Shokrollahi, Amin},
  title =	{{Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{277--288},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1817},
  URN =		{urn:nbn:de:0030-drops-18174},
  doi =		{10.4230/LIPIcs.STACS.2009.1817},
  annote =	{Keywords: Uniform sampling, Algebraic varieties, Randomized algorithms, Computational complexity}
}
  • Refine by Author
  • 8 Cheraghchi, Mahdi
  • 4 Myrisiotis, Dimitrios
  • 3 Guruswami, Venkatesan
  • 2 Grigorescu, Elena
  • 2 Kabanets, Valentine
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Circuit complexity
  • 4 Theory of computation → Pseudorandomness and derandomization
  • 3 Theory of computation → Expander graphs and randomness extractors
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Theory of computation → Cryptographic primitives
  • Show More...

  • Refine by Keyword
  • 2 Secret sharing scheme
  • 2 circuit lower bounds
  • 2 de Morgan formulas
  • 2 pseudorandom generators (PRGs)
  • 1 Algebraic varieties
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 4 2021
  • 2 2016
  • 2 2019
  • 2 2020
  • 1 2009
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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