Abstract
In [1], the authors presented a unified framework for constructing Universally Composable (UC) secure computation protocols, assuming only enhanced trapdoor permutations. In this work, we weaken the hardness assumption underlying the unified framework to only the existence of a stand-alone secure semi-honest Oblivious Transfer (OT) protocol. The new framwork directly implies new and improved UC feasibility results from only the existence of a semi-honest OT protocol in various models. Since in many models, the existence of UC-OT implies the existence of a semi-honest OT protocol.
Furthermore, we show that by relying on a more fine-grained analysis of the unified framework, we obtain concurrently secure computation protocols with super-polynomial-time simulation (SPS), based on the necessary assumption of the existence of a semi-honest OT protocol that can be simulated in super-polynomial times. When the underlying OT protocol has constant rounds, the SPS secure protocols constructed also have constant rounds. This yields the first construction of constant-round secure computation protocols that satisfy a meaningful notions of concurrent security (i.e., SPS security) based on tight assumptions.
A notable corollary following from our new unifed framwork is that stand-alone (or bounded-concurrent) password authenticated key-exchange protocols (PAKE) can be constructed from only semi-honest OT protocols; combined with the result of [2] that the existence of PAKE protocols implies that of OT, we derive a tight characterization of PAKE protocols.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Lin, H., Pass, R., Venkitasubramaniam, M.: A unified framework for concurrent security: universal composability from stand-alone non-malleability. In: STOC, pp. 179–188 (2009)
Nguyen, M.-H.: The Relationship Between Password-Authenticated Key Exchange and Other Cryptographic Primitives. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 457–475. Springer, Heidelberg (2005)
Yao, A.C.C.: How to generate and exchange secrets (extended abstract). In: FOCS, pp. 162–167 (1986)
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC, pp. 218–229 (1987)
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: FOCS, pp. 136–145 (2001)
Canetti, R., Fischlin, M.: Universally Composable Commitments. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 19–40. Springer, Heidelberg (2001)
Canetti, R., Kushilevitz, E., Lindell, Y.: On the Limitations of Universally Composable Two-party Computation without Set-up Assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 68–86. Springer, Heidelberg (2003)
Lindell, Y.: General composition and universal composability in secure multi-party computation. In: FOCS, pp. 394–403 (2003)
Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: STOC, pp. 494–503 (2002)
Barak, B., Canetti, R., Nielsen, J.B., Pass, R.: Universally composable protocols with relaxed set-up assumptions. In: FOCS, pp. 186–195 (2004)
Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally Composable Security with Global Setup. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 61–85. Springer, Heidelberg (2007)
Kalai, Y.T., Lindell, Y., Prabhakaran, M.: Concurrent general composition of secure protocols in the timing model. In: STOC, pp. 644–653 (2005)
Canetti, R., Pass, R., Shelat, A.: Cryptography from sunspots: How to use an imperfect reference string. In: FOCS, pp. 249–259 (2007)
Pass, R.: Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 160–176. Springer, Heidelberg (2003)
Prabhakaran, M., Sahai, A.: New notions of security: achieving universal composability without trusted setup. In: STOC, pp. 242–251 (2004)
Barak, B., Sahai, A.: How to play almost any mental game over the net - concurrent composition via super-polynomial simulation. In: FOCS, pp. 543–552 (2005)
Micali, S., Pass, R., Rosen, A.: Input-indistinguishable computation. In: FOCS, pp. 367–378 (2006)
Goldreich, O.: Foundations of Cryptography — Basic Tools. Cambridge University Press (2001)
Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20–31 (1988)
Ishai, Y., Prabhakaran, M., Sahai, A.: Founding Cryptography on Oblivious Transfer – Efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572–591. Springer, Heidelberg (2008)
Damgård, I., Nielsen, J.B., Orlandi, C.: On the Necessary and Sufficient Assumptions for UC Computation. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 109–127. Springer, Heidelberg (2010)
Maji, H.K., Prabhakaran, M., Rosulek, M.: A Zero-One Law for Cryptographic Complexity with Respect to Computational UC Security. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 595–612. Springer, Heidelberg (2010)
Goyal, V.: Constant round non-malleable protocols using one way functions. In: STOC, pp. 695–704 (2011)
Dwork, C., Naor, M., Sahai, A.: Concurrent zero-knowledge. J. ACM 51(6), 851–898 (2004)
Pass, R.: Bounded-concurrent secure multi-party computation with a dishonest majority. In: STOC, pp. 232–241. ACM, New York (2004)
Katz, J.: Which Languages Have 4-Round Zero-Knowledge Proofs? In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 73–88. Springer, Heidelberg (2008)
Groth, J., Ostrovsky, R.: Cryptography in the Multi-string Model. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 323–341. Springer, Heidelberg (2007)
Goyal, V., Ishai, Y., Sahai, A., Venkatesan, R., Wadia, A.: Founding Cryptography on Tamper-Proof Hardware Tokens. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 308–326. Springer, Heidelberg (2010)
Damgård, I., Groth, J.: Non-interactive and reusable non-malleable commitment schemes. In: STOC, pp. 426–437 (2003)
Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. In: FOCS, pp. 541–550 (2010)
Garg, S., Goyal, V., Jain, A., Sahai, A.: Concurrently Secure Computation in Constant Rounds. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 99–116. Springer, Heidelberg (2012)
Barak, B.: How to go beyond the black-box simulation barrier. In: FOCS, pp. 106–115 (2001)
Pass, R., Rosen, A.: Bounded-concurrent secure two-party computation in a constant number of rounds. In: FOCS. p. 404 (2003)
Lindell, Y.: Lower bounds and impossibility results for concurrent self composition. J. Cryptology 21(2), 200–249 (2008)
Barak, B., Canetti, R., Lindell, Y., Pass, R., Rabin, T.: Secure computation without authentication. J. Cryptology 24(4), 720–760 (2011)
Goyal, V., Jain, A., Ostrovsky, R.: Password-Authenticated Session-Key Generation on the Internet in the Plain Model. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 277–294. Springer, Heidelberg (2010)
Lindell, Y.: Bounded-concurrent secure two-party computation without setup assumptions. In: STOC, pp. 683–692 (2003)
Barak, B., Lindell, Y.: Strict polynomial-time in simulation and extraction. SIAM J. Comput. 33(4), 738–818 (2004)
Ishai, Y., Kushilevitz, E., Lindell, Y., Petrank, E.: Black-box constructions for secure computation. In: STOC, pp. 99–108 (2006)
Haitner, I.: Semi-honest to Malicious Oblivious Transfer—The Black-Box Way. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 412–426. Springer, Heidelberg (2008)
Lin, H., Pass, R., Tseng, W.-L.D., Venkitasubramaniam, M.: Concurrent Non-Malleable Zero Knowledge Proofs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 429–446. Springer, Heidelberg (2010)
Lin, H., Pass, R.: Non-malleability amplification. In: STOC, pp. 189–198 (2009)
Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. To appear in FOCS 2010 (2010)
Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC, pp. 503–513 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Pass, R., Lin, H., Venkitasubramaniam, M. (2012). A Unified Framework for UC from Only OT. In: Wang, X., Sako, K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34961-4_42
Download citation
DOI: https://doi.org/10.1007/978-3-642-34961-4_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34960-7
Online ISBN: 978-3-642-34961-4
eBook Packages: Computer ScienceComputer Science (R0)