96,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Sprache: Englisch
Attribute-based Encryption (ABE) Enables readers to understand applications of attribute-based encryption schemes in cloud computing with the support of blockchain technology With a focus on blockchain technology, Attribute-based Encryption (ABE) provides insight into the application of attribute-based encryption (ABE) schemes, discussing types of blockchains, fundamentals of blockchain, and how blockchains are constructed. Comprised of 16 chapters, the text provides an overview of the components that go into creating a dual ABE system of encryption proofs within the following: composite bilinear groups, dual pairing vector space framework, matrix pairing framework, framework for matrix pairing, and the application of cryptographic scheme on blockchain. The team of authors discuss the basic construction components of ABE and share the security models, including the selective and semi- adaptive security models, applying these to either prime order or composite order groups. The book also discusses the tools used for converting a composite order ABE scheme to prime order and an adaptive secure ABE scheme based on prime order. In Attribute-based Encryption (ABE), readers can expect to find information on: * Mathematical background of ABE, covering group and cyclic group, elliptic curves, curve selection, supersingular curves, ordinary curves, and weil and tate pairing * Basic construction components of ABE, covering access structure, monotone Boolean formula, linear secret-sharing scheme, and ordered binary decision diagram * Tools for converting composite order ABE schemes to prime order, covering security assumptions and conversion based on vectors for preliminaries, scheme construction, and security proof technique * Foundations of blockchain technology, covering blocks, miners, hash functions, and public key cryptography Attribute-based Encryption (ABE) is an essential resource for professionals working in the field of design and cybersecurity who wish to understand how to use blockchain and the ABE scheme to provide fine-grained access control in outsourced data on third-party cloud servers.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 552
Veröffentlichungsjahr: 2023
Ähnliche
Table of Contents
Cover
Table of Contents
Title Page
Copyright
About the Authors
Preface
Acknowledgments
Part I: Attribute-Based Encryption (ABE)
1 Foundation of Attribute-Based Encryption
1.1 Introduction
1.2 Functional Encryption
References
2 Mathematical Background
2.1 Group Theory
2.2 Ring Theory
2.3 Elliptic Curves
2.4 Divisors and Bilinear Map
2.5 Summary
References
3 Attribute-Based Encryption
3.1 Introduction
3.2 Basic Components of ABE Construction
3.3 Cryptographic Hard Assumptions
3.4 Provable Security
3.5 Security Notions
References
4 Data Access Control
4.1 Introduction
4.2 Concerns About Cloud-Based Access Control that Are Trustworthy
4.3 Summary
References
5 Selective Secure ABE Schemes Based on Prime Order Group
5.1 Introduction
5.2 The KP-ABE Scheme
5.3 The CP-ABE Scheme
5.4 Summary
References
6 Fully Secure ABE Schemes Based on Composite and Prime Order Groups
6.1 Introduction
6.2 A Fully Secure CP-ABE from Composite Order Group
6.3 A Fully Secure KP-ABE Scheme Based on Dual Vector Space
6.4 KP-ABE Scheme Based on Matrix
6.5 Summary
References
Part II: Concepts of Blockchain Technology
7 Blockchain Technology
7.1 Introduction
7.2 Architecture of Blockchain
7.3 Architecture of Blockchain 2.0 (Smart Contracts)
7.4 Architecture of Blockchain 3.0 (Blockchain Applications)
7.5 Blockchain 4.0
References
8 Scaling-Out Blockchains with Sharding
8.1 Introduction
8.2 Off-Chain Solution: Layer 2 Solutions
8.3 Rollups
8.4 Summary
References
Part III: Applying Blockchain with Real-Time Technologies
9 Blockchain Technology for Supply Management
9.1 Introduction
9.2 System Flow
References
10 Satellite Communication
10.1 Introduction
10.2 Analysis of Edge Computing Requirements of Low-Orbit Constellation Communication Networks
10.3 Summary
References
11 Foundation of Information-Centric Communication
11.1 Introduction
11.2 Information-Centric Communication
11.3 Name-Based Routing of Content
11.4 Benefits of Using ICN
11.5 Cost-Efficient and Scalable Distribution of Content Design Principles
11.6 ICN Design Challenges
References
12 Security Overall in Information-Centric Networks
12.1 Introduction
12.2 Content-Centric Network (CCN) Architecture
12.3 Naming System Design
12.4 Secure Naming Scheme for Information-Centric Networks
12.5 Data Transmission – Content Delivery
12.6 Traffic Load in Network Caching
12.7 Content's Freshness Detection
12.8 ICN Security
12.9 Attacks in ICN Architectures
12.10 ICN Attributes to Ensure Security Threats
12.11 Traffic Analysis and Prediction
12.12 Some Key Problem Statements
12.13 Blockchain-Based ICN Scheme Improvement
12.14 A Secured Information-Centric Network Based on Blockchain
12.15 Attribute-Based Encryption Scheme for the Information-Centric Network
References
13 Subscriber Data Management System Based on Blockchain
13.1 Introduction
13.2 Literature Review
13.3 System Design Description
13.4 Summary
References
14 A Secure Data-Sharing Blockchain-Based Crowdfunding System
14.1 Introduction
14.2 Literature Review
14.3 Proposed System
14.4 Summary
References
Index
End User License Agreement
List of Tables
Chapter 2
Table 2.1 Order of groups.
Chapter 3
Table 3.1 Secret sharing.
Chapter 5
Table 5.1 Notation.
Chapter 6
Table 6.1 Security proof structure.
Chapter 7
Table 7.1 Comparison of consensus algorithms.
Chapter 13
Table 13.1 Notation description.
List of Illustrations
Chapter 1
Figure 1.1 Symmetric encryption.
Figure 1.2 Asymmetric encryption.
Figure 1.3 Identity-based encryption.
Figure 1.4 Multiple users data sharing scenario.
Chapter 2
Figure 2.1 over .
Figure 2.2 Point addition on an elliptic curve over the real numbers.
Figure 2.3 Point doubling on an elliptic curve over the real numbers.
Figure 2.4 The inverse of a point on an elliptic curve.
Figure 2.5 The function .
Figure 2.6 The function .
Figure 2.7 The function .
Figure 2.8 The function .
Figure 2.9 Jump from to .
Chapter 3
Figure 3.1 Identity-based cryptography.
Figure 3.2 Key policy attribute-based encryption scheme.
Figure 3.3 Ciphertext policy attribute-based encryption scheme.
Figure 3.4 Secrets sharing of a secret among parties.
Figure 3.5 Graph showing equation .
Figure 3.6 Graph showing equation .
Figure 3.7 Graph showing equation .
Figure 3.8 Access tree and LSSS matrix.
Figure 3.9 KP-ABE cryptographic system.
Figure 3.10 CP-ABE cryptographic system.
Chapter 4
Figure 4.1 Basic access control system.
Chapter 7
Figure 7.1 An example of Merkle Tree (binary hash tree).
Figure 7.2 Block structure.
Figure 7.3 Categorization of blockchain nodes.
Figure 7.4 Blockchain peer-to-peer network.
Figure 7.5 A general Blockchain layered architecture.
Figure 7.6 classifications of blockchain consensus mechanisms.
Chapter 8
Figure 8.1 Scalability trilemma.
Figure 8.2 Sharding of blockchain network.
Figure 8.3 Improvements of sharding mechanism.
Figure 8.4 State channel.
Figure 8.5 Payment channel.
Figure 8.6 the zk-cave.
Figure 8.7 A numerical example of the Schnorr protocol.
Figure 8.8 A numerical example of the Pedersen protocol.
Chapter 9
Figure 9.1 Supply chain model.
Figure 9.2 System.
Figure 9.3 A simplified overview of the suggested secure covert communicatio...
Figure 9.4 Membership issuing key.
Figure 9.5 Sequence diagram of the system.
Figure 9.6 Block structure.
Figure 9.7 Block structure for a transaction pertaining to different transac...
Figure 9.8 Activity diagram of a simple scenario of two interacting parties ...
Chapter 10
Figure 10.1 Schematic diagram of satellite constellation topology.
Figure 10.2 Satellite coverage diagram.
Figure 10.3 Schematic diagram of satellite motion.
Figure 10.4 Edge computing platform logical structure.
Figure 10.5 Calculation offload execution flowchart.
Figure 10.6 System architecture.
Figure 10.7 System setup.
Figure 10.8 KeyGen.
Figure 10.9 Data encryption.
Figure 10.10 Data decryption.
Chapter 11
Figure 11.1 Content delivery overlay. In panel (a), content is delivered usi...
Figure 11.2 Name-based routing at a router.
Figure 11.3 Name-based routing mechanism.
Chapter 12
Figure 12.1 CCN architecture.
Figure 12.2 Data header format.
Figure 12.3 Traffic load in data caching.
Figure 12.4 ICN based on blockchain architecture.
Figure 12.5 Block structure.
Figure 12.6 CP-ABE in ICN design.
Figure 12.7 Data publication process.
Figure 12.8 Data retrieval process.
Chapter 13
Figure 13.1 SDM scheme based on blockchain.
Figure 13.2 Block structure.
Chapter 14
Figure 14.1 Simplified crowdfunding process.
Figure 14.2 Traditional crowdfunding process.
Figure 14.3 Crowdfunding models.
Figure 14.4 System model.
Figure 14.5 System framework.
Guide
Cover
Title Page
Copyright
About the Authors
Preface
Acknowledgments
Table of Contents
Begin Reading
Index
End User License Agreement
Pages
ii
iii
iv
xiii
xiv
xv
xvii
1
3
4
5
6
7
8
9
10
11
12
13
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
95
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
247
248
249
250
251
252
253
254
255
IEEE Press
445 Hoes Lane Piscataway, NJ 08854
IEEE Press Editorial Board
Sarah Spurgeon,
Editor in Chief
Jón Atli Benediktsson
Behzad Razavi
Jeffrey Reed
Anjan Bose
Jim Lyke
Diomidis Spinellis
James Duncan
Hai Li
Adam Drobot
Amin Moeness
Brian Johnson
Tom Robertazzi
Desineni Subbaram Naidu
Ahmet Murat Tekalp
Attribute-based Encryption (ABE)
Foundations and Applications within Blockchain and Cloud Environments
Qi XiaUniversity of Electronic Science and Technology of China, China
Jianbin GaoUniversity of Electronic Science and Technology of China, China
Isaac Amankona ObiriUniversity of Electronic Science and Technology of China, China
Kwame Omono AsamoahUniversity of Electronic Science and Technology of China, China
Daniel Adu WoraeUniversity of Electronic Science and Technology of China, China
Copyright © 2024 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates in the United States and other countries and may not be used without written permission. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in this book.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data
Names: Gao, Jianbin, author.
Title: Attribute-based encryption (ABE) : foundations and applications within blockchain and cloud environments / Jianbin Gao [and four others].
Description: Hoboken, New Jersey : Wiley-IEEE Press, [2024] | Includes index.
Identifiers: LCCN 2023036768 (print) | LCCN 2023036769 (ebook) | ISBN 9781119989356 (cloth) | ISBN 9781119989363 (adobe pdf) | ISBN 9781119989370 (epub)
Subjects: LCSH: Public key cryptography. | Blockchains (Databases)
Classification: LCC TK5102.94 .G365 2024 (print) | LCC TK5102.94 (ebook) | DDC 005.8/24–dc23/eng/20230824
LC record available at https://lccn.loc.gov/2023036768
LC ebook record available at https://lccn.loc.gov/2023036769
Cover design: WileyCover image: © Blackboard/Shutterstock
About the Authors
Qi Xia
Orcid id: 0000-0003-2245-2588
Qi Xia received the BSc, MSc, and PhD degrees in computer science from the University Electronic Science and Technology of China (UESTC), Chengdu, China, in 2002, 2006, and 2010, respectively. She is a Professor with the UESTC. She is currently the Deputy Director of the Cyberspace Security Research Centre, the Executive Director of the Blockchain Research Institute, the Executive Director of the Big Data Sharing and Security Engineering Laboratory of Sichuan province, and a Chief Scientist with YoueData Company Limited. She serves as the Principal Investigator of the National Key Research and Development Program of China in Cyber Security and has overseen the completion of more than 30 high-profile projects. She was a Visiting Scholar with the University of Pennsylvania (UPenn), Philadelphia, PA, USA, from 2013 to 2014. She has authored or coauthored more than 40 academic papers. Her research interests include network security technology and its application, big data security, and blockchain technology and its application. Dr. Xia has won the second place at the National Scientific and Technological Progress Awards in 2012. She is a member of the CCF blockchain committee.
Jianbin Gao
Orcid id: 0000-0001-7014-6417
Jianbin Gao received the PhD degree in computer science from the University Electronic Science and Technology of China (UESTC), Chengdu, China, in 2012. He was a Visiting Scholar with the University of Pennsylvania, Philadelphia, PA, USA, from 2009 to 2011. He is currently an Associate Professor with UESTC.
Isaac Amankona Obiri
Orcid id: 0000-0002-1642-0291
Isaac Amankona Obiri received his Master's and PhD in Computer Science and Technology from the University Electronic Science and Technology of China (UESTC), Chengdu, China, in 2022.
Kwame Omono Asamoah
Orcid id: 0000-0001-7361-1986
Kwame Omono Asamoah received a B.Sc. degree in computer science from the Kwame Nkrumah University of Science and Technology, Ghana, in 2014. He continued his academic journey by obtaining his master's degree in computer science and technology from the University of Electronic Science and Technology of China in 2018. Subsequently, he pursued his doctoral degree in computer science and technology from the University of Electronic Science and Technology of China, successfully completing it in 2022. He is currently a postdoctoral fellow at Zhejiang Normal University, where he actively engages in cutting-edge research. His current research interests encompass a wide range of topics, including blockchain technology, big data security, and educational technology.
Daniel Adu Worae
Orcid id: 0000-0002-6774-2725
Daniel Adu Worae received his BSc degree in Computer Engineering from the Kwame Nkrumah University of Science and Technology, Kumasi, Ghana, in 2020. He is currently pursuing his Master's degree in Computer Science and Technology at the University of Electronic Science and Technology of China (UESTC). His research interests include blockchain technology and its application, network and information security, cryptography, and computer networks.
Preface
In the last few decades, information and communication technology (ICT) devices and services have become central to our lives, fundamentally changing areas such as health, communication, travel, business, and recreation. Traditional ICT systems share and store sensitive data in untrusted networks. Thus, these sensitive data must be encrypted before being uploaded to a cloud server and a fine-grained access control must be supported when sharing sensitive data.
Since the emphasis is on multi-user data sharing, and the data encryptor does not know the identities of the data users in advance, symmetric encryption, asymmetric encryption, and identity-based encryption are impractical. The attribute-based encryption (ABE) schemes are excellent for multi-user data-sharing scenarios in which the identity of the data users is unknown in advance. ABE employs an access structure based on attributes in either the ciphertext or the secret key, and it is able to provide fine-grained access control with the guarantee that a user can only decrypt a message if they satisfy the constraints imposed by the access structure.
While blockchain technology has just recently become associated with new means of managing financial assets, its possibilities are practically limitless. Blockchain is a particularly promising and revolutionary technology because it reduces risk, eliminates fraud, and provides scalable transparency for a wide range of applications. Therefore, ABE schemes based on blockchain can achieve immense number of advantages including transparency, accountability, and data immutability.
This book provides guidelines for the current research and future trends in various areas associated with ABE and its integration with blockchain applications in cloud environments so that researchers get ready reference. It is expected that researchers and readers will get adequate information on these subjects, and the book will be helpful in their research endeavors. We'll look at the basic concepts of ABE, from the background knowledge, to specific constructions, theoretic proofs, and applications. Blockchain technology; practical aspects of what makes a blockchain, the inherent vulnerabilities of a decentralized network in the real world, the secret key for encryption and decryption and how to apply blockchain with real-time technologies.
November 2022
Qi Xia, China
Jianbin Gao, China
Isaac Amankona Obiri, Ghana
Daniel Adu Worae, Ghana
Acknowledgments
First, we would like to thank all the contributing authors. Without their work, this book would not have been possible. Namely, our thanks to Juan Wang, Yunbo Ding, Dr. Edson Tavares, and Dr. Christian Cobblah. We also thank them for cross-reading one another's chapters and providing fruitful feedback that has helped improve each chapter, and thus the book as a whole.
This work was supported by the Basic Strengthening Program (2021-JCJQ-JJ-0463), the scientific and technological innovation talents of Sichuan Province (2023JDRC0001), the Fundamental Research Funds for the Central Universities, the National Natural Science Foundation of China (No. U22B2029), and Shenzhen Research Program (No. JSGG20210802153537009).
Part IAttribute-Based Encryption (ABE)
1Foundation of Attribute-Based Encryption
1.1 Introduction
What is encryption? Encryption is a key concept in cryptography. To explain the meaning of encryption, let us consider the following scenario without being blown away by the whims of mathematics.
Imagine your friend Bob is organizing a back-alley chess game. Bob does not want anyone to come into his shady gambling den without authorization, so he issues you a pass with the phrase “Knock and wait.” When you knock on the right sleazy door, the bouncer asks for the pass in a genre-savvy baritone. You can get in if you say the right phrase. Otherwise, your entry will be denied, and you will stay outside in the metaphorical rain.
To stretch the analogy, Bob can alter the pass each time he hosts a chess game. Knowing the passphrase for the day, you can share it with one of your acquaintances or some of your friends in the criminal investigation bureau. In cryptography, the pass is referred to as a secret key. When plaintext is combined with a secret key, cryptography offers a black box that converts plaintext to ciphertext. The ciphertext is unreadable junk to those without the right secret key. On the other hand, those with a valid secret key can recover the plaintext from a given ciphertext back. The process involved in transforming plaintext into ciphertext is referred to as encryption. Succinctly put, encryption is the cryptographic mechanism of converting information into a secret code that conceals the true meaning of the transformed information (ciphertext). When an unauthorized party intercepts ciphertext, the intruder must determine which algorithm and keys were used to encrypt the message. The computation complexity required in decoding a ciphertext without a valid secret key is what makes encryption a crucial security tool.
Encryption has been a longstanding technique to secure sensitive data. Historically, it was used by governments and militaries. Encryption is used in modern times to secure data stored on computers and storage devices and data in transit across networks. Prior to the advent of public key cryptography, it was widely assumed that for two users to transmit data securely, they would need to establish a mutually held secret key. While this may be acceptable for certain small or close-knit groups, it is infeasible for larger networks, such as the Internet of today, which has billions of users. Diffie and Hellman [1] proposed a novel concept in public key cryptography over thirty years ago, where two parties can securely communicate without sharing a prior mutual secret, dramatically upsetting common knowledge held at the time. Public key encryption is a crucial tool today. It is widely used in developing tools ranging from secure web communication (e.g. secure shell [SSH], secure sockets layer [SSL]) to disk encryption and a secure software patch distribution. Before the introduction of functional encryption, there were widely held views that:
Encryption is a method of sending a message or data to a single entity with a secret key.
Access to encrypted data is all or nothing – one can either decrypt and read the entire plaintext or learn nothing about the plaintext other than its length.
These views determined the method used for computation of ciphertext and secret key before they were modified by functional encryption. Functional encryption enables a data encryptor to encrypt data with a boolean function, such that only a decryptor with the correct private key can recover the plaintext if the boolean function returns true. Before delving into the details of functional encryption and how it is a superior encryption technique, we will explore the earlier encryption techniques.
1.1.1 Symmetric Encryption
Howbeit, data can be encrypted with symmetric key encryption mechanisms. The symmetric key encryption algorithm uses only one secret key, referred to as a session key, to encipher and decipher information [2]. As seen in Figure 1.1, one secret key is required to cipher and decipher information in symmetric encryption. A key can be a number, a word, or a random sequence of letters. The key is used to scramble the plaintext of a message into unreadable content (ciphertext) and recover the content. Therefore, the session key must be shared in advance between the sender and recipient prior to its usage in the encryption method. Symmetric encryption includes advanced encryption standard (AES), RC4, data encryption standard (DES), RC5, and RC6. Encryption schemes like AES-128, 192, and 256 are the most extensively used symmetric algorithms.
The inherent problem with the symmetric encryption is that a session key must be exchanged between the data owner and data users in advance before a symmetric key encryption algorithm can be used [3]. However, it is impossible to know every potential data user in advance to share data with them in multi-user data sharing systems. Even if the data owner does, it has to encrypt the data repeatedly with each session key shared with the multiple data users in the system. There are as many as key pairs to be managed in an extensive network. Consequently, key management will undoubtedly involve high storage overhead.
1.1.2 Asymmetric Key Encryption
Symmetric encryption has existed for a very long time, whereas asymmetric encryption is very recent. For data encryption and decryption, asymmetric encryption requires two keys, namely public and private keys. The public keys are used for data encryption, whereas the private keys are required for data decryption. Asymmetric encryption enables parties to preserve sensitive information in an encrypted format on a public network, such as the Internet, without exchanging a session key in advance. Asymmetric encryption ensures that only the authorized recipient with the proper private key can decipher the encrypted messages. The use of two related keys in asymmetric encryption increases security, as anyone with the secret key can decipher the message. Anyone can send a message to any user using their public key, which is accessible to the public.
Figure 1.1 Symmetric encryption.
Figure 1.2 Asymmetric encryption.
As illustrated in Figure 1.2, the public key and private key are utilized to encrypt and decrypt a message, respectively. There is no need to protect the public keys because they are accessible to the whole public. However, the private key must be kept secret such that only the end user knows it; otherwise, any entity with knowledge of the private key can decrypt any communication encrypted with the corresponding public key. Using an asymmetric key for communication is substantially more secure than a symmetric key. Well-known asymmetric key encryption methods include EIGamal and Rivest–Shamir–Adleman (RSA).
To prevent man-in-the-middle attacks, asymmetric encryption relies on the public key infrastructure to associate a user's public key with a certificate. This certificate is “signed” by the Certificate Authority (CA), the digital equivalent of a notary. It is evident that the CA plays a significant role in the public key infrastructure (PKI) model since this approach is founded on the premise that the CA is true, trustworthy, and legitimate. Therefore, a hacker who takes control of a CA can use it to generate fake certificates and impersonate any public key.
Over the years, there have been repeated breaches of CA firms, including DigiNotar, GlobalSign, Comodo, and Digicert Malaysia. These attacks were a direct result of the commoditization of certificates, in which smaller, less qualified businesses have gained a larger proportion of the market for certificate authorities.
Asymmetric key encryption schemes also have some drawbacks similar to symmetric key encryption schemes. For example, the data owner must obtain each data user's public key, encrypt the data multiple times, and store multiple copies of the data in the cloud.
1.1.3 Identity-Based Encryption
Imagine a corporate email system in which the employees send encrypted communications. Alice discovers Bob's public key, writes a message, encrypts it in an email, and sends the email to Bob. However, Bob wrote his private key in his notebook, which he left at an airport. Or maybe Bob's private key was stored on his phone, and one of his children dropped it in the drain. Now that Bob has a new phone, he tries to read all of Alice's emails and discovers that he cannot. Without a private key, there are no emails that can be read. However, as is synonymous with key and door systems, when the lone key to a lock is lost, the entire lock must be replaced. Digital cryptosystems are no different; public and private keys are generated as a pair, and it is impossible to generate one from the other, just as it is impossible to construct a key from a lock. Bob must therefore generate a new pair of public and private keys, upload the new public key to the corporate directory, and inform everyone that the previous public key is no longer valid. As shown in Figure 1.3, if Alice does not detect this change, she will continue to send Bob encrypted emails using his previous public key, and Bob will continue to be unable to read them. It turns out that this is a widespread issue in cryptography systems – individuals are lousy at managing keys. In 1984, a cryptographer named Adi Shamir [4] came up with a brilliant concept: what if the firm itself managed the keys? He believed that the entire concept of public keys was excessively onerous and wished that individuals would use something more memorable: their identities (like a name or email). To send an email to Bob, simply use [email protected] as the recipient's public key. This concept is known as Identity-Based Encryption. In 2001, Dan Boneh and Matt Franklin [5] developed a system that is currently regarded as the most viable implementation of identity-based encryption to date. Identity-based encryption permits anyone within an organization to encrypt text using the identity of another user.
Figure 1.3 Identity-based encryption.
Identity-based encryption (IBE) altered the conventional notion of public-key cryptography by enabling the public-key to be any string, such as the recipient's email address. This means that a sender with access to the system's public parameters can encrypt a message using, for instance, the text-value of the recipient's name or email address as the key. The Private Key Generator provides the decryption key to the recipient (PKG). In order to function, the PKG first publishes a master public key and stores the associated master private key (referred to as the master key). Given the master public key, any party can derive the identity's public key by combining the master public key with the identity value. The person authorized to use the identity ID contacts the PKG to receive their corresponding private key, which is created using the master private key.
Consequently, parties can encrypt messages (or check signatures) without exchanging keys beforehand. This is especially beneficial in situations when pre-distribution of authenticated keys is impractical or impossible owing to technological limitations. However, IBE system has the same drawbacks as symmetric and asymmetric key encryption schemes, which makes it impractical for application in scenarios involving numerous users, particularly when the data owner is aware of the identities of all potential data users in advance. Also, if a Private Key Generator (PKG) is compromised, all communications protected for the lifespan of the public–private key pair utilized by that server are compromised as well. This makes the PKG an extremely desirable target for attackers. To reduce the risk posed by a hacked server, the master private–public key pair could be replaced with a new key pair that is independent. Nonetheless, this creates a key-management issue in which all users must possess the most recent public key for the server.
1.2 Functional Encryption
We will now describe a scenario to vividly highlight the challenges associated with data sharing and the need for functional data encryption. We consider data sharing among multiple entities. The entities in the data scenarios comprise the following:
Data owner
: This entity is the custodian of data that he/she would like to share with other people. He/she might have generated the data him or herself or has acquired the data from data producers such as IoT devices. The data owner can be a single entity, such as a patient, who wants to share their PHRs with a medical doctor for disease diagnosis and treatment, or a large organization, such as a hospital, which intends to share a medical record with a team of doctors in order to find an antidote to a disease outbreak. The data this entity is sharing is sensitive; it is usually encrypted offline before the data is outsourced to the cloud server.
Data users
: The data users' domain is made up of all the authorized recipients of the data as defined by the data owner. The users not only comprise people but devices as well. They access the outsourced data through the cryptographic service provider (CSP).
Cloud service provider
: This entity specializes in data sharing and storage. It stores the owner's encrypted data, which is received through a secure communication connection. It is a semi-trusted entity since it is considered that it will offer its services successfully, but it may attempt to read data.
Here, we consider a hypothetical data sharing between a patient and medical doctors. The patient is the data owner, while the medical doctors are the data users. Let's suppose a patient known as Bob is suffering from a rare disease known as “Achalasia,” and he wants to share his Personal Health Records (PHRs) with a specialized doctor in rare disease treatment who can provide medical service to him. In this scenario, Bob does not know beforehand who is actually available to provide the medical care he needs. Since PHRs are sensitive, Bob wants only medical doctors with certain credentials to access his data. So, Bob may encrypt the data over attributes such as (“medical doctor,” “rare disease,” and “City A”). Attribute-based encryption (ABE) allows only doctors in City A who specialize in rare diseases and are in close proximity to Bob's location to access his PHRs. The scenario of multiple users sharing data is depicted in Figure 1.4.
Traditionally, this kind of expressive access control has been enforced by a trusted server [6]. The server is entrusted with acting as a reference monitor, ensuring that a user has the proper certification before granting access to records or files. On the other hand, cloud servers are progressively storing data in a distributed manner over multiple cloud partners. Data replication across multiple locations has reliability and performance benefits. However, using multiple cloud data storage services has a high probability of one of the servers being compromised to expose the outsourced data. Hence, we would require the storage of sensitive data in encrypted form, so that the data remains private even if one of the hosting servers is compromised.
Figure 1.4 Multiple users data sharing scenario.
The idea of users having access to different segments of a ciphertext depending on the scope of access privileges was not considered in the domain of public key cryptography. However, with the emergence of “cloud” applications due to the improvement of computer networks and computing power, the concepts of public key encryption became wholly insufficient. For example, in many cases, a decryption policy must be specified in the ciphertext, and only those who meet the policy can decrypt. Depending on the decryptor's authority, we might only wish to grant access to a function of the plaintext. Consider a cloud service that stores encrypted photographs as a concrete example. An attacker might try to break into the cloud server to gain access to photographs with a specific face to extort money. As a result, the cloud requires a password-protected secret key that decrypts the target face's photographs but does not divulge any information about other images. More generally, the secret key may only expose a function of the plaintext image, such as a blurred image with the exception of the target face. Such tasks are incompatible with traditional public-key cryptography.
Functional encryption provides a new perspective of public key cryptosystems that offer an excellent balance of flexibility, efficiency, and security. A functional encryption scheme associates ciphertexts with descriptive values , secret keys with descriptive values , and a function , that defines what a user with a key for value should learn from a ciphertext with value . Attribute-based encryption (ABE), first presented by Sahai and Waters in [7], is a well-known form of functional encryption in which the ciphertext and secret key are determined by an access structure specified over attributes and subsets of attributes. A key can decrypt ciphertexts if the associated set of attributes meets the related access policy. ABE schemes are classified into two types: Ciphertext-Policy ABE (CP-ABE), in which access policies are embedded in ciphertexts and keys are associated with sets of attributes, and Key-Policy ABE (KP-ABE), which is the inverse of CP-ABE in which keys are associated with access policies and ciphertexts are associated with sets of attributes.
This section will explain techniques for developing provably secure functional encryption systems. We will concentrate on ABE schemes as an application. We will provide background information on the history of functional encryption and prior work in this field before presenting the summary.
1.2.1 Applications of Attribute-Based Encryption
ABE is beneficial in a range of applications. It can be used to enable fine-grained access control in public cloud computing while sharing encrypted data. Also, it can be used in the encryption of log data. Instead of encrypting each chunk of a log with all of the recipients' keys, the log can be encrypted selectively with attributes that match the recipients' attributes. The ABE primitive can be used for broadcast encryption to reduce the high cost of key management overhead. In vector-driven search engine interfaces, ABE techniques can be utilized. ABE provides a quick and easy technique to do a nearest-neighbor search across an encrypted database. Therefore, it can be used for biometric authentication as well. Because biometrics are inherently noisy, authentication should be effective when the supplied biometric is close to the user's credential in the system. The error-tolerance property of the ABE scheme can enable a private key (computed from a biometric measurement) to decrypt a ciphertext encrypted with a slightly different measurement of the same biometric.
1.2.2 Problems with Attribute-Based Encryption
The following are the key challenges impeding the deployment of the ABE scheme in systems.
Central trust
: Attribute-based encryption necessitates reliance on a centralized authority – the Private Key Generator (similar to Identity-Based Encryption). Hence, it is suitable for the business environments. There have been some scholarly studies in the literature on a more distributed version termed “
Decentralized Attribute-based Encryption
” (
DABE
); however, these schemes do not completely decentralize ABE. Instead, they expand the number of potential trust roots comparable to the CA architecture used on the web. This approach even makes the ABE scheme less secure.
Speed
: For attribute-based encryption, the creation of an access structure is required. The expressiveness of the access structure leads to expensive computation during decryption, which is the worst place to be slow because decryption is usually the most common process we perform against encryption. ABE scheme is roughly 20 times slower than classical symmetric encryption. This is related to ABE's expensive mathematical construct, such as bilinear pairing, exponentiation, and multiplication operations. Furthermore, the ABE scheme gets more computationally expensive as the number of attributes on a given access structure increases.
Malicious users revocation
: ABE systems suffer from the non-existence of malicious users revocation mechanisms. Revocation is more challenging in attribute-based systems, given that each attribute possibly belongs to multiple different users. Revoking attributes cannot revoke a specific identified malicious user but automatically revokes all the users in the system who shared the revoked attributes. Thus, revocation on attributes or attribute sets cannot accurately exclude malicious users.
1.2.3 A Brief History of Security Proof of Functional Encryption
Shamir's Identity-Based Encryption (IBE) [4] is credited with the invention of functional encryption. An identity-based encryption method allows any string to serve as a “public key,” rather than requiring public keys to be created in tandem with secret keys. For instance, a user can send an encrypted message to a recipient specified by an email address without requiring the recipient to have an established public key. Secret keys are associated with strings (also known as “identities”) must be obtained from a central authority who holds the master secret key. Suppose we want to impose a hierarchical structure on keys. In that case, we can generalize identity-based encryption to hierarchical identity-based encryption (HIBE), in which individuals can delegate secret keys to their subordinates.
There are inherent issues in providing security proof for functionality like IBE, which requires generating several secret keys from a single master secret key for different users. It is not enough to prevent one user from maliciously exploiting his own secret key to decrypt a ciphertext meant for another user; a robust security concept must also address collusion attacks, in which a group of users conspire to decipher a ciphertext encrypted to an identity outside of the group. To simulate such attacks, we imagine an adversary that is capable of acquiring a large number of secret keys and selecting the associated identities adaptively. At some stage, the adversary must select one identity to attack (for which no secret key has been collected), and it may then obtain keys for any additional identities. This necessitates security reduction to balance two competing goals: the simulator must be powerful enough to give the attacker as many keys as it adaptively seeks, but it must also be devoid of essential knowledge gained from the attacker's success.
The first security proofs for IBE schemes relied on the random oracle model, a heuristic that treats a fixed function as if it were truly random. The first security proofs presented in the standard model (which did not rely on such a heuristic) reached a weaker notion of security known as selective security. The selective security approach requires the attacker to choose the target of the attack before viewing the system's public settings. Because this is an unrealistic constraint, establishing selective security should be viewed as a step toward achieving comprehensive security rather than as an end in itself.
The concept of selective security makes a lot of sense in the context of the partitioning proof technique used by early research in IBE and HIBE. A partitioning proof splits all possible identities into two categories: those for which the simulator can generate secret keys and those that cannot. This gives the simulator a clear method to balance its competing aims, which include ensuring that all of the adversary's key requests are within the set of keys the simulator may make and that the attacked identity is inside the complement. Because the simulator already knows who is being attacked, the selective model makes the security proof much easier. The selective model enables a simulator to create a perfect partition, with the attacked identity being the only one for which the simulator cannot generate the secret key.
Waters [8] and Boneh and Boyen [9] overcame the requirement for selectivity to obtain an IBE security proof in the standard model. The security proof in [10] instructs the simulator to “guess” a partition and abort if the attacker attempts to exceed its bounds. The rich structure of more advanced schemes like HIBE and ABE, on the other hand, appears to doom using selective security proof owing to exponential security loss, as one must estimate a partition that preserves the partial ordering provided by the powers allocated to the individual keys.
Meanwhile, progress on attributed-based encryption systems slowed to a halt at selective security in the standard model. With the Sahai and Waters introduction of attribute-based systems [7], the subsequent ABE schemes in [11–15] only offered security proofs in the selective model.
Waters developed the dual system encryption approach [10] in response to the relative stagnation in proving methodology for functional encryption systems. Under conventional assumptions, his early work produced fully secure and efficient IBE and HIBE systems. Lewko and waters presented a more elegant implementation of dual system encryption in [16], allowing for even more efficiency gains in the context of HIBE. Lewko et al. [17] expanded the dual system encryption methods to obtain the standard model's first fully secure ABE systems. Okamoto and Takashima [18] used the basic and relatively conventional Decisional Linear Assumption (DLIN) to reach comparable results in a follow-up study. We will continue to explore the dual system encryption methodology in subsequent works [16, 19, 20] to provide a clear insight into a stronger security proof.
1.2.4 Dual System of Encryption
These works investigate the rich structure of composite order bilinear groups, which differs from prime order bilinear groups in several ways, most notably the inclusion of orthogonal subgroups of coprime orders. A composite order bilinear group has the structure of a direct product of prime order subgroups up to isomorphism so that each group member can decompose as the product of components from the individual subgroups. However, computing such a decomposition becomes challenging when the group order is hard to factor. Because of their orthogonality, these subgroups can serve as independent spaces, allowing a system designer to employ them in various ways without compromising their validity. The idea behind security is that these subgroups are virtually inseparable: given a random group element, determining which subgroups contribute non-trivial components should be difficult.
Although composite order bilinear groups offer appealing properties, it would be preferable to derive the same functionality and strong guarantees from other assumptions, particularly the DLIN in prime order bilinear groups. Working with prime order bilinear groups rather than composite order bilinear groups has various advantages. First, we can achieve security using the more common decisional linear assumption. Second, we can build considerably more efficient systems with the same security standards. This is because the difficulties of factoring the group order are often used to provide security in composite order groups. This requires using large group orders, which in turn slows down pairing computations significantly.
Okamoto and Takashima developed the framework of dual pairing vector spaces in prime order bilinear groups [21, 22]. They observed that dual pairing vector spaces could be used to implement the same proof techniques under the standard Decisional Linear Assumption [18, 23]. Working in prime order groups is advantageous since the group orders can be much smaller, so pairing computations can be much faster. In [24], Lewko further developed the connection between the dual pairing vector space framework based on the prior approach in the composite order setting. Their efforts have yielded a practical understanding of how to move dual system encryption proofs between composite and prime order settings. However, the reliance on q-type assumptions (size assumptions that grow with some parameter q) is a disadvantage of the proving technique provided in [24]. Many q-type assumptions are known to become stronger as q increases [25], and such dynamic and complex assumptions are not well understood in general). Obiri et al. [26] have recently improved the methodologies for establishing adaptive security for attribute-based encryption using static assumptions like the decisional linear assumption and the three-party Diffie–Hellman assumption. The advantage of the scheme in [26] is that it allows arbitrary attribute reuse in the access policy without increasing the size of the ciphertext proportion to the number of times an attribute appears in the access policy. However, because the approach depends on the dual vector subspace assumption, it necessitates large public parameters to achieve full security. Also, the authors in [27, 28] suggested another method for creating security proofs for the dual system of ABE schemes based on the matrix Diffie–Hellman assumption. This technique has proven to be beneficial because it is more efficient and more compact than dual vector space schemes.
This book focuses on using dual systems of encryption proof to construct adaptive, secure attribute-based encryption. This book provides readers with a thorough overview of the components that go into creating a dual ABE system of encryption proofs in:
Composite bilinear groups
Dual pairing vector space framework (prime order bilinear group)
Matrix pairing framework (prime order bilinear group)
After reading the book, the readers will learn which bilinear groups (composite order or prime order) to use in designing a new cryptographic scheme.
1.2.5 Summary
In this chapter, we covered the concepts of encryption and functional encryption and a brief history of functional encryption. This chapter's purpose is to provide a historical development of how the current technique for creating adaptive security of ABE schemes based on a dual system of encryption in the standard model came to be. We also investigated why ABE schemes were required because previous encryption methods could not provide fine-grained access control over encrypted data. Finally, we also investigated the need to construct an adaptive (fully) secure ABE scheme in prime order groups instead of composite order groups.
References
1
Diffie, W. and Hellman, M.E. (1977). Special feature exhaustive cryptanalysis of the NBS data encryption standard.
Computer
10 (6): 74–84.
2
Simmons, G.J. (1979). Symmetric and asymmetric encryption.
ACM Computing Surveys (CSUR)
11 (4): 305–330.
3
Boonkrong, S. (2021). Public key infrastructure. In:
Authentication and Access Control
, 31–43. Berkeley, CA: Apress.
4
Shamir, A. (1984). Identity-based cryptosystems and signature schemes. In:
Workshop on the Theory and Application of Cryptographic Techniques
, 47–53. Berlin, Heidelberg: Springer-Verlag.
5
Boneh, D. and Franklin, M. (2001). Identity-based encryption from the Weil pairing. In:
Annual International Cryptology Conference
, 213–229. Berlin, Heidelberg: Springer-Verlag.
6
Sulaiman, O.K. and Saripurna, D. (2021). Network security system analysis using access control list (ACL).
IJISTECH (International Journal of Information System & Technology)
5 (2): 192–197.
7
Sahai, A. and Waters, B. (2005). Fuzzy identity-based encryption. In:
Annual International Conference on the Theory and Applications of Cryptographic Techniques
, 457–473. Berlin, Heidelberg: Springer-Verlag.
8
Waters, B. (2005). Efficient identity-based encryption without random oracles. In:
Annual International Conference on the Theory and Applications of Cryptographic Techniques
, 114–127. Berlin, Heidelberg: Springer-Verlag.
9
Boneh, D. and Boyen, X. (2004). Secure identity based encryption without random oracles. In:
Annual International Cryptology Conference
, 443–459. Berlin, Heidelberg: Springer-Verlag.
10
Waters, B. (2009). Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions. In:
Annual International Cryptology Conference
, 619–636. Berlin, Heidelberg: Springer-Verlag.
11
Cheung, L. and Newport, C. (2007). Provably secure ciphertext policy ABE.
Proceedings of the 14th ACM Conference on Computer and Communications Security
, 456–465.
12
Goyal, V., Pandey, O., Sahai, A., and Waters, B. (2006). Attribute-based encryption for fine-grained access control of encrypted data.
Proceedings of the 13th ACM Conference on Computer and Communications Security
, 89–98.
13
Goyal, V., Jain, A., Pandey, O., and Sahai, A. (2008). Bounded ciphertext policy attribute based encryption. In:
International Colloquium on Automata, Languages, and Programming
, 579–591. Berlin, Heidelberg: Springer-Verlag.
14
Ostrovsky, R., Sahai, A., and Waters, B. (2007). Attribute-based encryption with non-monotonic access structures.
Proceedings of the 14th ACM Conference on Computer and Communications Security
, 195–203.
15
Waters, B. (2011). Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In:
International Workshop on Public Key Cryptography
, 53–70. Berlin, Heidelberg: Springer-Verlag.
16
Lewko, A. and Waters, B. (2010). New techniques for dual system encryption and fully secure HIBE with short ciphertexts. In:
Theory of Cryptography Conference
, 455–479. Berlin, Heidelberg: Springer-Verlag.
17
Lewko, A., Okamoto, T., Sahai, A. et al. (2010). Fully secure functional encryption: attribute-based encryption and (hierarchical) inner product encryption. In:
Annual International Conference on the Theory and Applications of Cryptographic Techniques
, 62–91. Berlin, Heidelberg: Springer-Verlag.
18
Okamoto, T. and Takashima, K. (2010). Fully secure functional encryption with general relations from the decisional linear assumption. In:
Annual Cryptology Conference
, 191–208. Berlin, Heidelberg: Springer-Verlag.
19
Lewko, A., Rouselakis, Y., and Waters, B. (2011). Achieving leakage resilience through dual system encryption. In:
Theory of Cryptography Conference
, 70–88. Berlin, Heidelberg: Springer-Verlag.
20
Lewko, A. and Waters, B. (2011). Decentralizing attribute-based encryption. In:
Annual International Conference on the Theory and Applications of Cryptographic Techniques
, 568–588. Berlin, Heidelberg: Springer-Verlag.
21
Okamoto, T. and Takashima, K. (2008). Homomorphic encryption and signatures from vector decomposition. In:
International Conference on Pairing-Based Cryptography
, 57–74. Berlin, Heidelberg: Springer-Verlag.
22
Okamoto, T. and Takashima, K. (2009). Hierarchical predicate encryption for inner-products. In:
International Conference on the Theory and Application of Cryptology and Information Security
, 214–231. Berlin, Heidelberg: Springer-Verlag.
23
Okamoto, T. and Takashima, K. (2013). Decentralized attribute-based signatures. In:
International Workshop on Public Key Cryptography
, 125–142. Berlin, Heidelberg: Springer-Verlag.
24
Lewko, A. (2012). Tools for simulating features of composite order bilinear groups in the prime order setting. In:
Annual International Conference on the Theory and Applications of Cryptographic Techniques
, 318–335. Berlin, Heidelberg: Springer-Verlag.
25
Cheon, J.H. (2006). Security analysis of the strong Diffie-Hellman problem. In:
Annual International Conference on the Theory and Applications of Cryptographic Techniques
, 1–11. Berlin, Heidelberg: Springer-Verlag.
26
Obiri, I.A., Xia, Q., Xia, H. et al. (2020). A fully secure KP-ABE scheme on prime-order bilinear groups through selective techniques.
Security and Communication Networks
, 2020: Article ID 8869057.
27
Kowalczyk, L. and Wee, H. (2020). Compact adaptively secure ABE for NC1 from k-Lin.
Journal of Cryptology
33 (3): 954–1002.
28
Tomida, J., Kawahara, Y., and Nishimaki, R. (2021). Fast, compact, and expressive attribute-based encryption.
Designs, Codes and Cryptography
89 (11): 2577–2626.
2Mathematical Background
2.1 Group Theory
Groups are one of the fundamental concepts in modern algebra. A group is a set together with an operation that combines two elements to form a third element which contains an identity element and inverse and satisfies certain natural properties such as associativity, cancellation, and solvability properties. In the field of cryptography, group theory is the most practical approach to take when constructing encryption systems. When it comes to cryptographic schemes that are based on integers, group theory is absolutely necessary for selecting prime numbers and the corresponding inverses for the purpose of scheme construction. In particular with the construction of Rivest–Shamir–Adleman (RSA) encryption, the theory is necessary for computing inverses in order to generate users' public and private information. This is because RSA encryption thrives on public and private keys.
2.1.1 Law of Composition
Let represent a set. A map: is referred to as a law of composition. For all the elements the image of the pair under the law of composition will be represented as . If a multiplicative notation is used, we also write .
Let be a set and denotes the law of composition. The law of composition is called associative if holds for all . It is called commutative if holds for all .
2.1.2 Groups
Definition 2.1 Let represents any non-empty set and: be a law of composition. We say that forms a group in terms of the operation, if all the following conditions are satisfied:
Closure
: For elements , .
Existence of identity
: There exists an element such that for all .
Associativity
: For all elements , we have .
Existence of inverse
: For an element , there exist such that .
Cancellation
: For all elements , if or if , then .
Solvability
: For all elements , there exists an element with , and an element with .
Example 2.1
is a group with identity element 0.
is not a group. Only 1 and are invertible.
Definition 2.2 We say a group is an Abelian group if ; else, the group is non-Abelian group, i.e. such that .
Definition 2.3 The order of group, represented by , is the smallest positive integer (if it exists) such that (identity element of ). If such an integer does not exist, the element is said to have infinite order. To compute the order of an element in a group , simply find the sequence until the first time the identity is obtain. If identity is never obtained, the order of becomes infinite.
Example 2.2
In the order of 0 is 1 and the order of any non-zero element is . For any non-zero element ‘
a
’ (where ‘
a
’ is an integer that is not equal to 0), the order is infinite (∞). This is because, in the additive group of integers, there is no positive integer ‘’ such that , except when ‘
a
’ is 0. In other words, no matter how many times you add a non-zero integer ‘
a
’ to itself, you will never reach the identity element 0.
For and the orders are as follows:
As shown in Table 2.1, the smallest positive integer with is the order of an element , denoted by . If there is no such , is set to . Torsion elements are group elements with a finite order. The cardinality of a group is defined by its order, . If a group has prime order, the group is cyclic.
2.1.3 Subgroups
Let a group have the operation with an identity element , where the inverse of an element is denoted . A subgroup of is a nonempty subset of with two properties:
if are in , then is in ; and
if is in , so is .
Table 2.1 Order of groups.
0
1
–
1
6
1
2
3
–
3
2
–
4
3
–
5
6
2
Definition 2.4 A subset of a group is considered to be a subgroup of if itself forms a group under the operation of . If is a subgroup of , then it is represented by . Further to show that is a proper subgroup of (proper in the sense of containment), we use . The subset of is trivially a subgroup of .
In other words, is a subset of , which is closed under multiplication and inverse.
2.1.4 Homomorphisms
Homomorphisms are maps that preserve the structure of two algebraic structures. They allow for the investigation of the interaction between various structures. A homomorphism for a group is defined as follows:
Definition 2.5 A homomorphism between two groups is a map with , where . If is bijective, we call an isomorphism.
A group homomorphism is a map that retains the operation between two groups. This implies that the group homomorphism maps the first group's identity element to the second group's identity element and the inverse of a first-group element to the inverse of its image.
The neutral element, , is preserved by group homomorphisms. Monomorphism refers to an injective group homomorphism. Epimorphism is when a group homomorphism is subjective. A bijective group homomorphism is an isomorphism. A group homomorphism that maps a group to itself is called endomorphism. Automorphism is an isomorphism that is also an endomorphism. If groups have an isomorphism between two groups, they are called isomorphic group and we write .
2.1.5 Cyclic Group
A cyclic group is a collection of elements in which each member is a power of a fixed element. As a result, a cyclic group can be generated by a fixed element , with each member in having the form for some integer .
Definition 2.6 A group is a cyclic if
The order of is the smallest positive integer such that . If there exists no positive integer such that , then has infinite order. In the case of an abelian group with operation, 0 is the identity element, the order of the positive integer has . For an element , the set of elements generated by is denoted by and comprises all elements of the form for all . This set is a subgroup of .
Example 2.3
The group is cyclic and generated by 1.
The group is not cyclic and is generated by the infinitely large set .
Theorem 2.1 For an element , . If is a generator of cyclic group (also denoted as ) then is also a generator of that group.
Proof: Let such that for some . Then . Since is arbitrary, . Then, it implies that . Hence, we have .
Example 2.4 A single element generates a cyclic group. Here are two motivating examples:
Addition can form a group of numbers generated by 1. By this, we mean that element 1 can be combined with itself to generate the complete set of integers under the group operation and inverses. If is a positive integer, is acyclic group of order generated by 1. The element 1 generates , since In other words, by adding 1 to itself, it will eventually get back to 0. The element 3 also generates :
