, 저자: Guo Yu, 승인을 받아 Odaily에서 복제.

많은 사람들이 영지식 증명에 대해 들어봤지만 시뮬레이션에 대해 들어본 사람은 거의 없지만 시뮬레이션은 영지식을 이해하는 열쇠입니다."제로 지식"과 "증거"에 대한 최초의 이해우리의 첫 번째 기사 "

"제로 지식"과 "증거"에 대한 최초의 이해

직관의 관점에서 설명하면 대화형 시스템에서 정보 유출이 있음을 증명하려면 어떤 비트가 정보 유출을 유발하는지 증명하면 되지만 정보 유출이 없음을 증명하려면 다음을 증명해야 합니다. 모든 정보 흐름에 직면해야 합니다. 말하자면 1, 2, 3, 4, 5, ...에서 번호가 매겨진 비트는 어떤 정보도 드러내지 않습니다. 판사님, 이게 어렵나요?

보안 정의 및 비구별성

우선 대화식 시스템, 즉 대화, "제로 지식"이 입증되어야 합니다. 결국, 현대 암호는 엄격한 공식 시스템을 기반으로 합니다. 증명하기 전에 "안전 가정"이 무엇인지 명확히 할 필요가 있습니다. 예를 들어 소위 보안 가정은 시스템의 권한 격리가 매우 정확하고 각 사용자는 승인된 정보만 볼 수 있다고 말하지만 이는 보안 가정에 기반합니다. 즉, 관리자 계정이 해킹되지 않았습니다. 또 다른 예는 모바일 뱅킹 소프트웨어에서 이체 기능은 SMS 인증 코드를 통해서만 완료할 수 있다는 것입니다.이 역시 보안 가정을 ​​기반으로 합니다: 휴대폰 SIM 카드가 복제되지 않았습니다. 우리가 안전하다고 생각하는 모든 시스템을 자세히 살펴보면 그다지 견고하지 않은 보안 가정이 많이 있습니다. Bitcoin 개인 키는 안전합니까? Bitcoin 계정에 대한 많은 보안 가정도 있습니다. 우선 귀하의 니모닉은 다른 사람에게 알려질 수 없으며 모바일 지갑에 개인 키를 저장하기 위한 암호화 알고리즘은 충분히 강력하며 키 파생 알고리즘은 규칙적이며 니모닉을 잊을 수 없습니다. , 등등.

보안 가정 없이 보안에 대해 이야기하는 것은 훌리건주의입니다. 모든 것이 안전합니다. 수학적 증명 후에만 모든 사람이 이 알고리즘/체계의 보안이 몇 가지 매우 명확한 "보안 가정"을 기반으로 한다는 것을 확신할 수 있습니다.

증명하기 전에 아직 한 가지 빠진 것이 있는데, 그것은 "안전 정의"입니다. 대부분의 사람들의 인지 시스템에서 보안은 모든 것이 설치될 수 있는 상자입니다. 안전이라는 단어에 대해 이야기할 때 안전이 무엇인지 생각해 본 적이 있습니까? 어떻게 안전한 것으로 간주됩니까?

"보안"은 수학적 의미에서 엄격한 정의가 필요합니다.

위대한 과학자 Claude Shannon은 정보 이론의 관점에서 매우 신뢰할 수 있는 보안 정의를 제시했습니다[2].

완벽한 보안: 당신이 공격자라고 가정하면 암호문을 통해 귀중한 정보를 얻을 수 없으며 이를 해독하는 유일한 방법은 맹목적으로 의존하는 것입니다.

여러분 생각해보세요 이 정의는 매우 흥미롭습니다.

그러나 이 정의는 너무 완벽해서 사용되는 암호화 알고리즘이 이 보안 정의를 충족하기 어렵습니다. 나중에 Goldwasser, Micali 등은 역사에 기록된 또 다른 고전적인 "확률적 암호화"[2]를 작성했습니다.

본 논문에서는 시맨틱 보안이라는 개념을 정의한다. 소위 시맨틱 보안은 완벽한 보안의 정의에 대한 일부 요구 사항을 완화합니다.

의미론적 보안: 당신이 공격자라고 가정하면 다항식 시간에 암호문을 통해 가치 있는 정보를 계산할 수 없습니다.

