type
status
date
slug
summary
tags
category
icon
password
基于椭圆曲线同源密码机制学习记录-II
SiGamal公钥加密算法
SiGamal: A supersingular isogeny-based PKE and its application to a PRF
作者：
Tomoki Moriya, Hiroshi Onuki, and Tsuyoshi Takagi
期刊 & 会议：
ASIACRYPT
时间：
2020
JCR/CCF：
CCF-B
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
理想类群群作用
理想类群在集合上的群作用
超奇异椭圆曲线上的理想类群存在一个群作用：
对于一个椭圆曲线，有一个群作用，其中表示一个二次虚数域的阶，是一个定义在有限域上的椭圆曲线的集合，该集合中的椭圆曲线的自同态环都是并且Frobenius自同态映射的迹. 是一个理想剩余类组成的类群.
一个类群作用的计算方法
- 选择随机的点，代入椭圆曲线方程并计算y的二次剩余是否存在，并分别置s=1或者s=-1
- 判断的符号位，并存储在集合S，这一步保证了所有的都对应的是二次剩余的点，而都对应的是，这是非二次剩余的点。
- 找到阶为的点Q作为生成元得到阶理想饶子群并计算同源，最后返回Montgomery曲线的唯一系数a
- 理想类群对应的核分别是且在中，或者
计算性困难问题
Commutative Supersingular Isogeny Computational Diffie-Hellman Problem
给定椭圆曲线，两个理想类，以及对应的群作用后的超奇异椭圆曲线，任意多项式时间敌手都不可以不可忽略的概率计算得到
Commutative Supersingular Isogeny Decisonal Diffie-Hellman Problem
给定椭圆曲线，三个理想类，以及对应的群作用后的超奇异椭圆曲线，任意多项式时间敌手都不能以不可忽略的概率区分以下两个分布和
注：当素数时，该困难问题可以在多项式时间内被解决
在不给出同源映射的情况下，计算点的像是困难的，所以下述两个问题是困难的
Points-Commutative Supersingular Isogeny Computational Diffie-Hellman Problem
Points-Commutative Supersingular Isogeny Decisional Diffie-Hellman Problem
SiGamal
SiGamal的基本原理图
Sigamal加密算法具体流程如下：
- : 给定素数，其中任意是一个小的奇素数，且所有的均不相同。初始的椭圆曲线，选择一个阶为的点. Alice选择一个随机的整数理想，其中是一个均匀随机选择的随机数。Alice计算椭圆曲线和该椭圆曲线上的点：，Alice的公钥为，私钥为，明文空间为
- ：给定消息，Bob计算并选择随机的整数理想，其中. 随后计算.最后发送密文给Alice
- ：Alice首先计算，然后根据和使用离散对数求解方法获得，进而.
C-SiGamal
C-SiGamal与SiGamal不同之处在于加密阶段，使用一个固定的点去替换了
SiGamal具体实现
SiGamal代码：http://tomoriya.work/code.html
CSIDH
SimS公钥加密
SimS: a Simplification of SiGamal
作者：
Tako Boris Fouotsa and Christophe Petit
期刊 & 会议：
PQC
时间：
2021
JCR/CCF：
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
IND-CCA attack
SiGamal在两种困难假设下仅能够实现OW-CPA或IND-CPA，不能够实现IND-CCA，Moriya等人在他们的文章给出了一个构造IND-CCA的SiGamal的想法-省略掉密文中的，但是这种方法并不能达到IND-CCA安全。
SimS
SimS的基本原理，删除了C-SiGamal中密文提供了额外点的像，解决了无法达到IND-CCA安全的问题
黑色表示公开信息，红色表示仅Alice知道的信息，蓝色是仅Bob知道的信息
IND-CCA安全证明
Commutative Supersingular Isogeny Knowledge of Exponent Problem
对于任意敌手，给定作为输入，输出一个新的密文，那么存在另一个敌手在给定相同输入时，输出
Proof:假设如果SimS不是IND-CCA安全，那么SimS也不会是IND-CPA安全的。首先，对于任意拥有解密预言机的敌手来说，给定某个密文作为输入后，输出一些合法的密文。因此，存在另一个敌手在给定相同的输入后可以输出相同的密文以及对应的理想,根据可以解密上面所有的密文得到明文。因此不需要解密预言机，仅需要两个敌手即可以区分挑战密文，因此不是CPA安全
Seta公钥加密
Seta: Supersingular Encryption from Torsion Attacks
作者：
Luca De Feo, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa, P´eter
Kutas, Antonin Leroux, Christophe Petit, Javier Silva, and Benjamin
Wesolowski
期刊 & 会议：
ASIACRYPT
时间：
2021
JCR/CCF：
CCF-B
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
Generalized Charles-Goren-Lauter hash function
Charles-Goren-Lauter hash function
- 选择一个初始的超奇异椭圆曲线并且j(E)=j
- 对于任意消息，根据每一位，选择与前一个相连的个同源中的第个。例如，初始时，根据选择与E相连的所有个阶同源中的第个得到曲线，随后根据选择与相连的所有个阶同源中的第个得到曲线（因为不能回溯，所以仅第一次是，后续都是）
- 计算消息对应的哈希值，即第n位对应的超奇异椭圆曲线的j-不变量
Generalized Charles-Goren-Lauter hash function
从单个-阶同源图扩展到了多个同源图（同源星）
- 中，
- 消息表示为如下形式：其中
显然，对于每一个
- 对于每个都去按照Charles-Goren-Lauter hash function方法去遍历得到哈希值，为了连通，令。初始时，对于消息，从对应的曲线开始出发然后遍历得到最后的哈希值，然后以该j-不变量作为遍历的初始曲线，即从对应的曲线出发，遍历得到对应的哈希值
- 哈希函数返回三个元素，分别是，即阶同源对应的j-不变量以及饶点对应的像
陷门哈希函数
Petit饶点攻击
Supersingular Isogeny with Trosion (SSI-T). 给定素数，光滑阶且，两条定义在上的超奇异椭圆曲线，饶子群的一组基以及它们经过同源映射后的像，恢复这个秘密同源
Seta加密算法
- : 计算一个定义在上的陷门超奇异椭圆曲线，设置公私钥对为
- 对于一个给定的消息，将消息m转换为，计算密文
- 给定私钥作为陷门哈希函数的陷门，计算，恢复消息
IND-CCA安全
参考文献
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~ 🍊