求解一类单向函数的 TMP 权衡方法

An Approach to Resolve a Kind of One Way Functions with TMP Trade Offs

针对求解一类具有良好伪随机性的单向函数，利用ＴＭＰ权衡技术，提出了一种新型的迭代算法．经过分析，此算法在计算上是可行的：其时间复杂度Ｔ～ｌｔ，空间复杂度Ｍ～ｍ，（其中ｍｌｔ≥Ｎ，Ｎ是所求问题定义域中元素的个数），且此算法将以极大概率（在随机性假设下，以１概率）在上述时空复杂度内得出所求结果；同时，对特殊问题ＤＥＳ进行复杂度分析，证明了此算法的优越性．

The paper seeks to efficiently work out a kind of one way functions with good pseudorandom property. Based on TMP trade offs technique, a new iterative approach is proposed. It is found out that the method is practical: time complexity T～lt , memory complexity M～m , where mlt≥N, N is the possible numbers of solutions in the problem, and the algorithm gives the answer within the above time memory complexity with considerably high probability (if random property is satisfied, the probability will be 1). After analyzing complexity of special problem (DES), the algorithm shows more advantages over that of the paper.