Score:2

คำถามเกี่ยวกับรูปแบบการพิสูจน์การลด

ธง tl

ในการพิสูจน์ความปลอดภัยการเข้ารหัสส่วนใหญ่จะใช้เทคนิคการพิสูจน์การลด ตอนนี้ฉันได้อ่านบทพิสูจน์การลดหย่อนมากมายและได้ลองทำด้วยตัวเองแล้ว และฉันคิดว่าฉันเข้าใจดีทีเดียว ในขณะที่อ่านบทพิสูจน์เหล่านั้น ฉันสังเกตเห็นสองรูปแบบหลักของการลดลงดังกล่าว

สมมติว่าเรามีแบบแผน $B$ ขึ้นอยู่กับ $A$. พวกเรารู้ $A$ ปลอดภัย หากใครต้องการพิสูจน์ความปลอดภัยของ $B$ โดยลดการรักษาความปลอดภัยของ $A$ เขาสามารถดำเนินการได้ดังนี้:

  1. สไตล์: สมมติว่าเป็นศัตรูที่สามารถทำลายได้ $B$ $\ลูกศรขวา$ สำหรับการลดลงสามารถสร้างศัตรูใหม่ขึ้นมาได้ $A$ ใช้ทำลายศัตรู $B$ $\ลูกศรขวา$ ผลที่ได้คือความขัดแย้งที่แสดงให้เห็นว่าไม่มีศัตรูที่ไม่มีความสำคัญเลย $B$
  2. สไตล์: สมมติว่าเป็นฝ่ายตรงข้าม ppt ตามอำเภอใจ $B$ $\ลูกศรขวา$ แสดง (เช่น ด้วยการวิเคราะห์แบบสุ่มของการทดลอง) ที่ทำลาย $B$ ยากพอ ๆ กับการทำลาย $A$จึงลดความซับซ้อนของการทำลายลง $B$ ถึงความซับซ้อนของการแตกหัก $A$ $\ลูกศรขวา$ เนื่องจากมีศัตรูเพียงเล็กน้อยเท่านั้นที่ต่อต้าน $A$ ไม่มีศัตรูที่ไม่สำคัญเลย $B$

แน่นอนว่าสิ่งนี้ทำให้ง่ายขึ้น แต่ฉันอยากให้คุณเข้าใจสิ่งที่ฉันสังเกตเห็น

คำถามของฉัน: สไตล์เหล่านี้มีอยู่จริงไหม? พวกเขาทั้งสอง (เขียนอย่างถูกต้องอย่างเป็นทางการ) สามารถพิสูจน์เหมือนกันได้หรือไม่? พวกเขาทั้งสอง (โดยเฉพาะรูปแบบที่ 1.) สมบูรณ์หรือไม่? ควรใช้รูปแบบใดในการพิสูจน์

แก้ไข: คำจำกัดความที่ชัดเจนยิ่งขึ้นของรูปแบบที่ 2: ในความรู้เบื้องต้นเกี่ยวกับการเข้ารหัสสมัยใหม่ พิสูจน์ระบบเข้ารหัสลับบน PRG: ในการวิเคราะห์สุ่ม พวกเขาระบุว่า การทำลายระบบเข้ารหัสลับนั้นมีความเป็นไปได้พอๆ กับการทำลาย PRGพวกเขาใช้สิ่งนี้เพื่อบอกเป็นนัยว่าฝ่ายตรงข้ามตามอำเภอใจจะต้องไม่คำนึงถึงรูปแบบนี้: เนื่องจากสิ่งนี้เล็กน้อยและพวกเขาก็มีโอกาสเหมือนกัน อีกฝ่ายหนึ่งจึงต้องไม่มีความสำคัญ

(หมายเหตุ: โดยย่อ ฉันจะอธิบาย 1. เป็น: $B \rightarrow A \rightarrow \unicode{x21af} \rightarrow B$ และ 2. เป็น: $B \rightarrow A \rightarrow (B = A) \rightarrow B$)

