싸이월드, 페이스북과 같은 소셜 네트워킹 서비스는 개인적인 데이터를 지인들과 공유하는데 매우 유용하다. 이들은 대부분 중앙 집중형 서버를 기반으로 하는데, 이 같은 시스템은 사용자들의 모든 통신 내역이 서버에게 노출된다는 단점을 가진다. 이러한 문제점을 개선하기 위해서 p2p 시스템에 착안한 분산된 소셜 네트워킹 서비스와 그 안에서 타인의 데이터에 접근하는 것을 제어하는 연구가 진행 중이다. 기존의 접근제어 기법에서는 신뢰하는 제 3기관이 필요하거나 프로토콜에 참여하는 모든 사용자들이 온라인 상태여야 하고, 사용자들이 분산된 방식으로 구축한 소셜 네트워크가 서버에게 노출되는 단점이 존재했다. M. Atallah 등은 처음으로 암호학적인 키 관리 기법을 활용해서 기존의 기법들이 지닌 문제점을 모두 해결했지만, 제안된 기법이 매우 비효율적이라는 한계가 있었다. 본 논문에서는 이 기법이 가진 비효율을 분석하고, 키 관리 기법이 아닌 대칭키 기반의 환형(circular) 암호를 최초로 적용하여 효율적인 접근제어 기법을 제안한다. 제안하는 기법은 온라인 상에 구축된 소셜 네트워크를 통해서 사용자 데이터에 대한 접근을 분산된 방식으로 제어하고, 서버가 그 네트워크를 추론할 수 없도록 기존의 기법보다 향상된 효율성과 안전성을 제공한다.
싸이월드, 페이스북과 같은 소셜 네트워킹 서비스는 개인적인 데이터를 지인들과 공유하는데 매우 유용하다. 이들은 대부분 중앙 집중형 서버를 기반으로 하는데, 이 같은 시스템은 사용자들의 모든 통신 내역이 서버에게 노출된다는 단점을 가진다. 이러한 문제점을 개선하기 위해서 p2p 시스템에 착안한 분산된 소셜 네트워킹 서비스와 그 안에서 타인의 데이터에 접근하는 것을 제어하는 연구가 진행 중이다. 기존의 접근제어 기법에서는 신뢰하는 제 3기관이 필요하거나 프로토콜에 참여하는 모든 사용자들이 온라인 상태여야 하고, 사용자들이 분산된 방식으로 구축한 소셜 네트워크가 서버에게 노출되는 단점이 존재했다. M. Atallah 등은 처음으로 암호학적인 키 관리 기법을 활용해서 기존의 기법들이 지닌 문제점을 모두 해결했지만, 제안된 기법이 매우 비효율적이라는 한계가 있었다. 본 논문에서는 이 기법이 가진 비효율을 분석하고, 키 관리 기법이 아닌 대칭키 기반의 환형(circular) 암호를 최초로 적용하여 효율적인 접근제어 기법을 제안한다. 제안하는 기법은 온라인 상에 구축된 소셜 네트워크를 통해서 사용자 데이터에 대한 접근을 분산된 방식으로 제어하고, 서버가 그 네트워크를 추론할 수 없도록 기존의 기법보다 향상된 효율성과 안전성을 제공한다.
Because people usually establish their online social network based on their offline relationship, the social networks (i.e., the graph of friendship relationships) are often used to share contents. Mobile devices let it easier in these days, but it also increases the privacy risk such as access cont...
Because people usually establish their online social network based on their offline relationship, the social networks (i.e., the graph of friendship relationships) are often used to share contents. Mobile devices let it easier in these days, but it also increases the privacy risk such as access control of shared data and relationship exposure to untrusted server. To control the access on encrypted data and protect relationship from the server, M. Atallah et al. proposed a hop-based scheme in 2009. Their scheme assumed a distributed environment such as p2p, and each user in it shares encrypted data on their social network. On the other hand, it is very inefficient to keep their relationship private, so we propose an improved scheme. In this paper, among encrypted contents and relationships, some authenticated users can only access the data in distributed way. For this, we adopt 'circular-secure symmetric encryption' first. Proposed scheme guarantees the improved security and efficiency compared to the previous work.
Because people usually establish their online social network based on their offline relationship, the social networks (i.e., the graph of friendship relationships) are often used to share contents. Mobile devices let it easier in these days, but it also increases the privacy risk such as access control of shared data and relationship exposure to untrusted server. To control the access on encrypted data and protect relationship from the server, M. Atallah et al. proposed a hop-based scheme in 2009. Their scheme assumed a distributed environment such as p2p, and each user in it shares encrypted data on their social network. On the other hand, it is very inefficient to keep their relationship private, so we propose an improved scheme. In this paper, among encrypted contents and relationships, some authenticated users can only access the data in distributed way. For this, we adopt 'circular-secure symmetric encryption' first. Proposed scheme guarantees the improved security and efficiency compared to the previous work.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 동적인 소셜 네트워크 환경에서 분산된 방식으로 프라이버시를 보호하는 효율적인 접근 제어 기법을 제안하였다. 기존 연구에서 서버가 소셜 네트워크를 추론하지 못하도록 연결정보를 비효율적으로 중복 암호화하는 문제점을 해결하기 위해서, 본 논문에서는 키를 또 다른 키로 암호화하는 환형 암호화를 적용시켰다. 이 기법은 기존의 기법과 동일한 안전성으로 서버로부터 개인의 프라이버시를 보호하고 개선된 효율성을 보장한다.
본 논문에서는 동적인 소셜 네트워크 환경에서 분산된 방식으로 프라이버시를 보호하는 효율적인 접근 제어 기법을 제안하였다. 기존 연구에서 서버가 소셜 네트워크를 추론하지 못하도록 연결정보를 비효율적으로 중복 암호화하는 문제점을 해결하기 위해서, 본 논문에서는 키를 또 다른 키로 암호화하는 환형 암호화를 적용시켰다.
더불어 키 유도 과정에서 서버가 주어진 소셜 네트워크를 추론할 수 있는 문제를 해결했지만, 그 해결방안이 매우 비효율적이라는 새로운 문제점이 제기되었다. 본 논문의 아이디어는 이 문제점을 개선시키려는 데에서 출발했다. M.
본 절에서는 제안하는 기법의 안전성을 분석한다. [정리 1]은 정적인 신뢰 그래프 로 이뤄진 접근 그래프 G′이 효과적으로 비 인가된 사용자의 접근을 막을 수 있는지 분석한다.
가설 설정
이 때, 중요한 점은 소셜 네트워크는 오프라인 인맥이 반영되기 때문에 대부분의 사용자 들은 주어진 프로토콜을 변형하지 않는 반-정직 (semi-honest)한 공격자로 가정한다는 점이다. 따라서 분석도 이러한 공격자를 가정하고 이뤄진다. 또한 서버는 암호화된 연결정보를 저장하고 일종의 공개 게시판처럼 자신이 저장한 데이터를 사용자들과 공유 한다.
사용자들이 오프라인 상태에서 공개게시판에 접근하여 필요한 공개 값을 다운받고 권한이 있는 값만 복호화 할 수 있다는 점에서, 서버는 특정 사용자가 어떤 사용자의 정보를 다운받는지 추적할 수 없다. 따라서 이후 제시될 [정리 1]과 [정리 2]는 사용자 입장의 공격자를 가정하고 안전성을 분석한다. 더불어 제안하는 기법은 기존의 기법[6]이 보장하는 안전성을 동일한 수준으로 보장하고, 주어진 소셜 네트워크를 서버가 추론할 수 없도록 하여 사용자의 프라이버시를 서버로부터 안전하게 보호한다.
주어진 시스템에서 두 사용자의 경로(path)는 소셜 네트워크에서 그들을 최단으로 잇는 사용자들의 순서 있는 집합(ordered set)이고, 그 집합 내 원소들의 총 개수를 경로의 길이(혹은 두 사용자가 떨어진 거리)로 정의한다. 또한, 두 사용자 간의 신뢰 수준은 그들의 거리에 반비례한다고 가정한다. 실제로 사용자의 관점에서 보았을 때, 자신의 친구를 친구의 친구보다 더 신뢰한다고 여길 것이므로 이 같은 가정은 매우 자연스럽다.
제안 방법
이 예제는 제안하는 기법의 아이디어를 간략히 소개하기 위한 것이다. 각각의 사용자보다는 서버의 관점에서 전체 알고리즘이 어떻게 수행되는지에 초점을 맞춰 개괄적인 아이디어를 살펴본다. 우선 예제에 사용될 기호들을 [표 1]과 같이 정리한다.
하지만 이 기법들은 그것에 활용된 준동형/속성 기반 암호 기술들이 비효율적이라는 단점 때문에, 전체적인 기법의 효율성도 여전히 문제로 남아있다. 본 논문에서 제안하는 기법은 이 문제를 해결하기 위해 대칭키 기반의 환형 암호시스템을 적용한다. 본 논문의 가장 큰 공헌은 환형 암호를 적용함으로 인해서, 접근키와 인맥정보를 한꺼번에 암호화하고 서버로부터 인맥정보도 안전하게 보호한다는 점이다.
제안하는 기법은 형성된 소셜 네트워크를 권한 없는 다른 사용자들과 서버로부터 보호하며 사용자가 키 유도에 필요한 공개정보만 내려 받을 수 있도록 키에 대한 접근제어를 수행한다. 우선 개괄적인 알고리즘을 간단한 예제로 살펴본 뒤에, 구체적인 기법을 소개한다.
이를 기반으로 [정리 2]는 동적인 그래프 G, G′에 대해서도 접근제어가 이뤄지는지 분석한다.
첫째로, 서버에 질의하여 받아오는 데이터의 양이 다. 제안하는 기법에서 각각의 사용자는 자신이 원하는 접근키를 얻기 위해 최대 L반경 내에 있는 사용자의 공개정보만 서버로부터 받고, 나머지 키 유도 과정은 자신의 기기 내에서 수행한다. 이는 Derive 알고리즘이 호출될 때 마다 서버가 사용자에게 전체 pub을 중복해서 반환해야 했던 기존의 기법보다 매우 효율적 이다.
제안하는 기법은 2009년에 제안된 기법[6]을 개선하였고, 제시한 공개문제(open problem)를 해결하였기 때문에, 효율성 및 안전성 분석은 [6]을 바탕으로 한다. [6]은 기존의 접근제어가 가지고 있던 문제(프로토콜에 참여하는 사용자들이 동시에 온라인이어야 하고, 타인의 연결정보가 노출되는 점)들을 최초로 해결하였지만 효율성 측면에서 새로운 문제점이 발생 했다.
기존의 기법[6]은 키 관리 기법을 적용시키기 위해서 키 유도에 쓸 키와 데이터 암호화에 쓸 키를 따로 관리하고, 개인을 식별할 공개 값을 ID 외에 별도로 설정하여 pub에 저장하는 번거로움이 존재했다. 제안하는 기법은 데이터 암호화에 사용할 키와 키유도에 사용할 키를 일원화시키고 이에 따른 안전성 문제를 해결하기 위해 환형 암호화 기법을 적용시켰다. 이렇게 함으로 인해서 별도로 관리하던 개인 식별 값을 없애고, 연결정보만 pub에 저장하여 연산의 효율성과 저장량을 동시에 향상시켰다.
제안하는 기법은 초기화 단계(Setup Phase), 키유도 단계(Derive Phase), 그리고 동적인 소셜 네트워크를 지원하는 확장된 단계(Extended Phase) 로 구성된다. 각 단계 별로 다음과 같은 알고리즘이 사용된다.
제안하는 기법은 형성된 소셜 네트워크를 권한 없는 다른 사용자들과 서버로부터 보호하며 사용자가 키 유도에 필요한 공개정보만 내려 받을 수 있도록 키에 대한 접근제어를 수행한다. 우선 개괄적인 알고리즘을 간단한 예제로 살펴본 뒤에, 구체적인 기법을 소개한다.
이론/모형
Atallah 등은 위에서 언급한 모든 단점을 해결한 최초의 기법을 제안했다[6]. 이 접근제어 기법은 같은 해에 발표된 키 관리 기법[7]을 활용 하여 초기화, 질의, 응답 알고리즘을 설계했고, 신뢰할 수 있는 제 3기관이 필요 없는 분산된 방식을 채택 했다. 또한, 서버가 최소한의 기능만 수행하고, 프로토콜을 수행하는 모든 사용자들이 동시에 로그인 상태 여야 하는 문제도 해결했다.
성능/효과
따라서 이후 제시될 [정리 1]과 [정리 2]는 사용자 입장의 공격자를 가정하고 안전성을 분석한다. 더불어 제안하는 기법은 기존의 기법[6]이 보장하는 안전성을 동일한 수준으로 보장하고, 주어진 소셜 네트워크를 서버가 추론할 수 없도록 하여 사용자의 프라이버시를 서버로부터 안전하게 보호한다.
둘째로, 필요한 변수의 양과 그것의 관리가 훨씬 효율적이다. 기존의 기법[6]은 키 관리 기법을 적용시키기 위해서 키 유도에 쓸 키와 데이터 암호화에 쓸 키를 따로 관리하고, 개인을 식별할 공개 값을 ID 외에 별도로 설정하여 pub에 저장하는 번거로움이 존재했다.
따라서 실제적으로 시스템에서 사용할 값은 데이터 접근을 허용할 사용자 범위가 전체 네트워크에서 차지하는 비율인 c(0 < c ≤ 1)에 대해서L≈cㆍlog(|V|)일 것이고, [표 6]의 O(NL-1L)는 페이스북의 전체 사용자 수가 5억 이상임을 감안하면 굉장히 향상된 복잡도임을 알 수 있다.
[6]은 기존의 접근제어가 가지고 있던 문제(프로토콜에 참여하는 사용자들이 동시에 온라인이어야 하고, 타인의 연결정보가 노출되는 점)들을 최초로 해결하였지만 효율성 측면에서 새로운 문제점이 발생 했다. 본 논문에서는 이러한 문제점을 효율적으로 해결하였고, 본 절을 통해서 안전성과 효율성이 개선되었음을 보인다.
본 논문에서 제안하는 기법은 이 문제를 해결하기 위해 대칭키 기반의 환형 암호시스템을 적용한다. 본 논문의 가장 큰 공헌은 환형 암호를 적용함으로 인해서, 접근키와 인맥정보를 한꺼번에 암호화하고 서버로부터 인맥정보도 안전하게 보호한다는 점이다. 접근키와 인맥정보를 함께 다뤄서 기법의 효율성을 개선했고, 이전 연구들에서 해결하지 못했던 ‘인맥정보의 보호’라는 공개 과제(open problem)를 해결했다.
셋째로, 연결정보 암호화 후에도 암호화 전의 기능을 무리 없이 제공한다는 점이다. 기존의 기법[6]은 서버가 네트워크를 추론해 낼 수 없게 하기 위해서 연결정보를 암호화했지만, 이와 동시에 접근 가능한 데이터들이 직접 연관된 사용자의 것으로 제한되어 암호화 전에 제공하던 기능을 수행할 수 없다.
접근키와 인맥정보를 함께 다뤄서 기법의 효율성을 개선했고, 이전 연구들에서 해결하지 못했던 ‘인맥정보의 보호’라는 공개 과제(open problem)를 해결했다.
[정리 2]의 대우는 신뢰 그래프 G 에대해서 depthG(u,v) > d(경로가 존재하지 않는 경우는 depthG(u,v) = ∞)인 임의의 두 사용자 u,v가 접근 그래프 G′에서 # ∈ G′와 # ∈ G′를 잇는 경로를 가질 수 없다는 것이다. 제안하는 기법에서 접근 키를 유도하는 구조상, 접근 그래프에서 경로가 존재 하지 않으면 접근키를 유도할 수 없고 데이터에 접근 하는 것도 불가능하다, 결론적으로, 적법한 거리내의 사용자만이 데이터에 접근 가능하다.
제안하는 기법은 소셜 네트워크에서 분산된 접근제어를 수행하는 관련 연구들 중 가장 효율적이다.
후속연구
이 기법은 기존의 기법과 동일한 안전성으로 서버로부터 개인의 프라이버시를 보호하고 개선된 효율성을 보장한다. 다만, 서버가 두 사용자 간의 연결경로를 찾기 위해 검색하는 과정에서 너비 우선 검색이 사용되는 단점이 존재하므로, 알고리즘 구조의 개선을 통해 검색 과정과 복호화 횟수를 최적화하는 것을 향후 연구 과제로 남긴다. 또한 소셜 네트워크만이 가지는 그래프 이론적 특성을 보안 메커니즘에 적용시켜 소셜 네트워크에 특화된 연구를 구축하는 것이 더 필요하다.
다만, 서버가 두 사용자 간의 연결경로를 찾기 위해 검색하는 과정에서 너비 우선 검색이 사용되는 단점이 존재하므로, 알고리즘 구조의 개선을 통해 검색 과정과 복호화 횟수를 최적화하는 것을 향후 연구 과제로 남긴다. 또한 소셜 네트워크만이 가지는 그래프 이론적 특성을 보안 메커니즘에 적용시켜 소셜 네트워크에 특화된 연구를 구축하는 것이 더 필요하다.
따라서 [표 6]의 키 유도를 위한 복호화 횟수는 이 같은 기능을 원활히 제공하기 위해 반드시 필요한 부하이고, 이 값을 알고리즘의 구조를 개선하여 최적화 하는 것이 최선일 것이다. 제안하는 기법은 기본적으로 필요한 복잡도인 O(NL-1)로 복호화를 수행하고, 이를 더욱 최적화시키는 것을 추후 연구 과제로 남긴다.
질의응답
핵심어
질문
논문에서 추출한 답변
소셜 네트워킹 서비스의 문제점은?
최근 페이스북과 같은 소셜 네트워킹 서비스 (Social Networking Services, SNS)를 이용하여 지인들과 개인적인 데이터를 공유하는 사용자들이 증가하고 있다. 이 서비스는 중앙 집중형 웹 서버를 기반으로 하기 때문에 사용자들의 모든 통신 내역이 서버에 노출된다. 이러한 취약점으로부터 사용자 프라이버시를 보호하고 이전과 동일한 서비스를 제공하기 위해서는 공유할 데이터와 네트워크 구성도(network topology)에 대한 접근제어가 필요하다.
소셜 네트워킹 서비스는 무엇에 유용한가?
싸이월드, 페이스북과 같은 소셜 네트워킹 서비스는 개인적인 데이터를 지인들과 공유하는데 매우 유용하다. 이들은 대부분 중앙 집중형 서버를 기반으로 하는데, 이 같은 시스템은 사용자들의 모든 통신 내역이 서버에게 노출된다는 단점을 가진다.
LPN 문제란 무엇인가?
LWE(Learning a linear function With Errors) 문제는 Lattice 기반 암호시스템에서 최근수 년 동안 활발하게 암호학적인 환경에 적용된 난제 이다. LPN(Learning Parity with Noise) 문제는 LWE 문제의 특수한 경우로, LWE문제와 더불어 양자 컴퓨팅 하에서도 현실적인 시간 내에 풀 수 있는 알고리즘이 없다고 알려진 난제이다.
참고문헌 (8)
B. Carminati, E. Ferrari, and A. Perego, "Rule-based access control for social networks," On the Move to Meaningful Internet System, LNCS 4278, pp. 1734-1744, 2006.
B. Carminati, E. Ferrari, and A. Perego, "Private relationships in social networks," Proceedings of IEEE International Conference on Data Engineering Workshop, pp. 163-171, Apr. 2007.
B. Carminati and E. Ferrari, "Privacy-aware collaborative access control in web-based social networks," Data and Applications Security X XII, LNCS 5094, pp. 81-96, 2008.
J. Domingo-Ferrer, "A public-key protocol for social networks with private relationships," Modeling Decisions for Artificial Intelligence, LNAI 4617, pp. 373-379, 2007.
V. Alexandre, J. Domingo-Ferrer, S. Francesc, and G.N. Ursula, "Privacy homomorphisms for social networks with private relationships," Elsevier, Computer Networks, vol. 52, no. 15, pp. 3007-3016, Oct. 2008.
K.B. Frikken and P. Srinivas, "Key allocation schemes for private social networks," Proceedings of the 8th ACM Workshop on Privacy in the Electronic Society, pp. 11-20, Nov. 2009.
M.J. Atallah, M. Blanton, N. Fazio, and K.B. Frikken, "Dynamic and efficient key management for access hierarchies," ACM Transactions on Information and System Security, vol. 12, no. 3, pp. 18-43, Jan. 2009.
B. Applebaum, D. Cash, C. Peikert, and A. Sahai, "Fast cryptographic primitives and circular-secure encryption based on hard learning problems," Advanced in Cryptology, CRYPTO'09, LNCS 5677, pp. 595-618, 2009.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.