Agenda
Background on Isogeny-Based Cryptography

One-Round Authenticated Group Key
Exchange from Isogenies

Isogenies between Elliptic Curves
HHS, CIM and CSIDH Key Exchange

ECC 2018

One-Round Authenticated Group Key Exchange (AGKE)
on CIM2018 / 11 / 21

Proposed Protocols: ݊-UM and Biclique ݊-DH Protocols

Realistic 2-Party AKE from HHS (e.g., CSIDH)

Katsuyuki TAKASHIMA ( Mitsubishi Electric )One-Round Authenticated Key Exchange (AKE) from SIDH
SIDH UM and Biclique Protocols

Joint work with Atsushi FUJIOKA ( Kanagawa U.),
Shintaro TERADA, Kazuki YONEYAMA ( Ibaraki U. )Security of Biclique SIDH AKE from di-SI-GDH Assumption
1

22© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Threat of Quantum Computers andCandidate Post-Quantum PKE
P. Shor’s factoring and discrete logarithm quantum
algorithms break widely-used public key encryption (PKE),
e.g., RSA, (EC)DH, Pairing crypto.
Candidates of post-quantum PKE
lattice crypto
multivariate crypto
code-based crypto
isogeny crypto

Background on Isogeny-Based
Cryptography

Quantum-resistant basic mathematical problems
lattice crypto䠖 shortest vector problem 䠄SVP䠅,closest vector problem 䠄CVP䠅
33

isogeny crypto䠖 (䠯䠥䠠䠤) isogeny problem,(CSIDH) group action inversion problem 44© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Isogenies between Elliptic Curves

Elliptic Curves in Cryptography•㻭㼚㻌㼑㼘㼘㼕㼜㼠㼕㼏㻌㼏㼡㼞㼢㼑㻌‫ ܧ‬㼛㼢㼑㼞㻌㼍㻌㼒㼕㼚㼕㼠㼑㻌㼒㼕㼑㼘㼐㻌 ॲ௤(‫݌ = ݍ‬௞ ,㼕㼟㻌㼐㼑㼒㼕㼚㼑㼐㻌㼎㼥㻌㼍㼚㻌㼑㼝㼡㼍㼠㼕㼛㼚㻌‫ ݕ‬ଶ = ݂(‫ )ݔ‬㼟㻚㼠㻚 deg ݂㻱㻚㼓㻚㻘㻌㻹㼛㼚㼠㼓㼛㼙㼑㼞㼥㻌㼒㼛㼞㼙㻌‫ܧ‬: ܾ‫ ݕ‬ଶ = ‫ ݔ‬ଷ + ܽ‫ ݔ‬ଶ + ‫ݔ‬,ܽ, ܾ(് 0) ‫ॲ א‬௤R := P + Q, (x3, y3) := (x1, y1) + (x2, y2)
Į࣭P := P + … + PĮ‫ ݌‬൒ 5)= 3㻚Q = (x2, y2)

P =(x1, y1)•

R = (x3, y3)

x3 := b{(y2-y1)/(x2-x1)}2-x1- x2-ay3 := {(y2-y1)/(x2-x1)}(x1-x3)-y1

ܲ+ܳgĮ 㼕㼚㻌㼠㼔㼑㻌㻰㼕㼒㼒㼕㼑㻙㻴㼑㼘㼘㼙㼍㼚㻌㼗㼑㼥㻌㼑㼤㼏㼔㼍㼚㼓㼑ܳ㻱㻯㻰㻴㻌: 㼎㼍㼟㼑㼐㻌㼛㼚㻌㼠㼔㼑㻌㼔㼍㼞㼐㼚㼑㼟㼟㻌㼛㼒㻌㼏㼍㼘㼏㼡㼘㼍㼠㼕㼚㼓㻌䃐 㼒㼞㼛㼙㻌( P , Į࣭P ):㻱㻯㻌㼐㼕㼟㼏㼞㼑㼠㼑㻌㼘㼛㼓㼍㼞㼕㼠㼔㼙•55© Mitsubishi Electric Corporation

Algorithms for Isogeny Problems

For example, a compact representation of ߶ is given by elliptic curves(݆-invariants) appearing in the sequence of κ௜ -isogenies if ߶ isdecomposed into a product of κ௜ -isogenies for small prime κ௜ ’s.
㻯㼛㼙㼜㼡㼠㼍㼠㼕㼛㼚㻌㼠㼕㼙㼑㻌㼣㼕㼠㼔㻌㼏㼘㼍㼟㼟㼕㼏㼍㼘㻌㼏㼛㼙㼜㼡㼠㼑㼞㼟㻯㼛㼙㼜㼡㼠㼍㼠㼕㼛㼚㻌㼠㼕㼙㼑㻌㼣㼕㼠㼔㻌㼝㼡㼍㼚㼠㼡㼙㻌㼏㼛㼙㼜㼡㼠㼑㼞㼟ܱ෨ ర ‫݌‬‫ܮ‬௣ 1/2, 3/2

ܱ෨

‫݌‬

㻖 elliptic curves ‫ ܧ‬with ‫݌ ܧ‬= {ܱா }

ܲ

߶

߶(ܲ)

߶ ܲ + ܳ = ߶ ܲ + ߶(ܳ)߶(ܳ)

Vélu's formula: Using elliptic curve ‫ ܧ‬and point ܴ, efficiently computean isogeny ߶: ‫ ܧ‬՜ ‫ܧ‬/‫ ۄܴۃ‬with kernel ‫ۄܴۃ‬.

66© Mitsubishi Electric Corporation

A HHS (‫ܩ‬, ܺ) consists of¾ a finite commutative group ‫ ܩ‬and¾ some set ܺ (not necessarily a group), where¾ ‫ ܩ‬acts freely and transitively on ܺ, i.e., ‫ ܩ‬ց ܺ

Given two isogenous elliptic curves ‫ ܧ‬and ‫ܧ‬Ԣ, computea (compact representation of) isogeny ߶: ‫ ܧ‬՜ ‫ ܧ‬ᇱ .

supersingular elliptic
curve *

Isogeny

Hard Homogenous Spaces (HHS) [Cou97,06]

Isogeny Problem

ordinary elliptic curves

Given two elliptic curves ‫ܧ‬, ‫ܧ‬Ԣ, an isogeny ߶: ‫ ܧ‬՜ ‫ܧ‬Ԣ is a surjective
map defined on points ܲ = (‫ݔ‬, ‫ )ݕ‬of ‫ ܧ‬by߶ ܲ = (݂ ‫ݔ‬, ‫ ݕ‬, ݃ ‫ݔ‬, ‫) ݕ‬
where ݂, ݃ are rational functions.
Additionally, if ܲ, ܳ are points on ‫ܧ‬, theni.e., ߶ is a homomorphism.
߶ ܲ+ܳ =߶ ܲ +߶ ܳ
If there is an isogeny between two elliptic curves ‫ܧ‬, ‫ܧ‬Ԣ, they arecalled isogenous.

ܱ෨ ర ‫݌‬

subexponental in log p䠖 ‫ܮ‬௣ ߙ, ܿ ؔ exp ܿ + ‫(݋‬1) log ‫ ݌‬ఈ log log ‫ ݌‬ଵିఈ

77© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

The following tasks are required to be easy
(e.g., polynomial-time)¾ compute the group operations on ‫ܩ‬,
¾ sample randomly from ‫ ܩ‬with (close to) uniform
distribution,¾ decide validity and equality of a representation ofelements of ܺ,¾ compute the action of a group element ݃ ‫ ܩ א‬onsome ‫ܺ א ݔ‬.

88© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Examples of HHS

HHS-Based DH Protocol

CRS (Couveignes-Rostovtsev-Stolbunov) HHS (‫ܩ‬, ܺ)¾ ܺ ؔ Ell௤ ࣩ : the set of isomorphismclasses over ॲ௤ of ordinary elliptic curves
with CM by ࣩ (an imaginary quadratic order)¾ ‫ ؔ ܩ‬Cl ࣩ : the ideal class group of ࣩ
CSIDH (by [CLMPR18]) HHS (‫ܩ‬, ܺ)¾ ܺ: the set of isomorphism classes over ॲ௣of supersingular elliptic curves withॲ௣ -rational endomorphism ring by ࣩ(an imaginary quadratic order)¾ ‫ ؔ ܩ‬Cl ࣩ : the ideal class group of ࣩ

Fundamental intractability assumptions on HHS (‫ܩ‬, ܺ)¾ Inversion intractability of the group action:
Intractable to compute ݃ from (‫ݔ‬, ݃ ‫)ݔ כ‬¾ 2-way computational DH ( 2-CDH ) assumption:
Intractable to compute ݄݃ ‫ ݔ כ‬from (‫ݔ‬, ݃ ‫ݔ כ‬, ݄ ‫)ݔ כ‬¾ variants of 2-CDH: 2-DDH, 2-GDH assumptions
Standard HHS-based DH protocol:
Alice
୙

୙

‫ ݔ‬՚ ܺ, public parameterࣵ ՚ ‫ܩ‬, Alice’s secret key,compute ࣵ ‫ݔ כ‬,‫ܭ‬୅୪୧ୡୣ ؔ ࣵ ‫ݔ כ ࣶ כ‬

ࣵ‫ݔכ‬

ࣶ‫ݔכ‬

Bob
୙

