Ideal lattice
સ્વતંત્ર ગણિતમાં, આદર્શ જાળી એ જાળીનો એક વિશેષ વર્ગ છે અને ચક્રીય જાળીનું સામાન્યીકરણ છે. આદર્શ જાળીઓ કુદરતી રીતે સંખ્યા સિદ્ધાંતના ઘણા ભાગોમાં જોવા મળે છે, પરંતુ અન્ય ક્ષેત્રોમાં પણ જોવા મળે છે. ખાસ કરીને, ક્રિપ્ટોગ્રાફીમાં તેમનું નોંધપાત્ર સ્થાન છે. માઇકિયાનસિયોએ ચક્રીય જાળીઓના સામાન્યીકરણને આદર્શ જાળી તરીકે વ્યાખ્યાયિત કર્યું. તેનો ઉપયોગ ક્રિપ્ટોસિસ્ટમ્સમાં જાળીનું વર્ણન કરવા માટે જરૂરી પરિમાણોની સંખ્યાને વર્ગમૂળથી ઘટાડવા માટે કરી શકાય છે, જે તેમને વધુ કાર્યક્ષમ બનાવે છે. આદર્શ જાળી એ એક નવો ખ્યાલ છે, પરંતુ સમાન જાળી વર્ગોનો ઉપયોગ લાંબા સમયથી કરવામાં આવે છે. ઉદાહરણ તરીકે, ચક્રીય જાળી, આદર્શ જાળીનો એક ખાસ કેસ, એન. ટી. આર. યુ. એનક્રિપ્ટ અને એન. ટી. આર. યુ. એસ. સાઇનમાં વપરાય છે. રીંગ લર્નિંગ વિથ એરર્સ પર આધારિત ક્વોન્ટમ કમ્પ્યુટર એટેક રેઝિસ્ટન્ટ ક્રિપ્ટોગ્રાફી માટે આદર્શ જાળી પણ આધાર બનાવે છે. આ આદર્શ જાળીઓમાં ટૂંકી વેક્ટર સમસ્યા (એસ. વી. પી.) સખત હોય છે એવી ધારણા હેઠળ આ ક્રિપ્ટોસિસ્ટમ્સ સાબિત રીતે સુરક્ષિત છે. સામાન્ય શબ્દોમાં કહીએ તો, આદર્શ જાળી એ ડિગ્રીની કેટલીક ઈરીડ્યુસિબલ બહુપદી માટે ફોર્મની રિંગ્સમાં આદર્શોને અનુરૂપ જાળી છે. અગાઉના કાર્યમાંથી આદર્શ જાળીની તમામ વ્યાખ્યાઓ નીચેની સામાન્ય કલ્પનાના ઉદાહરણો છેઃ ચાલો એક રિંગ હોઈએ જેનું એડિટિવ ગ્રુપ (એટલે કે, તે રેન્કનું ફ્રી-મોડ્યુલ છે) માટે આઇસોમોર્ફિક છે, અને ચાલો એક-પરિમાણીય વાસ્તવિક વેક્ટર સ્પેસ (દા. ત.,) માં કેટલાક જાળી માટે એડિટિવ આઇસોમોર્ફિઝમ મેપિંગ હોઈએ. એમ્બેડિંગ હેઠળ રિંગ માટે આદર્શ જાળીનો પરિવાર એ તમામ જાળીનો સમૂહ છે, જ્યાં વ્યાખ્યા સંકેતલિપીમાં આદર્શ છે ચાલો ડિગ્રીની મોનિક બહુપદી હોઈએ, અને ભાગાકાર રિંગને ધ્યાનમાં લઈએ. પ્રતિનિધિઓના પ્રમાણભૂત સમૂહનો ઉપયોગ કરીને અને વેક્ટર સાથે બહુપદીઓની ઓળખ કરીને, ભાગાકાર રિંગ પૂર્ણાંક જાળી માટે આઇસોમોર્ફિક (એક એડિટિવ ગ્રુપ તરીકે) છે, અને કોઈપણ આદર્શ અનુરૂપ પૂર્ણાંક સબલેટિસને વ્યાખ્યાયિત કરે છે. એક આદર્શ જાળી એ એક પૂર્ણાંક જાળી છે જે ડિગ્રી અને આદર્શની કેટલીક મોનિક બહુપદી માટે હોય છે. સંબંધિત ગુણધર્મો તે તારણ આપે છે કે પરિણામી કાર્ય અથડામણ પ્રતિરોધક હોવા માટેના સંબંધિત ગુણધર્મો છેઃ ઇરેડ્યુસિબલ હોવા જોઈએ. માત્રાત્મક અર્થમાં, રિંગ નોર્મ કોઈપણ બહુપદી કરતાં ઘણું મોટું નથી. પ્રથમ ગુણધર્મ સૂચવે છે કે વીંટીનો દરેક આદર્શ પૂર્ણ-ક્રમની જાળીને વ્યાખ્યાયિત કરે છે અને સાબિતીમાં મૂળભૂત ભૂમિકા ભજવે છે. લેમ્માઃ દરેક આદર્શ, જ્યાં ડિગ્રીની મોનિક, ઈરીડ્યુસિબલ પૂર્ણાંક બહુપદી છે, તે પૂર્ણ-ક્રમની જાળી માટે આઇસોમોર્ફિક છે. ડિંગ અને લિન્ડનરે પુરાવા આપ્યા હતા કે આદર્શ જાળીઓને સામાન્ય જાળીઓથી અલગ પાડવાનું બહુપદી સમયમાં કરી શકાય છે અને દર્શાવ્યું હતું કે વ્યવહારમાં અવ્યવસ્થિત રીતે પસંદ કરેલી જાળીઓ ક્યારેય આદર્શ હોતી નથી. તેઓ માત્ર એવા કેસને ધ્યાનમાં લેતા હતા કે જ્યાં જાળીનો સંપૂર્ણ ક્રમ હોય, એટલે કે. આધારમાં રેખીય સ્વતંત્ર વેક્ટરનો સમાવેશ થાય છે. આ મૂળભૂત પ્રતિબંધ નથી કારણ કે લ્યુબાશેવ્સ્કી અને મિસિએનસિઓએ બતાવ્યું છે કે જો જાળી ઇરેડ્યુસિબલ મોનિક બહુપદીના સંદર્ભમાં આદર્શ છે, તો તેને સંપૂર્ણ ક્રમ છે, જે ઉપરના લેમ્મામાં આપવામાં આવ્યો છે. અલ્ગોરિધમઃ સંપૂર્ણ ક્રમના પાયા સાથે આદર્શ જાળીઓને ઓળખવી માહિતીઃ સંપૂર્ણ ક્રમના આધારે પરિણામઃ સાચું અને, જો આદર્શ જાળીના સંદર્ભમાં ફેલાયેલું હોય, તો અન્યથા ખોટું. એચ. એન. એફ. ગણતરીમાં રૂપાંતરિત કરો, અને ઉત્પાદનની ગણતરી કરો જો માત્ર પી ની છેલ્લી કોલમ બિન-શૂન્ય હોય તો પછી આ કોલમ બરાબર કરવા માટે સેટ કરો નહીં તો ખોટા પાછા ફરો જો શોધવા માટે સી. આર. ટી. નો ઉપયોગ કરો અને અન્યથા ખોટા પાછા ફરો જો પછી સાચા પાછા ફરો, નહીં તો ખોટા પાછા ફરો જ્યાં મેટ્રિક્સ એમ છે આ અલ્ગોરિધમનો ઉપયોગ કરીને, તે જોઈ શકાય છે કે ઘણા જાળીઓ આદર્શ જાળી નથી. ઉદાહરણ તરીકે, ચાલો અને, પછી આદર્શ છે, પરંતુ નથી. તેનું ઉદાહરણ લ્યુબાશેવ્સ્કી અને મિકિઆન્સિઓ દ્વારા આપવામાં આવ્યું છે. તેના પર અલ્ગોરિધમનો અમલ કરવો અને આધારને બી તરીકે ઉલ્લેખ કરવો, મેટ્રિક્સ બી પહેલેથી જ હર્માઇટ નોર્મલ ફોર્મમાં છે તેથી પ્રથમ પગલાની જરૂર નથી. નિર્ધારક એ છે, સંલગ્ન મેટ્રિક્સ અને છેવટે, ઉત્પાદન એ છે કે આ બિંદુએ અલ્ગોરિધમ બંધ થઈ જાય છે, કારણ કે જો આદર્શ જાળીનો વિસ્તાર હોય તો તેની છેલ્લી કોલમ શૂન્ય હોવી જોઈએ. સંકેતલિપીમાં ઉપયોગ કરતા માઇકાન્સિઓએ સંરચિત ચક્રીય જાળીઓના વર્ગની રજૂઆત કરી, જે બહુપદી રિંગ્સમાં આદર્શોને અનુરૂપ હોય છે, અને ચક્રીય જાળીઓ માટે પોલી (એન)-એસવીપીના પ્રતિબંધની સૌથી ખરાબ-કેસ કઠિનતાના આધારે પ્રથમ સાબિત સુરક્ષિત એક-માર્ગી કાર્ય રજૂ કર્યું. (સમસ્યા γ-SVP આપેલ જાળીના બિન-શૂન્ય વેક્ટરની ગણતરીમાં છે, જેનું ધોરણ ટૂંકા બિન-શૂન્ય જાળી વેક્ટરના ધોરણ કરતાં γ ગણું વધારે મોટું નથી.) તે જ સમયે, તેના બીજગણિત માળખાને કારણે, આ એક તરફી કાર્ય એનટીઆરયુ યોજનાના મૂલ્યાંકન સમય અને સંગ્રહ ખર્ચની સરખામણીમાં ઉચ્ચ કાર્યક્ષમતાનો આનંદ માણે છે). ત્યારબાદ, લ્યુબાશેવ્સ્કી અને મિસિએનસિઓ અને સ્વતંત્ર રીતે પેઇકર્ટ અને રોઝને કાર્યક્ષમ અને સાબિત રીતે સુરક્ષિત અથડામણ પ્રતિરોધક હેશ કાર્યનું નિર્માણ કરવા માટે મિસિએનસિઓના કાર્યમાં કેવી રીતે ફેરફાર કરવો તે દર્શાવ્યું. આ માટે, તેઓએ આદર્શ જાળીનો વધુ સામાન્ય વર્ગ રજૂ કર્યો, જે બહુપદી રિંગ્સમાં આદર્શોને અનુરૂપ છે. અથડામણ પ્રતિકાર પોલી (એન)-એસવીપીથી આદર્શ જાળી (જેને પોલી (એન)-આઇડિયલ-એસવીપી કહેવાય છે) ના પ્રતિબંધની કઠિનતા પર આધાર રાખે છે. સરેરાશ-કેસ અથડામણ-શોધવાની સમસ્યા એ આદર્શ-એસ. આઈ. એસ. નામની એક કુદરતી ગણતરીની સમસ્યા છે, જે આદર્શ-એસ. વી. પી. ના સૌથી ખરાબ-કેસના ઉદાહરણો જેટલી જ મુશ્કેલ હોવાનું દર્શાવવામાં આવ્યું છે. આદર્શ જાળીઓથી સુરક્ષિત કાર્યક્ષમ હસ્તાક્ષર યોજનાઓ પણ પ્રસ્તાવિત કરવામાં આવી છે, પરંતુ આદર્શ જાળીઓથી કાર્યક્ષમ સાબિત સુરક્ષિત જાહેર કી એન્ક્રિપ્શનનું નિર્માણ એક રસપ્રદ ખુલ્લી સમસ્યા હતી. કી એક્સચેન્જ માટે LWE અને રીંગ LWE નો ઉપયોગ કરવાનો મૂળભૂત વિચાર પ્રસ્તાવિત કરવામાં આવ્યો હતો અને 2011 માં સિનસિનાટી યુનિવર્સિટીમાં જિન્તાઈ ડિંગ દ્વારા દાખલ કરવામાં આવ્યો હતો અને રીંગ LWE નો ઉપયોગ કરીને ક્વોન્ટમ પ્રતિરોધક કી એક્સચેન્જનું અદ્યતન વર્ણન પ્રદાન કર્યું હતું. 2012 માં કામચલાઉ પેટન્ટ અરજી દાખલ કરવામાં આવ્યા બાદ પેપર 2012 માં દેખાયું હતું. 2014 માં, પિકર્ટે ડિંગના સમાન મૂળભૂત વિચારને અનુસરીને એક મુખ્ય પરિવહન યોજના રજૂ કરી હતી, જ્યાં ડિંગના બાંધકામમાં ગોળાકાર કરવા માટે વધારાના સંકેત મોકલવાના નવા વિચારનો પણ ઉપયોગ કરવામાં આવે છે. સમાન વિભાવનાઓનો ઉપયોગ કરીને ડિજિટલ હસ્તાક્ષર ઘણા વર્ષો પહેલા વાદિમ લ્યુબાશેવ્સ્કી દ્વારા "ટ્રેપડોર્સ વિના જાળી સહીઓ" માં કરવામાં આવ્યા હતા. સાથે મળીને, પેઇકર્ટ અને લ્યુબાશેવ્સ્કીનું કાર્ય સમાન સુરક્ષા ઘટાડા સાથે રીંગ-એલડબલ્યુઇ આધારિત ક્વોન્ટમ એટેક રેઝિસ્ટન્ટ અલ્ગોરિધમ્સનો એક સમૂહ પ્રદાન કરે છે. કાર્યક્ષમ અથડામણ પ્રતિરોધક હેશ કાર્યો સંકેતલિપીમાં આદર્શ જાળીઓની મુખ્ય ઉપયોગીતા એ હકીકત પરથી ઉદ્ભવે છે કે આવા જાળીઓમાં અંદાજિત ટૂંકા વેક્ટર શોધવાની કઠિનતાના આધારે ખૂબ જ કાર્યક્ષમ અને વ્યવહારુ અથડામણ પ્રતિરોધક હેશ કાર્યો બનાવી શકાય છે. પીકર્ટ અને રોસેન, તેમજ લ્યુબાશેવ્સ્કી અને મિકિયાન્સિઓ દ્વારા સ્વતંત્ર રીતે અથડામણ પ્રતિરોધક હેશ કાર્યોનું નિર્માણ કરવામાં આવ્યું હતું, જે આદર્શ જાળી (ચક્રીય જાળીનું સામાન્યીકરણ) પર આધારિત હતું અને ઝડપી અને વ્યવહારુ અમલીકરણ પૂરું પાડ્યું હતું. આ પરિણામોએ ઓળખ યોજનાઓ અને સહીઓ સહિત અન્ય કાર્યક્ષમ ક્રિપ્ટોગ્રાફિક બાંધકામો માટે માર્ગ મોકળો કર્યો. લ્યુબાશેવ્સ્કી અને મિસિએનસિઓએ કાર્યક્ષમ અથડામણ પ્રતિરોધક હેશ વિધેયોની રચનાઓ આપી હતી જે આદર્શ જાળી માટે ટૂંકી વેક્ટર સમસ્યાની સૌથી ખરાબ સ્થિતિની કઠિનતાના આધારે સુરક્ષિત સાબિત થઈ શકે છે. તેઓએ હેશ ફંક્શન પરિવારોને આ રીતે વ્યાખ્યાયિત કર્યાઃ રિંગને જોતાં, જ્યાં ડિગ્રીની મોનિક, ઈરીડ્યુસિબલ બહુપદી છે અને આશરે ક્રમનો પૂર્ણાંક છે, તે રેન્ડમ તત્વો ઉત્પન્ન કરે છે, જ્યાં અચળાંક છે. ઓર્ડર કરેલું-ટુપલ હેશ કાર્ય નક્કી કરે છે. તે તત્વોનો નકશો બનાવશે, જ્યાં વ્યૂહાત્મક રીતે પસંદ કરેલ ઉપગણ છે. એક તત્વ માટે, હેશ છે. અહીં કી (હેશ ફંક્શન) નું કદ છે, અને બહુપદીની યોગ્ય પસંદગી માટે ફાસ્ટ ફોરિયર ટ્રાન્સફોર્મ (એફ. એફ. ટી.) નો ઉપયોગ કરીને સમયસર કામગીરી કરી શકાય છે. તે સતત હોવાથી, હેશિંગ માટે સમયની જરૂર પડે છે. તેઓએ સાબિત કર્યું કે હેશ ફંક્શન ફેમિલી અથડામણ પ્રતિરોધક છે તે દર્શાવીને કે જો કોઈ બહુપદી-સમય અલ્ગોરિધમ હોય જે શોધવામાં બિન-નગણ્ય સંભાવના સાથે સફળ થાય છે, જેમ કે, અવ્યવસ્થિત રીતે પસંદ કરેલા હેશ ફંક્શન માટે, તો "ટૂંકી વેક્ટર સમસ્યા" તરીકે ઓળખાતી ચોક્કસ સમસ્યા રિંગના દરેક આદર્શ માટે બહુપદી સમયમાં ઉકેલી શકાય છે. 2006માં લ્યુબાશેવ્સ્કી અને મિસિએનસિઓના કાર્યના આધારે, મિસિએનસિઓ અને રેગેવે આદર્શ જાળીઓના આધારે હેશ કાર્યોના નીચેના અલ્ગોરિધમનો વ્યાખ્યાયિત કર્યા હતાઃ પરિમાણોઃ પૂર્ણાંકો સાથે, અને વેક્ટર એફ. કીઃ વેક્ટરને સ્વતંત્ર રીતે અને એકસરખી રીતે પસંદ કરવામાં આવે છે. હેશ કાર્યઃ દ્વારા આપવામાં આવે છે. અહીં પરિમાણો છે, f એ વેક્ટર છે અને તે માળખાગત બ્લોક સાથેનું બ્લોક-મેટ્રિક્સ છે. સરેરાશ (માત્ર વ્યસ્ત બહુપદી સંભાવના સાથે પણ) ટૂંકા વેક્ટર શોધવાનું એ આદર્શ જાળીઓ પર સૌથી ખરાબ કિસ્સામાં વિવિધ જાળી સમસ્યાઓ (જેમ કે અંદાજિત એસવીપી અને એસઆઈવીપી) ને ઉકેલવા જેટલું જ મુશ્કેલ છે, જો કે વેક્ટર એફ નીચેના બે ગુણધર્મોને સંતોષેઃ કોઈપણ બે એકમ વેક્ટર યુ, વી માટે, વેક્ટર [એફઆરયુ] વી નાના હોય છે (કહો, બહુપદીમાં, સામાન્ય રીતે ધોરણમાં). બહુપદી પૂર્ણાંકો પર ઈરીડ્યુસિબલ છે, એટલે કે, તે નાના ડિગ્રીના પૂર્ણાંક બહુપદીઓના ગુણાકારમાં પરિબળ નથી. પ્રથમ ગુણધર્મ સર્ક્યુલન્ટ મેટ્રિસીસને અનુરૂપ વેક્ટર દ્વારા સંતુષ્ટ થાય છે, કારણ કે [F ≤u] v ના તમામ કોઓર્ડિનેટ્સ 1 દ્વારા બંધાયેલા છે, અને તેથી. જો કે, તેને અનુરૂપ બહુપદી ઈરીડ્યુસિબલ નથી કારણ કે તે પરિબળ બને છે, અને તેથી જ અથડામણને અસરકારક રીતે શોધી શકાય છે. તેથી, અથડામણ પ્રતિરોધક હેશ ફંક્શન્સ મેળવવા માટે સારી પસંદગી નથી, પરંતુ અન્ય ઘણી પસંદગીઓ શક્ય છે. ઉદાહરણ તરીકે, f ની કેટલીક પસંદગીઓ કે જેના માટે બંને ગુણધર્મો સંતુષ્ટ છે (અને તેથી, સૌથી ખરાબ-કેસ સુરક્ષા બાંયધરીઓ સાથે અથડામણ પ્રતિરોધક હેશ કાર્યોમાં પરિણમે છે) જ્યાં મુખ્ય છે, અને 2 ની ઘાત બરાબર છે. ડિજિટલ સિગ્નેચર ડિજિટલ સિગ્નેચર યોજનાઓ સૌથી મહત્વપૂર્ણ ક્રિપ્ટોગ્રાફિક પ્રિમિટિવ્સ પૈકીની એક છે. જાળીની સમસ્યાઓની સૌથી ખરાબ સ્થિતિની કઠિનતાના આધારે એક તરફી કાર્યોનો ઉપયોગ કરીને તેઓ મેળવી શકાય છે. જોકે, તેઓ અવ્યવહારુ છે. ભૂલો સાથે શીખવું, ભૂલો સાથે રિંગ લર્નિંગ અને ટ્રેપડોર લેટીસ પર આધારિત સંખ્યાબંધ નવી ડિજિટલ હસ્તાક્ષર યોજનાઓ વિકસાવવામાં આવી છે કારણ કે ભૂલો સાથે શીખવાની સમસ્યાને ક્રિપ્ટોગ્રાફિક સંદર્ભમાં લાગુ કરવામાં આવી હતી. આદર્શ (દા. ત., ચક્રીય) જાળીમાં ટૂંકા વેક્ટરની અંદાજિત જટિલતાના આધારે ડિજિટલ સહીઓનું તેમનું સીધું નિર્માણ. લ્યુબાશેવ્સ્કી અને મિકીઆન્સીયોની યોજના આદર્શ જાળી પર આધારિત સૌથી ખરાબ સુરક્ષા બાંયધરી ધરાવે છે અને તે આજની તારીખમાં જાણીતું સૌથી એસિમ્પ્ટોટિકલી કાર્યક્ષમ બાંધકામ છે, જે લગભગ રેખીય સમયમાં ચાલતા હસ્તાક્ષર ઉત્પાદન અને ચકાસણી અલ્ગોરિધમ્સ આપે છે. તેમના કાર્ય દ્વારા ઉઠાવવામાં આવેલી મુખ્ય ખુલ્લી સમસ્યાઓમાંની એક સમાન કાર્યક્ષમતા સાથે એક વખતની સહીનું નિર્માણ છે, પરંતુ નબળી કઠિનતાની ધારણા પર આધારિત છે. દાખલા તરીકે, સૌથી ટૂંકી વેક્ટર સમસ્યા (એસ. વી. પી.) (આદર્શ જાળીમાં) ને એક પરિબળમાં અંદાજિત કરવાની કઠિનતાના આધારે સુરક્ષા સાથે એક વખતની સહી પ્રદાન કરવી સારી રહેશે. તેમની રચના એક વખતની સહીઓ (એટલે કે એક વખતની સહીઓ) માંથી પ્રમાણભૂત પરિવર્તન પર આધારિત છે. સહીઓ કે જે સુરક્ષિત રીતે એક જ સંદેશ પર સહી કરવાની મંજૂરી આપે છે) સામાન્ય હસ્તાક્ષર યોજનાઓમાં, એક સાથે જાળી આધારિત એક વખતના હસ્તાક્ષરની નવીન રચના સાથે, જેની સુરક્ષા આખરે કોઈપણ ઇરેડ્યુસિબલ બહુપદી માટે રિંગમાં આદર્શોને અનુરૂપ તમામ જાળીઓમાં સૌથી ટૂંકા વેક્ટરને અંદાજિત કરવાની સૌથી ખરાબ સ્થિતિ કઠિનતા પર આધારિત છે. કી-જનરેશન એલ્ગોરિધમઃ ઇનપુટઃ, ડિગ્રીની ઈરીડ્યુસિબલ બહુપદી. સેટ કરો, બધા પોઝિટિવ માટે, સેટને આ રીતે વ્યાખ્યાયિત કરવા દોઃ જેમ કે સમાનરૂપે રેન્ડમ પસંદ કરો એક સમાન રીતે રેન્ડમ સ્ટ્રિંગ પસંદ કરો જો પછી સેટ કરો અન્ય સેટ કરો સ્ટ્રિંગના અંતમાં પ્રથમ 1 ની સ્થિતિ પર સેટ કરો જો અનુક્રમે અને તેમાંથી રેન્ડમ રીતે સ્વતંત્ર રીતે અને સમાન રીતે પસંદ કરો. ચકાસણી કીઃ અલ્ગોરિધમ પર સહી કરવીઃ ઇનપુટઃ સંદેશ એવી રીતે મોકલો કે; કી આઉટપુટ પર સહી કરવીઃ ચકાસણી અલ્ગોરિધમઃ ઇનપુટઃ સંદેશ; હસ્તાક્ષર; ચકાસણી કી આઉટપુટઃ "સ્વીકારો", જો અને "રદ કરો", અન્યથા. સ્વિફ્ટ હેશ કાર્ય હેશ કાર્ય ખૂબ કાર્યક્ષમ છે અને જટિલ સંખ્યાઓ પર ફાસ્ટ ફોરિયર ટ્રાન્સફોર્મ (એફ. એફ. ટી.) નો ઉપયોગ કરીને સમયસર એસિમ્પ્ટોટિક રીતે ગણતરી કરી શકાય છે. જો કે, વ્યવહારમાં, આ નોંધપાત્ર ઓવરહેડ ધરાવે છે. માઇકિયાનસિઓ અને રેગેવ દ્વારા વ્યાખ્યાયિત હેશ કાર્યોનું સ્વિફ્ટ કુટુંબ આવશ્યકપણે (એફ. એફ. ટી.) નો ઉપયોગ કરીને ઉપરના હેશ કાર્યનું અત્યંત ઑપ્ટિમાઇઝ કરેલું સ્વરૂપ છે. વેક્ટર f ને 2 ની ઘાત બરાબર માટે સુયોજિત કરવામાં આવે છે, જેથી અનુરૂપ બહુપદી ઈરીડ્યુસિબલ હોય. ચાલો એક અવિભાજ્ય સંખ્યા હોઈએ જે વિભાજીત થાય છે, અને પછીથી પસંદ કરવા માટે એક ઇન્વર્ટિબલ મેટ્રિક્સ હોઈએ. સ્વિફ્ટ હેશ ફંક્શન એક કીને મેપ કરે છે જેમાં સમાન રીતે પસંદ કરેલા વેક્ટરનો સમાવેશ થાય છે અને પહેલાની જેમ ક્યાં છે અને ક્યાં છે તે માટે ઇનપુટ છે. ઇન્વર્ટિબલ મેટ્રિક્સ દ્વારા ગુણાકાર એ એકસરખી રીતે પસંદ કરેલું અને એકસરખી રીતે પસંદ કરેલું નકશો બનાવે છે. વધુમાં, જો અને માત્ર જો. એકસાથે, આ બે હકીકતો સ્થાપિત કરે છે કે સ્વિફ્ટમાં અથડામણ શોધવી એ અંતર્ગત આદર્શ જાળી કાર્યમાં અથડામણ શોધવાની સમકક્ષ છે, અને સ્વિફ્ટના દાવો કરાયેલ અથડામણ પ્રતિકાર ગુણધર્મને આદર્શ જાળી પર સૌથી ખરાબ કેસ જાળીની સમસ્યાઓના જોડાણ દ્વારા સમર્થન આપવામાં આવે છે. સ્વિફ્ટ હેશ ફંક્શનનું અલ્ગોરિધમ છેઃ પરિમાણોઃ પૂર્ણાંકો જેમ કે 2 ની ઘાત, અવિભાજ્ય છે, અને. કીઃ વેક્ટરને સ્વતંત્ર રીતે અને એકસરખી રીતે પસંદ કરવામાં આવે છે. ઇનપુટઃ વેક્ટર. આઉટપુટઃ વેક્ટર, જ્યાં ઘટક મુજબ વેક્ટર પ્રોડક્ટ છે. ભૂલો સાથે શીખવું (એલડબલ્યુઇ) રીંગ-એલડબલ્યુઇ ભૂલો સાથે શીખવું (એલડબલ્યુઇ) સમસ્યા સૌથી ખરાબ-કેસ જાળી સમસ્યાઓ જેટલી જ મુશ્કેલ હોવાનું દર્શાવવામાં આવ્યું છે અને તેણે ઘણી ક્રિપ્ટોગ્રાફિક એપ્લિકેશનો માટે પાયો તરીકે સેવા આપી છે. જો કે, એલડબલ્યુઇ (LWE) ના ઉપયોગમાં અંતર્ગત દ્વિઘાત ઓવરહેડને કારણે આ એપ્લિકેશનો બિનકાર્યક્ષમ છે. ખરેખર કાર્યક્ષમ LWE કાર્યક્રમો મેળવવા માટે, લ્યુબાશેવ્સ્કી, પેઇકર્ટ અને રેગેવે રિંગ્સના વિશાળ વર્ગમાં LWE સમસ્યાના યોગ્ય સંસ્કરણને વ્યાખ્યાયિત કર્યું અને આ રિંગ્સમાં આદર્શ જાળીઓ પર સૌથી ખરાબ-કેસ ધારણાઓ હેઠળ તેની કઠિનતા સાબિત કરી. તેઓ તેમના LWE સંસ્કરણને રિંગ-LWE કહેતા હતા. ચાલો, જ્યાં સુરક્ષા પરિમાણ 2 ની ઘાત છે, તે તર્કસંગત પર ઈરીડ્યુસિબલ બનાવે છે. (આ ખાસ સાયક્લોટોમિક બહુપદીઓના પરિવારમાંથી આવે છે, જે આ કાર્યમાં વિશેષ ભૂમિકા ભજવે છે). ચાલો પૂર્ણાંક બહુપદી મોડ્યુલોની રીંગ બનીએ. (એટલે કે, અવશેષો મોડ્યુલો) ના ઘટકો સામાન્ય રીતે તેના કરતા ઓછી ડિગ્રીના પૂર્ણાંક બહુપદીઓ દ્વારા રજૂ થાય છે. ચાલો પૂરતું મોટું પબ્લિક પ્રાઇમ મોડ્યુલસ (બહુપદી દ્વારા બંધાયેલું) હોઈએ, અને પૂર્ણાંક બહુપદી મોડ્યુલો બંનેની રીંગ હોઈએ અને. ના ઘટકો-જેમના ગુણાંક છે તેના કરતા ઓછી ડિગ્રીની બહુપદીઓ દ્વારા રજૂ થઈ શકે છે. ઉપર વર્ણવેલ વર્તુળમાં, R-LWE સમસ્યાને નીચે પ્રમાણે વર્ણવી શકાય છે. ચાલો એક સમાન રેન્ડમ રીંગ એલિમેન્ટ હોઈએ, જે ગુપ્ત રાખવામાં આવે છે. પ્રમાણભૂત એલડબલ્યુઇની જેમ, હુમલાખોરનો ધ્યેય મનસ્વી રીતે ઘણા (સ્વતંત્ર) 'રેન્ડમ નોઇઝી રિંગ સમીકરણો' ને સાચા અર્થમાં એકસમાન સમીકરણોથી અલગ પાડવાનો છે. વધુ ખાસ રીતે, ઘોંઘાટીયા સમીકરણો એ સ્વરૂપના હોય છે, જ્યાં a સમાન રીતે અવ્યવસ્થિત હોય છે અને ઉત્પાદન અમુક 'નાના' અવ્યવસ્થિત ભૂલ શબ્દ દ્વારા વિચલિત થાય છે, જે ચોક્કસ વિતરણમાંથી પસંદ કરવામાં આવે છે. તેઓએ રિંગ-એલડબલ્યુઇના શોધ સંસ્કરણમાં આદર્શ જાળીઓ પર અંદાજિત એસવીપી (સૌથી ખરાબ કિસ્સામાં) થી ક્વોન્ટમ ઘટાડો આપ્યો, જ્યાં ધ્યેય મનસ્વી રીતે ઘણા ઘોંઘાટીયા ઉત્પાદનોમાંથી રહસ્ય (ઉચ્ચ સંભાવના સાથે, કોઈપણ માટે) પુનઃપ્રાપ્ત કરવાનો છે. આ પરિણામ સામાન્ય જાળીઓ માટે રેગેવના પુનરાવર્તિત ક્વોન્ટમ ઘટાડાની સામાન્ય રૂપરેખાને અનુસરે છે, પરંતુ આદર્શ જાળીઓ ઘટાડાના 'બીજગણિત' અને 'ભૌમિતિક' ઘટકો બંનેમાં કેટલાક નવા તકનીકી અવરોધો રજૂ કરે છે. તેમણે આ અવરોધોને દૂર કરવા માટે બીજગણિત સંખ્યા સિદ્ધાંતનો ઉપયોગ કર્યો, ખાસ કરીને, સંખ્યા ક્ષેત્રના કેનોનિકલ એમ્બેડિંગ અને ચાઇનીઝ રિમેઇન્ડર પ્રમેય. તેમને નીચેનો પ્રમેય મળ્યોઃ પ્રમેય ડિગ્રીનું મનસ્વી સંખ્યા ક્ષેત્ર હોઈ શકે છે. ચાલો મનસ્વી હોઈએ, અને (તર્કસંગત) પૂર્ણાંક મોડ્યુલસ એવું હોવું જોઈએ. જ્યાંથી-થી-સુધી સંભવિત બહુપદી-સમય ક્વોન્ટમ ઘટાડો છે. 2013માં, ગુનીસુ, લ્યુબાશેવ્સ્કી અને પોપલેમેને રિંગ લર્નિંગ વિથ એરર્સ પ્રોબ્લેમ પર આધારિત ડિજિટલ હસ્તાક્ષર યોજનાનો પ્રસ્તાવ મૂક્યો હતો. 2014 માં, પિકર્ટે તેમના પેપર, "લેટીસ ક્રિપ્ટોગ્રાફી ફોર ધ ઇન્ટરનેટ" માં રિંગ લર્નિંગ વિથ એરર્સ કી એક્સચેન્જ (RLWE-KEX) રજૂ કર્યું હતું. સિંઘના કાર્ય દ્વારા આનો વધુ વિકાસ થયો હતો. આદર્શ-એલડબલ્યુઈ સ્ટેહલે, સ્ટેઇનફેલ્ડ, તનાકા અને ઝાગાવાએ આદર્શ જાળીઓમાં અંદાજિત એસવીપીની સૌથી ખરાબ સ્થિતિની કઠિનતાના આધારે કાર્યક્ષમ જાહેર કી એન્ક્રિપ્શન યોજનાનું વર્ણન કરવા માટે એલડબલ્યુઈ સમસ્યા (આદર્શ-એલડબલ્યુઈ) ના માળખાગત સ્વરૂપને વ્યાખ્યાયિત કર્યું છે. આ પ્રથમ સી. પી. એ.-સુરક્ષિત જાહેર કી એન્ક્રિપ્શન યોજના છે જેની સુરક્ષા સબએક્સપોનેન્શલ ક્વોન્ટમ હુમલાઓ સામે-આઇડિયલ-એસ. વી. પી. ના સૌથી ખરાબ-કેસના ઉદાહરણોની કઠિનતા પર આધાર રાખે છે. તે એસિમ્પ્ટોટિક રીતે શ્રેષ્ઠ કાર્યક્ષમતા પ્રાપ્ત કરે છેઃ જાહેર/ખાનગી કીની લંબાઈ બિટ્સ છે અને અમોર્ટાઇઝ્ડ એન્ક્રિપ્શન/ડિક્રિપ્શન ખર્ચ એ બિટ ઓપરેશન્સ પ્રતિ મેસેજ બીટ છે (બિટને એક જ સમયે, કિંમતે એન્ક્રિપ્ટ કરવું). અહીં સુરક્ષા ધારણા એ છે કે-આઇડિયલ-એસવીપી કોઈપણ સબએક્સપોનેન્શિયલ ટાઇમ ક્વોન્ટમ અલ્ગોરિધમ દ્વારા ઉકેલી શકાતી નથી. તે નોંધપાત્ર છે કે આ પ્રમાણભૂત જાહેર કી ક્રિપ્ટોગ્રાફી સુરક્ષા ધારણાઓ કરતાં વધુ મજબૂત છે. બીજી બાજુ, મોટાભાગની જાહેર કી ક્રિપ્ટોગ્રાફીથી વિપરીત, જાળી આધારિત ક્રિપ્ટોગ્રાફી સબએક્સપોનેન્શિયલ ક્વોન્ટમ હુમલાઓ સામે સુરક્ષાની મંજૂરી આપે છે. સામાન્ય જાળી પર આધારિત મોટાભાગની ક્રિપ્ટોસિસ્ટમ્સ ભૂલો સાથે શીખવાની સરેરાશ-કેસ કઠિનતા (LWE) પર આધાર રાખે છે. તેમની યોજના એલડબલ્યુઇના માળખાગત સ્વરૂપ પર આધારિત છે, જેને તેઓ આદર્શ-એલડબલ્યુઇ કહે છે. આદર્શ જાળીઓના પ્રતિબંધથી ઊભી થતી બે મુખ્ય મુશ્કેલીઓને ટાળવા માટે તેમને કેટલીક તકનીકો રજૂ કરવાની જરૂર હતી. સૌપ્રથમ, અનસ્ટ્રક્ચર્ડ લેટીસ પર આધારિત અગાઉની ક્રિપ્ટોસિસ્ટમ્સ રેગેવની બાઉન્ડેડ ડિસ્ટન્સ ડીકોડિંગ પ્રોબ્લેમ (બી. ડી. ડી.) થી એલ. ડબલ્યુ. ઈ. (આ એસ. વી. પી. થી એલ. ડબલ્યુ. ઈ. માં ક્વોન્ટમ ઘટાડાનું શાસ્ત્રીય પગલું છે) સુધીના સૌથી ખરાબ કેસથી સરેરાશ કેસના શાસ્ત્રીય ઘટાડાનો ઉપયોગ કરે છે. આ ઘટાડો માનવામાં આવતી જાળીઓની બિનસંરચિતતાનો ઉપયોગ કરે છે, અને આદર્શ-એલડબલ્યુઇમાં સામેલ માળખાગત જાળીઓને વહન કરતો હોય તેવું લાગતું નથી. ખાસ કરીને, LWE મેટ્રિક્સની પંક્તિઓની સંભવિત સ્વતંત્રતા એક જ પંક્તિને ધ્યાનમાં લેવાની મંજૂરી આપે છે. બીજું, અગાઉના ક્રિપ્ટોસિસ્ટમ્સમાં ઉપયોગમાં લેવાતા અન્ય ઘટકો, એટલે કે એલડબલ્યુઇના કોમ્પ્યુટેશનલ વેરિઅન્ટમાંથી તેના નિર્ણાયક વેરિઅન્ટમાં રેગેવનો ઘટાડો, પણ આદર્શ-એલડબલ્યુઇ માટે નિષ્ફળ જણાય છેઃ તે એલડબલ્યુઇ મેટ્રિક્સના સ્તંભોની સંભવિત સ્વતંત્રતા પર આધાર રાખે છે. આ મુશ્કેલીઓને દૂર કરવા માટે, તેઓએ ઘટાડાના શાસ્ત્રીય પગલાને ટાળ્યું. તેના બદલે, તેઓએ SIS (સરેરાશ-કેસ અથડામણ-શોધ સમસ્યા) થી LWE સુધી નવા ક્વોન્ટમ સરેરાશ-કેસ ઘટાડાનું નિર્માણ કરવા માટે ક્વોન્ટમ પગલાનો ઉપયોગ કર્યો. તે આદર્શ-SIS થી આદર્શ-LWE સુધી પણ કામ કરે છે. સૌથી ખરાબ-કેસ આઇડિયલ-એસ. વી. પી. થી સરેરાશ-કેસ આઇડિયલ-એસ. આઈ. એસ. માં ઘટાડા સાથે, તેઓએ આઇડિયલ-એસ. વી. પી. થી આઇડિયલ-એલ. ડબલ્યુ. ઇ. માં ક્વોન્ટમ ઘટાડો મેળવ્યો. આ આદર્શ-LWE ના કોમ્પ્યુટેશનલ સ્વરૂપની કઠિનતા દર્શાવે છે. કારણ કે તેઓ નિર્ણયાત્મક સ્વરૂપની કઠિનતા પ્રાપ્ત કરી શક્યા ન હતા, તેઓએ એન્ક્રિપ્શન માટે સ્યુડોરાન્ડમ બિટ્સ મેળવવા માટે સામાન્ય હાર્ડકૉર કાર્યનો ઉપયોગ કર્યો હતો. આ જ કારણ છે કે તેમને એસ. વી. પી. ની ઘાતાંકીય કઠિનતા ધારણ કરવાની જરૂર હતી. સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શન એ એક સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શન (એફ. એચ. ઈ.) યોજના છે જે એન્ક્રિપ્ટેડ ડેટા પર ગણતરી માટે પરવાનગી આપે છે, પહેલા ડિક્રિપ્ટ કરવાની જરૂર વગર. સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શન યોજનાના નિર્માણની સમસ્યા સૌપ્રથમ 1978 માં રીવેસ્ટ, એડલેમેન અને ડર્ટૌઝોસ દ્વારા રજૂ કરવામાં આવી હતી, જે રીવેસ્ટ, એડલેમેન અને શમીર દ્વારા આરએસએની શોધ પછી ટૂંક સમયમાં જ રજૂ કરવામાં આવી હતી. એન્ક્રિપ્શન યોજના સર્કિટ માટે હોમોમોર્ફિક છે જો, કોઈપણ સર્કિટ માટે, આપવામાં આવે છે, અને, તે તેને ધરાવે છે. જો તે કદની તમામ સર્કિટ માટે હોમોમોર્ફિક હોય તો તે સંપૂર્ણપણે હોમોમોર્ફિક છે જ્યાં યોજનાનું સુરક્ષા પરિમાણ છે. 2009માં, જેન્ટ્રીએ સંપૂર્ણ હોમોમોર્ફિક એન્ક્રિપ્શન યોજનાના નિર્માણની સમસ્યાનો પ્રથમ ઉકેલ રજૂ કર્યો હતો. તેમની યોજના આદર્શ જાળી પર આધારિત હતી. આ પણ જુઓ લેટીસ-આધારિત ક્રિપ્ટોગ્રાફી હોમોમોર્ફિક એન્ક્રિપ્શન ભૂલો સાથે રિંગ લર્નિંગ કી એક્સચેન્જ પોસ્ટ-ક્વોન્ટમ ક્રિપ્ટોગ્રાફી ટૂંકા પૂર્ણાંક ઉકેલ સમસ્યા સંદર્ભો સંખ્યા સિદ્ધાંત લેટીસ-આધારિત ક્રિપ્ટોગ્રાફી પોસ્ટ-ક્વોન્ટમ ક્રિપ્ટોગ્રાફી