us flag
ใน #2: "แสดงว่าการทำลาย B นั้นยากพอๆ กับการทำลาย A" แตกต่างจาก #1 อย่างไร คุณจะแสดงสิ่งนี้อย่างไร นอกเหนือจากการใช้ศัตรู B ที่ประสบความสำเร็จเพื่อสร้างศัตรู A ที่ประสบความสำเร็จ คุณหมายถึงอะไรโดย "การวิเคราะห์แบบสุ่มของการทดลอง"? คุณมีตัวอย่างในใจของสิ่งที่คุณหมายถึง #2 หรือไม่?
Titanlord avatar
tl flag
ฉันคิดว่า [ตำราเรียนของ Katz & Lindell (ฉบับที่ 2)](https://www.cs.umd.edu/~jkatz/imc.html)) ใช้รูปแบบที่ 2 เช่น เพื่อพิสูจน์ PRG cryptoscheme ที่พวกเขาสร้างขึ้น
cn flag
@Mikero มันแตกต่างตรงที่คุณหลีกเลี่ยงการใช้การโต้แย้งโดยไม่จำเป็นและสับสนโดยไม่จำเป็น รูปแบบที่ 1 ทำให้คำสั่ง "*A* และ *not B* หมายถึงความขัดแย้ง" จากนั้นคุณสรุปว่า *B* เพราะคุณถือว่า *A* รูปแบบที่ 2 ในทางกลับกัน ทำให้คำสั่ง "*A* หมายถึง *B*" โดยตรง หลีกเลี่ยงการอ้อมที่ไม่จำเป็น ผลลัพธ์สุดท้ายจะเหมือนกันเว้นแต่คุณจะมีมุมมองแปลก ๆ เกี่ยวกับตรรกะ
us flag
@เมเฮอร์ น่าสนใจฉันไม่พบสไตล์ # 1 ที่จำเป็นต้องพิสูจน์ด้วยความขัดแย้ง ฉันตีความว่า "ถ้า A หัก B ก็หักด้วย" สิ่งที่ตรงกันข้ามคือถ้า B ปลอดภัยกว่า A จะปลอดภัย มีรูปแบบการพิสูจน์อื่น ๆ (ซึ่งฉันชอบจริง ๆ ) ที่หลีกเลี่ยงการสลับไปมาระหว่างการตีความที่ขัดแย้งกัน และอยู่ในโลกของ "ถ้า B ปลอดภัยกว่า A ปลอดภัย" แต่ฉันไม่รู้จัก #2 ในสิ่งนี้ คำถามเป็นคำอธิบายของรูปแบบนั้น
kelalaka avatar
in flag
มันเป็นเรื่องจริงที่บางครั้ง $p \implies q$ ไม่สามารถแสดงได้อย่างชัดเจน และสิ่งที่ตรงกันข้ามอาจแสดงได้ง่ายกว่า นั่นคือเหตุผลที่เราเลือกพวกเขา CS มีคำถามเกี่ยวกับการลดลงซึ่งคำนี้มาจาก [1](https://cs.stackexchange.com/q/11209/94479) และแม้แต่พวกเขาก็มีแท็ก [การลดลง](https://cs.stackexchange.com /questions/tagged/reductions?tab=Votes)
cn flag
@Mikero นี่อาจไม่ใช่การสนทนาที่ดีในความคิดเห็น แต่ฉันกำลังอ่านสไตล์ 1 เพื่ออ้างถึงการพิสูจน์ของแบบฟอร์ม "สมมติว่ามีเครื่อง PPT ที่แบ่ง A ด้วยความได้เปรียบที่ไม่ละเลย จากนั้นมี มีเครื่อง PPT ที่แบ่ง B ด้วยความได้เปรียบที่ไม่ละเลย ซึ่งขัดแย้งกับสมมติฐานที่ว่า B ปลอดภัย ดังนั้น A จึงไม่มีอยู่จริง" ในขณะที่รูปแบบที่ 2 กล่าวว่า "พิจารณาเครื่อง PPT ตามอำเภอใจ จากนั้นถือว่า B มีความปลอดภัย ข้อได้เปรียบของเครื่องนี้ถือว่าเล็กน้อย"
kelalaka avatar
in flag
สไตล์ที่สองต้องการการเขียนที่ดีขึ้นจาก Titanlord
Score:1
ธง ng

ข้อแตกต่างเพียงอย่างเดียวที่ฉันเห็นระหว่างรูปแบบที่ 1 และการแก้ไขที่ถูกต้องของรูปแบบที่ 2 คือรูปแบบที่ 1 ไม่มีสิ่งที่ชัดเจนในข้อที่ 2 เกี่ยวกับฝ่ายตรงข้าม/อัลกอริทึมที่ตั้งสมมติฐานให้โจมตี B และผลลัพธ์ที่เป็นปฏิปักษ์/อัลกอริทึมที่จะโจมตี A:

  1. อัลกอริทึมคือ Probabilistic Polynomial-Time; ที่มีอินพุตโดยปริยายพร้อมบิตสุ่ม และเรียกใช้พหุนามบางชื่อในช่วงเวลาหนึ่ง $P(n)$ สำหรับค่าพารามิเตอร์ความปลอดภัยทั้งหมด $n$ (หรือขนาดอินพุต) ผ่านขอบล่างบางส่วน
  2. พวกเขามีความน่าจะเป็นที่จะประสบความสำเร็จแบบไม่ละเลย (หรือไม่หายไป) นั่นคือ: สำหรับพหุนามบางตัว $P'$สำหรับขอบเขตคงที่ใดๆ $N\in\mathbb{N}$ มีค่าที่มีอยู่ $n>N$ สำหรับพารามิเตอร์ความปลอดภัย (หรือขนาดอินพุต) เพื่อให้ความน่าจะเป็นของความสำเร็จเป็นอย่างน้อย $1/P'(n)>0$.

เป็นเครื่องพิสูจน์ว่า “การทำลายระบบเข้ารหัสนั้นมีโอกาสพอๆ กับการทำลาย PRG” พิสูจน์ว่าใน 2 เราสามารถนำพหุนามกลับมาใช้ใหม่ได้ $P'$ และคุณค่าของ $n$ สำหรับขอบเขตที่กำหนด $N$ ที่เหมาะสมสำหรับการโจมตีตามสมมติฐานของ B ในการพิสูจน์ว่าการโจมตีของ A นั้นมีความเป็นไปได้ที่จะสำเร็จอย่างไม่มีนัยสำคัญ

กล่าวอีกนัยหนึ่ง รูปแบบที่ 1 เป็นการทำให้รูปแบบที่ 2 ง่ายขึ้น ซึ่งมักจะต้องสูญเสียความเข้มงวดไป สำหรับการพิสูจน์บางอย่างในรูปแบบที่ 1 มันจะได้รับการควบคุมสไตล์ที่ 2 เพื่อบอกได้อย่างมั่นใจว่าการพิสูจน์นั้นถูกต้องหรือไม่

มีสไตล์ที่ซับซ้อนมากยิ่งขึ้น เช่น โดยความน่าจะเป็นของความสำเร็จเป็นเชิงปริมาณในกรณีนี้, “การทำลายระบบเข้ารหัสนั้นมีโอกาสพอๆ กับการทำลาย PRG” เป็นสิ่งที่เรียกว่า หลักฐานแน่น. การพิสูจน์เชิงปริมาณอื่น ๆ นั้นยากที่จะปฏิบัติตาม

cn flag
เครื่อง PPT ทำงานในเวลาพหุนาม *เข้มงวด* ไม่ใช่ * เวลาพหุนามที่คาดไว้
cn flag
นอกจากนี้ ในข้อ 2. สิ่งที่คุณอธิบายคือความน่าจะเป็น *สังเกตได้* สิ่งนี้ *ไม่* มีความหมายเหมือนกันกับ non-negligible
fgrieu avatar
ng flag
@Maeher: ฉันใช้คำของคุณเกี่ยวกับคำจำกัดความของ PPT และฉันคิดว่าฉันเข้าใจและแก้ไขข้อผิดพลาดของฉันในคำจำกัดความของ non-negligible ขอบคุณสำหรับการแก้ไข!
cn flag
ฉันได้พยายามทำให้ประเด็นนั้นชัดเจนขึ้น เพียงย้อนกลับการแก้ไขหากคุณไม่ชอบ

โพสต์คำตอบ

คนส่วนใหญ่ไม่เข้าใจว่าการถามคำถามมากมายจะปลดล็อกการเรียนรู้และปรับปรุงความสัมพันธ์ระหว่างบุคคล ตัวอย่างเช่น ในการศึกษาของ Alison แม้ว่าผู้คนจะจำได้อย่างแม่นยำว่ามีคำถามกี่ข้อที่ถูกถามในการสนทนา แต่พวกเขาไม่เข้าใจความเชื่อมโยงระหว่างคำถามและความชอบ จากการศึกษาทั้ง 4 เรื่องที่ผู้เข้าร่วมมีส่วนร่วมในการสนทนาด้วยตนเองหรืออ่านบันทึกการสนทนาของผู้อื่น ผู้คนมักไม่ตระหนักว่าการถามคำถามจะมีอิทธิพลหรือมีอิทธิพลต่อระดับมิตรภาพระหว่างผู้สนทนา