ONB Type II, why?

Why do we need to use two field elements from two different field to generate a Type II ONB?

First pick an element of order in to find in field .

Why?

More to do, more to do

1. Check polynomial representation for different polynomial with same order, and convert it to normal basis
2. Find out whether ONB Type I is convertible to ONB Type II or vice versa. (Intuitively, this can be done, hmmm…)
3. Think how to choose curve applicable for all those representations. Is it better find the polynomial then convert it to ONB or is it easier to do it the other way around?

Another headache: choosing curves

Still in the middle writing the papers, now got stuck on choosing the curve that works with polynomial, ONB Type I and Type II.

For example, referring to Rosing’s book, the poly_prime 155bits is not really a prime polynomial, while the field size available for both Type I and II is 148bits. 155bits only for Type II.

Then after a curve has been choosed, I still have to make a code to convert that from polynomial basis to ONB I and II.

When will it be finished? Grrrrr 😦

How to compare?

Still trying to finish one paper and got stuck on how to compare the performance of one basis with another.

Space complexity? Time complexity? Execution time?

[Big headache.]

PhD to do

1. Dissertation focus: side channel attack
2. Write two (or maybe three) papers
3. Read Kumar’s book and contact him for further discussions
4. Find international journals

Discussions: help a lot

Have spent a week thinking about this and finally got the answers after had some discussions 🙂

Now move on to plaintext embedding algorithms.

Basis conversion with matrix

Basis conversion can be done easier with matrix 🙂

More answers for #2

Answering #2 from list of questions here:

An ONB of Type I exists a given field if:

• is a prime
• 2 is a primitive in

A Type II optimal normal basis exists in if:

• is prime
• either 2 is a primitive in or and 2 generates the quadratic residues in

Interesting notes:

An ONB exists in for 23% of all possible values of

said this paper. Hmmm, that’s something.

From one basis to another

Apparently converting from one basis to another like from polynomial to normal basis is not as easy as I thought, hmm… have spent days scribbling, thinking, frustated, madly curious, and end up browsing several papers about that and being succesfully diverted from the main target of doing paper on plaintext embedding, oh my!

Let me digest some more papers I have just downloaded 30secs ago, and will post something useful here as soon as possible 😉

[big headache continues…]

Answer for #1

Again, from here:

1. How to convert from polynomial to normal bases?

Answer:
GF element can be represented in Polynomial Basis (PB) or Normal Basis (NB).

For example we have polynomial

The PB representation in is

If be a field with elements and an element of it such that elements are linearly dependent. Then this set forms a normal basis for

The NB representation of elements in will only use 3 elemens , dan .