2
$\begingroup$

I'm currently taking a course in which we choose a stats-heavy paper and analyse it, summarising our work in the form of a written report and presentation. I have tried to find such a paper in crypto, even asking a professor who works in Information Security, but no success yet.

If possible, I'd like to be provided a list of stats-heavy papers in the field of Cryptography, or a similar field. Something related to elliptic curve crypto or how zero-knowledge proofs are used in homomorphic encryption are especially welcome.

Examples of sufficiently stats-heavy papers are:

David Aldous and Persi Diaconis. Longest increasing subsequences: from patience sorting to the baik-deift-johansson theorem. Bulletin of the American Mathematical Society, 36(4):413–432, 1999.

Benedikt Bauer and Michael Kohler. On deep learning as a remedy for the curse of dimensionality in nonparametric regression. 2019.

Bruce M Brown and Jonathan I Hewitt. Asymptotic likelihood theory for diffusion processes. Journal of Applied Probability, 12(2):228–238, 1975.

Victor J Yohai. High breakdown-point and high efficiency robust estimates for regression. The Annals of statistics, pages 642–656, 1987.

Peter J Huber. Robust regression: asymptotics, conjectures and monte carlo. The annals of statistics, pages 799–821, 1973.

Robert I Jennrich. Asymptotic properties of non-linear least squares estimators. The Annals of Mathematical Statistics, 40(2):633–643, 1969.

$\endgroup$

1 Answer 1

4
$\begingroup$

I am afraid your search for Annals of Stats etc. level of purely statistical theoretical papers in cryptology may not yield too many examples.

The field is very applied and the role of statistics is usually of the form, if this source (usually key generator) is i.i.d., uniform then such and such property holds.It is not very natural to model (other than ideal OTP) cryptosystems this way.

However, the IEEE Transactions on Information Theory does publish theoretical papers on cryptology with a probabilistic flavour.

I have some suggestions of papers to look at below:

N. Merhav and E. Arikan, "The Shannon cipher system with a guessing wiretapper", IEEE Trans. Inform. Theory, vol. 45, pp. 1860-1866, Sept. 1999.

X. Lai, J.L. Massey and S. Murphy, "Markov Ciphers and Differential Cryptanalysis", EUROCRYPT'91.

and here is one I found by searching for citations to Diaconis' work

Kulis, Lorek and Zagorski, "Randomized stopping times and provably secure pseudorandom permutation generators" available at https://eprint.iacr.org/2016/1049.pdf

Historical Anecdote: For both of Shannon's groundbreaking initial papers, A Mathematical Theory of Cryptography and A Mathematical Theory of Communication (see https://evervault.com/papers/shannon ) for a PDF of the first, there was some criticism from pure probabilists and statisticians that the papers were not rigorous enough. Shannon was of course a towering figure of 20th century science who together with Turing enabled most of modern data communications, but these criticisms based on rigour were mostly ill-founded. Shannon was focused on applications rather than generalizing the theory to arbitrary channels. And he also obtained the zero error capacity of the pentagon graph $C_5$ which has barely been improved in the 60 years since, even though the top combinatorialists and probabilists of the Hungarian school worked on it.

For example, J. Wolfowitz re-wrote Shannon's approach to information theory using the full epsilon-delta approach and measure theory. But he was rude enough to suggest that Shannon's work was inferior, which I'm sure Shannon didn't care about but others were offended on his behalf.

Other generalizations of Shannon's work were also obtained later on but Shannon had started the field and shown the direction as well as establishing such performance measures as channel capacity, perfect secrecy, confusion and diffusion. Some of these measures are hard to define precisely in full generality but this is part of their power.

$\endgroup$
3
  • $\begingroup$ I barely remember a paper where someone to combine Linear and Differential attack under statistical attack. Do you remembner that? Isn't this fall into this? I'm not sure how much the paper accepted by the community... $\endgroup$
    – kelalaka
    Sep 15, 2023 at 17:23
  • $\begingroup$ I am not sure if it would fall under this. However it reminded me of the author Dunkelman. There is E. Biham, O. Dunkelman and N. Keller, Enhanced Differential-Linear Cryptanalysis, Advances in Cryptology – Proceedings of ASIACRYPT 2002. And other papers by the same authors. Here is a thesis on this topic from COSIC: eprint.iacr.org/2006/451.pdf $\endgroup$
    – kodlu
    Sep 15, 2023 at 20:19
  • $\begingroup$ Ok, this is an interesting thesis, too. I barely remember the author name as Sergey Vaudaney, however, I couldn't see this on their articles. So, still misery for me. Thanks. $\endgroup$
    – kelalaka
    Sep 15, 2023 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.