Paper 2019/074

Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers

Chun Guo, Jonathan Katz, Xiao Wang, and Yu Yu


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
random permutation modesecure computation
Contact author(s)
wangxiao @ northwestern edu
2019-01-25: received
Short URL
Creative Commons Attribution


      author = {Chun Guo and Jonathan Katz and Xiao Wang and Yu Yu},
      title = {Efficient and Secure Multiparty Computation from Fixed-Key Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2019/074},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.