은 거기에 공개 키 암호화하는 알고리즘 관대 NP-하드나요?[마감]
https://stackoverflow.com/questions/311064
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
해 실제 양자 컴퓨터 현실이 되고,내가 궁금해 있는 경우에 공개 키 암호화 알고리즘을 기반으로 하는 NP-complete 문제가 아닌 정수 분해 또는 discrete logarithms.
편집:
을 확인하시기 바랍니"양자 컴퓨터에서 복잡한 계산론적으로"섹션 위키 문서에서는 양자 컴퓨터입니다. 그는 클래스의 문제 양자 컴퓨터 응답할 수 있(BQP)수 있다고 믿고 엄격하게 보다 쉽게 NP-complete.
Edit2:
'에 기반한 NP-complete 이'나쁜 표현하는 방법은 무엇에 관심이 있어요.
내가 무엇을 의도하는 요청에 대한 공개 키 암호화 알고리즘을 제공하는 모든 메서드에 대한 암호화를 사용할 수도 있습을 끊는 근본적인 NP-complete 문제입니다.이미 암호화를 증명 P=NP.
해결책
나는이 오래된 스레드가 매우 일반적이고 중요한 질문이기 때문에이 오래된 스레드에 응답하고 있으며 여기의 모든 답변은 부정확합니다.
원래 질문에 대한 짧은 대답은 명백한 "아니오"입니다. NP- 완료 문제 (따라서 다항식 시간 감소 하에서)를 기반으로하는 알려진 암호화 체계 (공공 키족은 물론)는 없다. 그러나 일부는 다른 사람들이 "더 가깝다"는 것이므로 자세히 설명하겠습니다.
여기서 명확히해야 할 것이 많으므로 "NP- 완료 문제를 기반으로하는"의 의미부터 시작하겠습니다. 이것에 대한 일반적으로 합의 된 해석은 다음과 같습니다. "NP- 완료 문제에 대해 다항식 시간 알고리즘이 존재하지 않는다고 가정 할 때 특정 공식 모델에서 안전한 것으로 입증 될 수 있습니다." 더 정확하기 위해, 우리는 알고리즘이 없다고 가정합니다. 언제나 NP- 완료 문제를 해결합니다. 이것은 알고리즘이하기가 정말 어려운 일이기 때문에 이것은 매우 안전한 가정입니다. 문제의 무작위 인스턴스를 좋은 확률로 해결하는 알고리즘을 만들기가 훨씬 쉽습니다.
그러나 암호화 체계에는 그러한 증거가 없습니다. 예외가 거의없는 문헌을 보면 (아래 참조) 보안 정리는 다음과 같이 읽습니다.
정리: 이 암호화 체계는 다항식 시간 알고리즘이 존재하지 않는다고 가정하면 일부 문제 X의 임의 인스턴스 해결.
"랜덤 인스턴스"부분에 유의하십시오. 구체적인 예의 경우, 우리는 2 개의 무작위 N- 비트 프라임의 생성물을 약간의 확률로 고려하기위한 다항식 시간 알고리즘이 존재하지 않는다고 가정 할 수 있습니다. 이것은 다항식 시간 알고리즘이 존재하지 않는다고 가정하는 것과는 매우 다릅니다 (안전하지 않음) 언제나 팩토링 모두 2 개의 무작위 N- 비트 프라임의 제품.
"랜덤 인스턴스"대 "최악의 사례 인스턴스"문제는 위의 여러 응답자를 넘어 뜨린 것입니다. McEliece- 타입 암호화 체계는 Decoding Linear Code의 매우 특별한 임의 버전을 기반으로하며 NP- 완성 된 실제 최악의 버전이 아닙니다.
이 "무작위 인스턴스"문제를 넘어서는 데는 이론적 컴퓨터 과학에 대한 깊고 아름다운 연구가 필요했습니다. Miklós Ajtai의 작업부터 시작하여, 우리는 보안 가정이 무작위 사례 대신 "최악의 경우"(보다 안전한) 가정 인 암호화 알고리즘을 발견했습니다. 불행히도, 최악의 가정은 NP 완전한 것으로 알려지지 않은 문제에 대한 것이며, 일부 이론적 증거는 NP- 완성 문제를 사용하도록 조정할 수 없다는 것을 시사합니다. 관심있는 사람들은 "격자 기반 암호화"를 찾아보십시오.
다른 팁
NP-HARD 문제에 기초한 일부 암호 시스템이 제안되었습니다 (예 : 메르클-hellman 서브 세트 서텀 문제를 기반으로하는 암호 시스템 Naccache-stern Knapsack cryptosystem 배낭 문제에 근거하여) 그러나 모두 깨졌습니다. 왜 이런거야? Scott Aaronson의 강의 16 이론적 컴퓨터 과학의 훌륭한 아이디어 이것에 대해 뭔가를 말합니다. 그것이 말하는 것은 다음과 같습니다.
이상적으로, 우리는 보안이 NP- 완료 문제를 기반으로하는 [cryptographic pseudorandom generator] 또는 cryptosystem을 구성하고 싶습니다. 불행히도 NP- 완료 문제는 항상 최악의 경우입니다. 암호화에서 이것은“거기 존재합니다 해독하기 어려운 메시지”, 암호화 시스템에 대한 보장이 아닙니다! 메시지는 압도적 인 확률로 해독하기가 어렵습니다. 수십 년의 노력에도 불구하고 NP- 완료 문제의 경우 최악의 사례와 평균 사례와 관련이있는 방법은 아직 발견되지 않았습니다. 이것이 바로 계산 보안 암호화 시스템을 원한다면 P ≠ NP보다 더 강력한 가정을해야합니다.
이었던 질문에서 1998:
의 가능성에 기초를 두는 암호화에는 가정 P!= NP 여 Oded Goldreich,이스라엘 레호보트,사피 Goldwasser
에서 추상적인:"우리의 결론은 문제는 남아 오픈".
-나는 경우는 변경 마지막 십년간에서는?
편집:
으로 지금까지 알 수 있습니다 질문은 여전히 오픈,최근 진행을 향한 응답의 이런 알고리즘이 존재합니다.
Adi Akavia,Oded Goldreich,사피 Goldwasser,그리고 데이 Moshkovitz 게시 이 논문에서 ACM2006: 에 기초를 두는 하나의 방법에서 기능한 NP-경도 "우리의 주요 연구 결과는 다음 두 가지 부정적인 결과를"
스탠포드 사이트 복잡한 동물원 에 도움이 decripting 어떤 사람들은 두 부정적인 결과를 의미합니다.
많은 형태가 고장 났지만 확인하십시오 메르클-hellman, NP- 완성 '매듭 문제'형태를 기반으로합니다.
Lattice Cryptography는 평균 케이스를 깨뜨리는 것이 특정 NP-Hard 문제 (일반적으로 가장 짧은 벡터 문제 또는 가장 가까운 벡터 문제)를 해결하는 것만 큼 어려운 암호 시스템을 설계 할 수있는 (오버) 일반화 된 집 메시지를 제공합니다.
소개 섹션을 읽는 것이 좋습니다 http://eprint.iacr.org/2008/521 그런 다음 크립토 시스템에 대한 참조를 쫓습니다.
또한 강의 노트를 참조하십시오 http://www.cs.ucsd.edu/~daniele/cse207c/, 원하는 경우 책을 링크합니다.
NP- 완성 및 공개 키 암호화에 대한 인터넷 검색은 실제로 불안한 긍정을 발견합니다. 이것 만화 PDF 에 따라 최소 지배적 세트 문제. 더 많이 읽은 다음 알고리즘이 안전하다는 것을 거짓말을 인정합니다 ... 기본 문제는 NP- 완성이지만 PK 알고리즘에 사용하면 어려움을 보존하지 않습니다.
또 다른 잘못된 긍정적 인 Google 찾기 : Crypto '97의 Goldreich-Goldwasser-Halevi Cryptosystem의 암호화. 초록에서 :
Crypto '97에서 Goldreich, Goldwasser 및 Halevi는 NP-HARD로 알려진 격자에서 가장 가까운 벡터 문제를 기반으로 한 공개 키 암호 시스템을 제안했습니다. 우리는 두 가지 의미를 갖는 체계 설계에 큰 결함이 있음을 보여줍니다. 암호 텍스트가 일반 텍스트에 대한 정보를 누출하고 암호 해독 문제는 일반적인 문제보다 훨씬 쉬운 특별한 가장 가까운 벡터 문제로 줄일 수 있습니다. .
귀하의 관심사와 관련된 웹 사이트가 있습니다. 쿼터 암호화 후.
여기 내 추론이 있습니다. 틀 렸으면 고쳐줘.
(i)``Breaking ''크립토 시스템은 반드시 NP와 Co-NP에서 문제입니다. (암호 시스템을 깨는 것은 다항식 시간에 일대일이고 계산 가능한 암호화 함수를 반전시키는 것이 포함됩니다. 따라서 암호 텍스트를 고려할 때 일반 텍스트는 다항식 시간에 확인할 수있는 인증서입니다. 따라서 암호 텍스트는 NP에 있으며 Co-NP에 있습니다.)
(ii) NP 및 CO-NP에 NP-HARD 문제가있는 경우 NP = CO-NP. (이 문제는 NP가 완료되고 Co-NP에서는 NP 언어 임의의 언어 가이 Co-NP 언어로 환원 가능하므로 NP는 Co-NP의 하위 집합입니다. 이제 대칭 : Co-NP의 모든 언어 L가 -L입니다. (칭찬) NP에서 -L은 co-np에 있는데 --------- L = -1입니다.)
(iii) i 생각한다 부울 공식이 만족스럽지 않다는 다항식 크기의 증거가 있으므로 NP! = co-np가 일반적으로 믿어진다.
결론 : 복잡성 이론적 추측은 NP- 하드 암호화 시스템이 존재하지 않음을 의미합니다.
(그렇지 않으면 NP 및 Co-NP에서 NP-HARD 문제가 있습니다.
RSA 및 기타 널리 사용되는 암호화 알고리즘은 정수 인수화의 어려움 (NP- 완성으로 알려져 있지 않음)을 기반으로하지만 NP- 완성 문제에 기반한 공개 키 암호화 알고리즘이 있습니다. "Public Key"및 "NP-Complete"에 대한 Google 검색에서 그 중 일부가 공개됩니다.
(양자 컴퓨터가 NP 완료 문제를 가속화하기 전에 잘못했지만 이것은 사실이 아닙니다. 나는 수정되었습니다.)
다른 많은 포스터에서 지적한 바와 같이, NP-HARD 또는 NP- 완료 문제를 기본으로 할 수 있습니다.
그러나 암호화를위한 일반적인 방법은 어려운 수학을 기반으로 할 것입니다 (즉, 깨지기 어렵습니다). 진실은 NP- 하드 문제를 해결하는 표준화 된 문자열을 만드는 것보다 숫자를 기존 키로 직렬화하는 것이 더 쉽다는 것입니다. 따라서 실용적인 암호는 아직 NP-HARD 또는 NP- 완성으로 입증되지 않은 수학적 문제를 기반으로합니다 (따라서 이러한 문제 중 일부는 P에있는 것으로 생각됩니다).
Elgamal 또는 RSA 암호화에서 파손되면 개별 로그를 크래킹해야하므로 이것을 살펴보십시오. 위키 백과 기사.
일반적인 이산 로그를 계산하기위한 효율적인 알고리즘이 알려져 있지 않습니다. LOGBG는 알려져 있습니다. 순진한 알고리즘은 원하는 G가 발견 될 때까지 B를 더 높고 더 높은 전력 K로 올리는 것입니다. 이것은 때때로 시험 곱셈이라고합니다. 이 알고리즘은 그룹 g 크기의 실행 시간 선형이어야하므로 그룹 크기의 숫자 수를 지수해야합니다. 그러나 Peter Shor로 인해 효율적인 양자 알고리즘이 존재합니다.http://arxiv.org/abs/quant-ph/9508027).
이산 로그 계산은 분명히 어렵습니다. 최악의 경우에도 효율적인 알고리즘이 알려져 있지 않을뿐만 아니라 평균 사례 복잡성은 무작위 자기 감소를 사용하는 최악의 경우만큼 어려운 것으로 보일 수 있습니다.
동시에, 이산 지수의 역 문제는 그렇지 않습니다 (예 : 제곱에 의해 지수를 사용하여 효율적으로 계산할 수 있음). 이 비대칭은 정수 인수 화와 정수 곱셈 사이의 것과 유사합니다. 암호화 시스템의 구성에서 두 비대칭 모두가 악용되었습니다.
광범위한 믿음은 이것들이 NP- 완성이지만 아마도 입증 될 수 없다는 것입니다. 양자 컴퓨터는 암호화를 효율적으로 깨뜨릴 수 있습니다!
아무도 실제로 질문에 대답하지 않았기 때문에 "McEliece"라는 힌트를 주어야합니다. 그것에 대해 약간의 검색을하십시오. 입증 된 NP- 하드 암호화 알고리즘입니다. O (n^2) 암호화 및 암호 해독 시간이 필요합니다. 그것은 크기 O (n^2)의 공개 키를 가지고 있으며, 이는 나쁘다. 그러나이 모든 범위를 낮추는 개선 사항이 있습니다.
