스위프트

스위프트
일반
디자이너	바딤 류바셰프스키, 다니엘레 미첸시오, 크리스 페이커트, 알론 로젠
초간출판	2008
관련	FFT 기반 알고리즘

암호학에서 SWIFT는 입증 가능한 보안 해시함수의 집합이다. 그것은 빠른 푸리에 변환(FFT)의 개념을 기반으로 한다. SWIFT는 FFT를 기반으로 한 최초의 해시함수는 아니지만 보안성에 대한 수학적 증거를 제공함으로써 스스로를 차별화한다. 또한 LLL 기반 감소 알고리즘을 사용한다. SWIFT에서 충돌을 찾는 것은 적어도 최악의 경우 주기/이상 격자에서 짧은 벡터를 찾는 것만큼 어렵다는 것을 알 수 있다. SWIFT는 어려운 수학 문제의 최악의 시나리오에 보안 감소를 부여함으로써 대부분의 다른 암호해시함수보다 훨씬 강력한 보안보증을 제공한다.

다른 많은 보안 해시함수와 달리 알고리즘은 3.2GHz Intel Pentium 4에서 40Mbit/s의 처리량을 낼 수 있어 상당히 빠르다. SWIFT는 바람직한 암호 및 통계 속성을 많이 만족하지만, 「다목적」 암호 해시함수가 되도록 설계되지 않았다. 예를 들어, 이것은 유사 함수가 아니며, 임의의 신탁을 적절한 인스턴스화하지 않을 것이다. 알고리즘은 충돌 저항의 증거를 제시하지 않는 대부분의 기존 해시함수보다 효율성이 떨어진다. 따라서, 그것의 실제 용도는 대부분 오랫동안 신뢰할 수 있어야 하는 디지털 서명과 같이 충돌 저항의 증거가 특히 중요한 애플리케이션에 있을 것이다.

SWIFFTX라 불리는 SWIFT의 개조가 NIST 해시함수 경연대회^[1] SHA-3 함수 후보로 제안되어 1라운드에서 거부되었다.^[2]

알고리즘

알고리즘은 다음과 같다.^[3]

