Roteamento de código: um novo ataque à verificação de posição

Republicado por Platão

seguidores: 0

Roteamento de código: um novo ataque à verificação de posição PlatoBlockchain Data Intelligence. Pesquisa vertical. Ai.

Universidade de Stanford

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

A tarefa criptográfica de verificação de posição tenta verificar a localização de uma parte no espaço-tempo, explorando restrições à informação quântica e à causalidade relativística. Um esquema de verificação popular conhecido como roteamento $f$ envolve exigir que o provador redirecione um sistema quântico com base no valor de uma função booleana $f$. As estratégias de trapaça para o esquema de roteamento $f$ exigem que o provador use emaranhamento pré-compartilhado, e a segurança do esquema depende de suposições sobre quanto emaranhamento um provador pode manipular. Aqui, apresentamos uma nova estratégia de trapaça na qual o sistema quântico é codificado em um esquema de compartilhamento de segredos e a estrutura de autorização do esquema de compartilhamento de segredos é explorada para direcionar o sistema de maneira adequada. Esta estratégia completa a tarefa de roteamento $f$ usando pares $O(SP_p(f))$ EPR, onde $SP_p(f)$ é o tamanho mínimo de um programa span sobre o campo $mathbb{Z}_p$ computing $ f$. Isso mostra que podemos atacar eficientemente esquemas de roteamento $f$ sempre que $f$ estiver na classe de complexidade $text{Mod}_ptext{L}$, após permitir o pré-processamento local. A melhor construção anterior alcançou a classe L, que se acredita estar estritamente dentro de $text{Mod}_ptext{L}$. Também mostramos que o tamanho de um esquema quântico de compartilhamento de segredos com função indicadora $f_I$ limita o custo de emaranhamento do roteamento $f$ na função $f_I$.

► dados BibTeX

