코드 라우팅: 위치 확인에 대한 새로운 공격

코드 라우팅: 위치 확인에 대한 새로운 공격

타임 스탬프 : 9 년 2023 월 11 일 오전 18:XNUMX
코드 라우팅: 위치 검증 PlatoBlockchain Data Intelligence에 대한 새로운 공격입니다. 수직 검색. 일체 포함.

조이 크리어 및 알렉스 메이

Stanford University

이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.

추상

위치 확인의 암호화 작업은 양자 정보의 제약 조건과 상대론적 인과성을 활용하여 시공간에서 한 당사자의 위치를 ​​확인하려고 시도합니다. $f$-라우팅으로 알려진 널리 사용되는 검증 체계에는 증명자가 부울 함수 $f$의 값을 기반으로 양자 시스템을 리디렉션하도록 요구하는 작업이 포함됩니다. $f$ 라우팅 계획에 대한 부정 행위 전략은 증명자가 사전 공유된 얽힘을 사용해야 하며, 계획의 보안은 증명자가 얼마나 많은 얽힘을 조작할 수 있는지에 대한 가정에 달려 있습니다. 여기서는 양자 시스템을 비밀 공유 체계로 인코딩하고 비밀 공유 체계의 권한 부여 구조를 활용하여 시스템을 적절하게 지시하는 새로운 부정 행위 전략을 제시합니다. 이 전략은 $O(SP_p(f))$ EPR 쌍을 사용하여 $f$ 라우팅 작업을 완료합니다. 여기서 $SP_p(f)$는 $mathbb{Z}_p$ 계산 $필드에 대한 스팬 프로그램의 최소 크기입니다. f$. 이는 로컬 전처리를 허용한 후 $f$가 복잡도 클래스 $text{Mod}_ptext{L}$에 있을 때마다 $f$ 라우팅 방식을 효율적으로 공격할 수 있음을 보여줍니다. 가장 초기의 구성은 엄격하게 $text{Mod}_ptext{L}$ 내부에 있는 것으로 여겨지는 클래스 L을 달성했습니다. 우리는 또한 표시 함수 $f_I$를 사용하는 양자 비밀 공유 방식의 크기가 $f_I$ 함수에 대한 $f$-라우팅의 상한 얽힘 비용임을 보여줍니다.

► BibTeX 데이터

► 참고 문헌

[1] Nishanth Chandran, Vipul Goyal, Ryan Moriarty 및 Rafail Ostrovsky. 위치 기반 암호화. 연례 국제 암호학 회의, 391-407페이지. 스프링거, 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, Timothy P Spiller. 양자 태깅: 양자 정보 및 상대론적 신호 제약을 통해 위치를 인증합니다. Physical Review A, 84 (1): 012326, 2011. https:/ / doi.org/ 10.1103/ PhysRevA.84.012326.
https : / /doi.org/10.1103/ PhysRevA.84.012326

[3] 애드리안 켄트. Minkowski 공간의 양자 작업. 고전 및 양자 중력, 29(22): 224013, 2012. 10.1088/​0264-9381/​29/​22/​224013.
https:/​/​doi.org/​10.1088/​0264-9381/​29/​22/​224013

[4] 윌리엄 K 우터스(William K Wootters)와 보이치에흐 H 주렉(Wojciech H Zurek). 단일 퀀텀은 복제할 수 없습니다. Nature, 299 (5886): 802–803, 1982. https://​/​doi.org/​10.1038/​299802a0.
https : / /dodo.org/ 10.1038 / 299802a0

[5] Adrian P Kent, William J Munro, Timothy P Spiller, Raymond G Beausoleil. 태깅 시스템, 11년 2006월 7,075,438일. 미국 특허 XNUMX.

[6] 로버트 A. 말라니. 양자 얽힘을 이용한 위치 의존 통신. 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 및 Christian Schaffner. 위치 기반 양자 암호: 불가능과 구성. 컴퓨팅에 관한 SIAM 저널, 43(1): 150–178, 2014. https:/ / doi.org/ 10.1137/ 130913687.
https : / /doi.org/ 10.1137 / 130913687

