Computational Aspects of Quadratic and High-Order Residues with Applications in Cryptography

A special issue of Mathematics (ISSN 2227-7390). This special issue belongs to the section "Mathematics and Computer Science".

Deadline for manuscript submissions: closed (20 September 2022) | Viewed by 11793

Special Issue Editor

Department of Computer Science, Alexandru Ioan Cuza University of Iasi, Iasi 700506, Romania
Interests: theories and tools for high-level modeling, design, and analysis of systems; cryptography and computer security; algebraic foundations of computer science
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Quadratic and high-order residues have increasingly caught researchers’ attention due to their applications in computational number theory and especially in cryptography. Some of the fields where they have produced useful results are primality testing, pseudo-random generators, public-key cryptography, secure multiparty computation, etc. However, intense research is still needed to clarify various computational aspects and make them more efficient in cryptographic applications.

This Special Issue aims to bring together original contributions to the understanding of the computational aspects of quadratic and high-order residues and their applications in cryptography. Areas of interest include but by no means are restricted to:

  1. Efficient computation of high-order residues;
  2. Distribution of quadratic and high-order residues;
  3. Sums of residues and non-residues;
  4. Signed residues;
  5. High-order residuosity problem and its relations with other computationally hard problems;
  6. Applications in cryptography (pseudo-random generators, public-key cryptography, secure multi-party computation, signcrytion, etc.).

Prof. Dr. Ferucio Laurentiu Tiplea
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Mathematics is an international peer-reviewed open access semimonthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • quadratic residue
  • high-order residue
  • distribution of residue
  • residuosity problem
  • cryptography

Published Papers (6 papers)

Order results
Result details
Select all
Export citation of selected articles as:

Research

13 pages, 288 KiB  
Article
Speeding-Up Elliptic Curve Cryptography Algorithms
by Diana Maimuţ and Alexandru Cristian Matei
Mathematics 2022, 10(19), 3676; https://0-doi-org.brum.beds.ac.uk/10.3390/math10193676 - 07 Oct 2022
Cited by 2 | Viewed by 1972
Abstract
In recent decades there has been an increasing interest in Elliptic curve cryptography (ECC) and, especially, the Elliptic Curve Digital Signature Algorithm (ECDSA) in practice. The rather recent developments of emergent technologies, such as blockchain and the Internet of Things (IoT), have motivated [...] Read more.
In recent decades there has been an increasing interest in Elliptic curve cryptography (ECC) and, especially, the Elliptic Curve Digital Signature Algorithm (ECDSA) in practice. The rather recent developments of emergent technologies, such as blockchain and the Internet of Things (IoT), have motivated researchers and developers to construct new cryptographic hardware accelerators for ECDSA. Different types of optimizations (either platform dependent or algorithmic) were presented in the literature. In this context, we turn our attention to ECC and propose a new method for generating ECDSA moduli with a predetermined portion that allows one to double the speed of Barrett’s algorithm. Moreover, we take advantage of the advancements in the Artificial Intelligence (AI) field and bring forward an AI-based approach that enhances Schoof’s algorithm for finding the number of points on an elliptic curve in terms of implementation efficiency. Our results represent algorithmic speed-ups exceeding the current paradigm as we are also preoccupied by other particular security environments meeting the needs of governmental organizations. Full article
Show Figures

Figure 1

15 pages, 322 KiB  
Article
The Case of Small Prime Numbers Versus the Joye–Libert Cryptosystem
by George Teşeleanu
Mathematics 2022, 10(9), 1577; https://0-doi-org.brum.beds.ac.uk/10.3390/math10091577 - 07 May 2022
Cited by 1 | Viewed by 1030
Abstract
In this paper, we study the effect of using small prime numbers within the Joye–Libert public key encryption scheme. We introduce two novel versions and prove their security. We further show how to choose the system’s parameters such that the security results hold. [...] Read more.
In this paper, we study the effect of using small prime numbers within the Joye–Libert public key encryption scheme. We introduce two novel versions and prove their security. We further show how to choose the system’s parameters such that the security results hold. Moreover, we provide a practical comparison between the cryptographic algorithms we introduced and the original Joye–Libert cryptosystem. Full article
Show Figures

Figure 1

