On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography

Ferucio Laurentiu Tiplea; Sorin Iftene; George Teseleanu; Anca-Maria Nica

Paper 2019/638

On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography

Ferucio Laurentiu Tiplea, Sorin Iftene, George Teseleanu, and Anca-Maria Nica

Abstract

We develop exact formulas for the distribution of quadratic residues and non-residues in sets of the form $a + X = {(a + x) mod n ∣ x \in X}$ , where $n$ is a prime or the product of two primes and $X$ is a subset of integers with given Jacobi symbols modulo prime factors of $n$ . We then present applications of these formulas to Cocks' identity-based encryption scheme and statistical indistinguishability.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. Applied Mathematics and Computation
Keywords: Jacobi symbol probability distribution statistical distance identity-based encryption
Contact author(s): ferucio tiplea @ uaic ro
siftene2013 @ gmail com
george teseleanu @ yahoo com
meinsta @ yahoo com
History: 2022-03-15: last of 3 revisions; 2019-06-03: received; See all versions
Short URL: https://ia.cr/2019/638
License: CC BY

BibTeX

@misc{cryptoeprint:2019/638,
      author = {Ferucio Laurentiu Tiplea and Sorin Iftene and George Teseleanu and Anca-Maria Nica},
      title = {On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/638},
      year = {2019},
      url = {https://eprint.iacr.org/2019/638}
}