## CryptoDB

### Noam Mazor

#### Publications

Year
Venue
Title
2021
TCC
Two of the most useful cryptographic primitives that can be constructed from one-way functions are pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs). In order to implement them in practice, the efficiency of such constructions must be considered. The three major efficiency measures are: the seed length, the call complexity to the one-way function, and the adaptivity of these calls. Still, the optimal efficiency of these constructions is not yet fully understood: there exist gaps between the known upper bound and the known lower bound for black-box constructions. A special class of one-way functions called unknown-regular one-way functions is much better understood. Haitner, Harnik and Reingold (CRYPTO 2006) presented a PRG construction with semi-linear seed length and linear number of calls based on a method called randomized iterate. Ames, Gennaro and Venkitasubramaniam (TCC 2012) then gave a construction of UOWHF with similar parameters and using similar ideas. On the other hand, Holenstein and Sinha (FOCS 2012) and Barhum and Holenstein (TCC 2013) showed an almost linear call-complexity lower bound for black-box constructions of PRGs and UOWHFs from one-way functions. Hence Haitner et al. and Ames et al. reached tight constructions (in terms of seed length and the number of calls) of PRGs and UOWHFs from regular one-way functions. These constructions, however, are adaptive. In this work, we present non-adaptive constructions for both primitives which match the optimal call-complexity given by Holenstein and Sinha and Barhum and Holenstein. Our constructions, besides being simple and non-adaptive, are robust also for almost-regular one-way functions.
2020
TCC
Consider a ppt two-party protocol $\varPi = (\mathsf {A} ,\mathsf {B} )$ in which the parties get no private inputs and obtain outputs $O^{\mathsf {A} },O^{\mathsf {B} }\in \left\{ 0,1\right\}$, and let $V^\mathsf {A}$ and $V^\mathsf {B}$ denote the parties’ individual views. Protocol $\varPi$ has $\alpha$-agreement if $\Pr [O^{\mathsf {A} }=O^{\mathsf {B} }] = \tfrac{1}{2}+\alpha$. The leakage of $\varPi$ is the amount of information a party obtains about the event $\left\{ O^{\mathsf {A} }=O^{\mathsf {B} }\right\}$; that is, the leakage$\epsilon$ is the maximum, over $\mathsf {P} \in \left\{ \mathsf {A} ,\mathsf {B} \right\}$, of the distance between $V^\mathsf {P} |_{O^{\mathsf {A} }= O^{\mathsf {B} }}$ and $V^\mathsf {P} |_{O^{\mathsf {A} }\ne O^{\mathsf {B} }}$. Typically, this distance is measured in statistical distance, or, in the computational setting, in computational indistinguishability. For this choice, Wullschleger [TCC ’09] showed that if $\epsilon \ll \alpha$ then the protocol can be transformed into an OT protocol.We consider measuring the protocol leakage by the log-ratio distance (which was popularized by its use in the differential privacy framework). The log-ratio distance between X, Y over domain $\varOmega$ is the minimal $\epsilon \ge 0$ for which, for every $v \in \varOmega$, $\log \frac{\Pr [X=v]}{\Pr [Y=v]} \in [-\epsilon ,\epsilon ]$. In the computational setting, we use computational indistinguishability from having log-ratio distance $\epsilon$. We show that a protocol with (noticeable) accuracy $\alpha \in \varOmega (\epsilon ^2)$ can be transformed into an OT protocol (note that this allows $\epsilon \gg \alpha$). We complete the picture, in this respect, showing that a protocol with $\alpha \in o(\epsilon ^2)$ does not necessarily imply OT. Our results hold for both the information theoretic and the computational settings, and can be viewed as a “fine grained” approach to “weak OT amplification”.We then use the above result to fully characterize the complexity of differentially private two-party computation for the XOR function, answering the open question put by Goyal, Khurana, Mironov, Pandey, and Sahai, [ICALP ’16] and Haitner, Nissim, Omri, Shaltiel, and Silbak [22] [FOCS ’18]. Specifically, we show that for any (noticeable) $\alpha \in \varOmega (\epsilon ^2)$, a two-party protocol that computes the XOR function with $\alpha$-accuracy and $\epsilon$-differential privacy can be transformed into an OT protocol. This improves upon Goyal et al. that only handle $\alpha \in \varOmega (\epsilon )$, and upon Haitner et al. who showed that such a protocol implies (infinitely-often) key agreement (and not OT). Our characterization is tight since OT does not follow from protocols in which $\alpha \in o( \epsilon ^2)$, and extends to functions (over many bits) that “contain” an “embedded copy” of the XOR function.