ࣶ ՚ ‫ܩ‬, Bob’s secret key,compute ࣶ ‫ݔ כ‬,‫ܭ‬୆୭ୠ ؔ ࣶ ‫)ݔ כ ࣵ( כ‬¾ Same as the CRS-based key exchange, CSIDH has asubexponential-time quantum algorithm attack.

99© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Useful Applications from Isogenies ?

݊-way non-interactive key exchange,
verifiable random functions,constrained pseudorandom functions,broadcast encryption,
witness encryption.

On the top of HHS given by (‫ܩ‬, ܺ), we build the notion of Cryptographic
Invariant Map (CIM).
By a CIM we mean a randomized algorithm MapGen that inputs asecurity parameter ߣ, outputs public parameters ‫ܺ( ؔ ݌݌‬, ܵ, ‫ܩ‬, ݁),and runs in time polynomial in ߣ, where¾ (‫ܩ‬, ܺ) is a HHS, and ܵ is a set,

They developed a framework of Cryptographic Invariant Maps (CIMs),
which is

¾ ݁ is a deterministic algorithm that runs in time polynomial in ߣand ݊, s.t. for ݊ > 0, it computes ݁௡ : ܺ ௡ ՜ ܵ that satisfies:¾ a new primitive closely related to a cryptographic multilinear
map, but¾ whose range does not necessarily have a group structure.

••݁௡ : ܺ × ‫ ܺ × ڮ‬՜ ܵ with• group action ‫ ܩ‬ց ܺ• multilinearity w.r.t. the action• ܵ is not necessarily a group1010© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Cryptographic Invariant Map (CIM) [BGK+18]

Very recently, Boneh et al. suggest another research direction for using
isogenies on elliptic curves in applied cryptography which includes:
•
•
•
•
•

¾ Efficient public key validation

1111© Mitsubishi Electric Corporation

Invariance property of ݁௡ : for all ‫ ܺ א ݔ‬and ݃ଵ , … , ݃௡ ‫ܩ א‬,݁௡ ݃ଵ ‫ݔ כ‬, … , ݃௡ ‫݁ = ݔ כ‬௡ ݃ଵ ‫݃ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫; ݔ‬

Non-degeneracy of ݁௡ : for all ݅ with 1 ൑ ݅ ൑ ݊ and‫ݔ‬ଵ , … , ‫ݔ‬௜ିଵ , ‫ݔ‬௜ାଵ , … , ‫ݔ‬௡ ‫ܺ א‬, the map ܺ ՜ ܵ defined by‫ ݕ‬հ ݁௡ ‫ݔ‬ଵ , … , ‫ݔ‬௜ିଵ , ‫ݕ‬, ‫ݔ‬௜ାଵ , … , ‫ݔ‬௡ is injective.

12
12© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

݊-way DH Assumptions [BGK+18]

Cryptographic Invariant Map (II)Fundamental Requirements for Cryptographic Invariant Maps (CIMs):The following isomorphism between abelian varieties holds

We say that MapGen satisfies the ݊-way computational Diffie-Hellman
assumption (݊-CDH) if for every polynomial time quantum algorithm ࣭,ࣵଵ ‫ࣵ × ڮ × ܧ כ‬௡ ‫ ܧ כ‬؆ ࣵଵ ‫ࣵ ڮ‬௡ ‫ ܧ × ܧ כ‬௡ିଵߣ ؔ Pr ࣭ ‫݌݌‬, ݃ଵ ‫ݔ כ‬, … , ݃௡ ‫݁ = ݔ כ‬௡ିଵ ݃ଵ ‫݃ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ݔ‬Adv௡େୈୌ
࣭

However, we have not yet suitable isomorphism invariants, s.t.
if ‫ܧ‬ଵ × ‫ܧ × ڮ‬௡ ؆ ‫ܧ‬ଵᇱ × ‫ܧ × ڮ‬௡ᇱ ֜ ݁௡ ‫ܧ‬ଵ × ‫ܧ × ڮ‬௡ = ݁௡ ‫ܧ‬ଵᇱ × ‫ܧ × ڮ‬௡ᇱ ,if ‫ܧ‬ଵ × ‫ܧ × ڮ‬௡ ؈ ‫ܧ‬ଵᇱ × ‫ܧ × ڮ‬௡ᇱ ֜ ݁௡ ‫ܧ‬ଵ × ‫ܧ × ڮ‬௡ ് ݁௡ ‫ܧ‬ଵᇱ × ‫ܧ × ڮ‬௡ᇱ .

is a negligible function of ߣ, when ‫ ݌݌‬՚ MapGen(ߣ), ݃ଵ , ‫ ڮ‬, ݃௡ ՚ ‫ ܩ‬and‫ ݔ‬՚ ܺ.

Two distributions ࣞ଴ and ࣞଵ , where ‫ ݌݌‬՚ MapGen(ߣ), ݃ଵ , ‫ ڮ‬, ݃௡ ՚ ‫ ܩ‬and‫ ݔ‬՚ ܺ:Candidates for Cryptographic Invariant Maps (CIMs) [BGK+18]:
Seeking for a higher dimensional analog of elliptic curve ݆-invariant¾ theta null invariant¾ ࣞ଴ is (‫݌݌‬, ݃ଵ ‫ݔ כ‬, … , ݃௡ ‫ݔ כ‬, ‫ݏ‬଴ ) where ‫ݏ‬଴ = ݁௡ିଵ ݃ଵ ‫݃ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ ݔ‬,¾ ࣞଵ is (‫݌݌‬, ݃ଵ ‫ݔ כ‬, … , ݃௡ ‫ݔ כ‬, ‫ݏ‬ଵ ) where ‫ݏ‬ଵ is random in Im ݁௡ିଵ ‫ܵ ك‬.

not satisfy the fundamental
requirements¾ Igusa invariants

We say that MapGen satisfies the ݊-way decisional Diffie-Hellman
assumption (݊-DDH) if for every polynomial time quantum algorithm ࣭,¾ Invariants of Kummer surfaces¾ Deligne invariant՜

not compute efficiently( if it’s efficiently computable, theisogeny problem become easy !! )13
13
© Mitsubishi Electric Corporation© Mitsubishi Electric Corporationߣ ؔ Pr ࣭ ‫ = ݖ‬1 | ‫ ݖ‬՚ ࣞ଴ െ Pr ࣭ ‫ = ݖ‬1 | ‫ ݖ‬՚ ࣞଵAdv௡ୈୈୌ
࣭is a negligible function of ߣ.

1414© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

݊-way Gap DH Assumption

We say that MapGen satisfies the ݊-way gap Diffie-Hellman
assumption (݊-GDH) if for every polynomial time quantum algorithm ࣭which accesses the ݊-DDH oracle ܱ ‫݊ = ڄ‬-DDH ‫ ڄ‬,ߣ ؔ Pr ࣭ ை ‫݌݌‬, ݃ଵ ‫ݔ כ‬, … , ݃௡ ‫݁ = ݔ כ‬௡ିଵ ݃ଵ ‫݃ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ݔ‬Adv௡ୋୈୌ
࣭is a negligible function of ߣ, when ‫ ݌݌‬՚ MapGen(ߣ), ݃ଵ , ‫ ڮ‬, ݃௡ ՚ ‫ ܩ‬and‫ ݔ‬՚ ܺ. For any input (‫ݔ‬ଵᇱ , … , ‫ݔ‬௡ᇱ , ‫ ݏ‬ᇱ ) where ‫ݔ‬௜ᇱ = ݃௜ᇱ ‫ = ݅( ݔ כ‬1, … , ݊), the݊-DDH oracle ܱ ‫݊ = ڄ‬-DDH ‫ ڄ‬acts as follows:

One-Round Authenticated Group Key Exchange(AGKE)
on Cryptographic Invariant Maps (CIM)¾ ݊-DDH ‫݌݌‬, ‫ݔ‬ଵᇱ , … , ‫ݔ‬௡ᇱ , , ‫ ݏ‬ᇱ = 0 if ‫ ݏ‬ᇱ = ݁௡ିଵ ݃ଵᇱ ‫݃ ڮ‬௡ᇱ ‫ݔ כ‬, ‫ݔ‬, … , ‫ ݔ‬,¾ ݊-DDH ‫݌݌‬, ‫ݔ‬ଵᇱ , … , ‫ݔ‬௡ᇱ , , ‫ ݏ‬ᇱ = 1 otherwise.

Galbraith and Vercauteren showed an attack against the 2-way gap DiffieHellman problem on SIDH since the degrees of isogenies used are fixed௘௘
by public param. as κଵభ and κଶమ for small primes κଵ , κଶ , e.g., κଵ = 2, κଶ = 3.

As the CSIDH protocol uses random degrees consisting multiple primesκଵ , … , κ௡ and they are not fixed by public parameters, the attack against
GDH problem cannot be applied to the CSIDH setting.

15
15© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

16
16© Mitsubishi Electric Corporation

Authenticated KE ( AKE )Authenticated Group KE ( AGKE )In an AKE protocol, two parties, called initiator and responder, have own
static public keys, exchange ephemeral public keys, and compute a
session key based on the public keys and the related secret keys.

It is natural to extend two-party authenticated key exchange to ݊-party
authenticated key exchange for ݊ > 2.

Several security models for AGKE:¾ The G-CK model is an AGKE variant of the CK model, and it captures
leakage of the session state.
ା
¾ The G-CK model integrates the G-CK model with KCI, wPFS and
MEX requirements.

Among several security models, the Canetti-Krawczyk (CK) model was
proposed to capture leakage of the session state.
ା

CK model: based on the CK
model, several additional security
requirements; key compromise
impersonation (KCI), weak perfectforward secrecy (wPFS) andmaximal exposure attacks (MEX)
are integrated.
We have no QROM secure norାCK secure one-round HHS-based
AKE protocols.
Cf. [DKS18] for CRS-based one

StatickeyାPreviously, tripartite AGKE protocols secure in the G-CK or G-CK model
were given by Manulis et al. and Suzuki et al.

Statickey

Ephemeral
key

Ephemeral
key

Session key=
17
17

Li and Yang introduced one-round AGKE protocol from multilinear maps,and Lan et al. introduced one-round AGKE protocol from iO.
ାThese protocols are not proved in the G-CK or G-CK model, andquantum-resistance is not considered.
Thus, we have no one-round AGKE protocols for general ݊ parties (݊ > 3)ାsecure in the G-CK or G-CK model, additionally against quantum
18
adversaries.
18© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Our Contributions from CIM and HHS
We propose two one-round AGKE protocols on CIMs.
¾ ݊-UM (݊-Unified Model) protocol which satisfies the G-CK
security: The security is proved under the ݊-way DDH
assumption in the quantum random oracle model (QROM).
¾ BC ݊-DH (biclique ݊-Diffie-Hellman) protocol whichା
satisfies the G-CK security: The security is proved underthe ݊-way GDH assumption in the random oracle model.

݊-UM Protocol

ܶଵ = ‫ݐ‬ଵ ‫ݔ כ‬

ܴଵ = ‫ݎ‬ଵ ‫ݔ כ‬‫ڮ‬ܶ௜ = ‫ݐ‬௜ ‫ݔ כ‬‫ڮ‬ܶ௡ = ‫ݐ‬௡ ‫ݔ כ‬‫ڮ‬ܴ௜ = ‫ݎ‬௜ ‫ ݔ כ‬ோ ‫ ڮ‬ோܴ௡ = ‫ݎ‬௡ ‫ݔ כ‬
ோభ
ோ೔
೔
೙
՜ ‫ڮ‬
‫ ڮ‬՚
ܼଵ = ݁௡ିଵ ܶଵ , … , ܶ௜ିଵ, ‫ݐ‬௜ ‫ܶ כ‬௜ାଵ , ܶ௜ାଶ, … , ܶ௡ܼଶ = ݁௡ିଵ ܴଵ , … , ܴ௜ିଵ , ‫ݎ‬௜ ‫ܴ כ‬௜ାଵ , ܴ௜ାଶ , … , ܴ௡ܵ‫ ܪ = ܭ‬ȫ, ܷଵ , … , ܷ௡ , ܴଵ , … , ܴ௡ , ܼଵ , ܼଶPublic parameters:
Protocol identifier ȫ ؔ nUM.
A random (݊ െ 1)-way cryptographic
invariant map ܺ, ܵ, ‫ܩ‬, ݁௡ିଵ ՚ோ MapGen(1ఒ ), and random ‫ ݔ‬՚ோ ܺ.
‫ܪ‬: 0,1 ‫ כ‬՜ 0,1 ఒ : hash function. Public parameters = ȫ, ܺ, ܵ, ‫ܩ‬, ݁௡ିଵ , ‫ݔ‬, ‫ ܪ‬.

Static secret and public keys: Party ܷ௜ chooses ‫ݐ‬௜ ՚ோ ‫ ܩ‬as the SSK.
Then, ܷ௜ computes ܶ௜ = ‫ݐ‬௜ ‫ ݔ כ‬as the SPK.

Key exchange: We suppose a session executed by ‫ܷ( = ܃‬ଵ , … , ܷ௡ ).
¾ ܷ௜ chooses ‫ݎ‬௜ ՚ோ ‫ ܩ‬as the ESK, and computes ܴ௜ = ‫ݎ‬௜ ‫ ݔ כ‬as the EPK.
Then, ܷ௜ broadcasts ȫ, role௜ ᇲ , ܷ௜ , ܴ௜ to ‫ܷ{ ך ܃‬௜ }.
¾ On receiving ȫ, role௝ ᇲ , ܷ௝ , ܴ௝ for all ݆ ് ݅, ܷ௜ computes
ܼଵ = ݁௡ିଵ ܶଵ , … , ܶ௜ିଵ , ‫ݐ‬௜ ‫ܶ כ‬௜ାଵ , ܶ௜ାଶ , … , ܶ௡ andܼଶ = ݁௡ିଵ ܴଵ , … , ܴ௜ିଵ , ‫ݎ‬௜ ‫ܴ כ‬௜ାଵ , ܴ௜ାଶ , … , ܴ௡ .
ܷ௜ generates the session key ܵ‫ ܪ = ܭ‬ȫ, ܷଵ , … , ܷ௡ , ܴଵ , … , ܴ௡ , ܼଵ , ܼଶ .

We Instantiate the proposed protocols on HHS withlimitation where the number of the user group is two.

¾ The CSIDH-based protocols are currently more realistic
than the general ݊-party CIM-based ones due to its
implementability.

© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

19
19© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

ܼଵ = ݁௡ିଵ ܶଵ , … , ܶ௜ିଵ , ‫ݐ‬௜ ‫ܶ כ‬௜ାଵ , ܶ௜ାଶ , … , ܶ௡ = ݁௡ିଵ ‫ݐ‬ଵ ‫ݐ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ ݔ‬,
ܼଶ = ݁௡ିଵ ܴଵ , … , ܴ௜ିଵ , ‫ݎ‬௜ ‫ܴ כ‬௜ାଵ , ܴ௜ାଶ , … , ܴ௡ = ݁௡ିଵ ‫ݎ‬ଵ ‫ݎ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ ݔ‬. 20

20© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Security of ݊-UM Protocol

Design Principle:

Theorem ( ݊-UM )ା

¾ G-CK security: maximum exposure resilience:Adv. can obtain either static or ephemeral secret key for each party
who is contained in a session.

The ݊-UM protocol is a post-quantum G-CK-secure ݊-party
authenticated key exchange protocol from the ݊-DDH
assumption in the QROM.

¾ To resist all exposure patterns, parties should compute shared valuesby all combinations of static or ephemeral key for each party.

In particular, for any quantum adversary ࣛ against the ݊-UM protocolthat runs in time at ݊௪ , involves at most ݊௨ honest parties and activates
at most ݊௦ sessions, and makes at most ݊௛ queries to the quantum
random oracle and ݊௤ StaticReveal queries,
there exists a ݊-DDH quantum solver ࣭ such that
Adv௡ୈୈୌ
ߣ
࣭

൒

୥ୡ୩

2 ‫ ڄ‬Adv௡୙୑,ࣛ ߣ ଶ݊௨ଶ ݊௦ଶ 8݊௛ ݊௤ + 3 ݊௛ + ݊௤ + 1

ସ

¾ In ݊-UM, party ܷ௜ computes
ܼூ = ݁௡ିଵ ܶଵ , … , ܶ௜ିଵ , ‫ݐ‬௜ ‫ܶ כ‬௜ାଵ , ܶ௜ାଶ , … , ܶ௡ andܼ‫݁ = ׎‬௡ିଵ ܴଵ , … , ܴ௜ିଵ , ‫ݎ‬௜ ‫ܴ כ‬௜ାଵ , ܴ௜ାଶ , … , ܴ௡ ,where ܼூ (resp. ܼ‫ ) ׎‬consists of only static (resp. ephemeral) keys.

¾ Let ‫[ ؔ ܫ‬1, ݊]. In biclique ݊-DH, party ܷ௜ additionally computes
ܼ௉ = ݁௡ିଵ ܸଵ , … , ܸ௜ିଵ , ‫ݒ‬௜ ‫ܸ כ‬௜ାଵ , ܸ௜ାଶ , … , ܸ௡ = ݁௡ିଵ ‫ݒ‬ଵ ‫ݒ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ݔ‬for all subsets ܲ of ‫ܫ‬, where,

where ࣭ runs in time ݊௪ plus time to perform ܱ( ݊௨ + ݊௦ ߣ) group
operations.

21
21© Mitsubishi Electric Corporation© Mitsubishi Electric Corporationଵ‫ݒ‬௜ = ‫ݐ‬௜ or ‫ݎ‬௜

7

8

1

1

1

1

0

0

0

0

‫ݐ‬ଵ

‫ݐ‬ଶ

‫଻ݐ‬

‫଼ݐ‬

‫ݎ‬ଵ

‫ݎ‬ଶ

‫଻ݎ‬

‫଼ݎ‬

ଵ

ோభ

ோ೔

௡ିଵ

௜

௜

ଵ

௜

௜

௜ିଵ

‫ڮ‬

truth value
Tr( ݅ ‫) ܲ א‬

2

ଵ

‫׎‬

௜

ோ೔

௜ାଵ

௜ାଶ

ோ೙

௡

௡

௡

௡

௡

ܼூ = ݁௡ିଵ ܴଵ, … , ܴ௜ିଵ, ‫ݎ‬௜ ‫ܴ כ‬௜ାଵ , ܴ௜ାଶ, … , ܴ௡Public parameters:
We set protocol identifier ȫ = BCnDH. ܵ‫ ܪ = ܭ‬ȫ, ܷଵ , … , ܷ௡ , ܴଵ , … , ܴ௡ , ܼ‫ ׎‬, … , ܼூ
The rest is the same as nUM. Public parameters are ȫ, ܺ, ܵ, ‫ܩ‬, ݁௡ିଵ , ‫ݔ‬, ‫ ܪ‬.

‫ݒ‬௜ = ‫ݐ‬௜ if ݅ ‫ ܲ א‬and ‫ݒ‬௜ = ‫ݎ‬௜ if ݅ ‫ܲ ב‬,
ܸ௞ = ܶ௞ if ݇ ‫ ܲ א‬and ܸ௞ = ܴ௞ if ݇ ‫ ܲ ב‬for any ݇ ് ݅.
݅=1

22
22

© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

ଵfor each subset ܲ of ‫]݊[ = ܫ‬,ܼ௉ = ݁௡ିଵ ܸଵ , … , ܸ௜ିଵ , ‫ݒ‬௜ ‫ܸ כ‬௜ାଵ , ܸ௜ାଶ , … , ܸ௡ = ݁௡ିଵ ‫ݒ‬ଵ ‫ݒ ڮ‬௡ ‫ݔ כ‬, ‫ݔ‬, … , ‫ݔ‬
where¾ For example, for ݊ = 8, and ܲ = 1,3,4,8• ‫ݒ‬௜ = ‫ݐ‬௜ if ݅ ‫ ܲ א‬and ‫ݒ‬௜ = ‫ݎ‬௜ if ݅ ‫ܲ ב‬,• ܸ௞ = ܶ௞ if ݇ ‫ ܲ א‬and ܸ௞ = ܴ௞ if ݇ ‫ ܲ ב‬for any ݇ ് ݅.
ܷ௜ generates the session key ܵ‫ ܪ = ܭ‬ȫ, ܷଵ , … , ܷ௡ , ܴଵ , … , ܴ௡ , ܼூ , … , ܼ‫ ׎‬.

‫ڮ‬ܶ =‫ݔכ ݐ‬‫ڮ‬ܶ =‫ݔכ ݐ‬
Biclique ݊í'+ Protocol ܴܶ == ‫ݔݔ ככ ݎݐ‬‫ڮ‬ܴ =‫ݔכ ݎ‬‫ڮ‬ܴ =‫ݔכ ݎ‬
՜ ‫ڮ‬
‫ ڮ‬՚
(III)
ܼ =݁
ܶ ,…,ܶ ,‫ ܶ כ ݐ‬,ܶ ,…,ܶBiclique ݊í'+ Protocol (II)••Biclique ݊í'+ Protocol (I)Static secret and public keys:
Same as nUM: (‫ݐ‬௜ , ܶ௜ ) are the pair of SSK and SPK of ܷ௜ .

static key
ephemeral key
23

23
23

© Mitsubishi Electric Corporation

Key exchange: we suppose a session executed by ‫ܷ( = ܃‬ଵ , … , ܷ௡ ).
¾ ܷ௜ chooses ‫ݎ‬௜ ՚ோ ‫ ܩ‬as the ESK, and computes ܴ௜ = ‫ݎ‬௜ ‫ ݔ כ‬as the EPK.
Then, ܷ௜ broadcasts ȫ, role௜ ᇲ , ܷ௜ , ܴ௜ to ‫ܷ{ ך ܃‬௜ }.
¾ On receiving ȫ, role௝ ᇲ , ܷ௝ , ܴ௝ for all ݆ ് ݅, ܷ௜ computes
ܼூ = ݁௡ିଵ ܶଵ , … , ܶ௜ିଵ , ‫ݐ‬௜ ‫ܶ כ‬௜ାଵ , ܶ௜ାଶ , … , ܶ௡ , … ,ܼ‫݁ = ׎‬௡ିଵ ܴଵ , … , ܴ௜ିଵ , ‫ݎ‬௜ ‫ܴ כ‬௜ାଵ , ܴ௜ାଶ , … , ܴ௡ as follows:
for all ܲ ‫)ܫ(࣪ א‬, ܼ௉ = ݁௡ିଵ ܸଵ , … , ܸ௜ିଵ , ‫ݒ‬௜ ‫ܸ כ‬௜ାଵ , ܸ௜ାଶ , … , ܸ௡ , where• ‫ݒ‬௜ = ‫ݐ‬௜ if ݅ ‫ ܲ א‬and ‫ݒ‬௜ = ‫ݎ‬௜ if ݅ ‫ܲ ב‬,• ܸ௞ = ܶ௞ if ݇ ‫ ܲ א‬and ܸ௞ = ܴ௞ if ݇ ‫ ܲ ב‬for any ݇ ് ݅.
Then, ܷ௜ generates the session keyܵ‫ ܪ = ܭ‬ȫ, ܷଵ , … , ܷ௡ , ܴଵ , … , ܴ௡ , ܼூ , … , ܼ‫ ׎‬, and completes the session. 24
24© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Security of biclique ݊-DH Protocol

Theorem ( biclique ݊-DH )Need for ݊-Gap DH Assumption

To simulate hash queries and session key reveal queries for
all non-trivial combinations, the ݊-DDH oracle is necessary tokeep consistency.

ାThe biclique ݊-DH protocol is a post-quantum G-CK
secure ݊-party authenticated key exchange protocol fromthe ݊-GDH assumption in the ROM.

¾ If hash function ‫ … ܪ‬, ܼூ , … , ܼ‫ ׎‬is queried, simulator should checkfor all subsets ܲ of ‫ܫ‬, whether ܼ௉ is the form ofܼ௉ = ݁௡ିଵ ܸଵ , … , ܸ௜ିଵ , ‫ݒ‬௜ ‫ܸ כ‬௜ାଵ , ܸ௜ାଶ , … , ܸ௡ where

In particular, for any quantum adversary ࣛ against the biclique ݊-DH
protocol that runs in time at ݊௪ , involves at most ݊௨ honest parties andactivates at most ݊௦ sessions, and makes at most ݊௛ queries to therandom oracle,

by inputting (ܸଵ , … , ܸ௜ିଵ , ܸ௜ , ܸ௜ାଵ , ܸ௜ାଶ , … , ܸ௡ ) to the ݊-DDH oracle.

there exists a ݊-GDH quantum solver ࣭ such that
Adv௡ୋୈୌ
ߣ ൒ min
࣭

1
1
1
1
୥ୡ୩శ
,…,
, ௡ ‫ ڄ‬Adv୆େ௡ୈୌ,ࣛ ߣ ,௡ , ௡ିଵ
௡ିଵ݊௨ ݊௨ ݊௦݊௦݊௨ ݊௦where ࣭ runs in time ݊௪ plus time to perform ܱ( ݊௨ + ݊௦ ߣ) group
operations and make ܱ(݊௛ + ݊௦ ) queries to the ݊-DDH oracle.

‫ݒ‬௜ = ‫ݐ‬௜ if ݅ ‫ ܲ א‬and ‫ݒ‬௜ = ‫ݎ‬௜ if ݅ ‫ܲ ב‬,
ܸ௞ = ܶ௞ if ݇ ‫ ܲ א‬and ܸ௞ = ܴ௞ if ݇ ‫ ܲ ב‬for any ݇ ് ݅.

•
•

25
25

݊-DDH
oraclewell-formedness ofܼ௉ for (any) ܲ ?

hash query for… , ܼூ , … , ܼ‫׎‬

stored / random
value in RO list adversary

yessimulator© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

26
26© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

CKା Secure AKE Protocol from HHS

CK Secure AKE Protocol from HHS

ା¾ Biclique 2-DH: HHS-based CK secure AKE protocol
ܶଵ = ‫ݐ‬ଵ ‫ݔ כ‬

We have one-round two-party
AKE protocols from HHS as
special cases of our AGKE.

ܴଵ = ‫ݎ‬ଵ ‫ݔ כ‬¾ 2-UM: HHS-based CK
secure AKE protocol

ܼଶ = ‫ݎ‬ଵ ‫ܴ כ‬ଶCorollary ( 2-UM )ܼଵ = ‫ݐ‬ଵ ‫ܶ כ‬ଶோభோమܶଶ = ‫ݐ‬ଶ ‫ݔ כ‬

ܶଵ = ‫ݐ‬ଵ ‫ݔ כ‬

ܴଶ = ‫ݎ‬ଶ ‫ݔ כ‬

ܼଵ = ‫ݐ‬ଶ ‫ܶ כ‬ଵܼଵ = ‫ݐ‬ଵ ‫ܶ כ‬ଶ,ܼଶ = ‫ݎ‬ଶ ‫ܴ כ‬ଵܴଵ = ‫ݎ‬ଵ ‫ݔ כ‬

ܼଶ = ‫ݎ‬ଵ ‫ܶ כ‬ଶோభோమܼଷ = ‫ݐ‬ଵ ‫ܴ כ‬ଶ , ܼସ = ‫ݎ‬ଵ ‫ܴ כ‬ଶܵ‫ ܪ = ܭ‬ȫ, ܷଵ , ܷଶ , ܴଵ , ܴଶ , ܼଵ , ܼଶܶଶ = ‫ݐ‬ଶ ‫ݔ כ‬

ܴଶ = ‫ݎ‬ଶ ‫ݔ כ‬

ܼଵ = ‫ݐ‬ଶ ‫ܶ כ‬ଵ ,ܼଷ = ‫ݎ‬ଶ ‫ܶ כ‬ଵ ,ܵ‫ ܪ = ܭ‬ȫ, ܷଵ , ܷଶ , ܴଵ , ܴଶ , ܼଵ , ܼଶ , ܼଷ , ܼସܼଶ = ‫ݐ‬ଶ ‫ܴ כ‬ଵܼସ = ‫ݎ‬ଶ ‫ܴ כ‬ଵCorollary ( biclique 2-DH )The 2-UM protocol is a post-quantum CK secure 2-party
authenticated key exchange protocol under the 2-DDH
assumption in the quantum random oracle model.

ାThe biclique 2-DH protocol is a post-quantum CK secure
2-party authenticated key exchange protocol under the 2GDH assumption in the random oracle model.
27
27© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

28
28© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Previous Works on SIDH-based AKE
SIDH is considered more efficient than CSIDH key exchange.
Therefore, we propose SIDH-based AKE protocols as well.

Very recently, several SIDH AKE protocols have been proposed.
Among them, only Galbraith’s proposal achieves one-round AKE,
however, the security is proved in the CK and random oracle model.

One-Round Authenticated Key Exchange
from SIDH

security
assumption

roundcomplexity

model

SIDH TS2 [Gal18]

SI-CDH

CK

ROM

1-round

AKE-SIDH-SIKE [Lon18]

SI-DDH

CK+

ROM

2-round

LJA [LJA18]

SI-DDHqCK

QROM

2-round

SI-DDH

CK+

ROM

2-roundା

AKEୗ୍ୈୌ-ଶ [XXW 18]

30
30

29
29

© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

SIDH Key Exchange

Our Contributions on SIDH AKE
We propose two efficient one-round AKE from SIDH䠖
1) SIDH UM AKE : secure in CK model under SI-DDH䠄SI Decisional-DH䠅
assumption in QROM.
2) biclique SIDH AKE : secure in CK+ model under di-SI-GDH䠄degreeinsentitive SI Gap-DH䠅assumption in ROM.
security
assumption

