개인 정보 검색

암호학에서 PIR(Private Information Research) 프로토콜은 어떤 항목이 검색되는지 밝히지 않고 사용자가 데이터베이스를 보유한 서버에서 항목을 검색할 수 있도록 하는 프로토콜이다.PIR은 사용자가 다른 데이터베이스 항목에 대한 정보를 얻을 필요가 없는 1-of-n 망각 전송의 약한 버전이다.

PIR을 달성하는 매우 비효율적인 한 가지 방법은 서버가 데이터베이스의 전체 사본을 사용자에게 보내는 것이다.사실, 이것은 단일 서버 설정에서 사용자 정보 이론적 프라이버시를 제공하는 유일한 프로토콜이다(^[2]클래식 또는 양자 설정에서^[1].이 문제를 해결하는 방법에는 두 가지가 있다: 서버를 계산적으로 경계로 만들거나, 여러 개의 비협조 서버가 있다고 가정하고 각각 데이터베이스 복사본을 가지고 있다.

이 문제는 1995년 초르, 골드리히, 쿠실레비츠, 수단에^[2] 의해 정보이론적 환경에서 도입되었고 1997년 쿠실레비츠와 오스트로프스키가 컴퓨터 환경에서 도입하였다.^[3]그 이후로 매우 효율적인 해결책이 발견되었다. $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ 데이터베이스(컴퓨터적으로 비공개) PIR은 지속적인(수정) 통신으로 달성할 수 있으며, k-database(정보 이론) PIR은 $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ O $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ 로그 $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ k $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ k $){\$ n $^{O\log \log$ k $}{k\log$ k $}}}}}오른쪽)$ 통신으로 $n^{O\left({\frac {\log \log k}{k\log k}}\right)}$ 수행할 수 있다.

컴퓨팅 PIR의 발전

