論文の概要: On Separation Logic, Computational Independence, and Pseudorandomness (Extended Version)
- arxiv url: http://arxiv.org/abs/2405.11987v1
- Date: Mon, 20 May 2024 12:39:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-21 13:14:56.740715
- Title: On Separation Logic, Computational Independence, and Pseudorandomness (Extended Version)
- Title（参考訳）: 分離論理、計算独立性、擬似性について(拡張版)
- Authors: Ugo Dal Lago, Davide Davoli, Bruce M. Kapron,
- Abstract要約: 本研究は,暗号シナリオにおける計算独立性について考察する。
分離論理のセマンティクスは,複雑性に縛られた敵を考慮に入れれば適用可能であることを示す。
注目すべきは、これは独立性と疑似ランダム性の間の実りある相互作用を可能にすることだ。
- 参考スコア（独自算出の注目度）: 1.024113475677323
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Separation logic is a substructural logic which has proved to have numerous and fruitful applications to the verification of programs working on dynamic data structures. Recently, Barthe, Hsu and Liao have proposed a new way of giving semantics to separation logic formulas in which separating conjunction is interpreted in terms of probabilistic independence. The latter is taken in its exact form, i.e., two events are independent if and only if the joint probability is the product of the probabilities of the two events. There is indeed a literature on weaker notions of independence which are computational in nature, i.e. independence holds only against efficient adversaries and modulo a negligible probability of success. The aim of this work is to explore the nature of computational independence in a cryptographic scenario, in view of the aforementioned advances in separation logic. We show on the one hand that the semantics of separation logic can be adapted so as to account for complexity bounded adversaries, and on the other hand that the obtained logical system is useful for writing simple and compact proofs of standard cryptographic results in which the adversary remains hidden. Remarkably, this allows for a fruitful interplay between independence and pseudorandomness, itself a crucial notion in cryptography.
- Abstract（参考訳）: 分離論理は、動的データ構造を扱うプログラムの検証に、多数の実りある応用があることが証明された構造論理である。
近年、Barthe, Hsu と Liao は分離論理式に意味論を与える新しい方法を提案している。
2つの事象が独立であることと、合同確率が2つの事象の確率の積であることは同値である。
独立性の弱い概念に関する文献は、本質的には計算的であり、すなわち、独立性は効率的な敵に対してのみ成り立ち、成功の無視可能な確率を変調する。
本研究の目的は、上記の分離論理の進歩の観点から、暗号シナリオにおける計算独立の性質を探ることである。
一方,分離論理のセマンティクスは,複雑性境界を考慮に入れれば適用可能であること,一方,得られた論理系は,敵が隠されたままの標準暗号結果の単純かつコンパクトな証明を書くのに有用であることを示す。
注目すべきなのは、これは独立性と疑似ランダム性の間の実りある相互作用を可能にすることだ。
関連論文リスト
- On the Independencies Hidden in the Structure of a Probabilistic Logic
Program [0.0]
非巡回基底論理プログラムにおけるd-セパレーションの条件依存性を計算する。
本稿では,ある条件付き独立文がプログラム構造によって暗示されるか否かを判断する,正しいメタ解釈手法を提案する。
論文 参考訳（メタデータ） (2023-08-30T08:55:55Z) - Modeling Hierarchical Reasoning Chains by Linking Discourse Units and
Key Phrases for Reading Comprehension [80.99865844249106]
本稿では,論理的推論の基盤として,対話レベルと単語レベルの両方の文脈を扱う総合グラフネットワーク(HGN)を提案する。
具体的には、ノードレベルの関係とタイプレベルの関係は、推論過程におけるブリッジと解釈できるが、階層的な相互作用機構によってモデル化される。
論文 参考訳（メタデータ） (2023-06-21T07:34:27Z) - An elementary belief function logic [6.091096843566857]
可能性と必要性の尺度、信念と妥当性の関数と不正確な確率の双対性は、モーダル論理と共通の特徴を共有している。
本稿では,MEL上にLukasiewicz論理を追加することにより,より単純な信念関数論理を考案できることを示す。
論文 参考訳（メタデータ） (2023-03-23T10:39:18Z) - Logical Satisfiability of Counterfactuals for Faithful Explanations in
NLI [60.142926537264714]
本稿では, 忠実度スルー・カウンタファクトの方法論について紹介する。
これは、説明に表される論理述語に基づいて、反実仮説を生成する。
そして、そのモデルが表現された論理と反ファクトの予測が一致しているかどうかを評価する。
論文 参考訳（メタデータ） (2022-05-25T03:40:59Z) - Adaptive n-ary Activation Functions for Probabilistic Boolean Logic [2.294014185517203]
マッチングやアリティ向上の活性化関数を用いて,任意の論理を単一層で学習できることが示される。
我々は,非ゼロパラメータの数を信念関数の有効アリティに直接関連付ける基礎を用いて,信念表を表現する。
これにより、パラメータの間隔を誘導することで論理的複雑性を低減する最適化アプローチが開かれる。
論文 参考訳（メタデータ） (2022-03-16T22:47:53Z) - Logical Credal Networks [87.25387518070411]
本稿では,論理と確率を組み合わせた先行モデルの多くを一般化した表現的確率論的論理である論理的クレダルネットワークを紹介する。
本稿では,不確実性のあるマスターミンドゲームを解くこと,クレジットカード詐欺を検出することを含む,最大後部推論タスクの性能について検討する。
論文 参考訳（メタデータ） (2021-09-25T00:00:47Z) - Uncertain Linear Logic via Fibring of Probabilistic and Fuzzy Logic [0.0]
確率論理とファジィ論理は 2つの異なる仮定に対応します 証拠ベースが現在利用できない命題の組み合わせについて
この2つの式は、線形論理における乗法および加法的作用素集合の自然な基底を与える。
資源の論理としての線形論理の概念」は、証拠の保存の原理を通じてここで証明される。
論文 参考訳（メタデータ） (2020-09-28T00:19:42Z) - Tractable Inference in Credal Sentential Decision Diagrams [116.6516175350871]
確率感性決定図は、解離ゲートの入力が確率値によってアノテートされる論理回路である。
我々は、局所確率を質量関数のクレーダル集合に置き換えることができる確率の一般化である、クレーダル感性決定図を開発する。
まず,ノイズの多い7セグメント表示画像に基づく簡単なアプリケーションについて検討する。
論文 参考訳（メタデータ） (2020-08-19T16:04:34Z) - Foundations of Reasoning with Uncertainty via Real-valued Logics [70.43924776071616]
我々は、本質的にすべての実数値論理をカバーするためにパラメータ化できる、音と強完全公理化を与える。
文のクラスは非常に豊かであり、各クラスは実数値論理の式の集合に対して可能な実値の集合を記述する。
論文 参考訳（メタデータ） (2020-08-06T02:13:11Z) - Logical Neural Networks [51.46602187496816]
ニューラルネットワーク(学習)と記号論理(知識と推論)の両方の重要な特性をシームレスに提供する新しいフレームワークを提案する。
すべてのニューロンは、重み付けされた実数値論理における公式の構成要素としての意味を持ち、非常に解釈不能な非絡み合い表現をもたらす。
推論は事前に定義されたターゲット変数ではなく、オムニであり、論理的推論に対応する。
論文 参考訳（メタデータ） (2020-06-23T16:55:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。