XiaoMi-AI文件搜索系统
World File Search Systemfocs
Quantum sount-sound sound零知识
我们研究量子零知识（经典）方案，这些方案反对量子重置攻击。我们的模型的灵感来自重置掠夺的经典模型（Barak-Goldreich-Goldwasser-Lindell，focs '01），提供了一个恶意的效率供您使用，并访问了对验证者的下一密码函数，并将其固定在某些初始随机磁带上；从而使其有效地重置（或等效地倒带）verifier。在我们的模型中，供者对verifier的功能具有量子访问，尤其可以在叠加中查询它。量子可重置的声音背后的动机是双重的：首先，确保在可能可以重置量子的情况下（例如智能卡或虚拟机），确保具有强大的安全保证。第二，从经典环境中汲取直觉，我们希望提高对量子后零知识的基本问题的理解。
任何非局部游戏的量子优势
我们展示了一种将任何 k 个证明者非局部博弈编译成单证明者交互式博弈的通用方法，同时保持相同的（量子）完整性和（经典）健全性保证（安全参数中的加性因子最多可忽略不计）。我们的编译器使用任何满足辅助（量子）输入自然正确性的量子同态加密方案（Mahadev，FOCS 2018；Brakerski，CRYPTO 2018）。同态加密方案用作模拟空间分离效果的加密机制，并且需要对加密查询评估 k - 1 个证明者策略（选出 k 个）。结合从著名的 CHSH 博弈（Clauser、Horne、Shimonyi 和 Holt，Physical Review Letters 1969）开始的（纠缠）多证明者非局部博弈的丰富文献，我们的编译器为构建机制来经典地验证量子优势提供了一个广泛的框架。
使用小深度量子电路进行量子性测试
最近，Brakerski、Christiano、Mahadev、Vazirani 和 Vidick (FOCS 2018) 展示了如何基于带错学习 (LWE) 假设构建量子性测试：该测试可以由量子计算机有效解决，但在 LWE 假设下无法由经典多项式时间计算机解决。该测试已导致多种加密应用。具体而言，它已应用于从单个不受信任的量子设备产生可证明的随机性、对单个量子设备进行自我测试以及独立于设备的量子密钥分发。在本文中，我们表明，这种量子性测试以及基本上所有上述应用实际上都可以通过一类非常弱的量子电路来实现：恒定深度量子电路与对数深度经典计算相结合。这揭示了这种基本量子性测试的新颖复杂性理论特性，并为小深度量子电路优于经典计算提供了新的具体证据。
突破位置验证的经典不可能性——DROPS
Chandran 等人 (SIAM J. Comput. '14) 正式引入了位置验证的加密任务，他们还表明该任务无法通过经典协议实现。在这项工作中，我们开始研究具有经典验证器的位置验证协议。我们发现量子性证明（以及计算假设）对于此类位置验证协议是必要的。在另一个方向上，我们调整了 Brakerski 等人 (FOCS '18) 的量子性证明协议来实例化此类位置验证协议。结果，我们实现了经典可验证的位置验证，假设有错误学习的量子难度。在此过程中，我们为 1-of-2 谜题的自然非局部游戏开发了 1-of-2 非局部健全性的概念，该概念由 Radian 和 Sattath (AFT '19) 首次提出，可视为计算不可克隆性属性。我们表明，1-of-2 非局部健全性遵循标准 2-of-2 健全性（因此也遵循自适应硬核位属性），这可能具有独立的意义。
cv.pdf div>
Conference reviewing AAAI Conference on Artificial Intelligence 2021 Conference on Artificial Intelligence, Ethics, and Society (AIES) 2019 Conference on Economics and Computation (EC) 2020 Conference on Learning Theory (COLT) 2018 Conference on Neural Information Processing Systems (NeurIPS) 2017, 2018, 2019, 2020, 2021 European Symposium on Algorithms (ESA) 2020 Innovations in Theoretical Computer Science (ITCS) 2021，2022国际自动机，语言和节目（ICALP）2022国际人工智能与统计会议（AISTATS）2019年国际学习代表国际会议（ICLR）2022，2022，2024国际机器学习国际机器学习会议（ICML）2017，2019，2019，2019年，2019年，2018年国际智能国际会议（2020年），2018年国际会议（IMAI）2018年国际会议（I），2018年（I）离散算法研讨会（SODA）2018，2020，2021，2023关于计算机科学基础（FOCS）2019年分布式计算原理（PODC）2016 2016年计算理论的研讨会（STOC）2017，2021，2021，2021，2024 on Web and Internet经济学（葡萄酒）的
编译型异或游戏价值的计算 Tsirelson 定理
非局部博弈是理解纠缠和在具有多个空间分离的量子设备的环境中构建量子协议的基础工具。在这项工作中，我们继续了 Kalai 等人 (STOC '23) 发起的研究，该研究是在经典验证器和单个加密受限的量子设备之间进行的编译非局部博弈。我们的主要结果是，Kalai 等人提出的编译器对于任何双人 XOR 游戏都是可靠的。Tsirelson 的一个著名定理表明，对于 XOR 游戏，量子值由半定程序精确给出，我们通过证明 SDP 上界对于编译的游戏成立，直到编译产生的错误可以忽略不计，从而获得了我们的结果。这回答了 Natarajan 和 Zhang (FOCS '23) 提出的问题，他们展示了 CHSH 游戏特定情况的可靠性。利用我们的技术，我们获得了几个额外的结果，包括（1）并行重复 XOR 游戏的编译值的严格界限、（2）任何编译的 XOR 游戏的运算符自测试语句，以及（3）任何 XOR 游戏的“良好”平方和证书，从中可以看出运算符的刚性。
多百万富翁的问题：新算法方法和协议
我们研究了多方计算中的一个基本问题，我们称之为多百万富翁问题（MMP）。给定一组私人整数输入，问题是要识别等于该集合的最大（或最小值）的输入子集，而无需揭示输入的任何更多信息，超出了所需的输出所暗示的内容。这样的问题是百万富翁问题的自然扩展，这是安德鲁Yao的开创性工作中提出的第一个多方计算问题（FOCS 1982）。一个密切相关的问题是最大值的最大值。我们研究了这些基本问题，并描述了几种算法方法和原始解决方案。此外，我们比较了几个选定设置下的协议的性能。随着保留隐私计算的应用在工业系统中越来越普遍实施，MMP和MAXP成为隐私保护统计，机器学习，拍卖和其他域中的重要构件。我们在这里提出的协议的重要优势之一就是它们的简单性。由于他们解决了各种应用程序场景中必不可少的基础问题的基本问题，因此我们认为对这些问题的提出的措施以及它们之间的比较将为未来的未来研究人员和安全分布式计算的从业人员服务。
量子计算的简洁经典验证
我们为量子计算 (BQP) 构建了一个经典可验证的简洁交互式论证，其通信复杂度和验证器运行时间在 BQP 计算的运行时间内是多对数的（在安全参数中是多项式的）。我们的协议是安全的，假设不可区分混淆 (iO) 和带错学习 (LWE) 的后量子安全性。这是普通模型中量子计算的第一个简洁论证；先前的工作（Chia-Chung-Yamakawa，TCC '20）需要长公共参考字符串和非黑盒使用以随机预言机建模的哈希函数。在技术层面，我们重新审视了构建经典可验证量子计算的框架（Mahadev，FOCS '18）。我们为 Mahadev 的协议提供了一个独立的模块化安全性证明，我们认为这是独立的兴趣。我们的证明很容易推广到验证者的第一条消息（包含许多公钥）被压缩的场景。接下来，我们将压缩公钥的概念形式化；我们将对象视为受约束/可编程 PRF 的泛化，并基于不可区分性混淆对其进行实例化。最后，我们使用（足够可组合的）简洁的 NP 知识论证将上述协议编译成完全简洁的论证。使用我们的框架，我们实现了几个额外的结果，包括
Clément L. Canonne – 简历
- 信息理论中的超越 IID 11（德国图宾根大学），2023 年 7 月 31 日至 8 月 4 日 https://sites.google.com/view/beyondiid11/beyond-iid-11 - 信息理论与数据科学研讨会（新加坡），2023 年 1 月 16 日至 27 日 https://ims.nus.edu.sg/events/information-theory-and-data-science-workshop/ - FOCS'22 上的隐私保护机器学习 (PPML) 研讨会，2022 年 11 月 1 日 https://ppml-workshop.github.io/ - DICTA'22 上的指导演讲，2022 年 10 月 29 日 https://dictaconference.org/dicta2022/ - 学习理论联盟指导研讨会，ALT'22，2022 年 3 月 15 日 https://let-all.com/alt22.html - 2021 Croucher 信息理论暑期课程 (CSCIT)，2021 年 8 月 23 日至 28 日 http://cscit.ie.cuhk.edu.hk/ - 稳健性和隐私会议，2021 年 3 月 22 日至 23 日 https://lecueguillaume.github.io/2021/02/17/conf_robust_privacy/ - Simons 研究所高维概率、几何和计算计划，2020 年 8 月 19 日至 12 月 18 日 https://simons.berkeley.edu/programs/hd20 - 推理问题：算法和下限，2020 年 8 月 31 日至 9 月 4 日 https://www.uni-frankfurt.de/84973818/Inference_problems__algorithms_and_ lower_bounds - 2019 年信息理论与应用 (ITA) 研讨会，2019 年 2 月 10 日至 15 日https://ita.ucsd.edu/ws/19/ - 2019 年局部算法研讨会 (WOLA)，2019 年 7 月 20 日至 22 日 http://people.inf.ethz.ch/gmohsen/WOLA19/
将OWSG和量子资金与Qefid
在经典的加密术中，单向函数（OWF）被广泛认为是“最小假设”，但量子加密的情况就不太清楚。最近的作品提出了两个并发候选量子密码学中最小假设的候选者：单向状态发生器（OWSGS），假定具有有效的验证算法的硬搜索问题的存在，并且EFI对，并假定存在困难的区分问题。最近的两篇论文[Khurana和Tomer Stoc'24; Batra和Jain focs'24]表明OWSG表示EFI对，但反向方向保持开放。在这项工作中，我们提供了有力的证据，表明相反的方向不存在：我们表明存在量子统一的甲骨文，而efi对存在，但OWSG不存在。实际上，我们显示了一个稍强的陈述，该语句也适用于输出经典位（QEFID对）的EFI对。因此，我们通过Oracle，QEFID对和单向拼图与OWSG和其他几个MicroCrypt原始词分开，包括有效可验证的单向拼图和不可消除的状态生成器。特别是解决了[Chung，Goldin和Gray Crypto'24]中留下的问题。使用类似的技术，我们还建立了一个完全黑框的分离（比私钥量子货币方案和QEFID对之间的较弱的分离（比Oracle分离略弱）。我们工作的一种概念含义是，有效的验证算法的存在可能会导致量子密码学中质性更强的原始素。