type
status
date
slug
summary
tags
category
icon
password
基于椭圆曲线同源密码机制学习记录-III
FESTA
Seta: Supersingular Encryption from Torsion Attacks
作者：
Andrea Basso, Luciano Maino, and Giacomo Pope (University of Bristol)
期刊 & 会议：
ASIACRYPT
时间：
2023
JCR/CCF：
CCF-B
阿贝尔簇
- 定义：一个阿贝尔簇是定义在一个域(通常是复数域或者有限域)上的一个完备的且射影的代数簇，同时它有一个代数群结构，且可交换。
- 一个阿贝尔簇是一个代数簇，满足以下条件：
- 代数群结构：存在群运算以及反元素运算，这些运算都是态射
- 完备性：任何定义在上的代数函数都可以延拓到其闭包
- 射影性：可以嵌入到某个射影空间
eg：维度为1的阿贝尔簇就是椭圆曲线，维度为2的阿贝尔簇就是阿贝尔曲线
- 阿贝尔曲面：两个椭圆曲线的直积就是一个阿贝尔平面。
- 极化(Polarization):阿贝尔簇上的一个正定对称线丛（或等价的一个代数映射：，即从一个阿贝尔簇映射到其对偶的态射）
- 主要极化(principal polarization):极化的一种特殊类型，对应的态射是同构的，即是一个双射
- 自然极化(natural polarization):
- 积极化(Product polarization):是一个阿贝尔曲面，每个椭圆曲线都有一个自然极化，积极化就是自然极化的线丛的外积
FESTA陷门哈希函数
陷门哈希构造原理图
- ，其中是饶子群的一组基;
- 给定整数以及矩阵，输出，分别对应以及，分别对应着两个同源的核子群(同源的阶分别为)
- 计算如下等式恢复经过同源后得到的像，然后通过SIDH攻击方法重构同源，随后根据私钥恢复
- 矩阵是对角矩阵，且行列式为1，矩阵系数属于
FESTA公钥加密
- 加密算法
计算如上面的陷门哈希函数计算相同
- 解密算法
- 根据陷门求逆具体流程
是代数闭包上定义的三条超奇异椭圆曲线，并且有两个同源映射，存在一个的二维极化同源，该二维极化同源的矩阵形式如下(是一个阶同源，且)
该同源的核为
根据上面的同源图对上述定理进行实例化,取得到一个的极化同源，极化同源核为
计算并对核中的进行替换得到
注：这儿还有个矩阵并不能抵消
计算
根据私钥中的同源计算得到同源
根据下面这个算法恢复出的核子群，进而恢复出同源
根据如下公式恢复矩阵
困难问题
(Decisional isogeny with scaled-torsion (DIST) problem). 给定超奇异椭圆曲线，饶子群的一组基,敌手无法在多项式时间内区分以下两个分布：
- ，其中，，
- ，其中，是一个随机超奇异椭圆曲线且与有相同的阶，是饶子群的一组基
(Computational isogeny with scaled-torsion (CIST) problem). 给定超奇异椭圆曲线，饶子群的一组基,以及椭圆曲线上的一组点，敌手无法在多项式时间内计算阶同源
(Computational isogeny with double scaled-torsion () problem). 给定超奇异椭圆曲线，饶子群的一组基,以及椭圆曲线上的一组点，超奇异椭圆曲线，饶子群的一组基,以及椭圆曲线上的一组点，，敌手无法在多项式时间内计算得到阶同源和阶同源
给定一个函数是一个Quantum partial-domain单向函数，当且仅当对于任意多项式时间敌手满足下式成立：
FESTA是一个Quantum partial-domain单向函数
对于FESTA来说，给定同源时，可以恢复出矩阵以及同源，因此恢复三个输入中的某一个的概率等于恢复所有输入的概率，而FESTA满足单向性，故它同样也是一个Quantum partial-domain单向函数
Quantum partial-domain单向函数+OAEP转换 ⇒ IND-CCA公钥加密算法（QROM下）
该结论参考这篇文章：https://eprint.iacr.org/2021/237.pdf（PKC’22）
Polynomial Attack for M-SIDH & FESTA
A Polynomial Time Attack for M-SIDH and FESTA
作者：
Wouter Castryck and Frederik Vercauteren(比利时鲁汶大学)
期刊 & 会议：
ASIACRYPT
时间：
2023
JCR/CCF：
CCF-B
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
M-SIDH & FESTA & CISDH的共同之处
Supersingular Isogeny with Trosion (SSI-T). 给定素数，光滑阶且，两条定义在上的超奇异椭圆曲线，饶子群的一组基以及它们经过同源映射后的像，恢复这个秘密同源
现有的针对SIDH的攻击都是基于饶点信息，通过饶子群中的点和它们对应的像来恢复出同源，M-SIDH、FESTA所基于的困难问题就是对饶点进行盲化，前者是使用同一个数盲化两个盲点，即，后者使用不同数来盲化饶点像，即
CSIDH:虽然CSIDH没有泄露任何饶点有关的信息，但是它仍然存在着隐私泄露。假设是两个Frobenius自同态，分别对应于,那么对于任意，当时，二次剩余有解，因此可以根据中国剩余定理得到对应的解，此时的Forbenius自同态特征多项式有两个不同的特征值（Forbenius自同态的特征值就是特征多项式等于0的解）.假设，且，因此有，（这是因为）.最后可以得到以下结论：
对于任意且，必然存在一个且使得成立。
对于另一个特征值同样存在一个相同的结论，即成立，此时的CSIDH与FESTA类似。
攻击的主要思路
对于一组饶子群的基对应的盲化后的像为，攻击的主要思路就是去构造一个新的同源并计算盲化后的这组基在同源下对应的像，然后根据SIDH攻击方法重构出同源，进而得到
是在下的push-forwards（）；是在下的push-forwards（）;且满足成立；，对于上述同源图，有以下结论成立：
从Lemma3可以得到盲化后的饶点在同源作用下的像，从而通过SIDH的攻击方法可以重构出同源，进而得到，这与SIDH的攻击方法类似。
M-SIDH
- 当恒等映射时，根据Lemma3得到（;此时，即）
在这种情况下，不能是标量乘自同态，否则就无法获得到和对应的作用下的像
- 当Forbenius自同态时，根据Lemmma3得到（;;;曲线上的Forbenius自同态）
上述两种情况中，都是一个比较小的自同态，矩阵必须是交换矩阵代数的中心化子中的元素
FESTA
对于FESTA，必须要求有一个基点是的特征向量，否则无法确定
- ：取，这是一个自同态（;此时，即）
- ：（;;;曲线上的Forbenius自同态）
的原因是因为在FESTA实现中使用的是曲线以及曲线，为保证有一个较小的，因此选择（这是针对的自同态环来选择的）
结论
- 当是恒等映射时，不能是标量乘映射，即:
- 当饶点群的基都是的特征值且，攻击才能够成功
- 当饶点群的基仅有一个是的特征值且，攻击才能够成功
- 当是Frobenius自同态时，不能也是Frobenius自同态
- 当饶点群的基都是的特征值且，攻击才能够成功
- 当饶点群的基仅有一个是的特征值且，攻击才能够成功
QFESTA
QFESTA: Efficient Algorithms and Parameters for FESTA using Quaternion Algebras
作者：
Kohei Nakagawa and Hiroshi Onuki(NTT社会信息实验室；东京大学)
期刊 & 会议：
CRYPTO
时间：
2024
JCR/CCF：
CCF-A
相关链接：详细信息如下（包括论文原文链接、会议PPT链接、会议视频链接、论文代码链接）
RepresentInteger
输入：一个整数
输出：一个与超奇异椭圆曲线自同态环同构的四元代数的阶子环中范数为的元素
PS:图里面的的范数计算有错误：一个四元数代数的范数是，当时，超奇异椭圆曲线自同态环同构的四元数代数阶子环是，所以任意元素的范数是
Kani’s criterion
是三个互素整数且，是四条不同的超奇异椭圆曲线
其中，，存在一个同源，，核为
EvalByKani
前提：已知初始的超奇异椭圆曲线
功能：根据核计算-同源并计算
输入：，其中分别是的基，分别是上的有限子集，
输出：
算法具体流程：
- 根据核计算-同源
- 如果的值域不是一个由超奇异椭圆曲线乘积生成的阿贝尔曲面，返回
- 否则，令是计算得到的的值域
- 如果都不与同构，则返回
- 否则，通过同构将或转为，并返回，其中
CodomainByKani
前提：不知道初始的超奇异椭圆曲线
功能：在EvalByKani的基础之上，通过Weil配对来解决未知的问题
输入：
输出：
算法具体流程：
- CodomainByKani的前三步与EvalByKani相同
- 令，
- 计算
- 计算Weil配对
- 如果返回以及，否则返回
QFESTA
功能：计算一个非光滑阶同源（Velu公式计算同源的复杂度是，因此通常是用于计算光滑阶（）的同源）以及同源
输入：同源的阶，整数，有限子集
输出：同源
算法具体流程：
- 通过FullRepresentInteger输出一个范数的阶子环中的元素
- 选择一个饶点群的基
- 通过CodomainByKani计算曲线以及同源作用的像
QFESTA
- Setup: 参数选择
素数中的选择：，仅仅是方便实现，没有其他的理论原因
- KeyGen:
- Enc:
- Dec: ，这是因为离散对数解出的值可能是，在模后的结果为，因此取最小值即可获得.
正确性
参数选取
困难问题
(Decisional isogeny with scaled-torsion (DIST) problem). 给定超奇异椭圆曲线，饶子群的一组基,敌手无法在多项式时间内区分以下两个分布：
- ，其中，，
- ，其中，是一个随机超奇异椭圆曲线且与有相同的阶，是饶子群的一组基
(Computational isogeny with scaled-torsion (CIST) problem). 给定超奇异椭圆曲线，饶子群的一组基,以及椭圆曲线上的一组点，敌手无法在多项式时间内计算阶同源
(Computational isogeny with double scaled-torsion () problem). 给定超奇异椭圆曲线，饶子群的一组基,以及椭圆曲线上的一组点，超奇异椭圆曲线，饶子群的一组基,以及椭圆曲线上的一组点，，敌手无法在多项式时间内计算得到阶同源和阶同源
变体DIST困难问题1：给定超奇异椭圆曲线，饶子群的一组基,其中,敌手无法在多项式时间内区分以下两个分布：
- ，是RandIsogImages
- ，是从所有阶同源以及其对应的像中均匀随机选择的
变体DIST困难问题2：给定超奇异椭圆曲线，饶子群的一组基,其中，敌手无法在多项式时间内区分以下两个分布：
- ，其中，是RandIsogImages
- ，其中，是一个随机超奇异椭圆曲线且与有相同的阶，是饶子群的一组基
安全分析
QFESTA是OW-CPA安全
证明思路：假设存在多项式时间敌手可以攻破QFESTA，令是变体DIST困难问题2的输出，是变体DIST困难问题1的输出，计算得到密文，因此无论是那个分布中选择得到的变体困难问题的输出，敌手都可以获得对应的矩阵，可以看作是的输入，因此敌手如果能够攻破QFESTA，那么必然可以破解困难问题。
OW-CPA安全通过FO转换后可以达到IND-CCA安全
参考文献
- Ebrahimi E. Post-quantum security of plain OAEP transform[C]//IACR International Conference on Public-Key Cryptography. Cham: Springer International Publishing, 2022: 34-51.
有关这篇论文的任何问题，欢迎您在底部评论区留言，一起交流~ 🍊