加法の微分方程式

暗号学において、加法微分方程式(DEA) は、 2 つの異なるグループ上の加算 (例: 2 ³²を法とする加算と GF(2) 上の加算) を混合し、入力と出力の差が XOR として表現される、差分 暗号解読に関連する最も基本的な方程式の 1 つです。

加法微分方程式(DEA) は次の形式になります。

${\displaystyle (x+y)\oplus ((x\oplus a)+(y\oplus b))=c}$

ここで、 および は- ビットの未知の変数であり、およびは既知の変数です。 および の記号は、それぞれモジュロ加算とビットごとの排他的論理和を表します。 上記の式は で表されます。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle +}$${\displaystyle \oplus}$ ${\displaystyle 2^{n}}$${\displaystyle (a,b,c)}$

セットしましょう

${\displaystyle S=\{(a_{i},b_{i},c_{i})|i<k\}}$

整数 はDEAシステムを表します。ここで は の多項式です。総当たり検索に指数時間がかかる場合、任意の DEA 集合の充足可能性は複雑性クラス Pにあることが証明されています。 ${\displaystyle i}$${\displaystyle k(n)}$ ${\displaystyle k(n)}$${\displaystyle n}$

2013年に、Chengqing LiらによってDEAの特殊な形式のいくつかの特性が報告されました。ここでは、およびは既知であると仮定されています。基本的に、この特殊なDEAは と表すことができます。発見された特性に基づいて、 を導出するアルゴリズムが提案され、分析されました。^[1]${\displaystyle a=0}$${\displaystyle y}$${\displaystyle (x\dotplus \alpha )\oplus (x\dotplus \beta )=c}$${\displaystyle x}$

任意の DEA セット (バッチまたは適応クエリ モデルのいずれか) の解決法は、 Souradyuti PaulとBart Preneelによるものです。この解決手法は、ストリーム暗号Helix の攻撃に使用されています。

• Souradyuti PaulおよびBart Preneel、「加法微分方程式のシステムの解法」、ACISP 2005。完全版 ( PDF )
• Souradyuti PaulおよびBart Preneel、「バッチ クエリによる加算の微分方程式を解くための最適アルゴリズム」、Indocrypt 2005。完全版 ( PDF )
• Helger Lipmaa 、 Johan Wallén、Philippe Dumas: 排他的論理和の加法微分確率について。FSE 2004: 317-331。