Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A New Analysis of the Kipnis-Shamir Method Solving the MinRank Problem Analisis Baru Kaedah Kipnis-Shamir Menyelesaikan Masalah MinRank

Shuhei NAKAMURA, Yacheng WANG, Yasuhiko IKEMATSU

  • pandangan teks lengkap

    0

  • Petikan Ini

Ringkasan:

Masalah MinRank disiasat sebagai masalah yang berkaitan dengan serangan pangkat dalam kriptografi multivariate dan penyahkodan kod pangkat dalam teori pengekodan. Kaedah Kipnis-Shamir adalah salah satu kaedah untuk menyelesaikan masalah, dan baru-baru ini, kemajuan ketara telah dibuat dalam anggaran kerumitannya oleh Verbel et al. Memandangkan kaedah ini mengurangkan masalah kepada masalah MQ, yang meminta penyelesaian kepada sistem persamaan kuadratik, kerumitannya bergantung pada tahap penyelesaian sistem kuadratik yang disimpulkan daripada kaedah tersebut. Nilai teori yang diperkenalkan oleh Verbel et al. menghampiri tahap penyelesaian minimum sistem kuadratik dalam kaedah walaupun nilainya ditakrifkan di bawah had tertentu untuk sistem yang dipertimbangkan. Sistem kuadratik di luar hadnya selalunya mempunyai tahap penyelesaian yang lebih besar, tetapi kerumitan penyelesaian tidak selalu lebih tinggi kerana ia mempunyai bilangan pembolehubah dan persamaan yang lebih kecil. Oleh itu, untuk membincangkan kerumitan terbaik kaedah Kipnis-Shamir, nilai teori diperlukan untuk menganggarkan darjah penyelesaian setiap sistem kuadratik yang disimpulkan daripada kaedah tersebut. Sistem kuadratik yang disimpulkan daripada kaedah Kipnis-Shamir sentiasa mempunyai pelbagai darjah, dan kerumitan penyelesaian dipengaruhi oleh sifat ini. Dalam kajian ini, kami memperkenalkan nilai teori yang ditakrifkan oleh pelbagai darjah dan menunjukkan bahawa ia menghampiri darjah penyelesaian setiap sistem kuadratik. Oleh itu, sistem yang disimpulkan daripada kaedah dibandingkan, dan kerumitan terbaik dibincangkan. Sebagai aplikasi, untuk serangan MinRank menggunakan kaedah Kipnis-Shamir terhadap skim tandatangan multivariate Rainbow, kami menunjukkan kes di mana sistem kuadratik yang disimpulkan di luar had Verbel et al. adalah yang terbaik. Khususnya, anggaran kerumitan serangan MinRank menggunakan kaedah KS terhadap set parameter Rainbow I, III dan V dikurangkan sebanyak kira-kira 172, 140 dan 212 bit, masing-masing, daripada anggaran Verbel et al.

Jawatankuasa
IEICE TRANSACTIONS on Fundamentals Vol.E106-A No.3 pp.203-211
Tarikh penerbitan
2023/03/01
Diumumkan
2022/09/29
ISSN dalam talian
1745-1337
DOI
10.1587/transfun.2022CIP0014
Jenis Manuskrip
Special Section PAPER (Special Section on Cryptography and Information Security)
kategori

Pengarang

Shuhei NAKAMURA
  Nihon University
Yacheng WANG
  Corporate Research & Development Center Toshiba
Yasuhiko IKEMATSU
  Kyushu University

Kata kunci

Contents [show]