पैलियर क्रिप्टोसिस्टम

1999 में Pascal Paillier द्वारा आविष्कृत और नाम दिया गया Paillier क्रिप्टोसिस्टम, सार्वजनिक कुंजी क्रिप्टोग्राफी के लिए एक संभाव्य असममित एल्गोरिथम है। माना जाता है कि 'एन'-वें अवशेष वर्गों की गणना की समस्या कम्प्यूटेशनल रूप से कठिन है। डिसीजनल कम्पोजिट रेज़िडुओसिटी धारणा इंट्रेक्टेबिलिटी (जटिलता) परिकल्पना है जिस पर यह क्रिप्टोसिस्टम आधारित है।

योजना एक योगात्मक होमोमोर्फिक एन्क्रिप्शन है; इसका मतलब यह है कि, केवल सार्वजनिक कुंजी और दी गई का एन्क्रिप्शन $m_{1}$ और $m_{2}$, कोई एन्क्रिप्शन की गणना कर सकता है $m_{1}+m_{2}$.

एल्गोरिथम

योजना इस प्रकार काम करती है:

मुख्य पीढ़ी

1. दो बड़ी अभाज्य संख्याएं चुनें $p$ और $q$ बेतरतीब ढंग से और स्वतंत्र रूप से एक दूसरे से ऐसा है $\gcd(pq,(p-1)(q-1))=1$. यह संपत्ति सुनिश्चित है यदि दोनों अभाज्य समान लंबाई के हैं।
2. गणना $n=pq$ और $\lambda =\operatorname {lcm} (p-1,q-1)$. lcm का मतलब कम से कम आम बहु है।
3. यादृच्छिक पूर्णांक का चयन करें $g$ कहाँ $g\in \mathbb {Z} _{n^{2}}^{*}$
4. बाग़ का धागा $n$ के क्रम को विभाजित करता है $g$ निम्नलिखित मॉड्यूलर गुणात्मक व्युत्क्रम के अस्तित्व की जाँच करके: $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$,

जहां समारोह $L$ परिभाषित किया जाता है $L(x)={\frac {x-1}{n}}$ .

ध्यान दें कि नोटेशन ${\frac {a}{b}}$ के मॉड्यूलर गुणन को निरूपित नहीं करता है $a$ के मॉड्यूलर गुणक व्युत्क्रम का गुना $b$ बल्कि इसका भागफल $a$ द्वारा विभाजित $b$, यानी, सबसे बड़ा पूर्णांक मान $v\geq 0$ संबंध को संतुष्ट करने के लिए $a\geq vb$.

• सार्वजनिक (एन्क्रिप्शन) कुंजी है $(n,g)$.
• निजी (डिक्रिप्शन) कुंजी है $(\lambda ,\mu ).$यदि समतुल्य लंबाई के p,q का उपयोग किया जाता है, तो उपरोक्त कुंजी जनरेशन चरणों का एक सरल संस्करण सेट करना होगा $g=n+1,\lambda =\varphi (n),$ और $\mu =\varphi (n)^{-1}{\bmod {n}}$, कहाँ $\varphi (n)=(p-1)(q-1)$ .कार्यान्वयन उद्देश्यों के लिए सरल संस्करण की सिफारिश की जाती है, क्योंकि सामान्य रूप में गणना का समय $\mu$ पर्याप्त रूप से बड़े अभाज्य p,q के साथ बहुत अधिक हो सकता है।

एन्क्रिप्शन

1. होने देना $m$ एन्क्रिप्टेड होने के लिए एक संदेश हो $0\leq m<n$
2. यादृच्छिक चयन करें $r$ कहाँ $0<r<n$ और $\gcd(r,n)=1$
3. सिफरटेक्स्ट की गणना इस प्रकार करें: $c=g^{m}\cdot r^{n}{\bmod {n}}^{2}$

डिक्रिप्शन

1. होने देना $c$ डिक्रिप्ट करने के लिए सिफरटेक्स्ट हो, जहां $c\in \mathbb {Z} _{n^{2}}^{*}$
2. सादे पाठ संदेश की गणना इस प्रकार करें: $m=L(c^{\lambda }{\bmod {n}}^{2})\cdot \mu {\bmod {n}}$

मूल कागज के रूप में बताते हैं, डिक्रिप्शन अनिवार्य रूप से एक एक्सपोनेंटिएशन मोडुलो है $n^{2}$.

समरूप गुण

