第1页 / 共262页
第2页 / 共262页
第3页 / 共262页
第4页 / 共262页
第5页 / 共262页
第6页 / 共262页
第7页 / 共262页
第8页 / 共262页
Introduction to Security Reduction.pdf
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
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