[8] Salman Beigi와 Robert König. 위치 기반 암호화에 대한 응용 프로그램으로 단순화된 즉각적인 비로컬 양자 계산. 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] 안드레아스 블럼, 마티아스 크리스탄들, 플로리안 스필먼. 다중 큐비트 공격으로부터 안전한 단일 큐비트 위치 확인 프로토콜입니다. 자연 물리학, 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 및 Florian Speelman. 정원 호스 모델. 이론적 컴퓨터 과학의 혁신에 관한 4차 회의 절차, 145–158페이지, 2013. https:/ / doi.org/ 10.1145/ 2422436.2422455.
https : / /doi.org/ 10.1145 / 2422436.2422455

[11] 하르트무트 클라우크(Hartmut Klauck)와 수파르타 포더(Supartha Podder). 정원 호스 모델의 새로운 경계. 소프트웨어 기술 및 이론 컴퓨터 과학 기초, 2014. 10.4230/​LIPIcs.FSTTCS.2014.481.
https://​/​doi.org/​10.4230/​LIPIcs.FSTTCS.2014.481

[12] 스리니바산 아루나찰람(Srinivasan Arunachalam)과 수파르타 포더(Supartha Podder). 통신 기념품: 기억이 없는 통신 복잡성. 제12회 이론 컴퓨터 과학 컨퍼런스(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] 알렉스 메이. 홀로그래피의 양자 작업. 고에너지 물리학 저널, 2019(10): 1–39, 2019. https:/ / doi.org/ 10.1007/ JHEP10(2019)233.
https : / /doi.org/ 10.1007 / JHEP10 (2019) 233

[14] 알렉스 메이, 제프 페닝턴, 조나단 소스. 홀로그램 산란에는 연결된 얽힘 쐐기가 필요합니다. 고에너지 물리학 저널, 2020 (8): 1–34, 2020. https:/ / doi.org/ 10.1007/ JHEP08(2020)132.
https : / /doi.org/ 10.1007 / JHEP08 (2020) 132

[15] 알렉스 메이. 비국소 계산 및 홀로그래피의 복잡성과 얽힘. Quantum, 6: 864, 2022년 2521월. ISSN 327-10.22331X. 2022/q-11-28-864-10.22331. URL https:/​/​doi.org/​2022/​q-11-28-864-XNUMX.
https:/​/​doi.org/​10.22331/​q-2022-11-28-864

[16] 아담 D 스미스. 일반 액세스 구조에 대한 양자 비밀 공유. arXiv 프리프린트 quant-ph/ 0001087, 2000. https:/ / doi.org/ 10.48550/ arXiv.quant-ph/ 0001087.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​0001087
arXiv : 퀀트 -PH / 0001087

[17] 후안 말다세나. 초등각 장 이론과 초중력의 N 한계. 국제 이론 물리학 저널, 38 (4): 1113–1133, 1999. https:/ / doi.org/ 10.1023/ A:1026654312961.
https : / /doi.org/ 10.1023 / A : 1026654312961

[18] 에드워드 위튼. 안티 시터 공간 및 홀로그램. 이론 및 수학 물리학의 발전, 2: 253–291, 1998. 10.4310/​ATMP.1998.v2.n2.a2.
https:/​/​doi.org/​10.4310/​ATMP.1998.v2.n2.a2

[19] 다니엘 고 테스 맨 양자 비밀 공유 이론. 물리적 검토 A, 61 (4) : 042311, 2000. https : / /doi.org/10.1103/PhysRevA.61.042311.
https : / /doi.org/10.1103/ PhysRevA.61.042311

[20] 벤저민 슈마허와 마이클 A. 닐슨. 양자 데이터 처리 및 오류 수정. 물리적 검토 A, 54(4): 2629, 1996. https:/​/​doi.org/​10.1103/​PhysRevA.54.2629.
https : / /doi.org/10.1103/ PhysRevA.54.2629

[21] 벤자민 슈마허와 마이클 D 웨스트모어랜드. 대략적인 양자 오류 수정. 양자 정보 처리, 1 (1): 5–12, 2002. https:/​/​doi.org/​10.1023/​A:1019653202562.
https : / /doi.org/ 10.1023 / A : 1019653202562