model

round
complexity

SIDH TS2 [Gal18]

SI-CDH

CK

ROM

1-round

AKE-SIDH-SIKE [Lon18]

SI-DDH

CK+

ROM

2-round

LJA [LJA18]

SI-DDHqCK

QROM

2-round

AKEୗ୍ୈୌ-ଶ [XXWା18]

SI-DDH

CK+

ROM

2-round

SIDH UM [FTTY18]

SI-DDHCK

QROM

1-roundbiclique SIDH [FTTY18]

di-SI-GDH

CK+

ROM

1-round

We introduce a new di-SI-GDH assumption, a variant of SI-GDH
assumption, for avoiding the GV (Galbraith-Vercauteren)-type attack for
SI-GDH problem.
31
31© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation௘௘㼜㼡㼎㼘㼕㼏㻌㼜㼍㼞㼍㼙㼑㼠㼑㼞㼟䠖 㼜㼞㼕㼙㼑㻌p 㻔㻌㼟㻚㼠㻚 ‫ ݌‬± 1 = ݂ ‫ ڄ‬κ஺ಲ κ஻ಳ 㻕㻘㻌㻌㼑㻚㼓㻚㻘㻌㻌κ஺ = 2, κ஻ = 3
㼟㼡㼜㼑㼞㼟㼕㼚㼓㼡㼘㼍㼞㻌㻱㻯㻌 ‫ॲ ܧ‬௣మ ؄ Ժ/ ‫ ݌‬± 1 Ժ ଶ ‫ ل‬Ժ/κ஺௘ಲ Ժ㼓㼑㼚㼑㼞㼍㼠㼛㼞㼟

