A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds

DOI10.1007/978-3-319-55911-7_42MaRDI QIDQ2988852zbMATH OpenOpenAlexFDO

Authors Maciej Skórski

Publication date 19 May 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-55911-7_42

zbMATH Keywords

boostingconvex optimizationregularity lemmascomputational indistinguishabilitylow-complexity approximations

Mathematics Subject Classification ID

Cryptography (94A60) Extremal set theory (05D05)

Recommendations

• Limits of a conjecture on a leakage-resilient cryptosystem
• A uniform-complexity treatment of encryption and zero-knowledge
• A uniform min-max theorem with applications in cryptography
• On the power of nonuniformity in proofs of security
• A Generalization of Linear Cryptanalysis and the Applicability of Matsui’s Piling-up Lemma
• Reconciling two views of cryptography (The computational soundness of formal encryption)
• scientific article; zbMATH DE number 1759457
• Leakage-resilient cryptography over large finite fields: theory and practice
• Regular lossy functions and their applications in leakage-resilient cryptography
• Number theoretic methods in cryptography. Complexity lower bounds

Cites work

• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• A simple algorithm for constructing Szemerédi's regularity partition
• A uniform min-max theorem with applications in cryptography
• How to fake auxiliary input
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Quick approximation to matrices and applications
• Szemerédi's lemma for the analyst

This page was built for publication: A Cryptographic View of Regularity Lemmas: Simpler Unified Proofs and Refined Bounds

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