의사난수 코드(PRC)는 코드워드가 균일 문자열과 계산적으로 구분되지 않는 키 기반 오류정정 코드다. 이 논문은 공개키에 의존하며 전송된 코드워드에도 의존할 수 있는 적대적 삭제 채널에 대한 고정 알파벳 공개키 PRC를 연구한다. 두 개의 독립 균일 q진 문자열의 점근적 정규화 최장 공통부분수열 길이를 감마로 정의할 때, 모든 고정 q≥2에 대해 단일 출력 디코더를 가진 다중 메시지 공개키 PRC는 delta가 1-감마보다 큰 모든 delta-삭제 채널에 견고할 수 없음을 증명했다. q=2인 경우 현재 엄격한 하한(감마≥0.792665992)에 따라 delta>0.207334008인 모든 상수 delta가 배제된다. 증명은 비밀키 없이 정보이론적 충돌 논증만으로 성립하며, 리스트 디코딩으로도 확장해 임계값이 메시지 수 증가에 따라 1/2에 근접함을 보였다.
- •공개키 의존적 적대적 삭제 채널에 대한 고정 알파벳 의사난수 코드(PRC)의 근본적 한계를 증명
- •모든 고정 q≥2에서 delta가 1-감마(LCS 길이 비율)보다 크면 견고한 다중 메시지 PRC 불가
- •이진(q=2) 경우 delta>0.207334008인 모든 상수 delta에서 견고성 불가능을 입증
- •증명은 비밀키 없이 정보이론적 충돌 논증만으로 성립, 리스트 디코딩까지 확장
- •임계값이 메시지 수 증가에 따라 1/2에 근접하는 경향을 확인
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes
- 1.공개키 의존적 적대적 삭제채널에 대한 고정알파벳 다중메시지 유사난수코드(PRC)의 강건성 한계를 증명
- 2.q진 균일 문자열의 점근적 정규화 최장공통부분열 길이(γ_q^LCS) 기준 강건성 불가능 임계값 도출
- 3.이진(q=2)의 경우 하한 γ_2≥0.792665992 기준 δ>0.207334008인 모든 삭제율서 강건성 불가능
- 4.리스트 디코딩 확장 시에도 임계값이 1/2에 근접함을 규명, 공개키 의존 채널 특유의 결과
왜 중요한가?
워터마킹 등에 쓰이는 유사난수코드가 견딜 수 있는 삭제공격의 근본적 한계를 수치로 제시해, 관련 프로토콜 설계 시 현실적인 강건성 기대치를 설정하는 데 기여한다.
본문 미리보기
arXiv:2609.02943v1 Announce Type: new Abstract: A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings. We study public-key PRCs over fixed alphabets against adversarial deletions, where the deletion channel may both depend on the public encoding key and the transmitted codeword. Let $\gamma_q^{\mathrm{LCS}}$ denote the asymptotic normalised longest-common-subsequence length of two independent uniform $q$-ary strin
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
