검증 가능한 컴퓨팅

Verifiable computing

검증 가능한 컴퓨팅(또는 검증된 컴퓨팅 또는 검증된 컴퓨팅)을 통해 컴퓨터는 검증 가능한 결과를 유지하면서 일부 기능의 계산을 신뢰할 수 없는 다른 클라이언트로 오프로드할 수 있다.다른 고객들은 기능을 평가하고 기능의 연산이 올바르게 수행되었다는 증거로 결과를 반환한다.이러한 개념의 도입은 SETI@home과 같은 프로젝트에서 신뢰할 수 없는 사용자들에게 "아웃소싱" 계산을 하는 현상이 점점 더 흔해지고, 또한 클라우드 컴퓨팅과 같이 더욱 강력한 계산 서비스에 컴퓨터 작업을 아웃소싱하려는 약한 고객들의 욕구가 증가하면서 비롯되었다.이 개념은 Babai 외 연구진에 의해 다시 작동되기 시작했으며,[1] "체크 연산"(Babai 외 연구), "위임 연산",[2] "인증된 연산"[3] 및 검증 가능한 컴퓨팅을 포함한 다양한 용어로 연구되어 왔다.검증 가능한 컴퓨팅이라는 용어 자체가 로사리오 겐나로, 크레이그 젠트리, 브라이언 파르노에 의해 공식화되었고,[4] 미칼리의 "인증된 연산"[3]을 반향한다.

동기부여 및 개요

그고 싶은 욕망은 상대적으로 취약한 계산 장치에서 계산 업무를 외주가 더 강력한 계산 서비스에(노동자)고, 실제 work[5]를 수행하지 않고 그럴듯한 검색 결과를 반환하기가 의뢰인의 소프트웨어를 수정하는 부정직한 노동자들의 문제 Verifiable C의 개념의 형식화 의욕(클라이언트)omp발화[4]

검증 가능한 컴퓨팅은 아웃소싱 기능의 결과를 클라이언트의 입력과 그 정확성에 대한 증명뿐만 아니라, 클라이언트가 처음부터 기능을 계산하는 것보다 훨씬 적은 계산 노력으로 증거를 검증할 수 있는 것에 대해서도 관심을 갖는다.

보안 코프로세서,[6][7] 신뢰할 수 있는 플랫폼 모듈(TPMs),[8] 대화형 증명,[9][10] 확률적으로 확인할 수 있는 증명,[11][12] 효율적인 주장,[13][14] 미칼리의 CS 증명 등 신뢰할 수 없는 작업자가 수행하는 기능의 계산을 검증하는 데 상당한 주의를 기울였다.[15]이러한 검증은 클라이언트가 정확성 증거를 검증하기 위해 작업자와 상호작용해야 하는 인터랙티브 프로토콜이거나, 랜덤 오라클 모델에서 증명될 수 있는 비 인터랙티브 프로토콜이다.[13][14][15]

복제를 통한 확인

가장 큰 검증 연산(SETI@home)은 복제에 의한 검증을 사용한다.

SETI@home 검증 프로세스는 하나의 클라이언트 시스템과 많은 작업자 시스템을 포함한다.클라이언트 컴퓨터는 동일한 워크유닛을 여러 대의 컴퓨터(최소 2대)로 보낸다.

기계가 실수로 꺼지거나 통신 장애가 발생하는 등 합리적인 시간 내에 충분한 결과를 반환하지 않을 경우—또는 결과가 일치하지 않음—계산 오류, 실제 작업을 하지 않고 허위 데이터를 제출하는 부정행위 등.—그러면 클라이언트 컴퓨터는 다른 작업자 기계로 더 동일한 작업유닛을 보낸다.결과의 최소 쿼럼(종종 2)이 일치하면, 고객은 그 결과(및 해당 작업 단위에 대한 다른 동일한 결과)가 정확하다고 가정한다.고객은 올바른 결과를 반환한 모든 기계에 크레딧을 부여한다.

검증 가능한 연산

Gennaro 등에서는 [4]검증 가능한 연산 체계의 개념을 함수 nF: {0,1} → {0,m1}의 계산에 대해 공동작업하기 위한 두 다항 시간 당사자 사이의 프로토콜로 정의했다.이 계획은 세 가지 주요 단계로 구성된다.

  1. 사전 처리 중.이 단계는 F와 관련된 일부 보조 정보를 계산하기 위해 클라이언트에 의해 한 번 수행된다.이 정보의 일부는 근로자와 공유되고 나머지는 비공개적이며 고객과 보관된다.
  2. 입력 준비.이 단계에서 클라이언트는 함수의 입력에 대한 일부 보조 정보를 계산한다.이 정보의 일부는 공개적인 반면 나머지는 비공개적이며 고객과 함께 보관된다.공적인 정보는 작업자에게 보내져 입력 데이터에 대한 F를 계산한다.
  3. 출력 계산 및 검증.이 단계에서 작업자는 앞의 두 단계에서 계산된 F함수와 입력과 관련된 공공정보를 이용하여 제공된 입력에 F함수의 인코딩된 출력을 계산한다.그런 다음 이 결과는 이전 단계에서 계산된 개인 정보를 사용하여 작업자가 반환한 결과를 디코딩하여 실제 출력값을 계산함으로써 클라이언트로 반환되어 정확성을 검증한다.

