Cryptology ePrint Archive: Report 2014/400

Composable Oblivious Extended Permutations

Peeter Laud and Jan Willemson

Abstract: An extended permutation is a function f : {1,...,m} -> {1,...,n}, used to map an n-element vector a to an m-element vector b by b_i = a_{f(i)}. An oblivious extended permutation allows this mapping to be done while preserving the privacy of a, b and f in a secure multiparty computation protocol. Oblivious extended permutations have several uses, with private function evaluation (PFE) being the theoretically most prominent one.

In this paper, we propose a new technique for oblivious evaluation of extended permutations. Our construction is at least as efficient as the existing techniques, conceptually simpler, and has wider applicability. Our technique allows the party providing the description of f to be absent during the computation phase of the protocol. Moreover, that party does not even have to exist - we show how to compute the private representation of f from private data that may itself be computed from the inputs of parties. In other words, our oblivious extended permutations can be freely composed with other privacy-preserving operations in a multiparty computation.

Category / Keywords: cryptographic protocols / Secure multiparty computation, Private function evaluation, Extended permutations

Date: received 30 May 2014, last revised 23 Jul 2014

Contact author: peeter laud at cyber ee

Available format(s): PDF | BibTeX Citation

Version: 20140723:150114 (All versions of this report)

Short URL: ia.cr/2014/400

Discussion forum: Show discussion | Start new discussion