Multivariate Public Key Cryptosystems
- © 2020
- Jintai Ding ORCID: https://orcid.org/0000-0003-1257-7598 0 ,
- Albrecht Petzoldt 1 ,
- Dieter S. Schmidt 2
Department of Mathematical Sciences, University of Cincinnati, Cincinnati, USA
You can also search for this author in PubMed Google Scholar
Department of Computer Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, Erlangen, Germany
Department of electrical engineering and computer science, university of cincinnati, springboro, usa.
- Due to the fast development in MPKC, this second edition has been totally rewritten with many more new ideas and research results
- Presents the essential ideas, methods, and examples, so that readers will not be distracted by technical details, which can be found in the references provided
- Relevant software for this book is available for public use located at the book’s website, which provides interested readers a starting point to further develop their understanding and computational intuition by experimenting with the software
Part of the book series: Advances in Information Security (ADIS, volume 80)
7031 Accesses
14 Citations
This is a preview of subscription content, log in via an institution to check access.
Access this book
- Available as EPUB and PDF
- Read on any device
- Instant download
- Own it forever
- Durable hardcover edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
Tax calculation will be finalised at checkout
Other ways to access
Licence this eBook for your library
Institutional subscriptions
Table of contents (8 chapters)
Front matter, introduction.
- Jintai Ding, Albrecht Petzoldt, Dieter S. Schmidt
Multivariate Cryptography
The matsumoto-imai cryptosystem, hidden field equations, oil and vinegar, the simplematrix encryption scheme, solving polynomial systems, back matter.
- Post-quantum Cryptograpy
- public key cryptography
- public key encryption
- digital signatures
- quantum computing
- Shor’s Algorithm
- quantum-resistant
- quantum-proof
- multivariate polynomials
- multivariate quadratic polynomials
- Groebner Basis
- XL algorithm
- Degree of regularity
- Min-Rank problem
- Unbalanced Oil-Vinegar Signature
- Rainbow Signature
- Algebraic Attack
About this book
Authors and affiliations.
Jintai Ding
Albrecht Petzoldt
Dieter S. Schmidt
About the authors
Bibliographic information.
Book Title : Multivariate Public Key Cryptosystems
Authors : Jintai Ding, Albrecht Petzoldt, Dieter S. Schmidt
Series Title : Advances in Information Security
DOI : https://doi.org/10.1007/978-1-0716-0987-3
Publisher : Springer New York, NY
eBook Packages : Computer Science , Computer Science (R0)
Copyright Information : Springer Science+Business Media, LLC, part of Springer Nature 2020
Hardcover ISBN : 978-1-0716-0985-9 Published: 01 October 2020
eBook ISBN : 978-1-0716-0987-3 Published: 30 September 2020
Series ISSN : 1568-2633
Series E-ISSN : 2512-2193
Edition Number : 2
Number of Pages : XXV, 253
Number of Illustrations : 30 b/w illustrations
Topics : Cryptology , Quantum Computing , Systems and Data Security , Symbolic and Algebraic Manipulation , Theory of Computation
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Systematic and Critical Review of RSA Based Public Key Cryptographic Schemes: Past and Present Status
Ieee account.
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
What a lovely hat
Is it made out of tin foil , paper 2005/393, multivariate quadratic polynomials in public key cryptography.
Christopher Wolf
This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography. In the first chapter, some general terms of cryptography are introduced. In particular, the need for public key cryptography and alternative schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest-Shamir-Adleman) nor the discrete logarithm (like ECC, elliptic curve cryptography). This is followed by a brief introduction of finite fields and a general discussion about Multivariate Quadratic systems of equations and ways of representing them. In this context, affine transformations and their representations are also discussed. After these tools are introduced, they are used to show how Multivariate Quadratic equations can be used for signature and encryption applications. In addition, the problem of Multivariate Quadratic polynomial equations is put into perspective and a link with the theory of NP-completeness is established. The second chapter concludes with the two related problems "isomorphism of polynomials" and "minimal rank" of the sum of matrices. Both prove useful in the cryptanalysis of Multivariate Quadratic systems. The main part of this thesis is about concrete trapdoors for the problem of Multivariate Quadratic public key systems. We can show that all such systems fall in one of the following four classes: unbalanced oil and vinegar systems (UOV), stepwise triangular systems (STS), Matsumoto-Imai Scheme A (MIA), and hidden field equations (HFE). Moreover, we demonstrate the use of several modifiers. In order to evaluate the security of these four basic trapdoors and their modifiers, we review some cryptanalytic results. In particular, we were able to develop our own contributions in this field by demonstrating an affine approximation attack and an attack using Gr"obner base computations against the UOV class. Moreover, we derived a key recovery and inversion attack against the STS class. Using our knowledge of the HFE class, we develop two secure versions of the signature scheme Quartz. Another important part of this thesis is the study of the key space of Multivariate Quadratic public key systems. Using special classes of affine transformations, denoted ``sustainers", we are able to show that all four basic classes have some redundancy in their key spaces and hence, have a smaller key space than previously expected. In particular for the UOV and the STS class, this reduction proves quite dramatic. For HFE and MIA, we only find some minor redundancies. Moreover, we are able to show that our results for MIA are the only ones possible, i.e., there are no other redundancies than the one we describe in this thesis. In addition, we extend our results to several important variations of HFE and MIA, namely HFE-, HFEv, HFEv-, and MIA-. They have been used in practice for the construction of signature schemes, namely Quartz and Sflash. In order to demonstrate the practical relevance of Multivariate Quadratic constructions and also of our taxonomy, we show some concrete examples. In particular, we consider the NESSIE submissions Flash, Sflash, and Quartz and discuss their advantages and disadvantages. Moreover, we describe some more recent developments, namely the STS-based schemes enhanced TTS, Tractable Rational Maps, and Rainbow. Then we move on to some application domains for Multivariate Quadratic public key systems. In particular, we see applications in the area of product activation keys, electronic stamps and fast one-way functions. Finally, we suggest some new schemes. In particular, we give a generalisation of MIA to odd characteristics and also investigate some other trapdoors like STS and UOV with the branching and the homogenisation modifiers. All in all, we believe that Multivariate Quadratic polynomial systems are a very practical solution to the problem of public key cryptography. At present, it is not possible to use them for encryption. However, we are confident that it will be possible to overcome this problem soon and use Multivariate Quadratic constructions both for encrypting and signing.
- < Previous
Home > SCRIPPS > SCRIPPS_STUDENT > SCRIPPS_THESES > 1816
Scripps Senior Theses
Cryptography and digital signatures.
Maya Nichols , Scripps College Follow
Graduation Year
Document type.
Campus Only Senior Thesis
Degree Name
Bachelor of Arts
Mathematics
Christopher Towse
Douglas Goodwin
Terms of Use & License Information
Terms of Use for work posted in Scholarship@Claremont .
Rights Information
© 2022 Maya Nichols
What is security and what makes a cryptosystem secure? This thesis explores these questions by looking at the components of a couple public- key cryptosystems and digital signature schemes, attacks against them, and ways of improving security.
Recommended Citation
Nichols, Maya, "Cryptography and Digital Signatures" (2022). Scripps Senior Theses . 1816. https://scholarship.claremont.edu/scripps_theses/1816
This thesis is restricted to the Claremont Colleges current faculty, students, and staff.
Since May 26, 2022
Advanced Search
- Notify me via email or RSS
- Colleges, Universities, and Library
- Schools, Programs, and Departments
- Disciplines
Author Corner
- Faculty Submission
- Student Submission
- Policies and Guidelines
Useful Links
- Claremont Colleges Library
- Claremont Colleges Digital Library
Home | About | FAQ | My Account | Accessibility Statement
Privacy Copyright
IMAGES
VIDEO
COMMENTS
3.2.3 Algorithms Break. It has been demonstrated that a quantum computer-based algorithm can break the symmetric key cryptographic algorithm by a factor of the square root of the size of the key. For instance, to find an image of a 256-bit hash function, a quantum algorithm will take only 2128 times.
that there exist both a public and private key for the two parties involved. An illustration of how public key cryptography works, from [15], follows: Public Encryption Key Private Decryption Key Alice E. a. D. a. Bob E. b. D. b. Figure 2.1: Generalized Public Key The security of public key cryptosystems lie in the creation and usage of one-way ...
Large quantum computers pose a threat to our public-key cryptographic infrastructure. The possible responses are: 1. Do nothing; accept the fact that quantum computers might be used to break widely ... This thesis presents several detailed cost estimates for attacks on public-key cryptosys-tems. These cost estimates track quantities that have ...
Multivariate public-key cryptography (MPKC) is considered a leading candidate for post-quantum cryptography (PQC). It is based on the hardness of the multivariate quadratic polynomial (MQ) problem, which is a problem of finding a solution to a system of quadratic equations over a finite field. In this paper, we survey some recent progress in ...
Since the inception of Cryptography, Information theory and Coding theory have influenced cryptography in myriad ways including numerous information-theoretic notions of security in secret sharing, multiparty computation and statistical zero knowledge; and by providing a large toolbox used extensively in cryptography. This thesis addresses two ...
Hellman [4] in 1976, and mostly known as public key cryptography, two keys are involved: one is public, and one is private. In general, the two keys are related by a mathematical process with the idea that it is computationally infeasible to determine one key given the other one. To encrypt and send a message, the sender uses the public key of ...
POST-QUANTUM PUBLIC-KEY CRYPTOGRAPHY by Mojtaba Bisheh Niasar A Dissertation Submitted to the Faculty of The College of Engineering and Computer Science in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Florida Atlantic University Boca Raton, FL August 2022
Nowadays, public-key cryptography has many applications and one of them is in cloud storage. Cloud storage is the storage service provided by the cloud server for the users to store their data. Since the data is uploaded to the server instead of ... In the first part of this thesis, we focus on tightly secure public-key cryptographic schemes ...
public-key cryptography Houda Ferradi To cite this version: Houda Ferradi. Integrity, authentication and confidentiality in public-key cryptography. Cryptography ... thesis through the French ANR Project ANR-12-INSE-0014 SIMPATIC. I express my affection to the numerous members of the ENS' Cryptography and Security teams. I will
The four-volume proceedings set LNCS 14601-14604 constitutes the refereed proceedings of the 27th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2024, held in Sydney, NSW, Australia, April 15-17, 2024. The 54 papers included in these proceedings were carefully reviewed and selected from 176 submissions.
Abstract. Identity-based encryption systems are characterized by the fact that the public key is easy to remember, and the step of linking the public key to a specific identity is omitted; the identity (e.g., an e-mail address) is the public key. Applications of Identity-based encryption are still relatively rare, although there are now various ...
This book gives a systematic introduction into the field of Multivariate Public Key Cryptosystems (MPKC), and presents the most promising multivariate schemes for digital signatures and encryption. Although, this book was written more from a computational perspective, the authors try to provide the necessary mathematical background.
Dec 2023. Nong Phuong Trang. Lưu Hồng Dũng. The paper proposes a type of block cipher algorithm based on cryptographic hash function and public key cryptography. The algorithm proposed here is ...
Public key Cryptography provides a set of cryptographic algorithms in achieving data security through confidentiality, integrity and authentication. Among all cryptographic algorithms in general and public key cryptography in particular, RSA is one of the most widely used and applied algorithms. Since its inception, it is commonly being adopted ...
The widespread use of public-key cryptography requires a public-key infrastruc-ture to publish and manage public-key values. Without a functioning infrastruc-ture, public-key cryptography is only marginally more useful than traditional, se-cret-key cryptography. This thesis presents a set of characteristics that are common to all public-key in-
Public Key: P= S F T. Private Key: T;S;F. Reduces number of variables in the public key smaller key sizes smaller signatures A new MinRank attack a problem to find linear combinations of a set of matrices to achieve the minimum rank. Rainbow is a NIST round 2 candidate. Jintai Ding Quantum Cryptanalysis, Simons Institute, 02.2020 18/40
2 Basic cryptography concepts 2.1 Public-key encryption An asymmetric, or public-key, encryption schemes is a triple of randomized algo-rithms having the following interfaces The key generator (given the security parameter) outputs a public key and a secret key. The encryption algorithm takes a public key and a valid message, and out-puts a ...
Thesis Advisor: Len Adleman, Assistant Professor. PAGE 2 Introduction. This thesis is concerned with the problem of actually achieving a practical communication system using public-key cryptography. The public-key paradigm seems suited for communications applications requiring security. The differences between traditional and
This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography. In the first chapter, some general terms of cryptography are introduced. In particular, the need for public key cryptography and alternative schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest ...
The major applications of public key cryptography are authentication, non-repudiation, and key exchange [3, 4]. The widely adopted public-key cryptography algorithm in use today is the RSA (Rivest ...
cryptographic ideas like symmetric and public-key cryptography, cryptographic protocols, cryptanalysis, and how they relate to blockchain technol-ogy. In doing so, the thesis establishes the foundation for evaluating the complex-ities associated with protecting and authenticating transactions in decentralized systems. As I move on, the ...
Public Key Systems The reader interested in public key cryptography is re ferred to [4] for an excellent tutorial overview. So that this thesis is self contained, two sections from that paper are reproduced below with only minor changes to introduce the con cepts of public key systems and digital signatures.
Abstract. What is security and what makes a cryptosystem secure? This thesis. explores these questions by looking at the components of a couple public-. key cryptosystems and digital signature schemes, attacks against them, and. ways of improving security.
This thesis aims at analysing the security of the standard hash function Cellular Authentication and Voice Encryption Algorithm (CAVE) used for authentication and key-derivation in the second generation (2G) North American IS-41 mobile phone system and proposes schemes that offer more resistance against these attacks.