Public-Key

為什麼 NTRUEncrypt 在大模數的不同值上失敗?

  • November 27, 2022

我試圖嚴格遵循此處的算法(保持相同的變數名稱)並在Sage Math引擎中重建密碼系統。它似乎適用於參數(N, p, q) = (11, 3, 31),但在最後引發斷言錯誤(N, p, q) = (11, 3, 29)。請看下面的程式碼:

N = 11
p = 3
q = 31 # fails for 29

R.<x> = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)
P.<x> = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)
Q.<x> = PolynomialRing(Zmod(q))
QQ = Q.quotient(x^N - 1)

f = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])

fp = PP(f) ^ -1
fq = QQ(f) ^ -1
assert fp * f == 1
assert fq * f == 1

h = QQ( (p * fq) * g )
m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1])
r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0])
e = QQ(r * h + m)
a = QQ(f) * e
a = ZZ['x']([coeff.lift_centered() for coeff in a.lift()])
b = PP(a)
c = fp * b
assert c == m

我在這裡做錯了什麼嗎?

PS 要快速檢查Sage程式碼,您可以使用此站點: https ://sagecell.sagemath.org/

沒有什麼不正確的,基於格的密碼術有解密失敗的機會,並且這種機會隨著度數和雜訊相對於模數的增加而增加。我認為查看此處的實際數字非常有啟發性,以便了解基於格的密碼學中固有的一些不確定性。如果我們擴展您的 sage 程式碼以並排生成兩個案例

N = 11
p = 3
q1 = 31
q2 = 29

R.<x> = PolynomialRing(ZZ)
RR = R.quotient(x^N - 1)
P.<x> = PolynomialRing(Zmod(p))
PP = P.quotient(x^N - 1)
Q1.<x> = PolynomialRing(Zmod(q1))
QQ1 = Q1.quotient(x^N - 1)
Q2.<x> = PolynomialRing(Zmod(q2))
QQ2 = Q2.quotient(x^N - 1)


f = RR([-1, 1, 1, 0, -1, 0, 1, 0, 0, 1, -1])
g = RR([-1, 0, 1, 1, 0, 1, 0, 0, -1, 0, -1])

fp = PP(f) ^ -1
fq1 = QQ1(f) ^ -1
fq2 = QQ2(f) ^ -1
assert fp * f == 1
assert fq1 * f == 1
assert fq2 * f == 1

h1 = QQ1( (p * fq1) * g )
h2 = QQ2( (p * fq2) * g )
m = PP([-1, 0, 0, 1, -1, 0, 0, 0, -1, 1, 1])
r = RR([-1, 0, 1, 1, 1, -1, 0, -1, 0, 0])
e1 = QQ1(r * h1 + m)
e2 = QQ2(r * h2 + m)
a1 = QQ1(f) * e1
al1 = ZZ['x']([coeff.lift_centered() for coeff in a1.lift()])
a2 = QQ2(f) * e2
al2 = ZZ['x']([coeff.lift_centered() for coeff in a2.lift()])
b1 = PP(al1)
b2 = PP(al2)
c1 = fp * b1
c2 = fp * b2

請注意,我還為一個(X)模組q $ a(x)\mod q $ 及其對Z[X] $ \mathbb Z[x] $ 的提升使用了單獨的變數。如果我們比較a1a2我們看到

sage: a1
27*xbar^10 + 3*xbar^9 + 30*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 20*xbar^3 + 27*xbar^2 + 24*xbar
sage: a2
25*xbar^10 + 3*xbar^9 + 28*xbar^8 + 4*xbar^7 + 15*xbar^6 + 10*xbar^5 + 4*xbar^4 + 18*xbar^3 + 25*xbar^2 + 22*xbar

這些是相同多項式一個(X)=r(X)G(X)p+F(X)米(X)$$ a(x)=r(x)g(x)p+f(x)m(x) $$ =−4個X10+3個X9−X8個+4個X7+15X6個+10X5個+4個X4個−11X3個−4個X2個−7X$$ =-4x^{10}+3x^9-x^8+4x^7+15x^6+10x^5+4x^4-11x^3-4x^2-7x $$ 在整數上,為了解密,我們想將這個多項式的每一個約簡提升到原始整數版本。整數多項式的係數是小整數乘積之和,所以我們希望它們不要變大。特別是,如果所有係數都在(−q/2個,q/2個) $ (-q/2,q/2) $ 範圍內,則縮減可以解釋為該區間中的留數,並無誤地提升回原始多項式。但是,如果我們看X6個 $ x^6 $ t 的係數是 15,這雖然在區間(−31/2個,31/2個) $ (-31/2,31/2) $ 內,但不在區間內(−29/2個,29/2個) $ (-29/2,29/2) $ 所以我們的減少不是微不足道的,我們的電梯不起作用。具體來說,如果我們看一下al1al2我們有

sage: al1
-4*x^10 + 3*x^9 - x^8 + 4*x^7 + 15*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x
sage: al2
-4*x^10 + 3*x^9 - x^8 + 4*x^7 - 14*x^6 + 10*x^5 + 4*x^4 - 11*x^3 - 4*x^2 - 7*x

在第二種情況下,我們在整數上恢復了錯誤的多項式,導致後續步驟失敗。q $ q $ 越大,整數多項式的係數落在可恢復範圍之外的可能性越小,從而減少解密失敗。然而,增加q $ q $ 可以讓攻擊者的生活更輕鬆,並且必須達成權衡。

在解密失敗的情況下,可以通過掃描提升多項式中接近q/2個 $ q/2 $ 的係數來糾正此類錯誤,然後查看如果我們將這些可疑係數調整為±q $ \pm q $ 會發生什麼。然而,這會導致解密時間不穩定,並產生各種側通道、欺騙和故障注入漏洞。

引用自:https://crypto.stackexchange.com/questions/102971