伪随机排列PRP和伪随机函数PRF

伪随机排列PRP一定是伪随机函数PRF吗？

以前遇到这个问题，在网上没有得到满意令人信服的解释

今天密码学老师带着期末复习，谈到了这个问题

老师的回答是：伪随机排列“不一定”是伪随机函数

首先，PRP是伪随机的，只是在排列之中看，它不能与真随机排列相区分

但是放在函数之中去，它就比较好分辨出来了：PRP是排列，是双射，一一对应；而PRF是函数，并不要求是双射。用“连线”去看，PRP是一一连线，PRF则可能比较杂乱，甚至有些没有连线，这就很好区分了。

因此，只要我们观察整个连接情况，就能区分PRP和真随机函数，也就是说PRP不是伪随机函数了

不过，从计算能力上看，我们只能进行多项式时间的查询，因此只要PRP的空间足够大，以致于我们不能探清它的拓扑结构，我们就区分不了了。此时，PRP是PRF

上面lin(n)是PRP输入，n是安全参数，lin(n)表示PRP输入长度是n的多项式

可能讲得不是很清楚，不过先就这样吧