영지식 증명

￭ 영지식 프로토콜, 개인 식별, multiparty 프로토콜등의 암호 프로토콜 구성시에 많이 이용되는 암호학적 기본 기술 ￭ Bit commitment 프로토콜 과정 1) commit 단계 A는 비트 b = 0 or b = 1을 B가 알지 못하도록 상자에 넣어 B에게 전달한다 2) reveal 단계 A는 B에게 상자의 자물쇠의 열쇠 번호를 알려주어 B가 상자내의 b의 값을 알도록 한다 ￭ 암호화 함으로써 commitment 실행 ( (X, Y는 유한집합) ￭ blob : b의 암호화된 형태 ￭ 비트위임 기법이 만족해야할 성질 ▸ 숨기는 것(concealing) : 비트 b = 0 또는 1에 대해 Vic은 blob f(b, x)로부터 b의 값을 결정할 수 없다 ▸ 구속(binding) : 나중에 Peggy는 b가 암호화되었던 값이었다는 것을 Vic에게 확신시키기 위하여 b를 암호화하는데 사용된 x의 값을 들추어냄으로써 blob을 공개할 수 있다. Peggy는 0 그리고 1 둘 다의 암호화된 결과로 blob을 공개할 수 없어야 한다 ￭ Goldwasser-Micali의 확률적 암호계 • (p, q는 소수) , 정수 n, m은 공개, 인수분헤 는 Peggy만 안다 • 그리고 • Peggy는 어떤 무작위 수 x를 선택하여 y = f(b, x)를 계산함으로써 b를 암호화한다 • y는 blob이다 • Peggy가 y를 공개하기 원할 때 b와 x를 들추어낸다 • Vic은 을 검증할 수 있다 • concealing 어떤 blob은 0 또는 1의 적당한 암호이다. 또 이 이차잉여 문제가 실행가능하지 않은 경우에는 평문값 x에 관한 어떠한 정보도 blob을 들추어내지 않는다