Search Results

Documents authored by Malkin, Tal

Document
DOI: 10.4230/LIPIcs.AFT.2024.1
Accountable Secret Leader Election

Authors: Miranda Christ, Kevin Choi, Walter McKelvie, Joseph Bonneau, and Tal Malkin

Published in: LIPIcs, Volume 316, 6th Conference on Advances in Financial Technologies (AFT 2024)

Abstract
We consider the problem of secret leader election with accountability. Secret leader election protocols counter adaptive adversaries by keeping the identities of elected leaders secret until they choose to reveal themselves, but in existing protocols this means it is impossible to determine who was elected leader if they fail to act. This opens the door to undetectable withholding attacks, where leaders fail to act in order to slow the protocol or bias future elections in their favor. We formally define accountability (in weak and strong variants) for secret leader election protocols. We present three paradigms for adding accountability, using delay-based cryptography, enforced key revelation, or threshold committees, all of which ensure that after some time delay the result of the election becomes public. The paradigm can be chosen to balance trust assumptions, protocol efficiency, and the length of the delay before leaders are revealed. Along the way, we introduce several new cryptographic tools including re-randomizable timed commitments and timed VRFs.
Cite as

Miranda Christ, Kevin Choi, Walter McKelvie, Joseph Bonneau, and Tal Malkin. Accountable Secret Leader Election. In 6th Conference on Advances in Financial Technologies (AFT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 316, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{christ_et_al:LIPIcs.AFT.2024.1,
  author =	{Christ, Miranda and Choi, Kevin and McKelvie, Walter and Bonneau, Joseph and Malkin, Tal},
  title =	{{Accountable Secret Leader Election}},
  booktitle =	{6th Conference on Advances in Financial Technologies (AFT 2024)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-345-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{316},
  editor =	{B\"{o}hme, Rainer and Kiffer, Lucianna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2024.1},
  URN =		{urn:nbn:de:0030-drops-209378},
  doi =		{10.4230/LIPIcs.AFT.2024.1},
  annote =	{Keywords: Consensus Protocols, Single Secret Leader Election, Accountability}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.12
Randomness Extraction from Somewhat Dependent Sources

Authors: Marshall Ball, Oded Goldreich, and Tal Malkin

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

Abstract
We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness. Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions. Going from the more restricted model to the less restricted one, our models and main results are as follows. 1) Bounded dependence as bounded coordination: Here we consider pairs of distributions that arise from independent random processes that are applied to the outcome of a single global random source, which may be viewed as a mechanism of coordination (which is adversarial from our perspective). We show that if the min-entropy of each of the two outcomes is larger than the length of the global source, then extraction is possible (and is, in fact, feasible). We stress that the extractor has no access to the global random source nor to the internal randomness that the two processes use, but rather gets only the two dependent outcomes. This model is equivalent to a setting in which the two outcomes are generated by two independent sources, but then each outcome is modified based on limited leakage (equiv., communication) between the two sources. (Here this leakage is measured in terms of the number of bits that were communicated, but in the next model we consider the actual influence of this leakage.) 2) Bounded dependence as bounded cross influence: Here we consider pairs of outcomes that are produced by a pair of sources such that each source has bounded (worst-case) influence on the outcome of the other source. We stress that the extractor has no access to the randomness that the two processes use, but rather gets only the two dependent outcomes. We show that, while (proper) randomness extraction is impossible in this case, randomness condensing is possible and feasible; specifically, the randomness deficiency of condensing is linear in our measure of cross influence, and this upper bound is tight. We also discuss various applications of such condensers, including for cryptography, standard randomized algorithms, and sublinear-time algorithms, while pointing out their benefit over using a seeded (single-source) extractor. 3) Bounded dependence as bounded mutual information: Due to the average-case nature of mutual information, here there is a trade-off between the error (or deviation) probability of the extracted output and its randomness deficiency. Loosely speaking, for joint distributions of mutual information t, we can condense with randomness deficiency O(t/ε) and error ε, and this trade-off is optimal. All positive results are obtained by using a standard two-source extractor (or condenser) as a black-box.
Cite as

Marshall Ball, Oded Goldreich, and Tal Malkin. Randomness Extraction from Somewhat Dependent Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2022.12,
  author =	{Ball, Marshall and Goldreich, Oded and Malkin, Tal},
  title =	{{Randomness Extraction from Somewhat Dependent Sources}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{12:1--12:14},
  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.12},
  URN =		{urn:nbn:de:0030-drops-156081},
  doi =		{10.4230/LIPIcs.ITCS.2022.12},
  annote =	{Keywords: Randomness Extraction, min-entropy, mutual information, two-source extractors, two-source condenser}
}
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.CCC.2021.14
Communication Complexity with Defective Randomness

Authors: Marshall Ball, Oded Goldreich, and Tal Malkin

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

Abstract
Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness. Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over 𝓁 bit strings that have min-entropy at least k ≤ 𝓁. We present general upper and lower bounds on the communication complexity in these cases, where the bounds are typically linear in 𝓁-k and also depend on the size of the fooling set for the function being computed and on its standard randomized complexity.
Cite as

