[go: up one dir, main page]

KR20090048623A - 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에대한 검색을 수행하는 방법 및 이를 위한 원격 데이터베이스를 제공하는 방법, 및 기계-판독가능 매체 - Google Patents

데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에대한 검색을 수행하는 방법 및 이를 위한 원격 데이터베이스를 제공하는 방법, 및 기계-판독가능 매체 Download PDF

Info

Publication number
KR20090048623A
KR20090048623A KR1020097004699A KR20097004699A KR20090048623A KR 20090048623 A KR20090048623 A KR 20090048623A KR 1020097004699 A KR1020097004699 A KR 1020097004699A KR 20097004699 A KR20097004699 A KR 20097004699A KR 20090048623 A KR20090048623 A KR 20090048623A
Authority
KR
South Korea
Prior art keywords
item
plain text
data
indexing
database
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
KR1020097004699A
Other languages
English (en)
Other versions
KR101403745B1 (ko
Inventor
엘레나 다니엘라 크리스토퍼
로렌티우 보그단 크리스토퍼
탄모이 두타
라울 가르시아
성 엘. 수에
Original Assignee
마이크로소프트 코포레이션
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 마이크로소프트 코포레이션 filed Critical 마이크로소프트 코포레이션
Publication of KR20090048623A publication Critical patent/KR20090048623A/ko
Application granted granted Critical
Publication of KR101403745B1 publication Critical patent/KR101403745B1/ko
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • G06F21/62—Protecting access to data via a platform, e.g. using keys or access control rules
    • G06F21/6218—Protecting access to data via a platform, e.g. using keys or access control rules to a system of files or objects, e.g. local or distributed file system or database
    • G06F21/6245—Protecting personal data, e.g. for financial or medical purposes
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
    • G06F21/60—Protecting data
    • G06F21/606—Protecting data by securing the transmission between two devices or processes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3236—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials using cryptographic hash functions

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Bioethics (AREA)
  • General Health & Medical Sciences (AREA)
  • Health & Medical Sciences (AREA)
  • Databases & Information Systems (AREA)
  • Computer Hardware Design (AREA)
  • Data Mining & Analysis (AREA)
  • Medical Informatics (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mathematical Physics (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Storage Device Security (AREA)

Abstract

인덱싱 값은 요청자 모르게, 원하는 평문 데이터 항목 및 암호화 키에 기초하여 결정될 수 있다. 인덱싱 값을 이용하여 인덱싱 구조의 엔트리에 액세스함으로써 비-결정적으로 암호화된 암호문 항목을 포함한 대응하는 데이터베이스 엔트리를 획득한다. 다른 실시예에서, 데이터베이스의 인덱싱 구조가 액세스될 수 있다. 안덱싱 구조의 항목들의 위치는 대응하는 평문 항목들에 기초할 수 있다. 인덱싱 구조의 대응하는 평문 항목에 관련된 참조는 암호화될 수 있고, 인덱싱 구조의 다른 정보는 비암호화될 수 있다. 인덱싱 구조의 일부가 메모리 내로 로딩되고, 평문 항목들 중 하나에 관련된 암호화된 참조들 중 적어도 하나는 복호화될 수 있다. 복호화된 참조를 이용하여 데이터베이스로부터의 대응하는 비-결정적으로 암호화된 데이터 항목에 액세스할 수 있다.
Figure P1020097004699
데이터베이스 시스템, 평문 데이터 항목, 인덱싱 값, 암호화 키, 메시지 인증 코드

Description

데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법 및 이를 위한 원격 데이터베이스를 제공하는 방법, 및 기계-판독가능 매체{ENCRYPTED DATA SEARCH}
회사들에서는 데이터베이스 시스템을 이용하여 그들의 여러 사업 측면에서 이용되는 데이터를 저장하고 검색한다. 그러한 데이터는 수백만 기록을 포함할 수 있으며, 회사들은 이들 중 적어도 일부, 예컨대, 고객 정보와 같은 개인 정보를 숨기기를 원한다. 그러한 정보는 악의적 의도를 가질 수 있는 다른 사람들에게는 가치있는 것이 될 수 있다. 어느 회사의 적대자가 그러한 개인 정보를 얻을 수 있게 되면, 그 적대자는 그 회사, 그 고객 또는 둘 모두에 문제를 일으킬 수 있다.
데이터베이스 내의 가치있는 정보를 보호하고 개인 규정 또는 정책들을 준수하기 위해 이용되는 일반적인 한 방법은 암호화이다. 그러나, 데이터베이스에서 암호화된 데이터를 이용할 경우에는, 예컨대, 기존 애플리케이션에 의한 그 데이터로의 허가된 액세스 허용 방법, 및 그 데이터 전부에 대해 복호화 및 선형 검색(linear search)을 행하지 않으면서 그 데이터의 특정 항목들(items)을 찾아내는 방법과 같은, 다른 쟁점들(issues)이 제기된다.
기존의 데이터베이스 시스템에서는 결정적 암호화(deterministic encryption)로 칭해질 수 있는 것을 사용함으로써 상기한 문제들을 해결하였다. 그러한 데이터베이스 시스템에서는, 동일한 암호화 키를 사용할 경우에는 평문(plaintext)의 항목(an item)은 항상 동일한 암호문으로 암호화될 것이다. 결정적 암호화의 예들은 전자 암호 일람표(electronic codebook; ECB) 모드 내의 블록 암호(block ciphers)의 이용 또는 일정한 초기화 벡터(IV)의 이용을 포함한다. 결정적 암호화는 주어진 암호화 키를 이용할 경우에는 항상 동일한 평문을 동일한 암호문으로 암호화하기 때문에, 데이터 패턴들을 인식할 수 있으므로, 정보 누설로 이어진다. 이는 특히, 암호화될 데이터가 너무 방대하여 단일 블록-어느 블록 암호 알고리즘을 이용하는 것에 따라 8 바이트 길이 또는 16 바이트 길이일 수 있음-에 적합하지 않을 때 문제로 된다.
본 요약은 이하의 상세한 설명에서 상세히 기술될 개념들에 대한 선택을 단순화된 형태로 도입하도록 제공된 것이다. 이 요약은 청구 대상물의 핵심적 특징들 또는 본질적 특징들을 구별하려는 것도, 또한 청구 대상물의 범주를 제한하려는 의도도 아니다.
후술될 실시예들은 비-결정적으로 암호화된 데이터에 대한 검색을 수행할 수 있는 데이터베이스 시스템에 관한 것이다.
일 실시예에서, 데이터베이스의 암호화된 열(column)의 비-결정적으로 암호화된 암호문 항목에 대응하는 데이터 항목에 대한 검색은 데이터베이스의 암호화된 열에 대응하는 인덱싱 구조를 이용하여 수행될 수 있다. 코드(code)는 데이터 항목 및 암호화 키에 기초하여 요청자가 모르게(transparently) 계산될 수 있다. 코드는 인덱싱 구조에 대한 인덱스로서 사용될 수 있으며, 인덱싱 구조는 대응하는 데이터 항목 및 암호화 키에 기초하여 각각의 코드에 따라 조직화된 엔트리를 가질 수 있다. 일부 구현에서, 인덱싱 구조의 엔트리 각각은 데이터베이스의 암호화된 열의 대응하는 비-결정적으로 암호화된 암호문 항목을 포함하는 데이터베이스의 행(row)에 액세스하기 위한 각각의 코드 및 데이터를 포함할 수 있다.
다른 실시예에서, 데이터베이스의 암호화된 열의 비-결정적으로 암호화된 암호문 항목에 대응하는 원하는 데이터 항목에 대한 검색은 데이터베이스의 암호화된 열에 대응하는 인덱싱 구조에 액세스함으로써 수행될 수 있다. 인덱싱 구조의 엔트리들은 데이터베이스의 암호화된 열의 비-결정적으로 암호화된 암호문 항목들에 대응하는 평문 데이터 항목들에 따라 조직화될 수 있다. 인덱싱 구조에서, 대응하는 평문 데이터 항목들에 관련된 참조들(references)은 암호화될 수 있으며, 인덱싱 구조 내의 다른 정보는 비암호화될 수 있다. 검색은 인덱싱 구조의 적어도 일부를 메모리 내로 로딩하고, 인덱싱 구조의 엔트리에 액세스하고, 인덱싱 구조의 엔트리의 참조들 중 적어도 하나를 복호화함에 의해 수행될 수 있다. 적어도 하나의 복호화된 참조는 데이터베이스의 암호화된 열의 대응하는 비-결정적으로 암호화된 암호문 항목을 포함한 데이터베이스의 행에 액세스하는 데 이용될 수 있다.
상기 및 기타의 다른 이점들 및 특징들을 얻을 수 있는 방법을 기술하기 위해, 이하에서 첨부된 도면에 도시된 특정 실시예들을 참조하면서 더 상세히 기술하고 묘사할 것이다. 이들 도면은 단지 전형적인 실시예들만을 예시한 것이므로, 그 범주를 제한하려는 것으로 여겨서는 안 된다는 조건 하에, 첨부된 도면을 이용하여 특수성(specificity) 및 상세(detail)를 추가하면서 구현예들을 기술하고 설명할 것이다.
도 1은 본 발명의 요지에 관한 예시적인 운영 환경을 도시한 도면.
도 2는 도 1의 처리 장치(102), 도 1의 처리 장치(104), 또는 두 처리 장치 모두를 구현하는 데 사용될 수 있는 예시적인 처리 장치의 기능 블록도.
도 3A 내지 도 3C는 본 발명의 요지에 관한 실시예에서 사용될 수 있는 예시적인 인덱싱 구조를 도시한 도면.
도 4는 도 3A 내지 도 3C의 예시적인 인덱싱 구조에 일치하게 수행될 수 있는 방법을 도시한 흐름도.
도 5는 본 발명의 요지에 관한 다른 실시예에서 사용될 수 있는 예시적인 인덱싱 구조를 도시한 도면.
도 6은 도 5의 예시적인 인덱싱 구조에 일치하여 수행될 수 있는 방법을 도시한 흐름도.
도 7은 본 발명의 요지에 관한 제3 실시예에서 수행될 수 있는 방법을 도시한 흐름도.
이하에서 실시예들을 상세히 기술하기로 한다. 비록 특정 구현들이 기술되지만, 이는 단지 예시 목적으로 행해진 것임은 말할 필요도 없다. 당업자라면, 본 발명의 요지의 사상 및 범주를 벗어나지 않는 한 다른 구성성분 및 구성을 사용할 수 있다는 것을 인식할 것이다.
예시적 운영 환경
도 1은 본 발명의 요지에 관한 실시예를 위한 예시적 운영 환경(100)을 도시한다. 운영 환경(100)은 처리 장치(102), 처리 장치(104) 및 네트워크(106)를 포함할 수 있다.
처리 장치(102)는, 예를 들어, 데이터베이스 시스템을 실행할 수 있는 서버 또는 다른 처리 장치일 수 있다. 처리 장치(104)는 애플리케이션을 실행하고 네트워크(106)를 통해 처리 장치(102)와 통신할 수 있는 퍼스널 컴퓨터(PC) 또는 다른 처리 장치일 수 있다.
네트워크(106)는 유선 또는 무선 네트워크일 수 있으며, 유선 또는 무선 수단을 통해 연결되는 다수의 장치를 포함할 수 있다. 네트워크(106)는 단지 하나의 네트워크 또는 일부가 상이한 유형의 네트워크일 수 있는 다수의 상이한 네트워크를 포함할 수 있다.
운영 환경(100)에서, 처리 장치(104)는 네트워크(106)를 통해 처리 장치(102)의 데이터베이스 내의 정보에 액세스하는 애플리케이션을 실행시킬 수 있다. 이 애플리케이션은 처리 장치(102)의 데이터베이스 내의 데이터를 생성, 삭제, 판독 또는 수정할 수 있다.
도 1은 예시적 운영 환경을 도시한다. 본 발명의 요지에 관한 다른 실시예에서 운영 환경(100)의 다른 운영 환경 또는 변화를 사용할 수 있다. 예를 들어, 도 1은 처리 장치(102)와 처리 장치(104)를 분리된 장치로서 도시한다. 그러나, 처리 장치(102 및 104)는 일 실시예에서 단일 처리 장치로 결합될 수 있다. 그러한 실시예에서는, 운영 환경은 네트워크(106)를 포함하지 않을 수 있다. 다른 실시예에서는, 처리 장치(102)에 의해 수행되는 기능 또는 서비스들은 예를 들어, 네트워크(106) 등의 네트워크를 통해 연결될 수 있는 다수의 처리 장치들 간에 배포될 수 있다.
예시적 처리 장치
도 2는 예시적 처리 장치(200)를 도시하는 기능 블록도로서, 이 처리 장치(200)는 처리 장치(102), 처리 장치(104) 또는 둘 모두를 구현하는 데 사용될 수 있다. 처리 장치(200)는 , 버스(210), 프로세서(220), 메모리(230), 판독 전용 메모리(ROM)(240), 저장 장치(250), 입력 장치(260), 출력 장치(270), 및 통신 인터페이스(280)를 포함할 수 있다. 버스(210)는 처리 장치(200)의 구성성분들 사이에서 통신을 행하게 한다. 처리 장치(102) 및 처리 장치(104) 모두를 단일 처리 장치로 구현하는 데 처리 장치(200)를 사용하는 실시예들에서, 통신 인터페이스(280)는 처리 장치(200)의 구성성분들 중 하나로서 포함되지 않을 수 있다.
프로세서(220)는 명령어들을 해석하고 실행하는 적어도 하나의 통상의 프로세서 또는 마이크로프로세서를 포함할 수 있다. 메모리(230)는 프로세서(220)에 의해 실행되는 정보 및 명령어들을 저장하는 랜덤 액세스 메모리(RAM) 또는 다른 유형의 동적 저장 장치일 수 있다. 메모리(230)는 또한 프로세서(220)에 의한 명령어들의 실행 중에 이용되는 일시적 변수(variables) 또는 다른 중간(intermediate) 정보를 저장할 수 있다. ROM(240)은 프로세서(220)를 위한 정적 정보 및 명령어들을 저장하는 통상의 ROM 장치 또는 다른 유형의 정적 저장 장치를 포함할 수 있다. 저장 장치(250)는 데이터 및/또는 명령어들을 저장하는 임의 유형의 매체를 포함할 수 있다. 처리 장치(200)가 처리 장치(102)를 구현하는 데 사용되면, 저장 장치(250)는 데이터베이스 시스템의 하나 이상의 데이터베이스를 포함할 수 있다.
입력 장치(260)는, 예컨대, 키보드, 마우스, 또는 여타의 입력 장치와 같은, 사용자에게 처리 장치(200)에 정보를 입력할 수 있게 하는 하나 이상의 통상의 기구(mechanisms)를 포함할 수 있다. 출력 장치(270)는 디스플레이, 프린터 또는 여타의 출력 장치를 비롯하여, 사용자에게 정보를 출력하는 하나 이상의 통상의 기구를 포함할 수 있다. 통신 인터페이스(280)는 처리 장치(200)가 다른 장치들 또는 네트워크들과 통신할 수 있도록 하게 하는 임의 송수신기 형태의 기구를 포함할 수 있다. 일 실시예에서, 통신 인터페이스(280)는 네트워크(106)에 대한 인터페이스를 포함할 수 있다.
처리 장치(200)는, 예를 들어, 메모리(230) 등의 컴퓨터-판독가능 매체 또는 다른 매체에 포함된 명령어들의 시퀀스를 실행하는 프로세서(220)에 응답하여 그러한 기능을 수행할 수 있다. 그러한 명령어들은 저장 장치(250) 등의 또 다른 컴퓨터-판독가능 매체로부터, 또는 통신 인터페이스(280)를 통한 분리된 장치로부터 메모리(230) 내로 판독 입력될 수 있다.
개관
전형적인 데이터베이스 시스템에서, 데이터는 테이블(tables)로 저장되는 것 으로 관찰될 수 있다. 테이블의 행은 파일의 레코드(record)에 해당한다. 일부 데이터베이스 시스템에서는 테이블의 열에 저장된 데이터가 암호화되도록 할 수 있다. 그러한 데이터베이스 시스템은 암호화된 열 내의 데이터가 결정적으로 암호화되어 있다는 조건 하에, 그 데이터에 대한 검색을 허가할 수 있다. 즉, 데이터베이스의 암호화된 열에서 결정적으로 암호화된 암호문에 대응하는 특정 평문 값을 갖는 테이블 내의 행들에 대한 검색이 수행될 수 있다. 그러나, 앞서 언급한 바와 같이, 결정적 암호화는 항상 평문 항목들을 동일한 대응하는 암호문 항목들로 암호화한다. 따라서, 데이터 패턴들이 인식가능해져 정보 누설로 이어질 수 있다.
예를 들어, 랜덤 초기화 벡터와 함께 암호-블록 연쇄(CBC) 모드의 블록 암호 이용과 같은 비-결정적 암호화 방법 또는 다른 비-결정적 암호화 방법들은 동일한 평문 데이터 항목들을 상이한 암호문 데이터 항목들로 암호화할 수 있다. 예를 들어, 랜덤 초기화 벡터와 함께 CBC 모드의 블록 암호의 이용에 따른 비-결정적 암호화는 평문의 현재 블록을 암호화하기 전에 평문의 현재 블록과 이전의 암호문 블록을 XOR(배타적 논리합) 연산함으로써 평문의 각 블록을 암호화할 수 있다. 따라서, 암호문 데이터 항목의 값은 대응하는 평문 데이터 항목 및 암호화 키뿐 아니라, 예를 들어, 이전에 암호화된 데이터 블록 또는 랜덤 초기화 벡터 등의 다른 데이터에도 기반될 수 있다.
본 발명의 요지에 관한 실시예들은, 데이터베이스의 암호화된 열의 비-결정적으로 암호화된 데이터에 대해 검색을 수행할 수 있는 데이터베이스 시스템에 관련된다. 일 실시예에서, 코드는 원하는 평문 데이터 항목 및 암호화 키에 기초하 여 계산될 수 있다. 이 코드는 메시지 인증 코드(MAC), 해싱된 메시지 인증 코드(HMAC), 또는 기타의 코드일 수 있다. 이 코드는 인덱싱 구조에 대한 인덱스로서 사용될 수 있으며, 인덱싱 구조는 대응하는 평문 데이터 항목들 및 암호화 키에 기초한 각각의 코드에 따라 조직화된 엔트리들을 가질 수 있다.
일 구현에서, 인덱싱 구조는 데이터베이스의 암호화된 열의 암호화된 데이터에 대응하는 특정의 평문 데이터 항목을 갖는 데이터베이스 내의 하나 이상의 행들을 검색하는 데 사용될 수 있는, B-트리 도는 다른 인덱싱 구조일 수 있다. 인덱싱 구조의 엔트리 각각은 대응하는 평문 데이터 항목 및 암호화 키에 기초하여 계산된 코드에 대응하는 인덱싱 값, 및 데이터베이스의 암호화된 열의 대응하는 비-결정적으로 암호화된 암호문 항목을 포함하는 데이터베이스의 행에 액세스하는 데이터를 포함할 수 있다.
다른 구현에서, 인덱싱 구조는 각각의 항목들에 대해 대응하는 해시값에 따라 할당되는 해시 버킷(hash buckets)을 포함할 수 있다. 해싱된 메시지 인증 코드는 각각의 평문 데이터 항목 및 암호화 키에 기초하여 계산될 수 있다. 해시값은 계산된 해싱된 메시지 인증 코드를 해싱함에 의해 생성될 수 있다. 해시 버킷의 각 항목은 각각의 평문 데이터 항목에 대응하는 비-결정적으로 암호화된 데이터 항목을 포함한 데이터베이스 엔트리를 획득하기 위한 정보를 포함할 수 있다.
다른 실시예에서, 데이터베이스의 비-결정적으로 암호화된 열에 대한 인덱싱 구조를 액세스할 수 있다. 인덱싱 구조의 각 엔트리는 데이터베이스의 암호화된 열의 비-결정적으로 암호화된 암호문 항목에 대응하는 평문 데이터 항목에 따라 조 직될 수 있다. 인덱싱 구조의 각 엔트리는 대응하는 평문 데이터 항목에 관련된 하나 이상의 참조를 포함할 수 있다. 대응하는 평문 데이터 항목에 관련된 하나 이상의 참조는 암호화될 수 있으며, 인덱싱 구조 내의 다른 정보는 암호화되지 않을 수 있다. 검색이 행해지면, 인덱싱 구조의 적어도 일부가 메모리 내로 로딩될 수 있어, 인덱싱 구조의 대응하는 엔트리 중 하나가 액세스될 수 있다. 인덱싱 구조의 엔트리 중 하나에 대한 하나 이상의 암호화된 참조는 복호화될 수 있어, 데이터베이스의 암호화된 열의 대응하는 비-결정적으로 암호화된 암호문 항목을 포함한 행에 액세스하는 데 이용된다.
일부 실시예에서는, 대칭 키를 이용하여 비-결정적 암호화 및 복호화를 수행할 수 있다. 즉, 암호화 키를 이용하여 데이터 항목을 비-결정적으로 암호화시킬 수 있으며, 동일한 암호화 키를 이용하여 암호화된 데이터 항목을 복호화할 수 있다.
다른 실시예에서는, 비대칭 키를 이용하여 비-결정적 암호화 및 복호화를 수행할 수 있다. 즉, 공개 암호화 키를 이용하여 데이터 항목을 비-결정적으로 암호화시킬 수 있으며, 개인 암호화 키를 이용하여 그 데이터를 복호화할 수 있다.
예시적 방법
데이터베이스 시스템은 전형적으로 특정 레코드 또는 행에 액세스하기 위해 데이터베이스의 열에 저장된 데이터를 신속하게 검색하는 임의 유형의 인덱싱 방식(indexing scheme)을 이용한다. 잘 알려진 한 인덱싱 방식은 B-트리의 이용을 포함하지만, 다른 실시예에서는 다른 인덱싱 방식도 사용될 수 있다. 일 실시예에 서는, 데이터베이스 시스템의 인덱싱 방식에 듀플릿(duplet)이라 칭하는 새로운 데이터 유형을 이용할 수 있다. 이 듀플릿은 쌍을 이룬(paired) 데이터 항목들을 포함할 수 있다. 예를 들어, 듀플릿은 데이터베이스의 암호화된 열에 저장된 비-결정적으로 암호화된 암호문 항목, 및 데이터베이스의 암호화된 열에 저장된 비-결정적으로 암호화된 암호문 항목과 동일할 수 있는 비-결정적으로 암호화된 암호문에 대응하는 평문 항목에 기초한 코드를 포함할 수 있다. 본 발명자들은 비-결정적으로 암호화된 암호문을 E-값이라 칭한다.
데이터베이스 시스템이 데이터베이스 내에 데이터를 삽입하거나 데이터베이스 내의 데이터를 갱신할 경우, 데이터베이스 시스템은 단일 원자 동작(a single atomic operation)에서 듀플릿의 두 부분을 동기화 상태로 유지시킬 수 있다. 즉, 일부 실시예에서, 데이터베이스 시스템은 듀플릿의 한 부분을 듀플릿의 다른 부분을 기입하지 않고는 기입할 수 없을 수 있다.
본 발명의 요지에 관한 실시예에서, 평문 항목에 기초한 코드는 메시지 인증 코드(MAC), 또는 다른 코드일 수 있다. 일 구현에서, MAC는 평문 항목 및 암호화 키를 이용하여 일방향 해시 계산되는, 해싱된 메시지 인증 코드(HMAC)일 수 있다. 암호화 키는 E-값을 형성하는 데 이용되는 암호화 키, E-값을 형성하는 데 이용되는 키에 의해 보호될 수 있는 제2 키, 또는 완전히 독립된 키의 등가물일 수 있다.
도 3A는 본 발명의 요지에 관련된 실시예에서 인덱싱 구조로서 사용될 수 있는 예시적인 B-트리를 도시한다. 예시적인 B-트리는 인덱스 노드(302, 312, 320, 326, 328, 330, 332, 334, 336, 338, 340 및 342)를 포함할 수 있다. 인덱스 노드 각각은 하나 이상의 엔트리를 포함할 수 있다. 리프(leaf) 노드가 아닌 인덱스 노드는 다른 인덱스 노드로의 하나 이상의 링크를 포함할 수 있다. 예를 들어, 인덱스 노드(302)는 다수의 엔트리를 포함할 수 있으며, 인덱스 노드(312, 320, 326 및 328) 등의 다른 인덱스 노드로의 링크를 더 포함할 수 있다. 인덱스 노드(312)는 다수의 엔트리를 포함할 수 있으며, 이 예에서 리프 노드일 수 있는, 인덱스 노드(330, 332 및 334) 등의 다른 인덱스 노드로의 링크를 더 포함할 수 있다. 인덱스 노드(320)는 적어도 하나의 엔트리와, 이 예에서 리프 노드일 수 있는, 인덱스 노드(336 및 338)로의 링크를 포함할 수 있다. 인덱스 노드(326)는 적어도 하나의 엔트리와, 이 예에서 리프 노드일 수 있는, 인덱스 노드(340)로의 링크를 포함할 수 있다. 인덱스 노드(328)는 적어도 하나의 엔트리와, 이 예에서 리프 노드일 수 있는, 인덱스 노드(342)로의 링크를 포함할 수 있다.
도 3B는 본 발명의 요지에 관한 도 3A의 예시적 인덱스 노드(302, 312 및 320)를 보다 상세히 도시한 것이다. 이 예시적인 B-트리 인덱싱 구조에서, 인덱스 노드의 각 엔트리는 듀플릿을 포함할 수 있다. 그러나, 다른 실시예에서의 다른 인덱싱 구조에서 듀플릿을 사용할 수 있다. 도 3B에 도시된 바와 같이, 각각의 인덱스 노드는 하나 이상의 항목을 포함할 수 있고, 하나 이상의 항목 각각은 듀플릿을 포함할 수 있다. 예를 들어, 인덱스 노드(302)는, 제1 평문 항목 및 키 k1에 의해 암호화된 제1 평문 항목에 대응하는 E-값, hdfyjd,에 기초한 MAC 또는 HMAC일 수 있는, 예를 들어, 33567 등의 코드일 수 있는 인덱스 값을 포함한 듀플릿을 갖는 제1 항목, 제2 평문 항목 및 키 k1에 의해 암호화된 제2 평문 항목에 대응하는 E-값, olhdrs,에 기초한 MAC 또는 HMAC일 수 있는, 예를 들어, 58957 등의 코드일 수 있는 인덱스 값을 포함한 듀플릿을 갖는 제2 항목, 및 제3 평문 항목 및 키 k1에 의해 암호화된 제3 평문 항목에 대응하는 E-값, thdksim,에 기초한 MAC 또는 HMAC일 수 있는, 예를 들어, 97460 등의 코드일 수 있는 인덱스 값을 포함한 듀플릿을 갖는 제3 항목을 포함할 수 있다. 도 3B에 도시된 바와 같이, 인덱스 노드(312)는 두 엔트리를 포함할 수 있다. 인덱스 노드(312)의 제1 엔트리는 제4 평문 항목 및 키 k1에 의해 암호화된 제4 평문 항목에 대응하는 E-값, ifjtrslkm,에 기초한 인덱스 값, 16485,을 갖는 듀플릿을 포함할 수 있다. 인덱스 노드(312)의 제2 엔트리는 제5 평문 항목 및 키 k1에 의해 암호화된 제5 평문 항목에 대응하는 E-값, eswgh,에 기초한 인덱스 값, 20945,을 갖는 듀플릿을 포함할 수 있다. 인덱스 노드(320)는 듀플릿을 포함한 하나의 엔트리를 포함할 수 있다. 듀플릿은 제6 평문 항목 및 키 k1에 의해 암호화된 제6 평문 항목에 대응하는 E-값, dfthvc,에 기초한 인덱스 값, 46789,을 가질 수 있다.
인덱스 노드(302)는, 엔트리가 인덱스 노드(302)의 인덱스 값 33567보다 작은 대응하는 인덱스 값을 갖는 인덱스 노드(312)로의 링크일 수 있는 링크(304), 엔트리가 인덱스 노드(302)의 인덱스 값 33567보다 크고 인덱스 값 58957보다 작은 대응하는 인덱스 값을 갖는 인덱스 노드(320)로의 링크인 링크(306), 하나 이상의 엔트리가 인덱스 노드(302)의 인덱스 값 58957보다 크고 인덱스 값 97460 보다 작은 각각의 인덱스 값을 갖는 인덱스 노드(326)에 인덱스 노드(302)를 링크할 수 있는 링크(308), 및 하나 이상의 엔트리가 인덱스 노드(302)의 인덱스 값 97460보다 큰 각각의 인덱스 값을 갖는 인덱스 노드(328)에 인덱스 노드(302)를 링크할 수 있는 링크(310)를 포함할 수 있다.
또한, 인덱스 노드(312)는, 인덱스 노드(312)의 인덱스 값 16485보다 작은 인덱스 값을 갖는 하나 이상의 엔트리를 포함할 수 있는 인덱스 노드(330)로의 링크(314), 인덱스 노드(312)의 인덱스 값 16485보다 크고 인덱스 값 20945보다 작은 인덱스 값을 갖는 하나 이상의 엔트리를 포함할 수 있는 인덱스 노드(332)로의 링크(316), 및 인덱스 노드(312)의 인덱스 값 20945보다 큰 인덱스 값을 갖는 하나 이상의 엔트리를 포함할 수 있는 인덱스 노드(334)로의 링크(318)를 포함할 수 있다. 인덱스 노드(320)는, 인덱스 노드(320)의 인덱스 값 46789보다 작은 인덱스 값을 갖는 하나 이상의 엔트리를 포함할 수 있는 인덱스 노드(336)로의 링크(322), 및 인덱스 노드(320)의 인덱스 값 46789보다 큰 인덱스 값을 갖는 하나 이상의 엔트리를 포함할 수 있는 인덱스 노드(338)로의 링크(324)를 포함할 수 있다.
인덱스 노드 엔트리 각각은 대응하는 평문 데이터 항목의 데이터 유형을 나타내는 정보(도시 안 됨)를 포함할 수 있으며, 데이터베이스의 암호화된 열의 대응하는 비-결정적으로 암호화된 암호문에 대한 참조 또는 포인터(도시 안 됨)를 포함할 수 있다. 또한, 인덱스 노드 각각은 도 3B의 예시적인 인덱싱 구조에서 도시된 것과는 다른 개수의 항목을 포함할 수 있다. 예를 들어, 인덱스 노드(302, 312 또는 320)는 도 3B에 도시된 것과 다른 개수의 항목을 각각의 인덱스 노드에 포함할 수 있다.
도 3A 및 도 3B의 인덱싱 구조는 예시적인 인덱싱 구조이다. 비록 도 3B가 인덱스 값 및 E-값을 포함한 예시적인 인덱싱 구조의 각 항목을 도시하지만, 다른 실시예에서는, 인덱싱 구조의 각 항목은 인덱스 값을 포함할 수 있으며, 대응하는 E-값은 별도의 데이터 구조에 존재한다. 예를 들어, 도 3C의 예시적인 인덱스 노드(302')는 도 3B의 인덱스 노드(302)와 유사하다. 그러나, 인덱스 노드(302')의 항목 각각은 이 예에서 인덱스 값인 듀플릿의 제1 엔트리; 및 테이블, 어레이 또는 다른 데이터 구조일 수 있는 데이터 구조(360)에 포함되는 대응하는 E-값에 대한 참조 또는 포인터를 포함할 수 있다. 비록 데이터 구조(360)가 데이터 구조(360) 내에서 연속한 위치에 있는 인덱스 노드(302')에 대응하는 E-값들을 도시하였지만, E-값들은 데이터 구조(360) 내에서 연속적이나 인접하지 않은 위치에 배열될 수 있다.
본 발명의 요지에 관한 실시예에서, 예를 들어, 도 3A 내지 도 3C의 인덱싱 구조 등의 인덱싱 구조는 인덱스 노드에 항목을 추가하거나 새로운 항목을 포함한 새로운 인덱스 노드를 추가함에 의해 처리 장치(102)에 의해 갱신될 수 있으므로, 인덱싱 구조 내의 새로운 항목에 대응하는 링크들은 도 3A 내지 도 3C에 도시된 바와 같이 수행된다. 즉, 인덱싱 구조에서 리프 노드가 아닌 노드에 추가된 각각의 새로운 항목은 추가된 항목의 인덱싱 값보다 작은 각자의 인덱싱 값을 갖는 하나 이상의 항목을 포함한 인덱스 노드를 가리키는(pointing) 제1 링크, 및 추가된 항목의 인덱싱 값보다 큰 각자의 인덱싱 값을 갖는 하나 이상의 항목을 포함한 인덱스 노드를 가리키는 제2 링크를 가질 수 있다. 또한, 인덱싱 구조에 새로운 인덱스 노드가 추가되면, 처리 장치(102)는 그 새로운 인덱스 노드를 가리키기 위해 인 덱싱 구조의 기존 링크들 중 적어도 하나를 갱신할 수 있다. 처리 장치(102)가 인덱싱 구조에 추가할 수 있는 각각의 새로운 항목은 각자의 인덱스 값, 및 대응하는 E-값 또는 대응하는 E-값에 대한 참조를 포함할 수 있다. 대응하는 E-값에 대한 참조가 인덱싱 구조의 항목에 저장되면, 대응하는 E-값은, 예를 들어, 테이블, 어레이 또는 다른 데이터 구조 등의 별도의 데이터 구조에 저장될 수 있다.
본 발명의 요지에 관한 실시예들에서, 예를 들어, 도 4는 도 3A 내지 도 3C의 예시적 인덱싱 구조 등의 인덱싱 구조를 이용하여 데이터베이스 내의 비-결정적으로 암호화된 데이터를 검색하는 예시적인 과정을 도시한 흐름도이다. 우선, 처리 장치(102)는 처리 장치(102)의 데이터베이스에 포함될 수 있는 원하는 데이터 항목에 대한 요청을 수신할 수 있다(단계 402). 이 요청은 예를 들어, 처리 장치(102)의 이용자 또는 애플리케이션 등의 요청자로부터, 또는 예를 들어, 네트워크(106) 등의 네트워크를 통해 처리 장치(102)와 통신할 수 있는, 예를 들어, 처리 장치(104) 등의 또 다른 처리 장치의 사용자 또는 애플리케이션 등의 요청자로부터 나올 수 있다. 이 요청은 원하는 데이터 항목을 찾는 것을 포함하는 검색 요청 또는 다른 요청일 수 있고, 원하는 데이터 항목의 평문 형태를 포함할 수 있다. 원하는 평문 데이터 항목이 주어지면, 처리 장치(102)는 요청자 모르게(transparently), 원하는 평문 데이터 항목 및 암호화 키에 기초한, 예를 들어, MAC 또는 HMAC 등의 코드일 수 있는 인덱싱 값을 계산할 수 있다(단계 404). 그 후 처리 장치(102)는 원하는 평문 데이터 항목에 대응하는 데이터의 위치를 알아내기 위한 시도에서 데이터베이스의 인덱싱 구조에 액세스하여 검색할 수 있다(단계 406). 인덱싱 구조가, 예를 들어, B-트리인 경우, 처리 장치(102)는 원하는 데이터를 찾아내기 위한 시도에서 B-트리를 횡단하기 위해 B-트리의 인덱스 노드 내의 듀플릿의 인덱스 값들을 검사할 수 있다.
다음에, 처리 장치(102)는 원하는 항목이 발견되었는가를 판정할 수 있다(단계 408). 원하는 항목을 발견하지 못했으면, 처리 장치(102)는 데이터베이스에서 원하는 데이터가 발견되지 않았음을 나타내는 표지(indication)를 반환할 수 있다.(단계 422). 아니면, 처리 장치(102)는 단계(404) 동안 계산된 인덱싱 값에 대응하는 듀플릿의 E-값을 얻을 수 있다(단계 410). 그 후, 처리 장치(102)는 E-값을 복호화여 대응하는 평문을 제공할 수 있다(단계 412). 그 후, 대응하는 평문은 단계(402) 동안 제공된 원하는 데이터 항목의 평문 형태와 비교될 수 있다(단계 414). 처리 장치(102)가 비교된 평문들이 동일한 것으로 판정하면, 데이터베이스로부터 인덱싱 구조 내에서 발견된 항목에 대응하는 데이터를 얻을 수 있으며, 이 데이터를 요청자에게 반환할 수 있다(단계 416). 즉, 인덱싱 구조에서 발견된 항목은 데이터베이스에 저장된 대응하는 데이터에 대한 참조를 포함할 수 있다. 그 후, 처리 장치(102)는 발견된 데이터 항목이 고유한지를 판정할 수 있다(단계 418). 일 구현에서, 처리 장치(102)는 발견된 데이터 항목이 데이터베이스 내의 주요 키인지에 기초하여, 또는 데이터베이스 또는 인덱싱 구조의 엔트리에 포함될 수 있는 고유 표시자, 또는 다른 기준에 기초하여, 발견된 데이터 항목이 고유한지를 판정할 수 있다. 처리 장치(102)가 데이터베이스에서 발견된 데이터 항목이 고유한 것으로 판정하면, 프로세스는 완료된다. 아니면, 처리 장치(102)는 인덱싱 값에 대응하는 다음 항목에 대해 인덱싱 구조를 검색할 수 있다(단계 420). 그 후, 처리 장치(102)는 단계(408 내지 424)를 반복할 수 있다.
단계(414) 동안 수행된 비교가 평문들이 동일하지 않은 것을 나타내면, 처리 장치(102)는 해시 충돌이 발생하였다고 판정한다. 즉, 동일한 암호화 키를 이용할 때, 서로 다른 두 평문 항목들이 동일한 인덱스 값을 생성한다. 그러한 발생 확률은 드물지만, 가능하다. 처리 장치(102)가 해시 충돌이 발생하였다고 판정하면, 처리 장치(102)는 해시 충돌을 해결하기 위해 잘 알려진 방법들 중 임의 방법을 사용할 수 있다(단계 424). 예를 들어, 일 실시예에서, 동일한 코드 또는 인덱싱 값(해시 충돌을 나타냄)을 갖는 항목들은 인덱싱 구조의 노드의 인접한 위치에 저장될 수 있다. 해시 충돌이 발생한 것으로 판정되면, 처리 장치(102)는 노드 내의 인접한 항목들을 검색하여, 그 노드 내의 인접한 항목들 중 임의의 항목이 E-값-복호될 때, 원하는 항목의 평문과 일치함-에 연관되는가를 판정한다. 일단 해시 충돌이 해결되면, 처리 장치(102)는 단계(408 내지 414)를 반복할 수 있다.
도 5는 본 발명의 요지에 관한 또 다른 실시예에서 사용될 수 있는 또 다른 예시적인 인덱싱 구조를 도시한다. 도 5는 예시적인 B-트리 인덱싱 구조를 도시하지만, 다른 실시예에서는 다른 인덱싱 구조를 사용할 수 있다. 도 5의 우측 상의 인덱싱 구조(502)의 일부는 그것이 메모리에 존재할 때 그 상태일 수 있는 인덱싱 구조(502)의 인덱스 노드를 도시한다. 메모리 내의 인덱싱 구조(502)는 평문 항목을 인덱스 값으로 이용하여 구축된 노드를 포함할 수 있다. 각 노드는 인덱스 값 또는 평문 항목, 및 다른 암호화되지 않은 데이터와 함께 평문 항목에 속하는 다른 데이터를 포함할 수 있다. 예를 들어, 메모리 내의 노드(502)는 두 항목을 포함할 수 있는데, 제1 항목은 인덱스 값으로서의 각자의 평문 항목, 평문-1, 및 제1 항목의 비암호화된 다른 정보일 수 있는 평문 항목에 관한 다른 데이터, 비암호화된 데이터-1을 포함할 수 있다. 노드(502)의 제2 항목은 인덱스 값으로서의 각자의 또 다른 평문 항목, 평문-2, 및 제2 항목의 비암호화된 다른 정보일 수 있는 평문 항목에 관한 다른 데이터, 비암호화된 데이터-2를 포함할 수 있다. 예를 들어, 인덱싱 구조가 데이터베이스에서 고용인 이름을 검색하도록 구축되어 있으면, 인덱스 값들은 고용인 이름일 수 있다. 그러한 인덱싱 구조에 대한 검색은 인덱싱 구조의 노드에서 원하는 이름이 발견될 때까지, 또는 원하는 이름이 발견되지 않을 경우에는 원하는 이름이 데이터베이스에 포함되지 않은 것으로 판정할 수 있을 때까지, 인덱싱 구조를 횡단함으로써 수행될 수 있다.
도 5의 좌측은 데이터베이스 시스템 내의 저장 장치에 저장될 때의 그 상태로의 인덱싱 구조(502)를 도시한다. 인덱싱 구조(502)의 저장된 버전은 모든 평문 참조의 암호화된 버전, 예를 들어, 노드(502)의 제1 항목의 enc-text-1 및 노드(502)의 제2 항목의 enc-text-2를 포함할 수 있다. 즉, 인덱스 값들을 포함한 모든 평문 참조는 인덱싱 구조의 조직을 변경하지 않은 채 암호화된 형태로 저장될 수 있다. 환언하자면, 인덱스 노드에서의 항목들의 순서 및 노드들 간의 연결(linkage)은 평문 인덱스 값에 따라 배열될 수 있지만, 인덱스 값을 포함한 모든 평문 참조는 암호화된 형태로 저장될 수 있다. 또한, 예를 들어, 평문 통계 자료(plaintext statistics)와 같은 인덱스에 의해 사용될 수 있는 평문 항목에 관련 된 임의 다른 정보 또한 암호화될 수 있다. 평문 항목에 관련된 정보를 포함한 인덱싱 구조에 의해 사용되는 평문 참조는 데이터베이스 내의 대응하는 데이터를 암호화하는 데 이용된 것과 동일한 키를 이용하거나, 또 다른 키에 의해, 저장된 인덱싱 구조에서 암호화될 수 있다.
도 5는 두 항목을 갖는 인덱싱 구조의 예시적인 노드를 도시한다. 다른 실시예서는, 인덱싱 구조의 노드에 더 많거나 더 적은 항목들이 저장될 수 있다.
도 6은 본 발명의 요지에 관한 실시예에서, 예를 들어, 도 5의 예시적 인덱싱 구조 등의 인덱싱 구조를 이용하여 데이터베이스 내의 비-결정적으로 암호화된 데이터를 검색하는 예시적인 프로세스를 도시하는 흐름도이다. 우선, 처리 장치(102)는 처리 장치(102)의 데이터베이스에 포함될 수 있는 원하는 데이터 항목에 대한 요청을 수신할 수 있다(단계 602). 이 요청은 예를 들어, 처리 장치(102)를 통하거나 또는 네트워크(106)와 같은 네트워크를 통해 처리 장치(104) 등의 또 다른 처리 장치를 통해, 사용자 또는 애플리케이션 등의 요청자에 의해 직접 행해질 수 있다. 이 요청은 검색 요청일 수 있으며, 원하는 평문 데이터 항목의 평문 형태를 포함할 수 있다. 다음에, 처리 장치(102)는 데이터베이스의 인덱싱 구조에 액세스하여 원하는 평문 데이터 항목에 대응하는 데이터베이스 내의 데이터에 대한 검색을 수행할 수 있다(단계 604). 그 후, 처리 장치(102)는 메모리(230) 등의 동적 저장 장치 내로 인덱싱 구조(502)의 적어도 일부를 로딩할 수 있다(단계 606). 그 후, 처리 장치(102)는 인덱싱 구조의 로딩된 부분의 암호화된 참조를 복호화할 수 있고(단계 608), 인덱싱 구조의 로딩된 부분을 이용하여 데이터베이스에서 하나 이상의 비-결정적으로 암호화된 데이터 항목을 발견하여 그것에 액세스할 수 있다(단계 610).
일 실시예에서, 처리 장치(102)는 인덱싱 구조의 암호화된 참조를 인덱스 페이지로서 복호화할 수 있으며, 인덱싱 구조의 일부가 메모리(230) 내로 로딩된다. 그러한 실시예에서, 검색은 인덱싱 구조로부터의 대응하는 평문 참조 및 다른 정보를 이용하여 수행될 수 있다. 다른 실시예에서, 인덱싱 구조로부터의 평문 참조는 검색이 수행될 때, 예를 들어, 인덱스로부터의 평문 참조를 필요로 할 때, 복호화될 수 있다.
도 6을 참조하여 상술한 예시적인 방법은 예를 들어, 동일성 검색(equality search) 등의 특정 데이터 항목에 속한 데이터에 대한 검색을 행하는 데 사용될 수 있거나, 또는 예를 들어, 범위(range) 검색 등의 데이터 값들의 범위에 속하는 데이터에 대한 검색을 행하는 데 사용될 수 있거나, 또는 예를 들어, 퍼지(fuzzy) 검색 등의 특정 데이터 항목과 유사한 정보에 대한 검색을 행하는 데 사용될 수 있다.
본 발명의 요지에 관한 실시예에서 사용될 수 있는 또 다른 예시적인 방법은 도 7을 참조하면서 기술하기로 한다. 이 방법은 해시-기반 인덱스를 지원하는 데이터베이스 시스템에서 사용될 수 있다. 도 7의 예시적인 방법에 따르면, 처리 장치(102)는 평문 항목에 관련된 데이터베이스 데이터를 찾는 검색 요청 또는 다른 요청을 수신할 수 있다(단계 702). 이 요청은 처리 장치(102)를 통하거나, 또는 네트워크(106) 등의 네트워크를 통해 처리 장치(104)와 같은 또 다른 처리 장치를 통해, 예를 들어, 사용자 또는 애플리케이션 등의 요청자에 의해 직접 행해질 수 있다. 처리 장치(102)는 암호화 키를 이용하여 평문 항목에 대해 HMAC를 계산할 수 있다(단계 704). 그 후, 처리 장치(102)는 계산된 HMAC를 해싱하여 해시 값을 생성할 수 있다(단계 706). 그 후, 처리 장치(102)는 그 해신 값을 해시-기반 인덱싱 구조(710) 내의 해시 버킷에 대한 인덱스 값으로서 사용하여 해시-기반 인덱싱 구조(710)의 인덱싱된 엔트리에 기초한 요청된 평문 데이터 항목에 관련된 정보를 얻을 수 있다.(단계 708). 해시 값은 평문 항목에 기초한 HMAC로부터 계산되므로, 해시-기반 인덱스의 해시 버킷들은 대응하는 평문 데이터 항목의 각자의 HMAC에 따라 평문 데이터 항목에 대응하는 항목에 대해 할당될 수 있다. 적어도 일부 실시예에서, 해시-기반 인덱싱 구조(710)는 요청된 평문 데이터 항목에 관련된 암호화된 정보를 갖는 데이터베이스 내의 항목으로의 링크를 포함할 수 있다. 암호화된 정보는 비-결정적으로 암호화된 데이터를 포함할 수 있다.
도 7에서 도시된 예시적인 해시-기반 인덱싱 구조 방법은 인덱스 해시 함수에 따라 해시 버킷의 배열 결과로서 발생할 수 있는 정보의 누설 가능성을 피할 수 있다.
결론
비록 본 발명의 요지를 구조적인 특징 및/또는 방법론적 단계에 특정된 언어로 기술하였지만, 첨부된 청구범위의 요지가 반드시 상술한 특정된 특징 또는 단계에만 제한되는 것은 아님은 말할 필요도 없다. 오히려, 상술한 특정된 특징 및 단계들은 청구범위를 구현하는 일례로서 기술한 것이다.
상기에서 비록 특정된 세부사항을 포함할 수 있더라도, 어째든 청구범위를 제한하려는 의도로 해석되어서는 안 된다. 상기 실시예들의 다른 구성도 본 발명의 범주의 일부이다. 또한, 본 발명의 요지에 관한 구현은 기술된 것보다 많거나 적은 단계를 가질 수 있거나, 또는 도시된 것과 다른 순서로 단계를 구현할 수 있다. 따라서, 주어진 임의 특정 예보다는, 첨부된 청구범위 및 그들의 법적 등가물만이 본 발명을 한정하는 것으로 해석되어야 한다.

Claims (20)

  1. 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법으로서,
    사용자가 모르게(transparently), 상기 사용자에 의해 제공된 원하는 평문 데이터 항목에 대한 인덱싱 값-상기 인덱싱 값은 상기 원하는 평문 데이터 항목 및 암호화 키에 적어도 일부 기초함-을 결정하는 단계(402, 404), 및
    상기 인덱싱 값을 이용하여 인덱싱 구조의 대응하는 엔트리에 액세스함으로써, 상기 원하는 평문 데이터 항목에 대응하는 비-결정적으로 암호화된 암호문을 포함한 데이터베이스 엔트리를 획득하는 단계(406, 408, 410, 412, 414, 416)
    를 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  2. 제1항에 있어서,
    상기 원하는 평문 데이터 항목에 대한 인덱싱 값을 결정하는 단계는,
    상기 원하는 평문 데이터 항목에 기초하여 메시지 인증 코드를 계산하는 단계를 더 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  3. 제1항에 있어서,
    상기 인덱싱 구조는 복수의 쌍을 이룬 데이터 항목 각각의 적어도 제1 항목을 포함하며, 상기 복수의 쌍을 이룬 데이터 항목 각각의 상기 제1 항목은 각자의 평문 데이터 항목 및 상기 암호화 키에 기초한 값을 갖는 인덱싱 데이터 항목이며, 상기 복수의 쌍을 이룬 데이터 항목 각각의 제2 항목은 상기 각자의 평문 데이터 항목에 대응하는 암호문인 것인, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  4. 제1항에 있어서,
    상기 인덱싱 구조는 복수의 쌍을 이룬 데이터 항목 각각의 적어도 제1 항목을 포함하며, 상기 복수의 쌍을 이룬 데이터 항목 각각의 상기 제1 항목은 해싱된 메시지 인증 코드 및 암호화 키를 각자의 평문 데이터 항목에 적용하는 것에 기초한 값을 갖는 인덱싱 데이터 항목이며, 상기 복수의 쌍을 이룬 데이터 항목 각각의 제2 항목은 상기 각자의 평문 데이터 항목에 대응하는 암호문인 것인, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  5. 제1항에 있어서,
    상기 인덱싱 구조는 복수의 쌍을 이룬 데이터 항목 각각의 적어도 제1 항목을 포함하며, 상기 복수의 쌍을 이룬 데이터 항목 각각의 상기 제1 항목은 해싱된 메시지 인증 코드 및 암호화 키를 각자의 평문 데이터 항목에 적용하는 것에 기초한 값을 갖는 인덱싱 데이터 항목이며, 상기 복수의 쌍을 이룬 데이터 항목 각각의 제2 항목은 상기 각자의 평문 데이터 항목에 대응하는 암호문이며, 상기 방법은,
    상기 인덱싱 값을 이용하여 상기 복수의 쌍을 이룬 데이터 항목 중 대응하는 것의 제2 항목을 획득하는 단계,
    상기 복수의 쌍을 이룬 데이터 항목 중 상기 대응하는 것의 상기 제2 항목을 복호화하는 단계, 및
    상기 복수의 쌍을 이룬 데이터 항목 중 상기 대응하는 것의 복호화된 상기 제2 항목을 상기 원하는 평문 데이터 항목과 비교하여 해시 충돌이 발생하였는가를 판정하는 단계
    를 더 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  6. 제1항에 있어서,
    상기 원하는 평문 데이터 항목에 대한 인덱싱 값을 결정하는 단계는,
    상기 암호화 키 및 상기 원하는 평문 데이터 항목에 기초하여 메시지 인증 코드를 계산하는 단계, 및
    계산된 상기 메시지 인증 코드를 해싱하여 상기 인덱싱 값을 결정하는 단계
    를 더 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  7. 제1항에 있어서,
    상기 인덱싱 구조는 대응하는 평문 데이터 항목의 해싱된 메시지 인증 코드에 따라 각자의 항목에 대해 할당된 복수의 해시 버킷(hash buckets)을 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대한 검색을 수행하는 방법.
  8. 적어도 하나의 프로세서를 위한 명령어들이 저장되어 있는 기계-판독가능 매체로서,
    상기 기계-판독가능 매체는,
    데이터베이스의 인덱싱 구조에 액세스하기 위한 명령어들(단계 604)-상기 인덱싱 구조의 항목들의 위치는 대응하는 평문 항목들에 기초하고, 상기 인덱싱 구조의 상기 대응하는 평문 항목들에 관련된 참조들(references)은 암호화되고, 상기 인덱싱 구조의 다른 정보는 비암호화됨(502)-;
    상기 인덱싱 구조의 적어도 일부를 메모리 내로 로딩시키는 명령어들(단계 606);
    상기 인덱싱 구조의 상기 적어도 일부에서의 상기 평문 항목들 중 대응하는 평문 항목에 관련된 상기 참조들 중 적어도 하나의 참조를 복호화하는 명령어들(단계 608); 및
    상기 참조들 중 복호화된 상기 적어도 하나의 참조를 이용하여 상기 데이터베이스로부터 대응하는 비-결정적으로 암호화된 데이터 항목에 액세스하는 명령어들(단계 610)
    을 포함하는, 기계-판독가능 매체.
  9. 제8항에 있어서,
    상기 인덱싱 구조의 상기 적어도 일부에서의 상기 대응하는 평문 항목에 관련된 상기 참조들 중 적어도 하나의 참조를 복호화하는 명령어들은 상기 인덱싱 구조의 페이지(a page)가 상기 메모리 내로 로딩될 때 실행되는, 기계-판독가능 매체.
  10. 제8항에 있어서,
    상기 인덱싱 구조의 상기 적어도 일부에서의 상기 대응하는 평문 항목에 관련된 상기 참조들 중 적어도 하나의 참조를 복호화하는 명령어들은, 상기 인덱싱 구조의 상기 적어도 일부를 이용하여 원하는 데이터 항목에 대응하는 상기 데이터베이스 내의 비-결정적으로 암호화된 데이터를 검색할 때 실행되는, 기계-판독가능 매체.
  11. 제8항에 있어서,
    상기 대응하는 평문 항목들에 관련된 상기 암호화된 참조들은 평문 통계 자료(plaintext statistics)를 포함하는, 기계-판독가능 매체.
  12. 제8항에 있어서,
    상기 인덱싱 구조는 B-트리를 포함하는, 기계-판독가능 매체.
  13. 제8항에 있어서,
    상기 인덱싱 구조의 상기 대응하는 평문 항목들에 관련된 상기 암호화된 참조들은 상기 데이터베이스에 저장된 비-결정적으로 암호화된 데이터 항목들을 암호화하는 데 사용된 것과 동일한 키를 사용하여 암호화되는, 기계-판독가능 매체.
  14. 제8항에 있어서,
    상기 인덱싱 구조의 상기 적어도 일부를 검색하여 원하는 범위의 데이터 항목에 대응하는 상기 데이터베이스로부터의 하나 이상의 비-결정적으로 암호화된 데이터 항목에 액세스하는 명령어들을 더 포함하는, 기계-판독가능 매체.
  15. 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법에 있어서,
    원하는 평문 데이터 항목에 대응하는 데이터베이스 엔트리를 위해 데이터베이스 시스템 내의 상기 비-결정적으로 암호화된 데이터 항목을 검색하라는 원격 요청을 네트워크를 통해 요청자로부터 수신하는 단계(402),
    상기 요청자가 모르게(transparently), 상기 원하는 평문 데이터 항목 및 암호화 키에 기초하여 코드를 계산하는 단계(404),
    상기 코드를 인덱싱 구조에 대한 인덱스로서 이용하여 상기 원하는 평문 데 이터 항목에 대응하는 상기 데이터베이스 엔트리를 획득하는 단계(406, 408, 410, 412, 414, 416), 및
    상기 요청자에게 데이터를 반환하는 단계(416)-반환된 상기 데이터는 상기 데이터베이스 시스템으로부터 획득한 상기 원하는 평문 데이터 항목에 대응하는 상기 데이터베이스 엔트리를 포함함-
    를 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법.
  16. 제15항에 있어서,
    상기 원하는 평문 데이터 항목 및 암호화 키에 기초하여 코드를 계산하는 단계는 해싱된 메시지 인증 코드를 계산하는 단계를 더 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법.
  17. 제15항에 있어서,
    상기 인덱싱 구조는 복수의 항목을 포함하며, 상기 복수의 항목 각각은 듀플릿(duplet)의 제1 항목 및 상기 듀플릿의 제2 항목을 적어도 포함하며, 상기 듀플릿의 상기 제1 항목은 대응하는 평문 데이터 항목 및 상기 암호화 키에 기초한 코드를 포함하며, 상기 듀플릿의 상기 제2 항목은 각각의 상기 평문 데이터 항목에 대응하는 비-결정적으로 암호화된 암호문을 포함하는, 데이터베이스 시스템에서 비 -결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법.
  18. 제15항에 있어서,
    상기 인덱싱 구조는 복수의 항목을 포함하며, 상기 복수의 항목 각각은 듀플릿의 제1 항목 및 상기 듀플릿의 제2 항목에 대한 참조를 적어도 포함하며, 상기 듀플릿의 상기 제1 항목은 대응하는 평문 데이터 항목 및 상기 암호화 키에 기초한 코드를 포함하며, 상기 듀플릿의 상기 제2 항목에 대한 상기 참조는 상기 듀필릿의 상기 제2 항목을 포함한 데이터 구조에 대한 포인터(pointer)를 포함하며, 상기 듀플릿의 상기 제2 항목은 각각의 상기 평문 데이터 항목에 대응하는 비-결정적으로 암호화된 암호문을 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법.
  19. 제15항에 있어서,
    상기 인덱싱 구조는 대응하는 해시 값에 따라 각각의 항목마다 할당되는 복수의 해시 버킷을 포함하며, 상기 대응하는 해시 값은 대응하는 평문 데이터 항목 및 상기 암호화 키에 기초하여 해싱된 메시지 인증 코드를 계산하고, 계산된 상기 해싱된 메시지 인증 코드를 해싱함에 의해 상기 대응하는 해시 값을 생성함으로써 결정되는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법.
  20. 제15항에 있어서,
    상기 인덱싱 구조는 B-트리를 포함하는, 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에 대해 검색을 수행하기 위한 원격 데이터베이스를 제공하는 방법.
KR1020097004699A 2006-09-06 2007-08-24 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에대한 검색을 수행하는 방법 및 이를 위한 원격 데이터베이스를 제공하는 방법, 및 기계-판독가능 매체 Active KR101403745B1 (ko)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US11/516,267 2006-09-06
US11/516,267 US7689547B2 (en) 2006-09-06 2006-09-06 Encrypted data search
PCT/US2007/076758 WO2008030717A1 (en) 2006-09-06 2007-08-24 Encrypted data search

Publications (2)

Publication Number Publication Date
KR20090048623A true KR20090048623A (ko) 2009-05-14
KR101403745B1 KR101403745B1 (ko) 2014-06-03

Family

ID=39153188

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020097004699A Active KR101403745B1 (ko) 2006-09-06 2007-08-24 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에대한 검색을 수행하는 방법 및 이를 위한 원격 데이터베이스를 제공하는 방법, 및 기계-판독가능 매체

Country Status (7)

Country Link
US (1) US7689547B2 (ko)
EP (1) EP2064638B1 (ko)
JP (1) JP4810611B2 (ko)
KR (1) KR101403745B1 (ko)
CN (1) CN101512525B (ko)
TW (1) TWI372345B (ko)
WO (1) WO2008030717A1 (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101703828B1 (ko) * 2015-10-15 2017-02-08 한국전자통신연구원 암호화된 데이터에 대한 색인 태그 생성 방법, 색인 태그를 이용한 암호화된 데이터 검색 방법 및 이를 위한 데이터베이스 장치

Families Citing this family (40)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8661263B2 (en) 2006-09-29 2014-02-25 Protegrity Corporation Meta-complete data storage
US7809142B2 (en) * 2007-06-19 2010-10-05 International Business Machines Corporation Data scrambling and encryption of database tables
US10262136B1 (en) * 2008-08-04 2019-04-16 Zscaler, Inc. Cloud-based malware detection
CN101770462A (zh) * 2008-12-30 2010-07-07 日电（中国）有限公司 用于密文索引和检索的装置和方法
CN101788985B (zh) * 2009-01-23 2013-01-23 日电（中国）有限公司 对加密倒排索引表进行k匿名更新的方法和装置
US8819451B2 (en) * 2009-05-28 2014-08-26 Microsoft Corporation Techniques for representing keywords in an encrypted search index to prevent histogram-based attacks
JP5411034B2 (ja) * 2010-03-19 2014-02-12 株式会社日立ソリューションズ データベース暗号化システム及び方法
US8533489B2 (en) * 2010-09-29 2013-09-10 Microsoft Corporation Searchable symmetric encryption with dynamic updating
WO2012081450A1 (ja) * 2010-12-13 2012-06-21 日本電気株式会社 暗号化データベース管理システム、クライアントおよびサーバ、自然結合方法およびプログラム
EP2738689A4 (en) 2011-07-29 2015-04-29 Nec Corp SYSTEM FOR GENERATING A DISPLAY OF INFORMATION RESISTANT INDEX, INDEX GENERATING DEVICE AND METHOD THEREFOR
US8832427B2 (en) 2012-03-30 2014-09-09 Microsoft Corporation Range-based queries for searchable symmetric encryption
WO2014028524A1 (en) * 2012-08-15 2014-02-20 Visa International Service Association Searchable encrypted data
US8943331B2 (en) * 2012-12-28 2015-01-27 Alcatel Lucent Privacy-preserving database system
US20140330836A1 (en) * 2013-05-06 2014-11-06 Thomson Reuters (Markets) Llc Offline searching of encrypted content
US9553867B2 (en) 2013-08-01 2017-01-24 Bitglass, Inc. Secure application access system
US10122714B2 (en) 2013-08-01 2018-11-06 Bitglass, Inc. Secure user credential access system
US9552492B2 (en) * 2013-08-01 2017-01-24 Bitglass, Inc. Secure application access system
US9852306B2 (en) 2013-08-05 2017-12-26 International Business Machines Corporation Conjunctive search in encrypted data
US9646166B2 (en) 2013-08-05 2017-05-09 International Business Machines Corporation Masking query data access pattern in encrypted data
CN104462990B (zh) * 2013-09-13 2019-02-26 腾讯科技（深圳）有限公司 字符串加解密方法和装置
US20170262546A1 (en) * 2014-07-30 2017-09-14 Hewlett Packard Enterprise Development Lp Key search token for encrypted data
US10853515B2 (en) 2014-09-15 2020-12-01 Salesforce.Com, Inc. Secure storage and access to sensitive data
US10013440B1 (en) * 2014-10-31 2018-07-03 Amazon Technologies, Inc. Incremental out-of-place updates for index structures
CN104572827B (zh) * 2014-12-08 2017-12-15 北京工业大学 一种基于跨明文与密文的混合搜索系统
JP6441160B2 (ja) 2015-04-27 2018-12-19 株式会社東芝 秘匿化装置、復号装置、秘匿化方法および復号方法
EP3292505A4 (en) * 2015-05-07 2018-06-13 Zerodb, Inc. Zero-knowledge databases
WO2017193108A2 (en) 2016-05-06 2017-11-09 ZeroDB, Inc. Encryption for distributed storage and processing
CN109983456B (zh) * 2016-09-22 2023-08-15 维萨国际服务协会 存储器内密钥范围搜索方法和系统
US10482279B2 (en) * 2016-11-08 2019-11-19 Microsoft Technology Licensing, Llc Pattern-less private data detection on data sets
US10360390B2 (en) * 2016-12-14 2019-07-23 Sap Se Oblivious order-preserving encryption
PT3388969T (pt) 2017-04-13 2020-01-16 Dswiss Ag Sistema de pesquisa
JP6632780B2 (ja) * 2017-09-12 2020-01-22 三菱電機株式会社 データ処理装置、データ処理方法及びデータ処理プログラム
CN110858251B (zh) * 2018-08-22 2020-07-21 阿里巴巴集团控股有限公司 数据查询方法和装置
US10783270B2 (en) 2018-08-30 2020-09-22 Netskope, Inc. Methods and systems for securing and retrieving sensitive data using indexable databases
US11003783B1 (en) * 2018-09-21 2021-05-11 Amazon Technologies, Inc. Searchable encrypted data stores
CA3126089C (en) 2019-03-01 2023-06-20 Cyborg Inc. System and method for statistics-based pattern searching of compressed data and encrypted data
EP4154147B1 (en) * 2020-06-29 2025-09-24 Huawei Technologies Co., Ltd. Data storage server and client devices for securely storing data
CN112182616B (zh) * 2020-09-29 2024-05-17 江苏大周基业智能科技有限公司 核心表数据的密码技术安全控制方法及系统
TWI835039B (zh) * 2021-06-16 2024-03-11 威聯通科技股份有限公司 索引節點配置方法、資料處理裝置與電腦可讀媒介
US12267420B2 (en) * 2022-12-09 2025-04-01 Yuen Ping Lee Systems and methods for programmable corporate policies and management intervention

Family Cites Families (45)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4827508A (en) * 1986-10-14 1989-05-02 Personal Library Software, Inc. Database usage metering and protection system and method
CA2000006C (en) * 1989-01-23 1994-07-12 Walter W. Chang Combinatorial signatures for data encoding and searching
US5293576A (en) * 1991-11-21 1994-03-08 Motorola, Inc. Command authentication process
US5475826A (en) 1993-11-19 1995-12-12 Fischer; Addison M. Method for protecting a volatile file using a single hash
JP3339688B2 (ja) * 1993-12-01 2002-10-28 アールピーケイ ニュージーランド リミテッド 非決定論的ミクスチャー発生器ストリーム暗号化システム
US5495533A (en) 1994-04-29 1996-02-27 International Business Machines Corporation Personal key archive
WO1996025801A1 (en) * 1995-02-17 1996-08-22 Trustus Pty. Ltd. Method for partitioning a block of data into subblocks and for storing and communicating such subblocks
US5742807A (en) * 1995-05-31 1998-04-21 Xerox Corporation Indexing system using one-way hash for document service
US5701469A (en) * 1995-06-07 1997-12-23 Microsoft Corporation Method and system for generating accurate search results using a content-index
JP3647940B2 (ja) * 1995-09-22 2005-05-18 富士通株式会社 データ管理装置
US5854916A (en) * 1995-09-28 1998-12-29 Symantec Corporation State-based cache for antivirus software
US5864852A (en) * 1996-04-26 1999-01-26 Netscape Communications Corporation Proxy server caching mechanism that provides a file directory structure and a mapping mechanism within the file directory structure
US5692124A (en) 1996-08-30 1997-11-25 Itt Industries, Inc. Support of limited write downs through trustworthy predictions in multilevel security of computer network communications
JP3022405B2 (ja) * 1997-06-03 2000-03-21 日本電気株式会社 画像メモリ制御装置
US6052686A (en) 1997-07-11 2000-04-18 At&T Corporation Database processing using schemas
US6012057A (en) * 1997-07-30 2000-01-04 Quarterdeck Corporation High speed data searching for information in a computer system
JP3056704B2 (ja) * 1997-08-25 2000-06-26 三菱電機株式会社 データ管理装置
US6233685B1 (en) 1997-08-29 2001-05-15 Sean William Smith Establishing and employing the provable untampered state of a device
JPH11143780A (ja) * 1997-11-05 1999-05-28 Hitachi Ltd データベースにおける秘密情報管理方法およびデータベースの秘密情報管理装置
AU2085199A (en) * 1997-11-19 1999-06-07 Security Dynamics Technologies, Inc. Digital coin tracing using trustee tokens
JP3849279B2 (ja) * 1998-01-23 2006-11-22 富士ゼロックス株式会社 インデクス作成方法および検索方法
JP3457184B2 (ja) * 1998-06-25 2003-10-14 シャープ株式会社 検索装置及びその制御プログラムを記憶した媒体
US7152165B1 (en) 1999-07-16 2006-12-19 Intertrust Technologies Corp. Trusted storage systems and methods
US6601026B2 (en) 1999-09-17 2003-07-29 Discern Communications, Inc. Information retrieval by natural language querying
US20010042099A1 (en) * 2000-02-02 2001-11-15 Doongo Technologies, Inc. Apparatus and methods for optimizing traffic volume in wireless email communications
US7412462B2 (en) * 2000-02-18 2008-08-12 Burnside Acquisition, Llc Data repository and method for promoting network storage of data
US7043641B1 (en) * 2000-03-08 2006-05-09 Igt Encryption in a secure computerized gaming system
US6968456B1 (en) 2000-08-08 2005-11-22 Novell, Inc. Method and system for providing a tamper-proof storage of an audit trail in a database
US7362868B2 (en) 2000-10-20 2008-04-22 Eruces, Inc. Hidden link dynamic key manager for use in computer systems with database structure for storage of encrypted data and method for storage and retrieval of encrypted data
US6928428B1 (en) * 2000-11-27 2005-08-09 Microsoft Corporation Distributed confidential contextual querying
WO2002056181A2 (en) * 2001-01-11 2002-07-18 Force Communications Inc Z File switch and switched file system
AU2002234258A1 (en) 2001-01-22 2002-07-30 Sun Microsystems, Inc. Peer-to-peer network computing platform
US7360075B2 (en) * 2001-02-12 2008-04-15 Aventail Corporation, A Wholly Owned Subsidiary Of Sonicwall, Inc. Method and apparatus for providing secure streaming data transmission facilities using unreliable protocols
US7062490B2 (en) * 2001-03-26 2006-06-13 Microsoft Corporation Serverless distributed file system
GB2377514B (en) * 2001-07-05 2005-04-27 Hewlett Packard Co Document encryption
US7266699B2 (en) 2001-08-30 2007-09-04 Application Security, Inc. Cryptographic infrastructure for encrypting a database
US7269729B2 (en) 2001-12-28 2007-09-11 International Business Machines Corporation Relational database management encryption system
US20030159054A1 (en) * 2002-02-19 2003-08-21 Minebea Co. Reconfigurable secure input device
US7287033B2 (en) * 2002-03-06 2007-10-23 Ori Software Development, Ltd. Efficient traversals over hierarchical data and indexing semistructured data
JP4077329B2 (ja) * 2003-01-31 2008-04-16 株式会社東芝 トランザクション処理システム、並行制御方法及びプログラム
US20030177115A1 (en) * 2003-02-21 2003-09-18 Stern Yonatan P. System and method for automatic preparation and searching of scanned documents
US20050004924A1 (en) * 2003-04-29 2005-01-06 Adrian Baldwin Control of access to databases
US10339336B2 (en) 2003-06-11 2019-07-02 Oracle International Corporation Method and apparatus for encrypting database columns
US7743069B2 (en) 2004-09-03 2010-06-22 Sybase, Inc. Database system providing SQL extensions for automated encryption and decryption of column data
US7571490B2 (en) 2004-11-01 2009-08-04 Oracle International Corporation Method and apparatus for protecting data from unauthorized modification

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101703828B1 (ko) * 2015-10-15 2017-02-08 한국전자통신연구원 암호화된 데이터에 대한 색인 태그 생성 방법, 색인 태그를 이용한 암호화된 데이터 검색 방법 및 이를 위한 데이터베이스 장치

Also Published As

Publication number Publication date
JP2010503118A (ja) 2010-01-28
TWI372345B (en) 2012-09-11
JP4810611B2 (ja) 2011-11-09
US20080059414A1 (en) 2008-03-06
WO2008030717A1 (en) 2008-03-13
EP2064638A4 (en) 2016-05-04
CN101512525B (zh) 2012-10-03
TW200817949A (en) 2008-04-16
US7689547B2 (en) 2010-03-30
CN101512525A (zh) 2009-08-19
EP2064638B1 (en) 2019-03-27
EP2064638A1 (en) 2009-06-03
KR101403745B1 (ko) 2014-06-03

Similar Documents

Publication Publication Date Title
KR101403745B1 (ko) 데이터베이스 시스템에서 비-결정적으로 암호화된 데이터에대한 검색을 수행하는 방법 및 이를 위한 원격 데이터베이스를 제공하는 방법, 및 기계-판독가능 매체
JP5156751B2 (ja) レンジド・ルックアップ
US10985902B2 (en) Dynamic symmetric searchable encryption
US7519835B2 (en) Encrypted table indexes and searching encrypted tables
US9720943B2 (en) Columnar table data protection
US20180294952A1 (en) Method for operating a distributed key-value store
JP6449093B2 (ja) 秘匿化データベースシステム及び秘匿化データ管理方法
US7930560B2 (en) Personal information management system, personal information management program, and personal information protecting method
JP5429502B2 (ja) 範囲検索システム、範囲検索方法、及び範囲検索用プログラム
Wiese et al. CloudDBGuard: A framework for encrypted data storage in NoSQL wide column stores
Fu et al. A privacy-preserving fuzzy search scheme supporting logic query over encrypted cloud data
US20200210595A1 (en) CryptoJSON Indexed Search Systems and Methods
WO2024130721A1 (en) Data storage server and client devices for securely storing and retrieving data
US11669506B2 (en) Searchable encryption
Zhang et al. Secure multi-keyword fuzzy search supporting logic query over encrypted cloud data
Jang et al. An effective queries execution algorithm on the encrypted database
CN115687535A (zh) 关系型数据库的管理方法及装置

Legal Events

Date Code Title Description
PA0105 International application

Patent event date: 20090305

Patent event code: PA01051R01D

Comment text: International Patent Application

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20120810

Comment text: Request for Examination of Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20130912

Patent event code: PE09021S01D

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

Patent event code: PE07011S01D

Comment text: Decision to Grant Registration

Patent event date: 20140306

GRNT Written decision to grant
PR0701 Registration of establishment

Comment text: Registration of Establishment

Patent event date: 20140528

Patent event code: PR07011E01D

PR1002 Payment of registration fee

Payment date: 20140528

End annual number: 3

Start annual number: 1

PG1601 Publication of registration
FPAY Annual fee payment

Payment date: 20170504

Year of fee payment: 4

PR1001 Payment of annual fee

Payment date: 20170504

Start annual number: 4

End annual number: 4

FPAY Annual fee payment

Payment date: 20180427

Year of fee payment: 5

PR1001 Payment of annual fee

Payment date: 20180427

Start annual number: 5

End annual number: 5

PR1001 Payment of annual fee

Payment date: 20210428

Start annual number: 8

End annual number: 8

PR1001 Payment of annual fee

Payment date: 20240424

Start annual number: 11

End annual number: 11