检索
E-mail
RSS

网络空间安全科学学报 >

2024 , Vol. 2 >Issue 5: 44 - 56

DOI: https://doi.org/10.20172/j.issn.2097-3136.240504

学术研究

抗侧信道攻击的后量子密码掩码转换方案

  • 张舒琪 1 ,
  • 李延斌 , 1, * ,
  • 王蓬勃 2 ,
  • 葛春鹏 1 ,
  • 徐秋亮 1
展开
  • 1. 山东大学软件学院，济南 250101
  • 2. 武汉船舶通信研究所，武汉 430205

网络出版日期: 2025-01-25

基金资助

国家自然科学基金(62072247, 62472259, 62172258)；泰山学者青年项目；山东省自然科学基金(ZR2024QF098)

版权

版权所有©《网络空间安全科学学报》编辑部 2024
收起

Mask conversion scheme on post quantum cryptographic for resisting side channel attacks

  • ZHANG Shuqi 1 ,
  • LI Yanbin , 1, * ,
  • WANG Pengbo 2 ,
  • GE Chunpeng 1 ,
  • XU Qiuliang 1
Expand
  • 1. School of Software, Shandong University, Jinan 250101, China
  • 2. Wuhan Maritime Communication Research Institute, Wuhan 430205, China

Online published: 2025-01-25

Copyright

Copyright ©2024 Journal of Aeronautical Materials. All rights reserved.
Fold

摘要

随着物联网（Internet of Things，IoT）技术的迅猛发展，数以亿计的设备通过网络互联，物联网安全性问题日益突出。尤其是在量子计算技术的推进下，传统的密码算法面临着前所未有的安全威胁。物联网设备所依赖的传统公钥加密算法在量子计算时代可能失效，给全球范围内的物联网应用带来了巨大的风险。作为抵御量子计算攻击的新型密码体系，后量子密码算法在物联网设备的安全性中起着至关重要的作用。然而，尽管后量子密码算法在理论上能够抵御量子计算的威胁，但在实际实现中，侧信道攻击（Side Channel Attaclss，SCA）风险依然不容忽视。侧信道攻击不依赖破解算法本身，而是通过分析物联网设备在运行加密算法时泄露的物理信息来破坏安全性。在此背景下，针对后量子密码算法的侧信道攻击掩码防护问题，综述了掩码转换方案——布尔到算术转换（Boolean to Arithmetic conversion，B2A）。通过对现有掩码技术的深入分析，详细阐述了B2A算法的原理、实现过程及其在抗侧信道攻击中的优势，为后量子密码算法在物联网设备中的安全实现提供思路，也为我国密码学领域的研究和发展提供参考。

关键词： 后量子密码; 侧信道攻击; 掩码防护; 掩码转换; 物联网安全

本文引用格式

张舒琪 , 李延斌 , 王蓬勃 , 葛春鹏 , 徐秋亮 . 抗侧信道攻击的后量子密码掩码转换方案[J]. 网络空间安全科学学报, 2024 , 2(5) : 44 -56 . DOI: 10.20172/j.issn.2097-3136.240504

Abstract

With the rapid development of the Internet of Things (IoT) technology, billions of devices are interconnected through networks, and IoT security issues are becoming increasingly prominent. Especially with the advancement of quantum computing technology, traditional cryptographic algorithms are facing unprecedented security threats. The traditional public key encryption algorithms relied upon by IoT devices may become ineffective in the era of quantum computing, posing significant risks to IoT applications worldwide. As a new cryptographic system to resist quantum computing attacks, post quantum cryptographic algorithms play a crucial role in the security of IoT devices. However, although post quantum cryptography algorithms can theoretically resist the threat of quantum computing, the risk of side channel attacks (SCA) in their practical implementation cannot be ignored. Side channel attacks do not rely on the cracking algorithm itself, but instead undermine security by analyzing the physical information leaked by IoT devices when running encryption algorithms. In this context, a mask conversion scheme called boolean to arithmetic conversion (B2A) is reviewed to address the issue of side channel attack mask protection in post quantum cryptography algorithms. Through in-depth analysis of existing masking techniques, the principle, implementation process, and advantages of B2A method in resisting side channel attacks are elaborated in detail, providing ideas for the secure implementation of post quantum cryptography algorithms in IoT devices and references for research and development in the field of cryptography in China.

Key words： post quantum cryptography; side channel attack; mask protection; mask conversion; internet of things security

0 引言

物联网（Internet of Things，IoT）技术的快速发展，使得数以亿计的设备通过网络互联，推动了智能家居、智能城市、工业物联网等应用的兴起。但是，随着物联网设备的普及，其安全性问题也日益凸显。物联网设备通常资源有限且分布广泛，这使得它们容易成为网络攻击的目标，尤其是在量子计算技术的快速推进下，传统的密码算法面临着前所未有的安全威胁。物联网设备所依赖的传统公钥加密算法，如RSA算法（Rivest-Shamir-Adleman algorithm，RSA）和椭圆加密算法（Elliptic curve cryptography，ECC）等，在量子计算时代可能失效，给全球范围内的物联网应用带来了巨大的风险[1]。
为应对这一威胁，后量子密码（Post-Quantum Cryptography，PQC）应运而生[2-3]。美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）于2016年发起了后量子密码算法标准化的工作[4]，在全球范围内引发了广泛关注。后量子密码旨在抵御量子计算攻击，它基于无法通过量子计算机有效破解的数学问题，如格、哈希、编码、多变量等困难问题[5-7]，其中基于格的密码算法占大多数。
然而，尽管格密码在理论上能够抵御量子计算的威胁，但其在实际应用中仍然面临侧信道攻击（Side Channel Attacks，SCA）的巨大挑战[8 -10]。侧信道攻击不依赖直接破解算法，而是通过监测设备运行时泄露的物理信息（如功耗、电磁辐射、时序信息等[11-13]）获取敏感数据，在此情况下，物联网设备特别容易受到侧信道攻击的威胁。随着NIST将后量子密码的抗侧信道攻击特性作为评判标准，同时有很多针对格密码硬件实现的攻击成功案例[14-17]，针对格密码的抗侧信道攻击研究和实现成为密码工程的热点。
一种最广为人知的侧信道攻击防护方法是掩码技术[18-19]。掩码技术最初是由Chari、Rao和Rohatgi在CHES 2002会议上提出[20]，其基本思想是将一个秘密值划分为t+1个值（其中t为掩码阶数），采用秘密共享机制来完成划分。这种方法使得攻击者必须获取多个内部变量才能恢复秘密值[21]。虽然分组密码常用布尔掩码来全面防护，但后量子密码方案通常需要结合算术掩码和布尔掩码以达成有效的保护[22]。布尔掩码适用于逻辑操作，算术掩码更适合能够简单表示为为算术电路的操作[23]（即模q的多项式运算），实现这两种掩码类型之间的高效可靠转换至关重要。
Kyber和Dilithium是两个具有代表性的基于格的后量子密钥封装和数字签名方案，在Kyber和Dilithium的具体算法中，有些运算适合用布尔值计算，有些运算适合用算术值运算，因此布尔到算术转换（Boolean to Arithmetic conversion，B2A）和算术到布尔转换（Arithmetic to Boolean conversion，A2B）很有必要。例如，Dilithium算法的随机采样和拒绝采样模块适合用布尔掩码操作，涉及密钥的运算则更适合用算术掩码实现[23]。
掩码B2A算法模块涉及的原理：布尔掩码x′=x$\oplus$ r, 变量x被随机数r掩码后得到掩码值x′，算术掩码$ A=x-r\;\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k} $, 变量x被随机数r掩码后得到掩码值$A $。目标是找到一种高效的算法，用于在布尔掩码和算术掩码之间进行转换，并且在转换过程中所有的中间变量都与待掩码的数据无关，从而保证其对差分功耗分析攻击（Differential Power Analysis，DPA）的安全性。B2A的基本转换公式为b1$\oplus $b2=$A $1+$A $2 mod p。（本文中，小写为布尔掩码，大写为算术掩码，加粗为向量，r/R为随机数）。
2001年，Goubin为了抵御DPA攻击，提出了一种早期的一阶B2A算法[Gou01][24]，并证明了其对抗DPA攻击的有效性。该算法使用简单的操作，计算复杂度较低，只需要7个基本操作；2017年， Coron针对传统掩码技术在高阶情况下的安全性和效率挑战，提出了一种新的高阶B2A算法[Cor17c][25]。该算法的时间复杂度$ \mathcal{O} $($ {2}^{n} $)与寄存器大小无关，相较于之前的算法，在低阶情况下显著提高了效率，降低了计算和内存开销；2018年，Bettale等在[Cor17c]中方案的基础上，提出了一种简化的高阶转换方案[26]，减少了掩码刷新的次数，使算法速度提升了25%，同时证明了算法在ISW（Ishai, Sahai and Wagner）探测模型下的安全性。2019年，Schneider等针对格密码和容错学习问题（Learning With Errors，LWE），提出了第一个受保护的二项式采样器，并引入了一种新的B2A方案[27]。该方案运行时间复杂度为$ \mathcal{O}(k\cdot {n}^{2}) $，在模素数方面相较于之前的算法有显著优势；2023年，Coron等为了优化高阶掩码技术，提出了一种模素数的B2A算法[28]，引入了ShiftMod算法用于实现高效的算术位移操作，并基于[BCZ18][26]和ShiftMod提出新的B2A算法[28]，该算法的时间复杂度与位数μ和模素数q无关。
目前，针对抗侧信道攻击的后量子密码掩码转换方案相关研究和应用相对较少。因此，本文针对现有的B2A转化算法进行了梳理，从低阶掩码转换到高阶掩码转换，从模$ {2}^{k} $的特殊情况到模素数q的一般情况，回顾了不同掩码转换方案，同时分析对比了相应实现的防护代价，并给出不同方案的实现建议。
本文的主要贡献有以下几个方面：
（1）分析了现有的B2A方案，梳理了相关实现原理和适用条件；
（2）对于不同的B2A方案，从理论到实践进行分析，评估了不同方案在不同掩码阶数和模素数条件下的效率和防护代价；
（3）结合不同场景，给出了不同B2A算法的具体实现建议，为后量子密码方案的安全实现提供了参考；
（4）探讨了B2A掩码转换技术在后量子密码和物联网设备中对抗侧信道攻击的应用及其未来发展方向。

