Recent work
These are some recent articles on higher residuosity.
2020
A New Generalisation of the Goldwasser-Micali Cryptosystem Based on the Gap 2k-Residuosity Assumption (Diana Maimuţ and George Teşeleanu)
Abstract.
We present a novel public key encryption scheme that enables users to exchange many bits messages by means of at least two large prime numbers in a Goldwasser-Micali manner. Our cryptosystem is in fact a generalization of the Joye-Libert scheme (being itself an abstraction of the first probabilistic encryption scheme). We prove the security of the proposed cryptosystem in the standard model (based on the gap2k-residuosity assumption) and report complexity related facts. We also describe an application of our scheme to biometric authentication and discuss the security of our suggested protocol. Last but not least, we indicate several promising research directions.
New Assumptions and Efficient Cryptosystems from the e-th Power Residue Symbol
(Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, Jun Shao, Licheng Wang and Zhusen Liu)
Abstract.
The e-th power residue symbol (αp)e is a useful mathematical tool in cryptography, where α is an integer, p is a prime ideal in the prime factorization of pZ[ζe] with a large prime p satisfying e∣p−1, and ζe is an e-th primitive root of unity. One famous case of the e-th power symbol is the first semantic secure public key cryptosystem due to Goldwasser and Micali (at STOC 1982). In this paper, we revisit the e-th power residue symbol and its applications. In particular, we prove that computing the e-th power residue symbol is equivalent to solving the discrete logarithm problem. By this result, we give a natural extension of the Goldwasser-Micali cryptosystem, where e is an integer only containing small prime factors. 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 complexity assumption naturally extended from the one used in the Goldwasser-Micali cryptosystem, 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 efficiency and better bandwidth utilization.
2020 – New number-theoretic cryptographic primitives (Éric Brier, Houda Ferradi, Marc Joye and David Naccache)
Abstract.
This paper introduces new prq-based one-way functions and companion signature schemes. The new signature schemes are interesting because they do not belong to the two common design blueprints, which are the inversion of a trapdoor permutation and the Fiat–Shamir transform. In the basic signature scheme, the signer generates multiple RSA-like moduli ni = pi2qi and keeps their factors secret. The signature is a bounded-size prime whose Jacobi symbols with respect to the ni’s match the message digest. The generalized signature schemes replace the Jacobi symbol with higher-power residue symbols. Given of their very unique design, the proposed signature schemes seem to be overlooked “missing species” in the corpus of known signature algorithms.
2019 – Additively Homomorphic IBE from Higher Residuosity (Michael Clear and Ciaran McGoldrick)
Abstract.
We present an identity-Based encryption (IBE) scheme that is group homomorphic for addition modulo a “large” (i.e. superpolynomial) integer, the first such group homomorphic IBE. Our first result is the construction of an IBE scheme supporting homomorphic addition modulo a poly-sized prime e. Our construction builds upon the IBE scheme of Boneh, LaVigne and Sabin (BLS). BLS relies on a hash function that maps identities to eth residues. However there is no known way to securely instantiate such a function. Our construction extends BLS so that it can use a hash function that can be securely instantiated. We prove our scheme IND-ID-CPA secure under the (slightly modified) eth residuosity assumption in the random oracle model and show that it sup-ports a (modular) additive homomorphism. By using multiple instances of the scheme with distinct primes and leveraging the Chinese Remainder Theorem, we can support homomorphic addition modulo a “large”(i.e. superpolynomial) integer. We also show that our scheme fore >2 is anonymous by additionally assuming the hardness of deciding solvability of a special system of multivariate polynomial equations. We provide a justification for this assumption by considering known attacks.
General description
2016 – Residue Number Systems in Cryptography: Design, Challenges, Robustness. Secure System Design and Trustable Computing, 115–161. (Schinianakis, D., and Stouraitis, T.)
Abstract.
As conventional arithmetic solutions have improved at a fine-grain level,researchers have turned their attention to alternative number system representations in an effort to further boost up cryptosystem performance. The ancient Residue Number System (RNS) has emerged as a key-player in this endeavor. This chapter attempts to highlight important concepts of residue arithmetic and new RNS applications in modern cryptography are presented in a systematic and holistic manner. Progressing from algorithm and complexity analysis to state-of-the-art hardware implementations and useful cryptanalytic properties, the prospective reader is acquainted with most of the implications and challenges of this emerging field, while open research points are also highlighted.
Old papers
- 1978 – On kth power residues (P. Chowla and S. Chowla)
- 1974 – Bounds for consecutive kth power residues in the Eisenstein integers (Richard B. Lakein)
Abstract.This paper extends to the Eisenstein integers a + bp (a, b in Z, p2 + p + 1 = 0) the problem of the existence of a bound on the size of a sequence of m consecutive kth power residues of p, for all but a finite number of primes p and independent of p. The least such bound is denoted by ΛE(k, m). It is shown that ΛE(k, 2) is finite for k = 2,3,4 or 6n +- 1. On the other hand, for every ΛE(k, 3) = ΛE(3k, 4) = ΛE(k, 6) = infinity. Similar results are obtained for the related bound for m consecutives all in the same coset modulo the subgroup of kth power residues. - 1969 – On the distribution of kth power residues and non-residues modulo n (Karl K. Norton)
- 1983 – Patterns of power residues (Emma Lehmer)
Abstract.This paper examines the question of whether a given pattern x, x + a1, … , x + am-1, of kth power residues of length m can be postponed indefinitely. This is the case when there exists a prime q, called a delay prime, which does not contain this pattern even if q itself is considered as a kth power residue. It is conjectured that if there exists no delay prime then there exists a finite limit Λ = Λ(k, m; a1, … , am-1) for which the corresponding pattern will occur before Λ in every sufficiently large prime of the form kn + 1.
English
Arabic
Chinese (Simplified)
Dutch
French
German
Greek
Hebrew
Hindi
Italian
Korean
Portuguese
Romanian
Russian
Serbian
Spanish