Arrow Research search

Author name cluster

Tal Malkin

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers
2 author rows

Possible papers

7

FOCS Conference 2018 Conference Paper

Non-Malleable Codes for Small-Depth Circuits

  • Marshall Ball
  • Dana Dachman-Soled
  • Siyao Guo 0001
  • Tal Malkin
  • Li-Yang Tan

We construct efficient, unconditional non-malleable codes that are secure against tampering functions computed by small-depth circuits. For constant-depth circuits of polynomial size (i. e. AC 0 tampering functions), our codes have codeword length n = k 1+0(1) for a k-bit message. This is an exponential improvement of the previous best construction due to Chattopadhyay and Li (STOC 2017), which had codeword length 2 O(√k). Our construction remains efficient for circuit depths as large as Θ(log(n)/loglog(n)) (indeed, our codeword length remains n ≤ k 1+ε ), and extending our result beyond this would require separating P from NC 1. We obtain our codes via a new efficient non-malleable reduction from small-depth tampering to split-state tampering. A novel aspect of our work is the incorporation of techniques from unconditional derandomization into the framework of non-malleable reductions. In particular, a key ingredient in our analysis is a recent pseudorandom switching lemma of Trevisan and Xue (CCC 2013), a derandomization of the influential switching lemma from circuit complexity; the randomness-efficiency of this switching lemma translates into the rate-efficiency of our codes via our non-malleable reduction.

Details

TCS Journal 2009 Journal Article

Private multiparty sampling and approximation of vector combinations

  • Yuval Ishai
  • Tal Malkin
  • Martin J. Strauss
  • Rebecca N. Wright

We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the componentwise combination of their vectors. The parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. Sublinear-communication private protocols have primarily been studied only in the two-party case. In contrast, this work focuses on multi-party settings. First, we give efficient private multiparty protocols for sampling a row of the data matrix and for computing arbitrary functions of a random row, where the row index is additively shared among two or more parties. These results can be used to obtain private approximation protocols for several useful combination functionalities. Moreover, these results have some interesting consequences for the general problem of reducing sublinear-communication secure multiparty computation to two-party private information retrieval (PIR). Second, we give protocols for computing approximations (summaries) of the componentwise sum, minimum, and maximum of the columns. Here, while providing a weaker privacy guarantee (where the approximation may leak up to the entire output vector), our protocols are extremely efficient. In particular, the required cryptographic overhead (compared to non-private solutions) is polylogarithmic in the number of rows.

Details DOI

FOCS Conference 2001 Conference Paper

On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates

  • Yael Gertner
  • Tal Malkin
  • Omer Reingold

We prove that, somewhat surprisingly, there is no black-box reduction of (poly-to-one) trapdoor functions to trapdoor predicates (equivalently, to public-key encryption schemes). Our proof follows the methodology that was introduced by R. Impagliazzo and S. Rudich (1989), although we use a new, weaker model of separation.

Details

FOCS Conference 2000 Conference Paper

The Relationship between Public Key Encryption and Oblivious Transfer

  • Yael Gertner
  • Sampath Kannan
  • Tal Malkin
  • Omer Reingold
  • Mahesh Viswanathan 0001

In this paper we study the relationships among some of the most fundamental primitives and protocols in cryptography: public-key encryption (i. e. trapdoor predicates), oblivious transfer (which is equivalent to general secure multi-party computation), key agreement and trapdoor permutations. Our main results show that public-key encryption and oblivious transfer are incomparable under black-box reductions. These separations are tightly matched by our positive results where a restricted (strong) version of one primitive does imply the other primitive. We also show separations between oblivious transfer and key agreement. Finally, we conclude that neither oblivious transfer nor trapdoor predicates imply trapdoor permutations. Our techniques for showing negative results follow the oracle separations of R. Impagliazzo and S. Rudich (1989).

Details
v2026.09.13