How to generate the APA SBox? I am trying to generate the S-Box provided in the Affine Power Affine paper (PDF) but I'm not sure I understand it fully.

The essence of the paper is this:

AES(i) = Affine(Power(i))

APA(i) = Affine(Power(Affine(i)))


Where Affine is the affine transform and Power is the inverse transform used in generating AES s-box.

Now to calculate the first value of the s-box, we take i = 0

APA(0) = Affine(Power(Affine(0)))

APA(0) = Affine(Power(63))     {Affine(0) = 63}

APA(0) = AES(63)

AES(63) = FB     {You can confirm this from wikipedia's page on Rijndael s-box}

So, APA(0) = FB


But the paper has a table which says that APA(0) is 8C.

There must be a mistake I made because I highly doubt that the paper has an error.
Actually, you are right and the paper is wrong.

They omitted the fact that they used a different generator and/or vector than the AES s-box. This is why you are not getting the same results.

I ran a brute force generation of all APA s-boxes, and none of them starting with $0x8C$ continued with the results of the paper. It is probable they used two different affine transformations, and it would take 65000 times longer to search that space, so I am not going to do it. There are other problems with the s-box; strict avalanche is inferior to the AES s-box, and there are 4 self inverse elements.

Here is the full report:

Iterative Periods: 2 (2)  12 (2)  26 (2)  176 (1)  
Self Inverse error at index 135  0x87
Self Inverse error at index 152  0x98
Self Inverse error at index 171  0xAB
Self Inverse error at index 225  0xE1


SAC Min/Max: -16  +16  12.5%, DSAC: 452, DDSAC: 220, Avg/Dev: 128.2 8.35, Satisfied: 60.9% (39)
GA: 358.6, Dist: 0 62 242 456 544 442 222 68 12
Aval: 0.0312, Dist: 16 0 4 8 20 32 24 20, Totals 124 0.0605

HOSAC Min/Max: -16  +16  12.5%, HODSAC: 1464, HODDSAC: 724, Avg/Dev: 128.1 7.86, Satisfied: 61.2% (137)
HOGA: 1176.8, Dist: 0 242 776 1602 1940 1598 754 234 22

BIC Min/Max: -16  +16, DBIC: 1508, Avg/Dev: 127.9 7.88, Satisfied: 58% (130), BIC: 0.12856 
HOBIC Min/Max: -16  +16, DBIC: 5244, Avg/Dev: 128.5 8.1, Satisfied: 57.4% (450), BIC: 0.13498 

Differential Uniformity: 4 (255)
Non-linearity: 112  Delta: 16 (255)
AutoCorrelation: 32 (255)
SSI: 133120


There is a revised version of that paper from 2010 which uses $0x5B$ for the generator and $0x5D$ for the vector, and generates a different s-box.

The 2nd paper had reproducible results. It also had no self inverse elements and a full iterative period, although it still did not have fully superior statistical properties to the AES s-box.

It should be noted that APA using the Rijndael affine transformation is a complete mess of fixed points and is unsuitable for cryptographic applications. APA s-boxes within a different finite field than $0x11B$ used by Rijndael are more interesting, field reduced using $0x165$ has the best results.