All reports by Author Ron Rothblum:

__
TR24-088
| 29th April 2024
__

Tamer Mour, Alon Rosen, Ron Rothblum#### Locally Testable Tree Codes

__
TR23-118
| 17th August 2023
__

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum#### Distribution-Free Proofs of Proximity

Revisions: 2

__
TR15-024
| 16th February 2015
__

Oded Goldreich, Tom Gur, Ron Rothblum#### Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs

__
TR13-183
| 22nd December 2013
__

Yael Tauman Kalai, Ran Raz, Ron Rothblum#### How to Delegate Computations: The Power of No-Signaling Proofs

Revisions: 1

__
TR13-107
| 7th August 2013
__

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum#### Efficient Multiparty Protocols via Log-Depth Threshold Formulae

__
TR13-078
| 28th May 2013
__

Tom Gur, Ron Rothblum#### Non-Interactive Proofs of Proximity

Revisions: 1

__
TR11-159
| 27th November 2011
__

Oded Goldreich, Ron Rothblum#### Enhancements of Trapdoor Permutations

Revisions: 1
,
Comments: 1

__
TR10-146
| 21st September 2010
__

Ron Rothblum#### Homomorphic Encryption: from Private-Key to Public-Key

__
TR10-145
| 21st September 2010
__

Ron Rothblum#### A Taxonomy of Enhanced Trapdoor Permutations

Tamer Mour, Alon Rosen, Ron Rothblum

Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the $i$-th codeword symbol depends only on the first $i$ message symbols. Codewords should have good ... more >>>

Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum

Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions $f : [n] \to \{0,1\}$ having a certain property $\Pi$ and reject functions that are $\varepsilon$-far from $\Pi$, where the distance is measured ... more >>>

Oded Goldreich, Tom Gur, Ron Rothblum

Proofs of proximity are probabilistic proof systems in which the verifier only queries a sub-linear number of input bits, and soundness only means that, with high probability, the input is close to an accepting input. In their minimal form, called Merlin-Arthur proofs of proximity (MAP), the verifier receives, in addition ... more >>>

Yael Tauman Kalai, Ran Raz, Ron Rothblum

We construct a 1-round delegation scheme (i.e., argument-system) for every language computable in time t=t(n), where the running time of the prover is poly(t) and the running time of the verifier is n*polylog(t). In particular, for every language in P we obtain a delegation scheme with almost linear time verification. ... more >>>

Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves

security against a single corrupted party. Such protocols are typically easy

to construct as they may employ techniques that do not ...
more >>>

Tom Gur, Ron Rothblum

We initiate a study of non-interactive proofs of proximity. These proof-systems consist of a verifier that wishes to ascertain the validity of a given statement, using a short (sublinear length) explicitly given proof, and a sublinear number of queries to its input. Since the verifier cannot even read the entire ... more >>>

Oded Goldreich, Ron Rothblum

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

Ron Rothblum

We show that any private-key encryption scheme that is weakly

homomorphic with respect to addition modulo 2, can be transformed

into a public-key encryption scheme. The homomorphic feature

referred to is a minimalistic one; that is, the length of a

homomorphically generated encryption should be independent of the

number of ...
more >>>

Ron Rothblum

Trapdoor permutations (TDPs) are among the most widely studied

building blocks of cryptography. Despite the extensive body of

work that has been dedicated to their study, in many setting and

applications (enhanced) trapdoor permutations behave

unexpectedly. In particular, a TDP may become easy to invert when

the inverter is given ...
more >>>