1 一阶模2k的B2A

Goubin提出了较早的一阶B2A算法，并证明了这种新算法对抗DPA攻击的有效性。算法采用简单的操作，如“XOR”“AND”“减法”和“逻辑左移”，并且具有较低的计算复杂度，只需要7个基本操作。

1.1 具体方案

$ \mathrm{\Psi }(x,r)=\left(x\mathrm{\oplus }r\right)-r\left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $
更准确地说，对任意$ x,{r}_{1},{r}_{2}\in {\mathbb{F}}_{{2}^{k}}\text{:} $
$ \mathrm{\Psi }\left(x,{r}_{1}\mathrm{\oplus }{r}_{2}\right)=x\mathrm{\oplus }\mathrm{\Psi }\left(x,{r}_{1}\right)\oplus \mathrm{\Psi }\left(x,{r}_{2}\right) $
Goubin提出的B2A算法基于$ \mathrm{\Psi } $的映射属性，参见式（2）。给定两个布尔掩码$ {x}_{1}\mathrm{、}{x}_{2} $作为输入，使得$ x={x}_{1}\mathrm{\oplus }{x}_{2} $，可以从$ \mathrm{\Psi } $和式（2）的定义得出：
$ x=\left({x}_{1}\mathrm{\oplus }{x}_{2}-{x}_{2}\right)+{x}_{2}=\mathrm{\Psi }\left({x}_{1},{x}_{2}\right)+{x}_{2}\quad\quad\;\; $
$ =\left(\begin{array}{c}\left({x}_{1}\oplus \Psi \right({x}_{1},r\oplus {x}_{2}\left)\right)\oplus \Psi ({x}_{1},r)\end{array}\right)+{x}_{2} $
其中，$ r\leftarrow \{\mathrm{0,1}{\}}^{k} $是随机生成的值。因此，可以计算算术掩码：
$ A\leftarrow \left(\begin{array}{c}{x}_{1}\oplus \Psi ({x}_{1},r\oplus {x}_{2})\end{array}\right)\mathrm{\oplus }\mathrm{\Psi }({x}_{1},r) $
最终给出$ x $的两个算术掩码$A $和$ {x}_{2} $：$ x=A+{x}_{2} \left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $。
上述B2A算法非常高效，因为只需要恒定数量的操作，与 $ k $无关。此外，很容易看出上述算法对一阶攻击是安全的，因为左项$ {x}_{1}\oplus \Psi ({x}_{1},r\oplus {x}_{2}) $与$ {x}_{2} $无关，右项$ \mathrm{\Psi }({x}_{1},r) $也与$ {x}_{2} $无关，最终当$ {x}_{2} $均匀分布时，算术掩码$A $也均匀分布。其具体算法如下所示。
算法1　GoubinSNI：布尔到算术转换，t-SNI变体
输入：$ {x}_{1},{x}_{2} $，满足 $ x={x}_{1}\oplus {x}_{2} $
输出：$ {A}_{1},{A}_{2} $，满足 $ x={A}_{1}+{A}_{2} $
1：$ s\leftarrow \{\mathrm{0,1}{\}}^{k}$
2：$ {a}_{1}\leftarrow {x}_{1}\oplus s$
3：$ {a}_{2}\leftarrow {x}_{2}\oplus s$
4：$ r\leftarrow \{\mathrm{0,1}{\}}^{k}$
5：$ u\leftarrow {a}_{1}\oplus \mathrm{\Psi }({a}_{1},r\oplus {a}_{2})$
6：$ {A}_{1}\leftarrow u\oplus \mathrm{\Psi }({a}_{1},r)$
7：$ {A}_{2}\leftarrow {a}_{2}$
8：$ \text{return}\;{A}_{1},{A}_{2}$

1.2 防护代价

一阶B2A掩码转换方案GoubinSNI是较早提出的B2A算法，只需要执行7个简单的基本操作，在一阶情况下优势很大，防护代价低，缺点是只有模2k版本。

1.3 算法分析

Goubin 基于函数映射$ \mathrm{\Psi }(x,r)=\left(x\mathrm{\oplus }r\right)-r\left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $，提出了较早的操作简单的B2A算法，只需要7个基本操作，但仅适用于一阶模$ {2}^{k} $的B2A转化。输入布尔掩码$ {x}_{1} $、$ {x}_{2} $，输出算术掩码$A_1 $=$ \left({x}_{1}\oplus \Psi ({x}_{1},r\oplus {x}_{2})\right)\mathrm{\oplus } \mathrm{\Psi }({x}_{1},r) $，$A _2 $=$ {x}_{2} $，满足$ {x}_{1}\mathrm{\oplus }{x}_{2} $=$A_1 $$ + $$A_2 $$ \left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $，算法只包含异或、减法和移位这些容易实现的简单基本操作，消耗资源少，利于轻量级的硬件快速实现。

2 高阶模2k的B2A

传统的掩码技术在高阶情况下可能存在安全性和效率上的挑战，如Hutter等[29]提出了一个高阶B2A转换算法，其时间复杂度与寄存器大小k无关，但是他们的算法在实际操作中面临三阶攻击和四阶攻击的挑战。同时其他一些传统的转换算法复杂度通常与寄存器大小有关。
Coron针对以上问题对Goubin算法进行了任意阶的推广，实现了高阶B2A算法，在ISW模型下证明了算法的安全性，且算法复杂度与寄存器大小无关。
Bettale等在Coron的基础上，将高阶B2A算法简化为具有较少掩码刷新次数的变体，速度提升了大约25%，同时也在 ISW探测模型下证明了算法的安全性。

2.1 具体方案

2.1.1 基于函数映射的高阶B2A（模$ {2}^{\mathit{k}} $）

以n个布尔掩码$ {x}_{i} $作为输入：$ x={x}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n} $，使用递归算法计算出n个算术掩码$ {D}_{i} $，使得$ x= {D}_{1}+\cdots +{D}_{n}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $。如图1所示，该算法是递归调用的，对具有$ n-1 $个输入的相同算法$ C $进行两次递归调用。
图 1 [Cor17c]中B2A算法的模块序列

Fig.1 Sequence of gadgets in the B2A algorithm from [Cor17c]

算法的步骤如下：首先执行掩码刷新操作R，同时将$ {x}_{i} $扩展为$ n+1 $个。根据$ \mathrm{\Psi } $函数的定义，可以得到：
$ \begin{aligned} x & ={x}_{1}\mathrm{\oplus }{x}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}\\& =({x}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}-{x}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1})+{x}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}\\& =\mathrm{\Psi }({x}_{1},{x}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1})+{x}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}\end{aligned} $
从$ \mathrm{\Psi } $函数的映射性质来看，左项可以分解为n个掩码$ \mathrm{\Psi }({x}_{1},{x}_{i}) $的异或，其中$ 2\leqslant i\leqslant n+1 $，第一个掩码为$ \overline{\left(n\wedge 1\right)}\cdot {x}_{1}\mathrm{\oplus }\mathrm{\Psi }({x}_{1},{x}_{2}) $：
$ \begin{aligned} x =&\overline{\left(n\wedge 1\right)}\cdot {x}_{1}\mathrm{\oplus }\mathrm{\Psi }({x}_{1},{x}_{2})\mathrm{\oplus }\mathrm{\Psi }({x}_{1},{x}_{3})\mathrm{\oplus }\cdots \mathrm{\oplus }\mathrm{\Psi }({x}_{1},{x}_{n+1})+\\&{x}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}\end{aligned} $
可以得到$ x $是两项的算术和，对应于图1中的两个分支。然后在两个分支上执行掩码刷新操作R，再经过一个压缩函数F，它简单地对最后两个掩码值进行异或操作，因此两个分支上只剩下$ n-1 $个掩码。在两个分支上分别对剩余的$ n-1 $个布尔掩码递归地应用B2A算法$ C_n $，输出$ n-1 $个算术掩码，得到：
$ x=\left({A}_{1}+\cdots +{A}_{n-1}\right)+\left({B}_{1}+\cdots +{B}_{n-1}\right) $
上述算法调用$ {C}_{n} $时，掩码的数量遵循序列：
$ {C}_{n}:n\to n+1\to n\to n-1 $
$ {C}_{n-1} $再递归调用$ n-1 $个掩码，具体如算法2。
算法2　 $ {{\boldsymbol{C}}}_{n} $：高阶布尔到算术掩码转换
输入：$ {x}_{1},\cdots ,{x}_{n} $
输出：$ {D}_{1}, \cdots ,{D}_{n} $，满足${x}_{1} \oplus \cdots \oplus {x}_{n} = {D}_{1} + \cdots + {D}_{n} \;(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k})$
1：if n=2 then
　 2：　　 $ {D}_{1},{D}_{2}\leftarrow \mathrm{G}\mathrm{o}\mathrm{u}\mathrm{b}\mathrm{i}\mathrm{n}\mathrm{S}\mathrm{N}\mathrm{I}\left({x}_{1},{x}_{2}\right) $
3：　　 $ \mathrm{r}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n}{D}_{1},{D}_{2} $
4：end if
5：$ {a}_{1},\cdots ,{a}_{n+1}\leftarrow $$ {\mathrm{RefreshMasks}}_{{n}}+1\left({x}_{1},\cdots ,{x}_{n},0\right) $
6：$ {b}_{1}\leftarrow \left(\overline{n\wedge 1}\right)\cdot {a}_{1}\mathrm{\oplus }\mathrm{\Psi }\left({a}_{1},{a}_{2}\right) $
7：for i = 2 to n do
8：　 $ {b}_{i}\leftarrow \mathrm{\Psi }\left({a}_{1},{a}_{i+1}\right) $
9：end for
10：$ {c}_{1},\cdots ,{c}_{n}\leftarrow $$ {\mathrm{RefreshMasks}}_{{n}}\left({a}_{2},\cdots ,{a}_{n+1}\right) $
11：$ {d}_{1},\cdots ,{d}_{n}\leftarrow $$ {\mathrm{RefreshMasks}}_{{n}}\left({b}_{1},\cdots ,{b}_{n}\right) $
12：　 $e_1,\ldots,e_{(n-2)}\leftarrow c_1,\ldots,c_{(n-2)} \; \text{and}\; e_{(n-1)}\leftarrow c_{(n-1)}\oplus c_n$
13：${f}_{1},\cdots ,{f}_{n-2}\leftarrow {d}_{1},\cdots ,{d}_{n-2}\;\mathrm{a}\mathrm{n}\mathrm{d}\;{f}_{n-1}\leftarrow {d}_{n-1}\oplus {d}_{n}$
14：$ {A}_{1},\cdots ,{A}_{n-1}\leftarrow {\mathcal{C}}_{n-1}({e}_{1},\cdots ,{e}_{n-1}) $
15：$ {B}_{1},\cdots ,{B}_{n-1}\leftarrow {\mathcal{C}}_{n-1}({f}_{1},\cdots ,{f}_{n-1}) $
16：$\mathrm{f}\mathrm{o}\mathrm{r}\;i=1\text{ }\mathrm{t}\mathrm{o}\;n-2\text{ }\mathrm{d}\mathrm{o}$
17：　　 $ {D}_{i}\leftarrow {A}_{i}+{B}_{i} $
18：$ \mathrm{e}\mathrm{n}\mathrm{d}\;\mathrm{f}\mathrm{o}\mathrm{r} $
19：$ {D}_{n-1}\leftarrow {A}_{n-1} $
20：$ {D}_{n}\leftarrow {B}_{n-1} $
21：$ \mathrm{r}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n}\;{D}_{1},\cdots ,{D}_{n} $
算法3　RefreshMasks：掩码刷新
输入：$ {x}_{1},\cdots ,{x}_{n} $
输出：$ {y}_{1},\cdots ,{y}_{n} $，满足 $ {y}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n}={x}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n} $
1：$ {y}_{n}\leftarrow {x}_{n} $
2：$ \text{for }i=1 $ to $ n-1\text{ do} $
3：　　 $ {r}_{i}\leftarrow \{0,1{\}}^{k} $
4：　　 $ {y}_{i}\leftarrow {x}_{i}\mathrm{\oplus }{r}_{i} $
5：　　 $ {y}_{n}\leftarrow {y}_{n}\mathrm{\oplus }{r}_{i} $
6：end for
7：$ \mathrm{r}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n}\;{y}_{1},\cdots ,{y}_{n} $

