Sog'lomlik (interaktiv isbot) - Soundness (interactive proof)

Sog'lomlik ning mulki hisoblanadi interaktiv isbotlash tizimlari Buning uchun hech qanday prover tekshiruvchini noto'g'ri bayonot uchun qabul qila olmaydi ${ displaystyle y not in L}$ kichik ehtimollikdan tashqari. Ushbu ehtimollikning yuqori chegarasi isbot tizimining aniqligi xatosi deb ataladi.

Rasmiy ravishda, har bir prover uchun ${ displaystyle ({ tilde { mathcal {P}}})}$va har bir ${ displaystyle y not in L}$:

${ displaystyle Pr [( perp, ({ text {accept}})) gets ({ tilde { mathcal {P}}}) (y) leftrightarrow ({ mathcal {V}}) ( y)] < epsilon.}$

kimdir uchun ${ displaystyle epsilon ll 1}$.Sustalik xatosi tekshiruvchining potentsial ishlash vaqtining polinomal qismi bilan chegaralangan ekan (ya'ni.) ${ displaystyle epsilon leq 1 / mathrm {poly} (| y |)}$), har doim tovushni xatolik paydo bo'lguncha kuchaytirish mumkin ahamiyatsiz funktsiya tekshiruvchining ishlash vaqtiga nisbatan. Bunga dalilni takrorlash va barcha dalillar tasdiqlangan taqdirdagina qabul qilish orqali erishiladi. Keyin ${ displaystyle ell}$ takrorlash, mustahkamlik xatosi ${ displaystyle epsilon}$ ga kamaytiriladi ${ displaystyle epsilon ^ { ell}}$.^[1]

Shuningdek qarang

• Interaktiv isbotlash tizimi
• Bilimning isboti
• Nolinchi ma'lumotni isbotlash

Adabiyotlar

Ushbu kriptografiya bilan bog'liq maqola a naycha. Siz Vikipediyaga yordam berishingiz mumkin uni kengaytirish.