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

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

योजना एक योगात्मक समरूपी कूट लेखन है; इसका अर्थ यह है कि, केवल सार्वजनिक कुंजी और $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. निम्नलिखित प्रमापीय गुणक व्युत्क्रम के अस्तित्व $\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}$ की जाँच करके सुनिश्चित करें कि $n$ $g$ के क्रम को विभाजित करता है, जहाँ फलन $L$ को $L(x)={\frac {x-1}{n}}$ के रूप में परिभाषित किया गया है। ध्यान दें कि संकेतन ${\frac {a}{b}}$ $a$ के प्रमापीय गुणन को b के प्रमापीय गुणक व्युत्क्रम से नहीं दर्शाता है, बल्कि b द्वारा विभाजित $a$ के भागफल को दर्शाता है, अर्थात, सबसे बड़े पूर्णांक मान $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}$ है।

समरूप गुण

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

• प्लेनटेक्स्ट का समरूपी जोड़

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

$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) के विरुद्ध सुरक्षा के उच्चतम स्तर का आनंद नहीं लेती है। सामान्यतः कूटलेखन में आघातवर्धनीयता की धारणा को एक लाभ के रूप में नहीं देखा जाता है, लेकिन सुरक्षित इलेक्ट्रॉनिक मतदान और प्रभावसीमा क्रिप्टोसिस्टम जैसे कुछ अनुप्रयोगों के अंतर्गत, यह गुण वास्तव में आवश्यक हो सकता है।

पैलियर और पोइंटचेवल ने हालांकि एक बेहतर क्रिप्टोसिस्टम का प्रस्ताव दिया, जिसमें संदेश m के संयुक्त द्रुतान्वेषण को यादृच्छिक r के साथ सम्मिलित किया गया। क्रैमर-शौप क्रिप्टोसिस्टम के उद्देश्य के समान, द्रुतान्वेषण एक आक्रामक को रोकता है, केवल c दिया गया है, और m को सार्थक तरीके से बदलने में सक्षम है। इस अनुकूलन के माध्यम से बेहतर योजना को यादृच्छिक दिव्यवक्ता प्रतिरूप में IND-CCA2 सुरक्षित दिखाया जा सकता है।।

अनुप्रयोग

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

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

इलेक्ट्रॉनिक नगद

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

प्रभावसीमा क्रिप्टोसिस्टम

पैलियर क्रिप्टोसिस्टम की समरूपी संपत्ति का उपयोग कभी-कभी प्रभावसीमा क्रिप्टोसिस्टम 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)