Correlated Randomness Reduction in Domain-Restricted Secure Two-Party Computation

Keitaro HIWATASHI, Koji NUIDA

Summary :

Secure two-party computation is a cryptographic tool that enables two parties to compute a function jointly without revealing their inputs. It is known that any function can be realized in the correlated randomness (CR) model, where a trusted dealer distributes input-independent CR to the parties beforehand. Sometimes we can construct more efficient secure two-party protocol for a function g than that for a function f, where g is a restriction of f. However, it is not known in which case we can construct more efficient protocol for domain-restricted function. In this paper, we focus on the size of CR. We prove that we can construct more efficient protocol for a domain-restricted function when there is a “good” structure in CR space of a protocol for the original function, and show a unified way to construct a more efficient protocol in such case. In addition, we show two applications of the above result: The first application shows that some known techniques of reducing CR size for domain-restricted function can be derived in a unified way, and the second application shows that we can construct more efficient protocol than an existing one using our result.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.3 pp.283-290
• Publication Date: 2024/03/01
• Publicized: 2023/10/04
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.2023CIP0023
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Keitaro HIWATASHI
  The University of Tokyo,National Institute of Advanced Industrial Science and Technology
Koji NUIDA
  National Institute of Advanced Industrial Science and Technology,Kyushu University

Keyword

secure computation,  information-theoretic security,  correlated randomness model,  graph