Diffie–Hellman problem
ಡಿಫ್ಫಿ-ಹೆಲ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯು (ಡಿಎಚ್ಪಿ) ಗುಪ್ತ ಲಿಪಿಶಾಸ್ತ್ರದ ಸಂದರ್ಭದಲ್ಲಿ ವೈಟ್ಫೀಲ್ಡ್ ಡಿಫ್ಫಿ ಮತ್ತು ಮಾರ್ಟಿನ್ ಹೆಲ್ಮ್ಯಾನ್ ಅವರು ಮೊದಲು ಪ್ರಸ್ತಾಪಿಸಿದ ಗಣಿತದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯ ಪ್ರೇರಣೆಯೆಂದರೆ, ಅನೇಕ ಭದ್ರತಾ ವ್ಯವಸ್ಥೆಗಳು ಏಕಮುಖ ಕಾರ್ಯಗಳನ್ನು ಬಳಸುತ್ತವೆಃ ಗಣಿತದ ಕಾರ್ಯಾಚರಣೆಗಳು ಲೆಕ್ಕಾಚಾರ ಮಾಡಲು ವೇಗವಾಗಿರುತ್ತವೆ, ಆದರೆ ಹಿಂತಿರುಗಿಸಲು ಕಷ್ಟ. ಉದಾಹರಣೆಗೆ, ಅವು ಸಂದೇಶವನ್ನು ಎನ್ಕ್ರಿಪ್ಟ್ ಮಾಡಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತವೆ, ಆದರೆ ಎನ್ಕ್ರಿಪ್ಶನ್ ಅನ್ನು ರಿವರ್ಸ್ ಮಾಡುವುದು ಕಷ್ಟ. ಡಿಎಚ್ಪಿ ಅನ್ನು ಪರಿಹರಿಸುವುದು ಸುಲಭವಾದರೆ, ಈ ವ್ಯವಸ್ಥೆಗಳು ಸುಲಭವಾಗಿ ಮುರಿಯಲ್ಪಡುತ್ತಿದ್ದವು. ಸಮಸ್ಯೆಯ ವಿವರಣೆ ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಸಮಸ್ಯೆಯನ್ನು ಅನೌಪಚಾರಿಕವಾಗಿ ಈ ಕೆಳಗಿನಂತೆ ಹೇಳಲಾಗಿದೆಃ ಜಿ ಅಂಶ ಮತ್ತು ಜಿಎಕ್ಸ್ ಮತ್ತು ಜಿಐನ ಮೌಲ್ಯಗಳನ್ನು ನೀಡಿದರೆ, ಜಿಎಕ್ಸಿಯ ಮೌಲ್ಯ ಏನು? ಔಪಚಾರಿಕವಾಗಿ, g ಎಂಬುದು ಕೆಲವು ಗುಂಪಿನ ಜನರೇಟರ್ ಆಗಿದೆ (ಸಾಮಾನ್ಯವಾಗಿ ಸೀಮಿತ ಕ್ಷೇತ್ರ ಅಥವಾ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಕ್ರ ಗುಂಪಿನ ಗುಣಾಕಾರ ಗುಂಪು) ಮತ್ತು x ಮತ್ತು y ಯಾದೃಚ್ಛಿಕವಾಗಿ ಆಯ್ಕೆ ಮಾಡಲಾದ ಪೂರ್ಣಾಂಕಗಳಾಗಿವೆ. ಉದಾಹರಣೆಗೆ, ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಕೀ ವಿನಿಮಯದಲ್ಲಿ, ಈವ್ಸ್ಡ್ರಾಪರ್ ಪ್ರೋಟೋಕಾಲ್ನ ಭಾಗವಾಗಿ ಜಿಎಕ್ಸ್ ಮತ್ತು ಜಿಐ ವಿನಿಮಯವನ್ನು ಗಮನಿಸುತ್ತಾನೆ ಮತ್ತು ಎರಡೂ ಪಕ್ಷಗಳು ಶೇರ್ಡ್ ಕೀ ಜಿಎಕ್ಸಿಯನ್ನು ಲೆಕ್ಕಾಚಾರ ಮಾಡುತ್ತವೆ. ಡಿ. ಎಚ್. ಪಿ. ಯನ್ನು ತ್ವರಿತವಾಗಿ ಪರಿಹರಿಸುವ ವಿಧಾನವು ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಕೀ ವಿನಿಮಯ ಮತ್ತು ಎಲ್ ಗಾಮಲ್ ಗೂಢಲಿಪೀಕರಣವನ್ನು ಒಳಗೊಂಡಂತೆ ಅದರ ಅನೇಕ ರೂಪಾಂತರಗಳ ಗೌಪ್ಯತೆಯನ್ನು ಉಲ್ಲಂಘಿಸಲು ಕದ್ದಾಲಿಕೆ ಮಾಡುವವರಿಗೆ ಅವಕಾಶ ನೀಡುತ್ತದೆ. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಗೂಢಲಿಪೀಕರಣದಲ್ಲಿ, ಕೆಲವು ಗುಂಪುಗಳಿಗೆ, ಡಿಎಚ್ಪಿ ಕಠಿಣವಾಗಿದೆ ಎಂದು ಭಾವಿಸಲಾಗಿದೆ ಮತ್ತು ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಊಹೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಈ ಸಮಸ್ಯೆಯು ಕೆಲವು ದಶಕಗಳಿಂದ ಪರಿಶೀಲನೆಯಿಂದ ಉಳಿದುಕೊಂಡಿದೆ ಮತ್ತು ಯಾವುದೇ "ಸುಲಭ" ಪರಿಹಾರವನ್ನು ಇನ್ನೂ ಪ್ರಚಾರ ಮಾಡಲಾಗಿಲ್ಲ. 2006ರಂತೆ, ಡಿ. ಎಚ್. ಪಿ. ಯನ್ನು ಪರಿಹರಿಸಲು ತಿಳಿದಿರುವ ಅತ್ಯಂತ ಪರಿಣಾಮಕಾರಿ ವಿಧಾನವೆಂದರೆ ಡಿಸ್ಕ್ರೀಟ್ ಲಾಗರಿಥಮ್ ಪ್ರಾಬ್ಲೆಮ್ (ಡಿ. ಎಲ್. ಪಿ.) ಅನ್ನು ಪರಿಹರಿಸುವುದು, ಇದು x ಅನ್ನು g ಮತ್ತು gx ಎಂದು ಕಂಡುಹಿಡಿಯುವುದು. ವಾಸ್ತವವಾಗಿ, ಅನೇಕ ಗುಂಪುಗಳಲ್ಲಿ ಡಿ. ಎಚ್. ಪಿ. ಯು ಡಿ. ಎಲ್. ಪಿ. ಯಷ್ಟೇ ಕಠಿಣವಾಗಿದೆ ಎಂಬುದನ್ನು ತೋರಿಸುವ ನಿಟ್ಟಿನಲ್ಲಿ (ಡೆನ್ ಬೋಯರ್, ಮೌರರ್, ವುಲ್ಫ್, ಬೋನ್ಹ್ ಮತ್ತು ಲಿಪ್ಟನ್ ಅವರಿಂದ) ಗಮನಾರ್ಹ ಪ್ರಗತಿಯನ್ನು ಸಾಧಿಸಲಾಗಿದೆ. ಸಾಮಾನ್ಯ ಗುಂಪುಗಳಲ್ಲಿ (ನೆಚೇವ್ ಮತ್ತು ಶೌಪ್ ಅವರಿಂದ) ಹೊರತುಪಡಿಸಿ, ಡಿಎಚ್ಪಿ ಅಥವಾ ಡಿಎಲ್ಪಿ ಕಠಿಣ ಸಮಸ್ಯೆಯಾಗಿದೆ ಎಂಬುದಕ್ಕೆ ಇಲ್ಲಿಯವರೆಗೆ ಯಾವುದೇ ಪುರಾವೆಗಳಿಲ್ಲ. ಎರಡೂ ಸಮಸ್ಯೆಗಳು ಕಠಿಣವಾಗಿವೆ ಎಂಬುದಕ್ಕೆ ಒಂದು ಪುರಾವೆಯು ಪಿ § ಎನ್. ಪಿ. ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಇತರ ರೂಪಾಂತರಗಳು ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಸಮಸ್ಯೆಯ ಅನೇಕ ರೂಪಾಂತರಗಳನ್ನು ಪರಿಗಣಿಸಲಾಗಿದೆ. ನಿರ್ಣಯಾತ್ಮಕ ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಸಮಸ್ಯೆಯು (ಡಿಡಿಎಚ್ಪಿ) ಅತ್ಯಂತ ಗಮನಾರ್ಹವಾದ ರೂಪಾಂತರವಾಗಿದೆ, ಇದು g, gx, ಮತ್ತು gy ನೀಡಿದ ಯಾದೃಚ್ಛಿಕ ಗುಂಪು ಅಂಶದಿಂದ gxy ಅನ್ನು ಪ್ರತ್ಯೇಕಿಸುತ್ತದೆ. ಕೆಲವೊಮ್ಮೆ ಡಿ. ಎಚ್. ಪಿ. ಯನ್ನು ಡಿ. ಡಿ. ಎಚ್. ಪಿ. ಯಿಂದ ಹೆಚ್ಚು ಸ್ಪಷ್ಟವಾಗಿ ಪ್ರತ್ಯೇಕಿಸಲು ಕಂಪ್ಯೂಟೇಶನಲ್ ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಪ್ರಾಬ್ಲಮ್ (ಸಿ. ಡಿ. ಎಚ್. ಪಿ.) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇತ್ತೀಚೆಗೆ ಜೋಡಿಗಳನ್ನು ಹೊಂದಿರುವ ಗುಂಪುಗಳು ಜನಪ್ರಿಯವಾಗಿವೆ, ಮತ್ತು ಈ ಗುಂಪುಗಳಲ್ಲಿ ಡಿಡಿಎಚ್ಪಿ ಸುಲಭವಾಗಿದೆ, ಆದರೂ ಡಿಹೆಚ್ಪಿ ಇನ್ನೂ ಕಠಿಣವಾಗಿದೆ ಎಂದು ಭಾವಿಸಲಾಗಿದೆ. ಡಿಎಚ್ಪಿಯ ಕಡಿಮೆ ಮಹತ್ವದ ರೂಪಾಂತರಗಳಿಗಾಗಿ ಉಲ್ಲೇಖಗಳನ್ನು ನೋಡಿ. ಬಿ. ಡೆನ್ ಬೋಯರ್, ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ನ ಉಲ್ಲೇಖಗಳು ಅಡ್ವಾನ್ಸಸ್ ಇನ್ ಕ್ರಿಪ್ಟಾಲಜಿ-ಕ್ರೈಪ್ಟೋ 88, ಲೆಕ್ಚರ್ ನೋಟ್ಸ್ ಇನ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ 403, ಸ್ಪ್ರಿಂಗರ್, ಪುಟ 530,1988 ರಲ್ಲಿ ಕೆಲವು ಅವಿಭಾಜ್ಯಗಳಿಗೆ ಪ್ರತ್ಯೇಕವಾದ ದಾಖಲೆಯಷ್ಟೇ ಪ್ರಬಲವಾಗಿವೆ. ಯು. ಎಮ್. ಮೌರರ್ ಮತ್ತು ಎಸ್. ವುಲ್ಫ್, ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಒರಾಕಲ್ ಇನ್ ಅಡ್ವಾನ್ಸಸ್ ಇನ್ ಕ್ರಿಪ್ಟಾಲಜಿ-ಕ್ರೈಪ್ಟೋ 96, (ಎನ್. ಕೊಬ್ಲಿಟ್ಜ್, ಆವೃತ್ತಿ. ), ಲೆಕ್ಚರ್ ನೋಟ್ಸ್ ಇನ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ 1070, ಸ್ಪ್ರಿಂಗರ್, ಪು. 268-282,1996. ಡಿ. ಬೋನೇಹ್ ಮತ್ತು ಆರ್. ಜೆ. ಲಿಪ್ಟನ್, ಅಲ್ಗಾರಿದಮ್ಸ್ ಫಾರ್ ಬ್ಲ್ಯಾಕ್-ಬಾಕ್ಸ್ ಫೀಲ್ಡ್ಸ್ ಅಂಡ್ ದೇರ್ ಅಪ್ಲಿಕೇಷನ್ ಟು ಕ್ರಿಪ್ಟೊಗ್ರಫಿ ಇನ್ ಅಡ್ವಾನ್ಸಸ್ ಇನ್ ಕ್ರಿಪ್ಟಾಲಜಿ-ಕ್ರೈಪ್ಟೋ 96, (ಎನ್. ಕೋಬ್ಲಿಟ್ಜ್, ಆವೃತ್ತಿ. ), ಲೆಕ್ಚರ್ ನೋಟ್ಸ್ ಇನ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ 1070, ಸ್ಪ್ರಿಂಗರ್, ಪು. 283-297,1996. ಎ. ಮುಜೇರೋ, ಎನ್. ಪಿ. ಸ್ಮಾರ್ಟ್ ಮತ್ತು ಎಫ್. ವರ್ಕೌಟರನ್, ಪ್ರಾಯೋಗಿಕ ಅನ್ವಯಿಕೆಗಳಲ್ಲಿ ಬಳಸುವ ದೀರ್ಘವೃತ್ತಾಕಾರದ ವಕ್ರಾಕೃತಿಗಳಿಗೆ ಡಿಎಚ್ಪಿ ಮತ್ತು ಡಿಎಲ್ಪಿ ನಡುವಿನ ಸಮಾನತೆ, ಎಲ್ಎಂಎಸ್ ಜೆ. ಕಂಪ್ಯೂಟ್. ಗಣಿತ., 7, ಪುಟಗಳು. 50-72,2004. [www.lms.ac.uk] ನೋಡಿ. ಡಿ. ಆರ್. ಎಲ್. ಬ್ರೌನ್ ಮತ್ತು ಆರ್. ಪಿ. ಗ್ಯಾಲಂಟ್, ದಿ ಸ್ಟ್ಯಾಟಿಕ್ ಡಿಫ್ಫಿ-ಹೆಲ್ಮನ್ ಪ್ರಾಬ್ಲಮ್, ಐಎಸಿಆರ್ ಇಪ್ರಿಂಟ್ 2004/306. ವಿ. ಐ. ನೆಚೇವ್, ಡಿಸ್ಕ್ರೀಟ್ ಲಾಗರಿಥಮ್ಗಾಗಿ ಡಿಟರ್ಮಿನೇಟ್ ಅಲ್ಗಾರಿದಮ್ನ ಸಂಕೀರ್ಣತೆ, ಮ್ಯಾಥಮೆಟಿಕಲ್ ನೋಟ್ಸ್, 55 (2), ಪು. 165-172,1994. ವಿ. ಶೌಪ್, ಲೋವರ್ ಬೌಂಡ್ಸ್ ಫಾರ್ ಡಿಸ್ಕ್ರೀಟ್ ಲಾಗರಿಥಮ್ಸ್ ಅಂಡ್ ರಿಲೇಟೆಡ್ ಪ್ರಾಬ್ಲಮ್ಸ್ ಇನ್ ಅಡ್ವಾನ್ಸಸ್ ಇನ್ ಕ್ರಿಪ್ಟಾಲಜಿ-EUROCRYPT 97, (W. ಫ್ಯುಮಿ, ಆವೃತ್ತಿ. ), ಲೆಕ್ಚರ್ ನೋಟ್ಸ್ ಇನ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ 1233, ಸ್ಪ್ರಿಂಗರ್, ಪು. 256-266,1997. ಕಂಪ್ಯೂಟೇಶನಲ್ ಗಡಸುತನದ ಊಹೆಗಳು ಸೀಮಿತ ಕ್ಷೇತ್ರಗಳು