我们提出了一种有效的公开性验证的完全同态加密方案,该方案能够通过密文评估任意布尔电路,还产生了正确的同质计算的简洁证明。我们的方案基于DUCAS和MICCIANCIO(EUROCRYPT'15)提出的FHEW,我们将Ginx同型累加器(Eurocrypt'16)结合起来,以改善自举效率。为了使证明效果生成证明,我们将广泛使用的Rank-1约束系统(R1C)推广到环设置并获得环R1C,并在FHEW中属于同型同态计算。特别是,我们开发了在环R1C中有效表达的技术,即“非算术”操作,例如用于FHEW结构中使用的小工具分解和模量切换。我们通过将RING R1CS实例转换为多项式的汇总检查协议,然后将其编译为简洁的非交互式证明,通过将基于晶格的基于晶格的多项式承诺纳入Cini,Malavolta,Malavolta,Nguyen,nguyen和Wee(Wee(Wee)(Wee(Crypto'24))。结合在一起,我们公开的可验证的FHE方案依赖于有关晶格问题的标准硬度,以便在时间O(| c | 2·Poly(λ))和大小O(log 2 | C | C |·Poly(λ))中产生简洁的电路C的简洁证明。此外,我们的计划还实现了Walter(EPRINT 2024/1207)的最近提议的IND-SA(在半活性攻击下没有可区分性),当可以验证同型计算时,该安全性准确地捕获了客户数据隐私。
●James Bartusek(UC Berkeley,US)●Mario Berta(rwth Aachen University,de)●Anne Broadbent(渥太华大学,CAN,CAN,CAN)●IVO PIETRO DEGIOVANNI(INRIM和EURAMET EMN-Q,IT) (加利福尼亚州蒙特利尔大学)●Tobias Gehring(丹麦技术大学,DK)●Christian Kurtsiefer(新加坡国立大学,SG)●Paul Kwiat(美国伊利诺伊州Urbana-Champaign,美国) (Jinan Quantum Technology,CN)●Giulio Malavolta(Max Planck安全与隐私研究所,DE)●Carl Miller(美国马里兰州NIST和美国大学)●Isaac Nape(Witwatersrand,SA)
这项工作完全打破了基于候选晶格的顺序工作证明(POSW)(POSW)的依次假设(以及其广泛的概括),该证明是由Lai和Malavolta在Crypto 2023上提出的。此外,它破坏了POSW的本质相同的变体,该变体与原始变体不同,仅在一个任意选择中与设计和安全性证明(在伪造的假设下)无关。这表明原始POSW可能具有的任何安全性都是脆弱的,并进一步激励基于基于晶格的假设来寻找建筑。具体而言,对于顺序性参数t和sis参数n,q,m = n log q,对顺序性假设的攻击找到了仅在仅在QuasipolyNomial Norm M log tt⌉(或norm o(√m)⌈logt⌉t⌉t⌉t⌉t⌉t⌉t⌉(差异)中,仅在GOOLANITHMIC -ogarithMic -ogarithmic〜o o n,q o n,q n,q(log)tt⌉中。这强烈伪造了这样的假设,即找到这种溶液需要在t中进行深度线性。(〜o n符号隐藏了在其下标出的变量中的多聚群因子。)另外,对于任何常数ε> 0,攻击在深度〜o o n,q(tε)中找到多项式标准m 1 /ε的解决方案。同样,对(稍微修改)POSW的攻击构建了一个有效的证据,以pologogarithmic〜o o n,q(log 2 t)深度构建,因此强烈伪造了这样做需要线性顺序工作的期望。