이 논문은 다수결(MAJ)과 XOR 조합 술어를 사용하는 골드라이히 의사난수생성기(PRG)의 실질적·점근적 안전성을 분석한다. 저자들은 씨앗 위치 일부를 추측해 다수결 입력이 고정되는 출력을 모아 잡음 없는 희소 선형방정식을 얻는 '결정적 풀링 복구(DPR)' 기법을 제안한다. ToSC 2025에 발표된 MAJ7⊕XOR4 챌린지(씨앗 길이 1024)에 DPR을 적용한 결과, 약 2^109.71 연산으로 복구가 가능해 주장된 128비트 보안 수준에 미달함을 보였다. 나아가 부분 다수결 편향을 이용하는 '편향 증폭 풀링 복구(BAPR)' 기법을 통해 특정 지역성 조건에서 지수함수적 보안이 성립하지 않음을 증명했다.
- •MAJ-XOR 조합 술어 기반 골드라이히 PRG의 구체적 보안성 분석
- •DPR 기법으로 MAJ7⊕XOR4 챌린지를 2^109.71 연산에 복구, 128비트 보안 미달
- •부분 다수결 편향 이용한 BAPR 기법으로 지수 보안 성립 안 함을 증명
- •대안 술어에서도 악용 가능한 아핀 구조와 잉여 제약 발견
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Cryptanalysis of Goldreich's PRGs with MAJ–XOR Predicates
- 1.Goldreich PRG의 MAJ-XOR 술어에 대한 새 공격 DPR(결정적 풀링 복구) 제안
- 2.ToSC 2025 MAJ7⊕XOR4 챌린지를 2^109.71 연산으로 복구, 128비트 보안 하회
- 3.부분 다수결 편향 이용한 BAPR로 특정 영역의 지수적 보안성 자체를 반증
- 4.제안된 대체 술어에서도 악용 가능한 아핀 구조·잉여 제약 추가 확인
왜 중요한가?
Goldreich PRG는 경량 프로토콜의 기반 가정인데, 특정 술어 조합의 실질 보안이 주장치보다 낮음을 실증해 술어 선택 기준 재검토가 필요함을 보여준다.
암호학의 핵심 구성 요소인 Goldreich의 의사 난수 생성기(PRG)에 대한 암호 분석 연구는 국내 블록체인 시스템의 근본적인 보안 취약점을 이해하는 데 필수적입니다. 이러한 기초 연구는 최신 암호화 프로토콜의 안전성을 평가하고 개선하는 데 중요한 통찰력을 제공합니다.
본문 미리보기
Goldreich's pseudorandom generators (PRGs) expand a secret seed by evaluating a fixed low-locality predicate on random subsets of its bits. We study the concrete and asymptotic security of constructions whose local predicate combines majority with XOR. We introduce Deterministic Pooled Recovery (DPR), which guesses a set of seed positions and pools the outputs whose majority inputs are forced by the guess. The selected outputs yield noiseless sparse linear equations. For the proposed \(\operator
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
