조지아공대 연구진이 아핀 행렬식 프로그램(ADP) 기반 위트니스 암호화의 구체적 후보안에 대한 결정론적 다항시간 공격을 제시했다. 이 방식은 2020년 ITCS에서 제안된 이후, 관련 난독화 후보안은 이미 깨졌지만 위트니스 암호화 구성 자체는 공격받지 않은 상태였다. 저자는 앞서 Soukhanov 등이 제안한 커뮤테이터 공격 기법을 활용해 은닉된 열공간을 복원하는 방식으로, 정리에 명시된 모든 q값 범위에서 공개 암호문 행렬로부터 암호화된 비트를 복원해낸다. 정수 SUBSET-SUM 인스턴스를 이용한 명시적 사례에서는 원 논문의 필드 크기 조건 하에 1-negl(n)의 확률로 비트가 복원되는 것으로 나타났다.
- •2020년 ITCS 제안 ADP 기반 위트니스 암호화 구체적 후보안을 결정론적 다항시간으로 깨는 공격 제시
- •Soukhanov 등의 커뮤테이터 공격 기법을 활용해 은닉된 열공간을 복원
- •정리에 명시된 모든 q값 범위와 정수 SUBSET-SUM 사례에서 공개 암호문으로부터 비트 복원 성공
- •원 논문의 필드 크기 조건 하에 1-negl(n) 확률로 암호화된 비트 복원 확인
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Cryptanalysis of a Candidate Witness Encryption Scheme for Affine Determinant Programs
본문 미리보기
At ITCS 2020, Bartusek, Ishai, Jain, Ma, Sahai, and Zhandry proposed a framework for witness encryption based on affine determinant programs and gave a concrete witness encryption candidate. Yao, Chen, and Yu later broke the separate ADP-based indistinguishability-obfuscation candidate, while noting that their attack did not apply to the witness-encryption construction. More recently, Soukhanov et al. proposed witness encryption from arithmetic affine determinant programs. Soukhanov subsequen
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 10:58AI 초안
