Computational indistinguishability
કોમ્પ્યુટેશનલ જટિલતા અને ક્રિપ્ટોગ્રાફીમાં, વિતરણના બે પરિવારો કોમ્પ્યુટેશનલ રીતે અવિભાજ્ય છે જો કોઈ કાર્યક્ષમ અલ્ગોરિધમ તેમની વચ્ચેનો તફાવત નજીવી સંભાવના સિવાય કહી શકે નહીં. ઔપચારિક વ્યાખ્યા ચાલો અને સુરક્ષા પરિમાણ n દ્વારા અનુક્રમિત બે વિતરણ સમૂહ હોઈએ (જે સામાન્ય રીતે ઇનપુટની લંબાઈનો સંદર્ભ આપે છે); આપણે કહીએ છીએ કે જો કોઈપણ બિન-સમાન સંભવિત બહુપદી સમય અલ્ગોરિધમ A માટે, નીચેનો જથ્થો n માં નગણ્ય કાર્ય હોય તો તે ગણતરીત્મક રીતે અવિભાજ્ય છે. બીજા શબ્દોમાં કહીએ તો, દરેક કાર્યક્ષમ અલ્ગોરિધમ જ્યારે મર્યાદામાં Dn અથવા En અનુસાર નમૂના આપવામાં આવે ત્યારે વર્તન તરીકે નોંધપાત્ર રીતે બદલાતું નથી. કોમ્પ્યુટેશનલ અસ્પષ્ટતાનું બીજું અર્થઘટન એ છે કે બહુપદી-સમયના અલ્ગોરિધમ્સ સક્રિય રીતે બે સમૂહ વચ્ચે તફાવત કરવાનો પ્રયાસ કરી શકતા નથીઃ કે આવા કોઈપણ અલ્ગોરિધમ માત્ર અનુમાન લગાવવા કરતાં નજીવું વધુ સારું પ્રદર્શન કરશે. સંબંધિત ધારણાઓ વ્યાખ્યામાં ગર્ભિત એવી શરત છે કે અલ્ગોરિધમ, વિતરણમાંથી એક નમૂનાના આધારે નક્કી કરવું આવશ્યક છે. કોઈ એવી પરિસ્થિતિની કલ્પના કરી શકે છે જેમાં બે વિતરણો વચ્ચે તફાવત કરવાનો પ્રયાસ કરતી અલ્ગોરિધમ, તેને જરૂરી હોય તેટલા નમૂનાઓ મેળવી શકે છે. તેથી બહુવિધ નમૂનાઓને જોતા બહુપદી-સમયના અલ્ગોરિધમ્સ દ્વારા અલગ કરી શકાતા નથી તેવા બે સમૂહને બહુપદી-સમયના નમૂના દ્વારા અવિભાજ્ય માનવામાં આવે છે. જો બહુપદી-સમય અલ્ગોરિધમ બહુપદી સમયમાં નમૂનાઓ ઉત્પન્ન કરી શકે છે, અથવા તેના માટે નમૂનાઓ ઉત્પન્ન કરતી રેન્ડમ ઓરેકલની ઍક્સેસ ધરાવે છે, તો બહુપદી-સમય નમૂના દ્વારા અસ્પષ્ટતા એ કોમ્પ્યુટેશનલ અસ્પષ્ટતાની સમકક્ષ છે. સંદર્ભો બાહ્ય કડીઓ યેહુદા લિન્ડેલ. ક્રિપ્ટોગ્રાફીનો પરિચય ડોનાલ્ડ બીવર અને સિલ્વિયો મિકાલી અને ફિલિપ રોગવે, ધ રાઉન્ડ કોમ્પ્લેક્સિટી ઓફ સિક્યોર પ્રોટોકોલ્સ (એક્સટેન્ડેડ એબ્સ્ટ્રેક્ટ), 1990, પીપી. 503-513 શફી ગોલ્ડવાસર અને સિલ્વિયો મિકાલી. સંભવિત એન્ક્રિપ્શન. JCSS, 28 (2): 270-299,1984 ઓડેડ ગોલ્ડરીચ. ક્રિપ્ટોગ્રાફીનો પાયોઃ ભાગ 2-મૂળભૂત ઉપયોગો. કેમ્બ્રિજ યુનિવર્સિટી પ્રેસ, 2004. જોનાથન કાટ્ઝ, યેહુદા લિન્ડેલ, "આધુનિક ક્રિપ્ટોગ્રાફીનો પરિચયઃ સિદ્ધાંતો અને પ્રોટોકોલ", ચેપમેન એન્ડ હોલ/સી. આર. સી., 2007 એલ્ગોરિધમિક માહિતી સિદ્ધાંત