On the distribution of quadratic residues and non-residues modulo composite integers and applications to cryptography

摘要

We develop exact formulas for the distribution of quadratic residues and non-residues in sets of the form a + X = {(a + x) mod n vertical bar x <- 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. (C) 2019 Elsevier Inc. All rights reserved.