Search

Your search keyword '"Malkin, Tal"' showing total 553 results
Start Over Author "Malkin, Tal"

Refine your results

more »

more »

more »

more »
553 results on '"Malkin, Tal"'

51. Efficient Robust Private Set Intersection

Author

Dachman-Soled, Dana, Malkin, Tal, Raykova, Mariana, Yung, Moti, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Abdalla, Michel, editor, Pointcheval, David, editor, Fouque, Pierre-Alain, editor, and Vergnaud, Damien, editor

Published
2009
Full Text
View/download PDF

52. A Unified Framework for the Analysis of Side-Channel Key Recovery Attacks

Author

Standaert, François-Xavier, Malkin, Tal G., Yung, Moti, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Joux, Antoine, editor

Published
2009
Full Text
View/download PDF

53. Simple, Black-Box Constructions of Adaptively Secure Protocols

Author

Choi, Seung Geol, Dachman-Soled, Dana, Malkin, Tal, Wee, Hoeteck, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Reingold, Omer, editor

Published
2009
Full Text
View/download PDF

55. Reputation Systems for Anonymous Networks

Author

Androulaki, Elli, Choi, Seung Geol, Bellovin, Steven M., Malkin, Tal, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Borisov, Nikita, editor, and Goldberg, Ian, editor

Published
2008
Full Text
View/download PDF

56. Optimal Cryptographic Hardness of Learning Monotone Functions

Author

Dachman-Soled, Dana, Lee, Homin K., Malkin, Tal, Servedio, Rocco A., Wan, Andrew, Wee, Hoeteck, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Aceto, Luca, editor, Damgård, Ivan, editor, Goldberg, Leslie Ann, editor, Halldórsson, Magnús M., editor, Ingólfsdóttir, Anna, editor, and Walukiewicz, Igor, editor

Published
2008
Full Text
View/download PDF

57. Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One

Author

Choi, Seung Geol, Dachman-Soled, Dana, Malkin, Tal, Wee, Hoeteck, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Canetti, Ran, editor

Published
2008
Full Text
View/download PDF

58. How Should We Solve Search Problems Privately?

Author

Beimel, Amos, Malkin, Tal, Nissim, Kobbi, Weinreb, Enav, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Menezes, Alfred, editor

Published
2007
Full Text
View/download PDF

59. Private Multiparty Sampling and Approximation of Vector Combinations

Author

Ishai, Yuval, Malkin, Tal, Strauss, Martin J., Wright, Rebecca N., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Arge, Lars, editor, Cachin, Christian, editor, Jurdziński, Tomasz, editor, and Tarlecki, Andrzej, editor

Published
2007
Full Text
View/download PDF

60. Towards a Separation of Semantic and CCA Security for Public Key Encryption

Author

Gertner, Yael, Malkin, Tal, Myers, Steven, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Rangan, C. Pandu, editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Vadhan, Salil P., editor

Published
2007
Full Text
View/download PDF

61. Two-Party Computing with Encrypted Data

Author

Choi, Seung Geol, Elbaz, Ariel, Juels, Ari, Malkin, Tal, Yung, Moti, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Kurosawa, Kaoru, editor

Published
2007
Full Text
View/download PDF

62. A Comparative Cost/Security Analysis of Fault Attack Countermeasures

Author

Malkin, Tal G., Standaert, François-Xavier, Yung, Moti, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Breveglieri, Luca, editor, Koren, Israel, editor, Naccache, David, editor, and Seifert, Jean-Pierre, editor

Published
2006
Full Text
View/download PDF

63. Generalized Environmental Security from Number Theoretic Assumptions

Author

Malkin, Tal, Moriarty, Ryan, Yakovenko, Nikolai, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Halevi, Shai, editor, and Rabin, Tal, editor

Published
2006
Full Text
View/download PDF

64. Mercurial Commitments with Applications to Zero-Knowledge Sets : Extended Abstract

Author

