กุญแจสาธารณะอยู่ใน conNP หมายความว่าอย่างไร

• เอ็น.พี คือชุดของปัญหาการตัดสินใจที่มี ตรวจสอบได้อย่างมีประสิทธิภาพ. ให้ตัวอย่าง $x$ ของปัญหาการตัดสินใจ มี "ข้อพิสูจน์" สั้นๆ $w$ ที่ให้ทั้งคู่ $(x, w)$หนึ่งสามารถตรวจสอบได้อย่างมีประสิทธิภาพว่า $x$ เป็นความจริง.

• คอป คือชุดของปัญหาการตัดสินใจที่มี หักล้างได้อย่างมีประสิทธิภาพ. ให้ตัวอย่าง $x$ ของปัญหาการตัดสินใจ มีคำว่า "dis-proof" สั้นๆ $w$ ที่ให้ทั้งคู่ $(x, w)$หนึ่งสามารถตรวจสอบได้อย่างมีประสิทธิภาพว่า $x$ เป็นเท็จ

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

1. สำหรับ RSA $N = pq$. ให้บางส่วน $N'$ ซึ่งจะใช้แบบฟอร์มนี้หรือไม่ก็ได้ เราสามารถตรวจสอบได้อย่างมีประสิทธิภาพผ่านพยาน $(พี, คิว)$.

2. สำหรับสมมติฐานประเภท DLOG ให้บางส่วน $(g, g^s)$เราสามารถตรวจสอบได้อย่างมีประสิทธิภาพในทำนองเดียวกัน $g^s$ ใช้แบบฟอร์มนี้ผ่านทางพยาน $s$

3. สำหรับโครงร่างขัดแตะ/โค้ด ให้บางส่วน $(ก, เป็น + จ)$เราสามารถตรวจสอบได้อย่างมีประสิทธิภาพ $(เป็น + e)$ ใช้แบบฟอร์มนี้ผ่านทางพยาน $(s, อี)$.

ทั้งหมดนี้หมายความว่า ด้วยคีย์ลับของ PKE บางตัว การตรวจสอบคีย์สาธารณะนั้นมีโครงสร้างถูกต้องนั้นค่อนข้างง่าย (และไม่ใช่แค่องค์ประกอบแบบสุ่ม)

ตอนนี้รหัสสาธารณะจะอยู่ในชุด conNP หากกำหนด "$pk$" นั่นคือ ไม่ กุญแจสาธารณะ (และแทนที่จะเป็นเพียง "องค์ประกอบสุ่ม") เราสามารถตรวจสอบสิ่งนี้ได้อย่างมีประสิทธิภาพ ตัวอย่างเช่น สำหรับ RSA ถ้ามีคนให้บางอย่างแก่คุณ $N$ นั่น ไม่ได้ เขียนเป็น $N = pq$คุณสามารถตรวจสอบสิ่งนี้ได้อย่างมีประสิทธิภาพผ่านการแยกตัวประกอบที่สมบูรณ์ของ $N = \prod_i p_i^{e_i}$. $((p_1, e_1),\dots,(p_k,e_k))$ จึงทำหน้าที่เป็นพยานให้ $N$ ไม่ เป็นคีย์สาธารณะ RSA และในแง่นี้คีย์สาธารณะ RSA เป็นทั้งชุด NP และชุด conNP

การอ้างสิทธิ์ในส่วนนั้นของกระดาษคือเงื่อนไขเบื้องต้น

การเข้ารหัสถูกกำหนดขึ้นและชุดของคีย์สาธารณะสร้างชุด conNP

มีข้อจำกัด โดยส่วนตัวแล้วฉันมองว่าส่วนแรกของสิ่งนี้มีข้อ จำกัด มากกว่าส่วนที่สอง ตัวอย่างเช่น สำหรับฉันแล้ว ดูเหมือนว่าในทั้งสามตัวอย่างที่ฉันกล่าวถึงข้างต้น คีย์สาธารณะสร้างชุด conNP ในสองตัวอย่างแรกนั้นชัดเจน และในตัวอย่างที่สาม ฉันคิดว่าการลดพื้นฐานที่แข็งแกร่งเพียงพอสามารถ/ควรทำงานเป็นพยานได้ โดยเฉพาะอย่างยิ่งถ้า $B$ เป็นพื้นฐานที่สั้นพอสำหรับคู่ของ $\mathcal{L}(A)$, แล้ว $(BAs + Be)$ จะเป็นเวกเตอร์ที่สั้นผิดปกติสำหรับตัวอย่าง "true LWE" แต่จะสุ่มอย่างสม่ำเสมอสำหรับตัวอย่างแบบสุ่ม เช่น จะไปเป็นพยานให้