首页 > 其他分享 >如何写好Simulation证明(三): 半诚实敌手模型下的OT

如何写好Simulation证明(三): 半诚实敌手模型下的OT

时间:2024-05-09 12:44:54浏览次数:27  
标签:敌手 Simulation beta alpha oplus OT sigma OWP view

4. Oblivious Transfer for Semi-Honest Adversaries

在本文中, 我们将给出一个证明: 基于enhanced OWP, 构造一个半诚实敌手模型下的OT. 首先我们先介绍enhanced OWP概念.

4.1 Enhanced OWP.

对这个特殊的OWP我们先不做过多的解释, 我们先关注参数. 一般正式的定义中, 一个OWP具有四个算法: \((I, S, F, F^{-1})\).

\(I\): 这个算法是在一族函数中选择了出一个函数, 用index \(\alpha\) 表示, 还有他的陷门 \(\tau\).
\(S\): 这个算法是选定函数的定义域, 在定义域中选择一个值 \(x\).
\(F\): 正向计算 \(f_\alpha(x)\).
\(F^{-1}:\) 反向计算 \(f^{-1}_\alpha(y, \tau)\). 拥有陷门 \(\tau\) 才能反向计算.

4.2 协议构造

  • Input: \(P_1\) 拥有 \(b_0, b_1 \in \{0,1\}\), \(P_2\) 拥有 \(\sigma \in \{0,1\}\). 这两个人都有 \((I, S, F, F^{-1})\), 这些参数定义了一个enhanced trapdoor permutation, 以及其 hardcore predicate \(B\).
    1. \(P_1\) runs \(I(1^n)\), 获得 \((\alpha, \tau)\), 前者指定了一个enhanced OWP, 后者是其陷门. 把 \((\alpha, \tau)\) 发送给 \(P_2\).
    1. \(P_2\) runs \(S(\alpha)\) twice. 第一个值记为 \(x_\sigma\), 第二个值记为 \(y_{1-\sigma}\). 计算 \(y_\sigma=f_\alpha(x_\sigma)\). 发送 \((y_0, y_1)\) 给 \(P_1\).
    1. \(P_1\) 使用陷门, 计算出 \(y_0, y_1\) 对应的 \(x_0, x_1\). 并计算对应的hardcore, 之后拿想发送的两个值做上异或, 即: \(\beta_0=B(\alpha,x_0)\oplus b_0, \beta_1=B(\alpha,x_1)\oplus b_1\). 把 \((\beta_0, \beta_1)\) 发送给 \(P_2\).
    1. \(P_2\) 显然能够自己算出 \(b_\sigma\).

4.3 安全性证明

这个协议的正确性是显然的, 我们需要证明其安全性. 我们用MPC的定义去证.

Thm: 假设 \((I, S, F, F^{-1})\) 构成一族 enhanced OWP, 以及hardcore predicate \(B\). 那么在半诚实敌手的安全性假设下, 上述协议能够安全地计算 functionality $f((b_0, b_1), σ) = (λ, b_σ) $.

Proof: 根据之前的定义, 我们需要构造两个模拟器 \(S_1, S_2\) 分别模拟 \(P_1, P_2\) 的view.

Step 1: Construct \(S_1\).

因为我们的目的是构造的 \(S_1\) 产生的 view 与真实的不可区分, 所以我们要先想需要考虑哪些参数. \(S_1\) 的输出是 \(P_1\) 的输入 \((b_0, b_1)\) 和输出(无). 模拟view时, 需要考虑 \(P_1\) 的输入, 随机带, 接收到的消息. 构造如下:

\(S_1(1^n, b_0, b_1):\)

  1. Chooses a uniformly distributed random tape \(r\) for \(P_1;\) (后面运行 \(I\) 需要)
  2. \((\alpha, \tau) \leftarrow I(1^n, r);\)
  3. Run \(S(\alpha)\) twice independently to get \(y_0, y_1;\)
  4. Output: \(((b_0, b_1), r; (y_0, y_1));\)

下面去证明协议产生的 view 和真实世界的 view 不可区分. 其实很简单, 我们看一下只需要证明 \((y_0, y_1)\) 和真实世界中的 \((f_\alpha(x_\sigma), y_{1-\sigma})\) 相等就行. 这是因为OWP的映射是一对一的, 是保持分布的. 详细证明如下:

当 \(\sigma=0\) 时, \(\{(F(\alpha,x_0),y_1)\}\overset{{c}}{\equiv}\{(y_0,y_1)\};\)
当 \(\sigma=1\) 时, \(\{(y_0, F(\alpha,x_1))\}\overset{{c}}{\equiv}\{(y_0,y_1)\};\)

所以最终: \(\{{S}_1(1^n,(b_0,b_1))\}\overset{c}\equiv\{\text{view}_1^\pi((b_0,b_1),\sigma)\}\).

