다변량 암호화

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 찾기 : "다변량 암호화"– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2022년 2월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

다변량 암호법은 유한 $F$의$$다변량 $다항식$을 기반으로 하는 비대칭 암호$$원형을 총칭하는 용어입니다. 경우에 따라 이러한 다항식은 지면 및 확장 필드 모두에서 정의될 수 있습니다.다항식의 차수가 2인 경우 다변량 4차 방정식에 대해 설명합니다.다변량 다항 방정식의 해결 시스템은 ^[1]NP-완전인 것으로 입증되었습니다.그렇기 때문에 이러한 스킴은 종종 양자화 후 암호화에 적합한 후보로 간주됩니다.다변량 암호 기술은 설계와 암호 분석 측면에서 매우 생산적이었습니다.전반적으로, 상황은 이제 더 안정되었고 가장 강력한 계획들은 시간의 시험을 견뎌냈다.다변량 방식이 사후 양자 알고리즘 중에서 가장 짧은 서명을 제공하기 때문에 다변량 암호화가 서명 체계를 구축하는 접근 방식으로서 더 성공적이라는 것은 일반적으로 인정된다.

역사

마츠모토 츠토무와 이마이 히데키(1988)는 유로크립트 회의에서 이른바 C* 스킴을 발표했다.C*는 Jacques Patarin(1995)에 의해 깨졌지만, 마츠모토와 이마이(Imai)의 일반 원칙은 개선된 제안의 세대를 고무시켰다.이후 연구에서, "숨겨진 단항 암호 체계"는 자크 파타린에 의해 개발되었다.접지 및 확장 필드를 기반으로 합니다.1996년 파타린이 개발한 "숨겨진 필드 방정식"(HFE)은 오늘날에도 여전히 인기 있는 다변량 체계이다[P96].HFE의 보안은 직접 Gröbner 기반 공격(FJ03, GJS06), 키 회복 공격(Kipnis & Shamir 1999) [BFP13] 등을 시작으로 철저히 조사되었다.HFE의 플레인버전은 시큐어 파라미터가 비실용적인 스킴으로 이어진다는 점에서 실질적으로 파손된 것으로 간주됩니다.그러나 마이너스 변종과 식초 변종과 같은 HFE의 일부 간단한 변종은 알려진 모든 공격에 대해 기본 HFE를 강화할 수 있게 한다.

HFE 외에도 파타린은 다른 방법을 개발했다.1997년에 그는 Aviad Kipnis 및 Louis Goubin(1995년 Kipnis, Patarin & Goubin)과 협력하여 "Balanced Oil & Segment"를, 1999년에 "Unbalanced Oil and Segment"를 발표했다: 목표 없음: CITREFKipnis PatarinGoubin1995(도움직임).

건설

