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.
• scientific article; zbMATH DE number 1962816
• 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
• 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 3131972 (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 1304075 (Why is no real title available?)
• scientific article; zbMATH DE number 1962816 (Why is no real title available?)
• scientific article; zbMATH DE number 2081103 (Why is no real title available?)
• scientific article; zbMATH DE number 1512694 (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
• On Some Exponential Sums
• On the statistical properties of Diffie-Hellman distributions
• Probabilistic communication complexity
• Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
• 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.
• scientific article; zbMATH DE number 1962816 (Why is no real title available?)
• 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)