다시 반복합니다. "현실 세계"에서 당신과 대화하는 사람은 실제적이고 정직한 앨리스이고, "이상 세계"에서 당신과 대화하는 사람은 Zlice(가짜 앨리스)이지만 Zlice는 외모와 언어가 동일합니다. as Alice 그것은 동일하지만 차이점은 Zlice가 "지식"을 모른다는 것입니다. 즉, 3색 문제에 대한 답을 모른다는 것입니다.

그런 다음 두 세계에서 두 개의 복식이 동시에 실제 및 가짜 앨리스와 대화합니다. 기적 같은 일이 일어났습니다.마침내 두 세계에서 두 아바타 모두 확신했고, n번의 도전 끝에 아무도 속이는 사람이 발견되지 않았습니다. 즉, "당신"의 두 아바타는 상대방이 정말로 "답"을 알고 있었다. 즉, "당신"은 당신이 "현실 세계"에 있는지 "이상 세계"에 있는지를 "구별"할 능력이 없으며 물론 당신이 이야기하고 있는지를 "구별"할 능력이 없습니다. 앨리스 또는 Zlice. 그뿐만 아니라 멜론을 먹는 사람들에게 내가 '나'를 어떤 세계의 관찰자로 둔다면 내 앞에 있는 '앨리스'처럼 보이는 사람이 진짜인지 아니면 당신처럼 '분별할 수 없을' 것입니다. 아니. 가짜.

두뇌를 태우는 결론은 다음과 같습니다.

이 대화식 시스템이 "제로 지식"인 이유는 무엇입니까?

Zlice는 지식이 없고 Alice와 구별할 수 없기 때문입니다.

다른 방식으로 설명하겠습니다. 당신도 나도 우리가 어느 세계에 있는지 구분할 수 없기 때문에 두 세계 사이의 상호 작용 과정은 거의 구분할 수 없으며 한 세계에는 지식이 없습니다. - "지도 삼색 문제"는 "영지식"입니다.

여기에도 전제가 있습니다. 이상적인 세계는 알고리즘적으로 구성할 수 있어야 합니다. 그런 다음 알고리즘을 통해 "이상적인 세계"를 "시뮬레이션"하고 Zlice라는 알고리즘을 구축하는 "신"이 있습니다. 그녀는 입력으로 "지식"이 없습니다. "이상적인 세계"는 "현실 세계"와 정확히 동일합니다.

대화 중에 진짜 앨리스가 정보를 유출하면 눈앞에 있는 사람이 진짜 앨리스인지 즈라이스인지 즉시 구별할 수 있다고 상상해보십시오. 즈라이스가 정보를 유출하는 척하는 것은 불가능합니다. 따라서 다음과 같은 결론을 내릴 수 있습니다.

진짜 앨리스는 어떤 정보도 누설하지 않았습니다.

자, 여기서는 "영 지식"을 정의하기 위해 "시뮬레이터"라는 개념을 사용합니다.

다음으로 제로 지식 증명 링크에 들어가기 시작합니다.

Save World State as Snapshot X

보조 제목

두 세계를 분리하다

증명의 영지식 프로세스는 시뮬레이터가 "무지식"으로 이상적인 세계를 시뮬레이션할 수 있도록 하는 "시뮬레이션" 알고리즘을 구성(발견)하는 것과 같습니다. 이 알고리즘이 존재하고 두 세계를 구분할 수 없으면 증명이 완료된 것입니다.

잠깐, 아마도 "당신"은 무언가 잘못되었다고 느낄 것입니다.

사실 여기에 핵심이 있는데, 영화 '인셉션' 스틸컷을 빌리자면 '이상세계'에는 '현실세계'와 근본적으로 다른 것들이 있다. 이것은 두 세계를 구별하는 열쇠이며 우리를 "인지할 수 없게" 만듭니다. 이것은 꿈속의 팽이가 아니라 일종의 "초능력", 시뮬레이터 시뮬레이터가 소유한 초능력입니다.

예를 들어, 그러한 초강대국은 "시간을 거슬러"입니다.

이미지 설명

(위 사진은 영화 '성촉의 날' 스틸컷. 주인공은 잠에서 깨어날 때마다 2월 2일 아침으로 돌아가 항상 같은 날을 살게 된다)

