The Impossibility of Basing One-Way Permutations on Central Cryptographic Primitives

We know that trapdoor permutations can be used to construct all kinds of basic cryptographic primitives, including trapdoor functions, public-key encryption, private information retrieval, oblivious transfer, key agreement, and those known to be equivalent to one-way functions such as digital signature, private-key encryption, bit commitment, pseudo-random generator and pseudo-random functions. On the other hand, trapdoor functions are not as powerful as trapdoor permutations, so the structural property of permutations seems to be something special that deserves a more careful study. In this paper we investigate the relationships between one-way permutations and all these basic cryptographic primitives. Following previous works, we focus on an important type of reductions called black-box reductions. We prove that no such reductions exist from one-way permutations to either trapdoor functions or private information retrieval. Together with previous results, all the relationships with one-way permutations have now been established, and we know that no such reductions exist from one-way permutations to any of these primitives except trapdoor permutations. This may have the following meaning, with respect to black-box reductions. We know that one-way permutations imply none of the primitives in "public cryptography," where additional properties are required on top of "one-wayness" \cite{IR89}, so permutations cannot be traded for any of these additional properties. On the other hand, we now know that none of these additional properties can be traded for permutations either. Thus, being a permutation seems to be something orthogonal to those additional properties on top of one-wayness. Like previous non-reducibility results, our proofs follow the oracle separation paradigm of Impagliazzo and Rudich.     

基于循环移位置换的超伪随机置换的构造

为了优化Luby和Rackoff给出的DES型置换的构造,我们给出了一种基于循环移位置换的超伪随机置换的构造方法。新构造简化了构造的复杂性和基于随机预言模型的安全性证明,并指出:首末两轮循环移位置换和中间两轮DES-型的随机置换的组合构造是超伪随机置换。新构造降低了区分优势的上界和敌手攻击成功的概率并降低了对首末轮函数的要求。     

Certifying Permutations: Noninteractive zero-knowledge based on any trapdoor permutation

In cryptographic protocols it is often necessary to verify/certify the tools in use. This work demonstrates certain subtleties in treating a family of trapdoor permutations in this context, noting the necessity to check certain properties of these functions. The particular case we illustrate is that of noninteractive zero-knowledge. We point out that the elegant recent protocol of Feige, Lapidot, and Shamir for proving NP statements in noninteractive zero-knowledge requires an additional certification of the underlying trapdoor permutation, and suggest a method for certifying permutations which fills this gap.A preliminary version of this paper appeared in Advances in Cryptology—Crypto 92 Proceedings, Lecture Notes in Computer Science, Vol. 740, E. Brickell, ed., Springer-Verlag, Berlin, 1992. This work was done while Mihir Bellare was at the IBM T.J. Watson Research Center, Yorktown Heights, NY.     

On the Construction of Pseudorandom Permutations: Luby—Rackoff Revisited

Luby and Rackoff [26] showed a method for constructing a pseudorandom permutation from a pseudorandom function. The method is based on composing four (or three for weakened security) so-called Feistel permutations, each of which requires the evaluation of a pseudorandom function. We reduce somewhat the complexity of the construction and simplify its proof of security by showing that two Feistel permutations are sufficient together with initial and final pairwise independent permutations. The revised construction and proof provide a framework in which similar constructions may be brought up and their security can be easily proved. We demonstrate this by presenting some additional adjustments of the construction that achieve the following: • Reduce the success probability of the adversary. • Provide a construction of pseudorandom permutations with large input-length using pseudorandom functions with small input-length. Received 2 August 1996 and revised 26 July 1997     

A cipher based on data-dependent permutations

Data-dependent permutations (DDP) are introduced as basic cryptographic primitives to construct fast hardware-oriented ciphers. Some variants of the DDP operations and their application in the cipher CIKS-1 are considered. A feature of CIKS-1 is the use of both the data-dependent transformation of round subkeys and the key-dependent DDP operations. Received March 2000 and revised May 2001 Online publication 29 August 2001     

A New Scheme to Realize Crosstalk-Free Permutation in Vertically Stacked Optical MINs*

