Applications Of The Power Residue Symbols In Cryptography

The quadratic residuosity plays an important role in the construction and design of cryptographic schemes and protocols.As we all know,the landmark work of Gold-wasser and Micali gave the first formal definition of ciphertext indistinguishability and semantic security,and then opened a new chapter in the field of provable security research in cryptography.They constructed the first probabilistic encryption scheme based on the quadratic residuosity.However,this scheme has a large ciphertext expan-sion,which reduces its practical application value.How to improve the Goldwasser-Micali scheme is an old and challenging problem.In addition to the application of ho-momorphic encryption,the quadratic residuosity can also be used to construct pseudo-random number generators,zero-knowledge proof protocols,digital signature schemes,etc.Identity-based cryptography(IBC)is considered as the evolution of public-key cryptography.It treats the user's identity information as a public key,thereby elimi-nating the need for digital certificates.At present,most of the IBC schemes are based on bilinear pairing construction.However,a bilinear pairing is not time- and power-efficient,and the security of these schemes generally relies on untested complexity as-sumptions or problems.Cocks constructed the first pairing-free identity-based encryp-tion(IBE)scheme based on the quadratic reciprocity.Although this scheme has faster encryption and decryption algorithms,it is not very efficient in bandwidth utilization,and it is not anonymous.These shortcomings make Cocks' scheme receive less atten-tion.Number theory is one of the oldest branches of mathematics.Gauss,Eisenstein,Kummer and Dedekind made significant contributions to the establishment and research of algebraic number theory.We have already seen the quadratic residuosity shines in cryptography.How to apply more knowledge of number theory to cryptography is an important subject worthy of study with theoretical and practical significance.Starting from the above background and problems,this thesis has completed the following three aspects of work:1.New efficient homomorphic cryptosystems from the power residue symbols:In this part of our work,we revisit the power residue symbols and give some of their applications in cryptography.In particular,we prove that computing a type of power residue symbols is relevant to solving some discrete logarithm problem.By this result,we give a natural extension of the Goldwasser-Micali cryptosys-tem.Compared to another extension of the Goldwasser-Micali cryptosystem due to Joye and Libert(at EUROCRYPT 2013),our proposal is more efficient in terms of bandwidth utilization and decryption cost.With a new hardness assumption naturally extended from the one the Goldwasser-Micali cryptosystem relies on,our proposal is provable IND-CPA secure.Furthermore,we show that our results on the e-th power residue symbol can also be used to construct lossy trapdoor functions and circular and leakage resilient public-key encryptions with more ef-ficiency and better bandwidth utilization.2.Anonymous IBE from quadratic residuosity with fast encryption: In this part of our work,we develop two variants of Cocks' identity-based encryption.One variant has faster encryption,where the most time-consuming part only requires several modular multiplications.The other variant makes the first variant anony-mous under suitable complexity assumptions,while its decryption efficiency is about twice lower than the first one.Both the variants have ciphertext expansion twice more extensive than the original Cocks' identity-based encryption.To al-leviate the issue of the second variant's large ciphertext expansion,we consider using it to construct a public-key encryption with keyword search scheme with a fast encryption algorithm by means of the transform in[1].3.Extended Galbraith's test on the anonymity of IBEs from higher residuosity:At PKC 2019,Clear and Mc Goldrick presented the first group homomorphic IBE scheme that supports homomorphic addition modulo a poly-sized prime e.As-suming that deciding solvability of a special system of multivariate polynomial equations is hard,they proved that their scheme for e > 2 is anonymous.In this part of work,we review the classical Galbraith's test on the anonymity of the first pairing-free IBE scheme due to Cocks.With the eye of the reciprocity law over Fq[x],we can have a profound understanding of the test and naturally extend it to give a practical attack on the anonymity of the Clear-Mc Goldrick IBE scheme.Furthermore,we believe that our technique plays a crucial role in anonymizing IBE schemes from higher residuosity.