New NP-Complete Problems Associated with Lattices(<Special Section>Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper, we introduce a new decision problem associated with lattices, named the Exact Length Vector Problem (ELVP), and prove the NP-completeness of ELVP in the l_∞ norm. Moreover, we define two variants of ELVP. The one is a binary variant of ELVP, named the Binary Exact Length Vector Problem (BELVP), and is shown to be NP-complete in any l_p norm (1≤p≤∞). The other is a nonnegative variant of ELVP, named the Nonnegative Exact Length Vector Problem (NELVP). NELVP is defined in the l_1 norm, and is also shown to be NP-complete.

• 一般社団法人電子情報通信学会の論文
• 2007-05-01

著者

• Hayashi Shunichi

  Chiba Univ. Chiba‐shi Jpn

• Hayashi Shunichi

  Graduate School Of Science And Technology Chiba University

• Tada Mitsuru

  Institute Of Media And Information Technology Chiba University

関連論文

• Provably Secure Multi-signature Scheme with Signers' Intentions
• Probabilistic Multi-Signature Schemes Using a One-Way Trapdoor Permutation(Discrete Mathematics and Its Applications)
• On the Security and the Efficiency of Multi-Signature Schemes Based on a Trapdoor One-Way Permutation(Discrete Mathematics and Its Applications)
• A Secure Multisignature Scheme with Signing Order Verifiability(Special Section on Cryptography and Information Security)
• A Digital Signature Scheme Based on NP-Complete Lattice Problems
• New NP-Complete Problems Associated with Lattices(Discrete Mathematics and Its Applications)

スポンサーリンク