Chase, Melissa, Healy, Alexander, Lysyanskaya, Anna, Malkin, Tal, Reyzin, Leonid, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Cramer, Ronald, editor

Published
2005
Full Text
View/download PDF

65. WAR: Wireless Anonymous Routing

Author

Blaze, Matt, Ioannidis, John, Keromytis, Angelos D., Malkin, Tal, Rubin, Avi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Christianson, Bruce, editor, Crispo, Bruno, editor, Malcolm, James A., editor, and Roe, Michael, editor

Published
2005
Full Text
View/download PDF

66. The Hierarchy of Key Evolving Signatures and a Characterization of Proxy Signatures

Author

Malkin, Tal, Obana, Satoshi, Yung, Moti, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Cachin, Christian, editor, and Camenisch, Jan L., editor

Published
2004
Full Text
View/download PDF

72. Randomness Extraction from Somewhat Dependent Sources

Author

Ball, Marshall, Goldreich, Oded, Malkin, Tal, Ball, Marshall, Goldreich, Oded, and Malkin, Tal

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 influen

Published
2022
Full Text
View/download PDF

73. Randomness Extraction from Somewhat Dependent Sources

Author

Marshall Ball and Oded Goldreich and Tal Malkin, Ball, Marshall, Goldreich, Oded, Malkin, Tal, Marshall Ball and Oded Goldreich and Tal Malkin, Ball, Marshall, Goldreich, Oded, and Malkin, Tal

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 influen

Published
2022
Full Text
View/download PDF

86. Communication Complexity with Defective Randomness

Author

Ball, Marshall, Goldreich, Oded, Malkin, Tal, and Kabanets, Valentine

Subjects
Theory of computation → Communication complexity, Randomized Communication Complexity, Randomness Extraction, Min-Entropy
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., LIPIcs, Vol. 200, 36th Computational Complexity Conference (CCC 2021), pages 14:1-14:10

Published
2021
Full Text
View/download PDF

87. Linear Threshold Secret-Sharing with Binary Reconstruction

Author

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

Subjects
Span programs, Secret sharing, Theory of computation → Computational complexity and cryptography, Lattice-based cryptography
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., LIPIcs, Vol. 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021), pages 12:1-12:22

Published
2021
Full Text
View/download PDF

89. Lower Bounds for Oblivious Near-Neighbor Search

Author

Larsen, Kasper Green, Malkin, Tal, Weinstein, Omri, Yeo, Kevin, and Chawla, Shuchi

Abstract

We prove an Ω(dlg n/(lg lg n) 2) lower bound on the dynamic cell-probe complexity of statistically oblivious approximate-near-neighbor search (ANN) over the ddimensional Hamming cube. For the natural setting of d = Θ(lg n), our result implies an Ω(lg 2 n) lower bound, which is a quadratic improvement over the highest (non-oblivious) cell-probe lower bound for ANN. This is the first super-logarithmic unconditional lower bound for ANN against general (non black-box) data structures. We also show that any oblivious static data structure for decomposable search problems (like ANN) can be obliviously dynamized with O(lg n) overhead in update and query time, strengthening a classic result of Bentley and Saxe (Algorithmica, 1980).

Published
2020

90. Limits to Non-Malleability

Author

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

Subjects
000 Computer science, knowledge, general works, Computer Science
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.

Published
2020
Full Text
View/download PDF

91. LP decoding corrects a constant fraction of errors

Author

Feldman, Jon, Malkin, Tal, Servedio, Rocco A., Stein, Cliff, and Wainwright, Martin J.

Subjects
Decoders -- Research, Linear programming -- Research
Abstract

We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length. Index Terms--Channel coding, factor graphs, iterative decoding, linear programming, low-density parity-check (LDPC) codes, message passing, Tanner graphs.

Published
2007

93. Limits to Non-Malleability

Author

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

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.

Published
2020
Full Text
View/download PDF

97. Secure Computation for Big Data

Author

Malkin, Tal, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Sahai, Amit, editor

Published
2013
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results