[22] 게르하르트 번트록, 카르스텐 담, 울리히 헤르트람프, 크리스토프 마이넬. logspace-mod 클래스의 구조와 중요성. 수학 시스템 이론, 25 (3): 223–237, 1992. https:/​/​doi.org/​10.1007/​BF01374526.
https : / /doi.org/ 10.1007 / BF01374526

[23] 마우리시오 카치머와 아비 위그더슨. 스팬 프로그램에서. [1993] 복잡성 이론 회의의 제102차 연간 구조 절차, 111–1993페이지. IEEE, 10.1109. 1993.336536/SCT.XNUMX.
https : / / doi.org/ 10.1109 / SCT.1993.336536

[24] 닐 D 존스, Y 에드먼드 리엔, 윌리엄 T 레이저. 비결정적 로그 공간에 대한 새로운 문제가 완료되었습니다. 수학 시스템 이론, 10 (1): 1–17, 1976. https:/​/​doi.org/​10.1007/​BF01683259.
https : / /doi.org/ 10.1007 / BF01683259

[25] 클라우스 라인하르트와 에릭 알렌더. 비결정론을 모호하지 않게 만듭니다. SIAM 컴퓨팅 저널, 29(4): 1118–1131, 2000. https:/​/​doi.org/​10.1137/​S0097539798339041.
https : / /doi.org/ 10.1137 / S0097539798339041

[26] 에릭 알렌더, 클라우스 라인하르트, 저우 시유. 균일 및 비균일 상한을 분리, 일치 및 계산합니다. 컴퓨터 및 시스템 과학 저널, 59 (2): 164–181, 1999. https:/​/​doi.org/​10.1006/​jcss.1999.1646.
https : / /doi.org/ 10.1006 / jcss.1999.1646

[27] 에얄 쿠실레비츠. 통신 복잡성. Advances in Computers, 44권, 331~360페이지. 엘스비어, 1997. https://​/​doi.org/​10.1016/​S0065-2458(08)60342-3.
https:/​/​doi.org/​10.1016/​S0065-2458(08)60342-3

[28] 노암 니산. 임계 게이트의 통신 복잡성. 조합론, Paul Erdos is Eighty, 1: 301–315, 1993.

[29] 로버트 로베레, 토니안 피타시, 벤자민 로스먼, 스티븐 A 쿡. 단조로운 범위 프로그램에 대한 지수 하한입니다. 2016년 IEEE 57차 컴퓨터 과학 기초(FOCS) 연례 심포지엄, 406~415페이지. IEEE, 2016/FOCS.10.1109.
https : / /doi.org/10.1109/FOCS.2016.51

[30] 플로리안 스필먼. 낮은 T 깊이 양자 회로의 즉각적인 비국소 계산. 양자 계산, 통신 및 암호화 이론에 관한 제11차 회의(TQC 2016), 라이프니츠 국제 정보학 회보(LIPIcs) 61권, 페이지 9:1~9:24, 독일 다그스툴, 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

인용

[1] Alex May, “비로컬 계산 및 홀로그래피의 복잡성과 얽힘”, 퀀텀 6, 864 (2022).

[2] Alex May, Jonathan Sorce, Beni Yoshida, "연결된 쐐기 정리 및 그 결과", 고에너지 물리학 저널 2022 11, 153 (2022).

[3] Kfir Dolev 및 Sam Cree, "비로컬 양자 계산을 위한 리소스로서의 홀로그래피", arXiv : 2210.13500, (2022).

[4] Kfir Dolev 및 Sam Cree, "작은 광원뿔을 사용한 양자 회로의 비국소 계산", arXiv : 2203.10106, (2022).

[5] Rene Allerstorfer, Harry Buhrman, Alex May, Florian Speelman 및 Philip Verduyn Lunel, “비로컬 양자 계산과 정보 이론 암호화 관련”, arXiv : 2306.16462, (2023).

[6] Llorenç Escolà-Farràs 및 Florian Speelman, "얽힌 공격자로부터 보호되는 단일 큐비트 손실 허용 양자 위치 검증 프로토콜", arXiv : 2212.03674, (2022).

위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2023-08-10 03:31:42). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.

On Crossref의 인용 서비스 인용 작품에 대한 데이터가 없습니다 (최종 시도 2023-08-10 03:31:41).

이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.

타임 스탬프 :

더보기 양자 저널