Marshall Ball, Oded Goldreich, and Tal Malkin. Communication Complexity with Defective Randomness. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 14:1-14:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.CCC.2021.14,
  author =	{Ball, Marshall and Goldreich, Oded and Malkin, Tal},
  title =	{{Communication Complexity with Defective Randomness}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{14:1--14:10},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.14},
  URN =		{urn:nbn:de:0030-drops-142886},
  doi =		{10.4230/LIPIcs.CCC.2021.14},
  annote =	{Keywords: Randomized Communication Complexity, Randomness Extraction, Min-Entropy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.80
Limits to Non-Malleability

Authors: Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin

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

Abstract
There have been many successes in constructing explicit non-malleable codes for various classes of tampering functions in recent years, and strong existential results are also known. In this work we ask the following question: When can we rule out the existence of a non-malleable code for a tampering class ℱ? First, we start with some classes where positive results are well-known, and show that when these classes are extended in a natural way, non-malleable codes are no longer possible. Specifically, we show that no non-malleable codes exist for any of the following tampering classes: - Functions that change d/2 symbols, where d is the distance of the code; - Functions where each input symbol affects only a single output symbol; - Functions where each of the n output bits is a function of n-log n input bits. Furthermore, we rule out constructions of non-malleable codes for certain classes ℱ via reductions to the assumption that a distributional problem is hard for ℱ, that make black-box use of the tampering functions in the proof. In particular, this yields concrete obstacles for the construction of efficient codes for NC, even assuming average-case variants of P ⊈ NC.
Cite as

Marshall Ball, Dana Dachman-Soled, Mukul Kulkarni, and Tal Malkin. Limits to Non-Malleability. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 80:1-80:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2020.80,
  author =	{Ball, Marshall and Dachman-Soled, Dana and Kulkarni, Mukul and Malkin, Tal},
  title =	{{Limits to Non-Malleability}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{80:1--80:32},
  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.80},
  URN =		{urn:nbn:de:0030-drops-117657},
  doi =		{10.4230/LIPIcs.ITCS.2020.80},
  annote =	{Keywords: non-malleable codes, black-box impossibility, tamper-resilient cryptogtaphy, average-case hardness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.86
On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?

Authors: Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin

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

Abstract
Garbling schemes, also known as decomposable randomized encodings (DRE), have found many applications in cryptography. However, despite a large body of work on constructing such schemes, very little is known about their limitations. We initiate a systematic study of the DRE complexity of Boolean functions, obtaining the following main results: - Near-quadratic lower bounds. We use a classical lower bound technique of Nečiporuk [Dokl. Akad. Nauk SSSR '66] to show an Ω(n²/log n) lower bound on the size of any DRE for many explicit Boolean functions. For some natural functions, we obtain a corresponding upper bound, thus settling their DRE complexity up to polylogarithmic factors. Prior to our work, no superlinear lower bounds were known, even for non-explicit functions. - Garbling-friendly PRFs. We show that any exponentially secure PRF has Ω(n²/log n) DRE size, and present a plausible candidate for a "garbling-optimal" PRF that nearly meets this bound. This candidate establishes a barrier for super-quadratic DRE lower bounds via natural proof techniques. In contrast, we show a candidate for a weak PRF with near-exponential security and linear DRE size. Our results establish several qualitative separations, including near-quadratic separations between computational and information-theoretic DRE size of Boolean functions, and between DRE size of weak vs. strong PRFs.
Cite as

Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 86:1-86:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ball_et_al:LIPIcs.ITCS.2020.86,
  author =	{Ball, Marshall and Holmgren, Justin and Ishai, Yuval and Liu, Tianren and Malkin, Tal},
  title =	{{On the Complexity of Decomposable Randomized Encodings, Or: How Friendly Can a Garbling-Friendly PRF Be?}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{86:1--86:22},
  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.86},
  URN =		{urn:nbn:de:0030-drops-117714},
  doi =		{10.4230/LIPIcs.ITCS.2020.86},
  annote =	{Keywords: Randomized Encoding, Private Simultaneous Messages}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.15
Two Party Distribution Testing: Communication and Security

Authors: Alexandr Andoni, Tal Malkin, and Negev Shekel Nosatzki

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

Abstract
We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have t samples from, respectively, distributions a and b over [n], and they need to test whether a=b or a,b are epsilon-far (in the l_1 distance). This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions. Despite being a natural constraint in applications, the two-party setting has previously evaded attention. We address two fundamental aspects of the two-party setting: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other’s input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have t samples from distributions a and b respectively, which may be correlated; the question is whether a,b are independent or epsilon-far from being independent. Our contribution is three-fold: 1) We show how to gain communication efficiency given more samples, beyond the information-theoretic bound on t. The gain is polynomially better than what one would obtain via adapting one-party algorithms. 2) We prove tightness of our trade-off for the closeness testing, as well as that the independence testing requires tight Omega(sqrt{m}) communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2-party communication lower bounds for testing problems, where the inputs are a set of i.i.d. samples. 3) We define the concept of secure distribution testing, and provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.
Cite as

Alexandr Andoni, Tal Malkin, and Negev Shekel Nosatzki. Two Party Distribution Testing: Communication and Security. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{andoni_et_al:LIPIcs.ICALP.2019.15,
  author =	{Andoni, Alexandr and Malkin, Tal and Nosatzki, Negev Shekel},
  title =	{{Two Party Distribution Testing: Communication and Security}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{15:1--15:16},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.15},
  URN =		{urn:nbn:de:0030-drops-105916},
  doi =		{10.4230/LIPIcs.ICALP.2019.15},
  annote =	{Keywords: distribution testing, communication complexity, security}
}
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