Paper 2025/1818

Simulation-based Security Notion of Correlation Robust Hashing with Applications to MPC

Chun Guo, School of Cyber Science and Technology, Shandong University, Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education, Shandong University, Shandong Research Institute of Industrial Technology

Xiaojie Guo, Shanghai Qi Zhi Institute, Shanghai Jiao Tong University

Xiao Wang, Northwestern University

Kang Yang, State Key Laboratory of Cryptology

Yu Yu, Shanghai Jiao Tong University, Shanghai Qi Zhi Institute

Abstract

This work studies the security and constructions of correlation robust (CR) hash functions in secure multi-party computation (MPC). Existing definitions of CR hashing are all game-based (i.e., no simulator to achieve programmability or extractability), but MPC protocols are proven secure in the simulation-based models including both stand-alone and universal composability models. We found that for some MPC protocols, e.g., TinyOT-like authenticated-triple generation protocols and correlated oblivious transfer (COT) extension protocols, such a mismatch could lead to a gap in security proofs, even for the semi-honest adversary and stand-alone model. To bridge the gap, we introduce a simulation-based security notion for CR hash functions to allow secure composition. Instead of building from scratch, we introduce such a simulator to a wide class of existing ideal-cipher-based CR hashing constructions, and derive the security bound from their original game-based CR security. This enables us to obtain an efficient CR hashing construction making just one call to a blockcipher, and is much more efficient than the construction from a random oracle used in previous TinyOT-like protocols. We showcase the utility of the new CR notion in easing security proofs and mitigating the risk of errors on two classes of protocols: (1) authenticated-triple generation protocols in the TinyOT family with a countermeasure; (2) COT extension protocols with bootstrapped iterations.

Note: Revised Section 6 and introduced a toy example in Section 2.4

@misc{cryptoeprint:2025/1818,
      author = {Hongrui Cui and Chun Guo and Xiaojie Guo and Xiao Wang and Kang Yang and Yu Yu},
      title = {Simulation-based Security Notion of Correlation Robust Hashing with Applications to {MPC}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1818},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1818}
}