2.1.2 改进的基于函数映射的高阶B2A（模$ {2}^{\mathit{k}} $）

Bettale等将[Cor17c]中的高阶B2A算法简化为具有更紧凑序列的B2A算法：
$ {C}_{n}:n+1\to n $
如图2所示，新的递归算法$ {C}_{n} $以$ n+1 $个掩码作为输入（而不是n个），并在两个分支上递归调用具有$ n $个输入的$ {C}_{n-1} $，最终在一些算术分组后输出$ n $个算术掩码。实际上，该方案依赖$ \mathrm{\Psi } $函数将掩码数量减少一个，因此，不再需要先前的压缩函数F，同时掩码刷新操作也只需要执行一次。递归算法$ {C}_{n} $以$ n $个布尔掩码和初始化的$ {x}_{n+1}=0 $作为输入，输出n个算术掩码。
图 2 [BCZ18]中B2A算法的模块序列

Fig.2 Sequence of gadgets in the B2A algorithm from [BCZ18]

递归算法$ {C}_{n} $输入$ n+1 $个布尔掩码$ {x}_{i} $：
$ x={x}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}，{x}_{n+1}=0 $
输出$ n $个算术掩码$ {D}_{i} $：
$ x={D}_{1}+\cdots +{D}_{n}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $
对于$ n=1 $，该算法输入两个布尔掩码$ {x}_{1} $和$ {x}_{2} $，输出$ {D}_{1}={x}_{1}\mathrm{\oplus }{x}_{2} $。现假设$ n\geqslant 2 $，根据图2说明算法：
（1）首先对$ n+1 $个布尔掩码$ {x}_{i} $执行掩码刷新操作，得到以下$ {y}_{i} $：
$ {y}_{1},\cdots ,{y}_{n+1}\leftarrow {\text{RefreshMasks}}_{n+1}({x}_{1},\cdots ,{x}_{n+1}) $
可以写为：
$\begin{aligned} x&={y}_{1}\mathrm{\oplus }{y}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1}\\&={y}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1}+({y}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1}-{y}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1})\\&={y}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1}+\mathrm{\Psi }({y}_{1},{y}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1})\end{aligned} $
（2）由$ \mathrm{\Psi } $的映射性质得：
$ x={y}_{2}\mathrm{\oplus }\cdots \mathrm{\oplus }{y}_{n+1}+\overline{\left(n\wedge 1\right)}\cdot {y}_{1}\mathrm{\oplus }\mathrm{\Psi }({y}_{1},{y}_{2})\mathrm{\oplus }\cdots \mathrm{\oplus }\mathrm{\Psi }({y}_{1},{y}_{n+1}) $
令$ {z}_{1}\leftarrow \overline{\left(n\wedge 1\right)}\cdot {y}_{1}\mathrm{\oplus }\mathrm{\Psi }({y}_{1},{y}_{2}) $， $ {z}_{i} \leftarrow {\Psi } ({y}_{1},{y}_{i+1})，(2\leqslant $$ i \leqslant n) $，得：
$ x={y}_{2}{\oplus }\cdots {\oplus }{y}_{n+1}+{z}_{1}{\oplus }\cdots {\oplus }{z}_{n} $
（3）对B2A算法$ {C}_{n-1} $执行两次递归调用：
$ {A}_{1},\cdots ,{A}_{n-1}\leftarrow {C}_{n-1}\left({y}_{2},\cdots ,{y}_{n+1}\right) $
$ {B}_{1},\cdots ,{B}_{n-1}\leftarrow {C}_{n-1}({z}_{1},\cdots ,{z}_{n}) $
由公式（1）得：
$ x={A}_{1}+\cdots +{A}_{n-1}+{B}_{1}+\cdots +{B}_{n-1} $
（4）通过一些加法分组将算术掩码的数量从2n−2减少到n，像[Cor17c]中一样，令$ {D}_{i}\leftarrow {A}_{i}+ {B}_{i} $，$(1\leqslant i\leqslant n-2) $，$ {D}_{n-1}\leftarrow {A}_{n-1} $，$ {D}_{n}\leftarrow {B}_{n-1} $，得到n个算术掩码：
$ x={D}_{1}+\cdots +{D}_{n}\left(\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}\right) $
[BCZ18]的高阶B2A算法、递归算法$ {C}_{n} $如下：
算法4　高阶布尔到算术掩码转换
输入：$ {x}_{1},\cdots ,{x}_{n} $
输出：$ {D}_{1},\cdots ,{D}_{n}$，满足${x}_{1}\oplus \cdots \oplus {x}_{n}={D}_{1}+\cdots + {D}_{n} \left(\mathrm{m}\mathrm{o}\mathrm{d}{2}^{k}\right) $
1：$ {D}_{1},\cdots ,{D}_{n}\leftarrow {C}_{n}({x}_{1},\cdots ,{x}_{n},0) $
2：$ \mathrm{r}\mathrm{e}\mathrm{t}\mathrm{u}\mathrm{r}\mathrm{n}\;{D}_{1},\cdots ,{D}_{n} $
算法5　 $ {{\boldsymbol{C}}}_{n} $：高阶布尔到算术掩码转换递归函数 (n+1→n)
输入：$ {x}_{1},\cdots ,{x}_{n+1} $,
输出：$ {D}_{1},\cdots ,{D}_{n} $，满足${x}_{1}\mathrm{\oplus }\cdots \mathrm{\oplus }{x}_{n+1}={D}_{1}+\cdots +{D}_{n} \text{(mod}\;{2}^{k}) $
1：if n =1 then
2：　　return $ {D}_{1}\leftarrow {x}_{1}\mathrm{\oplus }{x}_{2} $
3：end if
4：$ {y}_{1},\cdots ,{y}_{n+1}\leftarrow $RefreshMasks$ \left({x}_{1},\cdots ,{x}_{n+1}\right) $
5：$ {z}_{1}\leftarrow \left(\overline{n\wedge 1}\right)\cdot {y}_{1}\mathrm{\oplus }\Psi \left({y}_{1},{y}_{2}\right) $
6：for $ i=2 $ to $ n $ do
7：　　 $ {z}_{i}\leftarrow \Psi \left({y}_{1},{y}_{i+1}\right) $
8：end for
9：$ {A}_{1},\cdots ,{A}_{n-1}\leftarrow {\mathcal{C}}_{n-1}\left({y}_{2},\cdots ,{y}_{n+1}\right) $
10：$ {B}_{1},\cdots ,{B}_{n-1}\leftarrow {\mathcal{C}}_{n-1}\left({z}_{1},\cdots ,{z}_{n}\right) $
11：for $ i=1 $ to $ n-2 $ do
12：　　 $ {D}_{i}\leftarrow {A}_{i}+{B}_{i} $
13：end for
14：$ {D}_{n-1}\leftarrow {A}_{n-1} $
15：$ {D}_{n}\leftarrow {B}_{n-1} $
16：$ \text{return }{D}_{1},\cdots ,{D}_{n} $

2.2 防护代价

2.2.1 基于函数映射的高阶B2A（模$ {2}^{\mathit{k}} $）

