Paper 2018/1114

Lightweight Circuits with Shift and Swap

Subhadeep Banik, Francesco Regazzoni, and Serge Vaudenay

Abstract

In CHES 2017, Moradi et al. presented a paper on ``Bit-Sliding'' in which the authors proposed lightweight constructions for SPN based block ciphers like AES, Present and SKINNY. The main idea behind these constructions was to reduce the length of the datapath to 1 bit and to reformulate the linear layer for these ciphers so that they require fewer scan flip-flops (which have built-in multiplexer functionality and so larger in area as compared to a simple flip-flop). In this paper we take the idea forward: is it possible to construct the linear layer using only 2 scan flip-flops? Take the case of Present: in the language of mathematics, the above question translates to: can the Present permutation be generated by some ordered composition only two types of permutations? The question can be answered in the affirmative by drawing upon the theory of permutation groups. However straightforward constructions would require that the ``ordered composition'' consist of a large number of simpler permutations. This would naturally take a large number of clock cycles to execute in a flip-flop array having only two scan flip-flops and thus incur heavy loss of throughput. In this paper we try to analyze SPN ciphers like Present and Gift that have a bit permutation as their linear layer. We tried to construct the linear layer of the cipher using as little clock cycles as possible. As an outcome we propose smallest known constructions for Present and Gift block ciphers for both encryption and combined encryption+decryption functionalities. We extend the above ideas to propose the first known construction of the Flip stream cipher.