@artigo{Cree2023coderoutingnew, doi = {10.22331/q-2023-08-09-1079}, url = {https://doi.org/10.22331/q-2023-08-09-1079}, título = {Código- roteamento: um novo ataque à verificação de posição}, autor = {Cree, Joy e May, Alex}, diário = {{Quantum}}, issn = {2521-327X}, editor = {{Verein zur F{“{o} }rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, páginas = {1079}, mês = agosto, ano = {2023} }

► Referências

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty e Rafail Ostrovsky. Criptografia baseada em posição. Na Conferência Anual Internacional de Criptologia, páginas 391–407. Springer, 2009. https:////doi.org/10.1007/978-3-642-03356-8_23.
https://doi.org/10.1007/978-3-642-03356-8_23

[2] Adrian Kent, William J Munro e Timothy P Spiller. Marcação quântica: autenticação de localização por meio de informações quânticas e restrições de sinalização relativística. Physical Review A, 84 (1): 012326, 2011. https://doi.org/10.1103/PhysRevA.84.012326.
https: / / doi.org/ 10.1103 / PhysRevA.84.012326

[3] Adriano Kent. Tarefas quânticas no espaço Minkowski. Gravidade Clássica e Quântica, 29 (22): 224013, 2012. 10.1088/0264-9381/29/22/224013.
https://doi.org/10.1088/0264-9381/29/22/224013

[4] William K Wootters e Wojciech H Zurek. Um único quantum não pode ser clonado. Natureza, 299 (5886): 802–803, 1982. https:////doi.org/10.1038/299802a0.
https: / / doi.org/ 10.1038 / 299802a0

[5] Adrian P Kent, William J Munro, Timothy P Spiller e Raymond G Beausoleil. Sistemas de marcação, 11 de julho de 2006. Patente dos EUA 7,075,438.

[6] Robert A. Malaney. Comunicações dependentes de localização usando entrelaçamento quântico. Physical Review A, 81 (4): 042319, 2010. https://doi.org/10.1103/PhysRevA.81.042319.
https: / / doi.org/ 10.1103 / PhysRevA.81.042319

[7] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky e Christian Schaffner. Criptografia quântica baseada em posição: Impossibilidade e construções. SIAM Journal on Computing, 43 (1): 150–178, 2014. https://doi.org/10.1137/130913687.
https: / / doi.org/ 10.1137 / 130913687

[8] Salman Beigi e Robert König. Computação quântica não local instantânea simplificada com aplicações para criptografia baseada em posição. New Journal of Physics, 13 (9): 093036, 2011. 10.1088/1367-2630/13/9/093036.
https://doi.org/10.1088/1367-2630/13/9/093036

[9] Andreas Bluhm, Matthias Christandl e Florian Speelman. Um protocolo de verificação de posição de qubit único seguro contra ataques de vários qubits. Física da Natureza, páginas 1–4, 2022. https:////doi.org/10.1038/s41567-022-01577-0.
https://doi.org/10.1038/s41567-022-01577-0

[10] Harry Buhrman, Serge Fehr, Christian Schaffner e Florian Speelman. O modelo da mangueira de jardim. Em Proceedings of the 4th conference on Innovations in Theoretical Computer Science, páginas 145–158, 2013. https://doi.org/10.1145/2422436.2422455.
https: / / doi.org/ 10.1145 / 2422436.2422455

[11] Hartmut Klauck e Supartha Podder. Novos limites para o modelo de mangueira de jardim. Em Fundamentos de Tecnologia de Software e Ciência da Computação Teórica, 2014. 10.4230/LIPIcs.FSTTCS.2014.481.
https:///doi.org/10.4230/LIPIcs.FSTTCS.2014.481

[12] Srinivasan Arunachalam e Supartha Podder. Lembrança de comunicação: Complexidade de comunicação sem memória. Na 12ª Conferência de Inovações em Ciência da Computação Teórica (ITCS 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. 10.4230/LIPIcs.ITCS.2021.61.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2021.61

[13] Alex Maio. Tarefas quânticas em holografia. Journal of High Energy Physics, 2019 (10): 1–39, 2019. https://doi.org/10.1007/JHEP10(2019)233.
https: / / doi.org/ 10.1007 / JHEP10 (2019) 233

[14] Alex May, Geoff Penington e Jonathan Sorce. A dispersão holográfica requer uma cunha de emaranhamento conectada. Journal of High Energy Physics, 2020 (8): 1–34, 2020. https://doi.org/10.1007/JHEP08(2020)132.
https: / / doi.org/ 10.1007 / JHEP08 (2020) 132

[15] Alex Maio. Complexidade e emaranhamento em computação não local e holografia. Quantum, 6: 864, novembro de 2022. ISSN 2521-327X. 10.22331/q-2022-11-28-864. URL https:///doi.org/10.22331/q-2022-11-28-864.
https://doi.org/10.22331/q-2022-11-28-864

[16] Adam D Smith. Compartilhamento de segredos quânticos para estruturas de acesso geral. arXiv preprint quant-ph/0001087, 2000. https://doi.org/10.48550/arXiv.quant-ph/0001087.
https:///doi.org/10.48550/arXiv.quant-ph/0001087
arXiv: quant-ph / 0001087

[17] João Maldacena. O limite grande-N de teorias de campo superconformes e supergravidade. Jornal internacional de física teórica, 38 (4): 1113–1133, 1999. https://doi.org/10.1023/A:1026654312961.
https: / / doi.org/ 10.1023 / A: 1026654312961

[18] Eduardo Witten. Espaço anti-sitter e holografia. Avanços em Física Teórica e Matemática, 2: 253–291, 1998. 10.4310/ATMP.1998.v2.n2.a2.
https://doi.org/10.4310/ATMP.1998.v2.n2.a2

[19] Daniel Gotesman. Teoria do compartilhamento de segredos quânticos. Physical Review A, 61 (4): 042311, 2000. https://doi.org/10.1103/PhysRevA.61.042311.
https: / / doi.org/ 10.1103 / PhysRevA.61.042311

[20] Benjamin Schumacher e Michael A Nielsen. Processamento de dados quânticos e correção de erros. Physical Review A, 54 (4): 2629, 1996. https:////doi.org/10.1103/PhysRevA.54.2629.
https: / / doi.org/ 10.1103 / PhysRevA.54.2629

[21] Benjamin Schumacher e Michael D. Westmoreland. Correção aproximada de erros quânticos. Processamento de Informação Quântica, 1 (1): 5–12, 2002. https:////doi.org/10.1023/A:1019653202562.
https: / / doi.org/ 10.1023 / A: 1019653202562

[22] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf e Christoph Meinel. Estrutura e importância da classe logspace-mod. Teoria dos sistemas matemáticos, 25 (3): 223–237, 1992. https:///doi.org/10.1007/BF01374526.
https: / / doi.org/ 10.1007 / BF01374526

[23] Mauricio Karchmer e Avi Wigderson. Em programas de extensão. Em [1993] Proceedings of the Eight Annual Structure in Complexity Theory Conference, páginas 102–111. IEEE, 1993. 10.1109/SCT.1993.336536.
https: / / doi.org/ 10.1109 / SCT.1993.336536

[24] Neil D Jones, Y Edmund Lien e William T Laaser. Novos problemas concluídos para espaço de log não determinístico. Teoria dos sistemas matemáticos, 10 (1): 1–17, 1976. https:///doi.org/10.1007/BF01683259.
https: / / doi.org/ 10.1007 / BF01683259

[25] Klaus Reinhardt e Eric Allender. Tornando o não-determinismo inequívoco. SIAM Journal on Computing, 29 (4): 1118–1131, 2000. https:///doi.org/10.1137/S0097539798339041.
https: / / doi.org/ 10.1137 / S0097539798339041

[26] Eric Allender, Klaus Reinhardt e Shiyu Zhou. Isolamento, correspondência e contagem de limites superiores uniformes e não uniformes. Journal of Computer and System Sciences, 59 (2): 164–181, 1999. https:///doi.org/10.1006/jcss.1999.1646.
https: / / doi.org/ 10.1006 / jcss.1999.1646

[27] Eyal Kushilevitz. Complexidade da comunicação. Em Advances in Computers, volume 44, páginas 331–360. Elsevier, 1997. https:////doi.org/10.1016/S0065-2458(08)60342-3.
https://doi.org/10.1016/S0065-2458(08)60342-3

[28] Noam Nissan. A complexidade da comunicação das portas de limite. Combinatória, Paul Erdos tem oitenta anos, 1: 301–315, 1993.

[29] Robert Robere, Toniann Pitassi, Benjamin Rossman e Stephen A Cook. Limites inferiores exponenciais para programas de extensão monótona. Em 2016, 57º Simpósio Anual IEEE sobre Fundamentos da Ciência da Computação (FOCS), páginas 406–415. IEEE, 2016. 10.1109/FOCS.2016.51.
https: / / doi.org/ 10.1109 / FOCS.2016.51

[30] Florian Speelman. Computação instantânea não local de circuitos quânticos de baixa profundidade T. Na 11ª Conferência sobre a Teoria da Computação Quântica, Comunicação e Criptografia (TQC 2016), volume 61 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 9:1–9:24, Dagstuhl, Alemanha, 2016. Schloss Dagstuhl–Leibniz- Zentrum fuer Informatik. ISBN 978-3-95977-019-4. 10.4230/LIPIcs.TQC.2016.9.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2016.9

Citado por

[1] Alex May, “Complexidade e emaranhamento em computação não local e holografia”, Quântico 6, 864 (2022).

[2] Alex May, Jonathan Sorce e Beni Yoshida, “O teorema da cunha conectada e suas consequências”, Jornal de Física de Altas Energias 2022 11, 153 (2022).

[3] Kfir Dolev e Sam Cree, “Holografia como recurso para computação quântica não local”, arXiv: 2210.13500, (2022).

[4] Kfir Dolev e Sam Cree, “Computação não local de circuitos quânticos com pequenos cones de luz”, arXiv: 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman e Philip Verduyn Lunel, “Relacionando a computação quântica não local à criptografia teórica da informação”, arXiv: 2306.16462, (2023).

[6] Llorenç Escolà-Farràs e Florian Speelman, “Protocolo de verificação de posição quântica tolerante a perdas de qubit único seguro contra invasores emaranhados”, arXiv: 2212.03674, (2022).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-08-10 03:31:42). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2023-08-10 03:31:41).

Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.

Conteúdo com tecnologia de SEO e distribuição de relações públicas. Seja amplificado hoje.
PlatoData.Network Gerativa Vertical Ai. Capacite-se. Acesse aqui.
PlatoAiStream. Inteligência Web3. Conhecimento Amplificado. Acesse aqui.
PlatãoESG. Automotivo / EVs, Carbono Tecnologia Limpa, Energia, Ambiente, Solar, Gestão de resíduos. Acesse aqui.
BlockOffsets. Modernizando a Propriedade de Compensação Ambiental. Acesse aqui.
Fonte: https://quantum-journal.org/papers/q-2023-08-09-1079/

Carimbo de hora: 9 de agosto de 2023

Carimbo de hora: 21 de março de 2024

Republicado por Platão

Sumário

► dados BibTeX

► Referências

Citado por

TensorCircuit: um framework de software quântico para a era NISQ

O custo mínimo de comunicação para simular qubits emaranhados

Efeitos semi-inteiros vs. inteiros na sincronização quântica de sistemas de spin

Relações quantitativas entre diferentes contextos de medição

Acelerando Algoritmos Quânticos com Pré-computação

Solucionador Linear Quântico Variacional

Codificação e análise quântica em processo estocástico de tempo contínuo com aplicações financeiras

Uma cadeia de Markov de mistura rápida de qualquer sistema quântico de muitos corpos com lacunas

Um teorema de estrutura para modelos ontológicos não contextuais generalizados

Resoluções espectrais em álgebras de efeito

A catálise covariante requer correlações e bons referenciais quânticos degradam pouco

Sombras clássicas baseadas em medições localmente emaranhadas

Sobre Nós

Pesquisa vertical e IA

Plataforma

Fique Ligado

Conta