다변량 4진법에는 공개 키와 개인 키가 포함됩니다.개인 키는 두 개의 아핀 변환(S 및 T)과 반전하기 쉬운 2차 맵 $P{\displaystyle {}^{}}$δ: ${\displaystyle {}^{}}$ ${\displaystyle m^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ \ $displaystyle$ P$'\colon$ F$^{m}\rightarrow$ F$^{n$로 구성됩니다. 우리는 아핀 끝 $형상{\displaystyle }$ S${\displaystyle {}^{}}$ ${\displaystyle F^{}}$의${\displaystyle }n{\displaystyle }$ ×$$ \ $displaystyle$ n$\$$times$ n :${\displaystyle M_{}}$ S$(\$ 및$$ v ${\displaystyle {}^{}}$ ${\displaystyle {}_{}}$ F$$(\$displaystyle v_{S}\in$ F$^{n})$에 의한 시프트 벡터 및 T${\displaystyle :}$ ${\displaystyle F^{}}$ m ${\displaystyle {}^{}}$ F $(\$ T\$colon F^{m}\$오른쪽 $화살표$ F$^{m$에 $의한{\displaystyle }$ 시프트 벡터. 즉,

• $디스플레이$$M_{S}x+v_{S}$ 및$$
• ${\displaystyle T}$(${\displaystyle y}$ ) ${\displaystyle =}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{}^{}}$ y ${\displaystyle +}$ + ${\displaystyle v_{}}$T ( \ $displaystyle$T ( y ) =$M$_ { $T$} $y$' + v$_$ {$T$} 。

트리플${\displaystyle }$( ${\displaystyle {}^{}}$-${\displaystyle {}^{}{1}^{}}$, ${\displaystyle {{}^{}}^{}}$ ${\displaystyle {-}^{}}$ -${\displaystyle {}^{}{}^{}}$ , T${\displaystyle {}^{}}$- 1 $){$ $displaystyle$ ($S$^ { - $1$, { P ' }^{ - $1$, T^ { - 1$$} )는 트랩도어라고도 불리는 개인키입니다.공개 키는 P ${\displaystyle =}$ ${\displaystyle S}$ ${\displaystyle \circ }$ ${\displaystyle {}^{}\prime }$ ${\displaystyle T}${ $displaystyle$ P$=S\circ$ P$'\circ$ T$}$로, 트랩도어를 인식하지 않으면 반전하기 어렵습니다.

서명

시그니처는 개인 키를 사용하여 생성되며 다음과 같이 공개 키를 사용하여 검증됩니다.메시지는 기존의 해시함수를 통해 y${\displaystyle f^{}}$ F$$n \ $displaystyle$y \ $in$ F^ { $n$}의 벡터에 해시됩니다.시그니처는

$displaystyle$$T^{-1}\left({P'}^{-1}\left(S^{-1}(y$)\right$)\right$

서명된 문서의 수신자는 공개키 P를 소지하고 있어야 합니다.해시$y를 계산$하여 $시그니처{\displaystyle }$ x$($${\displaystyle x}$$)$$(x$) =$y(x$를 $만족$하는지 확인합니다.

적용들

이 섹션은 어떠한 출처도 인용하지 않습니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 섹션의 개선에 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.(2018년 8월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

• 기름과 식초의 불균형
• 숨김 필드 방정식
• SFLASH by NESSIE
• 레인보우
• TTS
• 석영
• 쿼드(암호화)
• 4개의 다변량 암호화 서명 방식(GeMMS, LUOV, Rainbow 및 MQDSS)이 NIST 사후 양자 경쟁의 2라운드에 진출했습니다.^[2] 보고서의 슬라이드 12를 참조하십시오.

레퍼런스

• [BFP13] L. Bettale, Jean-Charles Faugere 및 L. Perret, HFE, Multi-HFE 및 홀수 및 짝수 특성을 위한 변형 암호 분석.DCC'13
• [FJ03] 장 샤를 포제르와 A.Joux, Gröbner Bases를 사용한 HFE(Hidden Field 방정식) 암호 시스템의 대수적 암호 분석.암호'03
• [GJS06] L. Granboulan, Antoine Joux, J. Stern: HFE를 반전시키는 것은 준다중칭입니다.암호'06
• Kipnis, Aviad; Patarin, Jacques; Goubin, Louis (1999). "Unbalanced Oil and Vinegar Signature Schemes". Advances in Cryptology — EUROCRYPT '99. Berlin, Heidelberg: Springer. doi:10.1007/3-540-48910-x_15. ISBN 978-3-540-65889-4. ISSN 0302-9743. MR 1717470.
• Kipnis, Aviad; Shamir, Adi (1999). "Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization". Advances in Cryptology — CRYPTO' 99. Berlin, Heidelberg: Springer. doi:10.1007/3-540-48405-1_2. ISBN 978-3-540-66347-8. ISSN 0302-9743. MR 1729291.
• Matsumoto, Tsutomu; Imai, Hideki (1988). "Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption". Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. doi:10.1007/3-540-45961-8_39. ISBN 978-3-540-50251-7. ISSN 0302-9743. MR 0994679.
• Patarin, Jacques (1995). "Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'88". Advances in Cryptology — CRYPT0' 95. Lecture Notes in Computer Science. Vol. 963. Berlin, Heidelberg: Springer. pp. 248–261. doi:10.1007/3-540-44750-4_20. ISBN 978-3-540-60221-7. ISSN 0302-9743. MR 1445572.
• [P96] 자크 파타린, 숨겨진 필드 방정식(HFE) 및 다항식(IP)의 동형사상: 두 개의 새로운 비대칭 알고리즘 패밀리(확장 버전);유로크립트 '96
• Christopher Wolf와 Bart Prenel, 다변량 2차 방정식의 문제에 기초한 공개키 체계 분류법; 현재 버전: 2005-12-15
• Braeken, Christopher Wolf, Bart Prenel, 불균형의 오일과 식초의 안전성에 관한 연구, 최신판: 2005-08-06
• Jintai Ding 연구 프로젝트:Rainbow 및 TTS 다변량 공개키 서명방식에 관한 암호해석
• 저비용 스마트카드를 위한 고속 비대칭 시그니처 스킴인 Jacques Patarin, Nicolas Courtois, Louis Goubin, SFLASH.기본 사양 및 지원 문서.
• Bo-Yin Yang, Chen-Mou Chen, Bor-Rong Chen 및 Jiun-Ming Chen, 저자원 임베디드 시스템에서 최소화된 다변량 PKC 구현, 2006년
• 양보잉, 첸지운밍, 첸옌훙, TTS: 저비용 스마트 카드의 고속 서명, 2004년,
• 니콜라스 T. HFE, Quartz 및 Sflash와 같은 다변량 다항식 스킴의 Courtois, 쇼트 시그니처, Provable Security, Generic Attacks 및 Computational Security, 2005
• 알프레드 J. 메네지스, 폴 C. 반 우르쇼트, 스콧 A.Vanstone, 응용암호화 핸드북, 1997

외부 링크

• [1] HFE 공개키 암호화 및 서명
• [2] HFEBoost