บทพิสูจน์แฮชที่เหลือเป็นบทพิสูจน์ในการเข้ารหัสลับ ที่ Russell Impagliazzo , Leonid LevinและMichael Lubyกล่าวไว้เป็นครั้งแรก^{[ 1 ]}

เมื่อมี กุญแจ ลับXที่ประกอบด้วยบิตสุ่มแบบสม่ำเสมอn บิต ซึ่งฝ่ายตรงข้ามสามารถเรียนรู้ค่าของบิตt < nบิตบางส่วนของกุญแจนั้นได้ ทฤษฎีบทแฮชที่เหลือระบุว่า เป็นไปได้ที่จะสร้างกุญแจที่มีประมาณn − tบิต ซึ่งฝ่ายตรงข้ามแทบไม่มีความรู้เกี่ยวกับกุญแจนั้นเลย โดยที่ไม่รู้ว่า ฝ่ายตรงข้ามรู้ค่า บิต t ใดบ้าง เนื่องจากฝ่ายตรงข้ามรู้ค่าบิตทั้งหมด ยกเว้นn − tบิต ดังนั้นวิธีนี้จึงเกือบจะเหมาะสมที่สุด

กล่าวโดยละเอียดกว่านั้น ทฤษฎีบทแฮชที่เหลืออยู่ระบุว่า เป็นไปได้ที่จะสกัดบิตที่มีความยาวโดยประมาณเท่ากับ( เอนโทรปีต่ำสุดของX ) จากตัวแปรสุ่มXที่มีการกระจายตัวเกือบสม่ำเสมอ กล่าวอีกนัยหนึ่งคือ ผู้โจมตีที่มีความรู้บางส่วนเกี่ยวกับXจะแทบไม่มีความรู้เกี่ยวกับค่าที่สกัดได้เลย นี่เป็นที่รู้จักกันในชื่อการขยายความเป็นส่วนตัว (ดูส่วนการขยายความเป็นส่วนตัวในบทความการกระจายกุญแจควอนตัม ) ${\displaystyle H_{\infty }(X)}$

ในการตั้งค่าการเข้ารหัสควอนตัม การขยายความเป็นส่วนตัวจะต้องจำกัดข้อมูลที่เก็บไว้ในระบบควอนตัมด้วย Hayashi วิเคราะห์อัตราการลดลงแบบเลขชี้กำลังของข้อมูลที่รั่วไหลสำหรับการขยายความเป็นส่วนตัวแบบสุ่มสากล โดยให้ขอบเขตเลขชี้กำลังสำหรับการแฮชสากลเพื่อป้องกันข้อมูลด้านข้างควอนตัม^{[ 2 ]}

ตัวแยกค่าสุ่มให้ผลลัพธ์เดียวกัน แต่โดยปกติแล้วจะใช้ค่าสุ่มน้อยกว่า

ให้Xเป็นตัวแปรสุ่มเหนือและให้. ให้เป็นฟังก์ชันแฮชสากล 2 มิติ . ถ้า ${\displaystyle {\mathcal {X}}}$${\displaystyle m>0}$${\textstyle h\colon {\mathcal {S}}\times {\mathcal {X}}\rightarrow \{0,\,1\}^{m}}$

${\textstyle m\leq H_{\infty }(X)-2\log \left({\frac {1}{\varepsilon }}\right)}$

ดังนั้นสำหรับSที่เป็นเอกรูปทั่วและไม่ขึ้นอยู่กับXเราจะได้ว่า: ${\displaystyle {\mathcal {S}}}$

${\textstyle \delta \left[(h(S,X),S),(U,S)\right]\leq \varepsilon .}$

โดยที่Uเป็นแบบสม่ำเสมอทั่ว^และไม่ขึ้นอยู่กับS ^{[ 3} ]${\displaystyle \{0,1\}^{m}}$

${\textstyle H_{\infty }(X)=-\log \max _{x}\Pr[X=x]}$คือค่าเอนโทรปีต่ำสุดของXซึ่งใช้วัดปริมาณความสุ่ม ของ Xค่าเอนโทรปีต่ำสุดจะมีค่าน้อยกว่าหรือเท่ากับค่าเอนโทรปีของแชนนอน เสมอ โปรดทราบว่าคือความน่าจะเป็นของการเดาค่าX ได้ถูกต้อง (การเดาที่ดีที่สุดคือการเดาค่าที่มีความน่าจะเป็นมากที่สุด) ดังนั้น ค่าเอนโทรปีต่ำสุดจึงใช้วัดความยากง่ายของการเดาค่า X${\textstyle \max _{x}\Pr[X=x]}$

${\textstyle 0\leq \delta (X,Y)={\frac {1}{2}}\sum _{v}\left|\Pr[X=v]-\Pr[Y=v]\right|\leq 1}$คือระยะ ทางเชิงสถิติระหว่างXและY

• การแฮชสากล
• เอนโทรปีขั้นต่ำ
• เอนโทรปีของเรนยี
• ความปลอดภัยเชิงทฤษฎีสารสนเทศ