Application of mixed integer quadratic program to shortest vector problems

• Kimura Keiji

  Graduate School of Mathematics, Kyushu University

• Waki Hayato

  Institute of Mathematics for Industry, Kyushu University

• Yasuda Masaya

  Institute of Mathematics for Industry, Kyushu University

抄録

The security of lattice-based cryptography is mainly based on the fact that the shortest vector problem (SVP) is NP-hard. Our interest is to know how large-scale shortest vector problems can be solved by the state-of-the-art software for mixed-integer programs. For this, we provide a formulation for SVP via mixed integer quadratic program and show the numerical performance for TU Darmstadt's benchmark instances with the dimension up to 49.

収録刊行物

• JSIAM Letters

  JSIAM Letters 9 (0), 65-68, 2017

  一般社団法人 日本応用数理学会

キーワード

• shortest vector problem
• mixed integer quadratic program
• presolve

詳細情報

• CRID: 1390001205299681408
• NII論文ID: 130006077572
• DOI: 10.14495/jsiaml.9.65
• ISSN: 18830617
• ISSN: 18830609
• Web Site: https://www.jstage.jst.go.jp/article/jsiaml/9/0/9_65/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可