Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Efficient, Adaptively Secure, and Composable Oblivious Transfer with a Single, Global CRS.

Seung Geol Choi, Jonathan I. Katz, Hoeteck Wee, Hong-Sheng Zhou

Published Jan 1, 2012• 1 citation
OpenAlex

Abstract

We present a general framework for efficient, universally composable oblivious transfer (OT) protocols in which a single, global, common reference string (CRS) can be used for multiple invocations of oblivious transfer by arbitrary pairs of parties. In addition: • Our framework is round-efficient. E.g., under the DLIN or SXDH assumptions we achieve round-optimal protocols with static security, or 3-round protocols with adaptive security (assuming erasure). • Our resulting protocols are more efficient than any known previously, and in particular yield protocols for string OT using O(1) exponentiations and communicating O(1) group elements. Our result improves on that of Peikert et al. (Crypto 2008), which uses a CRS whose length depends on the number of parties in the network and achieves only static security. Compared to Garay et al. (Crypto 2009), we achieve adaptive security with better round complexity and efficiency. ∗Columbia University. Email: sgchoi@cs.columbia.edu. Portions of this work were done at the University of Maryland. This work was supported in part by the Intelligence Advanced Research Project Activity (IARPA) via DoI/NBC contract Number D11PC20194. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoI/NBC, or the U.S. Government. †Dept. of Computer Science, University of Maryland. Email: jkatz@cs.umd.edu. This work is supported in part by DARPA and by NSF awards #0447075, #1111599, and #1223623. ‡George Washington University. Email: hoeteck@alum.mit.edu. Supported by NSF CAREER award #1237429. §Dept. of Computer Science, Virginia Commonwealth University. Email: hszhou@vcu.edu. Work supported in part by an NSF CI postdoctoral fellowship, and done while at University of Maryland.

Related papers

Efficient and Universally Composable Security Oblivious Transfer

Fenghua Li

Non-committing encryption achieved only semantic security,in contrast,applications often require security against chosen ciphertext attacks.A main ingredient in the previous adaptive universally composable(UC)oblivious transfer protocols are non-committing encryptions.the previous proposals are not UC secure against adaptive adversaries in the so-called non-erase model.A new UC secure oblivious transfer protocols were proposed and schemes utilize two primitives of the verifiably smooth projective hashing and deniable encryption as constructed by.the double trapdoor decryption mechanism based on trapdoor commitment.Our construction is based on the decisional composite residuosity in common reference string (CRS) model.We constructed a two-message(1-round) string oblivious transfer protocol,which improves computational efficient that supports message spaces of size exponential and save O(n)-1 rounds communications efficient than bit-OT protocols.

Dianzi xuebao•Jan 1, 2008•1 citation

A Framework for Efficient Adaptively Secure Composable Oblivious Transfer in the ROM

Paulo S. L. M. Barreto, Bernardo David, Rafael Dowsley +2 more

Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct a round-optimal (2 rounds) universally composable (UC) protocol for oblivious transfer secure against active adaptive adversaries from any OW-CPA secure public-key encryption scheme with certain properties in the random oracle model (ROM). In terms of computation, our protocol only requires the generation of a public/secret-key pair, two encryption operations and one decryption operation, apart from a few calls to the random oracle. In~terms of communication, our protocol only requires the transfer of one public-key, two ciphertexts, and three binary strings of roughly the same size as the message. Next, we show how to instantiate our construction under the low noise LPN, McEliece, QC-MDPC, LWE, and CDH assumptions. Our instantiations based on the low noise LPN, McEliece, and QC-MDPC assumptions are the first UC-secure OT protocols based on coding assumptions to achieve: 1) adaptive security, 2) optimal round complexity, 3) low communication and computational complexities. Previous results in this setting only achieved static security and used costly cut-and-choose techniques.Our instantiation based on CDH achieves adaptive security at the small cost of communicating only two more group elements as compared to the gap-DH based Simplest OT protocol of Chou and Orlandi (Latincrypt 15), which only achieves static security in the ROM.

arXiv:1710.08256•Oct 23, 2017•18 citations

Universally composable oblivious transfer protocol based on VSPH

Jianfeng Ma

A new oblivious transfer protocol was proposed within the framework of universally composable security（UC-DT）.The protocol based on the verifiably smooth projective hashing（VSPH） is against adaptive adversaries in a common reference string（CRS） model.The UC-OT protocol improves computational efficiency with non-committing encryptions（NCE）which is based on decisional compounding residuosity,achieves UC-OT,and it saves O（n）-1 rounds in communication efficiency than bit-OT protocols.Compared with Canetti’s scheme in non-erase model,the message reduced once.Compared with Fischlin’s scheme,the message transfers were reduced twice,and the scheme does not rely on the auxiliary party,therefore it is more practical.

