12 Search Results for "Wee, Hoeteck"

Document
DOI: 10.4230/LIPIcs.DISC.2024.37
Sing a Song of Simplex

Authors: Victor Shoup

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We flesh out some details of the recently proposed Simplex atomic broadcast protocol, and modify it so that leaders disperse blocks in a more communication-efficient fashion. The resulting protocol, called DispersedSimplex, maintains the simplicity and excellent - indeed, optimal - latency characteristics of the original Simplex protocol. We also present a variant that supports "stable leaders". We also suggest a number of practical optimizations and provide concrete performance estimates that take into account not just network latency but also network bandwidth limitations and computational costs.
Cite as

Victor Shoup. Sing a Song of Simplex. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shoup:LIPIcs.DISC.2024.37,
  author =	{Shoup, Victor},
  title =	{{Sing a Song of Simplex}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{37:1--37:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.37},
  URN =		{urn:nbn:de:0030-drops-212649},
  doi =		{10.4230/LIPIcs.DISC.2024.37},
  annote =	{Keywords: Consensus, Atomic broadcast, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.TQC.2024.5
Revocable Quantum Digital Signatures

Authors: Tomoyuki Morimae, Alexander Poremba, and Takashi Yamakawa

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract
We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption. In this primitive, the signing key is a quantum state which enables a user to sign many messages and yet, the quantum key is also revocable, i.e., it can be collapsed into a classical certificate which can later be verified. Once the key is successfully revoked, we require that the initial recipient of the key loses the ability to sign. We construct digital signatures with revocable signing keys from a newly introduced primitive which we call two-tier one-shot signatures, which may be of independent interest. This is a variant of one-shot signatures, where the verification of a signature for the message "0" is done publicly, whereas the verification for the message "1" is done in private. We give a construction of two-tier one-shot signatures from the LWE assumption. As a complementary result, we also construct digital signatures with quantum revocation from group actions, where the quantum signing key is simply "returned" and then verified as part of revocation. Second, we define and construct digital signatures with revocable signatures from OWFs. In this primitive, the signer can produce quantum signatures which can later be revoked. Here, the security property requires that, once revocation is successful, the initial recipient of the signature loses the ability to find accepting inputs to the signature verification algorithm. We construct this primitive using a newly introduced two-tier variant of tokenized signatures. For the construction, we show a new lemma which we call the adaptive hardcore bit property for OWFs, which may enable further applications.
Cite as

Tomoyuki Morimae, Alexander Poremba, and Takashi Yamakawa. Revocable Quantum Digital Signatures. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 5:1-5:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{morimae_et_al:LIPIcs.TQC.2024.5,
  author =	{Morimae, Tomoyuki and Poremba, Alexander and Yamakawa, Takashi},
  title =	{{Revocable Quantum Digital Signatures}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{5:1--5:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.5},
  URN =		{urn:nbn:de:0030-drops-206757},
  doi =		{10.4230/LIPIcs.TQC.2024.5},
  annote =	{Keywords: Quantum cryptography, digital signatures, revocable cryptography}
}
Document
DOI: 10.4230/LIPIcs.ITC.2024.5
On the Power of Adaptivity for Function Inversion

Authors: Karthik Gajulapalli, Alexander Golovnev, and Samuel King

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
We study the problem of function inversion with preprocessing where, given a function f : [N] → [N] and a point y in its image, the goal is to find an x such that f(x) = y using at most T oracle queries to f and S bits of preprocessed advice that depend on f. The seminal work of Corrigan-Gibbs and Kogan [TCC 2019] initiated a line of research that shows many exciting connections between the non-adaptive setting of this problem and other areas of theoretical computer science. Specifically, they introduced a very weak class of algorithms (strongly non-adaptive) where the points queried by the oracle depend only on the inversion point y, and are independent of the answers to the previous queries and the S bits of advice. They showed that proving even mild lower bounds on strongly non-adaptive algorithms for function inversion would imply a breakthrough result in circuit complexity. We prove that every strongly non-adaptive algorithm for function inversion (and even for its special case of permutation inversion) must have ST = Ω(N log (N) log (T)). This gives the first improvement to the long-standing lower bound of ST = Ω(N log N) due to Yao [STOC 90]. As a corollary, we conclude the first separation between strongly non-adaptive and adaptive algorithms for permutation inversion, where the adaptive algorithm by Hellman [TOIT 80] achieves the trade-off ST = O(N log N). Additionally, we show equivalence between lower bounds for strongly non-adaptive data structures and the one-way communication complexity of certain partial functions. As an example, we recover our lower bound on function inversion in the communication complexity framework.
Cite as

Karthik Gajulapalli, Alexander Golovnev, and Samuel King. On the Power of Adaptivity for Function Inversion. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.ITC.2024.5,
  author =	{Gajulapalli, Karthik and Golovnev, Alexander and King, Samuel},
  title =	{{On the Power of Adaptivity for Function Inversion}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.5},
  URN =		{urn:nbn:de:0030-drops-205137},
  doi =		{10.4230/LIPIcs.ITC.2024.5},
  annote =	{Keywords: Function Inversion, Non-Adaptive lower bounds, Communication Complexity}
}
Document
DOI: 10.4230/LIPIcs.ITC.2024.9
Time-Space Tradeoffs for Finding Multi-Collisions in Merkle-Damgård Hash Functions

Authors: Akshima

Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)

Abstract
We analyze the multi-collision resistance of Merkle-Damgård hash function construction in the auxiliary input random oracle model. Finding multi-collisions or m-way collisions, for some parameter m, in a hash function consists of m distinct input that have the same output under the hash function. This is a natural generalization of the collision finding problem in hash functions, which is basically finding 2-way collisions. Hardness of finding collisions, or collision resistance, is an important security assumption in cryptography. While the time-space trade-offs for collision resistance of hash functions has received considerable attention, this is the first work that studies time-space trade-offs for the multi-collision resistance property of hash functions based on the popular and widely used Merkle-Damgård (MD) constructions. In this work, we study how the advantage of finding m-way collisions depends on the parameter m. We believe understanding whether multi-collision resistance is a strictly easier property than collision resistance is a fundamental problem and our work facilitates this for adversaries with auxiliary information against MD based hash functions. Furthermore, in this work we study how the advantage varies with the bound on length of the m colliding inputs. Prior works [Akshima et al., 2020; Ashrujit Ghoshal and Ilan Komargodski, 2022; Akshima et al., 2022] have shown that finding "longer" collisions with auxiliary input in MD based hash functions becomes easier. More precisely, the advantage of finding collisions linearly depends on the bound on the length of colliding inputs. In this work, we show similar dependence for m-way collision finding, for any m ≥ 2. We show a simple attack for finding 1-block m-way collisions which achieves an advantage of Ω̃(S/mN). For 2 ≤ B < log m, we give the best known attack for finding B-blocks m-way collision which achieves an advantage of Ω̃(ST/m^{1/(B-1)}N) when m^{1/(B-1)}-way collisions exist on every salt. For B > log m, our attack achieves an advantage of Ω̃(STB/N) which is optimal when SB ≥ T and ST² ≤ N. The main results of this work is showing that our attacks are optimal for B = 1 and B = 2. This implies that in the auxiliary-input random oracle model, the advantage decreases by a multiplicative factor of m for finding 1-block and 2-block m-way collisions (compared to collision finding) in Merkle-Damgård based hash functions.
Cite as

Akshima. Time-Space Tradeoffs for Finding Multi-Collisions in Merkle-Damgård Hash Functions. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{akshima:LIPIcs.ITC.2024.9,
  author =	{Akshima},
  title =	{{Time-Space Tradeoffs for Finding Multi-Collisions in Merkle-Damg\r{a}rd Hash Functions}},
  booktitle =	{5th Conference on Information-Theoretic Cryptography (ITC 2024)},
  pages =	{9:1--9:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-333-1},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{304},
  editor =	{Aggarwal, Divesh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.9},
  URN =		{urn:nbn:de:0030-drops-205171},
  doi =		{10.4230/LIPIcs.ITC.2024.9},
  annote =	{Keywords: Collision, hash functions, multi-collisions, Merkle-Damg\r{a}rd, pre-computation, auxiliary input}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.36
Gap MCSP Is Not (Levin) NP-Complete in Obfustopia

Authors: Noam Mazor and Rafael Pass

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

Abstract
We demonstrate that under believable cryptographic hardness assumptions, Gap versions of standard meta-complexity problems, such as the Minimum Circuit Size Problem (MCSP) and the Minimum Time-Bounded Kolmogorov Complexity problem (MKTP) are not NP-complete w.r.t. Levin (i.e., witness-preserving many-to-one) reductions. In more detail: - Assuming the existence of indistinguishability obfuscation, and subexponentially-secure one-way functions, an appropriate Gap version of MCSP is not NP-complete under randomized Levin-reductions. - Assuming the existence of subexponentially-secure indistinguishability obfuscation, subexponentially-secure one-way functions and injective PRGs, an appropriate Gap version of MKTP is not NP-complete under randomized Levin-reductions.
Cite as

Noam Mazor and Rafael Pass. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mazor_et_al:LIPIcs.CCC.2024.36,
  author =	{Mazor, Noam and Pass, Rafael},
  title =	{{Gap MCSP Is Not (Levin) NP-Complete in Obfustopia}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{36:1--36:21},
  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.36},
  URN =		{urn:nbn:de:0030-drops-204322},
  doi =		{10.4230/LIPIcs.CCC.2024.36},
  annote =	{Keywords: Kolmogorov complexity, MCSP, Levin Reduction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.14
A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results

Authors: Vikraman Arvind and Pushkar S. Joglekar

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

Abstract
We study the noncommutative rank problem, ncRANK, of computing the rank of matrices with linear entries in n noncommuting variables and the problem of noncommutative Rational Identity Testing, RIT, which is to decide if a given rational formula in n noncommuting variables is zero on its domain of definition. Motivated by the question whether these problems have deterministic NC algorithms, we revisit their interrelationship from a parallel complexity point of view. We show the following results: 1) Based on Cohn’s embedding theorem [Cohn, 1990; Cohn, 2006] we show deterministic NC reductions from multivariate ncRANK to bivariate ncRANK and from multivariate RIT to bivariate RIT. 2) We obtain a deterministic NC-Turing reduction from bivariate RIT to bivariate ncRANK, thereby proving that a deterministic NC algorithm for bivariate ncRANK would imply that both multivariate RIT and multivariate ncRANK are in deterministic NC.
Cite as

Vikraman Arvind and Pushkar S. Joglekar. A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.ICALP.2024.14,
  author =	{Arvind, Vikraman and Joglekar, Pushkar S.},
  title =	{{A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{14:1--14:19},
  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.14},
  URN =		{urn:nbn:de:0030-drops-201571},
  doi =		{10.4230/LIPIcs.ICALP.2024.14},
  annote =	{Keywords: noncommutative rank, rational formulas, identity testing, parallel complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.6
On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

Authors: V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya

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

Abstract
The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables [Hrubeš and Wigderson, 2015]. This rank computation problem has deterministic polynomial-time white-box algorithms [Ankit Garg et al., 2016; Ivanyos et al., 2018] and a randomized polynomial-time algorithm in the black-box setting [Harm Derksen and Visu Makam, 2017]. In this paper, we propose a new approach for efficient derandomization of black-box RIT. Additionally, we obtain results for matrix rank computation over the free skew field and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show: - Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the k×k matrix algebra is 2^Ω(k) [Andrej Bogdanov and Hoeteck Wee, 2005], we obtain a subexponential-time black-box RIT algorithm for rational formulas of inversion height almost logarithmic in the size of the formula. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. - We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. While an efficient rank computation was known for matrices with noncommutative formulas as entries [Ankit Garg et al., 2020], we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. - Motivated by the definition given by Bergman [George M Bergman, 1976], we define a new class of rational functions where a rational function of inversion height at most h is defined as a composition of a noncommutative r-skewed circuit (equivalently an ABP) with inverses of rational functions of this class of inversion height at most h-1 which are also disjoint. We obtain a polynomial-size linear pencil representation for this class which gives a white-box deterministic polynomial-time identity testing algorithm for the class.
Cite as

V. Arvind, Abhranil Chatterjee, Utsab Ghosal, Partha Mukhopadhyay, and C. Ramya. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.ITCS.2023.6,
  author =	{Arvind, V. and Chatterjee, Abhranil and Ghosal, Utsab and Mukhopadhyay, Partha and Ramya, C.},
  title =	{{On Identity Testing and Noncommutative Rank Computation over the Free Skew Field}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{6:1--6:23},
  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.6},
  URN =		{urn:nbn:de:0030-drops-175093},
  doi =		{10.4230/LIPIcs.ITCS.2023.6},
  annote =	{Keywords: Algebraic Complexity, Identity Testing, Non-commutative rank}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.28
Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE

Authors: Zvika Brakerski and Vinod Vaikuntanathan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Broadcast encryption remains one of the few remaining central cryptographic primitives that are not yet known to be achievable under a standard cryptographic assumption (excluding obfuscation-based constructions, see below). Furthermore, prior to this work, there were no known direct candidates for post-quantum-secure broadcast encryption. We propose a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits, where the ciphertext size depends only on the depth of the policy circuit (and not its size). This, in particular, gives us a Broadcast Encryption (BE) scheme where the size of the keys and ciphertexts have a poly-logarithmic dependence on the number of users. This goal was previously only known to be achievable assuming ideal multilinear maps (Boneh, Waters and Zhandry, Crypto 2014) or indistinguishability obfuscation (Boneh and Zhandry, Crypto 2014) and in a concurrent work from generic bilinear groups and the learning with errors (LWE) assumption (Agrawal and Yamada, Eurocrypt 2020). Our construction relies on techniques from lattice-based (and in particular LWE-based) cryptography. We analyze some attempts at cryptanalysis, but we are unable to provide a security proof.
Cite as

Zvika Brakerski and Vinod Vaikuntanathan. Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{brakerski_et_al:LIPIcs.ITCS.2022.28,
  author =	{Brakerski, Zvika and Vaikuntanathan, Vinod},
  title =	{{Lattice-Inspired Broadcast Encryption and Succinct Ciphertext-Policy ABE}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{28:1--28:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.28},
  URN =		{urn:nbn:de:0030-drops-156243},
  doi =		{10.4230/LIPIcs.ITCS.2022.28},
  annote =	{Keywords: Theoretical Cryptography, Broadcast Encryption, Attribute-Based Encryption, Lattice-Based Cryptography}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.12
Linear Threshold Secret-Sharing with Binary Reconstruction

Authors: Marshall Ball, Alper Çakan, and Tal Malkin

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
Motivated in part by applications in lattice-based cryptography, we initiate the study of the size of linear threshold (`t-out-of-n') secret-sharing where the linear reconstruction function is restricted to coefficients in {0,1}. We also study the complexity of such schemes with the additional requirement that the joint distribution of the shares of any unauthorized set of parties is not only independent of the secret, but also uniformly distributed. We prove upper and lower bounds on the share size of such schemes, where the size is measured by the total number of field elements distributed to the parties. We prove our results by defining and investigating an equivalent variant of Karchmer and Wigderson’s Monotone Span Programs [CCC, 1993]. One ramification of our results is that a natural variant of Shamir’s classic scheme [Comm. of ACM, 1979], where bit-decomposition is applied to each share, is optimal for when the underlying field has characteristic 2. Another ramification is that schemes obtained from monotone formulae are optimal for certain threshold values when the field’s characteristic is any constant. For schemes with the uniform distribution requirement, we show that they must use Ω(nlog n) field elements, for all thresholds 2 < t < n and regardless of the field. Moreover, this is tight up to constant factors for the special cases where any t = n-1 parties can reconstruct, as well as for any threshold when the field characteristic is 2.
Cite as

Marshall Ball, Alper Çakan, and Tal Malkin. Linear Threshold Secret-Sharing with Binary Reconstruction. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITC.2021.12,
  author =	{Ball, Marshall and \c{C}akan, Alper and Malkin, Tal},
  title =	{{Linear Threshold Secret-Sharing with Binary Reconstruction}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{12:1--12:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.12},
  URN =		{urn:nbn:de:0030-drops-143313},
  doi =		{10.4230/LIPIcs.ITC.2021.12},
  annote =	{Keywords: Secret sharing, Span programs, Lattice-based cryptography}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.13
One-One Constrained Pseudorandom Functions

Authors: Naty Peter, Rotem Tsabary, and Hoeteck Wee

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

Abstract
We define and study a new cryptographic primitive, named One-One Constrained Pseudorandom Functions. In this model there are two parties, Alice and Bob, that hold a common random string K, where Alice in addition holds a predicate f:[N] → {0,1} and Bob in addition holds an input x ∈ [N]. We then let Alice generate a key K_f based on f and K, and let Bob evaluate a value K_x based on x and K. We consider a third party that sees the values (x,f,K_f) and the goal is to allow her to reconstruct K_x whenever f(x)=1, while keeping K_x pseudorandom whenever f(x)=0. This primitive can be viewed as a relaxation of constrained PRFs, such that there is only a single key query and a single evaluation query. We focus on the information-theoretic setting, where the one-one cPRF has perfect correctness and perfect security. Our main results are as follows. 1) A Lower Bound. We show that in the information-theoretic setting, any one-one cPRF for punctured predicates is of exponential complexity (and thus the lower bound meets the upper bound that is given by a trivial construction). This stands in contrast with the well known GGM-based punctured PRF from OWF, which is in particular a one-one cPRF. This also implies a similar lower bound for all NC1. 2) New Constructions. On the positive side, we present efficient information-theoretic constructions of one-one cPRFs for a few other predicate families, such as equality predicates, inner-product predicates, and subset predicates. We also show a generic AND composition lemma that preserves complexity. 3) An Amplification to standard cPRF. We show that all of our one-one cPRF constructions can be amplified to a standard (single-key) cPRF via any key-homomorphic PRF that supports linear computations. More generally, we suggest a new framework that we call the double-key model which allows to construct constrained PRFs via key-homomorphic PRFs. 4) Relation to CDS. We show that one-one constrained PRFs imply conditional disclosure of secrets (CDS) protocols. We believe that this simple model can be used to better understand constrained PRFs and related cryptographic primitives, and that further applications of one-one constrained PRFs and our double-key model will be found in the future, in addition to those we show in this paper.
Cite as

Naty Peter, Rotem Tsabary, and Hoeteck Wee. One-One Constrained Pseudorandom Functions. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{peter_et_al:LIPIcs.ITC.2020.13,
  author =	{Peter, Naty and Tsabary, Rotem and Wee, Hoeteck},
  title =	{{One-One Constrained Pseudorandom Functions}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{13:1--13:22},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.13},
  URN =		{urn:nbn:de:0030-drops-121188},
  doi =		{10.4230/LIPIcs.ITC.2020.13},
  annote =	{Keywords: Constrained pseudorandom functions, function secret-sharing, conditional disclosure of secrets}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.68
Pseudorandomness and the Minimum Circuit Size Problem

Authors: Rahul Santhanam

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
We explore the possibility of basing one-way functions on the average-case hardness of the fundamental Minimum Circuit Size Problem (MCSP[s]), which asks whether a Boolean function on n bits specified by its truth table has circuits of size s(n). 1) (Pseudorandomness from Zero-Error Average-Case Hardness) We show that for a given size function s, the following are equivalent: Pseudorandom distributions supported on strings describable by s(O(n))-size circuits exist; Hitting sets supported on strings describable by s(O(n))-size circuits exist; MCSP[s(O(n))] is zero-error average-case hard. Using similar techniques, we show that Feige’s hypothesis for random k-CNFs implies that there is a pseudorandom distribution (with constant error) supported entirely on satisfiable formulas. Underlying our results is a general notion of semantic sampling, which might be of independent interest. 2) (A New Conjecture) In analogy to a known universal construction of succinct hitting sets against arbitrary polynomial-size adversaries, we propose the Universality Conjecture: there is a universal construction of succinct pseudorandom distributions against arbitrary polynomial-size adversaries. We show that under the Universality Conjecture, the following are equivalent: One-way functions exist; Natural proofs useful against sub-exponential size circuits do not exist; Learning polynomial-size circuits with membership queries over the uniform distribution is hard; MCSP[2^(ε n)] is zero-error hard on average for some ε > 0; Cryptographic succinct hitting set generators exist. 3) (Non-Black-Box Results) We show that for weak circuit classes ℭ against which there are natural proofs [Alexander A. Razborov and Steven Rudich, 1997], pseudorandom functions secure against poly-size circuits in ℭ imply superpolynomial lower bounds in P against poly-size circuits in ℭ. We also show that for a certain natural variant of MCSP, there is a polynomial-time reduction from approximating the problem well in the worst case to solving it on average. These results are shown using non-black-box techniques, and in the first case we show that there is no black-box proof of the result under standard crypto assumptions.
Cite as

Rahul Santhanam. Pseudorandomness and the Minimum Circuit Size Problem. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 68:1-68:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{santhanam:LIPIcs.ITCS.2020.68,
  author =	{Santhanam, Rahul},
  title =	{{Pseudorandomness and the Minimum Circuit Size Problem}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{68:1--68:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.68},
  URN =		{urn:nbn:de:0030-drops-117532},
  doi =		{10.4230/LIPIcs.ITCS.2020.68},
  annote =	{Keywords: Minimum Circuit Size Problem, Pseudorandomness, Average-case Complexity, Natural Proofs, Universality Conjecture}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.41
On the Inner Product Predicate and a Generalization of Matching Vector Families

Authors: Balthazar Bauer, Jevgenijs Vihrovs, and Hoeteck Wee

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function P and some modulus q. We are interested in encoding x to x_vector and y to y_vector so that P(x,y) = 1 <=> <x_vector,y_vector> = 0 mod q, where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus q. Using this approach, we also prove lower bounds on encodings for composite q, and then show tight upper bounds for such predicates as greater than, index and disjointness.
Cite as

Balthazar Bauer, Jevgenijs Vihrovs, and Hoeteck Wee. On the Inner Product Predicate and a Generalization of Matching Vector Families. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bauer_et_al:LIPIcs.FSTTCS.2018.41,
  author =	{Bauer, Balthazar and Vihrovs, Jevgenijs and Wee, Hoeteck},
  title =	{{On the Inner Product Predicate and a Generalization of Matching Vector Families}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{41:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.41},
  URN =		{urn:nbn:de:0030-drops-99400},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.41},
  annote =	{Keywords: Predicate Encryption, Inner Product Encoding, Matching Vector Families}
}
  • Refine by Author
  • 2 Wee, Hoeteck
  • 1 Akshima
  • 1 Arvind, V.
  • 1 Arvind, Vikraman
  • 1 Ball, Marshall
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Computational complexity and cryptography
  • 2 Security and privacy → Information-theoretic techniques
  • 2 Security and privacy → Public key encryption
  • 2 Theory of computation → Algebraic complexity theory
  • 2 Theory of computation → Cryptographic primitives
  • Show More...

  • Refine by Keyword
  • 1 Algebraic Complexity
  • 1 Atomic broadcast
  • 1 Attribute-Based Encryption
  • 1 Average-case Complexity
  • 1 Blockchain
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 6 2024
  • 2 2020
  • 1 2018
  • 1 2021
  • 1 2022
  • 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