論文の概要: Elections in the Post-Quantum Era: Is the Complexity Shield Strong
Enough?
- arxiv url: http://arxiv.org/abs/2403.05273v1
- Date: Fri, 8 Mar 2024 12:52:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-11 20:00:27.014680
- Title: Elections in the Post-Quantum Era: Is the Complexity Shield Strong
Enough?
- Title(参考訳): 量子時代後の選挙:複雑性は十分に強固か?
- Authors: \v{S}imon Schierreich
- Abstract要約: 量子コンピュータは、上述した複雑性シールドに対する新たな脅威だと考えている。
本稿では,選挙に対する攻撃の可能性について概説し,量子コンピューティングの能力について論じるとともに,今後の研究の方向性を図示する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The election, a cornerstone of democracy, is one of the best-recognizable
symbols of democratic governance. Voters' confidence in elections is essential,
and these days, we can watch practically in live broadcast what consequences
distrust in the fairness of elections may have. From the times of the
celebrated Gibbard-Satterthwaite theorem, it is well-known in the social-choice
community that most voting systems are vulnerable to the efforts of various
players to influence elections. Luckily for us, computing such influence to
affect election outcomes is a hard problem from the computational complexity
perspective. This intractability is regarded as a ``complexity shield'' that
secures voting rules against this malicious behavior.
In this work, we consider quantum computers to be a new threat to the
complexity shield described above, as they break out of standard computing
paradigms and unlock additional computational resources. To this end, we
provide an overview of possible attacks on election, discuss the abilities of
quantum computing, and chart possible directions for future research in this
area.
- Abstract(参考訳): この選挙は民主主義の基盤であり、民主統治の最も認知度の高いシンボルの1つである。
選挙に対する有権者の信頼は不可欠であり、近年では選挙の公正性に対する不信感が生放送で実際に見られるようになっている。
有名なギバード・サッタースウェイトの定理から、社会選択社会では、ほとんどの投票システムは選挙に影響を与える様々なプレイヤーの努力に弱いことが知られている。
幸いにも、選挙結果に影響を与えるような影響を計算することは、計算複雑性の観点からは難しい問題です。
この難易度は、この悪意ある行動に対する投票ルールを確保する「複合性シールド」と見なされる。
本研究では,量子コンピュータが標準的な計算パラダイムから脱却し,新たな計算資源を解き放つことにより,上記の複雑性シールドに対する新たな脅威となると考えている。
この目的のために、選挙攻撃の可能性の概要、量子コンピューティングの能力について議論し、この分野における今後の研究の方向性を示す。
関連論文リスト
- Learning to Manipulate under Limited Information [49.1574468325115]
私たちは、26のサイズの約4万のニューラルネットワークをトレーニングし、8つの異なる投票方法に対処しました。
ボルダなど一部の投票手法は限られた情報を持つネットワークで高度に操作可能であるのに対して、Instant Runoffのような投票手法はそうではない。
論文 参考訳(メタデータ) (2024-01-29T18:49:50Z) - Adaptively Weighted Audits of Instant-Runoff Voting Elections: AWAIRE [61.872917066847855]
即時投票(IRV)選挙の監査方法は、リスク制限や、各投票における投票の電子的記録であるキャスト投票記録(CVR)を必要とするものではない。
我々は,CVRが利用できない場合に,適応的に重み付けされたテストスーパーマーチンガルを用いてITV選挙を効率よく監査するRLA手法を開発した。
論文 参考訳(メタデータ) (2023-07-20T15:55:34Z) - Accelerating Voting by Quantum Computation [35.03314687289671]
本稿では,任意の匿名投票規則に適用可能な量子加速投票アルゴリズムを提案する。
我々のアルゴリズムは、$Thetaleft(fracntextMOVright)$ timeで高い確率で正しい勝者を出力する。
論文 参考訳(メタデータ) (2023-01-08T07:29:38Z) - Measuring a Priori Voting Power -- Taking Delegations Seriously [8.12790806321461]
本稿では,自由民主主義選挙における有権者の事前投票力を測定するための新たな権力指標を紹介し,その基盤となるネットワークが代表を制限している。
投票者の臨界度を計算することは、投票の重みがインスタンスサイズでアスリーバウンドである場合でも、#Pハードであることが示される。
我々は、これらの理論的性質を強調し、投票権の制限が有権者の投票力をどのように変えるかを示す数値的な結果を提供する。
論文 参考訳(メタデータ) (2023-01-06T11:16:57Z) - Anonymous voting scheme using quantum assisted blockchain [0.39146761527401425]
本稿では,量子支援ブロックチェーンに基づく匿名投票方式を提案する。
投票方式は監査可能であり、現在利用可能な技術を使って実装することができる。
論文 参考訳(メタデータ) (2022-06-07T11:07:28Z) - Expected Frequency Matrices of Elections: Computation, Geometry, and
Preference Learning [58.23459346724491]
我々は、Szufa et al.(AAMAS 2020)の「選挙マップ」アプローチを用いて、よく知られた投票分布を分析します。
分布の「スケルトン写像」を描き、その頑健さを評価し、その性質を分析する。
論文 参考訳(メタデータ) (2022-05-16T17:40:22Z) - Obvious Manipulability of Voting Rules [105.35249497503527]
Gibbard-Satterthwaite の定理は、全会一致で非独裁的な投票規則は、戦略的なものではないと述べる。
我々は投票規則を再検討し、明らかでない操作性という戦略的安全性の弱い概念を考察する。
論文 参考訳(メタデータ) (2021-11-03T02:41:48Z) - An algorithm for a fairer and better voting system [0.0]
本稿は、投票者を代表する最適な候補を見つけることの課題を解決することを目的とした、新しい、より優れた投票システムについて述べる。
私たちは、人工知能に基づいた選挙の現実的なシミュレーションを行うためのソースコードをGitHubに公開しています。
我々は、我々のアルゴリズムがInstant-Runoff Voting、Preferential Block Voting、Single Transferable Vote、First Past The Postよりも優れているという確証を持っている。
論文 参考訳(メタデータ) (2021-10-13T22:34:49Z) - Bribery as a Measure of Candidate Success: Complexity Results for
Approval-Based Multiwinner Rules [58.8640284079665]
有権者が承認投票(すなわち、承認した候補者の集合)を投じた場合のマルチウィナー選挙における贈収賄の問題を研究する。
我々は、いくつかの承認ベースのマルチウィナールール(AV、SAV、GAV、RAV、承認ベースのチェンバリン--Courant、およびPAV)を検討します。
一般に、我々の問題は、勝利した委員会の候補者の承認数を増やすための贈収賄行為を制限した場合、より容易になる傾向がある。
論文 参考訳(メタデータ) (2021-04-19T08:26:40Z) - Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's
Post-Quantum Security [67.06003361150228]
作業の証明(英: proof of work、PoW)は、当事者が計算タスクの解決にいくらかの労力を費やしたことを他人に納得させることができる重要な暗号構造である。
本研究では、量子戦略に対してそのようなPoWの連鎖を見つけることの難しさについて検討する。
我々は、PoWs問題の連鎖が、マルチソリューションBernoulliサーチと呼ばれる問題に還元されることを証明し、量子クエリの複雑さを確立する。
論文 参考訳(メタデータ) (2020-12-30T18:03:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。