มีอัลกอริธึมลายเซ็นดิจิทัลที่ใช้แฮชใดบ้างที่มีขนาดลายเซ็นที่เล็กพอสมควร

ฉันคิดว่าถ้าคุณ จริงๆ ตัดแต่งสิ่งต่างๆ ลง [1] คุณสามารถทำให้ลายเซ็นมีขนาดต่ำกว่า 100 ไบต์ นี่คือวิธีที่ฉันปรับความต้องการของคุณ:

• ฉันต้องการความปลอดภัย 128 บิตหรือดีกว่า (แม้ว่าจะไม่ใช่ข้อกำหนดที่ยาก)

  เนื่องจากคุณบอกว่าไม่ใช่ข้อกำหนดที่เข้มงวด ฉันจึงรีเซ็ตเป็นความปลอดภัย 80 บิต (หากคุณทำเช่นนี้ด้วยความปลอดภัย 128 บิต คุณจะได้รับลายเซ็นประมาณ 200 ไบต์) ด้วยการกำหนดเป้าหมายการรักษาความปลอดภัย 80 บิต เราสามารถใช้แฮช 80 บิตได้ (เช่น SHA-256 ตัดเหลือ 80 บิต - เราสามารถลองใช้ฟังก์ชันแฮชที่เร็วกว่าด้วยระดับความปลอดภัยที่น้อยกว่า อย่างไรก็ตาม จะเพิ่มความเร็วให้กับสิ่งต่างๆ เพียงเล็กน้อยเท่านั้น เลยไม่คิดว่ามันจะซื้ออะไรเราได้มาก)

• ฉันจะลงนามบล็อกข้อมูลที่มีขนาด 128 ไบต์หรือเล็กกว่านั้น

  ไม่ใช่ปัญหา

• แบบร่างลายเซ็นไม่จำเป็นต้องใช้อย่างแพร่หลาย สร้างมาตรฐานโดยหน่วยงานที่มีอำนาจใดๆ หรือเข้ากันได้กับระบบอื่นๆ

  ไม่มีใครบ้าพอที่จะสร้างมาตรฐานแนวทางนี้

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

  การคำนวณคีย์สาธารณะคือเสายาวตรงนี้ ดังนั้นผมจะใช้เวลาไม่เกิน 2 นาที อย่างไรก็ตาม คุณไม่ได้บอกว่าฮาร์ดแวร์คืออะไร ดังนั้นฉันจะถือว่าฮาร์ดแวร์นั้นค่อนข้างก้าวร้าวพอสมควร นั่นคือ 8 คอร์ที่รวดเร็วพร้อมฮาร์ดแวร์ AVX512 (อันที่จริง เราสามารถก้าวร้าวมากขึ้นด้วยฮาร์ดแวร์เฉพาะ อย่างไรก็ตาม นั่นจะไม่อนุญาตให้เราย่อขนาด ลายเซ็นขนาดนั้น)

• สมมติว่าฉันต้องการออกลายเซ็นประมาณ 10~20 ลายเซ็นเท่านั้น จากนั้นทิ้งคีย์ส่วนตัวไปตลอดกาล

  ฉันจะถือว่าลายเซ็นสูงสุด 20 ลายเซ็น (สูงสุด 16 จะทำให้เราลดขนาดลายเซ็นลงได้อีก 10 ไบต์)

ตกลง นี่คือสิ่งที่เราทำ: เราเริ่มต้นด้วยการออกแบบ LMS/XMSS (ไม่ว่าจะแก้ไข LMS เพื่อให้ใช้ปัจจัย W ที่ใหญ่ขึ้น หรือลบบิตมาสก์ของ XMSS และเปลี่ยนตำแหน่งด้วยวิธีอื่น) แล้ว:

• เรามีเป้าหมายที่ 20 ลายเซ็น; นี่แสดงถึงความสูงของ Merkle ที่ 5 (ซึ่งเราจะสามารถตัดกลับเป็น 4 ได้หากเราถือว่าได้สูงสุด 16 ลายเซ็น)

