論文の概要: Secret Sharing from Non-Extractable Randomness

• arxiv url: http://arxiv.org/abs/2610.20173v1
• Date: Wed, 14 Oct 2026 13:20:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.171258
• Title: Secret Sharing from Non-Extractable Randomness
• Title（参考訳）: 抽出不能なランダム性からの秘密共有
• Abstract要約: 我々は、0,1b+2$から0,1$までのすべての決定論的写像が、クラスのある情報源から少なくとも1/6$の統計距離にあることを示した。 これは、十分な秘密を共有することは、抽出可能なランダム性を必要としないことを意味する。
• 参考スコア（独自算出の注目度）: 6.785480149010636
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.
• Abstract（参考訳）: Bosley and Dodis (TCC 2007) は、鍵長の対数よりも長いメッセージの情報理論の暗号化に十分である不完全なランダム性ソースのクラスは、ほぼ均一なビットの決定論的抽出を認めなければならないことを示した。 Aggarwal、Chung、Obremski、Ribeiro (TCC 2022) は、漏洩回復性または非可逆性を備えたスキームに対して肯定的な回答を示した。 私たちはそれを否定的に答える。 すべての$b\ge2$に対して、$\{0,1\}^{b+2}$上の平坦なソースのクラスを構築し、そのクラス内の任意のソースを使用する$b$-bitの秘密を2つの$(b+1)$-bitの共有に共有する完全正かつ完全にプライベートな2つのスキームと共に、少なくとも$b$のミンエントロピーを、クラス内の任意のソースから$\{0,1\}^{b+2}$までのすべての決定論的写像が、クラス内のあるソースから少なくとも1/6$の距離にあることを示す。 これは、十分な秘密を共有することは、抽出可能なランダム性を必要としないことを意味する。 証明は短いパリティの議論である。 2-out-of-n$と$r$-out-of-r$の共有については、それぞれ$(b+1)$-bitの共有を持つ完全スキームを与えます。

関連論文リスト

• On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck [6.362676503567886]
  情報ボトルネック(IB)は、ターゲットの$Y$に関する情報を保持するソースの$X$の表現を求める。 古典的な議論は、少なくとも$|mathcalX|+1$の記号で表現を考えるのに十分であることを示している。 X$ がバイナリで$Y$ が有限であれば、$(X,Y)$ のすべての合同分布とすべてのレート制約に対して、IB最適値はバイナリ $U$ で達成される。
  論文  参考訳（メタデータ） (2026-10-05T16:23:00Z)
• Optimal entanglement-assisted source coding under a balanced-difference promise [0.0]
  絡み合いは、コーディングタスクに必要なコミュニケーションを減らすことができるが、その限界を理解するためには、達成可能な最小コストの確立が不可欠である。 我々は、Aliceが単語を受信し、Bobはその単語を含む無秩序な候補のペアを知っているゼロエラーソースコーディングタスクでこの問題に対処する。 我々は、$(q-1)ell$が偶数であるとき、そのタスクに正確に$n$メッセージが必要であることを証明している。
  論文  参考訳（メタデータ） (2026-09-14T15:43:27Z)
• An Optimal Agnostic PAC Algorithm [15.361702135159845]
  2進リスクに対して$L$と$L*=min_hin HL(h)$を書き、統計的に最適なリスク境界を達成する学習者を構築する。 これにより、PACが任意の固定された$L*$で普遍定数まで学習する際の無知なサンプル複雑性が解決される。
  論文  参考訳（メタデータ） (2026-08-06T17:57:25Z)
• Optimal Computational Secret Sharing [51.599517747577266]
  $(t, n)$-threshold secret sharingでは、秘密の$S$が$n$の参加者に分散される。 共有サイズが $tfrac|S|t + |K|t$ となる構成を示す。
  論文  参考訳（メタデータ） (2025-02-04T23:37:16Z)
• Low-degree Security of the Planted Random Subgraph Problem [12.329446579556606]
  植付されたランダムな部分グラフを最大$kleq n1 - Omega(1)$まで検出する際の低次硬さを証明した。 我々は,(1) ランダム関数のための通信最適化多元的PSMプロトコル,(2) 共有サイズが$(1 + epsilon)log n$ for any $epsilon > 0$ に対して,最大$r$の任意の最小限の連立関係を再構築し,最大$ell = o(epsilon log n)1/(r-1)$までの未定部分集合に対して秘密保持する,という予想を適用した。
  論文  参考訳（メタデータ） (2024-09-24T16:42:00Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。