A New Approximate Min-Max Theorem with Applications in Cryptography

DOI10.1007/978-3-662-48971-0_55zbMATH Open1472.68070arXiv1506.06633OpenAlexW2963639643MaRDI QIDQ3459902FDOQ3459902

Maciej Skórski

Publication date: 11 January 2016

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: We propose a novel proof technique that can be applied to attack a broad class of problems in computational complexity, when switching the order of universal and existential quantifiers is helpful. Our approach combines the standard min-max theorem and convex approximation techniques, offering quantitative improvements over the standard way of using min-max theorems as well as more concise and elegant proofs.

Full work available at URL: https://arxiv.org/abs/1506.06633

Recommendations

• A uniform min-max theorem with applications in cryptography
• scientific article; zbMATH DE number 991646
• Minimal achievable approximation ratio for MAX-MQ in finite fields
• Minimization of functionals associated with problems of cryptographic analysis of asymmetric ciphers.
• Cryptographic applications of capacity theory: on the optimality of Coppersmith's method for univariate polynomials
• scientific article; zbMATH DE number 1270243
• Minimalism in cryptography: the Even-Mansour scheme revisited
• New applications of Min-max theory
• Foundations of Information and Knowledge Systems

zbMATH Keywords

cryptographymin-max theoremsconvex approximation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Noncooperative games (91A10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

This page was built for publication: A New Approximate Min-Max Theorem with Applications in Cryptography

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