첫번째single-database 계산 부분 계획 n{n\displaystyle}보다 적은 통신 복잡도를 달성하기 위해 1997년 Kushilevitz, 오스트로프 스키. AleksandrNikolaevich.[3] 하며 n{n\displaystyle}은 어떤ϵ{\displaystyle \epsilon}, nϵ{\displaystyle n^{\epsilon}}, 통신의 복잡성 달성해 만들어졌다.뉴데이터베이스의 비트 mber.그들의 계획의 보안은 잘 연구된 이차적 잔류성 문제에 기초했다.1999년 크리스티안 카친, 실비오 미칼리, 마르쿠스 스타들러는^[4] 다층적 의사소통 복잡성을 달성했다.그들의 시스템의 보안은 피히딩 가정에 근거한다.2004년에 Helger Lipmaa는^[5] 로그-제곱 통신 $O(\ell \log n+k\log ^{2}n)$ O $O(\ell \log n+k\log ^{2}n)$ $O(\ell \log n+k\log ^{2}n)$ $O(\ell \log n+k\log ^{2}n)$ + $O(\ell \log n+k\log ^{2}n)$ $O(\ell \log n+k\log ^{2}n)$ 2 $O(\ell \log n+k\log ^{2}n)$ ) $O(\ell \log n+k\log ^{2}n)$ {\ $displaystyle$ O $(\ell \log n+k\log ^{2}n)$ 를 달성했는데 여기서 $O(\ell \log n+k\log ^{2}n)$ $where$ ${\displaysty \ell}$ 은 $\ell$ 문자열 길이, k ${\styledown k}$ 은 $k$ 보안 매개 변수다.그의 시스템의 보안은 Damgård-Jurik 암호 시스템과 같은 길이 유연성이 높은 동형 암호 시스템의 의미적 보안으로 감소한다.2005년에 Craig Gentry와 Zulfikar Ramzan은^[6] 데이터베이스의 로그 제곱 비트를 검색하는 로그 제곱 통신 복잡성을 달성했다.그들의 계획의 보안도 피히딩 가정의 변형에 기초하고 있다.2015년 아겔로스 키야스, 니코스 레오나르도스, 헬거 립마아, 카테리아나 파블리크, 치앙탕에 의해 드디어 $1$ $1$ 이 1 $1$ 로 낮아졌다.^[7]

이전의 모든 하위 통신 연산 PIR 프로토콜은 $\Omega (n)$ ( $\Omega (n)$ ) $\Oomega (n)$ 공개 키 $\Omega (n)$ 연산의 선형 계산 복잡성을 필요로 했다.2009년에 Helger Lipmaa는^[8] 통신 $O(\ell \log n+k\log ^{2}n)$ O ( $O(\ell \log n+k\log ^{2}n)$ $O(\ell \log n+k\log ^{2}n)$ + k $O(\ell \log n+k\log ^{2}n)$ $O(\ell \log n+k\log ^{2}n)$ $O(\ell \log n+k\log ^{2}n)$ ) ${\displaystyle O(\ell \log$ n $+k\log ^{2}n)}$ 와 최악의 $O(\ell \log n+k\log ^{2}n)$ 경우 $O(n/\log n)$ / $O(n/\log n)$ $O(n/\log n)$ ) ${\displaysty O(n/log n)$ 공개키 $O(n/\log n)$ 연산을 설계하였다.비연속 비트를 회수하는 상각 기술은 유발 이샤이, 에이알 쿠실레비츠, 라페일 오스트로프스키, 아밋 사하이 등이 검토했다.^[9]

오스트로프스키와 스키트가 보여주듯이 쿠실레비츠와 오스트로프스키와 립마아의 계획은 동형 암호화에 근거한 유사한 생각을 사용한다.^[10]쿠실레비츠와 오스트로프스키 프로토콜은 골드와세르-미칼리 암호체계, 립마아의 프로토콜은 담그그라드-쥬리크 암호체계에 기반을 두고 있다.

정보 정리 PIR의 발전

정보 이론적 보안을 달성하기 위해서는 여러 개의 비협조 서버가 있으며, 각각 데이터베이스 복사본을 가지고 있다는 가정이 필요하다.이러한 가정이 없다면, 어떤 정보 이론적으로 안전한 PIR 프로토콜은 최소한 데이터베이스 n의 크기인 통신량을 요구한다.다중 서버 PIR 프로토콜은 응답하지 않거나 악의적이거나 결탁하는 서버를 각각 강력하거나 비잔틴 강건하다고 한다.이 문제들은 베이멜과 스타울(2002)에 의해 처음 검토되었다.서버 중 k대만 응답하고, 서버 incorrectly은 잘못 응답하며, 클라이언트의 질의를 밝히지 않고 서버를 결탁할 때까지 견딜 수 있는 ℓ-서버 시스템을 「t-private ν-Byjantine의 강력한 k-out-of-f-piral PIR」[DGH 2012]라고 한다.2012년 C.데벳, I. 골드버그, 그리고 N. 헤닝거(DGH 2012)는 이론적 최대값인 $\nu <k-t-1$ $\nu <k-t-1$ < $\nu <k-t-1$ - $\nu <k-t-1$ - $\nu <k-t-1$ ${\displaystyle \nu <k-t-1$ }에 대해 비잔틴-로바스트인 최적으로 견고한 체계를 제안했다.샤미르의 '비밀 공유'를 이용해 질의를 숨기는 '골드버그'의 초기 의정서에 근거한 것이다.골드버그는 SourceForge에 대한 C++ 구현을 발표했다.^[11]

기타 암호화 원시 요소와의 관계

단방향 기능은 비경쟁적(즉, 비선형 통신 포함) 단일 데이터베이스를 계산적으로 개인 정보 검색에 필요하지만 충분하다고는 알려져 있지 않다.사실 그러한 의전은 조반니 디 크레스켄조, 탈 말킨, 라파일 오스트로프스키에 의해 망각적인 전출을 암시하는 것으로 증명되었다(아래 참조).^[12]

대칭 PIR이라고도 불리는 망각 전송은 사용자가 요청한 항목 이외의 어떤 항목도 배울 수 없다는 추가적인 제한이 있는 PIR이다.사용자와 데이터베이스 모두 개인 정보 보호 요건을 갖기 때문에 대칭이라고 불린다.

충돌 방지 암호해시함수는 이샤이, 쿠실레비츠, 오스트로프스키에서 알 수 있듯이 모든 단원 계산 PIR 체계에 의해 암시된다.^[13]

PIR 변주곡

Private Information Research의 기본 동기는 당사자(발신자) 중 한 사람(발신자)이 데이터베이스를 소유하고, 다른 부분(수신자)이 일정한 프라이버시 제한과 보증으로 질의하고자 하는 양 당사자 프로토콜의 가족이다.그러므로 프로토콜의 결과, 수신자가 데이터베이스의 i번째 값을 원한다면 i번째 항목을 배워야 하지만, 송신자는 i번째 항목에 대해 아무것도 배우지 않아야 한다.일반적인 PIR 프로토콜에서, 계산적으로 무제한 송신자는 i에 대해 아무것도 배울 수 없으므로 개인 정보 보호는 이론적으로 보존된다.PIR 문제가 제기된 이후, 그 해결책에 대한 다른 접근법이 추구되어 왔고 약간의 변형이 제안되었다.

CPR(Computerly Private Information Research) 프로토콜은 PIR 프로토콜과 유사하다: 수신자는 송신자의 데이터베이스에서 자신이 선택한 요소를 검색하여 송신자가 어떤 요소가 전송되었는지에 대한 지식을 얻지 못하게 한다.^[8]유일한 차이점은 프라이버시가 다항적으로 경계된 송신자에 대해 보호된다는 것이다.^[14]

CPR(Computerly Symmetric Private Information Research) 프로토콜은 CPR 프로토콜을 사용하는 유사한 시나리오에서 사용된다.송신자가 데이터베이스를 소유하고 있고, 수신자가 이 데이터베이스에서 i번째 값을 얻기를 원하는 경우, SPR 프로토콜 실행의 마지막에, 수신자는 i번째 값 외에 데이터베이스의 값에 대해 아무것도 배우지 않았어야 한다.^[14]

PIR 구현

문헌의 수많은 컴퓨터 PIR 및 정보 이론적 PIR 체계가 구현되었다.불완전한 목록은 다음과 같다.

MuchPIR은^[15] Postgres C/C++ Extension으로서의 CPR 구현[GitHub, 2021년].
SealPIR는^[16] 빠른 CPR 구현[ACLS 2018]이다.
팝콘은^[17] 미디어에 맞춘 PIR 구현이다[GCMSAW 2016].
Percy++^[11]는 [AG 2007, DGH 2012, CGKS 1998, 골드버그 2007, HOG 2011, LG 2015]의 구현을 포함한다.
RAID-PIR은^[18] [DHS 2014]의 ITPIR 계획의 구현이다.
XPIR은^[19] 빠른 CPR 구현[ABFK 2014]이다.
upPIR는^[20] ITPIR 구현[Cappos 2013]이다.

메모들

^ Baumeler, Ämin; Broadbent, Anne (17 April 2014). "Quantum Private Information Retrieval has Linear Communication Complexity". Journal of Cryptology. 28: 161–175. arXiv:1304.5490. doi:10.1007/s00145-014-9180-2. S2CID 1450526.
^ ^a ^b Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu (1 November 1998). "Private information retrieval" (PDF). Journal of the ACM. 45 (6): 965–981. CiteSeerX 10.1.1.51.3663. doi:10.1145/293347.293350. S2CID 544823.
^ ^a ^b ^c Kushilevitz, Eyal; Ostrovsky, Rafail (1997). "Replication is not needed: single database, computationally-private information retrieval". Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Miami Beach, Florida, USA: IEEE Computer Society. pp. 364–373. CiteSeerX 10.1.1.56.2667. doi:10.1109/SFCS.1997.646125. ISBN 978-0-8186-8197-4. S2CID 11000506.
^ Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). "Computationally Private Information Retrieval with Polylogarithmic Communication". Advances in Cryptology - EUROCRYPT '99. Prague, Czech Republic: Springer-Verlag. pp. 402–414. doi:10.1007/3-540-48910-X_28. ISBN 978-3-540-48910-8.
^ ^a ^b Lipmaa, Helger (2005). "An Oblivious Transfer Protocol with Log-Squared Communication". Proceedings of the 8th International Conference on Information Security (ISC 2005). Lecture Notes in Computer Science. Vol. 3650. Singapore: Springer-Verlag. pp. 314–328. CiteSeerX 10.1.1.73.8768. doi:10.1007/11556992_23. ISBN 978-3-540-31930-6.
^ Gentry, Craig; Ramzan, Zulfikar (2005). "Single-Database Private Information Retrieval with Constant Communication Rate". ICALP. LNCS. Vol. 3580. Springer. pp. 803–815. CiteSeerX 10.1.1.113.6572. doi:10.1007/11523468_65.
^ Kiayias, Aggelos; Leonardos, Nikos; Lipmaa, Helger; Pavlyk, Kateryna; Tang, Qiang (2015). "Optimal Rate Private Information Retrieval from Homomorphic Encryption". Proceedings on Privacy Enhancing Technologies 2015. Vol. 2015. DE GRUYTER. pp. 222–243. doi:10.1515/popets-2015-0016.
^ ^a ^b Lipmaa, Helger (2010). "First CPIR Protocol with Data-Dependent Computation". Proceedings of the 12th International Conference on Information Security and Cryptology. Lecture Notes in Computer Science. Vol. 5984. Seoul, Korea: Springer-Verlag. pp. 193–210. CiteSeerX 10.1.1.215.7768. doi:10.1007/978-3-642-14423-3_14. ISBN 978-3-642-14423-3.
^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit (2004). "Batch codes and their applications" (PDF). STOC'04. ACM. pp. 262–271. doi:10.1145/1007352.1007396. Retrieved 2015-10-23.
^ Ostrovsky, Rafail; Skeith III; William E. (2007). "A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. Springer-Verlag. pp. 393–411. doi:10.1007/978-3-540-71677-8_26. ISBN 978-3-540-71677-8.
^ ^a ^b Percy++ / SourceForge에서 C++의 PIR
^ Di Crescenzo, Giovanni; Malkin, Tal; Ostrovsky, Rafail (2000). "Single Database Private Information Retrieval Implies Oblivious Transfer". Eurocrypt 2000. LNCS. Vol. 1807. Springer. pp. 122–138. doi:10.1007/3-540-45539-6_10.
^ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail (2005). "Sufficient Conditions for Collision-Resistant Hashing". Proceedings of the Second Theory of Cryptography Conference. Cambridge, MA, USA: Springer-Verlag. pp. 445–456. doi:10.1007/978-3-540-30576-7_24. ISBN 978-3-540-30576-7.
^ ^a ^b Saint-Jean, Felipe (2005). "A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol" (PDF). Yale University Technical Report YALEU/DCS/TR-1333.
^ "MuchPIR Demo". 14 September 2021.
^ "SealPIR". Github. Retrieved 2018-06-07.
^ "Popcorn" (PDF). Archived from the original (PDF) on 2016-08-21. Retrieved 2016-05-26.
^ "encryptogroup/RAID-PIR". GitHub. Retrieved 2016-05-26.
^ "XPIR-team/XPIR". GitHub. Retrieved 2016-05-26.
^ "upPIR". uppir.poly.edu. Archived from the original on 2016-06-25. Retrieved 2016-05-26.

