Naor–Reingold pseudorandom function
1997માં, મોની નાઓર અને ઓમર રીંગોલ્ડે ખાનગી કી તેમજ જાહેર-કી ક્રિપ્ટોગ્રાફીમાં વિવિધ ક્રિપ્ટોગ્રાફિક પ્રિમિટિવ્સ માટે કાર્યક્ષમ રચનાઓનું વર્ણન કર્યું હતું. તેમનું પરિણામ એક કાર્યક્ષમ સ્યુડોરાન્ડમ કાર્યનું નિર્માણ છે. ધારો કે p અને l એ l |p −1 સાથે મુખ્ય સંખ્યાઓ છે. પછી દરેક (n + 1)-પરિમાણીય વેક્ટર a = (a0, a1,., an) માટે તેઓ કાર્યને વ્યાખ્યાયિત કરે છે જ્યાં x = x1. xn એ પૂર્ણાંક x, 0 ≤ x ≤ 2n − 1 નું બિટ પ્રતિનિધિત્વ છે, જો જરૂરી હોય તો કેટલાક વધારાના અગ્રણી શૂન્ય સાથે. ઉદાહરણ તરીકે ચાલો p = 7 અને l = 3; તેથી l |p −1. ગુણાકાર ક્રમ 3 નો g = 4 bul પસંદ કરો (કારણ કે 43 = 64 ષ્ણ 1 મોડ 7). n = 3, a = (1,1,2,1) અને x = 5 (5 ની બીટ રજૂઆત 101 છે) માટે, આપણે નીચે મુજબ ગણતરી કરી શકીએ છીએઃ કાર્યક્ષમતા નાઓર-રીંગોલ્ડ રચનામાં કાર્યનું મૂલ્યાંકન ખૂબ જ અસરકારક રીતે કરી શકાય છે. કોઈપણ બિંદુ પર કાર્યના મૂલ્યની ગણતરી એક મોડ્યુલર ઘાતાંક અને એન-મોડ્યુલર ગુણાકાર સાથે તુલનાત્મક છે. આ વિધેયની ગણતરી બંધાયેલ ઊંડાઈ અને બહુપદી કદની થ્રેશોલ્ડ સર્કિટ્સ દ્વારા સમાંતર કરી શકાય છે. નાઓર-રીંગોલ્ડ કાર્યનો ઉપયોગ સિમેટ્રિક એન્ક્રિપ્શન, પ્રમાણીકરણ અને ડિજિટલ સહીઓ સહિત ઘણી ક્રિપ્ટોગ્રાફિક યોજનાઓના આધાર તરીકે થઈ શકે છે. કાર્યની સુરક્ષા ધારો કે હુમલાખોર કાર્યના ઘણા આઉટપુટ જુએ છે, દા. ત. , અને ગણતરી કરવા માંગે છે. સરળતા માટે ધારો કે x1 = 0, પછી હુમલાખોરને અને વચ્ચે કોમ્પ્યુટેશનલ ડિફી-હેલમેન (સી. ડી. એચ.) ઉકેલવાની જરૂર છે. સામાન્ય રીતે, k થી k + 1 તરફ આગળ વધવાથી બીટ પેટર્નમાં ફેરફાર થાય છે અને જ્યાં સુધી k + 1 એ 2 ની ઘાત ન હોય ત્યાં સુધી કોઈ પણ ઘાતાંકને વિભાજિત કરી શકે છે જેથી ગણતરી અગાઉના બે પરિણામો વચ્ચે ડિફી-હેલમેન કીની ગણતરીને અનુરૂપ હોય. આ હુમલાખોર આગામી અનુક્રમ તત્વની આગાહી કરવા માંગે છે. આવો હુમલો ખૂબ જ ખરાબ હશે-પરંતુ હાર્ડ ડિફી-હેલમેન પ્રોબ્લેમ (ડી. એચ. પી.) સાથે જૂથોમાં કામ કરીને તેનો સામનો કરવો પણ શક્ય છે. ઉદાહરણ તરીકેઃ હુમલાખોર કાર્યના ઘણા આઉટપુટ જુએ છે. , અગાઉના ઉદાહરણમાં, અને. પછી, હુમલાખોર આ કાર્યના આગામી અનુક્રમ તત્વની આગાહી કરવા માંગે છે. જો કે, હુમલાખોર જાણવાથી અને પરિણામની આગાહી કરી શકતો નથી. એવા અન્ય હુમલાઓ છે જે સ્યુડોરાન્ડમ નંબર જનરેટર માટે ખૂબ જ ખરાબ હશેઃ વપરાશકર્તા આઉટપુટમાંથી રેન્ડમ નંબરો મેળવવાની અપેક્ષા રાખે છે, તેથી અલબત્ત પ્રવાહ અનુમાનિત ન હોવો જોઈએ, પરંતુ તેનાથી પણ વધુ, તે રેન્ડમ સ્ટ્રિંગથી અલગ ન હોવો જોઈએ. ચાલો કાર્યનું મૂલ્યાંકન કરવા માટે ઓરેકલની ઍક્સેસ સાથે અલ્ગોરિધમ સૂચવીએ. ધારો કે નિર્ણાયક ડિફી-હેલમેન ધારણા ધરાવે છે, નાઓર અને રીંગોલ્ડ દર્શાવે છે કે દરેક સંભવિત બહુપદી સમય અલ્ગોરિધમ અને પૂરતા પ્રમાણમાં મોટા n માટે નગણ્ય છે. પ્રથમ સંભાવના બીજ s = (p, g, a) ની પસંદગી પર લેવામાં આવે છે અને બીજી સંભાવના p, g બાય, ઇન્સ્ટન્સ જનરેટર પર પ્રેરિત રેન્ડમ વિતરણ પર લેવામાં આવે છે, અને તમામ કાર્યોના સમૂહ વચ્ચે કાર્યની રેન્ડમ પસંદગી પર લેવામાં આવે છે. રેખીય જટિલતા ક્રિપ્ટોગ્રાફિક હેતુઓ માટે ક્રમ કેટલો ઉપયોગી હોઈ શકે તેનું એક કુદરતી માપ તેની રેખીય જટિલતાનું કદ છે. રિંગ પર n-તત્વ ક્રમ W (x), x = 0,1,2,., n-1 ની રેખીય જટિલતા એ ટૂંકા રેખીય પુનરાવર્તન સંબંધ W (x + l) = Al − 1 W (x + l − 1) +. + A0 W (x), x = 0,1,2,., n-l − 1 સાથે A0,., Al − 1 ω ની લંબાઈ છે, જે આ ક્રમ દ્વારા સંતુષ્ટ થાય છે. કેટલાક> 0 માટે, n ≤ (1 +), કોઈપણ, પૂરતા પ્રમાણમાં મોટા l માટે, અનુક્રમની રેખીય જટિલતા, 0 ≤ x ≤ 2n-1 દ્વારા સૂચવવામાં આવે છે, જે સંભવતઃ મોટાભાગના વેક્ટર a ω સિવાય બધા માટે સંતોષ આપે છે. આ કાર્યની મર્યાદામાં ગેરફાયદા છે, એટલે કે તે ખૂબ જ રસપ્રદ કેસને લાગુ પડતું નથી વિતરણની એકરૂપતા નું આંકડાકીય વિતરણ લગભગ તમામ વેક્ટર માટે એકસમાન વિતરણની નજીક છે. સેટની વિસંગતતા હોવી જોઈએ. આમ, જો p ની બીટ લંબાઈ હોય તો બધા વેક્ટર માટે a ω બાઉન્ડ ધરાવે છે, જ્યાં અને જો કે આ ગુણધર્મમાં કોઈ તાત્કાલિક ક્રિપ્ટોગ્રાફિક અસરો હોય તેવું લાગતું નથી, તો વિપરીત હકીકત, એટલે કે બિન-સમાન વિતરણ, જો સાચું હોય તો આ કાર્યના ઉપયોગ માટે વિનાશક પરિણામો આવશે. લંબગોળ વળાંકમાં ક્રમ આ કાર્યનું લંબગોળ વળાંક સંસ્કરણ પણ રસપ્રદ છે. ખાસ કરીને, તે અનુરૂપ સિસ્ટમની ક્રિપ્ટોગ્રાફિક સુરક્ષામાં સુધારો કરવામાં મદદ કરી શકે છે. ધારો કે p> 3 અવિભાજ્ય છે અને E એ લંબગોળ વળાંક છે, પછી દરેક વેક્ટર a પેટાજૂથમાં મર્યાદિત ક્રમને આ રીતે વ્યાખ્યાયિત કરે છેઃ જ્યાં પૂર્ણાંકની બીટ રજૂઆત છે. નાઓર-રીંગોલ્ડ લંબગોળ વળાંક ક્રમને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છે કે જો નિર્ણાયક ડિફી-હેલમેન ધારણા હોય, તો અનુક્રમણિકા k બહુપદી સમયમાં ગણતરી કરવા માટે પૂરતી નથી, ભલે હુમલાખોર બહુપદીમાં ઘણા પ્રશ્નો રેન્ડમ <ID1:// en. વિકીપીડિયા. org/વિકિ/એલિપ્ટિક _ કર્વ પર કરે. સ્યુડોરાન્ડમ નંબર જનરેટર ક્રિપ્ટોગ્રાફી