잠깐, 독자 여러분, 우리가 방금 구별 불가능성에 대해 논의하지 않았습니까? 두 세계를 다시 구분해야 하는 이유는 무엇입니까? "혼란스러워". 당황하지 마십시오. 소위 불분명함은 이상적인 세계에서 개인의 인지를 목표로 합니다. 그리고 "미분 가능성"은 세상 밖에 있는 신들을 위한 것이다.

우리 주변에 시간과 공간을 여행할 수 있는 능력을 가진 사람이 있거나 그가 1년 전으로 시간을 거슬러 올라갈 수 있다면 우리 같은 평범한 사람들은 완전히 (멍)과 (비)를 혼동하고 인지하기 위해서. 그런 다음 "시뮬레이터"가 자신이 구축한 "이상적인 세계"에서 "시간의 역전"을 실현할 수 있다면 그는 몇 가지 마법적인 일을 달성하여 관찰자 "나"뿐만 아니라 검증자인 "당신"을 속일 수 있습니다. "당신"의 경우 "이상적인 세계"에서는 시간을 되돌릴 수 있지만 "현실 세계"에서는 실제 앨리스가 초능력을 갖는 것이 분명히 불가능하다는 것을 이해합니다. 당신과 나는 우리가 어느 세계에 있는지 알 수 없지만 적어도 두 세계의 "현실 세계"에서는 반대편의 앨리스가 우리를 속일 수 없다는 것을 알고 있습니다. 우리가 있는 세상. .

우선 "제로 지식"은 Alice의 이익을 보호하는 것입니다. Alice는 상호 작용 과정에서 Bob에게 더 많은 정보를 공개하고 싶지 않고 Bob이 자신의 비밀 w를 알기를 원하지 않으며 Bob이 A조차 분석하는 것을 원하지 않기 때문입니다. 정보의 조각. 그렇다면 이것을 보장하는 방법은 무엇입니까? 이때 등장하는 "시뮬레이터"는 실제 세계와 똑같은 "이상적인 세계"를 시뮬레이션할 수 있으며, "시뮬레이터"는 이 세계의 어떤 상대도 쉽게 속일 수 있어 자신이 현실 세계에 있는지, 이상 세계에 있는지 상대를 가리킨다. "시뮬레이터"는 비밀 w를 손에 쥐고 있지 않기 때문에 "이상적인 세계"는 영지식입니다. 그리고 두 세계의 구별 불가능성 때문에 우리는 Alice의 상호작용 프로토콜이 "영지식"이라고 결론을 내릴 수 있습니다.

• 지도 삼중 색칠 문제의 영지식 증명

• "Map Three Coloring Problem Interactive System"을 상기하십시오.

• 1단계: Alice는 지도 색칠 답을 완전히 교체한 다음 모든 꼭지점을 종이로 덮고 밥에게 줍니다.

• 2단계: Bob이 무작위로 가장자리를 선택합니다.

3단계: Alice는 지정된 가장자리의 양쪽 끝에 있는 꼭지점에서 종이 조각을 열고 Bob은 두 꼭지점의 색상이 같은지 확인하고 다르면 통과하고 같으면 실패합니다.

처음 단계로 돌아가 n회 반복

다음으로, 우리는 위의 상호 작용이 영지식임을 증명할 것입니다. 여기서 우리는 검증자 Bob이 정직하다고 가정하여 모든 사람이 증명 프로세스를 이해하는 데 도움이 될 것입니다. 그런 다음 Bob이 부정직한 경우 증명 방법에 대해 논의합니다.

"이상적인 세계"에서 Bob이 말하는 것은 전 세계의 모습을 시뮬레이션하는 "시뮬레이터"입니다. Bob은 삼색 문제에 대한 상호 작용 프로토콜에 따라 상호 작용합니다. 시뮬레이터에는 3색 응답이 없으며 모든 정점을 회색으로 표시합니다.

먼저 시뮬레이터는 Alice를 모방하고 각 정점을 종이로 덮습니다. 그런 다음 Bob에게 보냅니다.

Bob은 무작위로 가장자리를 선택하고 증명자에게 도전합니다.

이 가장자리의 양쪽 끝에 있는 색상이 회색이기 때문에 시뮬레이터는 현재 용지를 열 수 없습니다.

이때 시뮬레이터는 "슈퍼 파워"를 발휘하려고합니다. 그는 시간을 되돌리는 기술을 사용하고 대화의 첫 번째 단계로 돌아갑니다.

