Our construction is the first such protocol under reasonably standard cryptographic assumptions. That is, existence of a hash function collection that is collision resistent with respect to circuits of subexponential size, and existence of trapdoor permutations that are secure with respect to circuits of quasi-polynomial size.
We introduce a new technique: ``protocol condensing''. That is, taking a protocol that has strong security properties but requires *super-polynomial* communication and computation, and then transforming it into a protocol with *polynomial* communication and computation, that still inherits the strong security properties of the original protocol. Our result is obtained by combining this technique with previous techniques of Canetti, Lindell, Ostrovsky, and Sahai (STOC '02) and Pass (STOC '04).
Category / Keywords: Non-malleable protocols, concurrent composition, multi-party secure computation Publication Info: FOCS 2005 Date: received 10 Apr 2005, last revised 26 Aug 2005 Contact author: boaz at cs princeton edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: Improved introduction and other rewrites. No change in technical content from previous version. Version: 20050826:163302 (All versions of this report) Discussion forum: Show discussion | Start new discussion