type
status
date
slug
summary
tags
category
icon
password
基于椭圆曲线同源的后量子密码学习记录
符号说明
符号 | 解释 |
域 | |
环 | |
域的代数闭包 | |
or | 一个维的射影空间 |
-有理点 | |
[n] | |
函数域 | |
or or | 域上面的平面射影曲线 |
素数的幂 | |
有限域(个元素) | |
有限域的代数闭包 |
高等代数
代数闭域：指对每个非常值一元多项式都有根的域，即对代数方程求解操作是封闭的，亦即对于任意，都存在使得
代数闭包：包含的最小代数闭域，就是向域中添加非常值多项式的根扩张得到的域
环的特征：对于一个环，如果存在正整数使得对于任意的成立且是满足该条件的最小整数，则称为环的特征。域的特征与环的特征类似，有限域的特征一定是素数。
torsion-free Z-module
- 桡元素：存在一个非零元素使得，对于模中的任意元素有，称为桡元素
- 对于模中的任何非零元素，都不会存在一个非零元素使得，即仅有这一个桡元素
如果环 中的任意元素 满足 ，则要么 要么 ，那么我们称环 没有零除子(即不存在两个非零元素使得)。没有零除子的环也被称为整环（integral domain）
galois扩张：
伽罗华群
整数环：对于一个代数数域,其整数环是中所有代数整数组成的集合，代数整数是首一多项式的根。或者说，当且仅当环中不存在零因子被称为整环。
二次域：一个二次域是形如的扩域，其中d不能被平方数整除（即不是一个平方数），除了1。根据的值可以分为二次实数域和二次虚数域（）。二次虚数域中元素形式为：.二次虚数域的整数环，其中或者
- 的整数环：,判别式为。整数环为：
- 的整数环：,判别式为。整数环为：
四元数代数：给定两个非零有理数，构造一个四元数代数，是一个四维代数，其中
- 分裂(split):A同构于一个的矩阵代数，在Q上分裂当且仅当存在使得这个方程有解
- 分歧：即不同构于一个的矩阵代数
：一个是一个集合，并且该集合满足阿贝尔群结构并且对于标量乘法有
是一个代数结构，并且不需要满足交换律，一个的阶（order）是的子环，并且它是一个module，满足
循环群的光滑阶(smooth order)：令是一个循环群中的元素，其阶为，如果的所有素因子都不超过某个给定的正整数，则称是光滑的。
例如，模23的乘法群中，元素3的阶为5，对于一个给定的B=5，3的阶就是一个5光滑数。
分式理想和类群
- 分式理想是一个整数格
- 四元数代数的分式理想是一个秩为4的整数格
- 理想的范数是
- 阶子环是一个理想，最大阶子环是指不被其他阶子环所包含
- 左阶子环
- 当时，理想是一个整数理想
- 两个理想等价，当且仅当
p-进数域
- p进赋值，给定素数p，对于任意，将其写为分数形式，其中是整数且.定义p进赋值为，即素因数分解中的幂数。例如，，.
- p-进绝对值：
- p-进数域中，每个数都可以表示为无穷多项式级数：，其中.
仿射
定义1.1 n维仿射空间（Affine space）是多个n元组组成的集合，其中任意
定义1.2 n维仿射空间的-有理点是由以下n元组组成的集合，其中任意
定义1.3 仿射平面（Affine plane）：仿射平面是仿射空间在时的特例。仿射平面由一组线、一组点，以及一个点与线之间的重合关系所组成，并具有以下性质
- 给定任意两个不同的点，恰有一条线重合两个点
- 给定任意直线 l 及任意不与 l 重合的点 P，恰有一条与 P 重合，且不与 l 相交的线
- 存在4个点，使得没有线能重合两个以上的这些点。
- 仿射平面就是从射影平面出发，移除一条直线以及与该直线重合的所有点，即存在平行线。
定义1.4 仿射平面曲线是指中一个不可约多项式的零点集，即
定义1.5 给定仿射平面曲线，对于点，若，则称点为奇异点，该曲线为奇异的。否则称为光滑的。当曲线是非奇异的，其在点的切线为
射影
定义2.1 射影空间(projective space)：一个维的射影空间是一个所有满足以下要求的维元组组成的集合：
- 存在一个满足一个模等价关系
- 一个射影点的等价类通常表示为
定义2.2 n维-有理数点的集合表示为
定义2.3 无穷远空间(space at infinity)：对于一个维射影空间，固定，得到一个维的射影空间，称该射影空间为无穷远空间。无穷远空间中的点叫做无穷远点(points at infinity)
定义2.4 射影平面(projective plane): 射影平面就是射影空间的一个特例，此时，即。具体地说，射影平面由形如这样的点构成，其中且不全为，并且对于任意非零的都有。
从几何角度来看，射影平面由一组线、一组点，以及一个点与线之间的重合关系所组成，并具有以下性质:
- 给定任意两个不同的点，恰有一条线会重合这两个点
- 给定任意两条不同的线，恰有一个点会重合这两条线
- 存在四个点1，使得没有线可以重合两个以上的这些点
将一般的欧氏平面变换成射影平面的步骤如下：
- 将每组平行线附加上一个新的点。该点可被视为重合该组的每条线。不同组平行线会得到不同的点。这些点被称为无穷远点。
- 增加一条线，让该线视为重合所有（且只有）无穷远点。该线被称为无穷远线。
仿射&射影
仿射平面曲线和射影平面曲线之间存在着映射关系
齐次退化：射影平面曲线到仿射平面曲线
齐次化：仿射平面曲线到射影平面曲线
射影平面曲线上的无穷远点：当时，代入射影平面曲线方程和仿射平面曲线方程得到的值，即为无穷远点的坐标。
射影空间到仿射空间以及仿射空间到射影空间就是对上述映射推广至维即可。
对于任意交换环，一个齐次多项式，使用表示多项式中非零项的最大多项式次数，总会存在一个独一无二的齐次多项式满足并且，可以通过使用替换多项式的每一项得到多项式
仿射平面曲线映射到射影平面曲线的例子：
以第四个仿射平面曲线为例，从仿射平面曲线到射影平面曲线，经过映射得到，进一步化简即可得到射影平面曲线方程：。对于射影平面曲线上的无穷远点的计算，当时代入射影平面曲线，得到，再代入仿射平面曲线，得到或，根据射影空间的定义，可以将无穷远点记为。显然取或者时.
椭圆曲线
曲线的亏格(Genius)：曲线的亏格是代数几何和代数拓扑中的一个基本概念。在数学上，亏格有几个不同但密切相关的含义。最常见的概念是曲面的亏格，它指的是曲面上“孔”的数量。对于一个曲面来说，如果最多可以画出n条闭合曲线而不将曲面分开，则称该曲面的亏格为n。例如，球体和圆盘的亏格都是零，而圆环的亏格是一。
曲线光滑：光滑曲线是指曲线在其定义域内的每一点都是光滑的，即没有尖点、尖角或断点，并且曲线的导数（包括高阶导数）在这些点上都是连续的。如果一条曲线在某一点或某些点上存在奇异点，那么它在这些点上就不满足光滑曲线的定义。
椭圆曲线：椭圆曲线是一条光滑曲线并且亏格为1，同时有一个特定的基点。椭圆曲线是定义在射影空间上面的，仿射形式的椭圆曲线方程仅仅是为了简化计算。椭圆曲线的无穷远点在仿射空间其实是不存在的。
仿射映射：不会改变Weierstrass方程的形式当且仅当以下条件成立：
- 矩阵
- ，且
因此令，得到一个同样可以保证Weierstrass方程形式不变的新仿射映射，该变换的逆如下：
两条曲线是同构的当且仅当可以通过上述仿射变换转变为(上述仿射映射首先满足同态性，其次是一个双射，所以是一个同构)
Weierstrass方程：任意定义在域上的椭圆曲线都可以写成以下这种形式：
基点为无穷远点。当时，可以通过可逆变化对标准的Weierstrass方程进行化简。令得到如下形式的Weierstrass方程（因为，所以）.对于标准形式的Weierstrass方程定义如下一系列变量。
其中被称为不变量，被称为判别式。
进一步，如果，继续通过可逆变化对Weierstrass方程进行化简。令得到如下形式的Weierstrass方程
一个满足Weierstrass方程的曲线必然满足以下性质：
- 是非奇异的当且仅当判别式
- 有一个叉点当且仅当
- 有一个尖点当且仅当
- 对于任意一个椭圆曲线，j-不变量定义为.两个椭圆曲线是同构的当且仅当它们的j-不变量相等.
证明思路：首先对于标准的射影Weierstrass方程证明无穷远点不是奇异点(通过求偏导)，随后假设存在一个奇异点，然后去化简标准的Weierstrass方程，得到。根据叉点和尖点的定义，当且仅当有两个不同的根时，即有叉点。时有尖点。第4点的证明是根据不变量相等去找到仿射变换使得即可。
椭圆曲线的群运算规则
定义了无穷远点的有关运算，通过计算过的切线与椭圆曲线相交的方式来得到以下运算规则（的Weierstrass方程）。标准形式的Weierstrass同样可以根据这样的方式去推导。
满足上述运算规则定义了一个阿贝尔群。
奇异椭圆曲线：对于一个定义在有限域()，那么该椭圆曲线也是奇异的。对于一个奇异椭圆曲线，去除奇异点之后仍然还是可以构成一个满足椭圆曲线运算规则的阿贝尔群。
其他类型的椭圆曲线：根据Montgomery等式得到一个椭圆曲线
- Montgomery等式：并且满足
- 任意Montgomery等式可以转变为Weierstrass等式
Montgomery 曲线可以转换为 Weierstrass 曲线，下面给出转换过程：
考虑到 Montgomery 相比 Weierstrass 左侧多了一个的因子，采用变量代换把它消除，
此时距离 Weierstrass form 就差等式右边的的次数，目标是,现在是,因此要把项消掉，设
,则
此时就是符合 Weierstrass form 椭圆曲线上的一点。
- Montgomery曲线能够实现更快的运算。
twist：
同源
函数域：是一个平面射影曲线并且是一个非常值的齐次多项式，多项式在代数闭包中是不可约的。函数域是一个满足以下条件的有理函数的集合：
- 都是中的齐次多项式，并且
- 不能整除(并不是由理想中的元素，因为如果h是理想中的元素，那么必然有，即会整除)
- 当时，，此时对于任意使得，有。对于单个，如果，可能会存在一个，且
构成了一个环，并且任意非零元素都有逆元，所以是一个域。（当时，的逆元就是，否则，，这是因为）
对于任意射影等价类，由于是齐次多项式，因此可以得到
是一个平面射影曲线，并且存在一个，当且仅当可以表示为，称在点正则。
是域上面的两条平面射影曲线，一个有理映射是一个射影三元组，使得对于任意都是被定义的并且不全为0，并且在射影曲线上。有理映射是被定义的，当且仅当存在使得是在点被定义的。当上述有理映射可以在任意点被定义，称该有理映射为一个态射。
对于两个曲线之间的态射要么是常值映射，要么是一个满射。
证明：
是一个映射且满足，是一个定义在上的非常值态射：。是函数域中的一个函数（定义了一个有理映射，可以将曲线上的点映射到1维的射影空间，即，这是因为函数域的定义，函数域中的元素是这样的标准形式）。
对于定义在上的两条曲线，给定一个定义在上的非常值态射：，那么函数域是的一个代数扩张。
对于两个曲线之间的态射，当是一个常值映射时，，否则(代数扩张因子)
同源映射：对于两条椭圆曲线，同源映射是一个态射（非常值的有理映射）并且可以将上的无穷远点映射到上面的无穷远点，即
同源映射的具体实例：
- negation map：对于一个映射.显然它是一个有理映射，并且在任意点都被定义，因此是一个态射。同时，可以将无穷远点映射到其本身，因此是一个同源。进一步，它是一个的同源，因此是一个自同构。
- Frobenius自同态：映射.
从几何角度来说，同源就是将一条椭圆曲线上的点映射到了另一条椭圆曲线，并且保证无穷远点永远会被映射到无穷远点，即保持不变。从代数角度来说，同源映射是一个群同态
椭圆曲线是同源的，当且仅当存在一个同源映射并且，即不会将上的所有点都映射到无穷远点。
由于椭圆曲线是一个阿贝尔交换群，因此椭圆曲线上的同源映射也组成了一个群。对于所有从的同源映射组成了一个群，即.
证明：首先，对于任意两个同源映射运算后还是一个同源映射，满足封闭性。，满足结合律。单位元为，任意的逆元为，同时满足交换律，因此是一个阿贝尔交换群。
当同源映射是从，那么一系列这样的同源映射集合对于加法和组合构成了一个环，即。加法运算与上述相同，组合运算是指.此时的环是一个自同态环，环中的所有可逆元构成了一个自同构环。
证明：首先，对于构成一个群，只需要证明满足分配律，即，则构成环。
例子：，椭圆曲线点的倍乘构成一个同源，一系列的这种同源映射构成了一个自同态环
一个定义在域上的椭圆曲线的自同态环要么同构于有理数域，要么同构于一个二次虚数域的阶，要么同构于一个四元数代数的阶。
- 是一个定义在域上的椭圆曲线，，那么是一个非常值映射
- 群是一个torsion-free Z-module
- 环的特征为0且没有零除子
证明：对于性质1，首先判断m为偶数时，此时等价于判断是否等于。分和两种情况，分别证明。当m是奇数时，只需要证明存在一个非无穷远点的二阶点即可，因此（直观去理解性质1就是，当m是偶数时，不会出现所有点的阶数都为2，当m为奇数时，必然会有一个点的阶数为2且不为无穷远点）。对于性质2，根据torsion-free Z-module的定义，对于任意，有。因此要么，要么。对于性质3，根据性质2可知，的特征为0（环特征的定义与torsion-free Z-module类似），当且仅当或者(因为，)。因此是一个整环但不一定是交换环（超奇异椭圆曲线上面就不是交换环）。
椭圆曲线上的阶饶子群是一系列阶为的点组成的集合，即。椭圆曲线的饶子群就是这些不同阶数的饶子群的并集。
同源映射满足群同态，即
证明：没看明白，后面补充
同源映射核：对于一个非零的同源映射，它的核为是一个有限群。从定义上来看，这个核就是的一个子群，由所有能够通过同源映射映射到无穷远点的所有点构成。
同源映射可分：同源映射的可分性与核的结构密切相关。可分性指的是同源映射的核中没有重复的点，而不可分性则表示映射的核中包含了某些“重复的点”，即不同的点不会被同源映射到同一个点。
同源映射的核中点个数，其中是可分同源映射的
证明涉及代数几何，待补充。。。
给定两个非常值同源映射和，如果是可分的且，则存在一个唯一的同源映射满足
给定一个椭圆曲线以它的一个有限子群，那么存在一个唯一的椭圆曲线和一个可分同源映射并且该同源映射的核为
一个合数阶的同源映射通常可以划分为一系列素数阶的同源映射的组合。
因为任意定义在特征为的域上的椭圆曲线的同源映射都可以写作一个可分同源映射和Frobenius映射的组合。显然，Frobenius映射可以分解为一系列阶为的素数同源映射。因此只需要考虑可分的同源映射。是一个非平凡的阿贝尔群，因此根据阿贝尔群的分解定理，可以分为多个素数解群的直积。同时，对于一个定义在特征为的域上的椭圆曲线，给定一个有限子群，必然存在一个同源映射,并且该同源映射的核为有限子群G。这也是合数阶同源映射可以多个素数阶同源映射的组合的原因。
对于一个非常值同源映射且，则存在一个唯一的对偶同源并且满足(这是一个标量点乘同源映射)。对偶同源满足以下性质成立：
给定两条椭圆曲线和，是一个同源，同源映射的仿射标准型如下：
其中，
- 对于上述定义的同源的仿射基本形式满足
- 对于任意的仿射点，当且仅当或者时
- 当的导数是非零时，被称为可分离的(separable)
- 同源映射还可以写为，其中
对于任意仿射点，同源映射的核，显然构成了一个子群。
任意定义在特征为的域上面的椭圆曲线间的同源映射都可以写作一个separable同源映射和一个阶Frobenius态射的组合形式：
所有的素数度的可分同源映射的核的阶要么为2要么为奇数
同源映射计算的具体过程如下：
- 确定核子群：找到同源映射的核，这是的一个子群，由所有构成.
- 枚举椭圆曲线上的所有点以及无穷远点：枚举，计算得到
- 寻找一个阶为的子群，找到一个生成元满足，如果这样的点存在，则就是核子群。
- 构造同源映射：通过公式和核子群构造同源映射
Velu公式（核的阶为2）：给定定义在上的一个椭圆曲线以及是的一个根。令，存在下列有理映射
是一个可分的同源映射：，其中.该同源映射的核为一个阶为2的群
Velu公式（核的阶为奇数）：给定定义在上的一个椭圆曲线，是一个奇数阶的有限子群，对于每个非零点，定义变量
计算三元组
计算有理映射
是一个可分的同源映射：，其中，它的核为有限子群
从理想到同源：
- 由理想生成的饶子群：对于一个二次虚数域或者四元数代数的阶子环，给定一个理想，理想的饶子群定义为
- 由理想生成的同源：对于一个二次虚数域或者四元数代数的阶子环，给定一个理想，该理想对应的同源是，该同源映射的核为，并且该同源映射的度为，其中表示范数。
- 实例：
有限域上的椭圆曲线
Hasse定理：定义在有限域椭圆曲线，椭圆曲线上的点数为
证明：首先，对于一个定义在有限域中的椭圆曲线，每个，都有。因此当且仅当存在二次剩余的时候才会有且必然为2个解。对于一个模来说，二次剩余只会有一半，因此最多为个点和一个无穷远点。考虑Frobenius 同态，它是有限域上的自同态，满足：，其中。从 Frobenius 同态可以得到两个根，即 Frobenius 特征值。它们是复数，满足以下性质.这两个根的重要性质是它们的绝对值均为 由的性质，点数可以写成：.估计的大小。由于是模 的复数，即，因此： 于是，点数满足：
椭圆曲线称为超奇异的，如果中没有阶点，即阶扭子群
若，则是超奇异的当且仅当
Waterhouse: 给定有限域，整数，则存在定义在上的椭圆曲线且，当且仅当下述条件之一满足：
- m是偶数时，且
- 且
- 且
- m是奇数，且
- 且
- 且
当且仅当第一种情况下，椭圆曲线是普通的，其余情况下椭圆曲线是超奇异的
仅在2.a这种情况下超奇异椭圆曲线的自同态环是构于一个四元代数的最大阶，其余情况下自同态环是同构于一个二次虚数域的阶
给定一个椭圆曲线且，当且仅当时，是超奇异椭圆曲线，否则为普通椭圆曲线。
给定一个椭圆曲线且，当且仅当时，说超奇异椭圆曲线，否则为普通椭圆曲线。
超奇异椭圆曲线：一个定义在有限域的椭圆曲线被称为超奇异椭圆曲线当且仅当它的自同态环（自同态环的定义见同源部分）在代数闭包上是不可交换的。
超奇异椭圆曲线与普通奇异椭圆曲线的对比
属性 | 普通椭圆曲线 | 超奇异椭圆曲线 |
Frobenius特性 | ||
端同构环 | 二次虚数域的整数环 | 四元数代数 |
曲线的阶数 | 多样 | 唯一，固定为 |
同源图 | 稠密分布 | 扩展图结构 |
- Frobenius自同态的特征多项式为，其中是Frobenius轨迹，与椭圆曲线点的阶数关系为：.对于普通椭圆曲线，Frobenius轨迹满足.在超奇异椭圆曲线中。此时
- 普通椭圆曲线的端同构环为一个秩为2的整数环，通常是二次虚域的整数环，其中是判别式。它是一个交换代数结构。超奇异同源曲线的同构环是一个四元数代数，非交换
超奇异椭圆曲线的j-不变量通常都会在中，因此在考虑的代数闭包上的超奇异同源图时，通常都只考虑定义在有限域上定义的椭圆曲线。假设所有j-不变量在上的超奇异椭圆曲线组成的集合为
假设表示所有j-不变量在上的超奇异椭圆曲线组成的集合，那么有以下等式成立：
其中表示二次虚数域的理想类群的类数，即理想类群的大小
同源图
同源图是一个有限图，其中：
- 节点：表示椭圆曲线，通常由-不变量表示
- 边：表示两条椭圆曲线之间的一个同源映射
同源图的正则性：对于固定的素数，在有限域上，同源图是一个正则图：
- 每个节点与个其他节点相连
- 每条边对应一个-同源，即同源的
同源图的连通性：同源图是连通的，在固定的-不变量空间（特定类型的椭圆曲线，如普通椭圆曲线或超奇异椭圆曲线）中，总能通过一系列-同源从一个节点到达另一个节点。
模多项式是一个对称二元多项式，用于计算一个阶为的同源。该多项式满足以下性质：
- ，当且仅当和之间存在一个-同源
- 的次数为
模多项式的一般形式是：
其中。对于小素数,可以明确写出模多项式。例如：
·当
·当
随着的增大，模多项式的复杂度显著提高。
同源图构造的例子：
对于一个模多项式：
给定一个椭圆曲线，，根据模多项式构造一个的有限域的超奇异同源图，具体流程如下：
- 代入到模多项式
- 对模多项式进行分解（因为在代数闭包上多项式一定可以分解为一次项的乘积），因此是一个一元二次多项式的两个根。
- 超奇异同源图的节点为-不变量，在该例子中就是
- 计算的根
- 若存在解，那么解就是一个椭圆曲线的，且之间存在一个同源映射，即同源图中的两个节点之间有一条边，得到最终的同源图
基于同源的计算性困难问题
标准的同源计算困难问题：给定，寻找一个同源映射，并且对于这个同源映射必然会有
在给定模多项式以及时，模多项式方法可以有效判断椭圆曲线之间是否存在同源映射，但是并不能找到这个同源映射。
标准的同源判断性问题，即判断两条曲线之间是否存在同源映射并不是一个困难问题。因为两条椭圆曲线之间存在同源映射当且仅当，这是一个多项式时间内可以解决的。
此外，根据一个模多项式是否有解同样可以很容易判断是否存在同源映射.
判定性超奇异同源问题（Decisional Supersingular Isogeny,DSSI）给定素数，其中是互不相同的小素数，是一个正整数，是一个小的代数余子式（small cofactor）是一个阶为的定义在上的超奇异椭圆曲线。给定另一个定义在的椭圆曲线且，判断是不是的一个-同源
超奇异计算性 Diffe-Hellman(SSCDH)问题：令是核为的同源，是核为的同源，其中是从中随机选取且不同时整除给定曲线和点,找到的-不变量
超奇异判定性Diffe-Hellman(SSDDH)问题：给定以 1/2 概率采样的两种分布如下，给定一个元组，判断该元组从以下那个分布中进行采样得到的.
- ,其中和超奇异计算性Diffie-Hellman问题中的相同，且 . 从 中随机选择且不能同时被 整除.
- ,其中和超奇异计算性Diffe-Hellman问题中的相同，且,其中从 中随机选择且不能同时被 整除.
Modified Supersingular Cpomputational Diffie-Hellman(MSSCDH):令是核为的同源，是核为的同源，其中是从中随机选取且不同时整除 给定，找到
超奇异孪生计算性 Diffe-Hellman问题：令是核为的同源，是核为的同源，是核为的同源，其中是从中随机选取且不同时整除给定曲线和点,找到和的-不变量.
超奇异孪生判定性Diffie-Hellman问题：给定以 1/2 概率采样的两种分布如下，给定一个元组，判断该元组从以下那个分布中进行采样得到的.
- ,其中和超奇异孪生计算性Diffe-Hellman问题中的相同，且 以及. 从 中随机选择且不能同时被 整除.
- ,其中和超奇异孪生计算性Diffe-Hellman问题中的相同，且 以及其中从 中随机选择且不能同时被 整除.
超奇异同源Gap Diffie-Hellman问题(SSGDH)：令是核为的同源，是核为的同源，其中是从中随机选取且不同时整除 给定敌手，同时敌手针对任意输入，其中，可以访问一个SSDDH预言机并得到输出结果。敌手需要找到找到的-不变量.
根据预言机行为的不同可以进一步分为两类问题:
- degree-sensitive-SSGDH:当且仅当存在一个超奇异椭圆曲线以及同源使得以下三个条件成立时，SSDDH预言机输出，否则输出.
- 以及
- degree-insensitive-SSGDH：与degree-sensitive-SSGDH不同之处在于条件a.，其余条件保持不变。仅在以下条件成立时，SSDDH输出，否则输出.
. 以及
.
.
表示一个定义在有限域上的椭圆曲线的集合。该集合中的椭圆曲线的自同态环都是（是一个二次虚数域的阶）并且Frobenius自同态映射的迹。给定一组椭圆曲线，找到理想是困难的，其中是一个理想类群的左作用。
超奇异同源的辅助点计算问题(Supersingular Isogeny Auxillary Point Computation, SI-APC)
令是核为的同源，其中是从中均匀随机选择的。给定，计算点是困难的。
计算性超奇异同源问题(Computational Supersingular Isogeny, CSSI)
令是核为的同源，其中是一个阶为的随机点。给定,找到一个核子群生成元是困难的。
判定性超奇异乘积问题（Decisional Supersingular Product,DSSP）
令是一个的同源，给定一个以 1/2 概率从以下两种分布中采样得到的元组，判断该元组是从那个分布中选取的.
- 选择一个阶为的随机点，且
- 是一个随机选择的超奇异椭圆曲线且，是一个随机同源且
同源星：给定一个所有定义在有限域上且具有相同阶的椭圆曲线组成的集合，挑选（表示Forbenius自同态映射所对应的特征方程的判别式）和素数并且需要满足勒让德符号=1。此时，中所有-同源就形成了一个圈。挑选不同的满足需求的素数重复上述过程得到不同的-同源圈。所有-同源圈复合构成的图被称为同源星。
例子：有限域上的一个同源星
当足够大时，-同源圈也足够多，进而形成了非常复杂的同源星。
同源星上的同源搜索计算问题：在一个同源星上，计算个同源映射组成的同源链（如下所示）是困难（时间复杂度是输入规模的指数级）的。
SIDH密钥协商
SIDH密钥协商由以下算法组成：
- 给定安全参数，选择两个不同的小素数(通常为2，3) ，选择两个整数使得是一个素数且.选择一个初始的定义在有限域的椭圆曲线，以及该椭圆曲线的阶饶子群的生成元.
- : Alice和Bob分别选择两个秘密整数，计算有限循环子群以及，然后根据以这两个有限循环子群为核子群计算两个同源映射和
- ：Alice发送给Bob，Bob发送给Alice
- Alice以有限循环子群为核子群计算同源映射. Bob以有限循环子群为核子群计算同源映射.最后，Alice和Bob以-不变量作为协商密钥。
CSIDH密钥协商
群作用（Group Action）
对于群G和集合X以及一个映射，记。如果该映射对于所有的以及都满足条件和，则称该映射为群在集合上的群作用。显然，群作用可以隐藏群的结构，即对于这儿没有任何的群运算规则，因为X是群作用后的一个集合。
对于这种密钥协商方法来说，要求群必须是一个阿贝尔群，否则
超奇异椭圆曲线上的理想类群存在一个群作用：
对于一个椭圆曲线，有一个群作用，其中表示一个二次虚数域的阶，是一个定义在有限域上的椭圆曲线的集合，该集合中的椭圆曲线的自同态环都是并且Frobenius自同态映射的迹. 是一个理想剩余类组成的类群.
一个类群做用的计算方法
CSIDH的实现：