[논문]프라이버시 보존 분류 방법 동향 분석

김평; 문수빈; 조은지; 이윤호

프라이버시 보존 분류 방법 동향 분석 원문보기

情報保護學會誌 = KIISC review, v.27 no.3, 2017년, pp.33 - 41

김평 (서울과학기술대학교 ITM 전공) , 문수빈 (서울과학기술대학교 SW분석설계학과) , 조은지 (서울과학기술대학교 SW분석설계학과) , 이윤호 (서울과학기술대학교 ITM 전공)

초록
AI-Helper

기계 학습(machine-learning) 분야의 분류 알고리즘(classification algorithms)은 의료 진단, 유전자 정보 해석, 스팸 탐지, 얼굴 인식 및 신용 평가와 같은 다양한 응용 서비스에서 사용되고 있다. 이와 같은 응용 서비스에서의 분류 알고리즘은 사용자의 민감한 정보를 포함하는 데이터를 이용하여 학습을 수행하는 경우가 많으며, 분류 결과도 사용자의 프라이버시와 연관된 경우가 많다. 따라서 학습에 필요한 데이터의 소유자, 응용 서비스 사용자, 그리고 서비스 제공자가 서로 다른 보안 도메인에 존재할 경우, 프라이버시 보호 문제가 발생할 수 있다. 본 논문에서는 이러한 문제를 해결하면서도 분류 서비스를 제공할 수 있도록 도와주는 프라이버시 보존 분류 프로토콜(privacy-preserving classification protocol: PPCP) 에 대해 소개한다. 구체적으로 PPCP의 프라이버시 보호 요구사항을 분석하고, 기존의 연구들이 프라이버시 보호를 위해 사용하는 암호학적 기본 도구(cryptographic primitive)들에 대해 소개한다. 최종적으로 그러한 암호학적 기본 도구를 사용하여 설계된 프라이버시 보존 분류 프로토콜에 대한 기존 연구들을 소개하고 분석한다.

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

분류 알고리즘은 중요한 기계 학습 기술 중 하나이며, 분류 알고리즘에 대한 프라이버시 보호는 실제 사용자 데이터뿐만 아니라 분류의 기준이 되는 모델의 보호를 수행한다는 측면에서 향후 분류 방법을 포함하는 기계 학습 방법들의 사용 활성화를 위해 중요한 역할을 수행할 것으로 예상된다. 본 논문은 프라이버시 보존 분류 방법을 실현하기 위해 활용 가능한 암호학적 기본도구들과 이를 직접 적용한 프라이버시 보존 분류 방법들에 대한 조사를 수행하고, 다양한 측면에서 비교 분석을 수행하였다. 본 논문의 내용은 향후 본 분야를 공부하고자 하는 사람들에게 많은 도움이 되기를 희망한다.
본 절에서는 이전 절에서 설명한 암호학적 도구를 사용하여 제안된 프라이버시 보존 분류 방법들에 대해서 다룬다.
본 절에서는 프라이버시 보호 기반 분류 기술을 구현하기 위해 사용되는 암호기법적인 도구에 대해 정리한다. 데이터 프라이버시를 보호를 위해 데이터를 암호화했을 때, 분류 알고리즘을 수행하기 위해 필요한 암호문들에 대해 연산 방법들을 제공하는 기술들이 이에 해당한다.
기존의 프라이버시 보호 기반 기계 학습 연구들은 모델을 추출하는 학습 단계에서 사용되는 데이터의 프라이버시 보호에 초점을 두고 이루어져 왔으며, 사용자 입력 및 예측 결과에 대한 프라이버시의 고려에 미비점이 존재해왔다. 분류 기술에서 프라이버시 문제의 구체적인 정의는 R. Bost 등의 연구[5]에서 처음 이루어졌으며, 본 논문은 이와 같은 프라이버시 요건을 기준으로 분류알고리즘과 이를 위한 암호기법적인 기반 기술에 대해 조사 분석한다.

제안 방법

