1. 引言

安全社區已經開發出了一些出色的加密算法，這些算法非常安全，但最終，所有的數據都會被存儲在硅和金屬中，而入侵者越來越多地會在那里放置監視器來破解密鑰。

破解加密密鑰通常涉及暴力破解方法或利用實施過程中的缺陷。然而，人們對物理側信道攻擊的興趣日益濃厚。
側信道攻擊是指：

• 無意中泄露加密信息，如電磁輻射、功耗、電壓波動，甚至聲音和熱量變化。

目前很少有公司保護其設備免受側信道攻擊，尤其是因為這種攻擊成本高昂，需要使用復雜的設備進行大量測試。

隨著設備的速度越來越快，可能會發射越來越多的無線電和電磁 (electromagnetic，EM) 輻射。如：

• 2GHz 處理器的運行頻率與 Wi-Fi 信號 (2.4 GHz) 相同，且芯片通常不受無線電波發射保護，這是設備快速運行的自然副產品。由于這些高頻，通常很難阻止電磁輻射耦合到附近的電線和其他電路中：
  
  本文重點關注后量子簽名方案，如：Dilithium、SPHINCS+ 、FALCON和Raccoon的側信道攻擊問題。
  所謂Raccoon：
• 為由PQShied開發的，基于Lattice的后量子簽名方案。
• 已作為額外簽名，提交到NIST PQC競賽。
• 使用無aborts的Fiat-Shamir方法。而Dilithium則使用的是有aborts的Fiat-Shamir方法。
• 所謂無aborts的Fiat-Shamir方法，是指：支持分布式門限簽名，且對側信道攻擊進行了改進。
• 開源代碼實現見：https://asecuritysite.com/pqc/raccoon

2. PQC 中的側通道

在PQShield團隊 Masking-Friendly Signatures and the Design of Raccoon 的精彩演講中，作者概述了 PQC 簽名的三種主要方法（Dilithium、SPHINCS+ 和 FALCON）容易受到側信道攻擊：

在 FALCON 中，Karabulut 和 Aysu 表明，功耗主要源自簽名和私鑰（sk）的點積，甚至純粹是私鑰的點積：

Masking-Friendly Signatures and the Design of Raccoon 作者隨后展示了 Dilithium 如何存在側信道問題，并使用了經典的過河難題：

3. Dilithium后量子簽名方案

Dilithium keygen為：

• 從密鑰 ($sk$)和誤差矩陣 ( $e$ ) 中推導出公鑰 ( $vk$ ) ，采用經典的 LWE (learning with errors) 方法：
  $vk=\mathbf{A}?sk+e??$
  其中：
  • $\mathbf{A}$是$k\times l$矩陣，$t$是$k$ 個元素的向量。
  • 這些都取 ($\mathrm{mod}q$ )，其中$q$是素數。
  • 驗簽密鑰將是 $(\mathbf{A},vk)$，簽名密鑰是$sk$。

Dilithium簽名過程為：

• 采用一個簡短的隨機秘密（$r$）和消息（$msg$），并創建一個挑戰承諾（其中$e^{\prime }$是$e$的一個樣本），計算：
  $w=\mathbf{A}?r+e^{\prime }$??
  $c=Hash(vk，msg，w)$
  然后計算：
  $z=r+c?sk$
  • 若z太大，則重試以上計算流程。
• 最后返回 $(w,z)$ 作為簽名。

這是一個經典的帶有aborts的 Fiat-Shamir sigma 方法。該abort用于阻止簽名密鑰被泄露。

Dilithium驗簽過程為：

• 首先檢查z是否很小。
• 然后計算：
  $c^{\prime }=Hash(vk，msg，w)$
• 然后檢查：$\mathbf{A}?z\approx w+c?vk$

這是有效的，因為error值相對較小：

• $\mathbf{A}?z=\mathbf{A}?(r+c?sk)=\mathbf{A}?r+\mathbf{A}?c?sk\approx w+c?vk$
  因為 $\mathbf{A}?r\approx \mathbf{A}?r+e^{\prime }$且$\mathbf{A}?c?sk\approx vk?c$。

為了不泄露計算結果，可掩蓋該error值或 r。這是通過對均勻分布的error值進行采樣來完成的，這可能是一項相當耗時的任務。除此之外，aborts也會減慢簽名的生成速度：

4. Raccoon后量子簽名方案

Raccoon后量子簽名方案：

• 利用了 Lyubashevsky 的簽名方法（見Lyubashevsky 2009年論文《Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures》，以及2012年論文《Lattice signatures without trapdoors》），但沒有aborts。

Raccoon keygen為：

• 從密鑰 ($sk$)和經典 LWE（learning with errors）方法的error 矩陣$e$中得出公鑰 ( $vk$ )：
  $vk=\mathbf{A}?sk+e$??
  其中：
  • $\mathbf{A}$是$k\times l$矩陣，$t$是$k$ 個元素的向量。
  • 這些都取 ($\mathrm{mod}q$ )，其中$q$是素數。
  • 驗簽密鑰為 $(A,vk)$，簽名密鑰為$sk$。

Raccoon簽名過程為：

• 采用一個簡短的隨機秘密（$r$）和消息（$msg$），并創建一個挑戰承諾（其中$e^{\prime }$是$e$的一個樣本）：
  $w=\mathbf{A}?r+e^{\prime }$??
  $c=Hash(vk，msg，w)$
• 接下來計算：
  $z=r+c?sk$
  $y=c?e+e^{\prime }$??
• 那么簽名就是$c,z,y$。

Raccoon驗簽過程為：

• 計算：
  $w^{\prime }=\mathbf{A}?z+y?c?vk$
  $c^{\prime }=Hash(vk,msg,w^{\prime })$
• 然后檢查$c=c^{\prime }$是否成立，若成立則驗簽通過。
  • 這是因為：
    $w^{\prime }=\mathbf{A}?z+y?c?vk?\mathbf{A}?(c?sk+r)+c?e+e^{\prime }+c?(\mathbf{A}?sk+e)=\mathbf{A}?c?sk+\mathbf{A}?r+c?e+e^{\prime }?c?\mathbf{A}?sk?c?e=\mathbf{A}?r+e=w$
  • 因此 $Hash(vk,msg,w)$ 等于 $Hash(vk,msg,w^{\prime })$。

使用 Raccoon，不會在short emphemal secret（r）采樣中出現延遲，也不會有aborts：

總體而言，將其分成了 $d$份，其中 Raccoon 在masking方面的擴展性比 Dilithium 好得多：

5. 結論

PQShield團隊slide Masking-Friendly Signatures and the Design of Raccoon的結論部分，可看到 Raccoon 的假設與 Dilithium 類似，且更簡單。Raccoon驗簽（公鑰）密鑰大小也差不多。不幸的是，簽名大小是Dilithium的四倍。若使用masking，Raccoon比其他提議的標準要快得多：

參考資料

[1] Prof Bill Buchanan OBE FRSE 2024年6月博客 Side Channels in Post Quantum Cryptography
[2] PQShield團隊slide Masking-Friendly Signatures and the Design of Raccoon
[3] Thomas Prest——PQShield首席密碼學研究員博客
[4] 2023年11月20日 2nd Oxford Post-Quantum Cryptography Summit 2023 視頻PQC Scheme: Raccoon（相應slide見Raccoon）