근사치 검증을 위한 이중 하위 선형 대화형 증명(dsIPPs)

데이터의 전체를 읽지 않고도 속성을 증명할 수 있는 **이중 하위 선형 대화형 증명(dsIPPs)**을 연구한다. 이 방식은 증명 생성 시 입력 데이터의 극히 일부(sub-linear)만 읽으면 되며, 검증 단계에서는 그보다 더 적은 양의 데이터만 읽어도 되는 초고속 프로세스를 지향한다.

이 시스템은 속성 테스트(Property Testing) 원리를 활용한다. 정직한 증명자는 특정 속성을 가진 입력에 대해 검증자를 통과시킬 수 있지만, 속성에서 멀리 떨어진 입력을 가진 증명자는 검증자를 속일 수 없다.

연구진은 다음과 같은 경우에 적용 가능한 증명 체계를 구축했다.

• ROOBP(Read-Once Oblivious Branching Program)로 결정 가능한 모든 속성
• 입력 데이터의 Hamming weight(해밍 무게)에 대한 근사 검증
• 유계 차수 그래프 모델(Bounded-degree graph model)에서의 이분 그래프(Bipartiteness) 완화 모델