# Implementation of Post-quantum Authenticated Key Exchange from Ideal Lattices

I am implementing the Authenticated Key Exchange from Ideal Lattices on sage maths.

On page number 3 the full key exchange scheme is presented. In this key exchange scheme, they are using the Hash function $c=H_1(i,j,x_i)$ and $d=H_1(j,i,y_j,x_i)$ that will output the elements that are invertible in $R_q$, where $R_q=Z[x]/(x^n+1)$.

On page number 10, there is short note at the bottom of the page, that says to create such hash function one can use SHA-2 algorithm to obtain uniformly random string and then use it to sample from $D_{Z^n},\gamma$ and hash function will output the sample if it is invertible in $R_q$. I have created the following code to do this task:

def Hash1(message):
from Crypto.Hash import SHA256
import base62
output=SHA256.new(message)
print output
c=generate_error2(len(str(output.hexdigest())))
return c

def generate_error2(len):
f = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], len, sigma2)()
return Y(f)

sigma = sqrt(8/sqrt(2*pi))

R.<X> = PolynomialRing(GF(modulus),sparse=True)     # Gaussian field of integers
Y.<x> = R.quotient(X^(dimension) + 1)   # Cyclotomic field
c=Hash1(str(i)+str(j)+str(xi.list()))


This code will generate the elements in $R_q$, but how do I check if elements are invertible in $R_q$ or not?

• I assume you meant $R_q = \mathbb Z_q[x]/(x + 1)$. For an element of $R_q$ (i.e., a coset of $(x + 1)$), pick a polynomial representative of it and compute its polynomial gcd with $x + 1$? – Squeamish Ossifrage May 6 '18 at 19:28
• The $R_q$ discussed is $R_q=\mathcal{Z}_q[x]/(x^n+1)$. I am doing gcd using this command $b.gcd(x^{1024}+1)$ where b is random element in $R_q$. I am getting this error : AttributeError: 'PolynomialQuotientRing_generic_with_category.element_class' object has no attribute 'gcd' – vivek May 7 '18 at 4:48
• Sorry, I meant $x^n + 1$ above, not $x + 1$, but it's too late to edit. This sounds like a programming problem with Sage, not a cryptography problem. – Squeamish Ossifrage May 7 '18 at 5:04