Paper 2014/400

Composable Oblivious Extended Permutations

Peeter Laud and Jan Willemson


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Secure multiparty computationPrivate function evaluationExtended permutations
Contact author(s)
peeter laud @ cyber ee
2014-07-23: revised
2014-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Peeter Laud and Jan Willemson},
      title = {Composable Oblivious Extended Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2014/400},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.