SQISign签名算法

Quaternion Algebra Orders Ideals

1. 四元数代数，其中

2. 四元数代数的共轭为

3. 四元数代数的范数为，迹

4. 两个四元数代数的内积与范数之间的关系：

5. 分数理想是一个秩为4的整数格，其中是的一组基，理想的范数

6. 对于两个分数理想，如果，那么

7. 阶是四元数代数的子环，同样也是一个分数理想，阶子环中所有元素都是integral，因为他们的范数和迹是整数

8. 阶子环的判别式

9. 当阶子环不会被其他的阶子环包含，则称是最大的阶子环

10. 四元数代数序order的类型：
1. Eichler orders:两个最大序（maximal order）的交集，这两个最大序不一定要相等，即一个最大序也是一个Eichler order
2. Gorenstein orders:对于任意的序可以写成的形式，是扩展因子，当扩展因子是1时，是一个Gorenstein orders
3. Bass orders: 对于一个序，它的所有子序都是Gorenstein orders，称该序是一个Bass order

11. 一个分数理想的左阶，右阶，也被称为左阶的左分数理想。当分数理想是包含在它的左阶或者包含在它的右阶中，即，称该分数理想是integral

12. 一个整数范数的整数理想可以被表示为

13. cyclic ideal:对于任意的理想当且仅当对于所有的素数都有不成立被称为循环理想，也被称为primitive

14. 核理想：对于一个椭圆曲线E，以及任意一个有限子群G，定义核理想为，当G是一个循环子群时，核理想也是一个循环理想
核理想简单来说就是所有自同态环中能够将有限子群点映射到无穷远点的元素组成的集合。以最基本的的为例，这个自同态环必然可以将所有的核都映射到无穷远点。

15. 当且仅当时，理想的乘积才被定义

16. Special Extrmel order：一个的最大阶，该阶包含一个支持对正交分解，即的子阶，其中且是一个拥有最小判别式的二次阶。例如，当时，最大阶，包含一个子阶。显然，

17. 二次虚数域={}，共轭是，范数是，迹

18. 代数数域的判别式计算：选择其整数环的一组基，判别式

KLPT算法

1. EquivalentPrimeIdeal

2. RepresentInteger

3. IdealModConstraint

4. StrongApproximation

Identification Protocol

1. 选择一个随机的同源图游走，公开

2. 证明者生成一个随机的同源图游走：，并发送给验证者

3. 验证者计算一个随机的同源图游走：，并发送给证明者

4. 根据，证明者计算一个新的同源并且是

Signature

1. 公开参数：，;函数表示将映射到一个从出发，经过一个总的度数为的不可回溯的同源序列；哈希函数

2. 签名：选择一个随机同源，令，计算同源，根据已知的私钥以及同源计算一个同源使得是循环的，输出签名：

3. 验证：计算，恢复同源，验证同源是不是并且是循环的

SQISign2D-West

FixedDegreeIsogeny

IdealToIsogeny

1. 寻找一对范数互素的理想以及使得并且（这些互素的条件是为了保证，即后续可以对他们在这个群里面求逆元）
1. Heuristic假设：对于任意,均匀随机选择一对且，。然而由于是理想的范数，不具备这样的性质，它并不是均匀随机分布的。所以需要生成一个新的分布：

1. 通过FixedDegreeIsogeny计算deg为u，v的两个从出发的同源以及他们对应的理想

2. 计算一个的二维同源

计算对应的理想，即

第二步知道了两个同源，可以计算二维同源的核，进而可以计算二维同源

1. 根据 计算得到

RandomFixedNormIdeal

Sigma协议

theta坐标计算二维同源

参考文献