Vertical stacking is a novel alternative for constructing nonblocking multistage interconnection networks (MINs). Rearrangeably nonblocking optical MINs are attractive since they have lower complexity than their strictly nonblocking counterparts. In this paper, we study the realization of crosstalk-free permutations in rearrangeably nonblocking, self-routing banyan-type optical MINs built on vertical stacking. An available scheme for realizing crosstalk-free permutation in this type of optical MINs requires to first decompose a permutation into multiple crosstalk-free partial permutations based on the Euler-Split technique, and then to realize them crosstalk-free in different planes (stacked copies) of the MIN simultaneously. The overall time complexity of this scheme to realize a crosstalk-free permutation in an N × N optical MIN is O(N log N) which is dominated by the complexity of crosstalk-free decomposition. In this paper, we propose a new scheme for realizing permutations in this class of vertically stacked optical MINs crosstalk-free. The basic idea of the new scheme is to classify permutations into permutation classes such that all permutations in one class share the same crosstalk-free decomposition pattern. By running the Euler-Split based crosstalk-free decomposition only once for a permutation class and applying the obtained crosstalk-free decomposition pattern to all permutations in the class, crosstalk-free decomposition of permutations can be realized in a more efficient way. We show that the number of permutations in a permutation class is huge (N!)^N when log₂N is even and (2N!)^N/2 when log₂N is odd), and thus the average time complexity of crosstalk-free decomposition of a permutation becomes O(N).     

An Efficient Noninteractive Zero-Knowledge Proof System for NP with General Assumptions

We consider noninteractive zero-knowledge proofs in the shared random string model proposed by Blum et al. [5]. Until recently there was a sizable polynomial gap between the most efficient noninteractive proofs for NP based on general complexity assumptions [11] versus those based on specific algebraic assumptions [7]. Recently, this gap was reduced to a polylogarithmic factor [17]; we further reduce the gap to a constant factor. Our proof system relies on the existence of one-way permutations (or trapdoor permutations for bounded provers). Our protocol is stated in the hidden bit model introduced by Feige et al. [11]. We show how to prove that an n -gate circuit is satisfiable, with error probability 1/n ^O(1) , using only O(n lg n) random committed bits. For this error probability, this result matches to within a constant factor the number of committed bits required by the most efficient known interactive proof systems. Received 20 November 1995 and revised 7 October 1996     

The Security of Feistel Ciphers with Six Rounds or Less

This paper considers the security of Feistel networks where the round functions are chosen at random from a family of 2 ^k randomly chosen functions for any k . Also considered are the networks where the round functions are themselves permutations, since these have applications in practice. The constructions are attacked under the assumption that a key-recovery attack on one round function itself requires an exhaustive search over all 2 ^k possible functions. Attacks are given on all three-, four-, five-, and six-round Feistel constructions and interesting bounds on their security level are obtained. In a chosen text scenario the key recovery attacks on the four-round constructions, the analogue to the super pseudorandom permutations in the Luby and Rackoff model, take roughly only the time of an exhaustive search for the key of one round. A side result of the presented attacks is that some constructions, which have been proved super pseudorandom in the model of Luby and Rackoff, do not seem to offer more security in our model than constructions which are not super pseudorandom.     

A virtually nonblocking self-routing permutation network which routes packets in O(log2 N) time

Asymptotically nonblocking networks are O(log₂ N) depth self-routing permutation devices in which blocking probability vanishes when N (the number of network inputs) increases. This behavior does not guarantee, also for very large N, that all information always and simultaneously reaches its destination (and consequently that a whole permutation passes through the device) which is a requirement of the PRAM machine. In this work the conditions for which an asymptotically nonblocking network becomes asymptotically permutation nonblocking are studied, finally a virtually nonblocking device is obtained by a retransmission procedure which guarantees that all permutations always pass through this permutation device. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于余数系统与置换多项式的高速长周期伪随机序列生成方法

低复杂度长周期数字伪随机序列在现代加密、通信等系统中具有广泛的应用。该文提出一种基于余数系统和有限域置换多项式的伪随机序列生成方法。该方法基于中国剩余定理将多个互质的小周期有限域随机序列进行单射扩展生成长周期数字伪随机序列,置换多项式的迭代计算在多个并行的小动态范围有限域上进行,从而降低了硬件实现中迭代环路的计算位宽,提高了生成速率。该文还给出构建长周期伪随机序列的置换多项式参数选择方法和中国剩余定理优化方法,在现有技术平台下可轻易实现2100以上的序列周期。同时,该方法具有极大的迭代多项式选择自由度,例如仅在q2(mod)3且q503的有限域上满足要求的置换多项式就有10905种。硬件实现结构简单,基于Xilinx XC7Z020芯片实现290的随机序列仅需20个18 kbit的BRAM和少量逻辑资源,无需乘法器,生成速率可达449.236 Mbps。基于NIST的测试表明序列具有良好的随机特性。     

