SBoxes
Poseidon uses Sboxes (Substitution boxes) to apply a nonlinear transformation to the input data. This nonlinearity is crucial for security, as it makes the relationship between the input and output complex and difficult to reverseengineer or predict. In particular, it strengthens the hash against linear and differential cryptanalysis.
Poseidon uses a specific type of Sboxes, which are based on integer powers of the input. This is in contrast to other Sboxes, say used in AES, which may use other types of functions like lookups, multiplicative inverses, or XOR. Poseidon typically uses integer powers of the input, such as $x_{3}$ or $x_{5}$.
Why Nonlinearity Matters
 Resisting Linear Attacks: Cryptographic algorithms need to withstand linear attacks, where an attacker tries to find linear relations (like invariant subspaces which are like generalizations of eigenvectors) in the algorithm to break it. Nonlinear transformations disrupt such linear relationships.
 Diffusion: Nonlinear Sboxes help in spreading the influence of a single input bit over many output bits, a property known as diffusion.
Why choose $x_{3}$ and $x_{5}$?

Nonlinearity:
 Taking integer powers of numbers like $x_{2}$, $x_{3}$, $x_{4}$, and $x_{5}$ are inherently nonlinear.
 However, even powers (like $x_{2}$ or $x_{4}$) do exhibit some linearlike properties that we can see by doing:
$(a+b)_{2}=a_{2}+2ab+b_{2}$ whwere see see that the $2ab$ is itself linear, leading to less nonlinear behavior.  Odd powers ensure a higher degree of nonlinearity, which is more effective in thwarting linear and differential cryptanalysis.

Efficiency in Finite Fields:
 Computations like $x_{3}$ and $x_{5}$ can be very efficiently implemented in finite fields, especially those used in cryptographic applications like ZKPs.
 These operations strike a balance between providing sufficient nonlinearity and being computationally feasible. One could use higher powers like $x_{11}$ or $x_{13}$, but these would be more computationally expensive.
 ZKPs are typically built on top of polynomial schemes, so using monomials like $x_{3}$ and $x_{5}$ is a natural choice as they don't require writing complex circuits.
Invertibility
If we use a function like $x_{3}$ or $x_{5}$ in a cryptographic algorithm, we should be wary of whether it is invertible as this could lead to a vulnerability. In the field of real numbers, both $x_{3}$ and $x_{5}$ are invertible. However, when it comes to finite fields, this isn't always the case. In finite fields, the invertibility of functions like $x_{3}$ or $x_{5}$ depends on the specific properties of the field, especially its size and characteristic.

General Case:
 In general, for a finite field $F_{q}$ (where $q$ is a prime or a power of a prime), a function $f(x)=x_{n}$ is invertible if and only if $n$ is coprime to $q−1$ (see this link). This is because of the properties of the multiplicative group of the finite field.

Specific Cases of $x_{3}$ and $x_{5}$:
 Note that $3$ and $5$ are prime numbers, so they are always coprime to $q−1$.
Other kinds of Sboxes
Substitution boxes (Sboxes) are crucial components in many cryptographic systems, used to perform nonlinear transformations on input data. While Sboxes like those in the Poseidon hash function often use mathematical functions such as exponentiation in finite fields, there are various other designs and types of Sboxes used in different cryptographic algorithms. Some of these include the use of XOR operations, lookup tables, and more complex algebraic constructions.
 AES (Advanced Encryption Standard):
 AES uses a fixed Sbox for its nonlinear transformation step. The Sbox is essentially a predefined 256element lookup table, where each byte of input is replaced by the byte at the corresponding position in the table.
 The construction of the AES Sbox is based on the multiplicative inverse in the finite field $F_{2_{8}}$, followed by an affine transformation (which includes XOR with a constant).