A result on the distribution of quadratic residues with applications to elliptic curve cryptography

Muralidhara, V. N. ; Sen, Sandeep (2007) A result on the distribution of quadratic residues with applications to elliptic curve cryptography INDOCRYPT 2007, 8th International Conference on Cryptology in India .

[img]
Preview
PDF - Author Version
146kB

Official URL: http://www.cse.iitd.ernet.in/~ssen/conf/indocrypt0...

Abstract

In this paper, we prove that for any polynomial function f of fixed degree without multiple roots, the probability that all the (f(x + 1), f(x + 2), ..., f(x +κ)) are quadratic non-residue is ≈ 1/2κ. In particular for f(x) = x3 + ax + b corresponding to the elliptic curve y2 = x3 + ax + b, it implies that the quadratic residues (f(x + 1), f(x + 2), . . . in a finite field are sufficiently randomly distributed. Using this result we describe an efficient implementation of El-Gamal Cryptosystem. that requires efficient computation of a mapping between plain-texts and the points on the elliptic curve.

Item Type:Article
Source:Copyright of this article belongs to Springer.
ID Code:90267
Deposited On:08 May 2012 08:35
Last Modified:19 May 2016 04:32

Repository Staff Only: item control page