Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 8/2023

29-04-2023

A bivariate polynomial-based cryptographic hard problem and its applications

Author: Bagher Bagherpour

Published in: Designs, Codes and Cryptography | Issue 8/2023

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The problem of factoring a composite integer into the product of two distinct primes (the factoring problem) is one of the famous hard problems on which the security of many cryptographic primitives relies. In this paper, we introduce a new cryptographic hard problem (RSA-polynomial problem) and prove that solving the RSA-polynomial problem is at least as hard as solving the factoring problem. As applications of the RSA-polynomial problem, we propose a commitment scheme. The proposed scheme is free of any group-exponentiation and outperforms the previous commitment schemes. Also, using the lattice basis reduction techniques and the RSA-polynomial problem, we propose a method to factor composite integers that are the product of two distinct primes.
previous article Two faces of blindness
next article Optimal and extremal graphical designs on regular graphs associated with classical parameters
Literature
1.
Abdolmaleki B., Baghery K., Lipmaa H., Siim J., Zajac M.: DL- Extractable UC-Commitment Schemes, Applied Cryptography and Network Security, 17th International Conference, Bogota, Colombia (2019).
2.
Alkim E., Barreto P.S.L.M., Bindel N., Longa P., Ricardini J.E.: The Lattice-Based Digital Signature Scheme qTESLA, Applied Cryptography and Network Security: 18th International Conference, ACNS 2020, Italy, Rome (2020).
3.
4.
Blazy O., Chevalier C., Pointcheval D., Vergnaud D.: Analysis and Improvement of Lindell’s UC-Secure Commitment Schemes, Proceedings of the 11th International Conference on Applied Cryptography and Network Security, June 2013, pp. 534–551 (2013).
5.
Bresson E., Catalano D., Pointcheval D.: A Simple Public-Key Cryptosystem with a Double Trapdoor Decryption Mechanism and Its Applications, ASIACRYPT, LNCS 2894, pp. 37–54 (2003).
6.
Byali, M., Patra A., Ravi D., Sarkar P.: Fast and Universally-Composable Oblivious Transfer and Commitment Scheme with Adaptive Security, eprint.iacr (2017).
7.
Campanelli M., Fiore D., Querol A.: LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs, Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security (2019).
8.
Coppersmith D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U. (eds) Advances in Cryptology—EUROCRYPT’96. EUROCRYPT. Lecture Notes in Computer Science, Vol 1070. Springer, Berlin (1996). https://​doi.​org/​10.​1007/​3-540-68339-9_​16.
9.
10.
Crescenzo G.D., Katz J., Ostrovsky R., Smith A.: Efficient and Non-interactive Non-malleable Commitment, EUROCRYPT 2001, LNCS 2045, pp. 40–59 (2001).
11.
Damgard I.: Commitment Schemes and Zero-Knowledge Protocols, Lectures on Data Security, LNCS 1561, pp. 63–86 (1999).
12.
Fischlin M., Fischlin R.: Efficient non-malleable commitment schemes, CRYPTO 2000, LNCS 2000, pp. 413–431 (1880).
13.
Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for Hard Lattices and New Cryptographic Constructions, Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing (2008).
14.
Goyal V., Lee C.K., Ostrovsky R., Visconti I.: Constructing Non-malleable Commitments: A Black-Box Approach, IEEE 53rd Annual Symposium on Foundations of Computer Science, New Brunswick, NJ, USA (2012).
15.
Hamouda F.B., Blazy O., Chevalier C., Pointcheval D., Vergnaud D.: Efficient UC-Secure Authenticated Key-Exchange for Algebraic Languages, International Workshop on Public Key Cryptography, PKC 2013, pp. 272–291 (2013).
16.
Hardwick F.S., Gioulis A., Akram R.N., Markantonakis K.: E-Voting with Block Chain: An E-Voting Protocol with Decentralisation and Voter Privacy, 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) (2018).
17.
Howgrave-Graham N.: Finding small roots of univariate modular equations revisited. In: Darnell M. (ed.) Cryptography and Coding 1997. Lecture Notes in Computer Science, vol. 1355, pp. 131–142. Springer, Berlin (1997).
18.
Jhanwar M.P., Venkateswarlu A., Safavi-Naini R.: Paillier-Based Publicly Verifiable (Non-interactive) Secret Sharing, Designs codes and Cryptography. 18. March (2014).
19.
20.
Lindell Y.: Highly-efficient universally-composable commitments based on the DDH assumption. In: Proceedings of the 30th Annual International Conference on Theory and Applications of Cryptographic Techniques: Advances in Cryptology, pp. 446–466 (2011)
21.
22.
Micali S.: Fair public-key cryptosystems. In: Advances in Cryptology-CRYPTO’92, Lecture Notes in Computer Science, pp. 113–138. Springer, Berlin (1992).
23.
Micciancio D., Regev O.: Lattice-based cryptography. In: Bernstein D.J., Buchmann J., Dahmen E. (eds.) Post-quantum Cryptography. Springer, Berlin (2009).MATH
24.
Paillier P.: Public key cryptosystems based on composite degree residuosity classes. In: EUROCRYPT’99, p. 223–238 (1990).
25.
Pedersen T.P.: Non-interactive and information-theoretic secure verifiable secret sharing. In: Advances in Cryptology-CRYPTO’91, pp. 129–140 (1992).
26.
Schoenmakers B.: Lecture Notes Cryptographic Protocols. Department of Mathematics and Computer Science, Technical University of Eindhoven, Eindhoven (2022).
27.
Stinson D.R., Paterson M.R.: Cryptography Theory and Practice, 4th edn CRC Press, Boca Raton (2019).MATH
28.
Zaghian A., Bagherpour B.: A fast publicly verifiable secret sharing scheme using homogeneous linear recursion. Isecure 12, 79–87 (2020).
29.
Zhou J., Feng Y., Wang Z., Guo D.: Using secure multi-party computation to protect privacy on a permissioned block-chain. Sensors 21, 1540 (2021).CrossRef
Metadata
Title
A bivariate polynomial-based cryptographic hard problem and its applications
Author
Bagher Bagherpour
Publication date
29-04-2023
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 8/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-023-01229-1

Other articles of this Issue 8/2023

Designs, Codes and Cryptography 8/2023 Go to the issue

OriginalPaper

The q-ary Golay arrays of size are standard

OriginalPaper

Block-transitive 3-(v, k, 1) designs associated with alternating groups

OriginalPaper

Two faces of blindness

OriginalPaper

A general construction of regular complete permutation polynomials

OriginalPaper

Differential spectrum of a class of APN power functions

OriginalPaper

A polynomial time algorithm for breaking NTRU encryption with multiple keys

Premium Partner

    Image Credits