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 ω ஐத் தேர்ந்தெடுக்கவும் (43 = 64 ω1 மட்டு 7 என்பதால்). n = 3, a = (1,1,2,1) மற்றும் x = 5 (5 இன் பிட் பிரதிநிதித்துவம் 101 ஆகும்), நாம் பின்வருமாறு கணக்கிடலாம்ஃ செயல்திறன் நவோர்-ரிங்கோல்ட் கட்டுமானத்தில் செயல்பாட்டின் மதிப்பீட்டை மிகவும் திறமையாக செய்ய முடியும். எந்தவொரு குறிப்பிட்ட புள்ளியிலும் செயல்பாட்டின் மதிப்பைக் கணக்கிடுவது ஒரு மாடுலர் எக்ஸ்போனென்டியேஷன் மற்றும் n-மாடுலர் பெருக்கங்களுடன் ஒப்பிடத்தக்கது. இந்த செயல்பாட்டை வரம்புக்குட்பட்ட ஆழம் மற்றும் பல்லுறுப்புக்கோவை அளவு கொண்ட நுழைவாயில் சுற்றுகளால் இணையாக கணக்கிட முடியும். சமச்சீர் குறியாக்கம், அங்கீகாரம் மற்றும் டிஜிட்டல் கையொப்பங்கள் உள்ளிட்ட பல குறியாக்க திட்டங்களின் அடிப்படையாக நவோர்-ரிங்கோல்ட் செயல்பாட்டைப் பயன்படுத்தலாம். செயல்பாட்டின் பாதுகாப்பு ஒரு தாக்குபவர் செயல்பாட்டின் பல வெளியீடுகளைப் பார்க்கிறார் என்று வைத்துக்கொள்வோம், எ. கா. , மற்றும் கணக்கிட விரும்புகிறார். x1 = 0 என்று எளிமையாக வைத்துக்கொள்வோம், பின்னர் தாக்குபவர் மற்றும் பெறுவதற்கு இடையில் கணக்கீட்டு வேறுபாடு-ஹெல்மேன் (சி. டி. எச்) ஐ தீர்க்க வேண்டும். பொதுவாக, k இலிருந்து k + 1 க்கு நகர்வது பிட் வடிவத்தை மாற்றுகிறது, மேலும் k + 1 என்பது 2 இன் சக்தியாக இல்லாவிட்டால் ஒருவர் அடுக்கைப் பிரிக்கலாம், இதனால் கணக்கீடு முந்தைய இரண்டு முடிவுகளுக்கு இடையில் டிஃபி-ஹெல்மேன் விசையை கணக்கிடுவதற்கு ஒத்திருக்கிறது. இந்த தாக்குபவர் அடுத்த வரிசை உறுப்பை கணிக்க விரும்புகிறார். அத்தகைய தாக்குதல் மிகவும் மோசமாக இருக்கும்-ஆனால் கடினமான டிஃபி-ஹெல்மேன் சிக்கலுடன் (டிஹெச்பி) குழுக்களாக வேலை செய்வதன் மூலமும் அதை எதிர்த்துப் போராட முடியும். எடுத்துக்காட்டுஃ ஒரு தாக்குபவர் செயல்பாட்டின் பல வெளியீடுகளைக் காண்கிறார் எ. கா. , முந்தைய எடுத்துக்காட்டில் உள்ளபடி, மற்றும். பின்னர், தாக்குபவர் இந்த செயல்பாட்டின் அடுத்த வரிசை உறுப்பைக் கணிக்க விரும்புகிறார். இருப்பினும், தாக்குபவர் தெரிந்துகொள்வதிலிருந்து மற்றும் அதன் விளைவை கணிக்க முடியாது. ஒரு போலி எண் ஜெனரேட்டருக்கு மிகவும் மோசமாக இருக்கும் பிற தாக்குதல்கள் உள்ளனஃ பயனர் வெளியீட்டிலிருந்து சீரற்ற எண்களைப் பெற எதிர்பார்க்கிறார், எனவே நிச்சயமாக ஸ்ட்ரீம் கணிக்கப்படக்கூடாது, ஆனால் இன்னும் அதிகமாக, இது ஒரு சீரற்ற சரத்திலிருந்து பிரித்தறிய முடியாததாக இருக்க வேண்டும். செயல்பாட்டை மதிப்பிடுவதற்கான ஆரக்கிள் அணுகலுடன் வழிமுறையைக் குறிக்கலாம். டிஃபி-ஹெல்மேன் அனுமானம் வைத்திருக்கிறது என்று வைத்துக்கொள்வோம், ஒவ்வொரு நிகழ்தகவு பல்லுறுப்புக்கோவை நேர வழிமுறைக்கும் போதுமான அளவு பெரிய n மிகக் குறைவு என்பதை நவோர் மற்றும் ரெய்ன்கோல்ட் காட்டுகிறார்கள். முதல் நிகழ்தகவு விதை s = (p, g, a) இன் தேர்வுக்கு எடுத்துக் கொள்ளப்படுகிறது, இரண்டாவது நிகழ்தகவு p, g பை, இன்ஸ்டன்ஸ் ஜெனரேட்டரில் தூண்டப்பட்ட சீரற்ற விநியோகம் மற்றும் அனைத்து செயல்பாடுகளின் தொகுப்பிற்கும் இடையில் செயல்பாட்டின் சீரற்ற தேர்வு ஆகியவற்றிற்கு எடுத்துக் கொள்ளப்படுகிறது. நேரியல் சிக்கலானது ஒரு வரிசை குறியாக்க நோக்கங்களுக்காக எவ்வளவு பயனுள்ளதாக இருக்கும் என்பதற்கான ஒரு இயற்கையான அளவீடு அதன் நேரியல் சிக்கலின் அளவு ஆகும். ஒரு வளையத்தின் மீது உள்ள ஒரு n-உறுப்பு வரிசை W (x), x = 0,1,2,., n-1 இன் நேரியல் சிக்கலானது, குறுகிய நேரியல் மறுநிகழ்வு உறவின் நீளம் l ஆகும் 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 ஒரு நீள்வட்ட வளைவாக இருக்கட்டும், பின்னர் ஒவ்வொரு திசையனும் துணைக்குழுவில் ஒரு வரையறுக்கப்பட்ட வரிசையை பின்வருமாறு வரையறுக்கிறதுஃ முழு எண்ணின் பிட் பிரதிநிதித்துவம் எங்கே. நார்-ரிங்கோல்ட் நீள்வட்ட வளைவு வரிசை பின்வருமாறு வரையறுக்கப்படுகிறதுஃ டிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபிஃபி சூடோரேண்டம் எண் ஜெனரேட்டர்கள் கிரிப்டோகிராஃபி