• การวัดบนโปรเซสเซอร์ Xeon ของฉันแสดงให้เห็นว่าคอร์เดี่ยวสามารถคำนวณแฮช 6.6M ต่อวินาทีได้ด้วยคำสั่ง AVX2 หากเราใช้โปรเซสเซอร์ที่เร็วกว่าพร้อมคำแนะนำ AVX512 เราอาจได้รับแฮชสูงถึง 20M ต่อวินาที เรามี 8 คอร์ และเรามีเวลา 120 วินาทีในการคำนวณคีย์ ดังนั้นเราจึงมีเวลาคำนวณแฮชไม่มากเท่ากับ 2 หมื่นล้านแฮช

• ตอนนี้ เราต้องสร้างคีย์สาธารณะแบบใช้ครั้งเดียวที่มีลายเซ็น 20 อัน [2] (และอย่างอื่นค่อนข้างเล็กน้อยเมื่อเทียบกัน) ดังนั้น เรามีเวลาเกือบ 1 พันล้านแฮชต่อการเซ็นชื่อเพียงครั้งเดียว

• หากเราใช้ค่า Winternitz เป็น $W \ประมาณ 200,000,000$ซึ่งจะทำให้เราเข้ารหัสได้ประมาณ 27 บิต ตอนนี้ แฮชที่สัญญาณลายเซ็นครั้งเดียวคือ 80 บิต; ซึ่งหมายความว่าด้วยการเข้ารหัสผลรวมคงที่ เราควรสร้างตัวเลขฐาน 200,000,000 หลัก 4 หลัก (วิธีการป้อนค่าที่ลงนามใน SHAKE สร้าง 3 หลักฐาน 200,000,000 หลัก ดูว่ามีหลักที่สี่ที่ผลรวมเป็นเป้าหมายหรือไม่ ; ถ้าไม่ใช่ ให้ย้อนกลับมาสร้างตัวเลขเพิ่ม)

  • ที่จริงแล้ว เนื่องจากการคำนวณโซ่ของ winternitz แต่ละอันนั้นไม่สามารถขนานกันได้ เวลาที่ใช้ (ด้วยค่าประมาณของฮาร์ดแวร์ที่กำหนด) จริง ๆ แล้วจะเป็นประมาณ 2 นาที 40 วินาที ฉันรู้สึกว่ายังอยู่ในข้อกำหนด "[ไม่] มากกว่าหนึ่งหรือสองนาที" (และถ้าไม่ ให้ซื้อฮาร์ดแวร์ที่เร็วขึ้นเล็กน้อย...)

ดังนั้นลายเซ็นจะประกอบด้วย:

• ลายเซ็นเพียงครั้งเดียวของแฮช 4 แฮช ละ 10 ไบต์ = 40 ไบต์

• เส้นทางการตรวจสอบ; 5 แฮช ละ 10 ไบต์ = 50 ไบต์

• ตัวสุ่มแฮช (ซึ่งคุณต้องการเพื่อป้องกันการโจมตีแบบชนกันที่อาจเกิดขึ้นได้ นี่คือการสุ่มที่คุณผสมเข้าไปในข้อความเมื่อคุณแฮช) 40 บิต = 5 ไบต์

• ดัชนี (จริง ๆ แล้ว คุณสามารถวางสิ่งนี้ได้ และเพียงแค่ให้ผู้ตรวจสอบตรวจสอบดัชนีที่เป็นไปได้ทั้งหมด ฉันไม่คิดว่าการประหยัด 1 ไบต์นั้นคุ้มค่า) 1 ไบต์

ทั้งหมด: 96 ไบต์ (โดยมีความเป็นไปได้ที่ 86 ไบต์ หากคุณต้องการสร้างเพียง 16 ลายเซ็น)

[1]: คุณเคยดูภาพยนตร์เรื่อง "The Martian" (หรือให้ดีกว่านั้น อ่านหนังสือ - ดูรายละเอียดเพิ่มเติม) ถ้าใช่ สิ่งที่ฉันกำลังทำก็เหมือนกับที่มาร์ค วัตนีย์ทำกับ MAV...

[2]: สำหรับโหนด Merkle leaf ที่เราไม่เคยใช้ เราไม่ต้องคำนวณคีย์สาธารณะแบบใช้ครั้งเดียวเหล่านั้นจริง ๆ แต่เราสามารถใส่ค่าจำลองแทนได้ เราจะไม่สามารถเซ็นสัญญากับพวกเขาได้ - เราไม่เคยตั้งใจที่จะทำเช่นนั้น