의 연구[20]는 가산 연산을 지원하는 동형암호와 OT의 방법론을 사용하는 의사결정트리 및 난수 숲(Random Forest) 분류 알고리즘의 실현 방법을 제안하였다. 본 방법에서는 DGK 프로토콜에서의 비트단위 비교를 위한 계산을 OT에서 트리 평가에 대한 값들 중 1개를 선택하기 위한 값으로 사용한다.
Graepel 등의 연구[21] 에서는 부트스트래핑이 필요하지 않는 범위 안에서만 완전동형암호를 활용¹⁾하여 실질적으로 제한된 연산만이 가능한 상황에서 선형평균(Linear means), Fisher’s 선형판별(Fisher's linear discriminant) 알고리즘을 구현하였다. 본 연구에서는 모델에 대한 학습 단계도 포함하여 다루고 있으며, 연산 과정에서 사용자 입력에 대한 어떠한 값도 서버에 노출되지 않고, 1 라운드의 통신으로 분류가 가능한 특징이 있다. 그러나 가용 연산 능력의 제한으로 인해 분류 결과 값을 결정하기 위한 최종 비교 연산을 복호화 후 사용자에게 직접 하도록 요구하고 있으며, 이를 위해 사용자에게 모델을 사용한 연산 값의 범위와 대응되는 분류 결과에 대한 정보가 제공된다.
본 절에서는 III절에서 기술한 다양한 프라이버시 보존 분류 방법들을 정리하고 비교한다. 표 1은 사용하는 프라이버시 보존 분류 방법과 사용하는 암호학적 기본도구에 대한 비교이다.
David 등은 편의성 기반 암호기법을 사용하여 Naïve Bayes 분류 알고리즘과 Hyper-plane 분류 알고리즘을 구현하였다[25]. 해당 연구에서는 DGK 프로토콜을 편의성 기반 암호기법으로 구현하였다. DGK 프로토콜에서는 2가지 비완전동형암호가 요구되지만, 편의성 기반 암호기법은 프로토콜에서 참여자들의 모든 데이터는 식 (5)와 같이 안전하게 공유된 형태이기 때문에 별도의 암호학적인 도구가 필요하지 않다.
이에 대한 해결 방법으로 안전한 양자간 연산에서 사용되는 가블드 회로의 미세조정을 통해 분류 알고리즘에 최적화 시키는 형태의 연구[16]가 존재한다. 해당 연구에서는 ECG (Electro-Cardio-Gram)의 해석을 위한 브랜칭 프로그램(Branching Program)을 제안하고 있으며, 이 브랜칭 프로그램은 의사결정트리 분류 알고리즘(Decision Tree Classifier)으로 확장 가능하다.

이론/모형

해당 연구는 비교 연산의 경우, DGK 프로토콜과 비슷한 방법을 사용하지만, 비트 비교의 효율성을 위한 별도의 동형암호를 사용하지 않는다. 그리고 곱셈 연산을 수행하기 위해 Y. Elmehdwi 등의 연구[19]에서 제안된 프로토콜을 사용하였다.
본 논문에서는 프라이버시 보존 기계 학습에서의 한 종류인 프라이버시 보존 분류(Privacy-preserving Classification) 기법에 초점을 둔다. 데이터 분류에서는 이미 분류 결과가 기록되어 있는 다양한 샘플 데이터, 즉 학습 데이터를 바탕으로 분류 알고리즘에 사용되는 모델의 수립을 위한 학습 단계와 학습된 모델을 이용하여, 분류를 원하는 주체가 제공한 데이터들을 이용하여 분류 알고리즘을 수행, 해당 데이터에 대한 분류 결과를 얻는 예측 단계로 나누어진다.
Bost 등의 연구[5]는 분류 알고리즘에서 많이 사용되는 연산을 안전한 프로토콜의 구성 블록 형태로 설계하고, 이를 사용하여 프라이버시 보존 분류프로토콜을 구현할 수 있음을 Naïve Bayes 분류, Hyper-plane 분류, 의사결정트리 분류 알고리즘에 대해 보였다. 비교 연산은 DGK 프로토콜을 개선한 연구[20]의 방식을 차용하였으며, 곱셈 연산은 (7)의 방법, 그리고 의사결정트리 분류 알고리즘에서 트리 평가(evaluation)는 완전 동형암호를 사용하였다.

성능/효과

Bost등의 연구[5]에서는 검증을 위해 많이 사용되는 안전한 양자간 연산 프로토콜인 TASTY[7]와 Failplay[8]를 사용하여 Naïve Bayes 분류 알고리즘을 구현하였다. 성능 평가 결과, 3종류의 값만을 가지는 입력 x에 대하여 256GB 이상의 시스템 메모리가 필요하다는 것을 확인하였다. 또한 안전한 양자간 연산의 성능에 대해 분석한 연구[15]에서는 4GB 이내의 제한된 메모리를 사용할 경우 간단한 가산 연산 및 최소값의 인덱스를 찾는 연산이 실패할 확률이 TASTY에서는 71.

후속연구

본 논문은 프라이버시 보존 분류 방법을 실현하기 위해 활용 가능한 암호학적 기본도구들과 이를 직접 적용한 프라이버시 보존 분류 방법들에 대한 조사를 수행하고, 다양한 측면에서 비교 분석을 수행하였다. 본 논문의 내용은 향후 본 분야를 공부하고자 하는 사람들에게 많은 도움이 되기를 희망한다.
DGK 프로토콜에서는 2가지 비완전동형암호가 요구되지만, 편의성 기반 암호기법은 프로토콜에서 참여자들의 모든 데이터는 식 (5)와 같이 안전하게 공유된 형태이기 때문에 별도의 암호학적인 도구가 필요하지 않다. 이와는별도로, 후속 연구에서는 프로토콜의 최적화 및 기능의 추가를 통해 의사결정트리 분류 알고리즘, SVM(Support Vector Machine), 로지스틱 회귀(Logistic Regression) 분류 알고리즘을 제안하였다[29].

질의응답

핵심어	질문	논문에서 추출한 답변
	안전한 양자간 연산의 목표는 무엇인가?	안전한 양자간 연산의 목표는 상대방과 입력 값을 공유하지 않고 두 당사자가 입력 내용에 대한 임의의 함수를 공동으로 계산할 수 있도록 하는 것이다. 프라이버시 보존 분류 알고리즘 또한 서버는 모델 w를, 또한 클라이언트는 x를 공개하지 않고 분류 알고리즘 Cw을 수행한다는 측면에서 안전한 양자 간 연산에 포함된다고 볼 수 있다.
	분류 알고리즘은 어떻게 사용되고 있는가?	기계 학습(machine-learning) 분야의 분류 알고리즘(classification algorithms)은 의료 진단, 유전자 정보 해석, 스팸 탐지, 얼굴 인식 및 신용 평가와 같은 다양한 응용 서비스에서 사용되고 있다. 이와 같은 응용 서비스에서의 분류 알고리즘은 사용자의 민감한 정보를 포함하는 데이터를 이용하여 학습을 수행하는 경우가 많으며, 분류 결과도 사용자의 프라이버시와 연관된 경우가 많다.
	응용 서비스에서의 분류 알고리즘은 사용자의 민감한 정보를 포함하는 데이터를 이용하여 학습을 수행하는 경우가 많으며, 분류 결과도 사용자의 프라이버시와 연관된 경우가 많기 때문에 어떤 문제가 발생할 수 있는가?	이와 같은 응용 서비스에서의 분류 알고리즘은 사용자의 민감한 정보를 포함하는 데이터를 이용하여 학습을 수행하는 경우가 많으며, 분류 결과도 사용자의 프라이버시와 연관된 경우가 많다. 따라서 학습에 필요한 데이터의 소유자, 응용 서비스 사용자, 그리고 서비스 제공자가 서로 다른 보안 도메인에 존재할 경우, 프라이버시 보호 문제가 발생할 수 있다. 본 논문에서는 이러한 문제를 해결하면서도 분류 서비스를 제공할 수 있도록 도와주는 프라이버시 보존 분류 프로토콜(privacy-preserving classification protocol: PPCP) 에 대해 소개한다.

참고문헌 (26)

J. Wiens, J. Guttag, E. Horvitz, "Learning evolving patient risk processes for c. diff colonization," ICML Workshop on Machine Learning from Clinical Data, 2012.
A. Singh, J.Guttag, "A comparison of non-symmetric entropy-based classificat- ion trees and support vector machine for cardiovascular risk stratification," Annual International Conference of the IEEE Engineering in Medicine and Biology Society, pp. 79-82, 2011.
A. Singh, G. Nadkarni, J. Guttag, E. Bottinger, "Leveraging hierarchy in medical codes for predictive modeling," Proceedings of the 5th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics. ACM, pp. 96-103, 2014.
C. Aggarwal, S. Philip, "A general survey of privacy-preserving data mining models and algorithms," Privacy-preserving data mining, Springer US, pp. 11-52, 2008.
R. Bost, R. Popa, S. Tu, S. Goldwasser, "Machine Learning Classification over Encrypted Data," NDSS, 2015.
A. Yao, "Protocols for secure computations," Annual Symposium on Foundations of Computer Science, IEEE, pp. 160-164, 1982.
W. Henecka, A. Sadeghi, T. Schneider, I. Wehrenberg, "TASTY: tool for automating secure two-party computations," Proceedings of the 17th ACM conference on Computer and communications security, ACM, pp. 451-462, 2010.
D Malkhi, N Nisan, B Pinkas, Y Sella, "Fairplay-Secure Two-Party Computation System." USENIX Security Symposium, 4, 2004.
P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes," International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, pp. 223-238, 1999.
S. Goldwasser, S. Micali. "Probabilistic encryption & how to play mental poker keeping secret all partial information," Proceedings of the fourteenth annual ACM symposium on Theory of computing, ACM, pp. 365-377, 1982.
I. Damgard, M. Geisler, M. Kroigard. "A correction to'efficient and secure comparison for on-line auctions'," International Journal of Applied Cryptography, 1(4), pp. 323-324, 2009.

상세보기
C. Gentry, "Fully homomorphic encryption using ideal lattices," STOC. Vol. 9. pp. 169-178, 2009.

상세보기
D. Beaver, "Commodity-based cryptography," Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, ACM, pp. 446-455, 1997.
G. Asharov, Y. Lindell, T. Schneider, M. Zohner, "More efficient oblivious transfer and extensions for faster secure computation," Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, ACM, pp. 535-548, 2013.
J. Ziegeldorf, J. Metzke, M. Henze, K. Wehrle, "Choose wisely: a comparison of secure two-party computation frameworks," Security and Privacy Workshops, IEEE, pp. 198-205, 2015.
M. Barni, P. Failla, R. Lazzeretti, A. Paus, A. Sadeghi, T. Schneider, V. Kolesnikov, "Efficient privacy-preserving classification of ECG signals," First IEEE International Workshop on Information Forensics and Security, IEEE, pp. 91-95, 2009.
T. Veugen, "Improving the DGK comparison protocol," International Workshop on Information Forensics and Security, IEEE, pp. 49-54, 2012.
X. Liu, R. Lu, J. Ma, L. Chen, B. Qin, "Privacy-preserving patient-centric clinical decision support system on naive Bayesian classification," IEEE journal of biomedical and health informatics 20(2), pp. 655-668, 2016.

상세보기
Y. Elmehdwi, B. Samanthula, W. Jiang, "K-nearest neighbor classification over semantically secure encrypted relational data," IEEE transactions on Knowledge and data engineering, 27(5), pp. 1261-1273, 2015.

상세보기
D. Wu, T. Feng, M. Naehrig, K. Lauter, "Privately evaluating decision trees and random forests," Proceedings on Privacy Enhancing Technologies, 4, pp. 335-355, 2016.
T. Graepel, K. Lauter, M. Naehrig, "ML confidential: Machine learning on encrypted data," International Conference on Information Security and Cryptology, Springer Berlin Heidelberg, pp. 1-21, 2012.
J. Bos, K. Lauter, M. Naehrig, "Private predictive analysis on encrypted medical data," Journal of biomedical informatics, 50, pp. 234-243, 2014.

상세보기
A. Khedr, G. Gulak, V. Vaikuntanathan, "SHIELD: scalable homomorphic implementation of encrypted data-classifiers," IEEE Transactions on Computers, 65(9), pp. 2848-2858, 2016.

상세보기
W. Lu, S. Kawasaki, J. Sakuma, "Using Fully Homomorphic Encryption for Statistical Analysis of Categorical, Ordinal and Numerical Data," 2017.
B. David, R. Dowsley, R. Katti, A. Nascimento, "Efficient unconditionally secure comparison and privacy preserving machine learning classification protocols," International Conference on Provable Security. Springer International Publishing, pp. 354-367, 2015.
M. Cock, R. Dowsley, C. Horst, R. Katti, A. Nascimento, W. Poon, S. Truex, "Efficient and Private Scoring of Decision Trees, Support Vector Machines and Logistic Regression Models based on Pre-Computation," IEEE Transactions on Dependable and Secure Computing, DOI: 10.1109/TDSC.2017.2679189, 2017.

상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증