Step 2: Construct \(S_2\).

同样, 我们需要关注: 输入: \((\sigma)\), 输出: \((b_\sigma)\), view: \((r; \alpha, \beta_0, \beta_1)\). 在构造这个simulator的时候, 我们发现有一个困难, 因为不知道 \(b_{1-\sigma}\). 所以没法构造 \(\beta_{1-\sigma}\). 但是事实上是, 就当成是 \(0\) 就行. 具体构造如下:

\(S_2(1^n, \sigma, b_\sigma):\)

  1. Chooses uniformly distributed random tapes \(r_1, r_2\) for \(P_2;\) (后面运行 \(I,S\) 需要, 两个是因为运行两次 \(S\), 不过这是小问题)
  2. \((\alpha, \tau) \leftarrow I(1^n, r);\)
  3. \(x_\sigma \leftarrow S(\alpha; r_\sigma);\)
    \(y_{1-\sigma} \leftarrow S(\alpha, r_{1-\sigma});\)
    利用陷门计算出 \(x_{1-\sigma}\);
  4. \(β_σ = B(α, x_σ) ⊕ b_σ;\)
    \(β_{1-σ} = B(α, x_{1-σ});\)
  5. Output: \((σ, r_0, r_1; α, (β_0, β_1));\)

首先我们分析真实世界与模拟世界的不同(上面是真实世界):

\[\begin{align*} \text{view}_2^\pi((b_0,b_1),\sigma) &= \left(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus b_{1-\sigma})\right); \\ {S}_2(1^n,\sigma,b_\sigma) &= \left(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma}))\right) \end{align*} \]

显然, 当 \(b_{1-\sigma}=0\) 时, \(\text{view}_2^\pi((b_0,b_1),\sigma) \equiv S_2(1^n,\sigma,b_\sigma)\).
所以我们需要考虑的是, 当 \(b_{1-\sigma}=1\) 时, 两个分布是不可区分的. 即:

\[\left(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma})\oplus 1 \right) \overset c \equiv \left(\sigma,r_0,r_1;\alpha,(B(\alpha,x_\sigma)\oplus b_\sigma,B(\alpha,x_{1-\sigma}))\right). \]

简化一下式子, (把 \(\alpha\) 去掉了).

\[\left(\sigma, r_0, r_1;(B(x_\sigma)\oplus b_\sigma,B(x_{1-\sigma})\oplus 1 \right) \overset c \equiv \left(\sigma,r_0,r_1;B(x_\sigma)\oplus b_\sigma,B(x_{1-\sigma}))\right). \]

假设存在nuPPT的敌手 \(D\), 能够以 \(1/p(n)\) 的概率区分上述分布, 即:

\[\begin{align}\Pr[D(\sigma,r_0,r_1; (B( x_\sigma)\oplus b_\sigma,B( x_{1-\sigma})))&=1]-\Pr[D(\sigma,r_0,r_1; (B( x_\sigma)\oplus b_\sigma,B( x_{1-\sigma})\oplus1))=1]\ge \frac{1}{p(n)}\end{align} \]

我们将构造一个nuPPT算法 \(A\), 能够猜出hardcore. (\(A\) 把 \(\sigma, b_\sigma\) 的信息hardware到电路里)

\(A(r)\)(这里是随机带的意思)

  1. \(r_{1-\sigma} \leftarrow r;\)
  2. 随机选择 \(r_\sigma, x_\sigma=S(r_\sigma), β_σ = B( x_σ)⊕b_σ;\)
  3. 随机选择 \(\beta_{1-\sigma} \in \{0, 1\};\)
  4. \(c \leftarrow D((σ, r_0, r_1; (β_σ, β_{1−σ})));\)
  5. If \(c=1\), output \(β_{1−σ};\) else output \(1-β_{1−σ};\)

这个道理是这样的. \((1)\) 式是说, \(D\) 收到最后一项为 \(B( x_{1-\sigma})\) 时, 输出 \(1\) 的概率比接收到最后一项为 \(B( x_{1-\sigma}) \oplus 1\) 的概率显著得大. 所以当 \(D\) 输出 \(1\) 的时候, 我们就有理由猜测, \(D\) 接受到的最后一项为 \(B( x_{1-\sigma})\). 即 \(A\) 猜对了. 因为 这恰好就是 \(A\) 要猜的东西, 如果我给 \(D\) 的参数对了, 那么你输出 \(1\) 的概率会显著的大, 如果我给错了, 你输出 \(0\) 的概率会显著的大.

通过一些简单的转化, 我们可以证明:

\[\Pr[A(r) = B(f^{-1}(S(r)))] \geq \frac{1}{2} + \frac{1}{2p(n)}. \]

这和hardcore的性质矛盾, 所以 \(S_2\) 的输出和真实世界是不可区分的, 这下我们完成了 \(S_1\), \(S_2\) 的构造和证明, 所以安全性就证完了.

