# LOCUS Mode of Authenticated Encryption

**L**ightweight

**OC**b with r

**U**p

**S**ecurity, or LOCUS in abbreviation, is a

*tweakable block cipher based*authenticated encryption scheme that employs

**OCB**style of construction. LOCUS is a --- lightweight, ---online, --- parallel, --- beyond the birthday bound secure secure construction that achieves INT-RUP security. The design is motivated from OCB

^{[1]}. To instantiate LOCUS, we propose a small-tweak tweakable block cipher

**TweGIFT**. As the names suggest, TweGIFT is a tweakable variant of the GIFT

^{[2]}block cipher. This tweakable block cipher is explicitly designed for efficient processing of small tweaks of size 4 bits.

## Features

1. ** High Security: ** The use of nonce-based encryption key and masking key ensures that LOCUS-AEAD achieves beyond the birthday bound security. In fact, both of them achieve
the optimal security level, DT = O(2^{n+κ}), where D and T denote the data and time complexity,
respectively. Here D < 2^{n}, and T < 2^{κ} are obvious conditions.

2. ** Light-weight: ** Similar to LOTUS-AEAD, LOCUS-AEAD achieves the NIST lightweight standardization requirements with 64-bit block ciphers. This reduces the overall state size of the AEAD candidates, when instantiated with ultra-lightweight block
ciphers. Our dedicated tweakable block cipher, TweGIFT-64, is a perfectly suitable candidate for this.

3. **High Performance: **LOCUS-AEAD preserves the inherent high performance features of OCB. It is single pass and fully parallelizable.

5. **INT-RUP Secure **: Most of the existing block cipher based modes, notably OCB, OTR, COFB [6],
SUNDAE [2], do not provide any security in RUP model. This might be an issue in memory-constrained
lightweight environments or low-latency real-time streaming protocols. Our proposals solves the prob-
lem partially as they provide integrity security under RUP model.

6. **Versatility** : Probably, the single most important feature of our proposals is their scope of applicability. At one end of the spectrum, the parallelizability of LOCUS-AEAD make them a perfect candidate for applications in high performance infrastructures. On the other end, their overall state size is competitively small with respect to many existing lightweight candidates, which makes them suitable for low-area hardware implementations.

## Mode Specification

LOCUS authenticated encryption mode receives an (1)
128-bit encryption key K, (2) an 128-bit nonce N, (3) an
associated data A of arbitrary length, (4) and a message M
of arbitrary length as inputs, and returns a (5) ciphertext
C of same length as that of the message, and (6) an 128-bit
tag T.

LOCUS is a (short tweak) tweakable block cipher based authenticated encryption mode that employs OCB paradigm, where a nonce based key is derived and updated for the encryption of each block. For the purpose of domain separations, LOCUS uses 4-bit short tweaks.

## Specification of TweGIFT

This is a tweakable variant of GIFT-64-128 block
cipher that accepts short tweaks of length 4. The 4-bit
initial tweak is first expanded to an 32-bit value using a
linear code that generates code words of hamming distance 4.
All the operations of TweAES is identical to GIFT-64-128
except that we inject the 32-bit extended tweak after the
add round key operation at an interval of 5 rounds.

## Rationale

1. ** Choice of the Mode: ** Our primary goal is to design a lightweight AEAD that should be efficient, provides high performance capability and performs reasonably well in low-end devices as well. For efficiency, the AEAD should be one
pass. To obtain high performance capability, we aim for parallelizability. In addition, we demand integrity
in RUP model. This is specially useful for memory-constrained lightweight applications. Here
we start with the popular mode OCB. Similar to OTR, OCB also satisfies the first two
properties. OCB is online, one-pass and parallelizable. However, OCB is insecure
under the RUP model. This motivates us to design an AE mode which is structurally as simple as OCB but achieves RUP security while keeping the primary features, such as efficiency and parallelism, intact. The new proposal LOCUS-AEAD replace one block cipher call by two calls. The
rationale behind this modification is the observation that the intermediate state between the two block
cipher invocations can be used to generate a checksum, which is completely hidden and hence cannot be
controlled by the adversary (even if the adversary is allowed to make RUP queries). This hidden checksum
ensures integrity security in RUP model. The additional block cipher call per message block increases the
number of block cipher calls from to (2m + 1) to process an m-block message. However, this seems optimal as
for any INT-RUP secure parallel AEAD mode, at least (2m + 1) non-linear invocations are necessary to process
an -block message.

The associated data processing phase is based on a simple variant of the hash layer of PMAC, and the computation is completely parallel. The associated data processing can be done in parallel with the plaintext and/or ciphertext processing in order to maximize the performance in parallel computing environments.

OCB generates the tag using the checksum (simple XORs) of all the plain text blocks and the output of the processed associated data. However, two separate states are required to hold the message checksum and the AD checksum. We obtain INT-RUP security, by using an intermediate checksum (hidden to the adversary) instead of the plaintext checksum. Moreover, we do not store the intermediate checksum and AD checksum separately. Rather, we XOR the two checksums, which means that in a sequential im- plementations, the intermediate checksum can be computed on top of the AD checksum. This reduces the overall state size by size of one block.

A notable change in LOCUS-AEAD is the use of nonce and position dependent keys. OCB has only birthday bound security on the block size. This is because the security is generally lost once the input/output of any two distinct block cipher calls matches, as the two calls share the same encryption key. In LOCUS-AEAD, we overcome the birthday bound barrier by changing
the key and tweak pair for each block cipher call. So even if there is a collision among inputs/outputs, the
security remains intact, as the block cipher keys or tweaks are distinct. In fact, our modes are secure up
to data complexity of 2^{n}, and time complexity of 2^{k}, and combined data-time complexity up to 2^{n+κ} (see
section 3 for more details). This, in turn, helps us to construct AEAD algorithms with the desired security
level using an ultra-lightweight block cipher TweGIFT-64.

