Piling-up lemma

A Piling-up lemma, magyarul nagyjából „halmozási lemma”, a kriptográfiai elemzés egyik hasznos matematikai eszköze. Azt írja le, hogyan alakul több, egymástól független, nem teljesen véletlenszerű bit XOR-összege: a bemeneti bitek apró torzításai összeadódás helyett lényegében összeszorzódnak. 🔐

A lemma különösen a blokk-rejtjelek lineáris kriptoanalízisében fontos, mert segítségével megbecsülhető, hogy egy lineáris közelítés mennyire tér el a teljesen kiegyensúlyozott, 50–50%-os kimenettől. A fogalom megértéséhez érdemes áttekinteni a jelentését, eredetét és a mögötte álló valószínűségi összefüggést.

A Piling-up lemma jelentése a kriptográfiai elemzésben

A Piling-up lemma azt mondja meg, hogy független, kissé torzított bitek XOR-olásakor miként változik az eredmény torzítása. Ha egy bit nem pontosan fele-fele arányban vesz fel 0 és 1 értéket, akkor „biasról”, vagyis torzításról beszélünk. Több ilyen bit XOR-ja általában sokkal közelebb kerül a kiegyensúlyozott véletlenhez, kivéve, ha a torzítások jelentősek.

• XOR: kizáró vagy művelet, amely akkor ad 1-et, ha a bemenetek között páratlan számú 1 szerepel.
• Torzítás vagy bias: annak mértéke, hogy egy bit mennyire tér el az 50%-os eloszlástól.
• Függetlenség: az egyik bit értéke nem befolyásolja a többi bit értékét.

A kriptográfusok a lemmát például lineáris appro­ximációk valószínűségének kiszámítására használják. Ha egy rejtjel több részfolyamata külön-külön gyengén torzított kapcsolatot mutat, akkor a teljes XOR-kapcsolat torzítása a rész-torzítások szorzatából becsülhető meg. Ez megmutatja, hogy egy támadás várhatóan mennyi adatot és számítási erőforrást igényel. 📊

A Piling-up lemma eredete és angol elnevezése

A „Piling-up lemma” elnevezés az angol pile up kifejezésből származik, amelynek alapjelentése „felhalmozódik”, „egymásra rakódik”. A kriptográfiai szóhasználatban arra utal, hogy több kisebb statisztikai hatás halmozódik egymásra egy XOR-összegben. A lemmát leggyakrabban Mitsuru Matsui lineáris kriptoanalízisével kapcsolatban említik, amelyet az 1990-es évek elején dolgozott ki.

• Angol elnevezés: Piling-up lemma.
• Kapcsolódó terület: lineáris kriptoanalízis.
• Gyakran kapcsolt név: Mitsuru Matsui.
• Magyaros fordítások: halmozási lemma, XOR-halmozási lemma.

Az angol kifejezés a szakirodalomban ma is sokkal gyakoribb, ezért magyar nyelvű anyagokban is gyakran változatlanul szerepel. A lemma nem önálló kriptográfiai támadás, hanem egy számítási szabály, amely segít meghatározni egy összetett lineáris kapcsolat sikerességét. 🧮

A kifejezés etimológiája és magyar szinonimái

A piling-up két angol elemből áll: a pile jelentése „halom” vagy „kupac”, a pile up pedig azt fejezi ki, hogy valami egymásra halmozódik. A lemma görög eredetű matematikai szakkifejezés, amely egy bizonyításban felhasznált, önállóan is fontos segédállítást jelöl. Így a Piling-up lemma szó szerinti értelme körülbelül „a felhalmozódás segédtétele”.

• Halmozási lemma: a legközvetlenebb magyar fordítás.
• XOR-halmozási lemma: pontosítja, hogy XOR-műveletről van szó.
• Torzítások összeszorzásának tétele: magyarázó jellegű, nem szó szerinti elnevezés.
• XOR-torzítási lemma: szintén használható leíró magyar változat.

A magyar szinonimák közül egyik sem teljesen rögzült, ezért szakmai szövegekben célszerű az angol nevet és a magyar magyarázatot együtt használni. Például: „A Piling-up lemma, vagyis az XOR-torzítások halmozási lemmája szerint…” Ez egyszerre teszi felismerhetővé a nemzetközi fogalmat és érthetővé a jelentését az olvasó számára.

Független, torzított bitek XOR-összegének viselkedése

Legyenek (X_1, X_2, ldots, X_n) egymástól független bitek. Az egyes bitek torzítását a

[
varepsilon_i = 2P(X_i=0)-1
]

képlettel jelölhetjük. Ekkor az XOR-összeg, vagyis (X_1 oplus X_2 oplus cdots oplus X_n) torzítása:

[
varepsilon = prod_{i=1}^{n}varepsilon_i.
]

• Ha egy bit teljesen kiegyensúlyozott, akkor (varepsilon_i=0).
• Ha egy bit mindig 0, akkor (varepsilon_i=1).
• Ha egy bit mindig 1, akkor (varepsilon_i=-1).
• Az XOR-összeg 0 valószínűsége: (displaystyle P(X_1opluscdotsoplus X_n=0)=frac{1+varepsilon}{2}).

A képlet legfontosabb következménye, hogy a 0 és 1 közötti különbség gyorsan csökken, amikor több, csak kissé torzított bitet XOR-olunk össze. Ha például három bit torzítása rendre (0{,}2), (0{,}3) és (0{,}1), akkor az összesített torzítás (0{,}006), vagyis az eredmény már csak nagyon csekély mértékben tér el a teljesen kiegyensúlyozott eloszlástól. 📉

Példamondatok a Piling-up lemma gyakorlati használatára

A Piling-up lemma a gyakorlatban főként akkor jelenik meg, amikor egy kriptográfiai algoritmus több részleges lineáris összefüggését kell egyetlen összefüggéssé egyesíteni. A következő mondatok szemléltetik, hogyan használható a fogalom szakmai szövegben:

• „A három független approximáció torzítását a Piling-up lemma segítségével szoroztuk össze.”
• „Mivel az egyik részkapcsolat kiegyensúlyozott volt, a teljes XOR-közelítés torzítása nullává vált.”
• „A lemma alapján a lineáris támadás sikerességéhez nagyszámú ismert plaintext–ciphertext párra van szükség.”
• „A feltételezett függetlenség megsértése pontatlanná teheti a Piling-up lemma alkalmazását.”

Egy konkrét példában tegyük fel, hogy két független kapcsolat torzítása (0{,}25) és (0{,}4). Az XOR-összeg torzítása (0{,}25cdot0{,}4=0{,}1), ezért az összeg 0 értéke (55%)-os valószínűséggel fordul elő. Ez az eltérés még mérhető lehet, de a támadónak elegendő adatot kell gyűjtenie ahhoz, hogy a statisztikai különbséget megkülönböztesse a véletlen ingadozástól. 🔎

A Piling-up lemma egyszerű, mégis rendkívül hasznos összefüggés: megmutatja, hogy független, torzított bitek XOR-olásakor a torzítások összeszorzódnak. Emiatt több gyenge eltérés együtt gyakran már alig különböztethető meg a tökéletesen kiegyensúlyozott véletlentől.

A fogalom a lineáris kriptoanalízis alapvető eszköze, és az angol szakirodalomban továbbra is a Piling-up lemma elnevezés a legelterjedtebb. Magyarul a „halmozási lemma” vagy az „XOR-halmozási lemma” jól visszaadja a jelentését, különösen akkor, ha a képlettel és egy gyakorlati példával együtt mutatjuk be.