이 연구는 일반적인 소수 위수 순환군을 사용하는 고전적 제네릭 군 모델에서 NP에 대한 증인 암호화(witness encryption)를 무조건적으로 구성했다. 크기 n의 SAT 인스턴스에 대해 암호화 알고리즘은 다항 시간(poly(n))에 실행되며, 만족 가능한 대입값이 있으면 다항 시간에 오류 확률 2^-n^Ω(1)로 복호화가 가능하다. 만족 가능한 대입값이 존재하지 않을 경우, 최대 n^Θ(log n)회의 군 질의를 수행하는 모든 제네릭 공격자의 구별 우위는 n^-Θ(log n) 이하로 제한된다. 연구 과정에서 연구진은 랜덤화된 다항 시간 축소 아래 동차 MinRank 문제에 대한 최초의 초상수 배수 NP-난이도 근사불가능성 결과도 증명했으며, 이는 랭크-1 증인이 불리언 우측 인자를 가질 때도 로그 규모 간극을 달성한다.
- •일반 소수 위수 순환군을 사용하는 고전적 제네릭 군 모델에서 NP에 대한 증인 암호화를 무조건적으로 구성
- •크기 n의 SAT 인스턴스에서 암호화는 다항 시간, 만족 대입값 있을 시 오류확률 2^-n^Ω(1)로 복호화 가능
- •만족 불가능한 경우 n^Θ(log n)회 질의하는 공격자의 구별 우위도 n^-Θ(log n) 이하로 제한
- •부산물로 동차 MinRank 문제에 대한 최초의 초상수 배수 NP-난이도 근사불가능성 결과를 증명
- •랭크-1 증인이 불리언 우측 인자를 가질 때도 로그 규모의 근사 간극을 달성함을 보임
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Witness Encryption via Prime-Order Generic Groups
- 1.소수위수 순환군만으로 일반군 모델에서 NP에 대한 witness encryption을 무조건적으로 구성
- 2.SAT 인스턴스 크기 n에서 암호화는 다항시간, 충족 배정이 있으면 다항시간 복호에 오류확률 2^-n^Ω(1)
- 3.충족 배정이 없으면 n^Θ(log n)회 질의하는 일반 공격자도 구분 우위가 n^-Θ(log n)에 불과함을 증명
- 4.부수적으로 동차 MinRank 문제에 대한 최초의 초상수 배율 NP-난해성 근사결과도 함께 증명
왜 중요한가?
복잡한 격자·다중선형사상 가정 없이 표준적인 일반군 모델만으로 witness encryption을 구성해, 암호학의 오랜 난제였던 이 원시함수의 최소 가정 하한을 크게 낮춘 이론적 성과다.
NP 문제에 대한 증인 암호화를 구현한 이 연구는 암호학의 중요한 이론적 진보로, 영지식 증명 및 보안 컴퓨테이션의 미래를 엿보게 합니다. 블록체인 및 디지털 자산 보안 분야에서 기술 혁신을 추구하는 한국은 이러한 근본적인 암호학 연구 동향을 주시해야 합니다. 이는 당장 상용화되지 않더라도, 장기적으로 국내 블록체인 기술의 보안성과 효율성을 한 단계 끌어올릴 수 있는 기반 지식이 될 것입니다.
본문 미리보기
arXiv:2609.18275v1 Announce Type: new Abstract: We unconditionally construct witness encryption for NP in the classical generic-group model, using an ordinary cyclic group of prime order. For SAT instances of size $n$, the encryption algorithm runs in time poly$(n)$, and any satisfying assignment can be used to decrypt in poly$(n)$ time with correctness error $2^{-n^{\Omega(1)}}$. If no satisfying assignment exists, then every generic adversary making at most $n^{\Theta(\log n)}$ group queries
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
