基于CRYSTALS-Dilithium的自动驾驶数字签名验证优化技术

∼可在www.sciencedirect.com上在线获取ScienceDirectICTExpress 9（2023）100www.elsevier.com/locate/icte自动驾驶环境下用于有效签名和验证的CRYSTALS-Dilithium并行实现Seog Chung Seoa，SangWoo Anba韩国首尔国民大学金融信息安全系b韩国京畿道电信技术协会（TTA）接收日期：2021年9月7日;接收日期：2022年6月8日;接受日期：2022年8月12日2022年8月18日在线提供摘要在自动驾驶环境中，每辆车在发送和接收BSM的同时执行大量签名和验证（基本安全信息）实时。我们提出了一个优化的CRYSTALS-Dilithium软件，可以快速处理每个签名并使用嵌入式图形处理单元进行并行验证。为了提高效率，我们提出了一些优化技术，如基于虚拟操作的翘曲发散减少技术，并行实现NTT基于数论变换的多项式乘法，使用拒绝序列表优化拒绝采样过程，等等。建议的水晶-与NVIDIA Jetson AGX Xavier上的CPU上的Dilithium软件相比，Dilithium软件提供了高达19.41倍的性能提升，这是一款现成的自动驾驶汽车OBU（车载单元）。© 2022作者（S）。由爱思唯尔公司出版代表韩国通信和信息科学研究所这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。关键词：数字签名算法;后量子密码学;双锂晶体; GPU1. 介绍数字签名算法（DSA）是对网络上传输的消息的原始发送者的身份进行认证的过程。DSA对于自动驾驶汽车环境中的基本安全消息（BSM然而，由于量子计算机技术的最新发展，量子计算机中使用的量子算法可能会威胁到现有DSA的安全性。因此，美国国家标准与技术研究所（NIST）正在进行一项公开竞赛，以标准化对量子算法安全的后量子密码学（PQC）[1]。目前，几个基于PQC的DSA决赛选手正在竞争，其中大 多 数 是 基 于 格 的 密 码 算 法 。 其 中 ， CRYSTALS-Dilithium（也称为Dilithium）[2]被认为是一个有前途的NIST PQC标准候选者。如果基于PQC的DSA可以用于无人机通信，则可以保证对量子计算机的安全性，但仍然存在困难。*通讯作者。电子邮件地址：scseo@kookmin.ac.kr（南卡罗来纳州）Seo），swan06@tta.or.kr（S.An）。同行审议由韩国通信研究所负责教育与信息科学（KICS）。https://doi.org/10.1016/j.icte.2022.08.003在自动驾驶车辆通信中使用基于PQC的DSA的性能方面。特别是在队列环境中，每个车辆在实时发送和接收BSM的同时执行大量签名和验证。根据3GPP TS 22.186 [3]，需要10 ms 25 ms的延迟作为车辆排队信息交换的协同驾驶的自动化程度。此外，在紧急情况下，最大端到端延迟为3ms。因此，有必要优化目标基于PQC的DSA算法，以便将其平滑地应用于自动驾驶环境中的BSM安全。到目前为止，Dilithium的优化研究主要集中在典型的CPU和嵌入式MCU上，如Intel CPU和ARM MCU [4]的文件。虽然有在GPU平台上对Dilithium进行优化的研究较少[5]，主要集中在Dilithium的主要运算之一--基于数论变换（NTT）的多项式乘法的优化[6，7]。此外，没有任何已知的Dilithium软件在嵌入式GPU上。在本文中，我们在NVIDIA Jetson AGX Xavier [8]上提出了一种优化的Dilithium，用于自动驾驶汽车中的现成OBU（车载单元）。为了提高效率，我们充分利用嵌入式CUDA2405-9595/© 2022作者。 由Elsevier B.V.代表韩国通信和信息科学研究所出版。这是一CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。S.C. Seo和S. 一个ICT Express 9（2023）100101在目标板上的GPU，并提出了几个优化技术，可以提高每一个签名和验证的Dilithium的性能。针对现有文献中只关注基于NTT的多项式乘法运算的不足，本文对Dilithium的整个运算过程进行了优化。为了最大限度地减少签名和验证的延迟，我们实现了我们的软件与细粒度的方法，并引入虚拟操作技术，以减少翘曲发散。我们还优化了整个多项式运算，包括基于NTT的多项式乘法。此外，我们提出了一种新的技术，使用拒绝序列表的有效拒绝采样过程中使用几个条件分支，不适合GPU环境。在NVIDIA JetsonXavier板上基于ARMv8.2的微控制器上，与Dilithium软件相比，采用本文提出的技术，软件性能提高了10.73 ~19.41倍。据我们所知，这是第一次使用嵌入式GPU优化此外，我们提出的技术，特别是拒绝采样技术，可以用于其他基于格的PQC算法使用拒绝采样嵌入式GPU和典型的GPU。2. 建议的CRYSTALS-Dilithium实施2.1. GPU环境GPU专门用于并行任务。我们实现了多个签名和验证过程，Fig. 1. 签约环境。和验证平行操作设计在GPU在GPU环境中同时并行处理。并行优化实现技术有两个主要方向。第一种是细粒度技术，第二种是粗粒度技术。粗粒度技术被设计为使单个线程执行所有一系列操作。细粒度技术是一种多线程协作计算单个任务的方法。我们在GPU环境下设计的CRYSTALS-Dilithium如下。GPU块是一组线程，独立地执行单个签名和验证过程。块中的线程被实现为合作处理单个签名和验证过程。这个过程可以在图中看到。1 .一、2.2. 线程细粒度实现技术GPU线程通过称为线程束的指令调度器执行操作通常，32个线程构成一个线程束，并且同一线程束内的线程共享给定操作的开始和结束。如果同一线程束内的线程通过条件语句执行不同的操作，则会发生线程束发散问题。当出现线程束发散问题时，当满足一个条件语句的线程执行相应的操作时，不执行相应条件语句的线程等待，直到其他线程执行所有条件语句。 由于这极大地干扰了并行工作，因此必须实现所有线程执行相同的操作，而不会在同一个线程束中分支。在CRYSTALS-Dilithium中，当通过细粒度技术实现优化时，有些函数需要解决翘曲发散问题，有些函数不需要。因此，在本文中，我们描述了如何实现优化的方法，区分容易和困难的优化功能。2.2.1. 简单函数大多数CRYSTALS-Dilithium功能都是在256项的多项式向量。 当通过细粒度技术并行地操作多项式中的256项时，通常被称为简单函数的函数的特性是对一项的操作不影响其他项。换句话说，当将任务分配给每个线程并行操作时，我们不必担心这个问题，因为它不会干扰其他线程的工作。图 2显示了多边形相加函数作为示例。2.2.2. 复变函数难以用细粒度技术实现并行优化的函数分为两个主要特征。第一种情况是每个线程必须执行不同的操作，即使它试图与GPU执行并行操作，因为函数被设计在必须为每个项执行不同操作的结构中。如图3所示，当仅针对特定项需要附加操作时，可以实现为使得每个线程通过划分分支来执行不同的操作S.C. Seo和S. 一个ICT Express 9（2023）100102图二. 将256次多项式加法函数中的每一项作为独立线程并行处理的过程图三. 一种结构，在这种结构中，所有线程都通过增加一个伪操作来执行同一条指令，同时保持原始结果。梗概.但是，由于所有线程执行相同操作的效率最高，因此我们可以通过添加假手术通过虚拟操作，所有线程原子地执行相同的操作。但是，伪操作不会影响特定线程号上的结果因此，每个线程的操作结果根据线程的唯一编号第二种是对多项式执行的操作影响不同项的情况。一个代表性的函数是NTT [9]，该函数的优化实现技术可以在图中看到。四、在NTT，两个任期被配对以执行运算，并且由于配对项对于每个区间大小连续地改变，所以受运算影响的项也连续地改变。如果不执行线程的同步，则可能发生在执行要首先执行的操作之前由另一线程首先使用特定项的我们实现了一个区段号，它根据每个特定线程要共享的区段的大小进行划分，并根据每个区段中线程的唯一索引计算不同的术语。在同一段内运行的线程通过实现合并内存访问来提高内存访问效率，并且zetas（NTT中使用的常量值）被缓存在常量内存中并用于提高内存引用速度。2.2.3. 扩展矩阵函数优化CRYSTALS-Dilithium中占用最大计算负载的函数是扩展矩阵函数，该函数基于拒绝采样生成随机多项式向量矩阵[10]。拒绝抽样是在特定分布范围内抽取随机值的方法之一，其目的是使生成的样本符合特定样本的分布。因此，在拒绝抽样中，不仅需要生成随机值，而且还需要检查所生成的随机值是否落在期望的分布内。如果生成的随机值落在所需分布内，则接受该值，否则拒绝该值。在CRYSTALS-Dilithium中，通过散列函数SHAKE [11]创建随机值条目，并且在顺序读取条目的成员的同时逐个输入作为多项式项的接受值。然而，在GPU中，如果并行实现该确定处理，则产生显著的计算负荷。这是因为，如果每个线程都希望根据条件执行不同的任务，则很容易发生线程束发散问题为此，我们采用拒绝抽样法对随机多项式矩阵生成函数进行了修改，使之适合于并行运算。如可见于图5.在现有操作过程中，顺序读取生成的随机值项，并将接受的数据作为多项式项输入。问题是，即使多个线程可以对独立的随机值做出接受-拒绝决策，也不知道接受的值将输入哪个多项式项。这是因为，由于多项式的项被顺序地存储在接受的值中，因此每个线程可以将接受的值输入到S.C. Seo和S. 一个ICT Express 9（2023）100103图四、 设计为使用多个线程并 行执行一个NTT操作（线程id是每个线程独立拥有的唯一编号）。图五. 更改了expand_matrix函数，以便通过预先将其读入查找表来排除要拒绝的值，从而实现多项式系数的并行输入。只有当他们知道接受的值被存储到什么程度时，才能下一个术语为了克服这一限制，我们提出了一种技术，使用一个表中存储的拒绝位置。在多项式向量矩阵生成处理中，第一用户每次在接受-拒绝中发生拒绝时，在评估过程中，对应的拒绝值的位置被编号并存储在表中。以这种方式生成的拒绝序列表（Rejection SequenceTable，简称拒绝序列表）用于下一个签名和验证过程。在这种情况下，的概率是基于抽样接受概率。S.C. Seo和S. 一个ICT Express 9（2023）100104见图6。 一个密钥生成（左），签名（中），验证（右）处理时间（µs），根据每个块的线程数（越低越好）。水平轴是每个 块 的线程数，垂直轴是处理时间。表1CPU参考代码和GPU优化代码之间每秒的密钥生成/签名/验证过程数。平台CRYSTALS-Dilithium 2 CRYSTALS-Dilithium 3CRYSTALS-Dilithium 5凯基签署验证注册机标志验证凯基签名验证CPU5,1752,3724,3252,947 12682,6291,846九九九一千五百九十九（（（（（（（GPU84,99333,96567,738五万一千零九十九一万四千八百七十五44,50231,80020，396 27，511（+1，542%）（+1，331%）（+1，446%）（+1，633%）（+1，073%）（+1，592%）（+1，622%）（+1，941%）（+1，620%）在接收到种子值和随机数之后，第二操作器在继续采样之前生成随机值，并且根据记录在随机数中的位置信息来限制对已知被拒绝的随机值的访问。之后，GPU的线程需要找到一个独立的位置，重新安排根据的优先级，不管其他线程是否3. 性能分析我们的目标板是Jetson AGX Xavier板[8]，目前用于自动驾驶环境中的OBU，它包含ARMv8.2 MCU和512核Volta GPU。我们使用Jetson AGX Xavier的GPU测量了性能结果，并使用nvcc编译器在Linux操作系统上构建了用CUDA C编写的代码。参考CPU实现使用-O3选项构建（在此选项中，自动插入NEON指令[12]以提高效率），并在安装在Jetson AGX Xavier上的8核ARM v8.2 64位CPU上测量性能。所有结果均以重复100次相同签名和验证过程的结果的平均值表示，测量单位以时间（微秒，µs）为单位。图6示出了在细粒度实现模型中当N个线程用于处理一个Dilithium密钥生成、签名和验证操作时根据N所花费的时间。当每个块使用32个线程并处理一个签名和验证过程时，它花费的时间最少。这是因为作为GPU的指令调度器单元的warp的大小为32，并且warp单元操作中没有同步问题，因此线程可以表现出最高效的速度。因此，对于随后的结果，性能结果是在每个块所有结果均按照CRYSTALS-Dilithium安全等级2、3、5进行区分。表1显示了所提议的Dilithium实现的吞吐量。从图6和表1中可以看出，我们的Dilithium软件所需的延迟远远低于V2X（车辆到一切）场景中所需的延迟[3]。仿真结果表明，该软件的整体性能吞吐量明显优于在ARMv8.2 MCU上优化的参考实现。在密钥生成、签名和验证的情况下，所提出的软件分别实现了从15.42、10.73和14.46倍到16.33、19.41和16.20倍的性能改进。4. 结论本文提出了几种有效的CRYSTALS-Dilithium PQC DSA算法的并行优化策略。我们还介绍了NVIDIA的JetsonAGX Xavier板上的优化Dilithium由于Jetson AGX Xavier板中集成的GPU是Volta架构，并且所提出的技术基于CUDA编程模型，因此通过重新配置块中的线程数量以实现高效的细粒度执行模型，它们可以用于典型的NVIDIA GPU，包括基于Volta的或更新的架构。通过实验，我们已经表明，我们的软件取得了令人印象深刻的性能改善相比，参考CPU实现。此外，使用我们的软件，标准的延迟要求变得令人满意，这意味着量子计算机抗DSA系统可以顺利应用于V2X通信中的BSM安全。CRediT作者贡献声明Seog Chung Seo：概念化，软件，写作S.C. Seo和S. 一个ICT Express 9（2023）100105&编辑. SangWoo An：软件，写作竞合利益作者声明，他们没有已知的可能影响本文所报告工作确认这项工作得到了韩国政府（MSIT）资助的韩国国家研究基金会（NRF）的支持（编号：2022R1C1C1013368）引用[1] D.T. Nguyen，K. Gaj，使用基于NEON的ARMv 8特殊指令优化CRYSTALS-Kyber，NTRU和Saber的软件实现，在：NIST第三届PQC标准化会议，NIST PQC 2021，2021年。[2] L. Ducas，E. Kiltz，T.放大图片作者：Lepoint，V. 塞勒，D. Stehlé，CRYSTALS-Dilithium：A lattice-based digital signaturescheme，IACR Trans. Cryptogr. Hardw. Embed. 2018（1）（2018）238http://dx.doi.org/10.13154/tches.v2018.i1.238-268[3] 3GPP TS 22.186版本16.2.0版本16（增强V2X场景的服务要求），2020，https://www.etsi.org/deliver/etsi_ts/122100_122199/122186/16.02.00_60/ts_122186v160200p.pdf。[4] D.O.C. Greconici ， M.J. Kannwischer ， D. Sprenkels ， CompactDilithiumimplementations on cortex-M3 and cortex-M4，IACR Trans.Cryptogr. Hardw. Embed. 系统2021（2020）1[5] S. Akleylek ， Z.Y. Tok ， Efficient arithmetic for lattice-basedcryptography on GPU using the CUDA platform ， in ： 2014 22ndSignal Processing and Communications Applications Conference ，SIU，2014，pp. 854http://dx.doi.org/10.1109/SIU.2014.6830364[6] O.厄泽克角埃尔格岑足球俱乐部Mert，E. Ozturk，E. Savas，Efficient number theory transform implementation on GPU forhomomorphic encryption ， J. Supercomput. （ 2021 ） （ 2021 ）http://dx.doi.org/10.1007/s11227-021-03980-5.[7] W.- K.李，S。阿克利莱克，哥伦比亚特区- K.黄伟- S.是的，B.- M.戈伊，S.- O. Hwang，Nussbaumer算法和数论变换在GPU平台上的并行实现：应用于qTESLA，J. Supercomput。（2021）77（2021）3289-http://dx.doi.org/10.1007/[8] NVIDIAAGXXavier规格，https://developer.nvidia.com/embedded/jetson-agx-xavier-developer-kit。[9] H. Nejatollahi ， N. Dutt ， S. Ray ， F. 雷 加 佐 尼 岛 班 纳 吉 河Cammarota，Post-quantumlattice-basedcryptographyimplementations：Asurvey，ACM Comput. 监视器51（6）（2019）.[10] M.T. Wells ， G. Casella ， C.P. Robert ， Generalized Accept-RejectSamplingSchemes ， in ： A Festschrift for Herman Rubin ， InstituteofMathematical Statistics，2004，pp. 342-347[11] M. Dworkin，SHA-3标准：基于排列的散列和可扩展输出函数，在：联邦信息处理。Stds，NIST FIPS，美国国家标准与技术研究所，马里兰州盖瑟斯堡，2015年，http：//dx.doi.org/10.6028/NIST.FIPS.202网站。[12] ARM开发人员：ASIMD Vector Instructions，https://developer.arm。com/documentation/ddi0596/2020-12/SIMD-FP-Instructions.