Paillier क्रिप्टोसिस्टम की एक उल्लेखनीय विशेषता इसके होमोमोर्फिक एन्क्रिप्शन गुणों के साथ-साथ इसके गैर-नियतात्मक एन्क्रिप्शन (उपयोग के लिए एप्लिकेशन में इलेक्ट्रॉनिक वोटिंग देखें) है। चूंकि एन्क्रिप्शन फ़ंक्शन अतिरिक्त रूप से होमोमोर्फिक है, निम्नलिखित पहचानों का वर्णन किया जा सकता है:

• प्लेनटेक्स्ट का होमोमोर्फिक जोड़

दो सिफरटेक्स्ट का गुणनफल उनके संगत प्लेनटेक्स्ट के योग तक डिक्रिप्ट होगा,

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

सादा पाठ उठाने के साथ सिफरटेक्स्ट का उत्पाद $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}}{\bmod {n}}^{2})=m_{1}m_{2}{\bmod {n}}.\,$

अधिक आम तौर पर, एक निरंतर k तक बढ़ा हुआ सिफरटेक्स्ट, प्लेनटेक्स्ट और स्थिरांक के उत्पाद के लिए डिक्रिप्ट होगा,

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

हालांकि, दो संदेशों के पिलियर एन्क्रिप्शन को देखते हुए निजी कुंजी को जाने बिना इन संदेशों के उत्पाद के एन्क्रिप्शन की गणना करने का कोई ज्ञात तरीका नहीं है।

पृष्ठभूमि

पैलियर क्रिप्टोसिस्टम इस तथ्य का फायदा उठाता है कि कुछ असतत लघुगणकों की गणना आसानी से की जा सकती है।

उदाहरण के लिए, द्विपद प्रमेय द्वारा,

$(1+n)^{x}=\sum _{k=0}^{x}{x \choose k}n^{k}=1+nx+{x \choose 2}n^{2}+{\text{higher powers of }}n$

यह इंगित करता है कि:

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

इसलिए, यदि:

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

तब

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

इस प्रकार:

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

जहां समारोह $L$ परिभाषित किया जाता है $L(u)={\frac {u-1}{n}}$ (पूर्णांक विभाजन का भागफल) और $x\in \mathbb {Z} _{n}$.

सिमेंटिक सुरक्षा

जैसा कि ऊपर दिखाया गया है मूल क्रिप्टोसिस्टम चुने हुए-प्लेनटेक्स्ट हमलों (आईएनडी-सीपीए) के खिलाफ सिमेंटिक सुरक्षा प्रदान करता है। चुनौती सिफरटेक्स्ट को सफलतापूर्वक अलग करने की क्षमता अनिवार्य रूप से समग्र अवशेषों को तय करने की क्षमता के बराबर है। तथाकथित निर्णयात्मक समग्र अवशिष्ट धारणा (DCRA) को अट्रैक्टिव माना जाता है।