검증 가능한 연산 체계의 정의된 개념은 정확히 두 개의 메시지로 클라이언트와 근로자 사이의 상호작용을 최소화하는데, 여기서 프로토콜의 서로 다른 단계 동안에 각 당사자가 상대방에게 보낸 하나의 메시지가 있다.[4]

완전 동형 암호화에 기반한 예제 체계

겐나로 외 연구진은 완전한 동형 암호화 시스템과 결합된 야오(Yao)의 변위 회로를 사용하여[16][17] 어떤 기능 F에 대해서도 검증 가능한 연산 체계를 정의했다.[4]

검증 가능한 이 연산 체계 VC는 다음과 같이 정의된다.[4]

VC = (KeyGen, ProbGen, Compute, Verify)는 다음과 같은 4개의 알고리즘으로 구성된다.

  1. 키젠(F, λ) → (PK, SK):임의의 키 생성 알고리즘은 보안 파라미터 λ에 근거하여 공개 키와 비공개 키 두 개를 생성한다.공용 키는 대상 함수 F를 인코딩하고 작업자에게 전송되어 F를 계산한다.반면 비밀키는 의뢰인에 의해 비공개로 유지된다.
  2. ProvGenSK(x) → (vmsx, τx):문제 발생 알고리즘은 비밀키 SK를 사용하여 함수 입력 x를 공과 사의 두 가지 값으로 인코딩한다.공시가격 σx는 F(x)를 계산하기 위해 근로자에게 주어지는 반면, 비밀가 τx는 의뢰인에 의해 비공개로 유지된다.
  3. 계산(PK, ,x) → →y: 작업자는 클라이언트의 공개 키 PK와 인코딩된 입력 inputx를 사용하여 함수 출력 y = F(x)의 인코딩된 값 σy를 계산한다.
  4. 검증SK (τx, σy) → y ∪ ⊥: 검증 알고리즘은 비밀키 SK와 비밀키 "decoding" bothx를 모두 사용하여 작업자의 인코딩 출력 yy를 함수 F의 실제 출력으로 변환한다.σy가 x에 F의 유효한 출력을 나타내는 경우 y = F(x)를 출력하거나, 그렇지 않은 경우 ⊥을 출력한다.

Gennaro 등이 정의한 검증 가능한 연산 체계의 프로토콜은 다음과 같이 작용한다.[4]