참고 항목

참조

A. 베이멜, Y.이샤이, E. 쿠실레비츠, J.F.레이먼드정보-이론적 개인 정보 검색을 위한 $O(n^{1/(2k-1)})$ ( n $O(n^{1/(2k-1)})$ / $O(n^{1/(2k-1)})$ ( $O(n^{1/(2k-1)})$ $O(n^{1/(2k-1)})$ - 1 $O(n^{1/(2k-1)})$ ) ${\displaystyle O(n^{1/(2k-1)})$ 장벽 $O(n^{1/(2k-1)})$ 깨기.2002년 제43회 캐나다 밴쿠버 컴퓨터 과학 재단 연례 IEEE 심포지엄의 진행 261-270페이지.
A. 베이멜과 Y.Stahl, 강력한 정보-이론적 개인 정보 검색, 제3차 국제 통신 네트워크 보안 회의(SCN'02)의 진행, 페이지 326–341, 2003.Cite는 DGH 2012, op. cit에서 왔다.
[DGH 2012] Casey Devet, Ian Goldberg 및 Nadia Heyner, Optimally Robust Private Information Research, 제21회 USENIX 보안 심포지엄, 2012년 8월.
[AG 2007] C.아길라르 멜초르와 P. 가보릿.격자 기반 컴퓨팅 효율성이 높은 개인 정보 검색 프로토콜, 2007년 WEWoRC(West European Workshop on Research in Cryptology, WEWoRC)
[CGKS 1998] B.초, 오. 골드리히, E. 쿠실레비츠, M.수단, 민간 정보 검색, ACM 저널, 45(6):965–981, 1998.
[Goldberg 2007] I. Goldberg, 개인 정보 검색의 견고성 향상, IEEE 보안 및 개인 정보 보호 심포지엄(S&P), 2007.
[HOG 2011] R.헨리, F.올루모핀이랑 나.Goldberg, 전자 상거래를 위한 실용적인 PIR, ACM Conference on Computer and Communications Security, 2011.
[LG 2015] W. 루크스와 나.Goldberg, Multi-client 개인 정보 검색을 위한 Sublinear 스케일링, 국제 금융 암호화 및 데이터 보안 회의(FC), 2015.
[DHS 2014] D.뎀믈러, A.헤르츠버그, 그리고 T.Schneider, RAID-PIR: 실제 다중 서버 PIR, In Cloud Computing Security Workshop(CCSW), 2014년
[ABFK 2014] C.아길라-멜초르, J. 배리어, L. 푸스, M.-O. 킬리젠, "XPIR: 모든 사람을 위한 개인 정보 검색", 암호화 ePrint Archive, Report 2014/1025, 2014.
[GCMSAW 2016] T. 굽타, N. 크룩스, W. 멀더넘, S. 세티, L. 알비시, M.월피쉬, [1] 팝콘과 함께 확장 가능한 개인 미디어 소비.USENIX NSDI, 2016년 3월.
[Cappos 2013] J. Cappos, 보안 업데이트를 효율적이고 개인적으로 검색하기 위한 이론적 최적성 방지, 국제 금융 암호화 및 데이터 보안 회의(FC), 2013.
세르게이 예카닌.새로운 로컬 해독 가능한 코드 및 개인 정보 검색 체계, ECCC TR06-127, 2006.
[ACLS 2018] S. Angel, H. Chen, K. Laine, S. S. Setty, PIR(압축 질의 및 상각 질의 처리), IEEE 보안 및 개인 정보 보호 심포지엄(S&P), 2018.

외부 링크

[1] Baumeler, Ämin; Broadbent, Anne (17 April 2014). "Quantum Private Information Retrieval has Linear Communication Complexity". Journal of Cryptology. 28: 161–175. arXiv:1304.5490. doi:10.1007/s00145-014-9180-2. S2CID 1450526.

[ChoKusGolSud98-2] Chor, Benny; Kushilevitz, Eyal; Goldreich, Oded; Sudan, Madhu (1 November 1998). "Private information retrieval" (PDF). Journal of the ACM. 45 (6): 965–981. CiteSeerX 10.1.1.51.3663. doi:10.1145/293347.293350. S2CID 544823.

[KusOst97-3] Kushilevitz, Eyal; Ostrovsky, Rafail (1997). "Replication is not needed: single database, computationally-private information retrieval". Proceedings of the 38th Annual Symposium on Foundations of Computer Science. Miami Beach, Florida, USA: IEEE Computer Society. pp. 364–373. CiteSeerX 10.1.1.56.2667. doi:10.1109/SFCS.1997.646125. ISBN 978-0-8186-8197-4. S2CID 11000506.

[4] Cachin, Christian; Micali, Silvio; Stadler, Markus (1999). "Computationally Private Information Retrieval with Polylogarithmic Communication". Advances in Cryptology - EUROCRYPT '99. Prague, Czech Republic: Springer-Verlag. pp. 402–414. doi:10.1007/3-540-48910-X_28. ISBN 978-3-540-48910-8.

[Lip04-5] Lipmaa, Helger (2005). "An Oblivious Transfer Protocol with Log-Squared Communication". Proceedings of the 8th International Conference on Information Security (ISC 2005). Lecture Notes in Computer Science. Vol. 3650. Singapore: Springer-Verlag. pp. 314–328. CiteSeerX 10.1.1.73.8768. doi:10.1007/11556992_23. ISBN 978-3-540-31930-6.

[6] Gentry, Craig; Ramzan, Zulfikar (2005). "Single-Database Private Information Retrieval with Constant Communication Rate". ICALP. LNCS. Vol. 3580. Springer. pp. 803–815. CiteSeerX 10.1.1.113.6572. doi:10.1007/11523468_65.

[7] Kiayias, Aggelos; Leonardos, Nikos; Lipmaa, Helger; Pavlyk, Kateryna; Tang, Qiang (2015). "Optimal Rate Private Information Retrieval from Homomorphic Encryption". Proceedings on Privacy Enhancing Technologies 2015. Vol. 2015. DE GRUYTER. pp. 222–243. doi:10.1515/popets-2015-0016.

[Lip09-8] Lipmaa, Helger (2010). "First CPIR Protocol with Data-Dependent Computation". Proceedings of the 12th International Conference on Information Security and Cryptology. Lecture Notes in Computer Science. Vol. 5984. Seoul, Korea: Springer-Verlag. pp. 193–210. CiteSeerX 10.1.1.215.7768. doi:10.1007/978-3-642-14423-3_14. ISBN 978-3-642-14423-3.

[9] Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit (2004). "Batch codes and their applications" (PDF). STOC'04. ACM. pp. 262–271. doi:10.1145/1007352.1007396. Retrieved 2015-10-23.

[10] Ostrovsky, Rafail; Skeith III; William E. (2007). "A Survey of Single-Database Private Information Retrieval: Techniques and Applications". Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography. Springer-Verlag. pp. 393–411. doi:10.1007/978-3-540-71677-8_26. ISBN 978-3-540-71677-8.

[:0-11] Percy++ / SourceForge에서 C++의 PIR

[12] Di Crescenzo, Giovanni; Malkin, Tal; Ostrovsky, Rafail (2000). "Single Database Private Information Retrieval Implies Oblivious Transfer". Eurocrypt 2000. LNCS. Vol. 1807. Springer. pp. 122–138. doi:10.1007/3-540-45539-6_10.

[13] Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail (2005). "Sufficient Conditions for Collision-Resistant Hashing". Proceedings of the Second Theory of Cryptography Conference. Cambridge, MA, USA: Springer-Verlag. pp. 445–456. doi:10.1007/978-3-540-30576-7_24. ISBN 978-3-540-30576-7.

[TR1-14] Saint-Jean, Felipe (2005). "A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol" (PDF). Yale University Technical Report YALEU/DCS/TR-1333.

[15] "MuchPIR Demo". 14 September 2021.

[16] "SealPIR". Github. Retrieved 2018-06-07.

[17] "Popcorn" (PDF). Archived from the original (PDF) on 2016-08-21. Retrieved 2016-05-26.

[18] "encryptogroup/RAID-PIR". GitHub. Retrieved 2016-05-26.

[19] "XPIR-team/XPIR". GitHub. Retrieved 2016-05-26.

[20] "upPIR". uppir.poly.edu. Archived from the original on 2016-06-25. Retrieved 2016-05-26.

[2]

[1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Search