การที่ g และ h มีส่วนผูกพันในข้อผูกพันของ pedersen หมายความว่าอย่างไร

ฉันกำลังดูที่ รายงานการวิจัย เกี่ยวกับความไม่ปลอดภัยของการใช้สัญญาผูกมัด Pedersen ที่เฉพาะเจาะจง (ผิด)

ก่อนอื่น ฉันจะอธิบายขั้นตอนต่างๆ ของคำมั่นสัญญาของ Pedersen เพื่อให้สามารถแสดงให้เห็นได้หากฉันมีความเข้าใจผิดพื้นฐาน

ความเข้าใจของฉันเกี่ยวกับพันธสัญญาของ Pedersen

ประการแรก เราบอกว่า Bob ต้องการให้ Alice ส่งข้อความ ดังนั้นเขาจึงสร้างจำนวนเฉพาะขึ้นมาสองตัว หน้า และ ถาม.

p <--- ไพรม์สุ่ม q <--- ไพรม์สุ่ม

บ็อบจึงสร้างเครื่องกำเนิดไฟฟ้า กรัมซึ่งเป็นคำสั่งของ ถาม และอยู่ในกลุ่ม $Z_{p}^*$.

ก <--- $\in Z_{q}^*$

จากนั้นเขาก็เลือกค่าลับ x ใน $Z_{q} $:

x <--- $\in Z_{q} $

x เป็นรหัสลับซึ่งเขาใช้เพื่อรับรหัสสาธารณะ:

$h = g^{x} ม็อด p $

ตอนนี้อลิซต้องการส่งข้อความใดข้อความหนึ่ง และมีสิทธิ์เข้าถึงรหัสสาธารณะและรหัสลับของบ๊อบ เธอเลือกข้อความก่อน ม และจำนวนเต็มแบบสุ่ม รแล้วคำนวณความมุ่งมั่นของเธอ ค:

ค = $ g^{m}*h^{r}$

