Is it possible to compress true random permutation using low order polynomial interpolation? If yes, how it can be achieved?
This is just an extended comment, too long for a comment. Firstly, the abstract in your link https://link.springer.com/article/10.1007%2FBF02215679 discusses "data compression", but not "random", per se. And as @CandiedOrange first mentioned, random data isn't compressible. And that's simply by definition, e.g., google "Kolmogorov complexity". If you can compress a string, it's not random -- by definition.
But as my comment mentions, permutations aren't entirely random since they're constrained by the requirement that each integer 1,2,...,N appears exactly once. And that means N! possible permutations, versus N^N>>N! possible random sequences.
So here's one possible permutation compression strategy, though it has absolutely nothing to do with interpolation. Choose an enumeration of the permutations of 1...N, whereby you can reconstruct a permutation by its index 1...N! in the enumeration. And that index requires just log_2(N!) bits. In comparison, an enumeration of all sequences would require log_2(N^N) bits to specify an index, whereby random permutations are compressible compared to random sequences.