ให้นายกที่ปลอดภัย $พี$ และเครื่องกำเนิดไฟฟ้า $g$ ซึ่งสร้างค่าทั้งหมดจาก $1$ ถึง $P-1$ กับ
$$g^n \mod P$$
1.) ตอนนี้มีฟังก์ชั่น $f$ ซึ่งกำหนดค่าเฉพาะให้กับช่วงของสมาชิก
$$f(g^{i-a_i},...,g^{i+b_i}) = f(g^i) = v_{ia_ib_i}$$
2.) ให้ค่าเฉพาะดังกล่าว $v_{ia_ib_i}$ ชดเชยต่อไป $g^{q_i}$ และก่อนหน้านี้ $g^{-q'_i}$ สามารถคำนวณ/ประมาณได้ในเวลาค่อนข้างเร็ว (ชั่วโมง)
ตัวอย่าง:
ให้ค่าเฉพาะเหล่านั้นเป็นสมาชิกกลุ่มด้วย $g^k \equiv 0 \mod 10,000$.
การมอบหมาย (1.) จะเป็นค่าที่ใกล้เคียงที่สุด
ขณะนี้มีวิธีคำนวณค่าชดเชยที่เล็กที่สุดหรือไม่ $t$ เพื่อหาค่าเฉพาะถัดไป $g^r \equiv 0 \mod 1,000 $ กับ
$$g^k\cdot g^t = g^r$$
เหมือนกันสำหรับค่าเฉพาะก่อนหน้า (ทั้งที่มี $|t| \นาที$)
รายละเอียดเพิ่มเติม:
- จำนวนค่าที่ไม่ซ้ำกันจะน้อยกว่ามาก $พี$
- จะมีการสุ่มหมายเลขที่ไม่ซ้ำกันหนึ่งหมายเลขเสมอ คำนวณงานที่ได้รับมอบหมาย 1.) ไม่จำเป็นต้องเร็ว (ฉันเดาว่าหากมีวิธีแก้ไขบางอย่างก็ไม่สามารถแก้ไขได้อย่างรวดเร็วมิฉะนั้นการแก้ dlog จะง่าย)
- 2.) ไม่จำเป็นต้องเป็นการคำนวณที่แน่นอนการค้นหาบางประเภทระหว่างชุดค่าที่เป็นไปได้เล็กน้อยก็ใช้ได้เช่นกัน แต่จำเป็นต้องนำไปสู่ค่าเฉพาะถัดไป/ก่อนหน้าเสมอ
- ไม่จำเป็นต้องกำหนดสมาชิกกลุ่มทุกคนให้เป็นค่าเฉพาะดังกล่าว
- ความยาวของช่วงเวลา ($a+b+1$) ควรแตกต่างกัน (ในกรณีส่วนใหญ่) สำหรับค่าที่ไม่ซ้ำกัน
ดังนั้นทุกค่าที่สามารถสร้างขึ้นด้วย $g^{i-a_i}$ ถึง $g^{i+b_i}$
ได้รับมอบหมายให้ $f(ก^i)$.
เว้นแต่การกำหนดจะเปลี่ยนช่วงเวลา ($a,ข$) ก็เปลี่ยนไปทีละอย่างเช่นกัน ดังนั้นสำหรับ $g^{i+1}$:
$$a_{i+1} = a_i +1$$
$$b_{i+1} = b_i -1$$
($b = 0$ จะเป็นเส้นขอบของงาน)