pith. sign in

arxiv: 2508.21602 · v3 · submitted 2025-08-29 · 💻 cs.CR · cs.IT· math.IT

Condense to Conduct and Conduct to Condense

Tomasz Kazana This is my paper

Pith reviewed 2026-05-18 20:36 UTC · model grok-4.3

classification 💻 cs.CR cs.ITmath.IT
keywords low-conductance permutationsmulti-source somewhere condenserssomewhere condensersconfusion-diffusion networksindifferentiabilityexplicit constructionspermutationsconductance
0
0 comments X

The pith

Low-conductance permutations are equivalent to permutations possessing the information-theoretic properties of multi-source somewhere condensers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that permutations with low conductance are exactly those that satisfy the properties of multi-source somewhere condensers. It provides this equivalence as a general characterization and supplies the first explicit examples of such permutations. The work builds directly on the conductance notion introduced for analyzing indifferentiability of confusion-diffusion networks. A sympathetic reader would care because the link turns a search problem into an information-theoretic one, allowing constructions to transfer between the two views. This reduces the task of finding suitable permutations to one of building appropriate condensers.

Core claim

We present the first explicit examples of low-conductance permutations. We show that low-conductance permutations are equivalent to permutations possessing the information-theoretic properties of Multi-Source-Somewhere-Condensers, a specific variant of somewhere condensers. The notion of conductance of permutations was introduced by Dodis et al. in their work on indifferentiability of confusion-diffusion networks.

What carries the argument

The equivalence between low-conductance permutations and permutations that act as multi-source somewhere condensers, which maps the conductance measure to the ability to condense entropy from multiple sources.

If this is right

  • Explicit constructions of low-conductance permutations become available by adapting known multi-source somewhere condenser constructions.
  • The problem of locating low-conductance permutations reduces to the task of finding permutations with the corresponding condenser properties.
  • Properties and bounds proven for multi-source somewhere condensers transfer directly to low-conductance permutations via the equivalence.
  • Indifferentiability arguments for confusion-diffusion networks can now employ condenser-based reasoning.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The equivalence may let researchers import efficient randomness-extraction techniques to design better cryptographic permutations.
  • Similar conductance-to-condenser reductions could be explored for other combinatorial objects used in cryptography.
  • These explicit examples could be tested in simulated confusion-diffusion networks to check concrete security gains.

Load-bearing premise

The specific definition of conductance for permutations introduced by Dodis et al. is the right one that aligns with the indifferentiability goals in confusion-diffusion networks.

What would settle it

An explicit permutation that measures as low-conductance under the Dodis definition but fails to meet the multi-source somewhere condenser entropy-preservation properties, or the reverse.

read the original abstract

In this paper, we present the first explicit examples of low-conductance permutations. The notion of conductance of permutations was introduced by Dodis et al. in "Indifferentiability of Confusion-Diffusion Networks", where the search for low-conductance permutations was first initiated and motivated. As part of our contribution, we not only provide these examples, but also offer a general characterization of the problem: we show that low-conductance permutations are equivalent to permutations possessing the information-theoretic properties of Multi-Source-Somewhere-Condensers, a specific variant of somewhere condensers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims to provide the first explicit examples of low-conductance permutations, a notion introduced by Dodis et al. for analyzing indifferentiability of confusion-diffusion networks. It also presents a general characterization theorem establishing that low-conductance permutations are equivalent to permutations satisfying the information-theoretic properties of Multi-Source-Somewhere-Condensers, a specific variant of somewhere condensers.

Significance. If the equivalence holds rigorously and the constructions are explicit and verifiable, the work would be significant for bridging conductance metrics on permutations with condenser extraction guarantees. The explicit examples address an open problem left by Dodis et al., and the characterization could enable new analyses in cryptographic diffusion layers and multi-source randomness extraction.

major comments (2)
  1. [Characterization theorem] Characterization theorem (main equivalence result): the if-and-only-if direction requires explicit verification that the Dodis et al. conductance quantification (including any implicit modeling of input distributions and entropy rates) aligns exactly with the min-entropy and multi-source requirements of Multi-Source-Somewhere-Condensers without additional restrictions; any mismatch would undermine the general claim for arbitrary sources.
  2. [Explicit examples] Section presenting explicit examples: the manuscript must include concrete verification (e.g., conductance bounds or direct computation) that the given permutations satisfy the low-conductance definition, rather than relying solely on the equivalence mapping.
