Paper 2018/308
On perfectly secure 2PC in the OThybrid model
Bar Alon and Anat PaskinCherniavsky
Abstract
A well known result by Kilian (ACM 1988) asserts that general secure two computation (2PC) with statistical security, can be based on OT. Specifically, in the clientserver model, where only one party  the client  receives an output, Kilian’s result shows that given the ability to call an ideal oracle that computes OT, two parties can securely compute an arbitrary function of their inputs with unconditional security. Ishai et al. (EUROCRYPT 2011) further showed that this can be done efficiently for every twoparty functionality in $\mathrm{NC}^1$ in a single round. However, their results only achieve statistical security, namely, it is allowed to have some error in security. This leaves open the natural question as to which clientserver functionalities can be computed with perfect security in the OThybrid model, and what is the round complexity of such computation. So far, only a handful of functionalities were known to have such protocols. In addition to the obvious theoretical appeal of the question towards better understanding secure computation, perfect, as opposed to statistical reductions, may be useful for designing secure multiparty protocols with high concrete efficiency, achieved by eliminating the dependence on a security parameter. In this work, we identify a large class of clientserver functionalities $f:\mathcal{X}\times \mathcal{Y}\mapsto \{0,1\}$, where the server's domain $\mathcal{X}$ is larger than the client's domain $\mathcal{Y}$, that have a perfect reduction to OT. Furthermore, our reduction is 1round using an oracle to secure evaluation of many parallel invocations of $\binom21$bitOT, as done by Ishai et al. (EUROCRYPT 2011). Interestingly, the set of functions that we are able to compute was previously identified by Asharov (TCC 2014) in the context of fairness in twoparty computation, naming these functions fulldimensional. Our result also extends to randomized nonBoolean functions $f:\mathcal{X}\times \mathcal{Y}\mapsto\{0,\ldots,k1\}$ satisfying $\mathcal{X}>(k1)\cdot\mathcal{Y}$.
Note: Improved writeup.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. MINOR revision.
 Keywords
 2PCperfect securityOThybrid model
 Contact author(s)

alonbar08 @ gmail com
anatpc @ ariel ac il  History
 20210120: last of 7 revisions
 20180403: received
 See all versions
 Short URL
 https://ia.cr/2018/308
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/308, author = {Bar Alon and Anat PaskinCherniavsky}, title = {On perfectly secure 2PC in the OThybrid model}, howpublished = {Cryptology ePrint Archive, Paper 2018/308}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/308}}, url = {https://eprint.iacr.org/2018/308} }