Journal of Communications•Jan 1, 2007•0 citations

On Black-Box Complexity of Universally Composable Security in the CRS model.

Carmit Hazay, Muthuramakrishnan Venkitasubramaniam

In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption mod-elings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following: • Static UC secure computation. Designing the first static UC secure oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer. • One-sided UC secure computation. Designing adaptive UC secure two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation. • Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assum-ing only public-key encryption with oblivious ciphertext generation. As a corollary we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simu-latable public-key encryption (as well as a variety of concrete assumptions). We remark that such a result was not known even under non-black-box constructions.

•Jan 1, 2015•0 citations

Universally Composable Protocols with Relaxed Set-Up Assumptions

Boaz Barak, Ran Canetti, Jesper Buus Nielsen +1 more

A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•228 citations

Essentially Optimal Universally Composable Oblivious Transfer.

Ivan Damgård, Jesper Buus Nielsen, Claudio Orlandi

Oblivious transfer is one of the most important cryptographic primitives, both for theoretical and practical reasons and several protocols were proposed during the years. We provide the first oblivious transfer protocol which is simultaneously optimal on the following list of parameters: Security: it has universal composition. Trust in setup assumptions: only one of the parties needs to trust the setup (and some setup is needed for UC security). Trust in computational assumptions: only one of the parties needs to trust a computational assumption. Round complexity: it uses only two rounds. Communication complexity: it communicates O(1) group elements to transfer one out of two group elements. The Big-O notation hides 32, meaning that the communication is probably not optimal, but is essentially optimal in that the overhead is at least constant. Our construction is based on pairings, and we assume the presence of a key registration authority.

