ในการวิเคราะห์การเข้ารหัส บทพิสูจน์การซ้อนทับ ( piling -up lemma)เป็นหลักการที่ใช้ในการวิเคราะห์การเข้ารหัสเชิงเส้นเพื่อสร้างการประมาณเชิงเส้นของการทำงานของการเข้ารหัสแบบบล็อก บทพิสูจน์นี้ได้รับการแนะนำโดยMitsuru Matsui (1993) ในฐานะเครื่องมือวิเคราะห์สำหรับการวิเคราะห์การเข้ารหัสเชิงเส้น^{[ 1 ]}บทพิสูจน์นี้ระบุว่าอคติ (การเบี่ยงเบนของค่าที่คาดหวังจาก 1/2) ของฟังก์ชันบูลีนเชิงเส้น (XOR-clause) ของตัวแปรสุ่มไบนารีอิสระ มีความสัมพันธ์กับผลคูณของอคติอินพุต: ^{[ 2 ]}

${\displaystyle \varepsilon (X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=2^{n-1}\prod _{i=1}^{n}\varepsilon (X_{i})}$

หรือ

${\displaystyle I(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=\prod _{i=1}^{n}I(X_{i})}$

อคติ (ไปทางศูนย์^{[ 3 ]} ) และความไม่สมดุล อยู่ ที่ไหน: ^{[ 4 ] [ 5 ]}${\displaystyle \varepsilon \in [-{\tfrac {1}{2}},{\tfrac {1}{2}}]}$${\displaystyle I\in [-1,1]}$

${\displaystyle \varepsilon (X)=P(X=0)-{\frac {1}{2}}}$

${\displaystyle I(X)=P(X=0)-P(X=1)=2\varepsilon (X).}$

ในทางกลับกัน หากบทพิสูจน์ไม่เป็นจริง ตัวแปรอินพุตจะไม่เป็นอิสระ^{[ 6 ]}

บทพิสูจน์ย่อยนี้บ่งชี้ว่า การนำตัวแปรไบนารีอิสระมาทำการ XOR จะช่วยลดอคติลงเสมอ (หรืออย่างน้อยก็ไม่ทำให้อคติเพิ่มขึ้น) ยิ่งไปกว่านั้น ผลลัพธ์จะไม่มีอคติก็ต่อเมื่อมีตัวแปรป้อนเข้าอย่างน้อยหนึ่งตัวที่ไม่มีอคติ

โปรด ทราบ ว่าสำหรับ ตัวแปร สองตัว ปริมาณดังกล่าวเป็นการวัดความสัมพันธ์ระหว่าง และ ซึ่งเท่ากับ;สามารถตีความได้ว่าเป็นความสัมพันธ์ระหว่างกับ${\displaystyle I(X\oplus Y)}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle P(X=Y)-P(X\neq Y)}$${\displaystyle I(X)}$${\displaystyle X}$${\displaystyle 0}$

ทฤษฎีบทการซ้อนทับสามารถแสดงออกมาได้อย่างเป็นธรรมชาติมากขึ้นเมื่อตัวแปรสุ่มมีค่าอยู่ใน⁠ ⁠${\displaystyle \{-1,1\}}$ถ้าเราแนะนำตัวแปร(ที่แมป⁠ ⁠ไปยัง⁠ ⁠และ⁠ ⁠ไปยัง⁠ ⁠ ) แล้ว เมื่อพิจารณาดูแล้ว การดำเนินการ XOR จะแปลงเป็นผลคูณ: ${\displaystyle \chi _{i}=1-2X_{i}=(-1)^{X_{i}}}$${\displaystyle 0}$${\displaystyle 1}$${\displaystyle 1}$${\displaystyle -1}$

${\displaystyle \chi _{1}\chi _{2}\cdots \chi _{n}=1-2(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n})=(-1)^{X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}}}$

และเนื่องจากค่าที่คาดหวังคือความไม่สมดุลดังนั้น${\displaystyle E(\chi _{i})=I(X_{i})}$บทพิสูจน์จึงระบุว่า :

${\displaystyle E\left(\prod _{i=1}^{n}\chi _{i}\right)=\prod _{i=1}^{n}E(\chi _{i}),}$

ซึ่งเป็นคุณสมบัติที่ทราบกันดีของค่าคาดหวังสำหรับตัวแปรอิสระ

