Cryptology ePrint Archive: Report 2019/074

Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers

Chun Guo and Jonathan Katz and Xiao Wang and Yu Yu

Abstract: Many implementations of secure computation use fixed-key AES (modeled as a random permutation); this results in substantial performance benefits due to existing hardware support for~AES and the ability to avoid recomputing the AES key schedule. Surveying these implementations, however, we find that most utilize AES in a heuristic fashion; in the best case this leaves a gap in the security proof, but in many cases we show it allows for explicit attacks.

Motivated by this unsatisfactory state of affairs, we initiate a comprehensive study of how to use fixed-key block ciphers for secure computation---in particular for OT extension and circuit garbling---efficiently and securely. Specifically:

- We consider several notions of pseudorandomness for hash functions (e.g., correlation robustness), and show provably secure schemes for OT extension, garbling, and other applications based on hash functions satisfying these notions.

- We provide provably secure constructions, in the random-permutation model, of hash functions satisfying the different notions of pseudorandomness we consider.

Taken together, our results provide end-to-end security proofs for implementations of secure-computation protocols based on fixed-key block ciphers (modeled as random permutations). Perhaps surprisingly, at the same time our work also results in noticeable performance improvements over the state-of-the-art.

Category / Keywords: cryptographic protocols / random permutation mode, secure computation,

Date: received 21 Jan 2019

Contact author: wangxiao at northwestern edu

Available format(s): PDF | BibTeX Citation

Version: 20190125:221500 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]