Alice߶஺ : ‫ ܧ‬՜ ‫ܧ‬஺ ؔ ‫ ܧ‬Τ ܴ஺߶஺ ܲ஻ , ߶஺ ܳ஻ ‫ܧ א‬஺௘ْ Ժ/κ஻ಳ Ժ

ଶ

Bob

௘
݇஺ ՚ ԺΤκ஺ಲ Ժ ,ܴ஺ ؔ ܲ஺ + ݇஺ ܳ஺ ,ଶ௘‫ܧ‬஺ , ߶஺ ܲ஻ ,߶஺ ܳ஻‫ܧ‬஻ , ߶஻ ܲ஺ ,߶஻ ܳ஺߶஻ : ‫ ܧ‬՜ ‫ܧ‬஻ ؔ ‫ ܧ‬Τ ܴ஻ ,߶஻ ܲ஺ , ߶஻ ܳ஺ ‫ܧ א‬஻߶஺ ܴ஻ = ߶஺ ܲ஻ + ݇஻ ߶஺ ܳ஻߶஻ ܴ஺ = ߶஻ ܲ஺ + ݇஺ ߶஻ ܳ஺‫ܭ‬୅୪୧ୡୣ ؔ ݆ ‫ܧ‬஻ Τ ߶஻ (ܴ஺ )㼟㼔㼍㼞㼑㼐㻌㼗㼑㼥㻦‫ܭ‬୅୪୧ୡୣ = ݆ ‫ܧ‬஻ Τ ߶஻ ܴ஺݇஻ ՚ ԺΤκ஻ಳ Ժ ,ܴ஻ ؔ ܲ஻ + ݇஻ ܳ஻ ,= ݆ ‫ ܧ‬Τ ܴ஺ , ܴ஻㼟㼑㼏㼡㼞㼕㼠㼥㻦 㼎㼍㼟㼑㼐㻌㼛㼚㻌㼠㼔㼑㻌㼕㼚㼠㼞㼍㼏㼠㼍㼎㼕㼘㼕㼠㼥㻌㼛㼒㻌㼏㼛㼙㼜㼡㼠㼕㼚㼓㻌‫ܭ‬୆୭ୠ ؔ ݆ ‫ܧ‬஺ Τ ߶஺ (ܴ஻ )= ݆ ‫ܧ‬஺ Τ ߶஺ ܴ஻= ‫ܭ‬୆୭ୠ

