ข้อได้เปรียบเล็กน้อยสำหรับ DDH นั้นเล็กน้อยแค่ไหน?

ข้อสันนิษฐาน Diffie Hellman Decisional (DDH) ที่รู้จักกันดียืนยันว่าสำหรับข้อใดข้อหนึ่ง $n = \log คิว$ และเครื่องกำเนิดไฟฟ้า $g$ ของ $\mathbb{Z}_q$, สำหรับ i.i.d $A, B, C \sim U(\mathbb{Z}_q)$ต่อไปนี้จะแยกไม่สำหรับ PPT ใด ๆ $M$: $g^A, g^B, g^C$ เทียบกับ $g^A, g^B, g^{AB}$. นั่นคือถึงข้อได้เปรียบเล็กน้อย: $$\epsilon = \left| \Pr[M(g^A, g^B, g^C) = 1] - \Pr [M(g^A, g^B, g^{AB}) = 1 \right| \leq 1/\omega(n) $$ ฉันสนใจว่าข้อผิดพลาดเล็ก ๆ น้อย ๆ สามารถทำได้อย่างไร? นั่นคือมีความแตกต่างสำหรับสิ่งที่เล็กมากหรือไม่ $\epsilon = 2^{-O(n)}$? เป็นที่ทราบกันดีว่าควร ``เล็กน้อย'' อย่างไร $\epsilon$ เป็น?

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

ฟังก์ชั่น $\mu$ จะเล็กน้อยถ้ามันเติบโตช้า (หรือสลายตัวเร็วกว่า) มากกว่า 1 ในฟังก์ชันพหุนามใดๆ โดยเฉพาะสำหรับพหุนามใดๆ $\mathsf{โพลี}$สำหรับค่าคงที่บางอย่าง $N$แล้วสำหรับทุกคน $x \geq N$, เรามี: $$|\mu(x)| < \frac{1}{\mathsf{poly}(x)}.$$

ตัวอย่างของฟังก์ชันเล็กน้อยคือ $\mu(x) = 2^{-x}$. นี่เป็นเพราะพหุนามใด ๆ เราสามารถหา $N$ เช่นเดียวกับความไม่เท่าเทียมกันก่อนหน้านี้ เนื่องจากการสลายตัวเป็นแบบเลขชี้กำลัง เช่น การใช้พหุนาม $x^3$, อสมการไม่ได้อยู่ที่ $x = 2$ (เนื่องจาก $1/4 > 1/8$), $x = 3$ (เนื่องจาก $1/8 > 1/27$) และอื่นๆ แต่เมื่อ $x \geq 10$จากนั้นอสมการจะคงอยู่ (เช่น $2^{-10} < 1/10^3$). ดังนั้นใน eaxmple เฉพาะนี้ เราจะตั้งค่า $N = 10$.

ในตัวอย่างเฉพาะของ DDH สมมติว่า $M$ ใช้เวลาพหุนามในการคำนวณ DDH แบบสุ่มสามเท่า ($g^a,g^b,g^{ab}$). จากนั้นมีความเป็นไปได้เล็กน้อยที่ความท้าทาย DDH ที่ได้รับนั้นเป็นความท้าทายที่คำนวณได้ ดังนั้นมันจะชนะ เล็กน้อย มากกว่า $1/2$ เวลา (ชนะครึ่งเวลาจากการเดาแบบสุ่มอย่างสม่ำเสมอ) อย่างไรก็ตาม ข้อได้เปรียบนี้ไม่มีนัยสำคัญในแง่ทางเทคนิค เนื่องจากเป็น $M$ เป็น PPT มันสามารถคำนวณได้เฉพาะหลายสิ่งอันดับพหุนาม แต่จำนวนของสิ่งอันดับที่เป็นไปได้จะเพิ่มขึ้นแบบทวีคูณด้วยพารามิเตอร์ความปลอดภัย ดังนั้นข้อได้เปรียบจึงมีลักษณะดังนี้ $\textsf{poly}(\kappa)/2^{\kappa}$ซึ่งไม่สำคัญในแง่ที่เป็นทางการข้างต้น