สำหรับตัวแปรตาม สูตรข้างต้นจะเพิ่มพจน์ ความแปรปรวนร่วม (บวกหรือลบ) เข้ามา ดังนั้นบทพิสูจน์ย่อยจึงไม่เป็นจริง อันที่จริง เนื่องจาก ตัวแปร เบอร์นูลลี สองตัว จะเป็นอิสระต่อกันก็ต่อเมื่อไม่มีความสัมพันธ์กัน (กล่าวคือ มีความแปรปรวนร่วมเป็นศูนย์ ดูที่ภาวะไม่มีความสัมพันธ์กัน ) เราจึงได้สิ่งที่ตรงกันข้ามกับบทพิสูจน์ย่อยเรื่องการทับซ้อนกัน กล่าวคือ ถ้าบทพิสูจน์ย่อยนี้ไม่เป็นจริง ตัวแปรเหล่านั้นจะไม่เป็นอิสระต่อกัน (ไม่มีความสัมพันธ์กัน)

ทฤษฎีบทการสะสมช่วยให้นักวิเคราะห์รหัสสามารถกำหนดความน่าจะเป็นที่ความเท่าเทียมกันนั้นเป็นจริงได้:

${\displaystyle X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0}$

โดยที่s${\displaystyle X}$เป็นตัวแปรไบนารี ( นั่นคือ บิต: ⁠ ⁠${\displaystyle 0}$หรือ⁠ ⁠ ${\displaystyle 1}$)

ให้⁠ ⁠${\displaystyle P(A)}$แทน "ความน่าจะเป็นที่⁠ ⁠${\displaystyle A}$เป็นจริง" ถ้าเท่ากับหนึ่ง ⁠ ⁠${\displaystyle A}$จะเกิดขึ้นอย่างแน่นอน และถ้าเท่ากับศูนย์⁠ ⁠ ${\displaystyle A}$จะ ไม่เกิดขึ้น ก่อนอื่น เราจะพิจารณาทฤษฎีบทการซ้อนทับสำหรับ ตัวแปร ไบนารีสองตัว โดยที่และ⁠ ⁠${\displaystyle P(X_{1}=0)=p_{1}}$${\displaystyle P(X_{2}=0)=p_{2}}$

ต่อไปนี้ เรามาพิจารณาสิ่งต่อไปนี้:

${\displaystyle P(X_{1}\oplus X_{2}=0).}$

เนื่องจากคุณสมบัติของ การดำเนินการ XORทำให้สิ่งนี้เทียบเท่ากับ

${\displaystyle P(X_{1}=X_{2}).}$

และ${\displaystyle X_{1}=X_{2}=0}$เป็นเหตุการณ์ที่ไม่เกิดขึ้นพร้อมกันดังนั้นเราจึง${\displaystyle X_{1}=X_{2}=1}$สามารถกล่าวได้ ว่า

${\displaystyle P(X_{1}=X_{2})=P(X_{1}=X_{2}=0)+P(X_{1}=X_{2}=1)=P(X_{1}=0,X_{2}=0)+P(X_{1}=1,X_{2}=1).}$

ตอนนี้ เราต้องตั้งสมมติฐานหลักของทฤษฎีบทการสะสมผล: ตัวแปรไบนารีที่เรากำลังพิจารณานั้นเป็นอิสระต่อกันกล่าวคือ สถานะของตัวแปรหนึ่งไม่มีผลต่อสถานะของตัวแปรอื่น ๆ ดังนั้น เราสามารถขยายฟังก์ชันความน่าจะเป็นได้ดังนี้:

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =P(X_{1}=0)P(X_{2}=0)+P(X_{1}=1)P(X_{2}=1)}$
	${\displaystyle =p_{1}p_{2}+(1-p_{1})(1-p_{2})}$
	${\displaystyle =p_{1}p_{2}+(1-p_{1}-p_{2}+p_{1}p_{2})}$
	${\displaystyle =2p_{1}p_{2}-p_{1}-p_{2}+1}$

ตอนนี้เราแสดงความน่าจะเป็น⁠ ⁠${\displaystyle p_{1}}$และ⁠ ⁠${\displaystyle p_{2}}$เป็น⁠ ⁠${\displaystyle {\tfrac {1}{2}}+\varepsilon _{1}}$และ⁠ ⁠${\displaystyle {\tfrac {1}{2}}+\varepsilon _{2}}$โดยที่⁠ ⁠${\displaystyle \varepsilon }$คือค่าเบี่ยงเบนความน่าจะเป็น – จำนวนที่ความน่าจะเป็นเบี่ยงเบนไปจาก ⁠ ⁠${\displaystyle {\tfrac {1}{2}}}$

