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

Hongrui Cui; Chun Guo; Xiaojie Guo; Xiao Wang; Kang Yang; Yu Yu

Paper 2025/1818

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

Hongrui Cui

, Shanghai Jiao Tong University

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

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Correlation Robust Hash Functions Multiparty Computation Universal Composition
Contact author(s): rickfreeman @ sjtu edu cn
chun guo sc @ gmail com
guoxiaojie @ sqz ac cn
wangxiao1254 @ gmail com
yangk @ sklc org
yuyu @ yuyu hk
History: 2026-05-27: last of 3 revisions; 2025-10-03: received; See all versions
Short URL: https://ia.cr/2025/1818
License: CC BY

BibTeX

@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}
}