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
    print output
    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

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

  • $\begingroup$ 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$? $\endgroup$ – Squeamish Ossifrage May 6 '18 at 19:28
  • $\begingroup$ 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' $\endgroup$ – vivek May 7 '18 at 4:48
  • $\begingroup$ 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. $\endgroup$ – Squeamish Ossifrage May 7 '18 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.