Revealing random bit permutation I am new in cryptography. I want to determine the complexity of revealing a random bit permutation which is used as block cipher for plaintexts (bitstrings of length n). An adversary catches different ciphertexts (the permuted bitstrings of length n) and he also knows the set of possible plaintexts. If he tries all possible inverse permutations at the end there are more permutations that result in legal plaintexts. The difference is that all of the remained permutations result in different sending order of the plaintexts. Is it possible to reveal the used permutation? 

Any insight will be helpful.
Thank you in advance
I thought you were using a block cipher, i.e. a pseudorandom permutation. Instead as per your comment you are only permuting the order of the plaintext bits. This is not secure.

For example, you can imagine the bit permutation is an n-by-n square matrix, where each row and column has a single 1 and the rest 0s. The input and output are then vectors of size n.

Take a random input and output pair. If each has $\frac{n}{2}$ 1s and 0s on average, you get to know $\frac{n}{2}$ matrix evements from each row – those where the input is different from the output must be 0. So you get about half the matrix elements.

After two random pairs of plaintext and ciphertext you know on average about $\frac{3}{4}$ of the matrix. Then $\frac{7}{8}$, etc. You need on the order of $log_2(n)$ pairs to find the whole matrix. (With non-random plaintext it may take slightly more pairs than with random.)

Even before leaking the whole permutation, you will leak all sorts of information about the plaintext – for example, the number of 1 and 0 bits will be the same in the ciphertext. Two plaintexts that differ in $k$ bits will have ciphertexts differing in $k$ bits, etc.



Old answer based on using a block cipher:


  Is it possible to reveal the used permutation?


Not if the keyspace is large enough. There are $2^n!$ different $n$-bit permutations, but a block cipher typically has only a 128-bit or 256-bit keyspace, so not all permutations are possible. Unless the cipher is broken, the only way to narrow it down is a brute force search of the keyspace, which is intractable for 128+ bits.

As an aside, you would be using the block cipher directly on plaintexts. Unless the plaintexts are random (or known unique) bitstrings of length $\le n$ bits, that is not a secure mode of operation, it is ECB and is not semantically secure.