시뮬레이터는 이제 첫 번째 단계에 있으며, 여기에서 아래쪽 가장자리의 끝을 다른 색으로 염색하고 종이를 다시 덮고 Bob에게 보냅니다.

이때 Bob은 시간이 처음 단계로 되돌아간 것을 인식할 수 없으며, 그에게는 모든 것이 새롭고 "솔직히" 다시 하단 가장자리를 선택합니다.

이때 시뮬레이터는 종이를 안전하게 열어 밥이 확인하게 할 수 있습니다. Bob은 분명히 속을 것입니다. 그런 다음 Bob은 라운드마다 이 프로세스를 반복하고 매번 시뮬레이터는 시간을 거슬러 올라가 Bob을 속일 수 있습니다.

부정직한 밥

오래전 바그다드라는 도시에 알리바바라는 남자가 살았습니다. 매일 알리바바는 물건을 사러 시장에 갈 것입니다.

어느 날 알리바바는 도둑에게 지갑을 빼앗겨 동굴 입구까지 도둑을 쫓아갔고 도둑은 사라졌다. Alibaba는 아래 그림과 같이 동굴 입구에서 두 개의 분기점을 발견했습니다.

알리바바는 도둑들이 어디로 가고 있는지 몰랐기 때문에 "왼쪽" 갈림길을 살펴보기로 했습니다. 곧 알리바바는 이곳이 막다른 골목이고 도둑의 흔적이 없음을 발견했습니다. 그런 다음 그는 다시 확인하기 위해 "오른쪽" 분기점으로 갔고 막 다른 골목이었고 도둑의 흔적이 없었습니다. 알리 바바는 혼잣말을 했습니다. "도둑놈이 어디 갔지?"

다음날 알리바바는 다시 물건을 사러 시장에 갔다. 이번에는 또 다른 도둑이 바구니를 털었고, 이어 알리바바는 어제와 같은 동굴 입구까지 도둑을 쫓아갔다가 다시 도둑이 사라졌다. "갈래로 보면 도둑이 없고 왼쪽으로 가면 도둑이 없다. 이것은 매우 이상합니다.

3일째, 4일째, ..., 40일째 같은 이야기가 펼쳐지는데, 알리바바는 40번째 도둑을 신비한 동굴로 쫓아갔고, 도둑은 사라졌다. 알리바바는 이 동굴에 메커니즘이 있는 게 틀림없다고 생각해서 '오른쪽' 갈림길 끝에 숨어 오래 참을성 있게 기다렸다." 이때 담이 열렸다 도둑이 들어오자 다시 담이 닫혔고 이때 또 다른 피해자가 들이닥쳤다.

Ali Baba는 그들이 사라진 후 주문을 시도했고 매우 효과적이었고 Ali Baba는 벽이 "왼쪽"옆길로 이어지는 것을 발견했습니다. 나중에 Ali Baba는 주문을 대체할 방법을 찾아 새로운 주문과 동굴의 위치를 ​​양피지에 적었습니다.

참고: 이쯤 되면 이야기가 끝나지 않는다.... (자막) 오랜만에 오랜만에

수년 후인 1980년대에 알리바바의 양피지는 몇몇 암호학자의 손에 넘어갔다. 두 갈래 사이를 왔다 갔다 했다.

TV 방송국은 곧 이 이상한 사건을 알게 되었고, 암호 해독가 Mick Ali(암호 해독가 Micali와 비슷하게 발음됨)는 자신이 주문을 알고 있음을 TV 시청자에게 보여 주기로 결정했습니다. 모두가 동굴 입구에서 기다리고 있었습니다. 이때 Mick Ali는 혼자 동굴에 들어간 다음 호스트는 동전을 던져 Mick Ali가 빠져 나갈 포크를 결정했습니다. 알리바바와 40인의 도적을 기념하기 위해 믹 알리는 매번 성공으로 40번을 반복했다.

이것을 보고 점차 '시뮬레이션'에 대한 감이 오시나요? 여기서 두 번째 TV 방송국의 호스트는 "시간 반전" 대신 비디오를 자릅니다. 콘텐츠가 TV로 방송되는 세계인 '이상적인 세계'에 대한 그의 외부 개입도 같은 효과를 거뒀다. 이상적인 세상에서 편집은 본질적으로 초능력입니다.

