{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:40:06Z","timestamp":1751924406555,"version":"3.41.2"},"reference-count":42,"publisher":"International Association for Cryptologic Research","issue":"2","license":[{"start":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T00:00:00Z","timestamp":1736726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,6,2]]},"abstract":"<jats:p>We present unconditionally perfectly secure protocols in the semi-honest setting for several functionalities: (1) private elementwise equality; (2) private bitwise integer comparison; and (3) bit-decomposition. These protocols are built upon a new concept called Shared Oblivious Transfer (Shared OT). Shared OT extends the one-out-of-N String OT by replacing strings with integers modulo M and allowing additive secret-sharing of all inputs and outputs. These extensions can be implemented by simple local computations without incurring additional OT invocations. We believe our  Shared OT may be of independent interest.<\/jats:p>\n          <jats:p>Our protocols demonstrate the best round, communication, and computational complexities compared to all other protocols secure in a similar setting. Moreover, all of our protocols involve either 2 or 3 rounds. <\/jats:p>","DOI":"10.62056\/a0wa3z10k","type":"journal-article","created":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:09Z","timestamp":1751922549000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Shared OT and Its Applications"],"prefix":"10.62056","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-1698-2176","authenticated-orcid":false,"given":"Lucas","family":"Piske","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03efmqc40","id-type":"ROR","asserted-by":"publisher"}],"name":"Arizona State University","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7048-6585","authenticated-orcid":false,"given":"Jeroen","family":"van de Graaf","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/0176yjw32","id-type":"ROR","asserted-by":"publisher"}],"name":"Universidade Federal de Minas Gerais","place":["Brazil"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8298-6250","authenticated-orcid":false,"given":"Anderson","family":"Nascimento","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/05t1y0b59","id-type":"ROR","asserted-by":"publisher"}],"name":"Visa (United States)","place":["United States"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6013-9512","authenticated-orcid":false,"given":"Ni","family":"Trieu","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/03efmqc40","id-type":"ROR","asserted-by":"publisher"}],"name":"Arizona State University","place":["United States"]}]}],"member":"48349","published-online":{"date-parts":[[2025,7,7]]},"reference":[{"key":"ref1:FOCS:Yao86","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1109\/SFCS.1986.25","article-title":"How to Generate and Exchange Secrets (Extended Abstract)","author":"Andrew Chi-Chih Yao","year":"1986"},{"key":"ref2:STOC:BeaMicRog90","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1145\/100216.100287","article-title":"The Round Complexity of Secure Protocols (Extended\n  Abstract)","author":"Donald Beaver","year":"1990"},{"key":"ref3:C:GoyLiuSon19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-3-030-26951-7_4","article-title":"Communication-Efficient Unconditional MPC with Guaranteed\n  Output Delivery","volume":"11693","author":"Vipul Goyal","year":"2019"},{"key":"ref4:EPRINT:YNKM24","volume-title":"Unconditional Security using (Random) Anonymous Bulletin\n  Board","author":"Albert Yu","year":"2024"},{"key":"ref5:FOCS:Yao82b","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1109\/SFCS.1982.38","article-title":"Protocols for Secure Computations (Extended Abstract)","author":"Andrew Chi-Chih Yao","year":"1982"},{"key":"ref6:demmler2015aby","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2015.23113","article-title":"ABY-A framework for efficient mixed-protocol secure\n  two-party computation.","author":"Daniel Demmler","year":"2015"},{"key":"ref7:C:RosRoy21","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/978-3-030-84242-0_5","article-title":"Three Halves Make a Whole? Beating the Half-Gates Lower\n  Bound for Garbled Circuits","volume":"12825","author":"Mike Rosulek","year":"2021"},{"key":"ref8:C:DILO22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-031-15985-5_3","article-title":"Authenticated Garbling from Simple Correlations","volume":"13510","author":"Samuel Dittmer","year":"2022"},{"key":"ref9:C:DDGIKK23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-031-38557-5_12","article-title":"Perfect MPC over Layered Graphs","volume":"14081","author":"Bernardo David","year":"2023"},{"key":"ref10:EC:HeaKolNg24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-031-58740-5_7","article-title":"Garbled Circuit Lookup Tables with Logarithmic Number of\n  Ciphertexts","author":"David Heath","year":"2024"},{"key":"ref11:ICALP:LipTof13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"645","DOI":"10.1007\/978-3-642-39212-2_56","article-title":"Secure Equality and Greater-Than Tests with Sublinear Online\n  Complexity","volume":"7966","author":"Helger Lipmaa","year":"2013"},{"key":"ref12:EPRINT:Yu11","volume-title":"Sign Modules in Secure Arithmetic Circuits","author":"Ching-Hua Yu","year":"2011"},{"key":"ref13:PKC:NisOht07","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/978-3-540-71677-8_23","article-title":"Multiparty Computation for Interval, Equality, and\n  Comparison Without Bit-Decomposition Protocol","volume":"4450","author":"Takashi Nishide","year":"2007"},{"key":"ref14:CCS:BIKMMP17","doi-asserted-by":"publisher","first-page":"1175","DOI":"10.1145\/3133956.3133982","article-title":"Practical Secure Aggregation for Privacy-Preserving Machine\n  Learning","author":"Keith Bonawitz","year":"2017"},{"key":"ref15:CCS:NWKT24","doi-asserted-by":"publisher","first-page":"4420","DOI":"10.1145\/3658644.3670337","article-title":"AITIA: Efficient Secure Computation of Bivariate Causal\n  Discovery","author":"Truong Son Nguyen","year":"2024"},{"key":"ref16:EC:vBaPu24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-031-58740-5_12","article-title":"Fuzzy Private Set Intersection with Large Hyperballs","author":"Aron van Baarsen","year":"2024"},{"key":"ref17:PoPETS:MMTSBC24","doi-asserted-by":"publisher","first-page":"49","DOI":"10.56553\/popets-2024-0040","article-title":"Delegated Private Matching For Compute","volume":"2024","author":"Dimitris Mouris","year":"2024","journal-title":"PoPETs"},{"key":"ref18:AC:BlaKol04","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/978-3-540-30539-2_36","article-title":"Strong Conditional Oblivious Transfer and Computing on\n  Intervals","volume":"3329","author":"Ian F. Blake","year":"2004"},{"key":"ref19:6412624","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1109\/WIFS.2012.6412624","article-title":"Improving the DGK comparison protocol","author":"Thijs Veugen","year":"2012"},{"key":"ref20:ASIACCS:SamHuJia13","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1145\/2484313.2484386","article-title":"An efficient and probabilistic secure bit-decomposition","author":"Bharath K. Samanthula","year":"2013"},{"key":"ref21:SCN:YuYan12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-642-32928-9_24","article-title":"Probabilistically Correct Secure Arithmetic Computation for\n  Modular Conversion, Zero Test, Comparison, MOD and Exponentiation","volume":"7485","author":"Ching-Hua Yu","year":"2012"},{"key":"ref22:TCC:DFKNT06","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/11681878_15","article-title":"Unconditionally Secure Constant-Rounds Multi-party\n  Computation for Equality, Comparison, Bits and Exponentiation","volume":"3876","author":"Ivan Damg\u00e5rd","year":"2006"},{"key":"ref23:rei09","doi-asserted-by":"publisher","first-page":"325","DOI":"10.5220\/0002233603250330","article-title":"Multiparty comparison-an improved multiparty protocol for\n  comparison of secret-shared values","volume":"1","author":"Tord Ingolf Reistad","year":"2009"},{"key":"ref24:ICISC:ReiTof09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/978-3-642-14423-3_17","article-title":"Linear, Constant-Rounds Bit-Decomposition","volume":"5984","author":"Tord Reistad","year":"2010"},{"key":"ref25:C:DamNie03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-540-45146-4_15","article-title":"Universally Composable Efficient Multiparty Computation from\n  Threshold Homomorphic Encryption","volume":"2729","author":"Ivan Damg\u00e5rd","year":"2003"},{"key":"ref26:RSA:Toft09","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-642-00862-7_24","article-title":"Constant-Rounds, Almost-Linear Bit-Decomposition of Secret\n  Shared Values","volume":"5473","author":"Tomas Toft","year":"2009"},{"key":"ref27:rivestot","volume-title":"Unconditionally secure commitment and Oblivious Transfer\n  Schemes Using Private Channels and a Trusted Initializer","author":"Ronald L. Rivest"},{"key":"ref28:STOC:Beaver97","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1145\/258533.258637","article-title":"Commodity-Based Cryptography (Extended Abstract)","author":"Donald Beaver","year":"1997"},{"key":"ref29:EPRINT:Rabin05","volume-title":"How To Exchange Secrets with Oblivious Transfer","author":"Michael O. Rabin","year":"2005"},{"key":"ref30:C:EveGolLem82","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-1-4757-0602-4_19","article-title":"A Randomized Protocol for Signing Contracts","author":"Shimon Even","year":"1982"},{"key":"ref31:C:KolKum13","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/978-3-642-40084-1_4","article-title":"Improved OT Extension for Transferring Short Secrets","volume":"8043","author":"Vladimir Kolesnikov","year":"2013"},{"key":"ref32:CCS:KKRT16","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1145\/2976749.2978381","article-title":"Efficient Batched Oblivious PRF with Applications to\n  Private Set Intersection","author":"Vladimir Kolesnikov","year":"2016"},{"key":"ref33:ACNS:Couteau18","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-93387-0_16","article-title":"New Protocols for Secure Equality Test and Comparison","volume":"10892","author":"Geoffroy Couteau","year":"2018"},{"key":"ref34:CCS:RRKCGR20","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1145\/3372297.3417274","article-title":"CrypTFlow2: Practical 2-Party Secure Inference","author":"Deevashwer Rathee","year":"2020"},{"key":"ref35:C:EGKRS20","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1007\/978-3-030-56880-1_29","article-title":"Improved Primitives for MPC over Mixed Arithmetic-Binary\n  Circuits","volume":"12171","author":"Daniel Escudero","year":"2020"},{"key":"ref36:ISC:NMOHI03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/10958513_12","article-title":"Unconditionally Secure Homomorphic Pre-distributed Bit\n  Commitment and Secure Two-Party Computations","volume":"2851","author":"Anderson C. A. Nascimento","year":"2003"},{"key":"ref37:C:CrevdGTap95","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-44750-4_9","article-title":"Committed Oblivious Transfer and Private Multi-Party\n  Computation","volume":"963","author":"Claude Cr\u00e9peau","year":"1995"},{"key":"ref38:C:IKNP03","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-45146-4_9","article-title":"Extending Oblivious Transfers Efficiently","volume":"2729","author":"Yuval Ishai","year":"2003"},{"key":"ref39:C:PRTY19","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-030-26954-8_13","article-title":"SpOT-Light: Lightweight Private Set Intersection from\n  Sparse OT Extension","volume":"11694","author":"Benny Pinkas","year":"2019"},{"key":"ref40:C:Roy22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1007\/978-3-031-15802-5_23","article-title":"SoftSpokenOT: Quieter OT Extension from Small-Field\n  Silent VOLE in the Minicrypt Model","volume":"13507","author":"Lawrence Roy","year":"2022"},{"key":"ref41:C:BCGIKR22","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1007\/978-3-031-15979-4_21","article-title":"Correlated Pseudorandomness from Expand-Accumulate Codes","volume":"13508","author":"Elette Boyle","year":"2022"},{"key":"ref42:C:RagRinTan23","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1007\/978-3-031-38551-3_19","article-title":"Expand-Convolute Codes for Pseudorandom Correlation\n  Generators from LPN","volume":"14084","author":"Srinivasan Raghuraman","year":"2023"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T21:09:20Z","timestamp":1751922560000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/2\/4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,7]]},"references-count":42,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,7,7]]}},"URL":"https:\/\/doi.org\/10.62056\/a0wa3z10k","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,7]]},"assertion":[{"value":"2025-01-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-44"}}