검색 가능한 대칭 암호화
Searchable symmetric encryptionSSE(Searchable Symmetric Encryption)는 암호화된 문서 또는 파일을 [1][2]복호화할 필요 없이 효율적으로 검색할 수 있는 암호화 형식입니다.SSE를 사용하면 파일을 투명하게 공개하지 않고도 신뢰할 수 없는 클라우드 스토리지 서버에 파일을 아웃소싱할 수 있습니다.
묘사
검색 가능한 대칭 암호화 방식은 문서 D ( , , D) { = ( \ {_ {1 \ , \ {_ { })의 집합을 암호화하는 대칭 키 암호화 방식입니다. 여기서 각 는\ { \ { D_displaystylessbf {} } } } } } 。키워드 W(\ 암호 키(\ K와 W w를 지정하면 암호화된 데이터 수집을 할 수 있는 검색 를 생성할 수 있습니다검색 결과는 ww를 포함하는 암호화된 문서의 서브셋입니다.
스태틱 SSE
정적 SSE 스킴은 3개의 S S ( p , e n , a c h { (은 (는) 다음과 같이 작동합니다.
- {}은 파라미터 kk와 문서 컬렉션 D(\displaystyle \를 입력해 K(\ K와 된 컬렉션 E를 합니다
- k n은 K(\ K와 w(\ w를 입력하여 검색 토큰 를 합니다.
- a h {{는 암호화된 문서 E 와 검색 t 를 입력해 암호화된 세트 R E(\ \를 합니다
정적 SSE 방식은 클라이언트 및 신뢰할 수 없는 서버에 의해 다음과 같이 사용됩니다.클라이언트는 K(\ K와 암호화된 문서 를 반환하는 { 을 사용하여 데이터 수집을 암호화합니다.클라이언트는K(\ K의 비밀을 하고 Edisplaystyle {ED})를 합니다.{}을(를 신뢰할 수 없는 서버에 연결합니다 ww를 검색하려면 클라이언트는 K K 및 w(\displaystyle tk에서 h e(\ { 을 실행하여 서버에 하는검색 토큰 k(\ tk)를 생성합니다.서버는 E 를 하여 검색을 실행하고 암호화된 문서를 서버로 반환합니다.
다이내믹 SSE
동적 SSE 스킴은 검색과 더불어 문서 삽입 및 삭제를 지원합니다.다이내믹 SSE 스킴은 7가지 E ( p , n , h , t , , D t t e t s t t , e e t et s e t )style { 로 구성됩니다. 서 p { { n { { r h { {는 정적 케이스와 같으며 나머지 알고리즘은 다음과 같습니다.
- Token은 (는) K(\ K와 새로운 을 입력으로 하여 삽입 를 출력합니다.
- 된 문서 컬렉션 EDC와 삽입 을 입력해갱신된 암호화된 문서 { 를 출력합니다.
- Token은 (는) K(\ K와 문서 id)를 입력하여 삭제 토큰 를 출력합니다.
- e { \{ } 은 암호화된 데이터 D { \{ 및 삭제 k{ } 를 입력으로 하여 업데이트된 된 수집 E D { \ 를 출력합니다
새 + 을 추가하려면 클라이언트는 en({ {을 합니다. K (\의 을 (를) 생성하여 서버에 전송합니다.는 E(\displaystyle\mathbf { ik itk를 하여 {\displaystyle\{Insert을 하고 업데이트된 된 문서 컬렉션을 저장합니다. id를 가진 문서를 삭제하려면 클라이언트는 D T k n \ 를 합니다.Token 알고리즘을 K K 및 id)로 설정하고 서버에 하는 토큰 (\ dtk를 합니다.는 D 및 와 \{Delete를 하여 업데이트된 암호화된 문서 컬렉션을 저장합니다.
k n \ \ { Delete }를 하지 않는 SSE 스킴Token과 (}}을를 ) 세미 다이내믹이라고 .
검색 가능한 대칭 암호화의 역사
암호화된 데이터에 대한 검색 문제는 송, 바그너, 페리그에[1] 의해 검토되었지만 골드라이치와 오스트롭스키의[3] 망각 RAM에 대한 이전 연구는 이론적으로 이 문제를 해결하기 위해 사용될 수 있었다.이 work[1]. Goh[4]고 장과 Mitzenmacher[5]는 시간에 O(n){O(n)\displaystyle}, n{\displaystyle를 검색 알고리즘으로 새로운 통신 정보 지원 반 구성을 검색 알고리즘과 제 시간에 O(s){O(s)\displaystyle}, s=D{\displaystyles= \mathbf{D}}을 운영하는 체제 현황 평가 체계를 제안하였다.n}은문서 수Curtmola, Garay, Kamara 및 Ostrovsky는[2] 나중에 O{opt 시간을 하는 두 가지 정적 구성을 제안했습니다. 서 t\mathrm 은 w를 하는 문서 수입니다.또한 본 연구에서는 O( p t log (){ ( \ } \ ( ) } } 검색 시간을 한 반동적 구성을 제안했다. 서u { u }는 업데이트 횟수이다.최적의 동적 SSE 구조는 나중에 카마라, 파파만투 및 로더에 [6]의해 제안되었다.
고[4], 장, 미첸마허는[5] SSE에 대한 보안 정의를 제안했다.이는 SSE를 위한 적응형 보안 개념을 제안한 Curtmola, Garay, Kamara 및[2] Ostroovsky에 의해 강화되고 확장되었습니다.또한 이 작업은 SSE의 누출을 최초로 관찰하고 보안 정의의 일부로 SSE를 공식적으로 포착했다.누출은 Chase와 [7]Kamara에 의해 더욱 공식화되고 일반화되었습니다.이슬람, 쿠즈, 칸타르지오글루는 최초의 유출 [8]공격을 묘사했다.
앞에서 설명한 모든 구성은 단일 키워드 검색을 지원합니다.Cash, Jarecki, Jutla, Krawczyk, Rosu 및 Steiner는[9] n의 준선형 시간에서의 접속 검색을 지원하는 SSE 스킴을 제안했다.또한 하위 선형 시간에 검색 가능 정규 형식(SNF)으로 표현될 수 있는 분리 및 부울 검색을 지원하도록 구성을 확장할 수 있습니다.동시에 Pappas, Krell, Vo, Kolesnikov, Malkin, Choi, George, Keromytis 및 Bellovin은[10] 접속사 검색과 모든 분리 및 부울 검색을 지원하는 구조를 설명했습니다.
보안.
SSE 스킴은 신뢰할 수 없는 서버가 문서 또는 검색 쿼리에 대한 일부 정보를 제대로 정의되고 합리적인 누출 이외에는 학습할 수 없도록 설계되어 있습니다.계획의 누출은 그 자체가 여러 개의 누출 패턴으로 구성될 수 있는 누출 프로파일을 사용하여 공식적으로 기술된다.SSE 구축은 가능한 최고의 검색 효율성을 달성하면서 누출을 최소화하려고 시도합니다.
SSE 보안은 여러 적대적 모델에서 분석할 수 있지만 가장 일반적인 모델은 다음과 같습니다.
- 상대에게 암호화된 데이터 수집과 수집에 대해 실행된 모든 작업의 사본을 제공하는 영구 [2]모델
- 스냅샷 모델:[11] 상대에게 암호화된 데이터 수집만 제공됩니다(각 작업 후일 수도 있음).
영속적 모델의 보안
영구 모델에는 다양한 누출 프로파일을 달성하는 SSE 계획이 있다.최적의 시간에 단일 키워드 검색을 실현하는 정적 스킴의 가장 일반적인 유출 프로파일은 t \ { \ 입니다.이 프로파일은 컬렉션 내의 문서 수, 컬렉션 내의 각 문서의 크기, 쿼리가 반복된 경우, 그리고 검색과 일치하는 암호화된 문서를 나타냅니다.ch [2][12]쿼리그러나 검색 시간과 [13][14]저장에 추가 비용을 들이면서 유출을 크게 줄이는 방식을 구축하는 방법은 알려져 있습니다.
동적 SSE 방식을 고려할 때, 최적의 시간 검색을 사용하는 최신 구성에는 순방향[15] 개인 정보를 보장하는 누출 프로파일이 있습니다. 즉, 삽입물은 과거의 검색 쿼리와 상관할 수 없습니다.
스냅샷 모델의 보안
스냅샷 모델에서는 문서 수와 컬렉션 크기를 초과하는 누출이 없는 효율적인 동적 SSE 스킴을 구축할 수 있습니다.[11]스냅샷 모델에서 안전한 SSE 구조를 사용할 경우 시스템에 따라 이전 검색 [16]쿼리를 캐시할 수 있으므로 스킴의 도입 방법을 신중하게 고려해야 합니다.
암호 분석
누출 프로파일은 SSE 스킴의 누출만을 기술할 뿐 누출을 악용할 수 있는지 여부에 대해서는 기술하지 않습니다.따라서 암호 분석은 누출 프로파일의 실제 보안을 더 잘 이해하기 위해 사용됩니다.다양한 가정과 서로 다른 [17][18]누출 프로파일을 공격하는 다양한 적대적 모델에서 작동하는 다양한 공격이 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b c Dawn Xiaoding Song; Wagner, D.; Perrig, A. (2000). "Practical techniques for searches on encrypted data". Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000. IEEE Comput. Soc: 44–55. doi:10.1109/secpri.2000.848445. ISBN 0-7695-0665-8. S2CID 2829840.
- ^ a b c d e Curtmola, Reza; Garay, Juan; Kamara, Seny; Ostrovsky, Rafail (2006-10-30). "Searchable symmetric encryption: improved definitions and efficient constructions". Proceedings of the 13th ACM Conference on Computer and Communications Security. CCS '06. Alexandria, Virginia, USA: Association for Computing Machinery: 79–88. doi:10.1145/1180405.1180417. ISBN 978-1-59593-518-2. S2CID 961719.
- ^ Goldreich, Oded; Ostrovsky, Rafail (May 1996). "Software protection and simulation on oblivious RAMs". Journal of the ACM. 43 (3): 431–473. doi:10.1145/233551.233553. hdl:1721.1/103684. ISSN 0004-5411. S2CID 7502114.
- ^ a b Goh, Eu-Jin. "Secure Indexes".
- ^ a b Chang, Yan-Cheng; Mitzenmacher, Michael (2005). Ioannidis, John; Keromytis, Angelos; Yung, Moti (eds.). "Privacy Preserving Keyword Searches on Remote Encrypted Data". Applied Cryptography and Network Security. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 3531: 442–455. doi:10.1007/11496137_30. ISBN 978-3-540-31542-1.
- ^ Kamara, Seny; Papamanthou, Charalampos; Roeder, Tom (2012-10-16). "Dynamic searchable symmetric encryption". Proceedings of the 2012 ACM Conference on Computer and Communications Security. CCS '12. New York, NY, USA: Association for Computing Machinery: 965–976. doi:10.1145/2382196.2382298. ISBN 978-1-4503-1651-4. S2CID 243046.
- ^ Chase, Melissa; Kamara, Seny (2010). Abe, Masayuki (ed.). "Structured Encryption and Controlled Disclosure". Advances in Cryptology - ASIACRYPT 2010. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6477: 577–594. doi:10.1007/978-3-642-17373-8_33. ISBN 978-3-642-17373-8.
- ^ Islam, Mohammad; Kuzu, Mehmet; Kantarcioglu, Murat. "Access Pattern disclosure on Searchable Encryption:Ramification, Attack and Mitigation" (PDF). Network and Distributed System Security (NDSS) Symposium.
- ^ Cash, David; Jarecki, Stanislaw; Jutla, Charanjit; Krawczyk, Hugo; Roşu, Marcel-Cătălin; Steiner, Michael (2013). Canetti, Ran; Garay, Juan A. (eds.). "Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries". Advances in Cryptology – CRYPTO 2013. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 8042: 353–373. doi:10.1007/978-3-642-40041-4_20. ISBN 978-3-642-40041-4.
- ^ Pappas, Vasilis; Krell, Fernando; Vo, Binh; Kolesnikov, Vladimir; Malkin, Tal; Choi, Seung Geol; George, Wesley; Keromytis, Angelos; Bellovin, Steve (May 2014). "Blind Seer: A Scalable Private DBMS". 2014 IEEE Symposium on Security and Privacy. IEEE: 359–374. doi:10.1109/sp.2014.30. ISBN 978-1-4799-4686-0. S2CID 9165575.
- ^ a b Amjad, Ghous; Kamara, Seny; Moataz, Tarik (2019-01-01). "Breach-Resistant Structured Encryption". Proceedings on Privacy Enhancing Technologies. 2019 (1): 245–265. doi:10.2478/popets-2019-0014. S2CID 4047057.
- ^ "Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation – NDSS Symposium". Retrieved 2022-02-22.
- ^ Kamara, Seny; Moataz, Tarik; Ohrimenko, Olya (2018). Shacham, Hovav; Boldyreva, Alexandra (eds.). "Structured Encryption and Leakage Suppression". Advances in Cryptology – CRYPTO 2018. Lecture Notes in Computer Science. Cham: Springer International Publishing. 10991: 339–370. doi:10.1007/978-3-319-96884-1_12. ISBN 978-3-319-96884-1.
- ^ "Revisiting Leakage Abuse Attacks – NDSS Symposium". Retrieved 2022-02-22.
- ^ "Practical Dynamic Searchable Encryption with Small Leakage – NDSS Symposium". Retrieved 2022-02-22.
- ^ Grubbs, Paul; Ristenpart, Thomas; Shmatikov, Vitaly (2017-05-07). "Why Your Encrypted Database Is Not Secure". Proceedings of the 16th Workshop on Hot Topics in Operating Systems. HotOS '17. New York, NY, USA: Association for Computing Machinery: 162–168. doi:10.1145/3102980.3103007. ISBN 978-1-4503-5068-6. S2CID 10111288.
- ^ Yao, Jing; Zheng, Yifeng; Guo, Yu; Wang, Cong (2020-10-06). "SoK: A Systematic Study of Attacks in Efficient Encrypted Cloud Data Search". Proceedings of the 8th International Workshop on Security in Blockchain and Cloud Computing. SBC '20. New York, NY, USA: Association for Computing Machinery: 14–20. doi:10.1145/3384942.3406869. ISBN 978-1-4503-7609-9. S2CID 222179683.
- ^ Kamara, Seny; Kati, Abdelkarim; Moataz, Tarik; Schneider, Thomas; Treiber, Amos; Yonli, Michael (2021). "Cryptanalysis of Encrypted Search with LEAKER - A framework for LEakage AttacK Evaluation on Real-world data".
{{cite journal}}
:Cite 저널 요구 사항journal=
(도움말)