狠狠撸

狠狠撸Share a Scribd company logo
Digital signatures
What is a digital signature
? A digital signature allows the holder of the secret key (the signing key)
to sign a document
? Everyone who knows the verification key can verify that the signature
is valid (correctness)
? No one can forge a signature even given the verification key even
though he is given a signature
Structure of digital signature
? ??? 1? → (??, ??)
? ?????? ? → ???
? ????? ?, ??? → {0,1}
Structure of digital signature scheme (DSS)
? ??? 1? → (??, ??)
? ?????? ? → ???
? ????? ?, ??? → {0,1}
? Correctness
? ????? ?, ??????(?) = 1
? Unforgeability
? To be continued
DSS VS MAC
? ??? 1? → (??, ??)
? ?????? ? → ???
? ????? ?, ??? → {0,1}
? ??? 1? → ?
? ???? ? → ?
? v??? ?, ? → {0,1}
Mac forgery game
M ← {}
?′
?′
k ∈? 0,1 ?
(?, ?)
Wins if
? ? ? ?
? ?????? ?, ? = 1
?′ ← ????(?′)
M ← ? ∪ {?′} Repeat as many times
as the adversary wants
Signature forgery game
M ← {}
?′
???′
??, ?? ← ???(1?
)
(?, ???)
Wins if
? ? ? ?
? ???????? ?, ??? = 1
???′ ← ??????(?′)
M ← ? ∪ {?′} Repeat as many times
as the adversary wants
??
Definition of signature scheme
? Correctness:
? Pr ????? ?, ?????? ? = 1 ??, ?? ← ??? 1? = 1
? Unforgeability
? For all PPT adversary ?, there exists negligible function ?,
? Pr ? ???? ??? ????????? ??????? ???? ≤ ?(?)
Relation between macs and signatures
? Every signature scheme is a message authentication code.
? A mac scheme is not necessarily a signature.
? Without the key, it may be impossible to verify a mac.
Signatures are expensive
? They require public-key operations for each signature you wish to do.
? Hash functions are relatively cheap
Hash and sign
? Let (???′, ????′, ??????′) be a signature scheme and let ? be a
collision resistant hash function, then the following
? ??? 1? ? ???′ 1?
? ?????? ? ? ??????
′
(? ? )
? ???????? ?, ??? ? ????????
′
? ? , ??? = 1
Security of hash and sign
? Let (???′, ????′, ??????′) be a signature scheme and let ? be a collision resistant hash function, then the
following
? ??? 1?
? ???′
1?
? ?????? ? ? ??????
′
(? ? )
? ???????? ?, ??? ? ??????′
? ? , ??? = 1
? Essentially the same proof as hash and mac
? Breaking security of this scheme means
? Finding a collision
? Finding a signature on an unsigned message
Interesting property of plaintext RSA
? ??, ?? ← ?????? 1? ? ????? ????? ? = ?
? Due to the fact that ?? ? = ?? ?
= ???
RSA signature scheme
? Let (??????, ???, ???) denote the RSA encryption scheme
? ??? 1? ? {?? ← ??′, ?? ← ?? ∣ ??′, ??′ ← ?????? 1? }
? ?????? ? ? ????? ?
? ???????? ?, ??? ? ????? ??? = ?
Insecure RSA signature scheme
? ??? 1? ? { ?? ← ??, ?? ← ??′ ∣ ??′, ??′ ← ?????? 1? }
? ?????? ? ? ????? ?
? ???????? ?, ?????? ? = ????? ????? ?
? ????? ????? ? = ?? ?
= ???? = ?
Secure RSA signature scheme
? Assumptions
? Random oracle ? (Hash function modeled as a random oracle
? ? = ?? where ?, ? are prime
? ??? 1?
? { ?? ← ??, ?? ← ??′ ∣ ??′
, ??′
← ?????? 1?
}
? ?????? ? ? ????? ?(?)
? ???????? ?, ?????? ? ? ? ? = ????? ????? ?(?)
? ????? ????? ?(?) = (?(?))? ?
??? ?
? (?(?))? ?
??? ? = ?(?)??? ??? ?(?)
(??? ?) = ?(?)
Schnorr signature scheme
? Based on
? Group G
? Generator ? for G
? Random oracle ?
? Discrete logarithm
Schnorr signature scheme
? Requirement: Group ?, ? = ?, generator ?, random oracle ?
? ??? 1?
? ?? ∈? ?
? ?? ← ???
? ????????(?, ???)
? ?, ? ← ???
? u ← ?? ? ????
? Output ? ?, ? = ?
? ?????? ?
? ? ∈? ?|?|
? ? ← ??
? ? ← ?(?, ?)
? ? ← ? ? ?? + ? (??? ?)
? Output (?, ?)

More Related Content

Similar to module_14_digital_signatures.pptx (17)

A compact zero knowledge proof to restrict message space in homomorphic encry...
A compact zero knowledge proof to restrict message space in homomorphic encry...A compact zero knowledge proof to restrict message space in homomorphic encry...
A compact zero knowledge proof to restrict message space in homomorphic encry...
MITSUNARI Shigeo
?
[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...
[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...
[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...
PROIDEA
?
WEEK-2 (1).pdfdccccccccccccccccccccccccccccccccccc
WEEK-2 (1).pdfdcccccccccccccccccccccccccccccccccccWEEK-2 (1).pdfdccccccccccccccccccccccccccccccccccc
WEEK-2 (1).pdfdccccccccccccccccccccccccccccccccccc
deepak123mastermind
?
暗认本読书会11
暗认本読书会11暗认本読书会11
暗认本読书会11
MITSUNARI Shigeo
?
尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化
尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化
尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化
MITSUNARI Shigeo
?
Homomorphic Encryption
Homomorphic EncryptionHomomorphic Encryption
Homomorphic Encryption
G?ktu? Serez
?
Cryptography and PKI
Cryptography and PKICryptography and PKI
Cryptography and PKI
Rabei Hassan
?
Smart City Lecture 5 - Introduction to Encryption
Smart City Lecture 5 - Introduction to EncryptionSmart City Lecture 5 - Introduction to Encryption
Smart City Lecture 5 - Introduction to Encryption
Peter Waher
?
Face verification techniques: how to speed up dataset creation
Face verification techniques: how to speed up dataset creationFace verification techniques: how to speed up dataset creation
Face verification techniques: how to speed up dataset creation
Deep Learning Italia
?
Hash functions
Hash functionsHash functions
Hash functions
sameezahur
?
apidays LIVE Australia 2020 - WT* is JWT? by Maciej Treder
apidays LIVE Australia 2020 -  WT* is JWT? by Maciej Trederapidays LIVE Australia 2020 -  WT* is JWT? by Maciej Treder
apidays LIVE Australia 2020 - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE New York - WT* is JWT? by Maciej Treder
apidays LIVE New York -  WT* is JWT? by Maciej Trederapidays LIVE New York -  WT* is JWT? by Maciej Treder
apidays LIVE New York - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE Hong Kong - WT* is JWT? by Maciej Treder
apidays LIVE Hong Kong - WT* is JWT? by Maciej Trederapidays LIVE Hong Kong - WT* is JWT? by Maciej Treder
apidays LIVE Hong Kong - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE LONDON - WT* is JWT? by Maciej Treder
apidays LIVE LONDON - WT* is JWT? by Maciej Trederapidays LIVE LONDON - WT* is JWT? by Maciej Treder
apidays LIVE LONDON - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE Paris - WT* is JWT? by Maciej Treder
apidays LIVE Paris - WT* is JWT? by Maciej Trederapidays LIVE Paris - WT* is JWT? by Maciej Treder
apidays LIVE Paris - WT* is JWT? by Maciej Treder
apidays
?
Cs166 mynote
Cs166 mynoteCs166 mynote
Cs166 mynote
Kaya Ota
?
Recover A RSA Private key from a TLS session with perfect forward secrecy
Recover A RSA Private key from a TLS session with perfect forward secrecyRecover A RSA Private key from a TLS session with perfect forward secrecy
Recover A RSA Private key from a TLS session with perfect forward secrecy
Priyanka Aash
?
A compact zero knowledge proof to restrict message space in homomorphic encry...
A compact zero knowledge proof to restrict message space in homomorphic encry...A compact zero knowledge proof to restrict message space in homomorphic encry...
A compact zero knowledge proof to restrict message space in homomorphic encry...
MITSUNARI Shigeo
?
[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...
[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...
[CONFidence 2016] Marco Ortisi - Recover a RSA private key from a TLS session...
PROIDEA
?
WEEK-2 (1).pdfdccccccccccccccccccccccccccccccccccc
WEEK-2 (1).pdfdcccccccccccccccccccccccccccccccccccWEEK-2 (1).pdfdccccccccccccccccccccccccccccccccccc
WEEK-2 (1).pdfdccccccccccccccccccccccccccccccccccc
deepak123mastermind
?
尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化
尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化
尝颈蹿迟别诲-贰濒骋补尘补濒暗号を用いた任意関数演算の二者间秘密计算プロトコルの尘补濒颈肠颈辞耻蝉モデルにおける効率化
MITSUNARI Shigeo
?
Homomorphic Encryption
Homomorphic EncryptionHomomorphic Encryption
Homomorphic Encryption
G?ktu? Serez
?
Smart City Lecture 5 - Introduction to Encryption
Smart City Lecture 5 - Introduction to EncryptionSmart City Lecture 5 - Introduction to Encryption
Smart City Lecture 5 - Introduction to Encryption
Peter Waher
?
Face verification techniques: how to speed up dataset creation
Face verification techniques: how to speed up dataset creationFace verification techniques: how to speed up dataset creation
Face verification techniques: how to speed up dataset creation
Deep Learning Italia
?
apidays LIVE Australia 2020 - WT* is JWT? by Maciej Treder
apidays LIVE Australia 2020 -  WT* is JWT? by Maciej Trederapidays LIVE Australia 2020 -  WT* is JWT? by Maciej Treder
apidays LIVE Australia 2020 - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE New York - WT* is JWT? by Maciej Treder
apidays LIVE New York -  WT* is JWT? by Maciej Trederapidays LIVE New York -  WT* is JWT? by Maciej Treder
apidays LIVE New York - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE Hong Kong - WT* is JWT? by Maciej Treder
apidays LIVE Hong Kong - WT* is JWT? by Maciej Trederapidays LIVE Hong Kong - WT* is JWT? by Maciej Treder
apidays LIVE Hong Kong - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE LONDON - WT* is JWT? by Maciej Treder
apidays LIVE LONDON - WT* is JWT? by Maciej Trederapidays LIVE LONDON - WT* is JWT? by Maciej Treder
apidays LIVE LONDON - WT* is JWT? by Maciej Treder
apidays
?
apidays LIVE Paris - WT* is JWT? by Maciej Treder
apidays LIVE Paris - WT* is JWT? by Maciej Trederapidays LIVE Paris - WT* is JWT? by Maciej Treder
apidays LIVE Paris - WT* is JWT? by Maciej Treder
apidays
?
Recover A RSA Private key from a TLS session with perfect forward secrecy
Recover A RSA Private key from a TLS session with perfect forward secrecyRecover A RSA Private key from a TLS session with perfect forward secrecy
Recover A RSA Private key from a TLS session with perfect forward secrecy
Priyanka Aash
?

More from MehediHasanShaon1 (6)

Group 8.pptx
Group 8.pptxGroup 8.pptx
Group 8.pptx
MehediHasanShaon1
?
ccapresentation.ppt
ccapresentation.pptccapresentation.ppt
ccapresentation.ppt
MehediHasanShaon1
?
Jerad Bates - Public Key Infrastructure (1).ppt
Jerad Bates - Public Key Infrastructure (1).pptJerad Bates - Public Key Infrastructure (1).ppt
Jerad Bates - Public Key Infrastructure (1).ppt
MehediHasanShaon1
?
csedigitalsignatureppt-170420041737.pdf
csedigitalsignatureppt-170420041737.pdfcsedigitalsignatureppt-170420041737.pdf
csedigitalsignatureppt-170420041737.pdf
MehediHasanShaon1
?
seminar-151029231027-lva1-app6892.pdf
seminar-151029231027-lva1-app6892.pdfseminar-151029231027-lva1-app6892.pdf
seminar-151029231027-lva1-app6892.pdf
MehediHasanShaon1
?
Digital signature.ppt
Digital signature.pptDigital signature.ppt
Digital signature.ppt
MehediHasanShaon1
?

Recently uploaded (20)

The Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo Guru
The Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo GuruThe Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo Guru
The Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo Guru
kenyoncenteno12
?
CH. 4.pptxt and I will be there in about
CH. 4.pptxt and I will be there in aboutCH. 4.pptxt and I will be there in about
CH. 4.pptxt and I will be there in about
miesoabdela57
?
vnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptx
vnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptxvnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptx
vnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptx
deomom129
?
Boosting MySQL with Vector Search Scale22X 2025.pdf
Boosting MySQL with Vector Search Scale22X 2025.pdfBoosting MySQL with Vector Search Scale22X 2025.pdf
Boosting MySQL with Vector Search Scale22X 2025.pdf
Alkin Tezuysal
?
MTC Supply Chain Management Strategy.pptx
MTC Supply Chain Management Strategy.pptxMTC Supply Chain Management Strategy.pptx
MTC Supply Chain Management Strategy.pptx
Rakshit Porwal
?
Presentation.2 .reversal. reversal. pptx
Presentation.2 .reversal. reversal. pptxPresentation.2 .reversal. reversal. pptx
Presentation.2 .reversal. reversal. pptx
siliaselim87
?
Stasiun kernel pabrik kelapa sawit indonesia
Stasiun kernel pabrik kelapa sawit indonesiaStasiun kernel pabrik kelapa sawit indonesia
Stasiun kernel pabrik kelapa sawit indonesia
fikrimanurung1
?
Cost sheet. with basics and formats of sheet
Cost sheet. with basics and formats of sheetCost sheet. with basics and formats of sheet
Cost sheet. with basics and formats of sheet
supreetk82004
?
Class 3-Workforce profile updated P.pptx
Class 3-Workforce profile updated P.pptxClass 3-Workforce profile updated P.pptx
Class 3-Workforce profile updated P.pptx
angelananalucky
?
原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭
原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭
原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭
taqyed
?
iam free indeed.pptxiam free indeed.pptx
iam free indeed.pptxiam free indeed.pptxiam free indeed.pptxiam free indeed.pptx
iam free indeed.pptxiam free indeed.pptx
muhweziart
?
april 2024 paper 2 ms. english non fiction
april 2024 paper 2 ms. english non fictionapril 2024 paper 2 ms. english non fiction
april 2024 paper 2 ms. english non fiction
omokoredeolasunbomi
?
Data-Models-in-DBMS-An-Overview.pptx.pptx
Data-Models-in-DBMS-An-Overview.pptx.pptxData-Models-in-DBMS-An-Overview.pptx.pptx
Data-Models-in-DBMS-An-Overview.pptx.pptx
hfebxtveyjxavhx
?
stages-of-moral-development-lawrence-kohlberg-pdf-free.pdf
stages-of-moral-development-lawrence-kohlberg-pdf-free.pdfstages-of-moral-development-lawrence-kohlberg-pdf-free.pdf
stages-of-moral-development-lawrence-kohlberg-pdf-free.pdf
esguerramark1991
?
Introduction to database and analysis software’s suitable for.pptx
Introduction to database and analysis software’s suitable for.pptxIntroduction to database and analysis software’s suitable for.pptx
Introduction to database and analysis software’s suitable for.pptx
nabinparajuli9
?
Stasiun kernel pengolahan kelapa sawit indonesia
Stasiun kernel pengolahan kelapa sawit indonesiaStasiun kernel pengolahan kelapa sawit indonesia
Stasiun kernel pengolahan kelapa sawit indonesia
fikrimanurung1
?
加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭
加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭
加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭
taqyed
?
2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM
2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM
2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM
Timothy Spann
?
Analyzing Consumer Spending Trends and Purchasing Behavior
Analyzing Consumer Spending Trends and Purchasing BehaviorAnalyzing Consumer Spending Trends and Purchasing Behavior
Analyzing Consumer Spending Trends and Purchasing Behavior
omololaokeowo1
?
A Relative Information Gain-based Query Performance Prediction Framework with...
A Relative Information Gain-based Query Performance Prediction Framework with...A Relative Information Gain-based Query Performance Prediction Framework with...
A Relative Information Gain-based Query Performance Prediction Framework with...
suchanadatta3
?
The Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo Guru
The Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo GuruThe Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo Guru
The Marketability of Rice Straw Yarn Among Selected Customers of Gantsilyo Guru
kenyoncenteno12
?
CH. 4.pptxt and I will be there in about
CH. 4.pptxt and I will be there in aboutCH. 4.pptxt and I will be there in about
CH. 4.pptxt and I will be there in about
miesoabdela57
?
vnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptx
vnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptxvnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptx
vnptloveeeeeeeeeeeeeeeeeeeeeeeeeeee.pptx
deomom129
?
Boosting MySQL with Vector Search Scale22X 2025.pdf
Boosting MySQL with Vector Search Scale22X 2025.pdfBoosting MySQL with Vector Search Scale22X 2025.pdf
Boosting MySQL with Vector Search Scale22X 2025.pdf
Alkin Tezuysal
?
MTC Supply Chain Management Strategy.pptx
MTC Supply Chain Management Strategy.pptxMTC Supply Chain Management Strategy.pptx
MTC Supply Chain Management Strategy.pptx
Rakshit Porwal
?
Presentation.2 .reversal. reversal. pptx
Presentation.2 .reversal. reversal. pptxPresentation.2 .reversal. reversal. pptx
Presentation.2 .reversal. reversal. pptx
siliaselim87
?
Stasiun kernel pabrik kelapa sawit indonesia
Stasiun kernel pabrik kelapa sawit indonesiaStasiun kernel pabrik kelapa sawit indonesia
Stasiun kernel pabrik kelapa sawit indonesia
fikrimanurung1
?
Cost sheet. with basics and formats of sheet
Cost sheet. with basics and formats of sheetCost sheet. with basics and formats of sheet
Cost sheet. with basics and formats of sheet
supreetk82004
?
Class 3-Workforce profile updated P.pptx
Class 3-Workforce profile updated P.pptxClass 3-Workforce profile updated P.pptx
Class 3-Workforce profile updated P.pptx
angelananalucky
?
原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭
原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭
原版复刻加拿大多伦多大学成绩单(UTSG毕业证书) 文凭
taqyed
?
iam free indeed.pptxiam free indeed.pptx
iam free indeed.pptxiam free indeed.pptxiam free indeed.pptxiam free indeed.pptx
iam free indeed.pptxiam free indeed.pptx
muhweziart
?
april 2024 paper 2 ms. english non fiction
april 2024 paper 2 ms. english non fictionapril 2024 paper 2 ms. english non fiction
april 2024 paper 2 ms. english non fiction
omokoredeolasunbomi
?
Data-Models-in-DBMS-An-Overview.pptx.pptx
Data-Models-in-DBMS-An-Overview.pptx.pptxData-Models-in-DBMS-An-Overview.pptx.pptx
Data-Models-in-DBMS-An-Overview.pptx.pptx
hfebxtveyjxavhx
?
stages-of-moral-development-lawrence-kohlberg-pdf-free.pdf
stages-of-moral-development-lawrence-kohlberg-pdf-free.pdfstages-of-moral-development-lawrence-kohlberg-pdf-free.pdf
stages-of-moral-development-lawrence-kohlberg-pdf-free.pdf
esguerramark1991
?
Introduction to database and analysis software’s suitable for.pptx
Introduction to database and analysis software’s suitable for.pptxIntroduction to database and analysis software’s suitable for.pptx
Introduction to database and analysis software’s suitable for.pptx
nabinparajuli9
?
Stasiun kernel pengolahan kelapa sawit indonesia
Stasiun kernel pengolahan kelapa sawit indonesiaStasiun kernel pengolahan kelapa sawit indonesia
Stasiun kernel pengolahan kelapa sawit indonesia
fikrimanurung1
?
加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭
加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭
加拿大成绩单购买原版(鲍颁毕业证书)卡尔加里大学毕业证文凭
taqyed
?
2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM
2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM
2025-03-03-Philly-AAAI-GoodData-Build Secure RAG Apps With Open LLM
Timothy Spann
?
Analyzing Consumer Spending Trends and Purchasing Behavior
Analyzing Consumer Spending Trends and Purchasing BehaviorAnalyzing Consumer Spending Trends and Purchasing Behavior
Analyzing Consumer Spending Trends and Purchasing Behavior
omololaokeowo1
?
A Relative Information Gain-based Query Performance Prediction Framework with...
A Relative Information Gain-based Query Performance Prediction Framework with...A Relative Information Gain-based Query Performance Prediction Framework with...
A Relative Information Gain-based Query Performance Prediction Framework with...
suchanadatta3
?

module_14_digital_signatures.pptx

  • 2. What is a digital signature ? A digital signature allows the holder of the secret key (the signing key) to sign a document ? Everyone who knows the verification key can verify that the signature is valid (correctness) ? No one can forge a signature even given the verification key even though he is given a signature
  • 3. Structure of digital signature ? ??? 1? → (??, ??) ? ?????? ? → ??? ? ????? ?, ??? → {0,1}
  • 4. Structure of digital signature scheme (DSS) ? ??? 1? → (??, ??) ? ?????? ? → ??? ? ????? ?, ??? → {0,1} ? Correctness ? ????? ?, ??????(?) = 1 ? Unforgeability ? To be continued
  • 5. DSS VS MAC ? ??? 1? → (??, ??) ? ?????? ? → ??? ? ????? ?, ??? → {0,1} ? ??? 1? → ? ? ???? ? → ? ? v??? ?, ? → {0,1}
  • 6. Mac forgery game M ← {} ?′ ?′ k ∈? 0,1 ? (?, ?) Wins if ? ? ? ? ? ?????? ?, ? = 1 ?′ ← ????(?′) M ← ? ∪ {?′} Repeat as many times as the adversary wants
  • 7. Signature forgery game M ← {} ?′ ???′ ??, ?? ← ???(1? ) (?, ???) Wins if ? ? ? ? ? ???????? ?, ??? = 1 ???′ ← ??????(?′) M ← ? ∪ {?′} Repeat as many times as the adversary wants ??
  • 8. Definition of signature scheme ? Correctness: ? Pr ????? ?, ?????? ? = 1 ??, ?? ← ??? 1? = 1 ? Unforgeability ? For all PPT adversary ?, there exists negligible function ?, ? Pr ? ???? ??? ????????? ??????? ???? ≤ ?(?)
  • 9. Relation between macs and signatures ? Every signature scheme is a message authentication code. ? A mac scheme is not necessarily a signature. ? Without the key, it may be impossible to verify a mac.
  • 10. Signatures are expensive ? They require public-key operations for each signature you wish to do. ? Hash functions are relatively cheap
  • 11. Hash and sign ? Let (???′, ????′, ??????′) be a signature scheme and let ? be a collision resistant hash function, then the following ? ??? 1? ? ???′ 1? ? ?????? ? ? ?????? ′ (? ? ) ? ???????? ?, ??? ? ???????? ′ ? ? , ??? = 1
  • 12. Security of hash and sign ? Let (???′, ????′, ??????′) be a signature scheme and let ? be a collision resistant hash function, then the following ? ??? 1? ? ???′ 1? ? ?????? ? ? ?????? ′ (? ? ) ? ???????? ?, ??? ? ??????′ ? ? , ??? = 1 ? Essentially the same proof as hash and mac ? Breaking security of this scheme means ? Finding a collision ? Finding a signature on an unsigned message
  • 13. Interesting property of plaintext RSA ? ??, ?? ← ?????? 1? ? ????? ????? ? = ? ? Due to the fact that ?? ? = ?? ? = ???
  • 14. RSA signature scheme ? Let (??????, ???, ???) denote the RSA encryption scheme ? ??? 1? ? {?? ← ??′, ?? ← ?? ∣ ??′, ??′ ← ?????? 1? } ? ?????? ? ? ????? ? ? ???????? ?, ??? ? ????? ??? = ?
  • 15. Insecure RSA signature scheme ? ??? 1? ? { ?? ← ??, ?? ← ??′ ∣ ??′, ??′ ← ?????? 1? } ? ?????? ? ? ????? ? ? ???????? ?, ?????? ? = ????? ????? ? ? ????? ????? ? = ?? ? = ???? = ?
  • 16. Secure RSA signature scheme ? Assumptions ? Random oracle ? (Hash function modeled as a random oracle ? ? = ?? where ?, ? are prime ? ??? 1? ? { ?? ← ??, ?? ← ??′ ∣ ??′ , ??′ ← ?????? 1? } ? ?????? ? ? ????? ?(?) ? ???????? ?, ?????? ? ? ? ? = ????? ????? ?(?) ? ????? ????? ?(?) = (?(?))? ? ??? ? ? (?(?))? ? ??? ? = ?(?)??? ??? ?(?) (??? ?) = ?(?)
  • 17. Schnorr signature scheme ? Based on ? Group G ? Generator ? for G ? Random oracle ? ? Discrete logarithm
  • 18. Schnorr signature scheme ? Requirement: Group ?, ? = ?, generator ?, random oracle ? ? ??? 1? ? ?? ∈? ? ? ?? ← ??? ? ????????(?, ???) ? ?, ? ← ??? ? u ← ?? ? ???? ? Output ? ?, ? = ? ? ?????? ? ? ? ∈? ?|?| ? ? ← ?? ? ? ← ?(?, ?) ? ? ← ? ? ?? + ? (??? ?) ? Output (?, ?)