Coron的B2A算法操作次数为$ {T}_{n}=14\cdot {2}^{n}- 12\cdot n-21 $，复杂度为$ \mathcal{O}\left({2}^{n}\right) $，独立于寄存器大小k，而[CGV14][30]中算法的复杂度为$ \mathcal{O}(k\cdot {n}^{2}) $。表1中总结了[CGV14]（对于k = 32）和[Cor17c]的操作次数。可以看到，对于较小的阶数t，[Cor17c]比以往的工作至少快一个数量级。
表 1 B2A算法的操作计数，阶数最高为t=12，掩码份额为n=t+1

Table 1 Operation count for B2A conversion algorithms, up to security order t = 12, with n = t + 1 shares

B2A 安全阶数t（掩码份额n=t+1）
1 2 3 4 5 6 8 10 12
Goubin[Gou01][24] 7 — — — — — — — —
CGV, 32bits[CGV14][30] — 2 098 3 664 7 752 10 226 14 698 28 044 39 518 56 344
Coron[Cor17c][25] — 55 155 367 803 1 687 7 039 28 519 114 511
BCZ[BCZ18][26] — 49 123 277 591 1 225 5 053 20 401 81 829
在运行3.2 GHz英特尔处理器的iMac上使用Clang编译器，用C语言实现了[CGV14]和[Cor17c]中的算法。表2中列出了执行时间，趋势与表1一致。
表 2 B2A算法的运行时间（μs），在3.2 GHz英特尔处理器的iMac上用C语言实现

Table 2 Running time (μs) for B2A conversion algorithms. The implementation was done in C on a iMac running a 3.2 GHz Intel processor

B2A 安全阶数t（掩码份额n=t+1）
2 3 4 5 6 8 10 12
CGV, 32bits[CGV14][30] 1 593 2 697 4 297 55 23 7 301 10 919 15 819 21 406
Coron[Cor17c][25] 45 119 281 611 1 270 5 673 22 192 87 322
BCZ[BCZ18][26] 42 96 214 448 921 3774 13 899 54 572

2.2.2 改进的基于函数映射的高阶B2A（模$ {2}^{\mathit{k}} $）

用$ {T}_{n} $表示$ {C}_{n} $算法的操作次数，输入$ n+1 $个布尔掩码，输出$ n $个算术掩码。由于$ {C}_{1} $是单个XOR，有$ {T}_{1} $= 1。$ n+1 $个输入的掩码刷新的复杂度为$ 3(n+1)- 3=3n $个操作。$ \mathrm{\Psi } $函数的计算需要2个操作，假设计算$ \overline{\left(n\wedge 1\right)}\cdot {y}_{1}\mathrm{\oplus }\mathrm{\Psi }({y}_{1},{y}_{2}) $需要5个操作，共$ 2n+3 $个操作。最后，加法分组需要$ n-2 $个操作。得：
$ \begin{aligned} {T}_{n}&=3\cdot n+[2\cdot n+3]+2\cdot {T}_{n-1}+[n-2] \\&=2\cdot {T}_{n-1}+6\cdot n+1\end{aligned} $
即$ {T}_{n}=10\cdot {2}^{n}-6\cdot n-13 $。与[Cor17c]的$ {T}_{n}=14\cdot {2}^{n}- 12\cdot n-21 $相比，此算法的复杂度仍是$ n $的指数级，但是对于较大的$ n $，预期的加速比为29%。与现有算法的比较如表1所示。[BCZ18]算法的复杂度$ \mathrm{为}\mathcal{O}\left({2}^{n}\right) $，而[CGV14]算法的复杂度为$ \mathcal{O}({n}^{2}\cdot k) $，对于较小的n，[BCZ18]算法仍比[CGV14]算法高效。
表2中总结了算法的执行时间，结果与表1的结论一致，对于较小的n值，[BCZ18]比[CGV14]快至少一个数量级。同时还发现，阶数t越高，与[Cor17c]相比的加速比越大，对于t = 2，运行时间相似；对于t = 4，提速24%；而对于t = 6，提速26%。

2.3 算法分析

2.3.1 基于函数映射的高阶B2A（模$ {2}^{\mathit{k}} $）

Coron设计了递归算法$ {C}_{n} $，结合掩码刷新、Goubin提出的函数映射$ \mathrm{\Psi } $、压缩等步骤，将Goubin的一阶模$ {2}^{k} $的B2A算法推广到高阶模$ {2}^{k} $的B2A算法，复杂度为$ \mathcal{O}\left({2}^{n}\right) $，仍然与掩码位数无关。其中掩码刷新、压缩操作只涉及简单的异或操作，函数$ \mathrm{\Psi } $涉及异或、减法和移位操作，复杂度主要体现在递归函数$ {C}_{n} $上，故当n较小时更能体现出方案的优势。实验表明，对于较小的阶数（$ n $$\leqslant $8），从操作计数和运行时间上看，[Cor17c]比以往的工作至少快一个数量级。

2.3.2 改进的基于函数映射的高阶B2A（模$ {2}^{\mathit{k}} $）

[BCZ18]的方案也是基于Goubin提出的函数映射$ \mathrm{\Psi } $，对[Cor17c]的高阶模$ {2}^{k} $的B2A算法进行改进，修改了递归函数$ {C}_{n} $的输入维度：最初令$ {x}_{n+1}=0 $，输入变量个数由n变为n+1。同时减少了掩码刷新次数，去除了压缩步骤，算法复杂度仍为$ \mathcal{O}\left({2}^{n}\right) $，实际实现中（在3.2 GHz英特尔处理器iMac上用C语言实现）提速大约25%，且阶数越高，加速比越大。

3 高阶模q的B2A

以上B2A方案均适用于模数为$ {2}^{k} $的特殊情况，但基于格的后量子密码算法是基于模素数q的多项式构建的。显然，这些算法不能直接用于后量子密码防护的实现。在此背景下，Schneider等在[SPOG19]中提出了一种新的适用于模素数的B2A方案[27]，其时间复杂度为$ \mathcal{O}({n}^{2}·k) $，是t-SNI安全的，该方案针对模素数在某些参数上显著优于先前的算法；Coron等[28]在2023年提出了一些高阶掩码技术，如模切换、ShiftMod算法，应用于[BCZ18]的方案，将高阶模$ {2}^{k} $ B2A拓展为模q的B2A。

3.1 具体方案

3.1.1 基于一位掩码转换公式的高阶B2A（模q）

Schneider等使用的B2A转化公式如下，其中$ {x}_{1}\mathrm{、}{x}_{2} $均为1 bit。
$ {x}_{1}\mathrm{\oplus }{x}_{2}={x}_{1}+{x}_{2}-2\cdot {x}_{1}\cdot {x}_{2} $
$ \begin{aligned} x&={x}_{1}\mathrm{\oplus }{x}_{2}=\left({A}_{1}+{A}_{2}\right)\mathrm{\oplus }\left({B}_{1}+{B}_{2}\right) \\&=\left({A}_{1}+{A}_{2}\right)+\left({B}_{1}+{B}_{2}\right)-2\cdot \left({A}_{1}+{A}_{2}\right)\cdot \left({B}_{1}+{B}_{2}\right)\end{aligned} $
根据公式（3）可以得到算法6，具体步骤如下，这里输入的是1 bit的布尔掩码份额。其中第5行功能是由输入${\boldsymbol{A}} $、${\boldsymbol{B}} $计算$ \left({A}_{1}+{A}_{2}\right)\cdot \left({B}_{1}+{B}_{2}\right) $实现的，第6行对应计算公式（3）。
算法6　 $ {{{\bf{SecB2A}}}}_{{\boldsymbol{q-{\mathrm{Bit}}}}} $（简单的）
输入：$ {x}=({x}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{2}\text{，满足}\text{}\underset{i}{\oplus}{x}_{i}=x $
输出：$ {A}=({A}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q}\text{，满足}\displaystyle\sum _{i}{A}_{i}=x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
1：$ ({A}_{i}{)}_{1\leqslant i\leqslant n}\leftarrow 0 $
2：$ \text{for }j=1\text{ to }n\text{ do} $
3：　 $ ({B}_{i}{)}_{1\leqslant i\leqslant n}\leftarrow ({x}_{j},0,\cdots ,0) $
4：　 $ {{\boldsymbol{B}}}\leftarrow \mathrm{R}\mathrm{e}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{A}\mathrm{D}\mathrm{D}{{\boldsymbol{B}}},q) $
5：　 $ {{\boldsymbol{C}}}\leftarrow \mathrm{S}\mathrm{e}\mathrm{c}\mathrm{M}\mathrm{u}\mathrm{l}({{\boldsymbol{A}}},{{\boldsymbol{B}}}) $
6：　 $ \boldsymbol{A}\leftarrow \boldsymbol{A}+\boldsymbol{B}-2\cdot \boldsymbol{C} $
7：end for
算法7　RefreshADD（基于RefreshXOR [21]）
输入：$ {{\boldsymbol{A}}}={\left({A}_{i}\right)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q}\text{，}\text{满足}\text{}\sum _{i}{A}_{i}=x\;\mathrm{m}\mathrm{o}\mathrm{d}q $
输出：$ \boldsymbol{B}={\left({B}_{i}\right)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q} $，满足 $ \sum _{i}{B}_{i}=x\mathrm{m}\mathrm{o}\mathrm{d}q $
1：$ \boldsymbol{B}\leftarrow \boldsymbol{A} $
2：$ \text{for }i=1 $ to $ n-1\text{ do} $
3：　 $ \text{for}j=1+i $ to $ n\text{ do} $
4：　　 $ R\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{F}}_{q} $
5：　　 $ {B}_{i}\leftarrow {B}_{i}+r $
6：　　 $ {B}_{j}\leftarrow {B}_{j}-r $
7：　end for
8：end for
算法8　SecMul（基于SecAnd）
输入：$ \boldsymbol{A}=({A}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q} $，$ \boldsymbol{B}=({B}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q}\text{，满足}\text{}\sum _{i} {A}_{i}= x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q,\sum _{i}{B}_{i}\leftarrow y\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
输出：$ \boldsymbol{C}=({C}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q}\text{，满足}\text{}\sum _{i}{C}_{i}=x+y\text{ mod }q $
1：$ \boldsymbol{C}=\boldsymbol{A}\cdot \boldsymbol{B}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
2：$ \text{for }i=1 $ to $ n-1\text{ do} $
3：　 $ \text{for }j=1+i $ to $ n\text{ do } $
4：　　 $ {R}_{i,j}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{F}}_{q} $
5：　　 $ {R}_{j,i}\leftarrow \left({A}_{i}\cdot {B}_{j}\right)+{R}_{i,j}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
6：　　 $ {R}_{j,i}\leftarrow {R}_{j,i}+\left({A}_{j}\cdot {B}_{i}\right)\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
7：　　 $ {C}_{i}\leftarrow {C}_{i}-{R}_{i,j}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
8：　 $ {C}_{j}\leftarrow {C}_{j}+{R}_{j,i}\;{\mathrm{mod}}\;q $
9：　end for
10：end for
算法6有3层for循环，其时间复杂度为$ \mathcal{O}\left({n}^{3}\right) $，因此，随着阶数增加，其效率也会迅速下降。为此，需要对算法6做进一步优化。在保证安全性的情况下，可以通过以下两个方法进行改进：（1）不需要为每一轮迭代使用t-SNI安全性的刷新操作，即$ \mathrm{R}\mathrm{e}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{A}\mathrm{D}\mathrm{D} $，而是为每一轮迭代使用一次t-SNI刷新，并且只在结束时执行最后一次t-SNI刷新。这可以使时间复杂度从$ \mathcal{O}\left({n}^{3}\right) $降低到$ \mathcal{O}\left({n}^{2}\right) $，减少每次迭代刷新的复杂性。（2）不需要将两个完整的编码相乘为$ \mathrm{S}\mathrm{e}\mathrm{c}\mathrm{M}\mathrm{u}\mathrm{l}(\boldsymbol{A},\boldsymbol{B}) $，因此不需要刷新$ {x}_{j} $，而是计算分量乘法$ \boldsymbol{A}\cdot{x}_{j} $。时间复杂度从$ \mathcal{O}\left({n}^{3}\right) $降低到$ \mathcal{O}\left({n}^{2}\right) $。综上，对于1位的B2A，优化后的算法在算法9中给出，算法整体时间复杂度可以从$\mathcal{O}\left({n}^{3}\right) $降低到$\mathcal{O}\left({n}^{2}\right) $，其结构如图3所示。
图 3 算法9中$ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q-{\mathrm{Bit}}} $的结构