2. ** Choice of the TBC: ** The main motivation behind TweGIFT-64 is the lack of a good short-tweak tweakable block cipher, which is essential for instantiating LOCUS-AEAD. There are some extremely good tweakable block cipher candidates, most notably SKINNY [4], but they are designed to handle general purpose tweaks, and hence not optimized for very short tweaks of size 4 bits. In contrast, TweGIFT-64 is especially designed on top of the GIFT-64-128 block cipher to handle such small tweak values.

For the tweak expansion, we use a simple linear code that converts a 4-bit tweak value into an 8-bit codeword. The linear code is described below: This linear code has two advantages: (i) it is a distance 4 code, and (ii) it is very simple and requires only 7 XOR operations. We use two copies of the codeword to get a 16-bit codeword, which has distance 8. As we will see in the cryptanalysis, this high distance linear code ensures good differential characteristics for TweGIFT-64.

We choose to inject the expanded tweak into the block cipher state by masking it to the third bit of each nibble. This bit position has been chosen as the other three positions are already masked by the round key and round constant bits. The tweak injection at intervals of 4 rounds ensures very low differential probability for TweGIFT-64.

## Security

The security levels of our recommended instanstiations are presented below in the Table. Of note is the fact that we do not restrict the adversary to be nonce-respecting, and same nonce can be used for all the queries, without any degradation of the security. All these versions are equally secure in nonce-misusing scenario. Further we claim both privacy and integrity security under RUP model, where the decryption algorithm releases unverified plaintext.

Submissions | Privacy | Authenticity | ||
---|---|---|---|---|

Time | Data (in bytes) | Time | Data (in bytes) | |

LOCUS [TweGIFT] | 2^{128} |
2^{64} |
2^{128} |
2^{64} |

## Cryptanalysis

Here we provide the security analysis on TweGIFT-64 in the related-key setting. Without exploiting
the tweak, TweGIFT-64 offers exactly the same security as the original GIFT-64-128. Hence we focus our
attention on the attacks that exploit the tweak injection. The exact security bound, e.g. the lower bound of the number of active S-boxes and the upper bound of differential characteristic probability, can be obtained by using various tools based on MILP and SAT,
however to derive such bounds for the entire construction with 128-bit key difference is often infeasible. Here we focus on the feature that the tweak expansion function ensures a large number of active bits at the expanded tweak. This implies that differential trails with non-zero tweak difference will have a relatively large number of active S-boxes around the tweak injection. This motivates us to evaluate the tight bound of the differential characteristic probability for the 2-round transformation followed by the tweak injection and another 2-round transformation, which we call ``4-round core". Let p core be the maximum differential
characteristic probability of the 4-round core. Then, the probability for the entire construction is upper
bounded by (p core) 6 because 28 rounds of TweGIFT-64 contain six sequence of the 4-round core (see Fig. 3).

^{−16}, hence the maximum differential characteristic probability of 28 rounds can be upper bounded by 2

^{−16×6}= 2

^{−96}. This can also be viewed that the maximum differential characteristic probability reaches 2

^{−16×4}= 2

^{−64}and we have 8 rounds for the margin. One of the best differential trails for the 4-round core with probability 2

^{−16}is fully specified in Table 3.2. The tweak expansion ensures that the number of active bits in the expanded tweak is at least 8 when the tweak difference is non-zero. We note that, in the very middle round, both AddRoundKey and AddTweak are performed. However the key bits and tweak bits are XORed to different bit positions of the state. Thus, they cannot cancel each other to avoid affecting the state.

## NIST Light-weight Competition: Why LOCUS?

Here we provide a comparative study LOCUS-AEAD with other Parallel AE modes and depicts the advantages of our mode over other designs. Typically, the comparison is made with all the other parallel modes that are submitted to NIST which includes Flex-AEAD, LAEM, LILLIPUT-AE, PYJAMASK, QAMELEON, SKINNY AEAD.

Construction | Primitive size |
State size |
Rate | RUP Secure | Ciphertext Expansion |
---|---|---|---|---|---|

LOCUS | 64 (4-bit tweak) | 324 | 1 | YES | 64 |

Flex-AEAD | 128 | 768 | 1/3 | NO | 128 |

LAEM | 128 | 384 | 1/2 | NO | 64 per message block |

LILLIPUT-AE | 128 (192-bit tweak) | 704 | 1 | NO | 128 |

PYJAMASK | 128 (192-bit tweak) | 704 | 1 | NO | 128 |

QAMELEON | 128 (128-bit tweak) | 640 | 1 | NO | 128-255 |

SKINNY-AEAD | 128 (256-bit tweak) | 764 | 1 | NO | 128 |

## References

**^**Subhadeep Banik, Andrey Bogdanov, Atul Luykx, and Elmar Tischhauser. Sundae: Small universal deterministic authenticated encryption for the internet of things. IACR Transactions on Symmetric Cryptology, 2018(3):1–35, Sep. 2018.**^**Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards reaching the limit of lightweight encryption. In Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, pages 321–345, 2017.**^**NIST FIPS 197. Advanced Encryption Standard (AES). Federal Information Processing Standards Publication, 197, 2001.**^**Avik Chakraborti, Nilanjan Datta, and Mridul Nandi. On the optimality of non-linear computations for symmetric key primitives. J. Mathematical Cryptology, 12(4):241–259, 2018.**^**Elena Andreeva, Andrey Bogdanov, Atul Luykx, Bart Mennink, Nicky Mouha, and Kan Yasuda. How to securely release unverified plaintext in authenticated encryption. In Advances in Cryptology - ASIACRYPT 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part I, pages 105–125, 2014.