minor comments (2)
  1. [Preliminaries] Clarify the precise definition of the 'specific variant' of somewhere condensers used and how it differs from standard somewhere condensers in the preliminaries or introduction.
  2. [Notation and definitions] Ensure consistent notation for conductance, min-entropy, and condenser parameters across all sections and figures.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review and constructive comments. We appreciate the recognition of the significance of our explicit constructions and the characterization theorem bridging conductance and multi-source somewhere condensers. We address each major comment below.

read point-by-point responses

  1. Referee: [Characterization theorem] Characterization theorem (main equivalence result): the if-and-only-if direction requires explicit verification that the Dodis et al. conductance quantification (including any implicit modeling of input distributions and entropy rates) aligns exactly with the min-entropy and multi-source requirements of Multi-Source-Somewhere-Condensers without additional restrictions; any mismatch would undermine the general claim for arbitrary sources.

    Authors: The proof of the characterization theorem (Theorem 3.1) establishes the if-and-only-if equivalence by showing that the conductance definition, which quantifies the maximum probability of output sets under input distributions with given min-entropy rates, maps directly onto the multi-source somewhere condenser properties with identical modeling of distributions and entropy rates and no additional restrictions. To make this alignment fully explicit and address the concern, we will add a clarifying subsection in the revised manuscript that details the correspondence between the two sets of definitions. revision: yes

  2. Referee: [Explicit examples] Section presenting explicit examples: the manuscript must include concrete verification (e.g., conductance bounds or direct computation) that the given permutations satisfy the low-conductance definition, rather than relying solely on the equivalence mapping.

    Authors: We agree that including independent concrete verification strengthens the presentation of the explicit examples. In the revised manuscript we will incorporate direct conductance bounds and small-case computations for the constructed permutations to confirm they satisfy the low-conductance definition without sole reliance on the equivalence. revision: yes

Circularity Check

0 steps flagged

No significant circularity; equivalence is a derived characterization

full rationale

The paper defines low-conductance permutations via the external Dodis et al. notion and claims to prove their equivalence to permutations satisfying Multi-Source-Somewhere-Condenser properties. This is presented as a theorem and contribution alongside explicit constructions, not as a self-definition, fitted prediction, or reduction to prior self-citations. No load-bearing self-citation chains, ansatz smuggling, or renaming of known results appear in the abstract or described claims. The derivation is self-contained against external benchmarks (prior condenser literature and the cited conductance definition), with the if-and-only-if direction offered as independent content rather than forced by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are visible in the provided text. The work appears to rest on standard definitions from prior literature rather than new postulates.