다항식 변수를 $\alpha$ $\alpha$ 이라고 함
입력: $길이$ $m$ n $mn$ 의 $M$ $메시지$ M $M$
이항 계수가 있는 $R$ 특정 다항식 $링$ R $R$ 에서 $p_{i}$ $M$ $m$ 다항식 $m$ $p_{i}$ i ${\$ 의 집합으로 $M$ 변환하십시오.
SWIFT를 사용하여 $p_{i}$ 각 $p_{i}$ $p_{i}$ ${\$ 의 Fourier 계수를 계산한다.
$a_{i}$ 되고 SWIFT 계열에 $의존하도록$ i {\displaystyle a_ ${i}$ 의 $a_{i}$ 푸리에 계수를 정의하십시오 $.$
포인트-wise는 Fourier 계수 $p_{i}$ $p_{i}$ {\ $displaystyle$ p_ ${i$ }를 $p_{i}$ $각$ i {\ $displaystyle$ $a_$ ${$ $a_{i}$ }의 Fourier 계수로 곱한다 $i$
역 FFT를 사용하여 도 $<2n$ > $<2n$ $<2n$ 의 $f_{i}$ m ${\$ 를 $m$ 구하십시오 $<2n$
계산 $f=\sum _{i=1}^{m}(f_{i})$ = $f=\sum _{i=1}^{m}(f_{i})$ i $f=\sum _{i=1}^{m}(f_{i})$ = $f=\sum _{i=1}^{m}(f_{i})$ $f=\sum _{i=1}^{m}(f_{i})$ i $f=\sum _{i=1}^{m}(f_{i})$ ) $f=\sum _{i=1}^{m}(f_{i})$ $p$ p $p$ 및 $p$ $\alpha ^{n}+1$ + 1 ${\displaystyle \alpha ^{n}+1$
$f$ $f$ 을(를) $n\log(p)$ $n\log(p)$ $n\log(p)$ ) $n\log(p)$ 비트로 $f$ $n\log(p)$ 변환하여 출력한다.

4단계에서 FFT 작동은 반전하기 쉽고 확산, 즉 입력 비트를 혼합하기 위해 수행된다.
6단계의 선형 결합은 입력을 압축하기 때문에 혼동을 초래한다.
이것은 알고리즘이 하는 일에 대한 높은 수준의 설명일 뿐이며, 최종적으로 고성능 알고리즘을 산출하기 위해 더 높은 수준의 최적화가 사용된다.

예

n = 64, m= 16, p=257 매개변수에 대한 구체적인 값을 선택한다. For these parameters, any fixed compression function in the family takes a binary input of length mn = 1024 bits (128 bytes), to an output in the range $\mathbb {Z} _{p}^{n}$ , which has size $p^{n}=257^{64}$ . An output in ${\displaystyle \mathbb {Z} _$ ${p}^{n}}}$ 은(는) 528비트(66바이트)로 쉽게 표현할 수 있다 $\mathbb {Z} _{p}^{n}$ .

대수적 설명

그 SWIFFT 기능이 다항식환 R{R\displaystyle}에 대한 단순 대수 표현으로. 이러한 기능들의 가족 세가지 주요 매개 변수:2의 n{n\displaystyle} 힘, m을, 0{\displaystyle m>0}은 작은 정수 및 p을 해 주세요;0{\displaystyle p>0}b에 따라 묘사될 수 있계수 e (꼭 프라임은 아니지만, 프라임을 선택하기에 편리하다.) Define $R$ to be the ring $R=\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ , i.e., the ring of polynomials in $\alpha$ having integer coefficients, modulo $p$ and $\alpha ^{n}+1$ . R{R\displaystyle}의 한 요소 정도의 다항식, n{\displaystyle<>n}}Zp(_{p}에 계수. 그 SWIFFT은 가정에서 특정 기능 m{m\displaystyle}고정 요소를 1,…, R{\displaystyle a_{1},\ld ∈ m으로 지정된 작성할 수 있다.ots,링 $R$ $R$ 의 $a_{1},\ldots ,a_{m}\in R$ $a_{m}\in$ R $R$ 이를 승수라고 한다. 함수는 링 R에 대한 다음 방정식에 해당한다.

$\sum _{i=1}^{m}(a_{i}\cdot x_{i})$

$x_{1},\ldots ,x_{m}\in R$ $x_{1},\ldots ,x_{m}\in R$ , $x_{1},\ldots ,x_{m}\in R$ … , $x_{1},\ldots ,x_{m}\in R$ x $x_{1},\ldots ,x_{m}\in R$ $x_{1},\ldots ,x_{m}\in R$ R $x_{1},\ldots ,x_{m}\in R$ 는 $x_{1},\ldots ,x_{m}\in R$ 이진 계수를 가진 다항식이며, 길이 $m$ $n$ $mn$ 의 이진 입력에 해당한다 $mn$

다항식 제품 계산

위의 식을 계산하기 위해서는 다항식 제품 $a_{i}\cdot x_{i}$ $a_{i}\cdot x_{i}$ $a_{i}\cdot x_{i}$ $a_{i}\cdot x_{i}$ ${\$ 을 계산하는 것이 주된 문제 $a_{i}\cdot x_{i}$ 이러한 제품을 계산하는 빠른 방법은 콘볼루션 정리에 의해 주어진다. 이것은 특정 제한에 따라 다음과 같은 조건이 유지된다고 말한다.

{\mathcal {F}\{f*g\}={\mathcal {F}\{f\}\cdot {\mathcal {F}\{g\}}}}

여기서 ${\mathcal {F}}$ ${\$ 은(는) 푸리에 변환을 나타내고 ${\mathcal {F}}$ , $\cdot$ and ${\displaystyle \cdot$ }은 $($ 는) 포인트와 같은 제품을 나타낸다 $\cdot$ . 일반적으로 콘볼루션 정리 $*$ $*$ 은 $*$ (는) 곱셈이 아니라 콘볼루션을 나타낸다. 그러나 다항식 곱셈이 경련임을 보여줄 수 있다.

고속 푸리에 변환

Fourier 변환을 찾으려면 $O(n\log(n))$ $O(n\log(n))$ log $O(n\log(n))$ ( $O(n\log(n))$ $O(n\log(n))$ $O(n\log(n)$ 시간 내에 $O(n\log(n))$ 변환을 찾는 FFT(fast Fourier transform)를 사용하십시오. 이제 곱셈 알고리즘은 다음과 같다. FFT를 사용하여 각 다항식의 푸리에 계수를 한 번에 계산한다. 그런 다음 두 다항식의 각각의 푸리에 계수를 점으로 곱하고, 마지막으로 역 FFT를 사용하여 도 $<2n$ < $<2n$ $<2n$ 의 다항식을 반환한다 $<2n$

숫자-이론적 변환

일반적인 푸리에 변환 대신 SWIFT는 숫자-이성 변환을 사용한다. 숫자-이론적 변환은 통합의 복잡한 뿌리 대신 $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ ${\$ 의 통합의 뿌리를 사용한다. 이 일을 하기 위해서는 $\mathbb {Z} _{p}$ $\mathbb {Z} _{p}$ ${\$ 가 유한한 분야임을 $\mathbb {Z} _{p}$ 확실히 하고, 이 분야에는 원초적인 통일의 2n^th 뿌리가 존재한다는 것을 확실히 할 필요가 있다. $p-1$ - $p-1$ 을 $p-1$ $2n$ ${\displaystyle 2n$ $p-1$ 으로 나누는 $2n$ p {\ $displaystyle p-1$ } p $p-1$ - 1을 p - 1로 나누도록 $p$ ${\$ $displaystyle p-1$ }p를 $p$ 프라임으로 설정하면 된다.

파라미터 선택

m,p,n 매개변수는 다음과 같은 제한을 받는다.

n은 반드시 2의 힘이어야 한다.
p는 prime이어야 한다.
p-1은 2n의 배수여야 함
$\log(p)$ $\log(p)$ ( $\log(p)$ ) $\log(p)$ 은(는) m보다 작아야 $\log(p)$ 함(출력이 입력보다 작지 않아야 함)

가능한 선택은 n=64, m=16, p=257이다. 우리는 약 40Mbit/s의 처리량과 충돌 발견을 위한 약 $2^{106}$ 의 $2^{106}$ ${\$ 2 $^{106}$ 의 보안, 그리고 $2^{106}$ 512비트의 다이제스트 크기를 얻는다.

통계적 속성

(범용 해싱). SWIFT 기능군은 보편적이다. 즉, 고정 $고유$ x, $x^{}$ $'$ ${\$ x $,x$ 에 대해 $f(x)=f(x')$ ( $f(x)=f(x')$ ) $f(x)=f(x')$ = $f(x)=f(x')$ $f(x)=f(x')$ x $f(x)=f(x')$ ) ${\$ $displaystyle f}$ 의 무작위 선택에서 f $($ ) = f ( $f(x)=f(x')$ ′ $f(x)=f(x')$ ) {\ $displaystyf(x)=f(x')}$ 가 범위 $f(x)=f(x')$ 크기의 역일 확률이다.
(정규성). 압축함수의 SWIFT 계열은 정규적이다. 도메인에서 무작위로 균일하게 $x$ $x$ 한입력 x {\ $displaystyle x}$ 에 대해 출력 f $f(x)$ ( $f(x)$ ) {\ $displaystyle$ f $(x)}$ 이 범위에 $f(x)$ 걸쳐 균일하게 분포하는 경우 함수 $f$ {\ $displaystyle f}$ 은 $f$ 정규적이라고 한다.
(랜덤성 추출기). SWIFT는 무작위 추출기다. 해시 테이블과 관련 어플리케이션의 경우, 입력이 균일하지 않은 경우에도 해시함수의 출력이 균일하게(또는 가능한 한 균일하게 가깝게) 분배되는 것이 보통 바람직하다. 이러한 보증을 제공하는 해시함수는 입력의 불균일 랜덤성을 균일하게 분포된 출력(대부분)으로 증류하기 때문에 랜덤성 추출기라고 알려져 있다. 형식적으로 무작위 추출은 사실상 기능 계열의 속성이며, 여기서 하나의 기능이 무작위로 선택된다(그리고 입력에 대해 망각된다).

암호화 속성 및 보안

SWIFT는 선형성으로 인해 유사성이 아니다. $당사$ 제품군의 기능 f $f$ {\ $displaystyle$ f}과(와) 두 $x_{2}$ x $x_{1}$ 1 {\ $displaystyle x_$ $x_{1}+x_{2}$ }, x $x_{1}+x_{2}$ 2 {\ $displaystyle$ x_ ${1$ }+ $x_{2$ $}$ 와 $x_{2}$ $x_{1}+x_{2}$ $x_{1}+x_{2}$ $}}}$ 또한 유효한 입력이며 $x_{1}+x_{2}$ , $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ ( $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ ) $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ + f $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ ( $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ 2 $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ ) $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ = f $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ ( x $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ + $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ 2 $){\displaystyle f(x_{1})+f(x_{2})=f(x_{1}+x_{2}})}$ 가 있다 $f(x_{1})+f(x_{2})=f(x_{1}+x_{2})$ 이 관계는 무작위 함수에 대해 유지될 가능성이 매우 낮기 때문에 적들은 우리의 함수와 무작위 함수를 쉽게 구별할 수 있다.
저자들은 SWIFT 함수가 임의의 신탁처럼 동작한다고 주장하지 않는다. 함수는 진정으로 임의함수처럼 행동하면 임의의 신탁처럼 행동한다고 한다. 이는 함수가 고정되고 공개적이라는 점에서 유사성과는 다르다.
SWIFT 패밀리는 주기/이상 격자에서 짧은 벡터를 찾기가 가장 어려운 경우에 대해 비교적 가벼운 가정 하에 (무증증상으로) 내충돌성이 있다. 이것은 가족 또한 제2의 이미지 내성이 있다는 것을 암시한다.

이론적 보안

SWIFT는 입증 가능한 보안 암호해시함수의 예다. 대부분의 보안 증명과 마찬가지로, SWIFT의 보안 증명은 수학 문제를 풀기 어려운 특정 문제로의 축소에 의존한다. 이는 SWIFT의 보안이 이 수학 문제의 난이도에 크게 의존한다는 것을 의미한다는 점에 유의한다.

SWIFT 사례의 감소는 주기/이상 격자에서 짧은 벡터를 찾는 문제에 있다. 다음과 같은 조건이 유지된다는 것을 증명할 수 있다. $f$ $f$ 이(가) 제공한 임의 버전의 SWIFT에 대해 실현 가능한 $시간$ T $f$ $T$ 및 확률 $p$ ${\displaystyle$ p $} 내$ 에서 f $f$ 에서 충돌을 찾을 수 있는 $f$ 알고리즘이 있다고 가정합시다 $p$ 알고리즘은 패밀의 작지만 눈에 띄는 부분에서만 작동하도록 허용된다.y 스위프트. Then we can find also an algorithm $f_{2}$ which can always find a short vector in any ideal lattice over the ring $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ in some feasible time $T_{2}$ , depending on $T$ $그리고$ p ${\displaystyle$ p $p$ 즉, SWIFT에서 충돌을 발견하는 것은 $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ p $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ / ( $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ n + 1 $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ ) ${\displaystyle \mathb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ 를 넘는 격자에서 짧은 벡터를 찾는 최악의 시나리오만큼 어렵다는 것을 의미한다 $\mathbb {Z} _{p}[\alpha ]/(\alpha ^{n}+1)$ 현재 짧은 벡터를 찾는 가장 빠른 알고리즘은 $모두$ n $n$ 에서 지수적이다 $n$ 이 알고리즘은 SWIFT의 보안이 취약한 "취약 인스턴스"의 유의한 집합이 없음을 보장한다. 이 보장은 대부분의 다른 가능한 보안 해시함수에 의해 주어지지 않는다.

실용적인 보안

알려진 작업 공격은 일반화된 생일 공격인데, 이 공격에는 2번의¹⁰⁶ 조작이 필요하고, 역습 공격에는⁴⁴⁸ 2번의 조작이것은 뒤집기 공격이다. 이것은 보통 적에 의한 공격을 실현 불가능한 것으로 간주된다.

참조

^ Daniele Micciancio; Yuriy Arbitman; Gil Dogon; Vadim Lyubashevsky; Chris Peikert; Alon Rosen (2008-10-30). "SWIFFTX: A Proposal for the SHA-3 Standard" (PDF). Retrieved 2017-03-03.
^ "Second Round Candidates". National Institute of Standards and Technology. 2009-07-16. Archived from the original on 2017-06-04. Retrieved 2017-03-03.{{cite web}}: CS1 maint : bot : 원본 URL 상태 미상(링크)
^ Vadim Lyubashevsky; Daniele Micciancio; Chris Peikert; Alon Rosen (2008-02-21). "SWIFFT: A Modest Proposal for FFT Hashing" (PDF). Retrieved 2017-03-03.

[1] Daniele Micciancio; Yuriy Arbitman; Gil Dogon; Vadim Lyubashevsky; Chris Peikert; Alon Rosen (2008-10-30). "SWIFFTX: A Proposal for the SHA-3 Standard" (PDF). Retrieved 2017-03-03.

[2] "Second Round Candidates". National Institute of Standards and Technology. 2009-07-16. Archived from the original on 2017-06-04. Retrieved 2017-03-03.{{cite web}}: CS1 maint : bot : 원본 URL 상태 미상(링크)

[3] Vadim Lyubashevsky; Daniele Micciancio; Chris Peikert; Alon Rosen (2008-02-21). "SWIFFT: A Modest Proposal for FFT Hashing" (PDF). Retrieved 2017-03-03.

[1]

[2]

[3]

Search