हालांकि, उपरोक्त होमोमोर्फिक गुणों के कारण, सिस्टम मैलेबिलिटी (क्रिप्टोग्राफी) है, और इसलिए सिमेंटिक सुरक्षा के उच्चतम स्तर का आनंद नहीं लेता है, अनुकूली चुने गए-सिफरटेक्स्ट हमलों (IND-CCA2#Indistinguishability के तहत चुने गए सिफरटेक्स्ट हमले) के खिलाफ सुरक्षा। 2Fadaptive चुना सिफरटेक्स्ट हमला .28IND-CCA1.2C IND-CCA2.29|IND-CCA2)। आमतौर पर क्रिप्टोग्राफी में आघातवर्धनीयता की धारणा को एक लाभ के रूप में नहीं देखा जाता है, लेकिन सुरक्षित इलेक्ट्रॉनिक वोटिंग और थ्रेशोल्ड क्रिप्टोसिस्टम जैसे कुछ अनुप्रयोगों के तहत, यह गुण वास्तव में आवश्यक हो सकता है।

Paillier और Pointcheval ने हालांकि एक बेहतर क्रिप्टोसिस्टम का प्रस्ताव दिया, जिसमें संदेश m के संयुक्त हैशिंग को यादृच्छिक r के साथ शामिल किया गया। क्रैमर-शौप क्रिप्टोसिस्टम के इरादे के समान, हैशिंग एक हमलावर को रोकता है, केवल c दिए जाने पर, मी को सार्थक तरीके से बदलने में सक्षम होने से। इस अनुकूलन के माध्यम से बेहतर योजना को IND-CCA2#Indistinguishability Under Selected Ciphertext Attack.2Fadaptive Selected Ciphertext Attack .28IND-CCA1.2C IND-CCA2.29|IND-CCA2 को यादृच्छिक ओरेकल मॉडल में सुरक्षित दिखाया जा सकता है।

अनुप्रयोग

इलेक्ट्रॉनिक मतदान

सिमेंटिक सुरक्षा ही एकमात्र विचार नहीं है। ऐसी स्थितियां हैं जिनके तहत लचीलापन वांछनीय हो सकता है। उपरोक्त समरूप गुणों का उपयोग सुरक्षित इलेक्ट्रॉनिक वोटिंग सिस्टम द्वारा किया जा सकता है। एक साधारण बाइनरी (के लिए या उसके खिलाफ) वोट पर विचार करें। बता दें कि एम मतदाता या तो 1 (के लिए) या 0 (विरुद्ध) वोट डालते हैं। प्रत्येक मतदाता अपना वोट डालने से पहले अपनी पसंद को एन्क्रिप्ट करता है। चुनाव अधिकारी m एन्क्रिप्टेड वोटों का उत्पाद लेता है और फिर परिणाम को डिक्रिप्ट करता है और मान n प्राप्त करता है, जो सभी वोटों का योग है। चुनाव अधिकारी तब जानता है कि n लोगों ने वोट दिया और m-n लोगों ने खिलाफ वोट किया। यादृच्छिक आर की भूमिका यह सुनिश्चित करती है कि दो समान वोट केवल नगण्य संभावना के साथ समान मूल्य पर एन्क्रिप्ट होंगे, इस प्रकार मतदाता गोपनीयता सुनिश्चित करते हैं।

इलेक्ट्रॉनिक कैश

पेपर में नामित एक अन्य विशेषता सेल्फ-ब्लाइंडिंग (क्रिप्टोग्राफी) की धारणा है। यह डिक्रिप्शन की सामग्री को बदले बिना एक सिफरटेक्स्ट को दूसरे में बदलने की क्षमता है। यह एकाश के विकास के लिए उपयोगी है, मूल रूप से डेविड चाउम के नेतृत्व में एक प्रयास। विक्रेता को आपके क्रेडिट कार्ड नंबर, और इसलिए आपकी पहचान जानने की आवश्यकता के बिना किसी वस्तु के लिए ऑनलाइन भुगतान करने की कल्पना करें। इलेक्ट्रॉनिक कैश और इलेक्ट्रॉनिक वोटिंग दोनों में लक्ष्य यह सुनिश्चित करना है कि ई-सिक्का (इसी तरह ई-वोट) वैध है, जबकि साथ ही उस व्यक्ति की पहचान का खुलासा नहीं करना है जिसके साथ यह वर्तमान में जुड़ा हुआ है।

दहलीज क्रिप्टोसिस्टम

Paillier क्रिप्टोसिस्टम की होमोमोर्फिक संपत्ति का उपयोग कभी-कभी थ्रेशोल्ड क्रिप्टोसिस्टम ECDSA सिग्नेचर बनाने के लिए किया जाता है।

यह भी देखें

• नैकाचे-स्टर्न क्रिप्टोसिस्टम और ओकामोटो-उचियामा क्रिप्टोसिस्टम पैल्लियर के ऐतिहासिक पूर्ववर्ती हैं।
• डैमगार्ड-जुरिक क्रिप्टोसिस्टम पैल्लियर का एक सामान्यीकरण है।

संदर्भ

• Paillier, Pascal (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes" (PDF). Advances in Cryptology — EUROCRYPT ’99. EUROCRYPT. Springer. doi:10.1007/3-540-48910-X_16.
• 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.

टिप्पणियाँ

बाहरी संबंध

• The Homomorphic Encryption Project implements the Paillier cryptosystem along with its homomorphic operations.
• Encounter: an open-source library providing an implementation of Paillier cryptosystem and a cryptographic counters construction based on the same.
• python-paillier a library for Partially Homomorphic Encryption in Python, including full support for floating point numbers.
• The Paillier cryptosystem interactive simulator demonstrates a voting application.
• An interactive demo of the Paillier cryptosystem.
• A proof-of-concept Javascript implementation of the Paillier cryptosystem with an interactive demo.
• A googletechtalk video on voting using cryptographic methods.
• A Ruby implementation of Paillier homomorphic addition and a zero-knowledge proof protocol (documentation)