Amortizing Rate-1 OT and Applications to PIR and PSI
Amortizing Rate-1 OT and Applications to PIR and PSI
复制标题
摊销率 1 OT 以及 PIR 和 PSI 的应用
DOI：
10.1007/978-3-030-90456-2_5
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Miao, P.
中科院分区：
文献类型：
--
作者：
Chase, M.;Garg, S.;Hajiabadi, M.;Li, J.;Miao, P.
最近新构建的速率-1 OT [Döttling，Garg，Ishai，Malavolta，Mour和Ostrovsky，NIPPTO 2019]已经将这种原语置于聚光灯下，这些技术已经为私人信息检索和分支程序的同态加密带来了新的可行性结果。该构造的接收器通信由针对速率-1OT的单个实例的二次（在发送器的输入大小中）数量的组元素组成。最近[Garg，Hajiabadi，Ostrovsky，TCC 2020]将接收器通信改进为单个字符串OT的线性数量的组元素。然而，速率-1 OT的大多数应用程序需要执行多次，导致接收器的通信成本很大。在这项工作中，我们引入了一种新的技术，用于摊销多个速率-1 OT的成本。具体来说，基于标准的配对假设，我们得到了一个两个消息率-1 OT协议，每串OT的摊销成本渐近减少到只有四个组元素。我们的研究结果导致显着的通信改进PSI和PIR，SFE的分支程序的特殊情况。1.PIR：我们得到了一个速率为1的PIR方案与客户端通信成本组元素的安全参数和数据库大小N。值得注意的是，在一次设置（或一个PIR实例）后，任何随后的PIR实例只需要通信costnumber的组元素。2. PSI与不平衡的输入：我们将我们的技术应用于私有集合交集与不平衡的集合大小（其中接收者有一个较小的集合），并实现接收者组元素的通信，其中m，N分别是接收者和发送者集合的大小。类似地，在一次建立（或一个PSI实例）之后，任何随后的PSI实例仅需要组元素的通信costnumber。所有先前的用于上述不平衡设置的基于子线性通信非FHE的PSI协议也是基于速率-1OT，但是至少招致组元素。
Recent new constructions of rate-1 OT [Döttling, Garg, Ishai, Malavolta, Mour, and Ostrovsky, CRYPTO 2019] have brought this primitive under the spotlight and the techniques have led to new feasibility results for private-information retrieval, and homomorphic encryption for branching programs. The receiver communication of this construction consists of a quadratic (in the sender’s input size) number of group elements for a single instance of rate-1 OT. Recently [Garg, Hajiabadi, Ostrovsky, TCC 2020] improved the receiver communication to a linear number of group elements for a single string-OT. However, most applications of rate-1 OT require executing it multiple times, resulting in large communication costs for the receiver.In this work, we introduce a new technique for amortizing the cost of multiple rate-1 OTs. Specifically, based on standard pairing assumptions, we obtain a two-message rate-1 OT protocol for which the amortized cost per string-OT is asymptotically reduced to only four group elements. Our results lead to significant communication improvements in PSI and PIR, special cases of SFE for branching programs.1.PIR: We obtain a rate-1 PIR scheme with client communication cost ofgroup elements for security parameterand database sizeN. Notably, after a one-time setup (or one PIR instance), any following PIR instance only requires communication costnumber of group elements.2.PSI with unbalanced inputs: We apply our techniques to private set intersection with unbalanced set sizes (where the receiver has a smaller set) and achieve receiver communication ofgroup elements wherem,Nare the sizes of the receiver and sender sets, respectively. Similarly, after a one-time setup (or one PSI instance), any following PSI instance only requires communication costnumber of group elements. All previous sublinear-communication non-FHE based PSI protocols for the above unbalanced setting were also based on rate-1 OT, but incurred at leastgroup elements.
登录
查看更多内容
DOI：
10.1007/978-3-030-64375-1_3
发表时间：
2020
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Zvika Brakerski;P. Branco;Nico Döttling;Sanjam Garg;Giulio Malavolta
通讯作者：
Giulio Malavolta
可重复使用的指定验证者 NIZK 的新结构
DOI：
10.1007/978-3-030-26954-8_22
发表时间：
2019
期刊：
Graduate Studies in Mathematics
影响因子：
--
作者：
Alex Lombardi;Willy Quach;Ron D. Rothblum;Daniel Wichs;David J. Wu
通讯作者：
David J. Wu
DOI：
10.1007/978-3-662-53018-4_19
发表时间：
2016-08
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Elette Boyle;N. Gilboa;Yuval Ishai
通讯作者：
Elette Boyle;N. Gilboa;Yuval Ishai
DOI：
10.1007/978-3-030-17659-4_2
发表时间：
2019
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Sanjam Garg;Romain Gay;Mohammad Hajiabadi
通讯作者：
Mohammad Hajiabadi
提示 PRG、带加密的 OWF 等的新构造
DOI：
10.1007/978-3-030-56784-2_18
发表时间：
2020
期刊：
CRYPTO
影响因子：
--
作者：
Goyal, Risha;Vusirikala, Satyanarayana;Waters, Brent
通讯作者：
Waters, Brent