Fig.3 Structure of $ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q-{\mathrm{Bit}}} $ in Algorithm 9

下面证明算法10在正确地进行B2A转化，公式（4）是对布尔掩码值进行逐步异或的推导，公式（5）将算术掩码值相加，对应算法11的第2、9、11行，易得$ \displaystyle\sum _{i=1}^{n} {B}_{i} $=$ \displaystyle\sum _{i=1}^{n-1} {A}_{i} $。又因为算法11的输入$ \mathit{A} $是由算法10的输入$ {x}_{i} $得出的，因此公式（4）等价于公式（5）。
$ \begin{aligned} \stackrel{n}{\underset{i=1}{\oplus{x}_{i}}}&=\left(\left(\left(\left({x}_{1}\oplus {x}_{2}\right)\oplus {x}_{3}\right)\cdots \right)\oplus {x}_{n}\right) \\&=\stackrel{n-1}{\underset{i=1}{\oplus{x}_{i}}}+{x}_{n}-2\cdot \stackrel{n-1}{\underset{i=1}{\oplus{x}_{i}}}\cdot {x}_{n}\end{aligned} $
$ \begin{aligned} \sum _{i=1}^{n}{A}_{i}=&\sum _{i=1}^{n}{B}_{i}-2\cdot \sum _{i=1}^{n}{B}_{i}\cdot {x}_{n}+{x}_{n}\\& =\sum _{i=1}^{n-1}{A}_{i}-2\cdot \sum _{i=1}^{n-1}{A}_{i}\cdot {x}_{n}+{x}_{n} \\&=\stackrel{n-1}{\underset{i=1}{\oplus{x}_{i}}}-2\cdot \stackrel{n-1}{\underset{i=1}{\oplus{x}_{i}}}\cdot {x}_{n}+{x}_{n} \end{aligned}$
算法9　 $ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q-{\mathrm{Bit}}}\text{（}\text{优化的}\text{）} $
输入：$ {\boldsymbol{x}}=({{{x}}}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{2}\text{，}\text{满}\text{足}\underset{i}{\oplus} {x}_{i}=x\in {\mathbb{F}}_{2} $
输出：$ {{\boldsymbol{A}}}=({A}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q}，\mathrm{满}\mathrm{足}\sum _{i}{A}_{i}=x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
1：$ \boldsymbol{A}\leftarrow {\mathrm{B}2\mathrm{A}}_{q-{\mathrm{Bit}}}\left(\boldsymbol{x}\right) $
2：$ \boldsymbol{A}\leftarrow \mathrm{R}\mathrm{e}\mathrm{f}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{h}\mathrm{A}\mathrm{D}\mathrm{D}(\boldsymbol{A},q) $
算法10　 $ {\mathrm{B}2\mathrm{A}}_{q-{\mathrm{Bit}}}\text{} $
输入：$ {\boldsymbol{x}}=({x}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{2}\text{，}\text{满}\text{足}\underset{i}{\oplus} {x}_{i}=x\in {\mathbb{F}}_{2} $
输出：$ \boldsymbol{A}=({A}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q}，\mathrm{满}\mathrm{足}\sum _{i}{A}_{i}=x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
1：$ \boldsymbol{A}\leftarrow {x}_{1} $
2：$ \text{f }j=2\text{ to }n\text{ do} $
3：　 $ \boldsymbol{A}\leftarrow {\text{B2A}}_{q-{\mathrm{Bit}}}^{\left(j\right)}(\boldsymbol{A},{x}_{j}) $
4：$ \text{end for} $
算法11　 $ {\mathrm{B}2\mathrm{A}}_{q-{\mathrm{Bit}}}^{\left(n\right)} $
输入：$ \boldsymbol{A}=({A}_{i}{)}_{1\leqslant i\leqslant n-1}\in {\mathbb{F}}_{q} $，满足$ \sum _{i} {A}_{i}=x;{x}_{n}\in {\mathbb{F}}_{2} $
输出：$ \boldsymbol{C}=({C}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q} $，满足$ \sum _{i} {C}_{i}=\left(x\oplus {x}_{n}\right)\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
1：$ {B}_{n}\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{F}}_{q} $
2：$ {B}_{1}\leftarrow {A}_{1}-{B}_{n}\mathrm{m}\mathrm{o}\mathrm{d}q $
3：$ \text{for}j=2 $ to $ n-1\text{do} $
4：　 $ R\stackrel{\mathrm{\$}}{\leftarrow }{\mathbb{F}}_{q} $
5：　 $ {B}_{j}\leftarrow {A}_{j}-R\mathrm{m}\mathrm{o}\mathrm{d}q $
6：　 $ {B}_{n}\leftarrow {B}_{n}+R\mathrm{m}\mathrm{o}\mathrm{d}q $
7：end for
8：$ \text{for}j=1 $ to $ n\text{ do} $
9：　 $ \begin{array}{r}{C}_{j}\leftarrow {B}_{j}-2\cdot \left({B}_{j}\cdot {x}_{n}\right)\mathrm{m}\mathrm{o}\mathrm{d}q\end{array} $
10：end for
11：$ {C}_{1}\leftarrow {C}_{1}+{x}_{n}\mathrm{m}\mathrm{o}\mathrm{d}q $
然而算法9只适用于输入为1 bit的B2A，算法12给出了布尔掩码为多个bit的B2A。很容易看出，算法12就是在不断调用算法9来进行B2A转化，即将前面的转换分别应用于每个输入位，并结合分量加法。由此可见，算法12的时间复杂度为$ \mathcal{O}({n}^{2}k) $其中k=3时的基本结构如图4所示。
图 4 k=3时算法12中$ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q} $的结构

Fig.4 Structure of $ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q} $ in Algorithm 12 for k = 3

