Diffie–Hellman problem
ડિફી-હેલમેન પ્રોબ્લેમ (ડી. એચ. પી.) એ એક ગાણિતિક સમસ્યા છે જે સૌપ્રથમ ગુપ્તલેખનના સંદર્ભમાં વ્હિટફિલ્ડ ડિફી અને માર્ટિન હેલમેન દ્વારા પ્રસ્તાવિત કરવામાં આવી હતી. આ સમસ્યાની પ્રેરણા એ છે કે ઘણી સુરક્ષા પ્રણાલીઓ એક તરફી કાર્યોનો ઉપયોગ કરે છેઃ ગાણિતિક કામગીરી જે ગણતરી કરવા માટે ઝડપી હોય છે, પરંતુ તેને ઉલટાવવી મુશ્કેલ હોય છે. ઉદાહરણ તરીકે, તેઓ સંદેશને એન્ક્રિપ્ટ કરવામાં સક્ષમ કરે છે, પરંતુ એન્ક્રિપ્શનને ઉલટાવવું મુશ્કેલ છે. જો ડી. એચ. પી. ને ઉકેલવું સરળ હોત, તો આ પ્રણાલીઓ સરળતાથી તૂટી હોત. સમસ્યાનું વર્ણન ડિફી-હેલમેન સમસ્યાને અનૌપચારિક રીતે નીચે મુજબ વર્ણવવામાં આવી છેઃ એક તત્વ g અને gx અને gy ના મૂલ્યોને જોતાં, gxy નું મૂલ્ય શું છે? ઔપચારિક રીતે, g એ અમુક જૂથનું જનરેટર છે (સામાન્ય રીતે મર્યાદિત ક્ષેત્રનું ગુણાકાર જૂથ અથવા લંબગોળ વળાંક જૂથ) અને x અને y અવ્યવસ્થિત રીતે પસંદ કરેલા પૂર્ણાંકો છે. ઉદાહરણ તરીકે, ડિફી-હેલમેન કી એક્સચેન્જમાં, એક ઇવ્ઝડ્રોપર પ્રોટોકોલના ભાગ રૂપે જીએક્સ અને જીઆઈની આપ-લેનું નિરીક્ષણ કરે છે, અને બંને પક્ષો વહેંચાયેલ કી જીએક્સઆઈની ગણતરી કરે છે. ડી. એચ. પી. ને ઉકેલવાનું ઝડપી માધ્યમ જાસૂસી કરનારને ડિફી-હેલમેન કી એક્સચેન્જ અને એલગેમલ એન્ક્રિપ્શન સહિત તેના ઘણા પ્રકારોની ગોપનીયતાનું ઉલ્લંઘન કરવાની મંજૂરી આપશે. કોમ્પ્યુટેશનલ જટિલતા ક્રિપ્ટોગ્રાફીમાં, અમુક જૂથો માટે, એવું માનવામાં આવે છે કે ડી. એચ. પી. મુશ્કેલ છે, અને આને ઘણીવાર ડિફી-હેલમેન ધારણા કહેવામાં આવે છે. આ સમસ્યા થોડા દાયકાઓ સુધી તપાસ હેઠળ રહી છે અને હજુ સુધી કોઈ "સરળ" ઉકેલ જાહેર કરવામાં આવ્યો નથી. 2006 સુધીમાં, ડી. એચ. પી. ને ઉકેલવા માટે જાણીતું સૌથી કાર્યક્ષમ માધ્યમ ડિસ્ક્રીટ લઘુગણક સમસ્યા (ડી. એલ. પી.) ને ઉકેલવાનું છે, જે x આપેલ g અને gx શોધવાનું છે. હકીકતમાં, નોંધપાત્ર પ્રગતિ (ડેન બોઅર, મૌરર, વુલ્ફ, બોનેહ અને લિપ્ટોન દ્વારા) એ દર્શાવવા તરફ કરવામાં આવી છે કે ઘણા જૂથોમાં ડી. એચ. પી. લગભગ ડી. એલ. પી. જેટલું જ મુશ્કેલ છે. સામાન્ય જૂથો (નેચેવ અને શૌપ દ્વારા) સિવાય, ડી. એચ. પી. અથવા ડી. એલ. પી. એક મુશ્કેલ સમસ્યા છે તેનો આજ સુધી કોઈ પુરાવો નથી. એક સાબિતી કે ક્યાં તો સમસ્યા સખત છે તે સૂચવે છે કે P ષ્ણાંક NP. અન્ય પ્રકારો ડિફી-હેલમેન સમસ્યાના ઘણા પ્રકારો પર વિચાર કરવામાં આવ્યો છે. સૌથી નોંધપાત્ર પ્રકાર નિર્ણયાત્મક ડિફી-હેલમેન પ્રોબ્લેમ (ડીડીએચપી) છે, જે જી, જીએક્સ અને જી. આઈ. આપેલ રેન્ડમ ગ્રુપ એલિમેન્ટથી જી. એક્સ. આઈ. ને અલગ પાડવાનો છે. કેટલીકવાર ડી. એચ. પી. ને ડીડીએચપીથી વધુ સ્પષ્ટ રીતે અલગ પાડવા માટે તેને કોમ્પ્યુટેશનલ ડિફી-હેલમેન પ્રોબ્લેમ (સીડીએચપી) કહેવામાં આવે છે. તાજેતરમાં જોડીવાળા જૂથો લોકપ્રિય બન્યા છે, અને આ જૂથોમાં ડી. ડી. એચ. પી. સરળ છે, તેમ છતાં ડી. એચ. પી. હજુ પણ મુશ્કેલ હોવાનું માનવામાં આવે છે. ડી. એચ. પી. ના ઓછા નોંધપાત્ર પ્રકારો માટે સંદર્ભો જુઓ. સંદર્ભો બી. ડેન બોઅર, ડિફી-હેલમેન ક્રિપ્ટોલોજીમાં એડવાન્સિસ-ક્રાયપ્ટો 88, કોમ્પ્યુટર સાયન્સમાં વ્યાખ્યાન નોંધો 403, સ્પ્રિંગર, પૃષ્ઠ 530,1988 માં ચોક્કસ અવિભાજ્ય માટે અલગ લોગ જેટલા મજબૂત છે. યુ. એમ. મૌરર અને એસ. વુલ્ફ, ડિફી-હેલમેન ઓરેકલ ઇન એડવાન્સિસ ઇન ક્રિપ્ટોલોજી-ક્રાયપ્ટો 96, (એન. કોબ્લિટ્ઝ, એડ. ), કોમ્પ્યુટર સાયન્સમાં વ્યાખ્યાન નોંધો 1070, સ્પ્રિંગર, પીપી. 268-282,1996. ડી. બોનેહ અને આર. જે. લિપ્ટોન, બ્લેક-બોક્સ ક્ષેત્રો માટેના અલ્ગોરિધમ્સ અને ક્રિપ્ટોલોજીમાં એડવાન્સિસમાં ક્રિપ્ટોટોગ્રાફી માટે તેમની એપ્લિકેશન-ક્રાયપ્ટો 96, (એન. કોબ્લિટ્ઝ, એડ. ), કોમ્પ્યુટર સાયન્સમાં વ્યાખ્યાન નોંધો 1070, સ્પ્રિંગર, પીપી. 283-297,1996. એ. મુઝેરો, એન. પી. સ્માર્ટ અને એફ. વેરકાઉટેરન, વ્યવહારુ કાર્યક્રમોમાં ઉપયોગમાં લેવાતા લંબગોળ વળાંક માટે ડીએચપી અને ડીએલપી વચ્ચેની સમાનતા, એલએમએસ જે. કોમ્પ્યુટ. ગણિત., 7, પૃ. 50-72,2004. [www.lms.ac.uk] જુઓ. ડી. આર. એલ. બ્રાઉન અને આર. પી. ગેલન્ટ, ધ સ્ટેટિક ડિફી-હેલમેન પ્રોબ્લેમ, IACR ePrint 2004/306. વી. આઈ. નેચેવ, સ્વતંત્ર લઘુગણક માટે નિર્ધારિત અલ્ગોરિધમનો જટિલતા, ગાણિતિક નોંધો, 55 (2), pp. 165-172,1994. વી. શૂપ, લોઅર બાઉન્ડ્સ ફોર ડિસ્ક્રીટ લઘુગણક અને સંબંધિત સમસ્યાઓ ઇન એડવાન્સિસ ઇન ક્રિપ્ટોલોજી-EUROCRYPT 97, (W. ફ્યુમી, એડ. ), લેક્ચર નોટ્સ ઇન કોમ્પ્યુટર સાયન્સ 1233, સ્પ્રિંગર, પીપી. 256-266,1997. કોમ્પ્યુટેશનલ કઠિનતા ધારણાઓ મર્યાદિત ક્ષેત્રો