Paper 2017/030

Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation

Xiao Wang, Samuel Ranellucci, and Jonathan Katz


We propose a simple and efficient framework for obtaining efficient constant-round protocols for maliciously secure two-party computation. Our framework uses a function-independent preprocessing phase to generate authenticated information for the two parties; this information is then used to construct a single ``authenticated'' garbled circuit which is transmitted and evaluated. We also show how to efficiently instantiate the preprocessing phase by designing a highly optimized version of the TinyOT protocol by Nielsen et al. Our overall protocol outperforms existing work in both the single-execution and amortized settings, with or without preprocessing: - In the single-execution setting, our protocol evaluates an AES circuit with malicious security in 37 ms with an online time of just 1 ms. Previous work with the best online time (also 1 ms) requires 124 ms in total; previous work with the best total time requires 62 ms (with 14 ms online time). - If we amortize the computation over 1024 executions, each AES computation requires just 6.7 ms with roughly the same online time as above. The best previous work in the amortized setting has roughly the same total time but does not support function-independent preprocessing. Our work shows that the performance penalty for maliciously secure two-party computation (as compared to semi-honest security) is much smaller than previously believed.

Note: Fix a small bug in the TinyOT improvement

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
two-party computationsecure computation
Contact author(s)
wangxiao @ cs umd edu
2017-05-22: last of 5 revisions
2017-01-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiao Wang and Samuel Ranellucci and Jonathan Katz},
      title = {Authenticated Garbling and Efficient Maliciously Secure Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2017/030},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.