㼒㼞㼛㼙 ‫ܧ‬, ‫ܧ‬஺ , ߶஺ (ܲ஻ ), ߶஺ (ܳ32஻32)© Mitsubishi Electric Corporation

Crypto-Friendly Notation for SIDH

Proposed Biclique SIDH AKE Protocol௘ܵ‫ܭ‬ଵ ؔ ԺΤκଵభ Ժ ,alternative description for simple presentations ofour proposals••••ԭ ؔ ( ‫ܲ ;ܧ‬୅ , ܳ୅ , ܲ୆ , ܳ୆ ),ࣵ ؔ ݇୅
ԭࣵ ؔԭࣶࣵ

Original‫ܧ‬߶஻‫ܧ‬୆ ؔ‫ ܧ‬Τ ܴ஻‫ܧ‬୅ ; ߶୅ ܲ୆ , ߶୅ ܳ୆ؔ ݆(‫ܧ‬୆ Τ ߶୆ (ܴ୅ ) ),߶஺߶஻஺‫ܧ‬୅ ؔ‫ ܧ‬Τ ܴ஺,

ࣶ = ݇୆ ,ԭࣶ‫ ܧ‬Τ ܴ஺ , ܴ஻୙Bob

ؔ ‫ܧ‬୆ ; ߶୆ ܲ୅ , ߶୆ ܳ୅,

