Paper 2023/1225

One-Message Secure Reductions: On the Cost of Converting Correlations

Yuval Ishai, Technion – Israel Institute of Technology
Mahimna Kelkar, Cornell University
Varun Narayanan, University of California, Los Angeles
Liav Zafar, Technion – Israel Institute of Technology

Correlated secret randomness is a useful resource for secure computation protocols, often enabling dramatic speedups compared to protocols in the plain model. This has motivated a line of work on identifying and securely generating useful correlations. Different kinds of correlations can vary greatly in terms of usefulness and ease of generation. While there has been major progress on efficiently generating oblivious transfer (OT) correlations, other useful kinds of correlations are much more costly to generate. Thus, it is highly desirable to develop efficient techniques for securely converting copies of a given source correlation into copies of a given target correlation, especially when the former are cheaper to generate than the latter. In this work, we initiate a systematic study of such conversions that only involve a single uni-directional message. We refer to such a conversion as a one-message secure reduction (OMSR). Recent works (Agarwal et al, Eurocrypt 2022; Khorasgani et al, Eurocrypt 2022) studied a similar problem when no communication is allowed; this setting is quite restrictive, however, with few non-trivial conversions being feasible. The OMSR setting substantially expands the scope of feasible results, allowing for direct applications to existing MPC protocols. We obtain the following positive and negative results. - OMSR constructions. We present a general rejection-sampling based technique for OMSR with OT source correlations. We apply it to substantially improve in the communication complexity of optimized protocols for distributed symmetric cryptography (Dinur et al., Crypto 2021). - OMSR lower bounds. We develop general techniques for proving lower bounds on the communication complexity of OMSR, matching our positive results up to small constant factors.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
Contact author(s)
yuvali @ cs technion ac il
mahimna @ cs cornell edu
varunnkv @ gmail com
liavz @ cs technion ac il
2023-08-15: approved
2023-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuval Ishai and Mahimna Kelkar and Varun Narayanan and Liav Zafar},
      title = {One-Message Secure Reductions: On the Cost of Converting Correlations},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1225},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.