A Parallel Hill Climbing Algorithm for Pushing Dependent Data in Clients–Providers–Servers Systems

The up-link bandwidth in satellite networks and in advanced traffic wireless information system is very limited. A server broadcasts data files provided by different independent providers and accessed by many clients in a round-robin manner. The clients who access these files may have different patterns of access. Some clients may wish to access several files in any order (AND), some wish to access one out of several files (OR), and some clients may access a second file only after accessing another file (IMPLY). The goal of the server is to order the files in a way that minimizes the access time of the clients given some a priori knowledge of their access patterns. An appropriate clients–servers model was recently proposed by Bay-Noy, Naor and Schieber. They formulated three separate problems and proposed an algorithm that evaluates certain number of random permutations and chooses the one whose access time is minimized. In this paper, we formulate a combined AOI (AND-OR-IMPLY) problem, and propose to apply a parallel hill climbing algorithm (to each of the four problems), which begins from certain number of random permutations, and then applies hill climbing technique on each of them until there is no more improvement. The evaluation time of neighboring permutations generated in hill climbing process is optimized, so that it requires O(n) time per permutation instead of O(n ²) time required for evaluating access time of a random permutation, where n is the number of files the server broadcasts. Experiments indicate that the parallel hill climbing algorithm is O(n) times faster that random permutations method, both in terms of time needed to evaluate the same number of permutations, and time needed to provide a high quality solution. Thus the improvement is significant for broadcasting large number of files.     

Constructions of permutation arrays

A permutation array (PA) of length n and minimum distance d is a set of permutations of n elements such that any two permutations coincide in at most n - d positions. Some constructions of PAs are given     

A Reconfigurable TDMP Decoder for Raptor Codes

A Raptor code is a concatenation of a fixed rate precode and a Luby-Transform (LT) code that can be used as a rateless error-correcting code over communication channels. By definition, Raptor codes are characterized by irregularity features such as dynamic rate, check-degree variability, and joint coding, which make the design of hardware-efficient decoders a challenging task. In this paper, serial turbo decoding of architecture-aware Raptor codes is mapped into sequential row processing of a regular matrix by using a combination of code enhancements and architectural optimizations. The proposed mapping approach is based on three basic steps: (1) applying systematic permutations on the source matrix of the Raptor code, (2) confining LT random encoding to pseudo-random permutation of messages and periodic selection of row-splitting scenarios, and (3) developing a reconfigurable parallel check-node processor that attains a constant throughput while processing LT- and LDPC-nodes of varying degrees and count. The decoder scheduling is, thus, made simple and uniform across both LDPC and LT decoding. A serial decoder implementing the proposed approach was synthesized in 65 nm, 1.2 V CMOS technology. Hardware simulations show that the decoder, decoding a rate-0.4 code instance, achieves a throughput of 36 Mb/s at SNR of 1.5 dB, dissipates an average power of 27 mW and occupies an area of 0.55 mm².     

A Fast Recursive Algorithm and Architecture for Pruned Bit-reversal Interleavers

In this paper, pruned bit-reversal permutations employed in variable-length interleavers and their associated fast pruning algorithms and architectures are considered. Pruning permutations is mathematically formulated as a counting problem in a set of k integers and any subset of $\alpha $ consecutive integers under some permutation, where integers from this subset that map into indices less than some $\beta <k$ are to be counted. A solution to this problem using sums involving integer floors and related functions is proposed. It is shown that these sums can be evaluated recursively using integer operations. Specifically, a mathematical treatment for bit-reversal permutations (BRPs) and their permutation statistics are presented. These permutations have been mainly addressed using numerical techniques in the literature to speed up in-place computations of fast Fourier and related transforms. Closed-form expressions for BRP statistics including inversions, serial correlations, and a new statistic called permutation inliers that characterizes the pruning gap of pruned interleavers, are derived. Using the inliers statistic, a recursive algorithm that computes the minimum number of inliers in a pruned BR interleaver (PBRI) in logarithmic time complexity is presented. This algorithm enables parallelizing a serial PBRI algorithm by any desired parallelism factor by computing the pruning gap in lookahead rather than a serial fashion, resulting in significant reduction in interleaving latency and memory overhead. Extensions to 2-D block and stream interleavers are also presented. Moreover, efficient hardware architectures for the proposed algorithms employing simple logic gates are presented. Simulation results of interleavers employed in modern communication standards demonstrate 3 to 4 orders of magnitude improvement in interleaving time compared to existing approaches.     

