Join Log in
Score:0
Robert Singleton avatar Crypto

AES and quantum computing

za flag
Robert Singleton

I am trying to understand the AES-256 encryption algorithm as it would be implemented on a gated quantum computer (actually, a simulator), and I am having some trouble understanding the theory behind it. The papers I read start with the ring of polynomials given by $F_2[x]/(1 + x + x^3 + x^6 + x^8)$. What is the significance of the polynomial $1 + x + x^3 + x^6 + x^8$? And how does this relate to $GF(2^8)$?

105
0 + 0
aes
Robert Singleton avatar
za flag
Robert Singleton
The title of the paper I'm reading is "Reducing the Cost of Implementing the Advanced Encryption Standard as a Quantum Circuit."
0
Reply
poncho avatar
my flag
poncho
You might want to start with https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf - that tries to describe what AES is, including the multiplication operation that's confusing you.
4
Reply
kelalaka avatar
in flag
kelalaka
[AES stick guide](http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html)
1
Reply
kelalaka avatar
in flag
kelalaka
Our canonical answer [Galois fields in cryptography](https://crypto.stackexchange.com/q/2700/18298) and [Need help understanding math behind Rijndael S-Box](https://crypto.stackexchange.com/q/85670/18298) and
1
Reply
Score:1
meshcollider avatar Crypto
gb flag
meshcollider

To answer the specific question, $F_2[x]/(1 + x + x^3 + x^6 + x^8)$ is isomorphic to $GF(2^8)$. See here for more info.

The polynomial $g(x) = 1 + x + x^3 + x^6 + x^8$ is irreducible over $F_2$, so the quotient is a field. The degree of the polynomial is 8, so it is a degree 8 algebraic extension of $F_2$. In other words, it is $F_{2^8}$.

Elements in $F_2[x]/(g(x))$ are equivalence classes of polynomials modulo $g(x)$.

This is a standard way to construct finite-degree algebraic field extensions.

By the way, I think AES actually has $x^4$ instead of $x^6$ in the polynomial. Not sure if that was a typo in your question or if you read it somewhere.

0 + 0
Robert Singleton avatar
za flag
Robert Singleton
This was very helpful. I've been trying to factor the polynomial unsuccessfully over $_2$, so it's good to know that it is irreducible. How does one prove that that a specific polynomial is irreducible in $F_2$? I have very little intuition for $_2$. Also: you are indeed correct, the polynomial has $x^4$ instead of $x^6$. Is there a reason AES chose $1 + x + x^3 + x^4 + x^6$ instead of some other irreducible polynomail?
0
Reply
meshcollider avatar
gb flag
meshcollider
@RobertSingleton you can use [Rabin's test for irreducibility](https://en.m.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Rabin.27s_test_of_irreducibility). The choice of polynomial is just part of the standard.
1
Reply
kelalaka avatar
in flag
kelalaka
You can find how to see that AES polynomial(s) is irreducible [here](https://crypto.stackexchange.com/a/77958/18298). The selection reason of low weight irreducible it this that reduces the calculation costs in the Finite Field.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.