•Jan 1, 2008•4 citations
We present a general framework for efficient, universally composable oblivious transfer (OT) protocols in which a single, global, common reference string (CRS) can be used for multiple invocations of oblivious transfer by arbitrary pairs of parties. In addition: • Our framework is round-efficient. E.g., under the DLIN or SXDH assumptions we achieve round-optimal protocols with static security, or 3-round protocols with adaptive security (assuming erasure). • Our resulting protocols are more efficient than any known previously, and in particular yield protocols for string OT using O(1) exponentiations and communicating O(1) group elements. Our result improves on that of Peikert et al. (Crypto 2008), which uses a CRS whose length depends on the number of parties in the network and achieves only static security. Compared to Garay et al. (Crypto 2009), we achieve adaptive security with better round complexity and efficiency. ∗Columbia University. Email: sgchoi@cs.columbia.edu. Portions of this work were done at the University of Maryland. This work was supported in part by the Intelligence Advanced Research Project Activity (IARPA) via DoI/NBC contract Number D11PC20194. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of IARPA, DoI/NBC, or the U.S. Government. †Dept. of Computer Science, University of Maryland. Email: jkatz@cs.umd.edu. This work is supported in part by DARPA and by NSF awards #0447075, #1111599, and #1223623. ‡George Washington University. Email: hoeteck@alum.mit.edu. Supported by NSF CAREER award #1237429. §Dept. of Computer Science, Virginia Commonwealth University. Email: hszhou@vcu.edu. Work supported in part by an NSF CI postdoctoral fellowship, and done while at University of Maryland.
Non-committing encryption achieved only semantic security,in contrast,applications often require security against chosen ciphertext attacks.A main ingredient in the previous adaptive universally composable(UC)oblivious transfer protocols are non-committing encryptions.the previous proposals are not UC secure against adaptive adversaries in the so-called non-erase model.A new UC secure oblivious transfer protocols were proposed and schemes utilize two primitives of the verifiably smooth projective hashing and deniable encryption as constructed by.the double trapdoor decryption mechanism based on trapdoor commitment.Our construction is based on the decisional composite residuosity in common reference string (CRS) model.We constructed a two-message(1-round) string oblivious transfer protocol,which improves computational efficient that supports message spaces of size exponential and save O(n)-1 rounds communications efficient than bit-OT protocols.
Oblivious Transfer (OT) is a fundamental cryptographic protocol that finds a number of applications, in particular, as an essential building block for two-party and multi-party computation. We construct a round-optimal (2 rounds) universally composable (UC) protocol for oblivious transfer secure against active adaptive adversaries from any OW-CPA secure public-key encryption scheme with certain properties in the random oracle model (ROM). In terms of computation, our protocol only requires the generation of a public/secret-key pair, two encryption operations and one decryption operation, apart from a few calls to the random oracle. In~terms of communication, our protocol only requires the transfer of one public-key, two ciphertexts, and three binary strings of roughly the same size as the message. Next, we show how to instantiate our construction under the low noise LPN, McEliece, QC-MDPC, LWE, and CDH assumptions. Our instantiations based on the low noise LPN, McEliece, and QC-MDPC assumptions are the first UC-secure OT protocols based on coding assumptions to achieve: 1) adaptive security, 2) optimal round complexity, 3) low communication and computational complexities. Previous results in this setting only achieved static security and used costly cut-and-choose techniques.Our instantiation based on CDH achieves adaptive security at the small cost of communicating only two more group elements as compared to the gap-DH based Simplest OT protocol of Chou and Orlandi (Latincrypt 15), which only achieves static security in the ROM.
A new oblivious transfer protocol was proposed within the framework of universally composable security（UC-DT）.The protocol based on the verifiably smooth projective hashing（VSPH） is against adaptive adversaries in a common reference string（CRS） model.The UC-OT protocol improves computational efficiency with non-committing encryptions（NCE）which is based on decisional compounding residuosity,achieves UC-OT,and it saves O（n）-1 rounds in communication efficiency than bit-OT protocols.Compared with Canetti’s scheme in non-erase model,the message reduced once.Compared with Fischlin’s scheme,the message transfers were reduced twice,and the scheme does not rely on the auxiliary party,therefore it is more practical.
In this work, we study the intrinsic complexity of black-box Universally Composable (UC) secure computation based on general assumptions. We present a thorough study in various corruption mod-elings while focusing on achieving security in the common reference string (CRS) model. Our results involve the following: • Static UC secure computation. Designing the first static UC secure oblivious transfer protocol based on public-key encryption and stand-alone semi-honest oblivious transfer. As a corollary we obtain the first black-box constructions of UC secure computation assuming only two-round semi-honest oblivious transfer. • One-sided UC secure computation. Designing adaptive UC secure two-party computation with single corruptions assuming public-key encryption with oblivious ciphertext generation. • Adaptive UC secure computation. Designing adaptively secure UC commitment scheme assum-ing only public-key encryption with oblivious ciphertext generation. As a corollary we obtain the first black-box constructions of adaptive UC secure computation assuming only (trapdoor) simu-latable public-key encryption (as well as a variety of concrete assumptions). We remark that such a result was not known even under non-black-box constructions.
A desirable goal for cryptographic protocols is to guarantee security when the protocol is composed with other protocol instances. Universally composable (UC) protocols provide this guarantee in a strong sense: A protocol remains secure even when composed concurrently with an unbounded number of instances of arbitrary protocols. However, UC protocols for carrying out general tasks are known to exist only if a majority of the participants are honest, or in the common reference string (CRS) model where all parties are assumed to have access to a common string that is drawn from some pre-defined distribution. Furthermore, carrying out many interesting tasks in a UC manner and without honest majority or set-up assumptions is impossible, even if ideally authenticated communication is provided. A natural question is thus whether there exist more relaxed set-up assumptions than the CRS model that still allow for UC protocols. We answer this question in the affirmative: we propose alternative and relaxed set-up assumptions and show that they suffice for reproducing the general feasibility results for UC protocols in the CRS model. These alternative assumptions have the flavor of a "public-key infrastructure": parties have registered public keys, no single registration authority needs to be fully trusted, and no single piece of information has to be globally trusted and available. In addition, unlike known protocols in the CRS model, the proposed protocols guarantee some basic level of security even if the set-up assumption is violated.
Oblivious transfer is one of the most important cryptographic primitives, both for theoretical and practical reasons and several protocols were proposed during the years. We provide the first oblivious transfer protocol which is simultaneously optimal on the following list of parameters: Security: it has universal composition. Trust in setup assumptions: only one of the parties needs to trust the setup (and some setup is needed for UC security). Trust in computational assumptions: only one of the parties needs to trust a computational assumption. Round complexity: it uses only two rounds. Communication complexity: it communicates O(1) group elements to transfer one out of two group elements. The Big-O notation hides 32, meaning that the communication is probably not optimal, but is essentially optimal in that the overhead is at least constant. Our construction is based on pairings, and we assume the presence of a key registration authority.