Private information retrieval (PIR) is a protocol for accessing a remote database without revealing the locations that are accessed, even to the server holding the database. We introduce a new family of PIR... protocols in a model where the client is allowed to pre-process the database and use a secret key to access it privately. We obtain protocols that are extremely efficient, approaching the efficiency of trivial (non-private) database access in many important metrics, making them a great candidate for potential practical solutions. The security of our protocols is based on a family of intriguing hard problems which we call learning subspace with noise (LSN), that involve learning a hidden linear code given noisy random codewords. more

While we know that OWFs are the minimal assumption ... underlying classical cryptography, the search for a minimal assumption in quantum cryptography, i.e. in Microcrypt, has been troubling researchers in the field. Although many candidates have been proposed, a definite answer is still out of reach, and the relation between the various contenders is unclear. In this work, we shed light on the relation between two of the more prominent candidates: OWSGs and QEFIDs, suggesting the existence of further heirarchy inside Microcrypt. In particular, we show that average-case problems, with quantum instance and classical solution, become easier in some sense when the solution is efficiently verifiable. more

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

Tatreez is a prominent form of traditional Palestinian embroidery. In this project, we look into the beautiful geometry in tatreez and build an algorithm that generates original tatreez peices. At every run... of the algorithm, a fresh random peice is produced, where different shapes and new patterns appear. The algorithm thus gives birth to a never-ending collection of unique tatreez peices; some traditional-looking, some rather quirky, but all unpredictable! more