Jeff Hoffstein

Brown University

Digital signatures based on quadratic forms over the ring R=(Z/qZ)[x]/(x^N -1).

Heilbronn Number Theory Seminar

18th October 2017, 4:00 pm – 5:00 pm
Howard House, 4th Floor Seminar Room

I'll explain first what a digital signature is, without assuming previous knowledge. I'll then explain how a digital signature can be based on the following problem: Suppose one is given an element c = c(x) = c_0 + c_1 x +...+c_{N-1}x^{N-1} of R, with the c_i chosen randomly from the set {-1,0,1}. Also, suppose one is given a quadratic form Q(u,v) = r_1 u^2 +r_2 uv+r_3 v^2, with each r_i being an element of R, namely a polynomial in x of degree less than or equal to N-1 with coefficients in Z/qZ. Then, find polynomials u_0,v_0 contained in R, such that the new polynomial element of R, Q(u_0,v_0), when the coefficients are first reduced modulo q and then lifted to the integers to the interval (-q/2,q/2], satisfies two simultaneous constraints: the coefficients of Q(u_0,v_0) are small compared to q and also Q(u_0,v_0) is congruent to c(x) modulo 3.

Comments are closed.