Week 7: Abstract Algebra and ANTT

Writing CUDA kernels for post-quantum protocols like BINIUS requires composing hardware instructions using only math. The basis of mathematics starts from two different types of algebraic structures known as rings and fields, where ring elements support addition, subtraction, and multiplication while their division is well-defined for all non-zero members of the field. One thing that stands out regarding the use of cryptography compared to other branches of computing is the ability to operate with finite fields that have specific sizes and cannot be rounded off and thereby guarantee the required mathematical precision for proving Zero-Knowledge Protocols. As for the cases where a finite field of zeros and ones will not provide sufficient security, its extension is very important. For this purpose, extension fields are required to be constructed from quotient rings by dividing polynomial rings by an irreducible polynomial (i.e., equivalent to a prime number).

More precisely, the above mentioned approach proves to be useful when designing efficient hardware solutions, thus providing significant performance improvements. Namely, the protocol of BINIUS runs in the environment of characteristic-2 binary extension fields, allowing for perfect correspondence between mathematical abstraction and typical GPU architecture. Taking this fact into account, field additions can be replaced with bitwise XOR operations while carrying out optimized carry-less multiplications on the GPU. Furthermore, ANTTs in such fields lead to fast polynomial multiplication whenever vector operations are coalesced into memory space.