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 ಆಗಿದೆ) ಗಳಿಗೆ, ನಾವು ಈ ಕೆಳಗಿನಂತೆ ಲೆಕ್ಕ ಹಾಕಬಹುದುಃ ದಕ್ಷತೆ ನೌರ್-ರಿಂಗೋಲ್ಡ್ ರಚನೆಯಲ್ಲಿ ಕಾರ್ಯದ ಮೌಲ್ಯಮಾಪನವನ್ನು ಬಹಳ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಮಾಡಬಹುದು. ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಹಂತದಲ್ಲಿ ಕಾರ್ಯದ ಮೌಲ್ಯವನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುವುದನ್ನು ಒಂದು ಮಾಡ್ಯುಲರ್ ಘಾತಾಂಕ ಮತ್ತು ಎನ್-ಮಾಡ್ಯುಲರ್ ಗುಣಾಕಾರಗಳೊಂದಿಗೆ ಹೋಲಿಸಬಹುದು. ಈ ಕಾರ್ಯವನ್ನು ಸುತ್ತುವರಿದ ಆಳ ಮತ್ತು ಬಹುಪದ ಗಾತ್ರದ ಮಿತಿ ಸರ್ಕ್ಯೂಟ್ಗಳಿಂದ ಸಮಾನಾಂತರವಾಗಿ ಲೆಕ್ಕ ಹಾಕಬಹುದು. ನೊರ್-ರಿಂಗೋಲ್ಡ್ ಕಾರ್ಯವನ್ನು ಸಮ್ಮಿತೀಯ ಗೂಢಲಿಪೀಕರಣ, ದೃಢೀಕರಣ ಮತ್ತು ಡಿಜಿಟಲ್ ಸಹಿಗಳನ್ನು ಒಳಗೊಂಡಂತೆ ಅನೇಕ ಗುಪ್ತ ಲಿಪಿಶಾಸ್ತ್ರದ ಯೋಜನೆಗಳಿಗೆ ಆಧಾರವಾಗಿ ಬಳಸಬಹುದು. ಕಾರ್ಯದ ಭದ್ರತೆ ಆಕ್ರಮಣಕಾರನು ಕಾರ್ಯದ ಹಲವಾರು ಫಲಿತಾಂಶಗಳನ್ನು ನೋಡುತ್ತಾನೆ ಎಂದು ಭಾವಿಸಿ, ಉದಾಹರಣೆಗೆ. , ಮತ್ತು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಬಯಸುತ್ತಾರೆ. ಸರಳತೆಗಾಗಿ 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−1W (x + l−1) +. + A0W (x), x = 0,1,2,., n-l−1 ಮತ್ತು A0,., Al−1 ω ಉದ್ದವಾಗಿದೆ. ಕೆಲವು> 0, n ≤ (1 +), ಯಾವುದೇ, ಸಾಕಷ್ಟು ದೊಡ್ಡ l ಗೆ, ಅನುಕ್ರಮದ ರೇಖೀಯ ಸಂಕೀರ್ಣತೆ, 0 ≤ x ≤ 2n-1, ಬಹುಶಃ ಹೆಚ್ಚಿನ ವಾಹಕಗಳನ್ನು ಹೊರತುಪಡಿಸಿ ಎಲ್ಲರಿಗೂ ತೃಪ್ತಿಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಈ ಕೆಲಸದ ಮಿತಿಯು ಅನಾನುಕೂಲಗಳನ್ನು ಹೊಂದಿದೆ, ಅಂದರೆ ಇದು ಅತ್ಯಂತ ಆಸಕ್ತಿದಾಯಕ ಪ್ರಕರಣವಾದ ವಿತರಣೆಯ ಏಕರೂಪತೆಗೆ ಅನ್ವಯಿಸುವುದಿಲ್ಲ ಅಂಕಿಅಂಶಗಳ ವಿತರಣೆಯು ಬಹುತೇಕ ಎಲ್ಲಾ ವಾಹಕಗಳಿಗೆ ಏಕರೂಪ ವಿತರಣೆಗೆ ಘಾತೀಯವಾಗಿ ಹತ್ತಿರದಲ್ಲಿದೆ. ಸೆಟ್ನ ವ್ಯತ್ಯಾಸವಿರಲಿ. ಹೀಗಾಗಿ, p ನ ಬಿಟ್ ಉದ್ದವಾಗಿದ್ದರೆ, ಎಲ್ಲಾ ವಾಹಕಗಳಿಗೆ a ω ಬಂಧವು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುತ್ತದೆ, ಅಲ್ಲಿ ಮತ್ತು ಈ ಗುಣಲಕ್ಷಣವು ಯಾವುದೇ ತಕ್ಷಣದ ಕ್ರಿಪ್ಟೋಗ್ರಾಫಿಕ್ ಪರಿಣಾಮಗಳನ್ನು ಹೊಂದಿಲ್ಲವೆಂದು ತೋರುತ್ತದೆಯಾದರೂ, ವಿಲೋಮ ಸತ್ಯ, ಅಂದರೆ ಏಕರೂಪವಲ್ಲದ ವಿತರಣೆ, ನಿಜವಾಗಿದ್ದರೆ ಈ ಕಾರ್ಯದ ಅನ್ವಯಗಳಿಗೆ ವಿನಾಶಕಾರಿ ಪರಿಣಾಮಗಳನ್ನು ಬೀರುತ್ತದೆ. ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಕ್ರರೇಖೆಯಲ್ಲಿನ ಅನುಕ್ರಮಗಳು ಈ ಕಾರ್ಯದ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಕ್ರರೇಖೆಯ ಆವೃತ್ತಿಯೂ ಸಹ ಆಸಕ್ತಿದಾಯಕವಾಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಇದು ಅನುಗುಣವಾದ ವ್ಯವಸ್ಥೆಯ ಗುಪ್ತ ಲಿಪಿ ಭದ್ರತೆಯನ್ನು ಸುಧಾರಿಸಲು ಸಹಾಯ ಮಾಡಬಹುದು. p> 3 ಅವಿಭಾಜ್ಯವಾಗಿರಲಿ ಮತ್ತು E ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಕ್ರರೇಖೆಯಾಗಿರಲಿ, ನಂತರ ಪ್ರತಿ ವಾಹಕ a ಉಪಗುಂಪಿನಲ್ಲಿ ಒಂದು ಸೀಮಿತ ಅನುಕ್ರಮವನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸುತ್ತದೆಃ ಪೂರ್ಣಾಂಕದ ಬಿಟ್ ಪ್ರಾತಿನಿಧ್ಯ ಎಲ್ಲಿದೆ. ನೊರ್-ರಿಂಗೋಲ್ಡ್ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಕ್ರರೇಖೆಯ ಅನುಕ್ರಮವನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ ನಿರ್ಧಾರಕ ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಊಹೆಯು ಹೊಂದಿದ್ದರೆ, ಸೂಚಕ k ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ಸಾಕಾಗುವುದಿಲ್ಲ, ಆಕ್ರಮಣಕಾರನು ಯಾದೃಚ್ಛಿಕ <ID1:// en. ವಿಕೀಪೀಡಿಯಾ. org/ವಿಕಿ/ಎಲಿಪ್ಟಿಕ್ _ ಕರ್ವ್ಗೆ ಬಹುಪದೀಯವಾಗಿ ಅನೇಕ ಪ್ರಶ್ನೆಗಳನ್ನು ಮಾಡಿದರೂ ಸಹ. ಸ್ಯೂಡೋರಾಂಡಂ ಸಂಖ್ಯೆ ಜನರೇಟರ್ಗಳು ಕ್ರಿಪ್ಟೋಗ್ರಫಿ