skip to main content
Idioma:

The Power of Negations in Cryptography

Guo, Siyao ; Malkin, Tal ; Oliveira, Igor C. ; Rosen, Alon

Theory of Cryptography, p.36-65 [Periódico revisado por pares]

Berlin, Heidelberg: Springer Berlin Heidelberg

Texto completo disponível

Citações Citado por
  • Título:
    The Power of Negations in Cryptography
  • Autor: Guo, Siyao ; Malkin, Tal ; Oliveira, Igor C. ; Rosen, Alon
  • Assuntos: Boolean Circuit ; Boolean Function ; Cryptographic Primitive ; Monotone Function ; Pseudorandom Generator
  • É parte de: Theory of Cryptography, p.36-65
  • Notas: The first author was partially supported by RGC GRF grant CUHK 410111. The second and the third author were supported in part by NSF grants CCF-116702 and CCF-1423306. The first and the third author did part of this work while visiting IDC Herzliya, supported by the ERC under the European Union’s Seventh Framework Programme (FP/2007-2013) Grant Agreement n. 307952. The fourth author was supported by ISF grant no. 1255/12 and by the ERC under the European Union’s Seventh Framework Programme (FP/2007-2013) Grant Agreement n. 307952.
  • Descrição: The study of monotonicity and negation complexity for Bool-ean functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to it in the cryptographic context. Recently, Goldreich and Izsak (2012) have initiated a study of whether cryptographic primitives can be monotone, and showed that one-way functions can be monotone (assuming they exist), but a pseudorandom generator cannot. In this paper, we start by filling in the picture and proving that many other basic cryptographic primitives cannot be monotone. We then initiate a quantitative study of the power of negations, asking how many negations are required. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following. Unlike one-way functions, one-way permutations cannot be monotone.We prove that pseudorandom functions require logn − O(1) negations (which is optimal up to the additive term).We prove that error-correcting codes with optimal distance parameters require logn − O(1) negations (again, optimal up to the additive term).We prove a general result for monotone functions, showing a lower bound on the depth of any circuit with t negations on the bottom that computes a monotone function f in terms of the monotone circuit depth of f. This result addresses a question posed by Koroth and Sarma (2014) in the context of the circuit complexity of the Clique problem.
  • Títulos relacionados: Lecture Notes in Computer Science
  • Editor: Berlin, Heidelberg: Springer Berlin Heidelberg
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.