CNF를 암호화 할 수 있습니까? 수 있습니다

그것은 CNF 변환 할 수 있습니다 다른 CNF로 그러한

C

Ψ(C)
  1. 함수 는 비밀 랜덤 파라미터 에서 다항식 시간으로 계산할 수 있습니다 .
    Ψ

    r


  2. Ψ(C)

    경우만 용액을 보유 해결책을 갖는다. C

  3. r을 사용하여 의 모든 솔루션 를 효율적으로 의 솔루션으로 변환 할 수 있습니다 .
    x

    Ψ(C)

    C

    r

  4. r이 없으면
    r

    솔루션 x

    (또는 \ Psi (\ mathcal C) 의 다른 속성 Ψ(C)

    )는 \ mathcal C 해결에 도움이되지 않습니다 C

    .

그러한 \ Psi 가 있다면

Ψ

, 다른 사람들이 우리에게 계산 문제를 해결하기 위해 사용할 수 있습니다 (CNF를 다른 문제로 대체 할 수 있습니다-문제를보다 구체적으로 만들고 싶기 때문에 CNF를 선택했습니다). 그들이 우리가 어떤 문제를 해결했는지 알고 있더라도 가능한 해결책으로 이익을 얻을 수없는 방법. 예를 들어, 컴퓨터 게임에 인수 분해 문제를 포함시킬 수 있으며,이를 통해 플레이어는 때때로 계산 증명을 보내 백그라운드에서 문제에 대해 작업하는 경우에만 게임을 할 수 있습니다. 아마도 이런 방식으로 소프트웨어를 “무료”로 만들 수도 있습니다. “무료”는 부모의 전기 요금에 (아마도 더 높은) 비용을 숨길 수 있습니다.

답변

Feigenbaum의 Encrypting Problem Instances 에서는 요구 사항을 충족하는 NP-complete 문제에 대한 암호화 기능의 정의 (Def. 1)를 제안합니다. 그녀는 NP- 완전 문제 비교 벡터 불평등이 그러한 암호화 기능을 인정한다는 것을 증명합니다. 그녀는 주요 정리로 CNF-SAT와 p- 동형 인 모든 NP- 완전 문제를 암호화 할 수 있다고 결론을 내립니다.

답변

언급 한 응용 프로그램은 문헌에서 “유용한 작업 증명”이라고합니다 (예 : 이 기사 참조) .

당신은 사용할 수 있습니다 완전히 호모 모르 픽 암호화 입력을 공개하지 않고 신뢰할 수없는 자에게 계산을 위임 (일반 텍스트가 CNF의 인스턴스) 방식을.

CNF를 다른 CNF에 매핑하지는 않지만 의도 한 응용 프로그램에서는 작동하기 때문에 이것은 귀하의 질문에 정확히 답하지 않습니다.

답변