Suppose we wish to encode a huge amount of data that is created across multiple generations. Each generation creates new information and we would like to encode it in an online manner into a... repository. We want the encoding to be such that we can still decode and retrieve the information even if few errors happened along the way. Further, we want to be able to test that the stored data is properly encoded by reading only a few locations in the (potentially huge) repository. In this work, we build the first locally testable tree codes, which offer a solution to such a scenario. more

Correlation intractable hash functions are functions where it is hard to find an input-output pair satisfying some desired correlation. Such functions are a central tool in communication-efficient... cryptographic protocols. In this work, we investigate the complexity of building correlation intractable hash functions from basic cryptographic building blocks: one-way functions, i.e. functions that are hard to invert, or collision-resistant hash functions, i.e. functions under which it is hard to find two colliding inputs. more

Imagine you want to prove a computational statement over some secret (e.g. a password) without leaking any information about the secret. You also want to do so by sending a one-shot proof... , without any interaction with a verifier. Non-interactive zero knowledge (NIZK) proofs are the tool to accomplish this cryptographic task. In this work, we lower the bar for the cryptographic structure needed to build NIZKs. Specifically, we build such proofs where security is based on the LPN and DDH assumptions, which encompass much weaker structure than the assumptions known to imply NIZKs before, e.g. LWE, QR or Factoring. more

One of the main goals in the design of secure computation protocols is to reduce the communication cost needed for privacy. In... this work, we introduce a new cryptographic building block, which we call trapdoor hash functions, that allows to build communication-efficient protocols for prominent cryptographic functionalities, e.g. oblivious transfer and private information retreival. more

Consider the problem of privately outsourcing a database to remote server(s). While encryption can be used to hide the data itself, one must use oblivious RAM to hide the access pattern to the data. In this... work, we make progress in constructing efficient oblivious RAM protocols where the database is stored in two or more servers. more