pith-pipeline@v0.9.0 · 5608 in / 1023 out tokens · 31675 ms · 2026-05-18T20:36:09.385762+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages

  1. [1]

    Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures

    Divesh Aggarwal, Ivan Damg˚ ard, Jesper Buus Nielsen, Maciej Obremski, Er- ick Purwanto, Joao Ribeiro, and Mark Simkin. Stronger leakage-resilient and non-malleable secret sharing schemes for general access structures. InAdvances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceed...

    work page 2019

  2. [2]

    Non- malleable reductions and applications

    Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, and Maciej Obremski. Non- malleable reductions and applications. InProceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pages 459–468. Association for Com- puting Machinery, 2015

    work page 2015

  3. [3]

    Inception makes non- malleable codes stronger

    Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski. Inception makes non- malleable codes stronger. In Yael Kalai and Leonid Reyzin, editors,Theory of Cryptography, pages 319–343. Springer International Publishing, 2017

    work page 2017

  4. [4]

    Leakage-resilient al- gebraic manipulation detection codes with optimal parameters

    Divesh Aggarwal, Tomasz Kazana, and Maciej Obremski. Leakage-resilient al- gebraic manipulation detection codes with optimal parameters. In2018 IEEE International Symposium on Information Theory (ISIT), pages 1131–1135, 2018

    work page 2018

  5. [5]

    Extracting randomness using few independent sources.SIAM Journal on Computing, 36(4):1095–1118, 2006

    Boaz Barak, Russell Impagliazzo, and Avi Wigderson. Extracting randomness using few independent sources.SIAM Journal on Computing, 36(4):1095–1118, 2006

    work page 2006

  6. [6]

    Simulating independence: New constructions of condensers, ramsey graphs, dis- persers, and extractors.Journal of the ACM (JACM), 57(4):1–52, 2010

    Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, and Avi Wigderson. Simulating independence: New constructions of condensers, ramsey graphs, dis- persers, and extractors.Journal of the ACM (JACM), 57(4):1–52, 2010

    work page 2010

  7. [7]

    Cambridge University Press, 1996

    Mihir Bellare and Phillip Rogaway.Foundations of Cryptography: Basic Applica- tions. Cambridge University Press, 1996

    work page 1996

  8. [8]

    Merkle-damg˚ ard revisited: How to construct a hash function

    Jean-S´ ebastien Coron, Yevgeniy Dodis, C´ ecile Malinaud, and Prashant Puniya. Merkle-damg˚ ard revisited: How to construct a hash function. InAnnual Interna- tional Cryptology Conference, pages 430–448. Springer, 2005

    work page 2005

  9. [9]

    On extracting private randomness over a public channel

    Yevgeniy Dodis and Roberto Oliveira. On extracting private randomness over a public channel. InInternational Workshop on Randomization and Approximation Techniques in Computer Science, pages 252–263. Springer, 2003

    work page 2003

  10. [10]

    On the (non) universality of the one-time pad

    Yevgeniy Dodis and Joel Spencer. On the (non) universality of the one-time pad. InThe 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 376–385. IEEE, 2002

    work page 2002

  11. [11]

    Indifferentiabil- ity of confusion-diffusion networks

    Yevgeniy Dodis, Martijn Stam, John Steinberger, and Tianren Liu. Indifferentiabil- ity of confusion-diffusion networks. InCryptology ePrint Archive, Report 2015/680, 2015

    work page 2015

  12. [12]

    Non-malleable extractors and symmetric key cryptography from weak secrets

    Yevgeniy Dodis and Daniel Wichs. Non-malleable extractors and symmetric key cryptography from weak secrets. InProceedings of the 41st Annual ACM Sympo- sium on Theory of Computing (STOC), pages 601–610. ACM, 2009. 14

    work page 2009

  13. [13]

    Nearly optimal pseudorandomness from hardness.SIAM Journal on Computing, 45(2):567–600, 2016

    Dean Doron, Dana Moshkovitz, Justin Oh, and David Zuckerman. Nearly optimal pseudorandomness from hardness.SIAM Journal on Computing, 45(2):567–600, 2016

    work page 2016

  14. [14]

    Cryptographic coding for data-bank privacy

    H¨ orst Feistel. Cryptographic coding for data-bank privacy. Technical report, IBM Thomas J. Watson Research Center, 1970

    work page 1970

  15. [15]

    How to construct random functions

    Oded Goldreich, Shafi Goldwasser, and David Micali. How to construct random functions. InJournal of the ACM, volume 42, pages 742–780. ACM, 1995

    work page 1995

  16. [16]

    Expander graphs in computer science: Applications and constructions

    Mohammad Goudarzi and Igor Shinkar. Expander graphs in computer science: Applications and constructions. InIEEE Symposium on Foundations of Computer Science (FOCS), pages 45–58, 2020

    work page 2020

  17. [17]

    Graham and Joel H

    Ronald L. Graham and Joel H. Spencer. A constructive solution to a tournament problem.Canadian Mathematical Bulletin, 14(1):45–48, 1971

    work page 1971

  18. [18]

    Constructing hard functions from weak one-way functions

    Russell Impagliazzo and Valentine Kabanets. Constructing hard functions from weak one-way functions. InProceedings of the 34th Annual Symposium on Foun- dations of Computer Science (FOCS), pages 66–75. IEEE, 1999

    work page 1999

  19. [19]

    How to recycle random bits

    Russell Impagliazzo and David Zuckerman. How to recycle random bits. InProceed- ings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 248–253. IEEE, 1989

    work page 1989

  20. [20]

    Deterministic extractors for bit-fixing sources and exposure-resilient cryptography.SIAM Journal on Computing, 36(5):1231– 1247, 2007

    Jesse Kamp and David Zuckerman. Deterministic extractors for bit-fixing sources and exposure-resilient cryptography.SIAM Journal on Computing, 36(5):1231– 1247, 2007

    work page 2007

  21. [21]

    Extractors: Optimal up to constant factors

    Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. Extractors: Optimal up to constant factors. InProceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 602–611, 2003

    work page 2003

  22. [22]

    Indifferentiability, impos- sibility results on reductions, and applications to the random oracle methodology

    Ueli Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, impos- sibility results on reductions, and applications to the random oracle methodology. In Moni Naor, editor,Theory of Cryptography, pages 21–39. Springer Berlin Hei- delberg, 2004

    work page 2004

  23. [23]

    List-decodable codes and their applications.IEEE Transactions on Information Theory, 63(4):2153–2166, 2017

    Milena Mihail and Ravi Kumar. List-decodable codes and their applications.IEEE Transactions on Information Theory, 63(4):2153–2166, 2017

    work page 2017

  24. [24]

    Substitution-permutation networks, pseudorandom functions, and natural proofs

    Eric Miles and Emanuele Viola. Substitution-permutation networks, pseudorandom functions, and natural proofs. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012. Springer Berlin Heidelberg, 2012

    work page 2012

  25. [25]

    Extractors with weak random seeds

    Ran Raz. Extractors with weak random seeds. InProceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pages 11–20. ACM, 2005

    work page 2005

  26. [26]

    Extractors and condensers

    Ran Raz and Shmuel Safra. Extractors and condensers. InProceedings of STOC, pages 563–572, 2005

    work page 2005

  27. [27]

    Pseudorandomness

    Ronen Shaltiel. Pseudorandomness. InFoundations and Trends in Theoretical Computer Science, volume 7, pages 1–336, 2011. 15

    work page 2011

  28. [28]

    Recent developments in explicit constructions of extractors.Bul- letin of the EATCS, 104:67–95, 2011

    Ronen Shaltiel. Recent developments in explicit constructions of extractors.Bul- letin of the EATCS, 104:67–95, 2011

    work page 2011

  29. [29]

    CRC Press, 3rd edition, 2006

    Douglas Stinson.Cryptography: Theory and Practice. CRC Press, 3rd edition, 2006

    work page 2006

  30. [30]

    Explicit condensers with small seed length.SIAM Journal on Computing, 46(3):1111–1133, 2017

    Amos Ta-Shma. Explicit condensers with small seed length.SIAM Journal on Computing, 46(3):1111–1133, 2017

    work page 2017

  31. [31]

    Extracting randomness from samplable distribu- tions

    Luca Trevisan and Salil Vadhan. Extracting randomness from samplable distribu- tions. InProceedings 41st Annual Symposium on Foundations of Computer Science, pages 32–42. IEEE, 2000

    work page 2000

  32. [32]

    Foundations and Trends in Theoretical Computer Science, 2012

    Salil Vadhan.Pseudorandomness, volume 7. Foundations and Trends in Theoretical Computer Science, 2012

    work page 2012

  33. [33]

    Expanders that beat the eigenvalue bound: Explicit construction and applications.Combinatorica, 19(1):125–138, 1999

    Avi Wigderson and David Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications.Combinatorica, 19(1):125–138, 1999

    work page 1999

  34. [34]

    Dispersers, deterministic amplification, and weak random sources

    Aviad Cohen Wigderson. Dispersers, deterministic amplification, and weak random sources. InFoundations of Computer Science, volume 30, page 14. Citeseer, 1989. A Original Language Formulations from [11] A.1 Theorem 3, Appendix B from [11] The result quoted in the introduction: CondDegα∝§↕⌉∫∫⌉⨿⊓⊣↕1 +log(3nw) αn , providedα∝§↕⌉∫∫⌉⨿⊓⊣↕1 2−1 nw, was originall...

    work page 1989