International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Yuval Ishai , Technion
Mahimna Kelkar , Cornell University, Cornell Tech
Varun Narayanan , Technion
Liav Zafar , Technion
DOI: 10.1007/978-3-031-38557-5_17 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 efficiency 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-way secure reduction (OMSR). Recent works (Agarwal et. al, Eurocrypt 2022; Khorasgani et. al, Eurocrypt 2022) studied a similar problem when no communication was 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.
  title={One-Message Secure Reductions: On the Cost of Converting Correlations},
  author={Yuval Ishai and Mahimna Kelkar and Varun Narayanan and Liav Zafar},