type
status
date
slug
summary
tags
category
icon
password
不经意传输（OT）是安全多方计算中最核心的技术之一，本文对OT中的几个基础概念进行简单介绍。
OT
定义
OT是一种密码学协议，由Rabin在1981年提出，是一种基础的多方安全计算协议。协议由发送方、接收方两方参与，发送方拥有一个“消息-索引”对。每次传输时接收方选择一个索引，并接收。接收方无法得知发送方的任何其他消息，发送方也不了解接收方选择的哪个消息。当n取2的时候，实际上是1-out-of-2 OT，即两方安全计算。
例子
假设某旅行社拥有N个景点的旅游资料，小美想去其中的A景点游玩，希望向旅行社购买相关资料。但是小美非常在意自己的隐私，不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件：
（1）小美不希望向旅行社泄露“我准备去A景点”这一信息；
（2）旅行社只希望出售小美出钱购买的那份资料，而不泄露小美未购买的N-1份资料；
看起来这种隐私条件似乎是无法满足的：旅行社只要把景点A的资料给到小美，就必然了解了“小美正在关注A景点”这一信息；除非旅行社把所有N份资料都给出，但是这又违背了旅行社的利益；
但是神奇的OT可以让交易在这种“不可能的条件”下达成。简而言之，在OT协议中，旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密，然后发送给小美；小美可以从密文中解密出A的资料，而无法解密出其他N-1份资料。
baseOT
定义
其实并未找到baseOT的标准定义，按照我的理解，这是完全参照标准OT定义来实现的一种最基础的OT协议，即通过最朴素的公钥加密来实现2选1或多选1。baseOT有很多种实现方式，例如基于RSA,基于DH,基于ECC等。
常见协议
baseOT的实现有很多，但大致思路都差不多，利用公钥加密和异或加密的性质。这里给出一些例子：
ROT
定义
ROT是random OT的缩写。一般是接收方输入一个选择索引，发送方无输入，协议为发送方提供两组伪随机字符组，把其中一组给接收方。因此，ROT几乎是没有通信量的，这也是为什么我们需要用ROT来实现标准OT，目的就是为了减小通信量。ROT的一个重要特点是S没有输入但有输出。
ROT—>OT
ROT增加一些通信过程即可实现标准OT。首先在初始化时，发送方S已经有，接收方R有，此时S输入一对比特，R输入，S发送，R可通过计算来得到所选的：
上述协议中，我们假设R在交互过程的输入是ROT初始化过程中使用的选择位b。当R在交互过程选择的输入不是b而是非b的时候。可以多一轮交互来实现选择：
COT
定义
全称为Correlated OT，Correlated表示相关性，该协议会产生两个相关的消息，把其中一个给接收方。具体来说，S输入一个相关性常数，协议随机生成随机字符串，然后给S返回，给R返回。如下图所示，
COT—>ROT
将ROT归约到COT，即用COT来实现ROT的过程非常简单，只需要S和R都做一个抗关联性的哈希，即可将输出的关联性去掉。同时，还可以将原本长度为l的字符串约简为长度为k的字符串，可以利用这个特性去构造更复杂的协议，同时极大减少通信量。
OT—>COT
这里其实是IKNP协议中抽象出来的一小部分，利用标准OT来实现COT的过程。
ROT—>COT
这里是从ROT转化到COT的过程，该思路用在了优化IKNP中。
总结
我认为引入ROT和COT本质上还是为了用更小的计算和通信量去构造复杂的标准OT协议，比如下一篇文章要将到的IKNP协议。
📎 参考文章
欢迎您一起交流~
- Author:ZimaBlue
- URL:https://www.zimablue.life/article/ot1
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!