배낭 암호 시스템
Knapsack cryptosystems배낭암호시스템은 배낭문제 해결의 난이도에 기반한 보안을 가진 암호시스템입니다.이러한 알고리즘의 단순한 버전이 수십 [1]년 동안 고장났기 때문에 이러한 알고리즘은 여전히 인기가 없습니다.그러나 이러한 유형의 암호 시스템은 양자화 후 [citation needed]암호화에 적합한 후보입니다.
가장 유명한 배낭 암호 시스템은 RSA 암호 시스템과 같은 해에 공개된 최초의 공개 키 암호 시스템 중 하나인 Merkle-Hellman 공개 키 암호 시스템입니다.그러나 이 시스템은 [2]Shamir로부터의 공격, Adleman의 [3]공격, 저밀도 공격 등 여러 가지 공격에 의해 파괴되었습니다.
그러나, 지금까지 안전하다고 생각되는 현대의 배낭 암호 시스템이 존재합니다.그 중에는 2006년 [4]Nasako-Murakami가 있습니다.
배낭 암호 시스템은 고전적인 암호 분석을 거치지 않을 경우 양자 컴퓨터에서도 어려울 것으로 생각됩니다.RSA와 같은 큰 정수를 인수분해하거나 ECDSA와 같은 이산 로그 계산에 의존하는 시스템에서는 Shor의 [5]알고리즘으로 다항식 시간에 해결되는 문제가 발생하지 않습니다.
레퍼런스
- ^ Schneier, Bruce (2004). Secrets and Lies. Wiley Publishing, Inc. p. 95. ISBN 978-0-471-25311-2.
- ^ Shamir 1982. 오류:: 1982
- ^ Adleman 1982. 오류:: 1982
- ^ Nasako & Murikami 2006. 오류:: Murikami 2006
- ^ Shor, Peter (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. S2CID 2337707.
참고 문헌
- Leonard Adleman (1982), "On breaking the titrated Merkle-Hellman public-key cryptosystem", Crypto'82, Springer: 303–308, doi:10.1007/978-1-4757-0602-4_29, ISBN 978-1-4757-0604-8
- Adi Shamir (1982), "A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems", Focs '82: 145–152, doi:10.1109/SFCS.1982.5
- T. Nasako; Y. Murakami (2006), "A high-density knapsack cryptosystem using combined trapdoor", Japan Society for Industrial and Applied Mathematics, 16 (4): 519–605, doi:10.11540/jsiamt.16.4_591
