학계에서는 그동안 데이터를 암호화한 후 성능 향상, 즉 암호화된 데이터를 빠르게 검색하려고 많이 노력했습니다. 그 노력의 방향은 ‘암호화된 데이터를 기준으로 검색이 가능한 새로운 인덱스’를 생성하는 것이었습니다. 암호화된 데이터에도 인덱스를 만들 수 있다면 원하는 데이터를 찾을 때 인덱스를 보고 복호화해야 할 데이터를 지정하거나 복호화할 데이터의 양을 줄일 수 있기 때문입니다. 이때 순서 정보, 즉 인덱스는 암호화 이전의 순서 정보와 일치해야 합니다.

이런 방식은 2000년대 초반에 버킷 인덱스(Bucket-based Index), 해시 인덱스(Hash-based Index), B 트리 인덱스(B+tree Index) 방식으로 시작하여 다양하게 발전해 왔습니다. 어떤 방식이든 인덱스로 구성하면 인덱스에는 필연적으로 원본 데이터의 통계 정보가 담길 수밖에 없습니다. 따라서 공격자에게 인덱스 정보를 노출하지 않도록 관리해야 합니다.

암호화된 데이터를 검색하는 인덱스 방식을 조금 다르게 접근하는 방식이 OPE(Order Preserving Encryption : 순서 유지 암호화)입니다. OPE는 말 그대로 데이터의 정렬 순서를 유지하면서 암호화를 수행하는 방식입니다. 이는 지금까지 배운 암호화의 (안전성) 개념과 정면으로 충돌합니다. 혼돈과 확산으로 데이터를 최대한 흩트려 놓은 상태가 안전한데, 순서가 유지된다면 이를 과연 암호화라고 할 수 있을까요? 지금부터 OPE는 과연 암호화라고 할 수 있는 안전한 방식인지 살펴보겠습니다.