According to the Barrington's theorem, any circuit in NC1 can be converted to a branching program, whose main operation is the composition of permutations (along with the choosing of permutations according to inputs, which we omit here) . So I wonder whether there is a scheme that can directly encrypt the two-line notation of permutation, which also enables to do the composition of permutations on the ciphertext, except the general methods by using FHE/Multilinear mapping on permutation matrices?


1 Answer 1


One can do bounded-length "composition of permutations on the ciphertext"
by Evaluating Branching Programs on Encrypted Data.
Public key length and ciphertext length both scale linearly with the number of permutations.

Leveled FHE can evaluate arbitrary-length compositions of permutations, since iterated composition of permutations can be carried out in low depth. $\:$ (So, one does not need full FHE.)
I don't know of any less general methods than that for arbitrary-length compositions.

  • $\begingroup$ By a quick check, I think that this paper in fact described an interactive protocol based on OT. Do you have any hints about a non-interactive cryptographic scheme? Anyway, thank you. $\endgroup$
    – phan
    Commented Aug 24, 2015 at 4:54
  • $\begingroup$ I don't have any hints about that, but their hint about that forms section 3.1, which starts on page 7. $\hspace{.4 in}$ $\endgroup$
    – user991
    Commented Aug 24, 2015 at 5:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.