이 이야기는 실제로 1989년 Mimi 컨퍼런스에서 발표된 "How to Explain Zero-Knowledge Protocols to Your Children"(How to Explain Zero-Knowledge Protocols to Your Children)[3]이라는 논문에서 나온 것입니다.

보조 제목

시뮬레이션 및 튜링 머신

초강대국에 관해서는 이것이 비과학적이라고 생각하십니까? 예, 우리가 무언가를 설명하기 위해 아무 생각 없이 "초능력"을 사용한다면 우리의 논리는 일관적이지 않을 것입니다. 이상적인 세계에서 시뮬레이터는 아무렇게나 열 수 없습니다.예를 들어 시뮬레이터는 Bob의 내부 상태를 직접 수정해서는 안됩니다.예를 들어 Bob은 검증 단계에서 분명히 검증 단계에 실패했지만 시뮬레이터는 검증 결과를 " "모든 대화형 시스템은 지식이 없다"라는 잘못된 결론을 증명하게 됩니다.

시뮬레이터는 이상적인 세계에서 전능한 신이 아닙니다.

그렇다면 에뮬레이터는 정확히 무엇일까요? 시뮬레이터는 사실 튜링 머신일 뿐입니다. "시간 되감기"나 "동영상 편집"과 같은 소위 초능력은 신비한 초능력이 아니라 튜링 기계로 실현할 수 있는 기능입니다. 컴퓨터 전문가인 친구들은 VMWare, 가상 머신 및 기타 소프트웨어를 사용했을 것입니다. 이 기사에서 언급한 "시뮬레이터"는 컴퓨터 환경을 가상화할 수 있는 "가상 머신" 소프트웨어로 상상할 수 있습니다. 텍스트. "시간을 거슬러"를 설명하는 방법? 가상 머신 소프트웨어의 "스냅샷" 기능(Snapshot)을 사용하셨는지 모르겠습니다. 가상 머신 소프트웨어를 복원할 수 있습니다. 스냅샷을 저장한 위치로 이동하여 계속 실행하십시오.

참고: 사실 소위 시간 반전은 컴퓨터의 기본 작업이며 프로그래밍 언어 이론에는 연속이라는 개념이 있습니다. 추상적으로 말하면 Continuation은 지금부터 미래까지의 계산을 나타냅니다. Continuation은 제어 흐름의 명시적인 추상화이며 goto, call-with-current-continuation, 심지어 스레드 스케줄링까지도 Continuation을 운영하기 위한 연산자로 간주될 수 있습니다. 예를 들어, call/cc, 즉 call-with-current-continuation은 "backtracking" 기능을 쉽게 구현할 수 있습니다. 스냅샷 저장은 현재 연속을 저장하는 것으로 이해할 수 있으며 과거의 특정 순간으로 돌아가는 것은 이 연속을 적용하는 것입니다.

Zlice 또는 Bob에 관계없이 각 관찰자는 실행 가능한 프로그램입니다. 이러한 프로그램은 가상 머신에 복사됩니다. Zlice와 Bob의 대화는 실제로 두 프로그램 간의 통신입니다. 관찰자는 Zlice 및 Bob 프로세스의 IO에 있는 Hook 프로그램입니다. 위 맵에서 삼색 "이상적인 세계"의 정직한 Bob은 실제로 가상 머신의 "난수 생성기"를 호출하는 Bob 프로세스이며 이 난수 생성기는 Zlice에 의해 조작될 수 있습니다. "실제 세계"는 가상 시스템 소프트웨어를 실행하는 외부 컴퓨터 환경입니다.

영지식을 증명하는 과정은 알고리즘을 찾는 것, 더 일반적으로는 외부 컴퓨터 시스템에서 실행되지만 가상 머신의 기능을 실현하는 코드 조각을 작성하는 것입니다. 그리고 가상 머신에는 입력으로 "지식"이 없는 Zlice가 있어야 하며, 이는 가상 머신에 입력되어 실행되는 Bob을 속일 수 있습니다.

시뮬레이션은 어디에나 있으며 Gödel의 불완전성 정리는 시뮬레이션 개념을 사용하여 Godel Numbers로 공식 산술을 시뮬레이션합니다. Turing은 자신을 시뮬레이션할 수 있는 "Universal Turing Machine"의 개념을 제안했습니다.

