5 ms·

Could someone with more knowledge than myself help explain what the practical applications of this are?

by NickM 4y ago

greesil 4y ago
I guess cryptography, but they're also used in GPS, and CDMA.
karma_fountain 4y ago
Error correcting codes, specifically https://en.wikipedia.org/wiki/BCH_code https://en.wikipedia.org/wiki/BCH_code
corsix 4y ago
The next article in blog order is one application: https://www.corsix.org/content/reed-solomon-for-software-raid https://www.corsix.org/content/reed-solomon-for-software-rai... Another application is crypto: the SubBytes step of AES maps very neatly onto gf2p8affineinvqb, so algorithms that are similar to AES but not exactly AES could make use of gf2p8affineinvqb
- salicideblock 4y ago
  Expanding on this,a very nice property of Galois Counter Mode (GCM) for AES is that encrypting one block does not require the previous block to be encrypted, like in AES-CBC. This means that AES-GCM can take advantage of data parallelism and there are big speedups in threaded and pipelined CPUs. In short, you can get big latency and throughout gains by using AES-GCM over AES-CBC.
- nwellnhof 4y ago
  > algorithms that are similar to AES but not exactly AES The SM4 cipher, for example: https://en.wikipedia.org/wiki/SM4_%28cipher%29 https://en.wikipedia.org/wiki/SM4_%28cipher%29
Rebelgecko 4y ago
I think these instructions can drastically speed up the GCM part of AES-GCM, which is used by a lot of https websites (not sure if it's the most popular TLS cipher, but it's almost definitely top 3). Part of why Salsa/Chaha become popular on phones and embedded devices is because for a while only x86 had specialized instructions for GCM
adonovan 4y ago
You can think of a Galois field as a specially chosen permutation of a set of numbers such as 0-255 and a redefinition or remapping of the arithmetic operators + - * / such that each one is reversible: if a op b = c, then given c and b you can find a by applying the inverse of op. (In normal arithmetic of course, multiplication and division aren't reversible because of zero.) The actual operators aren't ADD SUB MUL DIV, but they are like them in the sense that they are easy to implement in a hardware ALU as functions over bit patterns. This unlocks all kinds of clever techniques. For example, it lets you efficiently compute a "rolling" hash of every n-byte substring of a document, by simply sliding an n-byte window across the document one byte at a time, multiplying the previous hash by the incoming byte and dividing by the outgoing byte. This has lots of applications in cryptography, compression, searching, and so on.
- superjan 4y ago
  Thanks for the explanation. Are addition/ multiplication still linked the same was as for normal integers? Like 2*a == a + a? Edit: I do get that ‘2’ in GF might not be the same as integer 2.
  - gizmo686 4y ago
    Pretty much. Fields are generally considered to be the structure that links the common notion addition and multiplication. In particular, you need 3 things to qualify as a field: 1) Multiplication behaves as expected (without reference to addition) 2) Addition behaves as expected (without reference to multiplication) 3) a(b+c) = ab + bc The third requirement is the only part of fields that links multiplication to addition. In particular, if we assume that 2=1+1, then we have: 2a = (1+1)a = a(1+1) = a+a
    - ngcc_hk 4y ago
      What is meant by “without reference to”. How about - Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. Is that count?
hughw 4y ago
You can do discrete Fourier transforms in Galois fields. That used to be more important when floating point was less ubiquitous. And if you’re designing custom hardware to do FFTs you can save a lot transistors if you’re willing to discretize. A fantastic reference is [1] [1] Fast Algorithms for Digital Signal Processing. https://www.google.com/books/edition/Fast_Algorithms_for_Digital_Signal_Proce/1O5SAAAAMAAJ?hl=en https://www.google.com/books/edition/Fast_Algorithms_for_Dig...

Could someone with more knowledge than myself help explain what the practical applications of this are?

by NickM 4y ago

Could someone with more knowledge than myself help explain what the practical applications of this are?

greesil 4y ago

I guess cryptography, but they're also used in GPS, and CDMA.

karma_fountain 4y ago

Error correcting codes, specifically https://en.wikipedia.org/wiki/BCH_code https://en.wikipedia.org/wiki/BCH_code

corsix 4y ago

The next article in blog order is one application: https://www.corsix.org/content/reed-solomon-for-software-raid https://www.corsix.org/content/reed-solomon-for-software-rai... Another application is crypto: the SubBytes step of AES maps very neatly onto gf2p8affineinvqb, so algorithms that are similar to AES but not exactly AES could make use of gf2p8affineinvqb

salicideblock 4y ago
Expanding on this,a very nice property of Galois Counter Mode (GCM) for AES is that encrypting one block does not require the previous block to be encrypted, like in AES-CBC. This means that AES-GCM can take advantage of data parallelism and there are big speedups in threaded and pipelined CPUs. In short, you can get big latency and throughout gains by using AES-GCM over AES-CBC.
nwellnhof 4y ago
> algorithms that are similar to AES but not exactly AES The SM4 cipher, for example: https://en.wikipedia.org/wiki/SM4_%28cipher%29 https://en.wikipedia.org/wiki/SM4_%28cipher%29

Rebelgecko 4y ago

I think these instructions can drastically speed up the GCM part of AES-GCM, which is used by a lot of https websites (not sure if it's the most popular TLS cipher, but it's almost definitely top 3). Part of why Salsa/Chaha become popular on phones and embedded devices is because for a while only x86 had specialized instructions for GCM

adonovan 4y ago

You can think of a Galois field as a specially chosen permutation of a set of numbers such as 0-255 and a redefinition or remapping of the arithmetic operators + - * / such that each one is reversible: if a op b = c, then given c and b you can find a by applying the inverse of op. (In normal arithmetic of course, multiplication and division aren't reversible because of zero.) The actual operators aren't ADD SUB MUL DIV, but they are like them in the sense that they are easy to implement in a hardware ALU as functions over bit patterns. This unlocks all kinds of clever techniques. For example, it lets you efficiently compute a "rolling" hash of every n-byte substring of a document, by simply sliding an n-byte window across the document one byte at a time, multiplying the previous hash by the incoming byte and dividing by the outgoing byte. This has lots of applications in cryptography, compression, searching, and so on.

superjan 4y ago
Thanks for the explanation. Are addition/ multiplication still linked the same was as for normal integers? Like 2*a == a + a? Edit: I do get that ‘2’ in GF might not be the same as integer 2.
- gizmo686 4y ago
  Pretty much. Fields are generally considered to be the structure that links the common notion addition and multiplication. In particular, you need 3 things to qualify as a field: 1) Multiplication behaves as expected (without reference to addition) 2) Addition behaves as expected (without reference to multiplication) 3) a(b+c) = ab + bc The third requirement is the only part of fields that links multiplication to addition. In particular, if we assume that 2=1+1, then we have: 2a = (1+1)a = a(1+1) = a+a
  - ngcc_hk 4y ago
    What is meant by “without reference to”. How about - Addition is move and multiplication is also a move. a + b move from 0 a step then b steps. a * b is move a step b times. Is that count?

hughw 4y ago

You can do discrete Fourier transforms in Galois fields. That used to be more important when floating point was less ubiquitous. And if you’re designing custom hardware to do FFTs you can save a lot transistors if you’re willing to discretize. A fantastic reference is [1] [1] Fast Algorithms for Digital Signal Processing. https://www.google.com/books/edition/Fast_Algorithms_for_Digital_Signal_Proce/1O5SAAAAMAAJ?hl=en https://www.google.com/books/edition/Fast_Algorithms_for_Dig...