Overview of the Poseidon Permutation
This section describes the Poseidon permutation. It consists of rounds, where each round has the following steps:
AddRoundConstants
: where constants (denoted byarc
in the code) are added to the internal state,SubWords
: where the S-box is applied to the internal state,MixLayer
: where a matrix is multiplied with the internal state.
The total number of rounds we denote by . There are two types of round in the Poseidon construction, partial and full. We denote the number of partial and full rounds by and respectively.
In a full round in the SubWords
layer the S-box is applied to each element of the
internal state, as shown in the diagram below:
┌───────────────────────────────────────────────────────────┐
│ │
│ AddRoundConstants │
│ │
└────────────┬──────────┬──────────┬──────────┬─────────────┘
│ │ │ │
┌─▼─┐ ┌─▼─┐ ┌─▼─┐ ┌─▼─┐
│ S │ │ S │ │ S │ │ S │
└─┬─┘ └─┬─┘ └─┬─┘ └─┬─┘
│ │ │ │
┌────────────▼──────────▼──────────▼──────────▼─────────────┐
│ │
│ MixLayer │
│ │
└────────────┬──────────┬──────────┬──────────┬─────────────┘
│ │ │ │
▼ ▼ ▼ ▼
In a partial round, in the SubWords
layer we apply the S-box only to one element
of the internal state, as shown in the diagram below:
│ │ │ │
│ │ │ │
┌────────────▼──────────▼──────────▼──────────▼─────────────┐
│ │
│ AddRoundConstants │
│ │
└────────────┬──────────────────────────────────────────────┘
│
┌─▼─┐
│ S │
└─┬─┘
│
┌────────────▼──────────────────────────────────────────────┐
│ │
│ MixLayer │
│ │
└────────────┬──────────┬──────────┬──────────┬─────────────┘
│ │ │ │
▼ ▼ ▼ ▼
We apply half the full rounds () first, then we apply the partial rounds, then the rest of the full rounds. This is called the HADES design strategy in the literature.