A construction of a cipher from a single pseudorandom permutation

We suggest a scheme for a block cipher which uses only one randomly chosen permutation,F. The key, consisting of two blocks,K ₁ andK ₂, is used in the following way. The message block is XORed withK ₁ before applyingF, and the outcome is XORed withK ₂, to produce the cryptogram block. We show that the resulting cipher is secure (when the permutation is random or pseudorandom). This removes the need to store, or generate a multitude of permutations. Shimon Even was supported by the Fund for the Promotion of Research at the Technion, and by Bellcore, Morristown, NJ 07940, U.S.A. Part of the work was done while Yishay Mansour was in the IBM T.J. Watson Research Center.     

New Approaches to Designing Public Key Cryptosystems Using One-Way Functions and Trapdoors in Finite Groups

A symmetric key cryptosystem based on logarithmic signature s for finite permutation groups was described by the first author in [6], and its algebraic properties were studied in [7]. In this paper we describe two possible approaches to the construction of new public key cryptosystems with message space a large finite group G , using logarithmic signature s and their generalizations. The first approach relies on the fact that permutations of the message space G induced by transversal logarithmic signature s almost always generate the full symmetric group S _G on the message space. The second approach could potentially lead to new ElGamal-like systems based on trapdoor, one-way functions induced by logarithmic signature -like objects we call meshes , which are uniform covers for G .     

On optimal permutation codes

Permutation codes are vector quantizers whose codewords are related by permutations and, in one variant, sign changes. Asymptotically, as the vector dimension grows, optimal Variant I permutation code design is identical to optimal entropy-constrained scalar quantizer (ECSQ) design. However, contradicting intuition and previously published assertions, there are finite block length permutation codes that perform better than the best ones with asymptotically large length; thus, there are Variant I permutation codes whose performances cannot be matched by any ECSQ. Along similar lines, a new asymptotic relation between Variant I and Variant II permutation codes is established but again demonstrated to not necessarily predict the performances of short codes. Simple expressions for permutation code performance are found for memoryless uniform and Laplacian sources. The uniform source yields the aforementioned counterexamples     

一种新的正形置换构造方法

正形置换在密码体制设计中应用广泛。该文基于正形置换和正形拉丁方截集的一一对应关系,研究了正形置换的构造问题,给出了由n元正形置换构造n+1元正形置换的新方法,该方法利用正形拉丁方An的一个截集及其补序截集,扩展得到正形拉丁方An+1的一个复合截集,并由此构造出正形拉丁方An+1的截集。证明了按这种方法由任一n元正形置换可以构造出22n个n+1元正形置换。     

Permutation fixed points with application to estimation of minimumdistance of turbo codes

We present a systematic technique for obtaining all the input sequences that are mapped by a given permutation either to themselves or to shifted versions of themselves (generically called permutation fixed points). Such sequences or their subsets, represent the primary candidates for examination in connection with obtaining estimates of the minimum distance of parallel concatenated codes, specially for interleaver lengths for which the determination of the actual minimum distance may be very difficult. Subsequently, we present a new class of permutations that nearly achieve the lower bound on the number of possible fixed points associated with a given permutation of prime length p. Preliminary experimental evidence suggests that certain permutations of this class lead to turbo codes with large minimum distances fur short interleaver lengths     

基于奇异值分解的半易损水印算法

随着数字图像在报刊杂志、医院、法庭中的广泛应用，越来越需要一种有效的图像认证方法，数字水印技术为上述问题提供了一个潜在的解决方案。本文提出了一种基于分组奇异值分解（SVD）的半易损水印技术，算法将经过伪随机排序的二值图像通过量化策略嵌入到分组SVD分解中最大的奇异值点，提取水印信号无需使用原始图像。仿真实验表明水印是不可察觉的，可将JPEG有损压缩同恶意攻击区分开来，能够准确地定位被篡改的图像内容。