Cryptology ePrint Archive: Report 2019/638
On the Distribution of Quadratic Residues and Non-residues Modulo Composite Integers and Applications to Cryptography
Ferucio Laurentiu Tiplea and Sorin Iftene and 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)\bmod n\mid 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.
Category / Keywords: public-key cryptography / Jacobi symbol, probability distribution, statistical distance, identity-based encryption
Original Publication (with minor differences): Applied Mathematics and Computation
Date: received 2 Jun 2019, last revised 15 Mar 2022
Contact author: ferucio tiplea at uaic ro, siftene2013 at gmail com, george teseleanu at yahoo com, meinsta at yahoo com
Available format(s): PDF | BibTeX Citation
Version: 20220315:091954 (All versions of this report)
Short URL: ia.cr/2019/638
[ Cryptology ePrint archive ]