Constructing Canonical Strategies for Parallel Implementation of Isogeny Based Cryptography
Constructing Canonical Strategies for Parallel Implementation of Isogeny Based Cryptography
复制标题
构建基于同源密码学并行实现的规范策略
DOI：
10.1007/978-3-030-05378-9_10
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Koray Karabina
中科院分区：
文献类型：
--
作者：
A. Hutchinson;Koray Karabina
基于等基因的密码系统是一种非常有竞争力的系统，它具有抵御量子攻击的潜在安全性。基于等基因的系统的运行时间主要是由一系列点乘法和超奇异椭圆曲线上按特定顺序进行的等基因计算决定的。序列的顺序对算法的运行时间起着重要的作用，当使用单个处理器时，可以有效地确定在所有可能的选择中产生最小成本的最优策略。在本文中，我们推广了这一思想，并提出了在两种不同的并行化模型下确定K处理器策略的新算法：每曲线并行化（PCP）和连续曲线并行化（CCP）。在PCP模型下，给出了规范化策略的几种递归公式及其代价。因此，我们展示了如何在PCP模型下构建最佳（最优）策略。对于一些密码学上有趣的参数，我们可以得到最多24个% (for \(K=2\)), 40% (for \(K=4\)), and 51% (for \(K=8\)) theoretical speed ups over the optimal strategies with one processor. The more general CCP model offers a refinement of PCP, and yields up to 30% (for \(K=2\)), 47% (for \(K=4\)), and 55% (for \(K=8\)) theoretical speed ups over the optimal strategies with one processor.
Isogeny based cryptographic systems are one of the very competitive systems that are potentially secure against quantum attacks. The run time of isogeny based systems are dominated by a sequence of point multiplications and isogeny computations performed over supersingular elliptic curves in a specific order. The order of the sequence play an important role in the run time of the algorithms, and an optimal strategy can be efficiently determined yielding the minimum cost among all possible choices when a single processor is in use. In this paper, we generalize this idea and propose new algorithms that determine strategies for K processors under two different parallelization models: Per-Curve Parallelization (PCP) and Consecutive-Curve Parallelization (CCP). We present several recursive formulation of canonical strategies and their cost under the PCP model. As a result, we show how to construct the best (optimal) strategies under the PCP model. For some cryptographically interesting parameters, we obtain up to 24% (for \(K=2\)), 40% (for \(K=4\)), and 51% (for \(K=8\)) theoretical speed ups over the optimal strategies with one processor. The more general CCP model offers a refinement of PCP, and yields up to 30% (for \(K=2\)), 47% (for \(K=4\)), and 55% (for \(K=8\)) theoretical speed ups over the optimal strategies with one processor.