Threshold circuit lower bounds on cryptographic functions

DOI10.1016/J.JCSS.2005.03.001MaRDI QIDQ2485284zbMATH OpenOpenAlexWikidataFDO

Authors Eike Kiltz, Hans Ulrich Simon

Publication date 3 August 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2005.03.001

zbMATH Keywords

Exponential sumsSpectral NormThreshold circuits

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Recommendations

• Complexity theoretic aspects of some cryptographic functions
• Complexity theoretic lower bounds on cryptographic functions.
• On the representation of Boolean predicates of the Diffie-Hellman function
• Geometric arguments yield better bounds for threshold circuits and distributed computing
• Lower bounds on threshold and related circuits via communication complexity

Cites work

• A linear lower bound on the unbounded error probabilistic communication complexity.
• A public key cryptosystem and a signature scheme based on discrete logarithms
• Communication complexity and Fourier coefficients of the Diffie-Hellman key
• Complexity theoretic aspects of some cryptographic functions
• Complexity theoretic lower bounds on cryptographic functions.
• Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
• Harmonic Analysis of Polynomial Threshold Functions
• scientific article; zbMATH DE number 5862918 (Why is no real title available?)
• scientific article; zbMATH DE number 52979 (Why is no real title available?)
• scientific article; zbMATH DE number 194139 (Why is no real title available?)
• scientific article; zbMATH DE number 954401 (Why is no real title available?)
• scientific article; zbMATH DE number 3091928 (Why is no real title available?)
• Majority gates vs. general weighted threshold gates
• New directions in cryptography
• New public key cryptosystems based on the dependent-RSA problems
• On Some Exponential Sums
• On the representation of Boolean predicates of the Diffie-Hellman function
• On the statistical properties of Diffie-Hellman distributions
• Primzahlverteilung
• Probabilistic communication complexity
• Public-key cryptosystems based on composite degree residuosity classes
• Relations between communication complexity, linear arrangements, and computational complexity
• Some doubly exponential sums over Z_m
• The Hadamard Maximum Determinant Problem
• Threshold circuits of bounded depth

Cited in

(4)

• Complexity theoretic aspects of some cryptographic functions
• Complexity theoretic lower bounds on cryptographic functions.
• On the representation of Boolean predicates of the Diffie-Hellman function
• Lower Bounds in the Hardware Token Model

This page was built for publication: Threshold circuit lower bounds on cryptographic functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2485284)