${\displaystyle P(X_{1}\oplus X_{2}=0)}$	${\displaystyle =2(1/2+\varepsilon _{1})(1/2+\varepsilon _{2})-(1/2+\varepsilon _{1})-(1/2+\varepsilon _{2})+1}$
	${\displaystyle =1/2+\varepsilon _{1}+\varepsilon _{2}+2\varepsilon _{1}\varepsilon _{2}-1/2-\varepsilon _{1}-1/2-\varepsilon _{2}+1}$
	${\displaystyle =1/2+2\varepsilon _{1}\varepsilon _{2}}$

ดังนั้น ความเอนเอียงของความน่าจะเป็นสำหรับ${\displaystyle \varepsilon _{1,2}}$ผลรวม XOR ข้างต้นคือ⁠ ⁠${\displaystyle 2\varepsilon _{1}\varepsilon _{2}}$ .

สูตรนี้สามารถขยายไปใช้กับค่าอื่นๆ ได้มากขึ้นดังนี้${\displaystyle X}$ :

${\displaystyle P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)=1/2+2^{n-1}\prod _{i=1}^{n}\varepsilon _{i}}$

โปรดทราบว่าหากค่าใดค่าหนึ่งของs เป็น${\displaystyle \varepsilon }$ ศูนย์ นั่นคือ ตัวแปรไบนารีตัวใดตัวหนึ่งไม่มี อคติ ฟังก์ชันความน่าจะเป็นทั้งหมดก็จะไม่มีอคติเช่นกัน ซึ่งเท่ากับ⁠ ⁠${\displaystyle {\tfrac {1}{2}}}$

นิยามที่เกี่ยวข้องอีกแบบหนึ่งที่แตกต่างออกไปเล็กน้อยของอคติคือ⁠ ⁠${\displaystyle \varepsilon _{i}=P(X_{i}=1)-P(X_{i}=0)}$ซึ่งก็คือลบด้วยค่าก่อนหน้าสองเท่า ข้อดีคือตอนนี้ด้วย

${\displaystyle \varepsilon _{\text{total}}=P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=1)-P(X_{1}\oplus X_{2}\oplus \cdots \oplus X_{n}=0)}$

เรามี

${\displaystyle \varepsilon _{\text{total}}=(-1)^{n+1}\prod _{i=1}^{n}\varepsilon _{i},}$

การบวกตัวแปรสุ่มเท่ากับการคูณค่าความเอนเอียง (ตามความหมายที่ 2) ของตัวแปรเหล่านั้น

ในทางปฏิบัติ ค่าs เป็น${\displaystyle X}$ค่าประมาณของS-box (ส่วนประกอบการแทนที่) ของการเข้ารหัสแบบบล็อก โดยทั่วไปค่า s จะ${\displaystyle X}$เป็นอินพุตของ S-box และ ค่า s จะเป็นเอาต์พุตที่สอดคล้องกัน เพียงแค่ดูที่ S-box นักวิเคราะห์รหัสก็สามารถบอกได้ว่าความเอนเอียงของความน่าจะ เป็น${\displaystyle Y}$เป็นอย่างไร เคล็ดลับคือการหาชุดค่าผสมของอินพุตและเอาต์พุตที่มีความน่าจะเป็นเป็นศูนย์หรือหนึ่ง ยิ่งค่าประมาณใกล้เคียงกับศูนย์หรือหนึ่งมากเท่าใด ค่าประมาณนั้นก็จะยิ่งมีประโยชน์มากขึ้นในการวิเคราะห์รหัสเชิงเส้น

อย่างไรก็ตาม ในทางปฏิบัติ ตัวแปรไบนารีไม่ได้เป็นอิสระต่อกันอย่างที่สมมติไว้ในการพิสูจน์ทฤษฎีบทการซ้อนทับ (piling-up lemma) จึงต้องคำนึงถึงข้อนี้เมื่อนำทฤษฎีบทนี้ไปใช้ มันไม่ใช่สูตรการถอดรหัสอัตโนมัติ

• ความแปรปรวน § คุณสมบัติ – ความแปรปรวนของผลรวมของตัวแปรจริงอิสระ