logo资料库

Introduction to Security Reduction.pdf

第1页 / 共262页
第2页 / 共262页
第3页 / 共262页
第4页 / 共262页
第5页 / 共262页
第6页 / 共262页
第7页 / 共262页
第8页 / 共262页
资料共262页,剩余部分请下载后查看
Preface
Acknowledgements
Contents
Chapter 1 Guide to This Book
Chapter 2 Notions, Definitions, and Models
2.1 Digital Signatures
2.2 Public-Key Encryption
2.3 Identity-Based Encryption
2.4 Further Reading
Chapter 3 Foundations of Group-Based Cryptography
3.1 Finite Fields
3.1.1 Definition
3.1.2 Field Operations
3.1.3 Field Choices
3.1.4 Computations over a Prime Field
3.2 Cyclic Groups
3.2.1 Definitions
3.2.2 Cyclic Groups of Prime Order
3.2.3 Group Exponentiations
3.2.4 Discrete Logarithms
3.2.5 Cyclic Groups from Finite Fields
3.2.6 Group Choice 1: Multiplicative Groups
3.2.7 Group Choice 2: Elliptic Curve Groups
3.2.8 Computations over a Group
3.3 Bilinear Pairings
3.3.1 Symmetric Pairing
3.3.2 Asymmetric Pairing
3.3.3 Computations over a Pairing Group
3.4 Hash Functions
3.5 Further Reading
Chapter 4 Foundations of Security Reduction
4.1 Introduction to Basic Concepts
4.1.1 Mathematical Primitives and Superstructures
4.1.2 Mathematical Problems and Problem Instances
4.1.3 Cryptography, Cryptosystems, and Schemes
4.1.4 Algorithm Classification 1
4.1.5 Polynomial Time and Exponential Time
4.1.6 Negligible and Non-negligible
4.1.7 Insecure and Secure
4.1.8 Easy and Hard
4.1.9 Algorithm Classification 2
4.1.10 Algorithms in Cryptography
4.1.11 Hard Problems in Cryptography
4.1.12 Security Levels
4.1.13 Hard Problems and Hardness Assumptions
4.1.14 Security Reductions and Security Proofs
4.2 An Overview of Easy/Hard Problems
4.2.1 Computational Easy Problems
4.2.2 Computational Hard Problems
4.2.3 Decisional Easy Problems
4.2.4 Decisional Hard Problems
4.2.5 How to Prove New Hard Problems
4.2.6 Weak Assumptions and Strong Assumptions
4.3 An Overview of Security Reduction
4.3.1 Security Models
4.3.2 Weak Security Models and Strong Security Models
4.3.3 Proof by Testing
4.3.4 Proof by Contradiction
4.3.5 What Is Security Reduction?
4.3.6 Real Scheme and Simulated Scheme
4.3.7 Challenger and Simulator
4.3.8 Real Attack and Simulation
4.3.9 Attacks and Hard Problems
4.3.10 Reduction Cost and Reduction Loss
4.3.11 Loose Reduction and Tight Reduction
4.3.12 Security Level Revisited
4.3.13 Ideal Security Reduction
4.4 An Overview of Correct Security Reduction
4.4.1 What Should Bob Do?
4.4.2 Understanding Security Reduction
4.4.3 Successful Simulation and Indistinguishable Simulation
4.4.4 Failed Attack and Successful Attack
4.4.5 Useless Attack and Useful Attack
4.4.6 Attack in Simulation
4.4.7 Successful/Correct Security Reduction
4.4.8 Components of a Security Proof
4.5 An Overview of the Adversary
4.5.1 Black-Box Adversary
4.5.2 What Is an Adaptive Attack?
4.5.3 Malicious Adversary
4.5.4 The Adversary in a Toy Game
4.5.5 Adversary's Successful Attack and Its Probability
4.5.6 Adversary's Computational Ability
4.5.7 The Adversary's Computational Ability in a Reduction
4.5.8 The Adversary in a Reduction
4.5.9 What the Adversary Knows
4.5.10 What the Adversary Never Knows
4.5.11 How to Distinguish the Given Scheme
4.5.12 How to Generate a Useless Attack
4.5.13 Summary of Adversary
4.6 An Overview of Probability and Advantage
4.6.1 Definitions of Probability
4.6.2 Definitions of Advantage
4.6.3 Malicious Adversary Revisited
4.6.4 Adaptive Choice Revisited
4.6.5 Useless, Useful, Loose, and Tight Revisited
4.6.6 Important Probability Formulas
4.7 An Overview of Random and Independent
4.7.1 What Are Random and Independent?
4.7.2 Randomness Simulation with a General Function
4.7.3 Randomness Simulation with a Linear System
4.7.4 Randomness Simulation with a Polynomial
4.7.5 Indistinguishable Simulation and Useful Attack Together
4.7.6 Advantage and Probability in Absolutely Hard Problems
4.8 An Overview of Random Oracles
4.8.1 Security Proof with Random Oracles
4.8.2 Hash Functions vs Random Oracles
4.8.3 Hash List
4.8.4 How to Program Security Reductions with Random Oracles
4.8.5 Oracle Response and Its Probability Analysis
4.8.6 Summary of Using Random Oracles
4.9 Security Proofs for Digital Signatures
4.9.1 Proof Structure
4.9.2 Advantage Calculation
4.9.3 Simulatable and Reducible
4.9.4 Simulation of Secret Key
4.9.5 Partition
4.9.6 Tight Reduction and Loose Reduction Revisited
4.9.7 Summary of Correct Security Reduction
4.10 Security Proofs for Encryption Under Decisional Assumptions
4.10.1 Proof Structure
4.10.2 Classification of Ciphertexts
4.10.3 Classification of the Challenge Ciphertext
4.10.4 Simulation of the Challenge Ciphertext
4.10.5 Advantage Calculation 1
4.10.6 Probability PT of Breaking the True Challenge Ciphertext
4.10.7 Probability PF of Breaking the False Challenge Ciphertext
4.10.8 Advantage Calculation 2
4.10.9 Definition of One-Time Pad
4.10.10 Examples of One-Time Pad
4.10.11 Analysis of One-Time Pad
4.10.12 Simulation of Decryption
4.10.13 Simulation of Challenge Decryption Key
4.10.14 Probability Analysis for PF
4.10.15 Examples of Advantage Results for AFK and AFI
4.10.16 Advantage Calculation 3
4.10.17 Summary of Correct Security Reduction
4.11 Security Proofs for Encryption Under Computational Assumptions
4.11.1 Random and Independent Revisited
4.11.2 One-Time Pad Revisited
4.11.3 Solution to Hard Problem Revisited
4.11.4 Simulation of Challenge Ciphertext
4.11.5 Proof Structure
4.11.6 Challenge Ciphertext and Challenge Hash Query
4.11.7 Advantage Calculation
4.11.8 Analysis of No Advantage
4.11.9 Requirements of Decryption Simulation
4.11.10 An Example of Decryption Simulation
4.11.11 Summary of Correct Security Reduction
4.12 Simulatable and Reducible with Random Oracles
4.12.1 H-Type: Hashing to Group
4.12.2 C-Type: Commutative
4.12.3 I-Type: Inverse of Group Exponent
4.13 Examples of Incorrect Security Reductions
4.13.1 Example 1: Distinguishable
4.13.2 Example 2: Useless Attack by Public Key
4.13.3 Example 3: Useless Attack by Signature
4.14 Examples of Correct Security Reductions
4.14.1 One-Time Signature with Random Oracles
4.14.2 One-Time Signature Without Random Oracles
4.14.3 One-Time Signature with Indistinguishable Partition
4.15 Summary of Concepts
4.15.1 Concepts Related to Proof
4.15.2 Preliminaries and Proof by Contradiction
4.15.3 Security Reduction and Its Difficulty
4.15.4 Simulation and Its Requirements
4.15.5 Towards a Correct Security Reduction
4.15.6 Other Confusing Concepts
Chapter 5 Digital Signatures with Random Oracles
5.1 BLS Scheme
5.2 BLS+ Scheme
5.3 BLS# Scheme
5.4 BBRO Scheme
5.5 ZSS Scheme
5.6 ZSS+ Scheme
5.7 ZSS# Scheme
5.8 BLSG Scheme
Chapter 6 Digital Signatures Without Random Oracles
6.1 Boneh-Boyen Scheme
6.2 Gentry Scheme
6.3 GMS Scheme
6.4 Waters Scheme
6.5 Hohenberger-Waters Scheme
Chapter 7 Public-Key Encryption with Random Oracles
7.1 Hashed ElGamal Scheme
7.2 Twin Hashed ElGamal Scheme
7.3 Iterated Hashed ElGamal Scheme
7.4 Fujisaki-Okamoto Hashed ElGamal Scheme
Chapter 8 Public-Key Encryption Without Random Oracles
8.1 ElGamal Scheme
8.2 Cramer-Shoup Scheme
Chapter 9 Identity-Based Encryption with Random Oracles
9.1 Boneh-Franklin Scheme
9.2 Boneh-BoyenRO Scheme
9.3 Park-Lee Scheme
9.4 Sakai-Kasahara Scheme
Chapter 10 Identity-Based Encryption Without Random Oracles
10.1 Boneh-Boyen Scheme
10.2 Boneh-Boyen+ Scheme
10.3 Waters Scheme
10.4 Gentry Scheme
References
FuchunGuo· WillySusilo· YiMu Introduction to Security Reduction
Introduction to Security Reduction
Fuchun Guo • Willy Susilo • Yi Mu Introduction to Security Reduction
Fuchun Guo School of Computing Information Technology & University of Wollongong Wollongong, New South Wales, Australia Yi Mu School of Computing Information Technology & University of Wollongong Wollongong, New South Wales, Australia Willy Susilo School of Computing Information Technology & University of Wollongong Wollongong, New South Wales, Australia ISBN 978-3-319-93049-7 (eBook) ISBN 978-3-319-93048-0 https://doi.org/10.1007/978-3-319-93049-7 Library of Congress Control Number: 2018946564 © Springer International Publishing AG, part of Springer Nature 2018 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. Printed on acid-free paper This Springer imprint is published by the registered company Springer International Publishing AG part of Springer Nature. The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
To my lovely wife Yizhen, two adorable sons John and Kevin, and my kindly mother Suhua. To the memory of my father Yongming. –Fuchun Guo To my wife Aurelia and our beloved son Jayden, without whom this work will never be accomplished. –Willy Susilo To my family! –Yi Mu
Preface Security reduction is a very popular approach for proving security in public-key cryptography. With security reduction, roughly speaking, we can show that breaking a proposed scheme is as difficult as solving a mathematical hard problem. However, how to program a correct security reduction using an adversary’s adaptive attack is rather complicated. The reason is that there is no universal security reduction for all proposed schemes. Security reductions given in cryptographic research papers are often hard for be- ginners to fully comprehend. To aid the beginners, some cryptography textbooks have illustrated how to correctly program security reductions with simpler exam- ples. However, security reductions mentioned in research papers and previous text- books are usually for specific schemes. The difference in security reductions for different schemes leads to confusion for the beginners. There is a need for a book that systematically introduces how to correctly program a security reduction for a cryptosystem, not for a specific scheme. With this in mind, we wrote this book, which we hope will help the reader understand how to correctly program a security reduction. The contents of this book, especially the foundations of security reductions, are based on our understanding and experience. The reader might find that the expla- nations of concepts are slightly different from those in other sources, because we have added some “condiments” to help the reader understand these concepts. For example, in a security reduction, the adversary is not a black-box adversary but a malicious adversary who has unbounded computational power. We thought this book would be completed within one year, but we underesti- mated its difficulty. It has taken more than four years to complete the writing of this book. There must still be errors that have not yet been found. We welcome any comments and suggestions. University of Wollongong, Australia May 2018 Fuchun Guo, Willy Susilo, and Yi Mu vii
Acknowledgements We finally accomplished something which is meaningful and useful for our research society. Our primary goal is to make confusing concepts of security reductions van- ish, and to provide a clear guide on how to program correct security reductions. Here, we would like to record some of our major milestones as well as to acknowl- edge several people who have helped us complete this book. The time that we started to write this book can be traced back to the second half of 2013, after Dr. Fuchun Guo received his PhD degree in July of that year. At that time, being a research assistant, Fuchun was invited to co-supervise Professor Willy Susilo and Professor Yi Mu’s PhD students at the University of Wollongong, Aus- tralia. Fuchun’s primary task was to help Willy and Yi train PhD students with very little background in public-key cryptography. It is evident that there is a big gap between savvy researchers and PhD students just starting on their PhD journeys. Furthermore, we found it was really ineffective for our students to read papers by themselves to understand security proofs and some tricky methods in security reduc- tions. How to quickly train our students remains an elusive problem as we have to repeat the interactions with each individual student day by day. We collected some basic but important knowledge that all our students must master in their studies to conduct research in public-key cryptography. Then we decided to write this book to- gether to help our students. Hence, the original motivation of writing this book was to save our time in the training of our students. We do hope that this book will also benefit others who want to start their research careers in public-key cryptography, or others who want to study the techniques used in programming correct security reductions. The first version of this book was completed in April 2015. In that version, Chap- ter 4 had only about 50 pages. That version was rather incomprehensible with a lot of logic and consistency problems. Then, we started to polish the book, which was completed in August 2017. It took 28 months to clarify many important concepts that are contained in this book. We patiently crafted Chapter 4 to ensure that all con- cepts and knowledge are presented clearly and are easy to understand. Originally, we either did not fully understand many concepts or did not clearly know how to explain them. A significant amount of time was used to think about how to explain ix
x Acknowledgements each concept and exemplify it with a simple, yet clear, example. We were very pas- sionate in completing this book without thinking about any time constraints. The external proofreading by our students was started in September 2017 and completed in March 2018. More than ten PhD students were involved in the proofreading. We believe this was an invaluable experience for us, which paints a very nice story to share and remember. This book would never have been completed without the hard work of our students. At the early stage of this book writing, we received a lot of feedback from the process of training our students. This invaluable experience helped us see which concepts are hard for students to understand and how to clearly explain these. We are indebted to our colleagues and students: Rongmao Chen, Jianchang Lai, Peng Jiang, Nan Li, and Yinhao Jiang. They provided insightful feedback and thoughts when we trained them in public-key cryptography. We can now proudly say that these people have now completed their PhD studies and they have mastered the required skills as independent researchers in public-key cryptography, thanks to the information and training that are provided in this book. When we completed the writing of this book, we decided to invite our PhD stu- dents to read it first. Without too much surprise, our students still found many con- fusing concepts and unclear knowledge points. They provided a lot of invaluable comments and advice that have been used to improve the quality of this book. In particular, more than 20 pages were added to Chapter 4 to improve the clarity of this important chapter. Specifically, we would like to thank these people: Jianchang Lai, Zhen Zhao, Ge Wu, Peng Jiang, Zhongyuan Yao, Tong Wu, and Shengming Xu for their helpful advice and feedback. The first manuscript given to students for proofreading was full of typos and grammatical errors. We would like to thank the following people for their help in improving this book: Jianchang Lai, Fatemeh Rezaeibagha, Zhen Zhao, Ge Wu, Peng Jiang, Xueqiao Liu, Zhongyuan Yao, Tong Wu, Shengming Xu, Binrui Zhu, Ke Wang, Yannan Li, and Yanwei Zhou. We would also like to thank all authors of published references that have been cited in this book, especially those authors whose schemes have been used as exam- ples. We merely reorganized this knowledge and put it together with our understand- ing and our logic. We would also like to thank the Springer editor Ronan Nugent and the copy-editors of Springer, who gave us a lot of insightful comments and advice that have indeed improved the quality and clarity of this book. Last but not least, we would like to thank our families who have always been very supportive. We spent so much time in editing and correcting this book, and without their patience, it would have been impossible to complete. Thank you. Finally, we hope that the reader will find that this book is useful. University of Wollongong, Australia May 2018 Fuchun Guo, Willy Susilo, and Yi Mu
分享到:
收藏