CRYP-F02
SESSION ID:
Masayuki Fukumitsu, Shingo Hagawa
Associate Professor, Assistant Professor Hokkaido Information University, Tohoku University
#RSAC Fiat-Shamir-type (FS-type) Signature Schemes
Signature Schemes derived via the FS transformation [FS87]
< Schnorr [Sch91], Guillou-Quisquater(GQ) [GQ88], Okamoto [Oka93], Lyubashevsky[Lyu08]
FS trans.
#RSAC Security Proofs in Random Oracle Model Instantiations:
Schnorr signature scheme is cure under the discrete log (DL) assumption
GQ signature scheme is cure under the RSA assumption
Assumption on
Underlying ID
Provable Security
Of its FS-type sig.
[PS00]HVZKPoK⇒uf-cma
[AABN08]imp-pa cure⇔uf-cma
There are affirmative results on the provable curity of FS-type sig.
#RSAC What Does Mean FS-type Signature Is Secure?
There is a polytime reduction algorithm R which breaks
an underlying cryptographic assumption by accessing an adversary algorithm A against a designated FS-type signature scheme.
R (breaking assumption)
A (attacking to
FS sig.)
#RSAC Proof Techniques
The results [PS00, AABN08] rely on the followings:
Forking Lemma
Random Oracle Model
–Is a.k.a. Ideal curity model
–Restricts any party to obtain any hash value from the random oracle
–Is applied to prove the curity of many cryptographic schemes
R (simulating random oracle)
A
