Keccak Optimization

Padding and sponge optimization

Can use RLC for array operations.

Xor optimization

Since a core primitive of keccak is xor, one class of approaches focuses on optimizing (batch) xor.

Bit-packing approach

For bit strings a_i, b_i \in {0, 1}, we can construct for some N > 0 the encoding

A = \sum_i a_i 2^{iN}
B = \sum_i b_i 2^{iN}

so that

A + B = \sum_i (a_i + b_i) 2^{iN}.

Thus the iN-bits of A + B are the bits of xor(A, B).

We can generalize this –- if we have k bitstrings with corresponding encodings A_1, ..., A_k, then the iN bits of A_1 + ... + A_k are the bits of xor(A_1, ..., A_k) so long as k < 2^N. We can thus do k joint xors using a single range check.

The general technique here is to encode a bit string a_i \in {0, 1} by the sparse encoding

A = \sum_i a_i B^i

for some special base vector. Next, if we want to compute some coordinate function f(\{a_i^1\}, \{a_i^2\}, ...) of bit-strings, we can compute some linear function

X = \sum_j c_j * A_j = \sum_i (\sum_j c_j * a_i^j) * B^i

so that the mapping from f(a_i^1, ..., a_i^k) to (\sum_j c_j * a_i^j) is injective on bitstring inputs.

Mixing gate

References

Select a repo