F 함수는 키 생성 알고리즘이 적용되는 부울 회로로 표시되어야 한다.키 생성 알고리즘은 공개 키와 비밀 키를 계산하기 위해 이 부울 회로에 걸쳐 야오밍의 가블링 절차를 실행한다.PK(Public Key)는 garbled 회로를 나타내는 모든 암호문으로 구성되며, 비밀키(SK)는 모든 임의 와이어 라벨로 구성된다.생성된 비밀키는 문제 발생 알고리즘에서 사용된다.이 알고리즘은 먼저 동형 암호 체계를 위해 새로운 쌍의 공용 키와 비밀 키를 생성한 다음, 이 키를 동형 체계와 함께 사용하여 혼용 회로의 비밀 키로 대표되는 올바른 입력 와이어를 암호화한다.생성된 암호문은 작업자에게 주어지는 입력( (x)의 공개 인코딩을 나타내고, 비밀키(τx)는 클라이언트에 의해 비공개로 유지된다.그 후, 작업자는 문제 발생 알고리즘에 의해 생성된 암호문 위에 야오 프로토콜의 계산 단계를 적용한다.이는 최종 출력 와이어 값(수치)에 도달할 때까지 게이트 암호문의 암호를 재귀적으로 해독하여 수행된다.암호화 체계의 동형성 속성은 작업자가 정확한 출력 와이어의 암호화를 얻을 수 있게 한다.마지막으로 작업자는 실제 출력 y = F(x) 또는 or을 계산하기 위해 출력물의 암호문을 해독하는 클라이언트에 반환한다.

검증 가능한 연산 체계의 정의는 그 체계가 정확하고 안전해야 한다고 명시한다.문제 발생 알고리즘이 정직한 작업자가 인코딩된 출력 값을 계산하여 그러한 입력에 대한 F의 평가에 부합하고 성공적으로 검증할 수 있는 값을 산출할 경우 Scheme Correctness가 달성된다.반면에 악의적인 작업자가 주어진 함수 F와 입력 x에 대해 부정확한 출력을 수용하도록 검증 알고리즘을 설득할 수 없는 경우 검증 가능한 연산 체계가 안전하다.

실용적인 검증 가능한 컴퓨팅

검증 가능한 컴퓨팅은 이론적으로(완전히 동형식 암호화를 사용하거나 확률적으로 확인 가능한 증거를 통해) 가능하다는 것이 증명되었지만, 알려진 구성의 대부분은 실제로 매우 비싸다.최근 일부 연구자들은 검증 가능한 연산을 실용적으로 만드는 것을 검토했다.그러한 노력 중 하나는 UT Austin 연구원들의 작업이다.[18]저자들은 확률적으로 확인할 수 있는 증거에 근거한 주장 체계로 시작하여 그 비용을 10배20 절감한다.그들은 또한 Pepper 시스템에서도 그들의 기술을 실행했다.저자들은 "지금까지의 우리의 결론은 보안시스템 구축을 위한 도구로서 PCP와 주장시스템이 손실된 원인이 아니라는 것"이라고 지적했다.

현재 여러 그룹의 구현이 포함된 전체 영역이 조사되었다.[19]

참조

  1. ^ Babai, László; Fortnow, Lance; Levin, Leonid A.; Szegedy, Mario (1991-01-01). Checking Computations in Polylogarithmic Time. Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing. STOC '91. New York, NY, US: ACM. pp. 21–32. CiteSeerX 10.1.1.42.5832. doi:10.1145/103418.103428. ISBN 978-0897913973.
  2. ^ Goldwasser, Shafi; Kalai, Yael Tauman; Rothblum, Guy N. (2008-01-01). Delegating Computation: Interactive Proofs for Muggles. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing. STOC '08. New York, NY, US: ACM. pp. 113–122. doi:10.1145/1374376.1374396. ISBN 9781605580470.
  3. ^ a b Micali, S. (2000-01-01). "Computationally Sound Proofs". SIAM Journal on Computing. 30 (4): 1253–1298. CiteSeerX 10.1.1.207.8277. doi:10.1137/S0097539795284959. ISSN 0097-5397.
  4. ^ a b c d e f g Gennaro, Rosario; Gentry, Craig; Parno, Bryan (31 August 2010). Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers. CRYPTO 2010. doi:10.1007/978-3-642-14623-7_25.
  5. ^ Molnar, D. (2000). "The SETI@Home problem". ACM Crossroads. 7 (1).
  6. ^ Smith, S.; Weingart, S. (1999). "Building a high-performance, programmable secure coprocessor". Computer Networks. 31 (8): 831–960. CiteSeerX 10.1.1.22.8659. doi:10.1016/S1389-1286(98)00019-X.
  7. ^ Yee, B. (1994). Using Secure Coprocessors (PhD thesis). Carnegie Mellon University.
  8. ^ Trusted Computing Group (July 2007). Trusted platform module main specification. 1.2, Revision 103.
  9. ^ L. 바바이(1985)"무차별성을 위한 트레이딩 집단 이론."미국 뉴욕주 뉴욕주 컴퓨팅 이론 심포지엄 421-429페이지
  10. ^ S. 골드워서, S. 미칼리, C.랙오프(1989년)."대화형 교정 시스템의 지식 복잡성." SIAM 컴퓨팅 저널, 186-1, 페이지 186–208
  11. ^ S. 아로라와 S. 사프라(1998년)."확률적으로 확인할 수 있는 증거: NP의 새로운 특성화." ACM 저널, 45, 페이지 501-555
  12. ^ O. 골드레이치(1998년).현대 암호학, 확률론적 증명 및 유사성.알고리즘 및 조합 시리즈, 17, 스프링거
  13. ^ a b J. 킬리안(1992년)."효율적인 제로 지식 증명과 논쟁에 관한 노트(확장된 추상적)."컴퓨터 이론에 관한 ACM 심포지엄의 진행과정
  14. ^ a b J. 킬리안(1995년)."효율적인 인수(예비 버전) 향상."영국 런던의 Crypto Procedures에서 311–324페이지.스프링거-베를라그
  15. ^ a b S. 미칼리(1994년)."CS 증명서(확장된 추상)."컴퓨터 과학의 기초에 관한 IEEE 심포지엄의 진행, 페이지 436-453.
  16. ^ A. 야오(1982년)."보안 컴퓨팅을 위한 프로토콜"컴퓨터 과학의 기초에 관한 IEEE 심포지엄의 진행, 페이지 160-164
  17. ^ A. 야오(1986)"비밀을 생성하고 교환하는 방법."컴퓨터 과학의 기초에 관한 IEEE 심포지엄의 진행, 페이지 162-167
  18. ^ Setty, Srinath; McPherson, Richard; Blumberg, Andrew J.; Walfish, Michael (February 2012). Making Argument Systems for Outsourced Computation Practical (Sometimes). Network & Distributed System Security Symposium (NDSS) 2012.
  19. ^ Walfish, Michael; Blumberg, Andrew J. (2015-01-01). "Verifying Computations Without Reexecuting Them". Commun. ACM. 58 (2): 74–84. doi:10.1145/2641562. ISSN 0001-0782.