The $\mathsf {Rasta}$ cipher, proposed by Dobraunig et al. (CRYPTO 2018), is an HE-friendly cipher enjoying the fewest ANDs per bit and the lowest ANDdepth among the existing ciphers. A novel feature of $\mathsf {Rasta}$ is that its affine layers are freshly and randomly generated for every encryption. In this paper, we propose a new variant of $\mathsf {Rasta}$ , dubbed $\mathsf {Masta}$ . Similarly to $\mathsf {Rasta}$ , $\mathsf {Masta}$ takes as input a (master) secret key and a nonce, and generates a keystream block for each counter. On the other hand, $\mathsf {Masta}$ has two main differences from $\mathsf {Rasta}$ : $\mathsf {Masta}$ uses modular arithmetic to support HE schemes over a non-binary plaintext space, and it uses a smaller number of random bits in the affine layers by defining them with finite field multiplication. In this way, $\mathsf {Masta}$ outperforms $\mathsf {Rasta}$ in a transciphering framework with $\mathsf {BGV}/ \mathsf {FV}$ -style HE schemes. Our implementation shows that $\mathsf {Masta}$ is 505 to 592 times faster in terms of the throughput on the client-side, while 4792 to 6986 times faster on the server-side.
Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a wn-bit block cipher from n-bit public permutations (often called S-boxes), which alternate keyless and “local” substitution steps utilizing such S-boxes, with keyed and “global” permutation steps which are non-cryptographic. Many widely deployed block ciphers are constructed based on the SPNs, but there are essentially no provable-security results about SPNs. In this work, we initiate a comprehensive study of the provable security of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying n-bit permutation is modeled as a public random permutation. When the permutation step is linear (which is the case for most existing designs), we show that 3 SPN rounds are necessary and sufficient for security. On the other hand, even 1-round SPNs can be secure when non-linearity is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-birthday” (up to \(2^{2n/3}\) adversarial queries) security, and, as the number of non-linear rounds increases, our bounds are meaningful for the number of queries approaching \(2^n\). Finally, our non-linear SPNs can be made tweakable by incorporating the tweak into the permutation layer, and provide good multi-user security. As an application, our construction can turn two public n-bit permutations (or fixed-key block ciphers) into a tweakable block cipher working on wn-bit inputs, 6n-bit key and an n-bit tweak (for any \(w\ge 2\)); the tweakable block cipher provides security up to \(2^{2n/3}\) adversarial queries in the random permutation model, while only requiring w calls to each permutation, and 3w field multiplications for each wn-bit input.
19 June 2017 in IACR Transactions on Symmetric Cryptology
We propose new constructions of Message Authentication Codes (MACs) from tweakable or conventional block ciphers. Our new schemes are either stateless and deterministic, nonce-based, or randomized, and provably secure either in the standard model for tweakable block cipher-based ones, or in the ideal cipher model for block cipher-based ones. All our constructions are very efficient, requiring only one call to the underlying (tweakable) block cipher in addition to universally hashing the message. Moreover, the security bounds we obtain are quite strong: they are beyond the birthday bound, and nonce-based/randomized variants provide graceful security degradation in case of misuse, i.e., the security bound degrades linearly with the maximal number of repetitions of nonces/random values.
15 December 2021 in IEEE Transactions on Computers
Grover’s search algorithm allows a quantum adversary to find a $k$ -bit secret key of a block cipher by making O( $2^{k/2}$ ) block cipher queries. Resistance of a block cipher to such an attack is evaluated by quantum resources required to implement Grover’s oracle for the target cipher. The quantum resources are typically estimated by the $\textit {T}$ -depth of its circuit implementation and the number of qubits used by the circuit (width). Since the AES S-box is the only component which requires $\textit {T}$ -gates in a quantum implementation of AES, recent research has put its focus on efficient implementation of the AES S-box. However, any efficient implementation with low $\textit {T}$ -depth will not be practical in the real world without considering qubit consumption of the implementation. In this work, we propose three methods of trade-off between time and space for the quantum implementation of the AES S-box. In particular, one of our methods turns out to use the smallest number of qubits among the existing methods, significantly reducing its $\textit {T}$ -depth.