Primal implication as encryption

Preprint English OPEN
Krupski, Vladimir (2013)
  • Subject: Computer Science - Logic in Computer Science
    acm: TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
    arxiv: Computer Science::Cryptography and Security | Computer Science::Logic in Computer Science

We propose a "cryptographic" interpretation for the propositional connectives of primal infon logic introduced by Y. Gurevich and I. Neeman and prove the corresponding soundness and completeness results. Primal implication $\imp{\varphi}{\psi}$ corresponds to the encryption of $\psi$ with a secret key $\varphi$, primal disjunction $\vp{\varphi}{\psi}$ is a group key and $\bot$ reflects some backdoor constructions such as full superuser permissions or a universal decryption key. For the logic of $\bot$ as a universal key (it was never considered before) we prove that the derivability problem has linear time complexity. We also show that the universal key can be emulated using primal disjunction.
  • References (8)

    [1] Y. Gurevich and I. Neeman. DKAL: Distributed-Knowledge Authorization Language. In Proc. of CSF 2008, pages 149-162. IEEE Computer Society, 2008.

    [2] Y. Gurevich and I. Neeman. DKAL 2 - A Simplified and Improved Authorization Language. Technical Report MSR-TR-2009-11, Microsoft Research, February 2009.

    [3] Y. Gurevich and I. Neeman. Logic of infons: the propositional case. ACM Transactions on Computational Logic, 12(2), 2011.

    [4] L. Beklemishev and Y. Gurevich. Propositional primal logic with disjunction. J. of Logic and Computation 22 (2012), 26 pages.

    [5] C. Cotrini and Y. Gurevich. Basic primal infon logic. Microsoft Research Technical Report MSR-TR-2012-88, Microsoft Research, August 2012.

    [6] A. Troelstra and H. Schwichtenberg. Basic proof theory, Cambridge Tracts in Theoretical Computer Science, 43, Cambridge University Press, Cambridge, 1996.

    [7] Oded Goldreich. Foundations of Cryptography: Volume 1, Basic Tools, Cambridge University Press, Cambridge, 2001.

    [8] M. Blum. Coin Flipping by Telephone. Proceedings of CRYPTO 1981, pp. 11-15

  • Metrics
    No metrics available
Share - Bookmark