initiator

responder

static key of Bob୙୙

ephemeral key of Alice

ԭ

ԭࣵ

ԭࣶ

ԭࣶ
= ԭࣵ ࣶ

ࣵ

33
33© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation୙

calculate ‫ܤ‬ଵ ؔ ԭ ࣶభ , ‫ܤ‬ଶ ؔ ԭ ࣶమई ՚ ܵ‫ܭ‬ଵ , calculate ܺ ؔ ԭ ௫

Crypto-friendly୙ࣶଵ ՚ ܵ‫ܭ‬ଵ , ࣶଶ ՚ ܵ‫ܭ‬ଶ ,calculate ‫ܣ‬ଵ ؔ ԭࣵభ , ‫ܣ‬ଶ ؔ ԭࣵమ
static key of Aliceԭࣵ ࣶ ؔ ݆(‫ܧ‬୅ Τ ߶୅ (ܴ୆ ) ).

߶஺஻୙ࣵଵ ՚ ܵ‫ܭ‬ଵ , ࣵଶ ՚ ܵ‫ܭ‬ଶ ,Alice݁ ؔ κ୅ , κ୆ , ݁୅ , ݁୆ ,௘ܵ‫ܭ‬ଶ ؔ ԺΤκଶమ Ժ ,use only
static keys
ࣵଵ , ‫ܤ‬ଶܻܼଵ ؔ ܻ ࣵభ , ܼଶ ؔ ‫ܤ‬ଶ ई ,ܼଷ ؔ ‫ܤ‬ଶ ࣵభ , ܼସ ؔ ܻ ई ,उ ՚ ܵ‫ܭ‬ଶ , calculate ܻ ؔ ԭ उephemeral key of Bobܼܺଵ ؔ ‫ܣ‬ଵ उ , ܼଶ ؔ ܺ ࣶమ ,ܼଷ ؔ ‫ܣ‬ଵ ࣶమ , ܼସ ؔ ܺ उ ,‫ܭ‬୅୪୧ୡୣ ؔ ‫ܭ‬୆୭ୠ ؔ ‫ (ܪ‬ȫ, ܼଵ , ܼଶ , ܼଷ , ܼସ , Alice, Bob, ܺ, ܻ )use only
static keys
ࣶଶ , ‫ܣ‬ଵ

34
34© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Two Types of SI-Gap-DH Problem (II)Two Types of SI-Gap-DH Problem (I)We have two types of SI-GDH problems according to the SI-DDH oracle.

ds-, di-SI-GDH problems
Let ࣭ be a quantum machine adversary䠊¾ degree-sensitive SI-GDH (ds-GDH) problem䠖
The ds-DDH oracle answers true ifᇱthere exists a supersingular EC ‫ܧ‬୅୆
and a commutative diagram below s.t.

ୖFor pk ୱ୧ୢ୦ = (ԭ ؔ ‫ܲ ;ܧ‬୅ , ܳ୅ , ܲ୆ , ܳ୆ , Ղ ؔ κ୅ , κ୆ , ݁୅ , ݁୆ ) ՚ Genୱ୧ୢ୦ (1ఒ )୙୙•and ࣵ ՚ ܵ‫ܭ‬୅ , ࣶ ՚ ܵ‫ܭ‬୆ , ࣭ receives ( pk ୱ୧ୢ୦ , ԭࣵ , ԭ ࣶ ), and ࣭ accesses theᇱᇱᇱᇱSI-DDH oracle for any input ࣲ = ( pk ୱ୧ୢ୦ , ‫ܧ‬୅ᇱ ; ܲ୅୆, ܳ୅୆, ‫ܧ‬୆ᇱ ; ܲ୆୅
, ܳ୆୅
,
ᇱ
ᇱ
ᇱ
ᇱ
ᇱ
ᇱ
ᇱ
ࣺ ) where ܲ୅୆ , ܳ୅୆ (resp. ܲ୆୅ , ܳ୆୅ ) are points in ‫ܧ‬୅ (ॲ௣మ ) (resp. ‫ܧ‬୆ (ॲ௣మ ))and ࣺԢ ‫ॲ א‬௣మ , and then outputs ࣺ ‫ॲ א‬௣మ . If ࣺ = ԭࣵ ࣶ = ԭ ࣶ

ࣵ

•

௘

ᇱ
degree ݀୅ᇱ of ߶୅ᇱ (and ߶୆୅) satisfies ݀୅ᇱ = κ୅ఽ and௘ᇱᇱᇱ
degree ݀୆ of ߶୆ (and ߶୅୆ ) satisfies ݀୆ᇱ = κ୆ా

ᇱ
ᇱ
ᇱ
ᇱ
ᇱ
ܲ୅୆
= ߶୅ᇱ ܲ୆ , ܳ୅୆= ߶୅ᇱ ܳ୆ , ܲ୆୅= ߶୆ᇱ ܲ୅ , ܳ୆୅= ߶୆ᇱ ܳ୅ and ࣺᇱ = ݆(‫ܧ‬୅୆
).

¾ degree-insensitive SI-GDH (di-GDH) problem䠖
The di-DDH oracle answers true ifᇱand a commutative diagram below s.t.
there exists a supersingular EC ‫ܧ‬୅୆, ࣭ wins.

According to the behavior of SI-DDH oracle, we have the following two
types of SI-GDH problems, i.e.,••¾ degree-sensitive SI-GDH (ds-GDH) problem and¾ degree-insensitive SI-GDH (di-GDH) problem.