Discussion. 很多人看完这个协议会有疑问, 这个协议也得亏在半诚实模型下, 两个人能够按照协议流程走. 不然的话, 稍微自由点的 \(P_2\) 都能够在第 2 步自己选择 \(x_0, x_1\), 然后计算对应的 \(y\). 这样 \(P_2\) 能得到 \(b_0, b_1\) 两个值. 所以我们能够看到, 半诚实的模型其实啥也没保护.

所以总结一下, 在半诚实敌手模型下, 由于敌手会按照协议走, 所以我们构造的 simulator 不需要 rewind. 接下来我们会讲怎么对付ZK中的恶意 (malicious) 的 Verifier.

标签:敌手,Simulation,beta,alpha,oplus,OT,sigma,OWP,view
From: https://www.cnblogs.com/yangm17/p/18181881

相关文章

  • 如何写好Simulation证明(一): 语义安全
    密码学中很多证明需要用到Simulation,尤其是ZK,MPC等等.对于初学者来说,涉及Simulation的证明往往不容易理解,更别说自己独立证明,所以有必要学习一下如何写这样的证明.文章主要参考YehudaLindell的讲义:Howtosimulateit.1.Introduction什么是Simulation?中文翻译......
  • springboot整合mybatis自动生成框架
    1、添加自动生成配置在根目录下创建:mybatis-generate.xml<?xmlversion="1.0"encoding="UTF-8"?><!DOCTYPEgeneratorConfigurationPUBLIC"-//mybatis.org//DTDMyBatisGeneratorConfiguration1.0//EN""http://mybat......
  • idea使用svn报错-Error:Can not get current revision for file
    idea中使用svn结果报错:Error:CannotgetcurrentrevisionforfileD:/IDEADire…,并且idea提示一下警告:解决方案:安装svn的时候要主要勾选上第二个选项,如下图所示:最后在idea中配置svn的安装路径下的svn.exe,File->settings->VersionControl–>Subversion......
  • springboot整合mybatis-plus手动配置
    1、添加依赖<dependency><groupId>com.alibaba</groupId><artifactId>druid</artifactId><version>1.1.6</version></dependency><dependency>......
  • 美团二面:SpringBoot读取配置优先级顺序是什么?
    引言SpringBoot作为一种轻量级的Java应用程序框架,以其开箱即用、快速搭建新项目的特性赢得了广大开发者的青睐。其核心理念之一就是简化配置过程,使开发者能够快速响应复杂多变的生产环境需求。为了实现这一点,SpringBoot支持丰富的外部化配置机制,允许应用程序根据不同的部署环境......
  • dotnet 9 WPF 支持 Style 的 Setter 填充内容时可忽略 Value 标签
    本文记录WPF在dotnet9的一项XAML编写语法改进点,此改进点用于解决编写Style的Setter进行给Value赋值时,不能将Value当成默认内容,需要多写Value标签的问题。通过此改进点可减少两行XAML代码在原先的WPF版本里面,对Style的Setter填充复杂的对象内容时,大概的......
  • 解决SpringBoot内置tomcat出现error:An incompatible version [1.2.16] of the Apache
    问题描述在运行SpringBoot时出现一个error2024-05-08T20:52:06.512+08:00ERROR20752---[springboot3-003-demo][main]o.a.catalina.core.AprLifecycleListener:Anincompatibleversion[1.2.16]oftheApacheTomcatNativelibraryisinstalled,wh......
  • 小组练习 :结合本小组项目写下能想到的所有 SWOT在学习通提交解答的同时,可以同步发布在
    小组练习:结合本小组项目写下能想到的所有SWOT在学习通提交解答的同时,可以同步发布在团队和个人博客上,作为学习心得体会,记录下来。我的答案:【第二组】答:SWOT分析是一种战略规划工具,用于评估一个项目或企业的优势(Strengths)、劣势(Weaknesses)、机会(Opportunities)和威胁(Threat......
  • 小组练习 :结合本小组项目写下能想到的所有 SWOT
    结合本小组项目写下能想到的所有SWOT答:SWOT分析是一种战略规划工具,用于评估一个项目或企业的优势(Strengths)、劣势(Weaknesses)、机会(Opportunities)和威胁(Threats)。以下是针对本小组校园跑腿项目的SWOT分析:优势(Strengths):创新性:校园跑腿项目可能提供了一种新颖的服务,满足了校......
  • swot分析
    产品SWOT分析优势(Strengths):独特的功能或设计。高品质或可靠性。强大的品牌认知度。成本效益高。良好的客户关系和售后服务。劣势(Weaknesses):功能有限,无法与竞争对手匹敌。定价高于市场平均水平。缺乏市场知名度。技术问题或故障率高。客户服务响应速度慢。机会(Opportu......