파일리어 암호체계

1999년 파스칼 파일리에가 발명하고 이름을 딴 파일리어 암호시스템은 공개키 암호화를 위한 확률론적 비대칭 알고리즘이다.n번째 잔류물 등급 계산 문제는 계산적으로 어렵다고 여겨진다.의사결정 복합 잔존도 가정은 이 암호 시스템의 기반이 되는 난해성 가설이다.

이 체계는 가법동형 암호체계로서, $m_{1}$ 와 $m_{1}$ 1 ${\$ $}},$ $m_{2}$ 2 $m_{1}+m_{2}$ {\ $displaystyle m_{1$ }+m_ ${$ 2}}의 암호화만을 고려할 때 $m_{2}$ $m_{1}+m_{2}$ 1 + $m_{1}+m_{2}$ $m_{1}+m_{2}$ {\ $displaystyle m_{1}+m_{$ 2}}의 암호화를 계산할 수 있다는 것을 의미한다 $m_{1}+m_{2}$

알고리즘.

이 계획은 다음과 같다.

키 생성

$\gcd(pq,(p-1)(q-1))=1$ $\gcd(pq,(p-1)(q-1))=1$ ( $\gcd(pq,(p-1)(q-1))=1$ - $\gcd(pq,(p-1)(q-1))=1$ ) $\gcd(pq,(p-1)(q-1))=1$ = 1 ${\displaystyle$ q $)=$ $1}$ 과 같은 큰 소수 p ${\$ displaystyle $q}$ 과 $p$ $q$ {\ $displaystyle$ $\gcd(pq,$ ( $p-1)($ q-1 $)=$ 1}처럼 서로 독립적으로 $q$ 임의로 큰 소수 $p$ {\ $d$ $\gcd(pq,(p-1)(q-1))=1$ 를 선택하십시오. 이 속성은 동일하면 확실하다.^[1]
계산 $n=pq$ $n=pq$ = $n=pq$ $n=pq$ $n=pq$ 및 $\lambda =\operatorname {lcm} (p-1,q-1)$ = $\lambda =\operatorname {lcm} (p-1,q-1)$ $\lambda =\operatorname {lcm} (p-1,q-1)$ - $\lambda =\operatorname {lcm} (p-1,q-1)$ , $\lambda =\operatorname {lcm} (p-1,q-1)$ - $\lambda =\operatorname {lcm} (p-1,q-1)$ ) ${\displaystyle \lambda =\operatorname {lcm}(p-1,q-1$ lcm는 최소공통 다수를 의미한다.
임의 정수 $g$ $g$ 을(를) 선택하십시오. 여기서 $g$ $g\in \mathbb {Z} _{n^{2}}^{*}$ $g\in \mathbb {Z} _{n^{2}}^{*}$ Z $g\in \mathbb {Z} _{n^{2}}^{*}$ $g\in \mathbb {Z} _{n^{2}}^{*}$ ${\$ g\ $in \mathb$ { $Z} _{n^{2}}^{*}}}}}}}$
n $g$ ${\displaystyle$ $n}$ 이(가) $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ = $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ ( $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ ( G $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ ) $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ - $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ n ${\$ 의 순서를 나누도록 $n$ 하십시오.

여기서 기능

L

L

은(는)

L(x)={\frac {x-1}{n}}

L(x)={\frac {x-1}{n}}

)

L(x)={\frac {x-1}{n}}

=

L(x)={\frac {x-1}{n}}

-

L(x)={\frac {x-1}{n}}

{\

로 정의된다

L

.

L(x)={\frac {x-1}{n}}

{\frac {a}{b}}

{\

표기법은

a

b

의

a

모듈형 곱셈을 의미하는

b

b

이

a

아니라 b {\displaystyle

b}

로

나눈 {\

displaystyle

a}

의 몫

b

즉 최대 정수 값 v

v\geq 0

을 의미한다.

v\geq 0

a\geq vb

v\geq 0

을(를) 사용하여

a\geq vb

≥

a\geq vb

a\geq vb

a\geq vb

의 관계를 충족하십시오

a\geq vb

공용(암호화) 키는 $(n,g)$ ( $(n,g)$ , $(n,g)$ ) $(n,g)$ 입니다 $(n,g)$
비공개( $(\lambda ,\mu ).$ ) 키는 ( $(\lambda ,\mu ).$ , $(\lambda ,\mu ).$ $(\lambda ,\mu ).$ . ${\displaystyle$ (\ $lambda ,\mu$ ) 입니다. $}$

If using p,q of equivalent length, a simpler variant of the above key generation steps would be to set $g=n+1,\lambda =\varphi (n),$ and $\mu =\varphi (n)^{-1}{\bmod {n}}$ , where ${\displaystyle \varphi (n)=(p-1)(q-$ $1)}$ .^[1]

암호화

$0\leq m<n$ $m$ 을(를) 0 $0\leq m<n$ < $0\leq m<n$ ${\displaystyle 0\leq m<n})$ 에서 암호화하도록 두십시오 $m$ .
임의 $r$ $r$ 을(를) 선택하십시오. $0<r<n$ 서 $r$ 0 $0<r<n$ < $0<r<n$ < $0<r<n$ > $0<r<n$ {\ $displaystyle$ 0 $<r<n}$
$c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ = $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ r $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$ ${\$ }{\ $bmod$ }^{2 $}}:$

암호 해독

$c$ $c$ 을(를) 해독할 암호문이 되게 $c$ 하십시오. 여기서 c $c\in \mathbb {Z} _{n^{2}}^{*}$ Z $c\in \mathbb {Z} _{n^{2}}^{*}$ $c\in \mathbb {Z} _{n^{2}}^{*}$ $c\in \mathbb {Z} _{n^{2}}^{*}$ ${\$ c\ $in \mathb$ {Z $} _{n^{2}}^{*}}}}}}$
일반 텍스트 메시지를 다음과 같이 계산하십시오. $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ = $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ 2 $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ ) $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$ ${\$

원본에서^[2] 지적했듯이, 암호 해독은 "본질적으로 하나의 지수화 modulo n ${\$ n $^{2}}"$ 이다.

동형성

Paillier 암호 시스템의 주목할 만한 특징은 비결정적 암호화와 함께 그것의 동형질적 특성이다. (사용은 어플리케이션의 전자투표 참조)암호화 기능이 부가적으로 동형성이므로 다음과 같은 정체성을 설명할 수 있다.

일반 텍스트의 동형 추가

두 개의 암호문의 생산물은 해당 일반 텍스트의 합계로 해독할 것이다.

D(E(m_{1},r_{1})\cdot E(m_{2},r_{2}}{\bmod{n}^{n}}}=m_{1}+m_{2}{\bmod {n}\,},

일반

텍스트 상승 g

g

이(가) 있는 암호 텍스트의 곱은 해당 일반 텍스트의 합으로 해독된다

g

.

D(E(m_{1},r_{1})\cdot g^{m_{2}}:{\bmod{n}^{2}=m_{1}+m_{2}{\bmod {n}}\,

일반 텍스트의 동형 곱하기

일반 텍스트의 힘으로 상승된 암호 텍스트는 두 개의 일반 텍스트의 곱으로 해독된다.

D(E(m_{1},r_{1})^{m_{2}}:{\bmod{n}^{2}=m_{1}m_{2}{\bmod {n},\,

D(E(m_{2},r_{2})^{m_{1}{{1}{n}^{2}=m_{1}m_{2}{\bmod {n}}\,

보다 일반적으로, 상수 k로 올린 암호문은 일반 텍스트와 상수의 곱으로 해독된다.

D(E(m_{1},r_{1})^{k}{\bmod{n}^{2}=km_{1}{\bmod {n}}\,

그러나, Paillier 암호화로 두 개의 메시지를 볼 때, 개인 키를 모르는 상태에서 이러한 메시지의 제품의 암호화를 계산할 수 있는 방법은 알려져 있지 않다.

배경

Paillier 암호 시스템은 특정 이산 로그가 쉽게 계산될 수 있다는 사실을 이용한다.

예를 들어, 이항 정리에 의해

{\displaystyle (1+n)^{x}=\sum _{k=0}^{x}{x \선택 k}n^{k}=1+nx+{x \선택 }n^{2}+{\text{n}}}}의 권한

이는 다음을 나타낸다.

{\displaystyle (1+n)^{x}\equiv 1+nx{\pmod{n^{2}}:

따라서 다음과 같은 경우:

y=(1+n)^{x}{\bmod{n}^{2}

그때

x\equiv {\frac {y-1}{n}}{\pmod {n}}

x\equiv {\frac {y-1}{n}}{\pmod {n}}

x\equiv {\frac {y-1}{n}}{\pmod {n}}

-

x\equiv {\frac {y-1}{n}}{\pmod {n}}

(

x\equiv {\frac {y-1}{n}}{\pmod {n}}

x\equiv {\frac {y-1}{n}}{\pmod {n}}

)

{\

n}{\

pmod{n

따라서 다음과 같다.

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

(

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

+ n

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

) x

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

2

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

)

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

x

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

(

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

L((1+n)^{x}{\bmod {n}}^{2})\equiv x{\pmod {n}}

)

{\

L

(1+n)^{x}{\bmod{n}^{n}}\equiv

x

{\pmod{n

여기서

L

{\displaystyle

L}

함수

는

L(u)={\frac {u-1}{n}}

)

L(u)={\frac {u-1}{n}}

=

L(u)={\frac {u-1}{n}}

-

L(u)={\frac {u-1}{n}}

{\

정수분할의 양)

x\in \mathbb {Z} _{n}

x\in \mathbb {Z} _{n}

Z n {\

displaysty x\in \mathb {Z} _{n}

로 정의된다

L

x\in \mathbb {Z} _{n}

의미 보안

위와 같은 원래의 암호체계는 선택된 일반 텍스트 공격(IND-CPA)에 대한 의미적 보안을 제공한다.챌린지 암호문을 성공적으로 구별할 수 있는 능력은 본질적으로 복합 잔존도를 결정할 수 있는 능력에 해당된다.소위 의사결정 복합 잔류성 가정(DCRA)은 난치성이 있다고 여겨진다.

그러나 앞에서 언급한 동형체 특성 때문에 시스템은 유연성이 높으며 따라서 적응형 선택-지침 공격(IND-CCA2)에 대한 보호와 같은 최고 수준의 의미적 보안을 누리지 못한다.일반적으로 암호에서는 취약성의 개념이 "장점"으로 보이지 않지만, 보안 전자 투표와 임계 암호 시스템과 같은 특정 응용 프로그램에서는 이 속성이 실제로 필요할 수 있다.

그러나 Paillier와 Pointcheval은 계속해서 임의의 r과 메시지 m의 해싱 결합을 통합하는 개선된 암호 시스템을 제안하였다.크레이머의 의도와 비슷하다.션프 암호 시스템, 해싱은 c만 주어진 공격자가 의미 있는 방법으로 m을 변화시킬 수 있는 것을 방지한다.이러한 적응을 통해 개선된 체계가 랜덤 오라클 모델에서 IND-CCA2 안전한 것으로 나타날 수 있다.

적용들

전자투표

의미적 보안만이 유일한 고려사항이 아니다.순응성이 바람직할 수 있는 상황이 있다.위와 같은 동형성 속성은 안전한 전자투표시스템에 의해 활용될 수 있다.간단한 2진수("용" 또는 "반대") 표를 고려하십시오.유권자들이 1표 또는 0표를 던지게 하자.각 투표자는 투표를 하기 전에 자신의 선택을 암호화한다.선거관리관은 m암호화된 표의 산출물을 취합한 후 결과를 해독하여 모든 표의 합계인 n값을 얻는다.그러면 선거관리관은 n명의 사람들이 투표했고 m-n 사람들이 반대했다는 것을 안다.무작위 r의 역할은 동등한 두 표가 무시할 수 있는 가능성만으로 동일한 값으로 암호화되도록 보장하고, 따라서 유권자의 프라이버시를 보장한다.

전자현금

종이에 이름 붙여진 또 다른 특징은 자기맹점의 개념이다.이것은 암호 해독의 내용을 바꾸지 않고 하나의 암호문을 다른 암호문으로 바꾸는 능력이다.이것은 원래 데이비드 차움이 주도한 노력인 에코시 개발에 적용되었다.온라인에서 당신의 신용카드 번호와 그에 따른 당신의 신원을 알 필요가 없는 상품을 지불한다고 상상해 보라.전자현금과 전자투표 모두에서 목표는 전자코인(현명한 전자투표)이 유효한지 확인하는 동시에, 동시에 현재 제휴하고 있는 사람의 신원을 공개하지 않는 것이다.

임계값 암호 시스템

Paillier 암호 시스템의 동형성 속성은 때때로 Threshold ECDSA 시그니처를^[3] 구축하는 데 사용된다.

참고 항목

나카체-스테인 암호체계와 오카모토 암호체계-우치야마 암호 체계는 파일리에의 역사적 선행이다.
Damg–rd-Jurik 암호 체계는 Paillier의 일반화다.

참조

Paillier, Pascal; Pointcheval, David (1999). "Efficient Public-Key Cryptosystems Provably Secure Against Active Adversaries". ASIACRYPT. Springer. pp. 165–179. doi:10.1007/978-3-540-48000-6_14.
Paillier, Pascal (1999). Cryptosystems Based on Composite Residuosity (Ph.D. thesis). École Nationale Supérieure des Télécommunications.
Paillier, Pascal (2002). "Composite-Residuosity Based Cryptography: An Overview" (PDF). CryptoBytes. 5 (1). Archived from the original (PDF) on October 20, 2006.

메모들

^ ^a ^b 조나단 캣츠, 예후다 린델, "현대 암호학의 도입: 원칙과 프로토콜", 채프먼 & 홀/CRC, 2007
^ Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". Advances in Cryptology — EUROCRYPT ’99. Springer: 223–238. doi:10.1007/3-540-48910-X_16.
^ Canetti, Ran; Gennaro, Rosario; Goldfeder, Steven; Makriyannis, Nikolaos; Peled, Udi (30 October 2020). "UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts". Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery: 1769–1787. doi:10.1145/3372297.3423367.

외부 링크

호모모르픽 암호화 프로젝트는 Paillier 암호체계를 그것의 동모픽 작동과 함께 시행한다.
접점: Paillier 암호 시스템의 구현을 제공하는 오픈 소스 라이브러리 및 이를 기반으로 한 암호화 카운터 구축.
python-paillier는 부동 소수점 번호에 대한 완전한 지원을 포함하여 Python에서 부분적으로 동형 암호화를 위한 라이브러리.
Paillier 암호체계 인터랙티브 시뮬레이터는 투표 어플리케이션을 보여준다.
Paillier 암호 시스템에 대한 대화형 데모.
Paillier 암호 시스템의 개념 증명 Javascript 구현(대화형 데모 포함)
암호방식을 이용한 투표에 관한 구글테크톡 동영상.
Paillier 동형성 첨가 및 제로 지식 증명 프로토콜의 루비 구현

[katzLindell-1] 조나단 캣츠, 예후다 린델, "현대 암호학의 도입: 원칙과 프로토콜", 채프먼 & 홀/CRC, 2007

[Paillier1999-2] Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes". Advances in Cryptology — EUROCRYPT ’99. Springer: 223–238. doi:10.1007/3-540-48910-X_16.

[3] Canetti, Ran; Gennaro, Rosario; Goldfeder, Steven; Makriyannis, Nikolaos; Peled, Udi (30 October 2020). "UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts". Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery: 1769–1787. doi:10.1145/3372297.3423367.

[1]

[2]

[3]

Search