35
35© Mitsubishi Electric Corporation© Mitsubishi Electric Corporationᇱ
degree ݀୅ᇱ of ߶୅ᇱ (and ߶୆୅) is a power of κ୅ andᇱᇱᇱ
degree ݀୆ of ߶୆ (and ߶୅୆) is a power of κ୆

ᇱ
ᇱ
ᇱ
ᇱ
ᇱ
ܲ୅୆
= ߶୅ᇱ ܲ୆ , ܳ୅୆= ߶୅ᇱ ܳ୆ , ܲ୆୅= ߶୆ᇱ ܲ୅ , ܳ୆୅= ߶୆ᇱ ܳ୅ and ࣺᇱ = ݆(‫ܧ‬୅୆
).

߶୆ᇱ

‫ܧ‬

‫ܧ‬୆ᇱ

߶୅ᇱ

ᇱ
߶୆୅

‫ܧ‬୅ᇱ

ᇱ
߶୅୆

ᇱ
‫ܧ‬୅୆

ᇱ
݀୅ᇱ = deg ߶୅ᇱ = deg ߶୆୅ᇱ݀୆ᇱ = deg ߶୆ᇱ = deg ߶୅୆36
36© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Solving ds-SI-GDH Problem by GV-type Attack

Galbraith-Vercauteren (GV) Attack

Attack for ds-SI-GDH problem using ds-SI-DDH oracle.

Attack for SIDH isogeny problem using the decision degree (DD) oracle
for SIDH isogenies.

¾ Solver ࣭ obtains the following ds-SI-GDH problem instance.

¾ Solver ࣭ obtains the following SIDH isogeny problem instance( pk ୱ୧ୢ୦ = (ԭ ؔ ‫ܲ ;ܧ‬୅ , ܳ୅ , ܲ୆ , ܳ୆ , Ղ ؔ κ୅ , κ୆ , ݁୅ , ݁୆ ),‫ܧ‬୅ , ܲ୅୆ ؔ ߶୅ (ܲ୆ ), ܳ୅୆ ؔ ߶୅ (ܳ୆ ), … )( pk ୱ୧ୢ୦ = (ԭ ؔ ‫ܲ ;ܧ‬୅ , ܳ୅ , ܲ୆ , ܳ୆ , Ղ ؔ κ୅ , κ୆ , ݁୅ , ݁୆ ),௘
where ߶஺ : ‫ ܧ‬՜ ‫ܧ‬஺ is an κ୅ఽ -isogeny, and the goal of ࣭ is to reveal ߶୅ 䠊‫ܧ‬୅ , ܲ୅୆ ؔ ߶୅ (ܲ୆ ), ܳ୅୆ ؔ ߶୅ (ܳ୆ ))௘ఽ
where ߶஺ : ‫ ܧ‬՜ ‫ܧ‬஺ is an κ୅ -isogeny, and the goal of ࣭ is to reveal ߶୅ 䠊

¾ ࣭ calculates ‫ א ݑ‬Ժ such that ‫ ڄ ݑ‬κ୅ ‫ ؠ‬1 (mod κ୆ )and then κ୅ -isogeny ߰: ‫ܧ‬୅ ՜ ‫ܧ‬Ԣ. ࣭ sends‫ܧ‬෪ ୱ୧ୢ୦ = (ԭ, ݁ǁ ؔ κ୅ , κ୆ , ݁୅ െ 1, ݁୆ ,( pk
‫ ܧ‬ᇱ , ‫ܲ(߰ ڄ ݑ‬୅୆ ), ‫ܳ(߰ ڄ ݑ‬୅୆ ))

߶୅

‫ܧ‬Ԣ

‫ܧ‬Ԣ

߰

‫ܧ‬Ԣ ?

¾ ࣭ calculates ‫ א ݑ‬Ժ s.t. ‫ ڄ ݑ‬κ୅ ‫ ؠ‬1 (mod κ୆ )and then κ୅ -isogeny ߰: ‫ܧ‬୅ ՜ ‫ܧ‬Ԣ, and௘ᇱκ୆ా -isogenies ‫ ܧ‬՜ ‫ܧ‬୆ᇱ , ‫ܧ‬Ԣ ՜ ‫ܧ‬୅୆
s.t. the right
diagram is commutative. ࣭ sends෪ ୱ୧ୢ୦ = (ԭ, ݁ǁ ؔ κ୅ , κ୆ , ݁୅ െ 1, ݁୆ ,
( pk

‫ܧ‬୅

ᇱ
‫ ܧ‬ᇱ , ‫ܧ‬୆ᇱ , … , ݆(‫ܧ‬୅୆
))

௘ ିଵ

to the DD oracle. The oracle distinguishes whether ‫ܧ‬Ԣ is κ୅ఽ ௘ ାଵ
isogenous to ‫ ܧ‬or κ୅ఽ - isogenous to ‫ܧ‬, i.e., whether ߰ is abacktracking step on the path given by ߶஺ . By repeating this, ࣭reveals ߶୅ .

37
37

© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Security of Biclique SIDH AKEfrom di-SI-GDH Assumption

‫ܧ‬

‫ܧ‬୆ᇱ

߶୅

‫ܧ‬Ԣ

‫ܧ‬Ԣ

߰

‫ܧ‬Ԣ ?

‫ܧ‬୅

ᇱ
‫ܧ‬୅୆

to the ds-SI-DDH oracle. The oracle distinguishes whether ߰ is abacktracking step on the path given by ߶஺ . By repeating this, ࣭reveals ߶୅ .

38
38

© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

References

Theoremା

The biclique SIDH protocol is a post-quantum CK -secure authenticated
key exchange protocol under the di-SI-GDH assumption in the random
oracle model.

[FTTY18] A. Fujioka, K. Takashima, S. Terada, K. Yoneyama,“Supersingular Isogeny Diffie-Hellman Authenticated Key
Exchange”, to appear in ICISC 2018,
full version: ePrint Archive 2018/730¾ To distinguish the degree of isogeny (or distance between two elliptic
curves in the κ୅ -isogeny graph) is crucial for the GV-type attack.

[FTY18] A. Fujioka, K. Takashima, K. Yoneyama,“One-Round Authenticated Group Key Exchange from
Isogenies”, ePrint Archive 2018/1033¾ The GV-type attack adversaries have no advantages in the di-SI-GDH
problem, where the decision oracle cannot distinguish the degree of
isogeny.
¾ Therefore, (in contrast to the ds-SI-GDH problem,) we may assume thatthe di-SI-GDH problem cannot be solved by any efficient adversaries,
and can be used for the basis of the security of our biclique scheme.
39
39© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

40
40© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

Conclusions
We proposed two one-round AGKE protocols from
Cryptographic Invariant Maps (CIMs).

Thank you for your attention

We instantiate the proposed protocols on HHS withlimitation where the number of the user group is two.
In particular, the protocols instantiated by CSIDH are
currently more realistic than the general ݊-party
CIM-based ones.

We also proposed two one-round AKE protocols from
SIDH, which is more efficient.

41
41© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation

42
42© Mitsubishi Electric Corporation© Mitsubishi Electric Corporation