ตอนนี้อลิซสามารถส่งคำมั่นสัญญาไปให้บ๊อบได้แล้ว เมื่ออลิซต้องการเปิดเผยความมุ่งมั่นของเธอ เธอก็ส่ง ม และ `r`` ถึง Bob ตอนนี้ Bob สามารถคำนวณและเปรียบเทียบสิ่งเดียวกันได้แล้ว

การประยุกต์ใช้ในการลงคะแนนเสียงและปัญหาความเป็นอิสระ

ในบทความที่อ้างถึงก่อนหน้านี้ โครงร่างนี้ใช้เพื่อยืนยันความสมบูรณ์ของชุดการลงคะแนนแบบสับเปลี่ยน ในบริบทนี้ รายการของ น การลงคะแนนที่เข้ารหัสจะแสดงโดย $ m_{1},...,m_{n} $. จากนั้น คำมั่นสัญญาของ pedersen สำหรับรายการโหวตจะถูกคำนวณโดย:

$ c = G_{1}^{m_1} ... G_{n}^{m_n} * H^{r}$

แล้วเอกสารก็พูดถึงค่าของ ช และ ชม (อาจมีความสับสนในสัญกรณ์เนื่องจากฉันคุ้นเคยกับการใช้ตัวพิมพ์เล็ก g และ h สำหรับตัวสร้างสำหรับตัวสร้างและ PK ในขณะที่กระดาษเลือกใช้ตัวพิมพ์ใหญ่) แต่กระดาษระบุปัญหาต่อไปนี้ที่อาจเกิดขึ้น:

"หากความเป็นอิสระถูกละเมิดระหว่าง H กับ Gi ค่าเดียว ความมุ่งมั่นเพิ่มเติม c สามารถเปิดสำหรับเวกเตอร์ของข้อความทางเลือกใดๆ mâ²1,..., mâ²n หากสิ่งนี้เกิดขึ้น อาร์กิวเมนต์พิสูจน์การสับเปลี่ยนทั้งหมดจะพังทลายลง กล่าวคือ เป็นไปได้ที่จะสร้างหลักฐานปลอมสำหรับการสุ่มที่ไม่ถูกต้อง"

ฉันสับสนเล็กน้อยว่ามันหมายถึงอะไรสำหรับค่าของ $G_{i}$ และ H เป็น "อิสระ" และน่าจะหมายถึงเมื่อเรามีเวอร์ชันต่างๆ ของ ชดังนั้นฉันจึงมีคำถามสองข้อ:

1

ถ้าเรามี n G หมายความว่ากลุ่มที่เราทำงานอยู่จำเป็นต้องมีตัวกำเนิด n ตัวใช่หรือไม่

2 จะมีหนึ่ง H และเครื่องกำเนิดไฟฟ้าหลายเครื่องได้อย่างไร? ถ้า ชม คำนวณโดยใช้ ชแล้วซึ่ง ช ใช้ในการคำนวณคีย์สาธารณะ ชม. บางทีฉันอาจเข้าใจผิดเกี่ยวกับสิ่งพื้นฐานเกี่ยวกับการก่อสร้างที่ระบุไว้ในกระดาษ

ฉันสับสนเล็กน้อยว่ามันหมายถึงอะไรสำหรับค่าของ $G_i$ และ $H$ เป็น "อิสระ"

อันที่จริง บทความนี้ให้คำจำกัดความที่ค่อนข้างดี:

ความเป็นอิสระหมายถึงลอการิทึมที่ไม่ต่อเนื่องตามลำดับ $h = \log_G H$ และ $g = \log_H G$ ไม่เป็นที่รู้จักสำหรับทุกคน

นั่นคือไม่มีใครควรรู้วิธีแก้ปัญหา $x$ ถึง $G^x = H$

อย่างไรก็ตาม เนื่องจากเรากำลังทำงานกับเครื่องกำเนิดหลายตัว ปรากฎว่าเราต้องการคำชี้แจงที่หนักแน่นกว่า นั่นคือไม่มีใครทราบวิธีแก้ปัญหาที่ไม่น่าสนใจ $(a_1, a_2, ..., a_n, b)$ สำหรับความสัมพันธ์ $G_1^{a_1} \cdot G_2^{a_2} \cdot ... \cdot G_n^{a_n} \cdot H^b = 1$ซึ่งวิธีแก้ปัญหาเล็กน้อยคือ $a_1 \equiv a_2 \equiv ... \equiv a_n \equiv b \equiv 0$.

อย่างไรก็ตาม ใช้แนวคิดเดียวกัน

ถ้าเรามี $n$ $G$หมายความว่ากลุ่มที่เราทำงานอยู่จำเป็นต้องมี $n$ เครื่องกำเนิดไฟฟ้า?

ใช่. จริงๆ แล้ว เรามีอีกมาก ถ้าเราจัดการกับกลุ่มที่มีขนาด $คิว$ ที่ไหน $คิว$ เป็นนายกแล้วจะมี $q-1$ เครื่องกำเนิดไฟฟ้า เพราะเราต้องการ $คิว$ เป็นอย่างน้อย 256 บิต (เพื่อทำให้ปัญหาล็อกแยกยาก) นั่นหมายความว่าเรามีไฟล์ ใหญ่ จำนวนเครื่องปั่นไฟที่เราสามารถใช้ได้

จะมีได้อย่างไร $H$, และเครื่องกำเนิดไฟฟ้าหลายเครื่อง? ถ้า $H$ คำนวณโดยใช้ $G$,

ที่จริงเราไม่ได้คำนวณ $H$ โดยใช้ $G$เราเลือกมันอย่างอิสระ

ตอนนี้ ถ้าคุณกลับไปที่กระดาษต้นฉบับของ Pedersen เขาแนะนำให้ผู้ตรวจสอบเลือก $H$ (และด้วยเหตุนี้อาจทำการเลือกนั้นโดยเลือกค่าสุ่ม $h$ และคอมพิวเตอร์ $H = G^h$และการให้ $H$ (แต่ ไม่ $h$) ถึงผู้พิสูจน์); ด้วยวิธีนี้ ผู้ตรวจสอบจะมั่นใจได้ว่าผู้พิสูจน์ไม่ทราบบันทึกแยก

อย่างไรก็ตาม ทุกวันนี้เราสร้าง $G$ และ $H$ อย่างอิสระ (ไม่มีใครรู้ความสัมพันธ์อย่างแท้จริง) - วิธีการนี้ขยายไปถึงหลาย ๆ คนอย่างเห็นได้ชัด $G$ ค่า