Based on Group Actions and Generic Isogenies
undefined
A Lower Bound on the Length of Signatures
Based on Group Actions and Generic Isogenies
D
A
N
B
O
N
E
H
1
,
J
I
A
X
I
N
G
U
A
N
2
,
A
N
D
M
A
R
K
Z
H
A
N
D
R
Y
2
,
3
1 STANFORD UNIVERSITY
2 PRINCETON UNIVERSITY
3 NTT RESEARCH, INC.
undefined
Based on
A Lower Bound on the Length of Signatures
Group Actions and Generic Isogenies
Hardness Assumptions
Post-Quantum Cryptography
Most constructions are from (structured)
Lattices
Group-Action-Based
Cryptography
Cryptographic Group Actions [Cou06, ADMP21]
G
X
Group
G
Set
X
*:
G
×
X
→
X
Identity
e
:
e
*
x
=
x
for all
x
Compatibility:
(
gh
)
*
x
=
g
* (
h
*
x
)
for all
g
,
h
,
x
Discrete log: Given
x
,
y
=
g
*
x
, find
g
Sub-Exponential [Kup05,
Reg04, Kup13, Pei20]
Isogeny-Based Cryptography
•
An isogeny is a surjective group morphism between two elliptic curves
•
Group Actions derived from isogeny graphs of elliptic curves [Cou06, RS06]
•
Constructions from
supersingular
isogeny graphs [JF11, FJP14] to avoid the sub-
exponential quantum algorithms for DLog
•
Recent attacks on key exchange protocols based on SIDH [CD22, MM22, Rob22]
•
SIDH is
not
a group action
•
Does not affect
other isogeny-based protocols such as SeaSign [DG19, DPV19],
CSI-FiSh[BKV19, EKP20, CS20] and SQISign [DKL
+
20, DLW22]
Based on Group Actions and Generic Isogenies
A Lower Bound on the Length of Signatures
Our Result
Group-Action-
Based Signature
Maurer’s Generic
Group Model [Mau05]
Shoup’s Generic
Group Model [Sho97]
Implies Random
Oracles [ZZ21]
Signature Impossible
[DHH
+
21]
ID Protocols
Group-Action-
Based ID Protocol
ID Protocol (w/ group action oracle)
P(pk, sk)
V(pk)
1/0
t
V(pk)
1
Our Main Theorem
If a public coin ID protocol in the black box group action model has
completeness
C
,
P
set elements in the public key, and
N
set elements in the
transcript, then for an adversary with access to a polynomial
t
number of
transcripts, the soundness error
S
is bounded by:
S ≥ P
-N
S ≥ C - P/t
Proof
Intuition
x
1
x
2
a
1
x
P
…
a
2
…
a
N
x
3
x
4
a
3
a
4
pk
x
1
=
h
*
a
1
=
h’
*
a
1
a
2
Conclusion
•
Lower Bound of 𝛀(𝝀
𝟐
/𝐥𝐨𝐠 𝝀) for group-action based signatures
•
How to circumvent our lower bound?
•
Signature schemes
not
from ID protocols
•
Non-generic use of group actions
•
Other hardness assumptions
Thank you!
This content discusses lower bounds on signature lengths based on group actions and generic isogenies in cryptography. It covers topics such as isogeny-based cryptography, post-quantum cryptography, hardness assumptions, and ID protocols in a comprehensive manner.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies DAN BONEH1, JIAXIN GUAN JIAXIN GUAN2, AND MARK ZHANDRY2,3 1 STANFORD UNIVERSITY 2 PRINCETON UNIVERSITY 3 NTT RESEARCH, INC.
A Lower Bound on the Length of Signatures Group Actions and Generic Isogenies Based on
Post-Quantum Cryptography Most constructions are from (structured) Lattices Group-Action-Based Cryptography
Cryptographic Group Actions [Cou06, ADMP21] Identity e: e * x = x for all x G X Compatibility: (gh) * x = g * (h * x) for all g, h, x Group G Set X Discrete log: Given x, y = g * x, find g *: G X X Sub-Exponential [Kup05, Reg04, Kup13, Pei20]
Isogeny-Based Cryptography An isogeny is a surjective group morphism between two elliptic curves Group Actions derived from isogeny graphs of elliptic curves [Cou06, RS06] Constructions from supersingular isogeny graphs [JF11, FJP14] to avoid the sub- exponential quantum algorithms for DLog Recent attacks on key exchange protocols based on SIDH [CD22, MM22, Rob22] SIDH is not a group action Does not affect other isogeny-based protocols such as SeaSign [DG19, DPV19], CSI-FiSh[BKV19, EKP20, CS20] and SQISign [DKL+20, DLW22]
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies
Our Result ?? Maurer s Generic Group Model [Mau05] Group-Action- Based ID Protocol ?( ????) Signature Impossible [DHH+21] ID Protocols ?? Group-Action- Based Signature ?( ????) Shoup s Generic Group Model [Sho97] Implies Random Oracles [ZZ21]
ID Protocol (w/ group action oracle) 1/0 V(pk) P(pk, sk) 1 t V(pk)
Our Main Theorem If a public coin ID protocol in the black box group action model has completeness C, P set elements in the public key, and N set elements in the transcript, then for an adversary with access to a polynomial t number of transcripts, the soundness error S is bounded by: ? ? ? 1 ? ? ? ???? S P-N S C - P/t ? ? + ? ?( ????) ? ?
Proof Intuition ? ? 1 ? ? ? ???? a1 a2 a3 a4 aN x1 = h * a1 pk x1 x4 xP x3 x2 = h * a1 a2
Conclusion Lower Bound of ?(??/????) for group-action based signatures How to circumvent our lower bound? Signature schemes not from ID protocols Non-generic use of group actions Other hardness assumptions