그러나 "시뮬레이션"의 가장 초기 개념은 "유토피아"[4] 책의 7권에서 나옵니다. 고대 그리스 철학자 플라톤은 그러한 우화-동굴의 비유를 말했습니다.

어두운 동굴에 쇠사슬에 묶인 채 그들 앞에 있는 벽만 보이도록 길러진 죄수들이 줄지어 있다고 상상해 보십시오. 이 죄수 뒤에는 벽이 있고 그 뒤에는 불 더미가 있습니다.불과 벽 사이에서 어떤 사람들은 소품과 인형을 들고 앞뒤로 걸어 다니므로 소품과 인형이 반사 아래 벽에 그림자를 드리울 것입니다. 불의. 그리고 이 죄수들은 하루 종일 이 그림자만 볼 수 있습니다. 이 죄수들은 태어나면서부터 눈앞의 동굴 벽에 있는 온갖 그림자를 듣고 보았고, 그들이 보는 이 그림자가 현실 세계라고 생각할 것이기 때문입니다.

그러던 어느 날 한 죄수가 실수로 사슬에서 풀려났고 뒤를 돌아보니 불이 난 것을 보았다. 그러나 그는 희미한 그림자만 보고 자랐고 처음으로 밝은 불을 보았습니다. 소품과 인형을 보고 누가 이 소품과 인형이 진짜 물건이라고 말한다면 그는 분명히 비웃고 그림자가 진짜라고 주장할 것입니다.

얼마 후 그는 동굴 안에 있는 죄수들에게 연민을 느끼고 그들을 모두 끌어낼 생각을 했습니다. 그러나 그가 다시 동굴로 돌아왔을 때 그는 외부의 밝은 세상에 적응했기 때문에 명확하게 볼 수 없었습니다. 대신 감금된 죄수들은 그가 눈먼 장님이고 말도 안 되는 소리를 하는 미친 사람이라고 생각했고, 마침내 그가 죄수들을 동굴 밖으로 나오게 하려고 안간힘을 쓰다가 죄수들에게 죽임을 당했습니다.

계속되다

이것은 쇠사슬에 묶인 죄수의 줄과 같은 인간의 운명에 대한 알레고리로, 우리는 눈으로 보는 것이 세상의 진실이라고 생각하지만 실상은 그 위에 드리워진 그림자처럼 허상일 수도 있다. 동굴벽..

계속되다

이 게시물에서는 영지식을 이해하는 데 필요한 핵심 개념인 시뮬레이션을 소개합니다. 어떤 영지식 프로토콜도 "이상적인 세계"를 구성함으로써 이해할 수 있습니다. 이 개념을 처음 접하는 독자들은 곰곰이 생각해 볼 필요가 있다.

지도 삼색 문제에서 "이상적인 세계"와 "현실 세계" 사이의 Bob의 대화를 다시 살펴보십시오. Bob은 두 세계를 구별할 수 없지만 한 가지 확신할 수 있는 것은 현실 세계에서 Alice에게는 초능력이 없다는 것입니다.

참조

여기에 문제가 있습니다. Alice는 초능력이 없으며 Alice가 실제로 답을 가지고 있음을 직접적으로 증명하지 않습니다. 이 대화형 프로토콜이 Alice가 지식을 가지고 있어야 한다는 것을 보장하지 않는다면 어떻게 될까요? "제로 지식"은 Alice의 이익을 보호하고 Bob의 이익은 누가 보장합니까? 이 질문은 다음 글로 남겨둔다.

[2] Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984.

[3]Quisquater, J.J., Quisquater, M., Quisquater, M., Quisquater, M., Guillou, L., Guillou, M.A., Guillou, G., Guillou, A., Guillou, G. and Guillou, S., 1989, August. How to explain zero-knowledge protocols to your children. In Conference on the Theory and Application of Cryptology (pp. 628-631). Springer, New York, NY.

[1] "영지식"과 "증거"에 대한 최초의 이해. Ambi Lab. 2019.

[5] Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The knowledge complexity of interactive proof systems." SIAM Journal on computing 18.1 (1989): 186-208.

[6] Oded, Goldreich. "Foundations of cryptography basic tools." (2001).

[7] Rackoff, Charles, and Daniel R. Simon. "Non-interactive zero-knowledge proof of knowledge and chosen ciphertext attack." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1991.

[8] Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems." Journal of the ACM (JACM) 38.3 (1991): 690-728.