System and Method for Private-Key Fully Homomorphic Encryption and Private Search Between Rings

摘要

A system for producing a public ring that is fully homomorphically encrypted. The system comprises a processor which generates a first presentation G of a ring, wherein G=x, y|x²=0, y²=0, xy+(p+1)yx=1, where x and y are generators and p is a first private prime number. The system further generates a second presentation H of the ring. H is defined as follows: H=x, y, t|x²=0, y²=0, t=m₁yx, xy+m₂yx+t=1. In addition, m₁ and m₂ are positive integers and p+1=m₁+m₂, wherein t is a generator and the first presentation G and the second presentation H are isomorphic. The system further produces a public ring Ĥ that is fully homomorphically encrypted, where:; $$ \hat{H}=〈x,y,tN·1=1,x^2=1,y^2=0,\mathrm{xyx}=x,\mathrm{yxy}=y,\mathrm{tx}=0,\mathrm{yt}=0,t^2=t+\frac{m_2^2-m_2}{m_1}\mathrm{tyx}〉,$$ ;N=pq and further, q is a second private prime number, and the public ring Ĥ is further, publically available. A corresponding method is also disclosed.