算法12　 $ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q} $
输入：$ \boldsymbol{x}=({x}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{{2}^{k}} $，满足$ \text{}\underset{i}{\oplus} {x}_{i}=x\in {\mathbb{F}}_{{2}^{k}} $
输出：$ \boldsymbol{A}=({A}_{i}{)}_{1\leqslant i\leqslant n}\in {\mathbb{F}}_{q} $，满足$ \displaystyle\sum _{i} {A}_{i}=x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
1：$ \boldsymbol{A}\leftarrow {\text{SecB2A}}_{{q}-\text{Bit}}\left(\right(\mathbf{x} > > (k-1))\wedge 1) $
2：$ \text{for }j=2\text{ to }k\text{ do} $
3：　 $ \boldsymbol{B}\leftarrow \mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2{\mathrm{A}}_{{q}-\mathrm{B}\mathrm{i}\mathrm{t}}\left((\mathbf{x} > > (k-j\left)\right)\wedge 1\right) $
4：　 $ \boldsymbol{A}\leftarrow 2\cdot \boldsymbol{A}+\boldsymbol{B}\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
5：$ \mathrm{e}\mathrm{n}\mathrm{d}\text{ for} $

3.1.2 基于函数映射的高阶B2A（模q）

Coron等提出的ShiftMod算法实现了模2q到模q的转换，它需要依赖1bit B2A算法，通过对[SPOG19]中的1bit B2A工具进行微小修改，达到free-SNI安全性来实现。ShiftMod算法可以对任何整数模进行有效的算术移位，实现从模2q到模q的算术掩码转化，即由$ x={x}_{1}+\cdots +{x}_{n}\text{ (mod 2}{q}\text{)} $到$ a={a}_{1}+\cdots + {a}_{n} \text{}\text{(mod}q) $，通过式（6）计算：
$ a=\Bigg\lfloor\frac{x}{2}\Bigg\rfloor=\frac{x-x\;\mathrm{m}\mathrm{o}\mathrm{d}\;2}{2}\mathrm{m}\mathrm{o}\mathrm{d}\;q $
首先，提取$ {x}_{i} $的最低有效位$ {b}_{i} $，通过修改的1bit B2A算法输出：
$ {y}_{1}+\cdots +{y}_{n}={b}_{1}\oplus \cdots \oplus {b}_{n}=\left(x\;\mathrm{mod}\;2\right)\left(\mathrm{mod}2q\right) $
计算$ {z}_{i}={x}_{i}-{y}_{i}\;\mathrm{m}\mathrm{o}\mathrm{d}\;2q $，通过算法13中第4至7行生成新的算术掩码，使得$ {z}_{i} $都为偶数，这样可以方便在下一步操作中直接通过移位操作进行除以2的处理。
算法13　ShiftMod
输入：模数$ {q}^{\text{'}}=2q $和$ {x}_{1},\cdots ,{x}_{n}\in {\mathbb{Z}}_{2q} $
输出：$ {a}_{1},\cdots ,{a}_{n}\in {\mathbb{Z}}_{q} $，满足$ {a}_{1}+\cdots + {a}_{n}=\lfloor ({x}_{1}+\cdots + {x}_{n})/2\rfloor \left(\mathrm{m}\mathrm{o}\mathrm{d}\;q\right) $
1：$ \text{for }i=1 $ to $ n\text{ do }{b}_{i}\leftarrow {x}_{i}\&1 $
2：$ \left({y}_{1},\cdots ,{y}_{n}\right)\leftarrow 1 $bit B2A$ \left(2q,\left({b}_{1},\cdots ,{b}_{n}\right)\right) $
3：$ \text{for }i=1 $ to $ n\text{ do }{z}_{i}\leftarrow {x}_{i}-{y}_{i} $ mod $ 2q $
4：for $ i=1 $ to $ n-1 $ do
5：　 $ {z}_{n}\leftarrow {z}_{n}+\left({z}_{i}\&1\right)\mathrm{m}\mathrm{o}\mathrm{d}2q $
6：　 $ {z}_{i}\leftarrow {z}_{i}-\left({z}_{i}\&1\right) $ mod $ 2q $
7：end for
8：$ \begin{array}{r}\text{for }i=1\text{ to }n\text{ do }{a}_{i}\leftarrow {z}_{i}\gg 1\end{array} $
9：$ \text{return }{a}_{1},\cdots ,{a}_{n} $
[CGTZ23][28]中给出了一个B2A近似算法，该算法通过模数切换引入一个误差e。首先，应用[BCZ18]中的B2A方案，将μ位布尔掩码转换为一定参数k$\geqslant $μ的算术模$ {2}^{k} $掩码。然后，在第二步中使用模数切换，将算术掩码从模$ {2}^{k} $转换为模q，模数切换算法复杂度为$ \mathcal{O}\left(n\right) $。为了得到精确算法，利用之前提出的ShiftMod工具，从近似算法中消除误差e，其额外复杂度为$ \mathcal{O}\left({n}^{2}\mathrm{l}\mathrm{o}\mathrm{g}n\right) $，总体复杂度仍是$ \mathcal{O}\left({2}^{n}\right) $。
ModSwitch（模数切换）输入$ x={x}_{1}+\cdots +{x}_{n} \left(\text{mod }{p}_{1}\right) $，输出$ {y}_{1}+\cdots +{y}_{n}=\left\lfloor\dfrac{x\cdot {p}_{2}}{{p}_{1}}\right\rfloor+e\text{}\text{ mod}{p}_{2} $，进行算法14所示的模数切换会产生误差，经证明，误差$ e $在$ 0\leqslant e\leqslant n-1 $范围内。
算法14　ModSwitch 模数切换
输入：$ {p}_{1},{p}_{2}\in \mathbb{N} $，算术掩码$ {x}_{1},\cdots ,{x}_{n}\in {\mathbb{Z}}_{{p}_{1}} $，满足 $ x= {x}_{1}+\cdots +{x}_{n}\left(\text{mod }{p}_{1}\right) $
输出：$ {y}_{1},\cdots ,{y}_{n}\in {\mathbb{Z}}_{{p}_{2}} $，满足$ {y}_{1}+\cdots +{y}_{n}=\lfloor x\cdot {p}_{2}/{p}_{1}\rfloor + e\text{ mod }，{p}_{2}，0\leqslant e < n $
1：$ \mathrm{for}\;i=1\;\mathrm{t}\mathrm{o}\;n\;\mathrm{d}\mathrm{o}\;{y}_{i}\leftarrow \left\lfloor{x}_{i}\cdot \dfrac{{p}_{2}}{{p}_{1}}\right\rfloor\;\mathrm{m}\mathrm{o}\mathrm{d}\;{p}_{2} $
2：$ {y}_{1}\leftarrow {y}_{1}+\left(n-1\right)\;{\mathrm{mod}}\;{p}_{2} $
3：$ \begin{array}{c}\text{r}\text{e}\text{t}\text{u}\text{r}\text{n }({y}_{1},\cdots ,{y}_{n})\end{array} $
算法15　BtoAqApprox
输入：模数$ q $，μ位的布尔掩码$ {u}_{1},\cdots ,{u}_{n} $，满足$ {u}_{1}\oplus \cdots \oplus {u}_{n}=x $
输出：算术掩码$ {y}_{1},\cdots ,{y}_{n} $，满足$ {y}_{1}+\cdots +{y}_{n}= x+e \text{(mod }q\text{)，}\text{}\text{for }\text{}0\leqslant e < n $
1：$ k\leftarrow \lceil {\mathrm{l}\mathrm{o}\mathrm{g}}_{2}q\rceil +\mu $
2：$ a\leftarrow \lceil {2}^{k}/q\rceil $
3：$ {x}_{1},\cdots ,{x}_{n}\leftarrow {\mathrm{B}\mathrm{t}\mathrm{o}\mathrm{A}\mathrm{E}\mathrm{x}\mathrm{p}}_{\mu ,{2}^{k}}({u}_{1},\cdots ,{u}_{n} $
4：$ \text{for }i=1\text{ to }n\text{ do }{y}_{i}\leftarrow \left\lfloor{x}_{i}\cdot a\cdot \dfrac{q}{{2}^{k}}\right\rfloor {\mathrm{mod}}\;q $
5：$ \begin{array}{c}{y}_{1}\leftarrow {y}_{1}+\left(n-1\right){\mathrm{mod}}\;q\end{array} $
6：$ \text{return }{y}_{1},\cdots ,{y}_{n} $
近似算法15 BtoAqApprox输入$ x $的布尔掩码$ {u}_{1},\cdots ,{u}_{n} $，满足$ x=u_1\oplus\cdots\oplus u_n $，输出算术掩码$ {y}_{1}+\cdots + {y}_{n}=x+e\text{}\mathrm{m}\mathrm{o}\mathrm{d}\text{}q $，其中$ e\in \mathbb{Z} $，0 $ \leqslant e\leqslant $n−1。BtoAExp表示[BCZ18]中的B2A算法，得到$ x={x}_{1}+\cdots + {x}_{n}\text{}\mathrm{m}\mathrm{o}\mathrm{d}\text{}{2}^{k} $，再通过模数切换，从模$ {p}_{1}={2}^{k} $切换到模$ {p}_{2}=q $。
$ {y}_{1}+\cdots +{y}_{n}=\left\lfloor\frac{x\cdot a\cdot q}{{2}^{k}}\right\rfloor+e\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
整体操作$ {T}_{\mathrm{B}\mathrm{t}\mathrm{o}{\mathrm{A}}_{\mathrm{q}}\mathrm{A}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{x}}=10\cdot {2}^{n}-3n-13 $，复杂度为$ \mathcal{O}\left({2}^{n}\right) $。
精确算法16 BtoAqExact的目标是得到准确无误差的算术掩码值$ {z}_{1}+\cdots +{z}_{n}=x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $。在近似算法的基础上迭代$ \alpha $次ShiftMod算法，即可消除误差$ e $并获得模$ q $的算术掩码：
$ {z}_{1}+\cdots +{z}_{n}=\left\lfloor\frac{{y}_{1}+\cdots +{y}_{n}}{{2}^{\alpha }}\right\rfloor=x\;\mathrm{m}\mathrm{o}\mathrm{d}\;q $
算法16　BtoAqExact
输入：模数$ q $，μ位的布尔掩码$ {u}_{1},\cdots ,{u}_{n} $，满足$ {u}_{1}\oplus \cdots \oplus {u}_{n}=x $
输出：算术掩码$ {y}_{1},\cdots ,{y}_{n} $，满足$ {y}_{1}+\cdots + {y}_{n}=x\text{ (mod} \;q\text{)} $
1：$ \alpha \leftarrow \lceil{\mathrm{log}}_{2}n\rceil，k\leftarrow \lceil{\mathrm{log}}_{2}q\rceil+\mu +\alpha ， $
$ {q}^{\prime}\leftarrow {2}^{\alpha }\cdot q，a\leftarrow \lceil {2}^{k}/q\rceil $
2：$ {x}_{1},\cdots ,{x}_{n}\leftarrow {\mathrm{B}\mathrm{t}\mathrm{o}\mathrm{A}\mathrm{E}\mathrm{x}\mathrm{p}}_{\mu ,{2}^{k}}({u}_{1},\cdots ,{u}_{n}) $
3：　　 $ \text{for }i=1\text{ to }n\text{ do }{y}_{i}\leftarrow \lfloor ({x}_{i}\cdot a\cdot q)/{2}^{k-\alpha }\rfloor \;\mathrm{m}\mathrm{o}\mathrm{d}\;{q}^{\prime} $
4：$ {y}_{1}\leftarrow {y}_{1}+n-1 $
5：$ \text{for }i=0\text{ to }\alpha -1\text{ do } $
$ ({y}_{1},\cdots ,{y}_{n})\leftarrow \mathrm{S}\mathrm{h}\mathrm{i}\mathrm{f}\mathrm{t}\mathrm{M}\mathrm{o}\mathrm{d}({2}^{\alpha -i}\cdot q,({y}_{1},\cdots ,{y}_{n}\left)\right) $
6：$ \text{return }{y}_{1},\cdots ,{y}_{n} $

3.2 防护代价

3.2.1 基于一位掩码转换公式的高阶B2A（模q）

假设随机性生成需要单位时间，并且不考虑模约简，[SPOG19]中SecB2Aq算法的时间复杂度为：
$ {T}_{\text{SecB2Aq}}(n,k)=\frac{9k{n}^{2}}{2}+\frac{5kn}{2}-2n-3k $
表3比较了不同阶数和掩码位数下B2A方案的操作计数，采用了NewHope q = 12 289的素数模数。应该注意的是，模加法SecAddModp需要$ {2}^{k} > 2q $。因此，在此评估中，应用$ {k}^{\prime}=\lceil {\mathrm{l}\mathrm{o}\mathrm{g}}_{2}\;2q\rceil =15 $。
表 3 对于算法12 $ {\mathrm{S}\mathrm{e}\mathrm{c}\mathrm{B}2\mathrm{A}}_{q} $，使用素数模q=12 289进行B2A的操作计数，n个份额

Table 3 Operation count for Boolean-to-arithmetic conversions with prime modulo q = 12 289 for algorithms 12 SecB2Aq, with n shares

n
2 3 4 5 6 7 8 9 10 11 16
k=4 76 174 308 478 684 926 1 204 1 518 1 868 2 254 4 724
k=8 156 354 624 966 1 380 1 866 2 424 3 054 3 756 4 530 9 480
k=15 296 669 1 177 1 820 2 598 3 511 4 559 5 742 7 060 8 513 17 803

3.2.2 基于函数映射的高阶B2A（模q）

表4为18位模q B2A算法的操作次数，对于Dilithium安全级别2中的参数μ=18，由表4可知，算法$ {\text{BtoA}}_{\text{q}}\text{Approx} $和$ {\text{BtoA}}_{\text{q}}\text{Exact} $在t$ \leqslant $8的情况下优于[SPOG19]中的算法。
表 4 对于素数q=223−213+1，18位模q B2A算法的操作计数，安全阶数达到t=12,使用n=t+1个份额

Table 4 Operation count for 18-bit B2A modulo q conversion algorithms, up to security order t = 12, with n = t + 1 shares, for prime q=223−213+1

B→A mod q安全阶数 t
2345681012
[SPOG19]
18→mod q		8041 4142 1863 1204 2166 89410 22014 194
BtoAqApprox581352926091 2465 08020 43481 868
BtoAqExact1542856101 0321 7866 16021 93883 860
表5是用C语言实现、在搭载Intel® CoreTM i7-1065G7 @1.30GHz CPU的笔记本电脑上获得的基准测试结果。该表比较了不同模q的B2A算法，结论与表4中给出的操作计数相符。BtoAqApprox和BtoAqExact算法在小阶数时优于[SPOG19]中的算法。然而，对于较高的阶数则表现不佳，主要瓶颈来自[BCZ18]中模$ {2}^{k} $的B2A，其复杂度是指数级的。
表 5 μ位模q的B2A算法的循环计数（μ=18，$ q={2}^{23}-{2}^{13}+1 $）

Table 5 Cycle counts for a μ-bit B2A mod q conversion for μ = 18 and $ q={2}^{23}-{2}^{13}+1 $.

B→A mod qSecurity order t
123456
[SPOG19]69413072275339542886251
BtoAqApprox24803105189081963
BtoAqExact351445979127021333537

3.3 算法分析

3.3.1 基于一位掩码转换公式的高阶B2A（模q）

[SPOG19]中给出基于$ {x}_{1}\mathrm{\oplus }{x}_{2}={x}_{1}+{x}_{2}-2\cdot {x}_{1}\cdot {x}_{2} $的1位模q的B2A转化方法，算法复杂度为$ \mathcal{O}\left({n}^{2}\right) $，将其应用到k位掩码的每一位上得到多位模q的B2A算法，复杂度为$ \mathcal{O}({n}^{2}·k) $，与掩码阶数和输入位数有关。算法有加法、减法和乘法操作，乘法操作实现复杂，并且需要迭代调用1bit B2A，多处用到模q操作，在硬件实现上可能消耗更多资源。但是其在t$\geqslant $10的高阶掩码转化时体现出了优势，从操作计数和需要的随机位数两方面看，都比其他两种模q的B2A算法效果好。

3.3.2 基于函数映射的高阶B2A（模q）

[CGTZ23]中给出了ModSwitch和ShiftMod算法，将[BCZ18]的模$ {2}^{k} $的B2A算法转换成模q的B2A算法，总体复杂度仍是$ \mathcal{O}\left({n}^{2}\right) $，与掩码位数k和模数q无关。其中ModSwitch将模数$ {2}^{k} $转化为q并引入误差e，复杂度为$ \mathcal{O}\left(n\right) $，ShiftMod消除误差得到精确算术掩码，复杂度为$ \mathcal{O}\left({n}^{2}\mathrm{l}\mathrm{o}\mathrm{g}n\right) $。从操作计数、实际运行的循环计数和调用rand32()的次数方面看，在低阶情况(n$ \leqslant $8)下 BtoAqExact要优于其他B2A算法。对于较高的阶数，主要瓶颈来自[BCZ18]中模$ {2}^{k} $的B2A，其复杂度是指数级的。

4 总结及建议

以上内容整体上可以概括为两种B2A方案：第一种利用[SPOG19]中的基本转换公式：$ {x}_{1}\mathrm{\oplus }{x}_{2}= {x}_{1}+{x}_{2}-2\cdot {x}_{1}\cdot {x}_{2} $，实现1位模q的B2A转化，复杂度为$ \mathcal{O}\left({n}^{2}\right) $，相应k比特的B2A算法复杂度为$ \mathcal{O}({n}^{2}·k) $；第二种利用Goubin提出的基本函数映射：$ \mathrm{\Psi }(x,r)= \left(x\mathrm{\oplus }r\right)-r\;\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k} $，实现一阶下模$ {2}^{k} $的B2A转化，其突出特点是复杂度与掩码位数k无关且只有7个操作，但只适用于一阶掩码模$ {2}^{k} $的情况。
（1）[SPOG19]方案——高阶模qB2A
需要对布尔掩码的每一位单独进行复杂度为$ \mathcal{O}\left({n}^{2}\right) $的B2A转化。算法复杂度：$ \mathcal{O}({n}^{2}·k) $，与掩码阶数和位数有关。
（2）[Gou01]方案—— 一阶模$ {2}^{{k}} $B2A
基于函数映射，提出较早的操作简单的一阶B2A算法。算法复杂度：7个简单操作。
（3）[Cor17c]方案——高阶模$ {2}^{{k}} $B2A
设计递归算法$ {\mathcal{C}}_{n} $，将[Gou01]的一阶模$ {2}^{{k}} $的B2A算法推广到高阶模$ {2}^{{k}} $的B2A算法。复杂度：$ \mathcal{O}\left({2}^{\mathrm{n}}\right) $，在实际运行中，对于较小的阶数（n$ \leqslant $8），比以往工作至少快一个数量级。
（4）[BCZ18]方案——高阶模$ {2}^{{k}} $B2A
对[Cor17c]的高阶模$ {2}^{{k}} $的B2A算法进行改进，修改递归函数$ {\mathcal{C}}_{n} $的输入维度，减少掩码刷新次数，去除压缩步骤。复杂度：$ \mathcal{O}\left({2}^{\mathrm{n}}\right) $，在实际实现中提速大约25%。
（5）[CGTZ23]方案——高阶模qB2A
给出ModSwitch和ShiftMod算法，将[BCZ18]的模$ {2}^{k} $的B2A算法转换成模q的B2A算法。复杂度：ModSwitch和ShiftMod的额外复杂度分别是$ \mathcal{O}\left(n\right)\mathrm{和}\mathcal{O}\left({n}^{2}\mathrm{l}\mathrm{o}\mathrm{g}n\right) $，总体复杂度仍是$ \mathcal{O}\left({n}^{2}\right) $，与掩码位数k和模数q无关。在低阶情况(n$ \leqslant $8)下的性能优于[SPOG19]。突出特点：复杂度与位数k和模数q无关，适用于掩码阶数较小、位数较大的情况。
在硬件实现上，乘法运算、模运算、随机数生成等操作会消耗较多的计算资源。在硬件中，乘法器的实现比加法器复杂得多，尤其是当处理较大的位宽时，乘法器不仅需要更多的逻辑单元，还需要更大的寄存器和更多的时钟周期，如果算法中涉及到多次乘法，尤其是递归或迭代的乘法操作，资源消耗会大幅增加；模运算涉及除法，除法在硬件中实现起来比乘法更复杂，尤其是在大数模运算的情况下，它需要实现复杂的除法器或者利用迭代近似算法，消耗大量的逻辑单元和时钟周期，频繁进行模运算，资源消耗显著增加；频繁调用随机数生成器也会增加资源消耗。
[SPOG19]基于的基本公式$ {x}_{1}\mathrm{\oplus }{x}_{2}={x}_{1}+{x}_{2}- 2\cdot {x}_{1}\cdot {x}_{2} $涉及加法、减法和乘法操作，并且[SPOG19]中多位的B2A转化需要将一位的B2A迭代应用于每一位。此外，在算法中多处用到模q操作，需要使用的随机数也较多，都不利于轻量级的硬件实现。[SPOG19]中的算法更适合高阶掩码，在低阶时优势并不明显。
而[CGTZ23]中的B2A算法基于基本函数映射$ \mathrm{\Psi }(x,r)=\left(x\mathrm{\oplus }r\right)-r\;\mathrm{m}\mathrm{o}\mathrm{d}\;{2}^{k}$，只涉及7个简单的异或、减法、移位操作，资源消耗相对较低。虽然扩展到高阶转化引入了复杂度较高的递归函数调用，但在一阶掩码下不需要进行递归调用。同时，也设计了高效的算术移位算法ShiftMod和模数转化算法ModSwitch，将$ {\mathbb{F}}_{{2}^{k}} $上的算术掩码转化到$ {\mathbb{F}}_{q} $上。并且算法BtoAqExact中一些参数（如α、k、$ {q}^{\prime} $、a）在具体情境下都是定值，可以提前计算出来。因此，相比之下，[CGTZ23]中的B2A算法似乎更适合低阶轻量级的硬件实现。

5 B2A的应用与发展方向

随着物联网和后量子密码学的发展，B2A掩码转换在抵御侧信道攻击方面扮演了重要角色。这项技术被广泛应用于后量子密码算法中，特别是在Kyber和Dilithium的掩码安全实现中。尽管关于B2A算法的研究已取得显著进展，但面对物联网设备资源限制及轻量化硬件实现的挑战，进一步优化其效率和防护能力仍是研究的重点。
在Kyber和Dilithium的掩码安全实现中，B2A尤为关键。掩码实现的采样器和其他布尔到算术掩码转换的场景都需要用到B2A算法，在实际实现中，尤其是在资源受限的物联网设备上，常常应用低阶掩码就可以达到抗侧信道攻击的效果。
在未来研究中，B2A算法的复杂度应进一步降低以适应轻量化场景。如何在保证掩码转换安全性的前提下，减少计算资源消耗和降低时间开销，是优化的方向。设计针对性强、成本较低的抗侧信道攻击模型，特别是对于低阶掩码转换，如何在有限硬件资源下提升防护效率，是应用中亟待解决的问题。

6 结束语

本文详细综述了后量子密码中抗侧信道攻击的B2A方案的研究进展。通过对现有的多种B2A方案进行分析，不仅探讨了这些方案的理论基础，还评估了它们在不同应用场景中的实际防护效果和实现成本，为后量子密码算法的安全实现，特别是在物联网设备中的应用，提供了重要的参考。然而，仍然存在一些未解决的问题。首先，目前的B2A方案在高阶掩码下的效率和安全性仍有提升空间，特别是在面向大规模物联网设备时，需要更加轻量化且高效的解决方案。其次，在硬件实现过程中，复杂运算的资源消耗问题依然是一个挑战，如何优化操作以减少资源消耗仍须深入研究。此外，抗量子计算的密码算法在实际部署中的侧信道安全性，还需要更多实际的评估和实验，以验证理论模型的适用性和有效性。

参考文献

原文顺序 | 文献年度倒序 | 文中引用次数倒序
1
BANERJEE U,PATHAK A,CHANDRAKASAN A P. An energy-efficient configurable lattice cryptography processor for the quantum-secure Internet of Things[C]//2019 IEEE International Solid-State Circuits Conference (ISSCC). IEEE,2019:46-48.

2
眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势[J]. 电子与信息学报, 2020, 42 (2): 287- 294.

DOI

SUI H, WU W L. Research status and development trend of posterior quantum symmetric cryptography[J]. Journal of Electronics and Informatics, 2020, 42 (2): 287- 294.

DOI

3
王永利, 徐秋亮. 量子计算与量子密码的原理及研究进展综述[J]. 计算机研究与发展, 2020, 57 (10): 2015- 2026.

DOI

WANG Y L, XU Q L. Review on the principle and research progress of quantum computing and quantum cryptography[J]. Computer Research & Development, 2020, 57 (10): 2015- 2026.

DOI

4
LI J, LOUCKS W, ZHAI Y I, et al. The national institute of standards and technology post-quantum cryptography[EB/OL].(2016-08-02)[2024-08-07] https://csrc.nist.gov/projects/post-quantum-cryptography.

5
ROY K S, KALITA H K. A survey on post-quantum cryptography for constrained devices[J]. International Journal of Applied Engineering Research, 2019, 14 (11): 2608- 2615.

6
LU X, LIU Y, ZHANG Z, et al. LAC: practical ring-LWE based public-key encryption with byte-level modulus[J]. IRCA Cryptology ePrint Archive, 2018, 2018, 1009.

7
ZHANG J, YU Y, FAN S, et al. Improved lattice-based CCA2-secure PKE in the standard model[J]. Science China Information Sciences, 2020, 63 (8): 1- 22.

8
XU Z, PEMBERTON O, ROY S S, et al. Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: the case study of kyber[J]. IEEE Transactions on Computers, 2021, 71 (9): 2163- 2176.

9
BHASIN S,D'ANVERS J P,HEINZ D,et al. Attacking and defending masked polynomial comparison for lattice-based cryptography[J]//IACR Transactions on Cryptographic Hardware and Embedded Systems,2021:334-359.

10
AMIET D,CURIGER A,LEUENBERGER L,et al. Defeating Newhope with a Single Trace[C]//International Conference on Post-Quantum Cryptography. Cham:Springer,2020:189-205.

11
ZHANG F, YANG B, DONG X, et al. Side-channel analysis and countermeasure design on arm-based quantum-resistant SIKE[J]. IEEE Transactions on Computers, 2020, 69 (11): 1681- 1693.

DOI

12
KANNWISCHER M J,PESSL P,PRIMAS R. Single-trace attacks on keccak[C]//IACR Transactions on Cryptographic Hardware and Embedded Systems,2020:243-268.

13
HASSAN S,GRIDIN I,DELGADO-LOZANO I M,et al. Déjà Vu:side-channel analysis of mozilla’s NSS[C]//Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. ACM,2020:1887-1902.

14
PESSL P,PRIMAS R. More practical single-trace attacks on the number theoretic transform[C]//International Conference on Cryptology and Information Security in Latin America. Cham:Springer,2019:130-149.

15
SCHAMBERGER T,RENNER J,SIGL G,et al. A power side-channel attack on the CCA2-secure HQC KEM[C]//19th Smart Card Research and Advanced Application Conference (CARDIS2020). Cham:Springer International Publishing,2021:119-134.

16
GELLERSEN T,SEKER O,EISENBARTH T. Differential power analysis of the picnic signature scheme[C]//Post-Quantum Cryptography:12th International Workshop,PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings 12. Springer International Publishing, 2021: 177-194.

17
LIU Y, ZHOU Y, SUN S, et al. On the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage[J]. IEEE Transactions on Information Forensics and Security, 2020, 16, 1868- 1879.

18
CHARI S,JUTLA C S,RAO J R,et al. Towards sound approaches to counteract power-analysis attacks[C]//Advances in Cryptology-CRYPTO’ 99: 19th Annual International Cryptology Conference Santa Barbara, California, USA, August 15–19, 1999 Proceedings 19. Springer Berlin Heidelberg, 1999: 398-412.

19
PROUFF E,RIVAIN M. Masking against side-channel attacks:a formal security proof[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013:142-159.

20
CHARI S,RAO J R,ROHATGI P. Template attacks[C]//Cryptographic Hardware and Embedded Systems-CHES 2002:4th International Workshop Redwood Shores. Berlin,Heidelberg:Springer,2003:13-28.

21
BARTHE G,BELAÏD S,ESPITAU T,et al. Masking the GLP lattice-based signature scheme at any order[C]//Advances in Cryptology-EUROCRYPT 2018:37th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Cham:Springer International Publishing,2018:354-384.

22
BOS J W,GOURJON M,RENES J,et al. Masking kyber:first-and higher-order implementations[J]//IACR Transactions on Cryptographic Hardware and Embedded Systems. 2021:173-214.

23
MIGLIORE V,GÉRARD B,TIBOUCHI M,et al. Masking dilithium-efficient implementation and side-channel evaluation[C]//Applied Cryptography and Network Security:17th International Conference,ACNS 2019. Cham:Springer International Publishing,2019:344-362.

24
GOUBIN L. A sound method for switching between boolean and arithmetic masking[C]//Cryptographic Hardware and Embedded Systems-CHES 2001:3rd International Workshop. Berlin,Heidelberg:Springer,2001:3-15.

25
CORON J S. High-order conversion from boolean to arithmetic masking[C]//International Conference on Cryptographic Hardware and Embedded Systems. Cham:Springer International Publishing,2017:93-114.

26
BETTALE L,CORON J S,ZEITOUN R. Improved high-order conversion from Boolean to arithmetic masking[J]//IACR Transactions on Cryptographic Hardware and Embedded Systems. 2018:22-45.

27
SCHNEIDER T,PAGLIALONGA C,ODER T,et al. Efficiently masking binomial sampling at arbitrary orders for lattice-based crypto[C]//Public-Key Cryptography-PKC 2019:22nd IACR International Conference on Practice and Theory of Public-Key Cryptography. Cham:Springer International Publishing,2019:534-564.

28
CORON J S,GÉRARD F,TRANNOY M,et al. Improved gadgets for the high-order masking of Dilithium. [J]//IACR Transactions on Cryptographic Hardware and Embedded Systems. 2023:110-145.

29
HUTTER M, TUNSTALL M. Constant-time higher-order boolean-to-arithmetic masking[J]. Journal of Cryptographic Engineering, 2019, 9 (2): 173- 184.

DOI

30
CORON J S,GROßSCHÄDL J,VADNALA P K. Secure conversion between boolean and arithmetic masking of any order[C]//International Workshop on Cryptographic Hardware and Embedded Systems. Berlin,Heidelberg:Springer,2014:188-205.

Options
文章导航

/

〈 〉

禁止存储和处理涉密及内部敏感信息
网站版权 © 《网络空间安全科学学报》编辑部
地址：北京市西城区月坛北小街2号院1号楼　
邮编：100037　
电话：010-89061756/89061778　
E-mail：wlkjaqkxxb@caasse.cn
技术支持：北京玛格泰克科技发展有限公司

京ICP备16032046号-20