9 pages, 260 KiB  
Article
Efficient Generation of Roots of Power Residues Modulo Powers of Two
by Ferucio Laurenţiu Ţiplea
Mathematics 2022, 10(6), 908; https://0-doi-org.brum.beds.ac.uk/10.3390/math10060908 - 11 Mar 2022
Viewed by 1435
Abstract
We propose a characterization for the roots of power residues modulo powers of two. By this characterization, the remainder of dividing a root by a power of two is uniformly distributed in a set with two odd integers, while the quotient is uniformly [...] Read more.
We propose a characterization for the roots of power residues modulo powers of two. By this characterization, the remainder of dividing a root by a power of two is uniformly distributed in a set with two odd integers, while the quotient is uniformly distributed in an initial segment of positive integers. This property allows us to generate roots of power residues modulo powers of two efficiently. Full article
Show Figures

Figure 1

18 pages, 312 KiB  
Article
Lightweight Secure Integer Comparison
by Thijs Veugen
Mathematics 2022, 10(3), 305; https://0-doi-org.brum.beds.ac.uk/10.3390/math10030305 - 19 Jan 2022
Cited by 3 | Viewed by 1403
Abstract
We solve the millionaires problem in the semi-trusted model with homomorphic encryption without using intermediate decryptions. This leads to the computationally least expensive solution with homomorphic encryption so far, with a low bandwidth and very low storage complexity. The number of modular multiplications [...] Read more.
We solve the millionaires problem in the semi-trusted model with homomorphic encryption without using intermediate decryptions. This leads to the computationally least expensive solution with homomorphic encryption so far, with a low bandwidth and very low storage complexity. The number of modular multiplications needed is less than the number of modular multiplications needed for one Pallier encryption. The output of the protocol can be either publicly known, encrypted, or secret-shared. The private input of the first player is computationally secure towards the second player, and the private input of the second player is even unconditionally secure towards the first player. We also introduce an efficient client-server solution for the millionaires problem with similar security properties. Full article
Show Figures

Figure 1

9 pages, 303 KiB  
Article
An Efficient Approach to Point-Counting on Elliptic Curves from a Prominent Family over the Prime Field Fp
by Yuri Borissov and Miroslav Markov
Mathematics 2021, 9(12), 1431; https://0-doi-org.brum.beds.ac.uk/10.3390/math9121431 - 19 Jun 2021
Viewed by 3924
Abstract
Here, we elaborate an approach for determining the number of points on elliptic curves from the family Ep={Ea:y2=x3+a(modp),a0}, where p [...] Read more.
Here, we elaborate an approach for determining the number of points on elliptic curves from the family Ep={Ea:y2=x3+a(modp),a0}, where p is a prime number >3. The essence of this approach consists in combining the well-known Hasse bound with an explicit formula for the quantities of interest-reduced modulo p. It allows to advance an efficient technique to compute the six cardinalities associated with the family Ep, for p1(mod3), whose complexity is O˜(log2p), thus improving the best-known algorithmic solution with almost an order of magnitude. Full article
16 pages, 281 KiB  
Article
Generalized Galbraith’s Test: Characterization and Applications to Anonymous IBE Schemes
by Paul Cotan and George Teşeleanu
Mathematics 2021, 9(11), 1184; https://0-doi-org.brum.beds.ac.uk/10.3390/math9111184 - 24 May 2021
Cited by 1 | Viewed by 1231
Abstract
The main approaches currently used to construct identity-based encryption (IBE) schemes are based on bilinear mappings, quadratic residues and lattices. Among them, the most attractive approach is the one based on quadratic residues, due to the fact that the underlying security assumption is [...] Read more.
The main approaches currently used to construct identity-based encryption (IBE) schemes are based on bilinear mappings, quadratic residues and lattices. Among them, the most attractive approach is the one based on quadratic residues, due to the fact that the underlying security assumption is a well-understood hard problem. The first such IBE scheme was constructed by Cocks, and some of its deficiencies were addressed in subsequent works. In this paper, we focus on two constructions that address the anonymity problem inherent in Cocks’ scheme, and we tackle some of their incomplete theoretical claims. More precisely, we rigorously study Clear et al.’s and Zhao et al.’s schemes and give accurate probabilities of successful decryption and identity detection in the non-anonymized version of the schemes. Furthermore, in the case of Zhao et al.’s scheme, we give a proper description of the underlying security assumptions. Full article
Back to TopTop