Source author record

Simon R. Blackburn

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR Information Theory math.IT Discrete Mathematics Cryptography and Security math.NT math.GT math.RA

Catalog footprint

Research overview

18works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The enumeration of finite rings

Let $p$ be a fixed prime. We show that the number of isomorphism classes of finite rings of order $p^n$ is $p^α$ , where $α=\frac{4}{27}n^3+O(n^{5/2})$ . This result was stated (with a weaker error term) by Kruse and Price in 1969; a problem with their proof was pointed out by Knopfmacher in 1973. We also show that the number of isomorphism classes of finite commutative rings of order $p^n$ is $p^β$ , where $β=\frac{2}{27}n^3+O(n^{5/2})$ . This result was stated (again with a weaker error term) by Poonen in 2008, with a proof that relies on the problematic step in Kruse and Price's argument.

preprint2021arXiv

Block-avoiding point sequencings

Let $n$ and $\ell$ be positive integers. Recent papers by Kreher, Stinson and Veitch have explored variants of the problem of ordering the points in a triple system (such as a Steiner triple system, directed triple system or Mendelsohn triple system) on $n$ points so that no block occurs in a segment of $\ell$ consecutive entries (thus the ordering is locally block-avoiding). We describe a greedy algorithm which shows that such an ordering exists, provided that $n$ is sufficiently large when compared to $\ell$ . This algorithm leads to improved bounds on the number of points in cases where this was known, but also extends the results to a significantly more general setting (which includes, for example, orderings that avoid the blocks of a design). Similar results for a cyclic variant of this situation are also established. We construct Steiner triple systems and quadruple systems where $\ell$ can be large, showing that a bound of Stinson and Veitch is reasonable. Moreover, we generalise the Stinson--Veitch bound to a wider class of block designs and to the cyclic case. The results of Kreher, Stinson and Veitch were originally inspired by results of Alspach, Kreher and Pastine, who (motivated by zero-sum avoiding sequences in abelian groups) were interested in orderings of points in a partial Steiner triple system where no segment is a union of disjoint blocks. Alspach~\emph{et al.}\ show that, when the system contains at most $k$ pairwise disjoint blocks, an ordering exists when the number of points is more than $15k-5$ . By making use of a greedy approach, the paper improves this bound to $9k+O(k^{2/3})$ .

preprint2016arXiv

A Practical Cryptanalysis of the Algebraic Eraser

Anshel, Anshel, Goldfeld and Lemieaux introduced the Colored Burau Key Agreement Protocol (CBKAP) as the concrete instantiation of their Algebraic Eraser scheme. This scheme, based on techniques from permutation groups, matrix groups and braid groups, is designed for lightweight environments such as RFID tags and other IoT applications. It is proposed as an underlying technology for ISO/IEC 29167-20. SecureRF, the company owning the trademark Algebraic Eraser, has presented the scheme to the IRTF with a view towards standardisation. We present a novel cryptanalysis of this scheme. For parameter sizes corresponding to claimed 128-bit security, our implementation recovers the shared key using less than 8 CPU hours, and less than 64MB of memory.

preprint2016arXiv

On the security of the Algebraic Eraser tag authentication protocol

The Algebraic Eraser has been gaining prominence as SecureRF, the company commercializing the algorithm, increases its marketing reach. The scheme is claimed to be well-suited to IoT applications but a lack of detail in available documentation has hampered peer-review. Recently more details of the system have emerged after a tag authentication protocol built using the Algebraic Eraser was proposed for standardization in ISO/IEC SC31 and SecureRF provided an open public description of the protocol. In this paper we describe a range of attacks on this protocol that include very efficient and practical tag impersonation as well as partial, and total, tag secret key recovery. Most of these results have been practically verified, they contrast with the 80-bit security that is claimed for the protocol, and they emphasize the importance of independent public review for any cryptographic proposal.

preprint2016arXiv

PIR Array Codes with Optimal PIR Rates

There has been much recent interest in Private information Retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient protocols. In this paper we are interested in designing PIR array codes. We consider the case when we have $m$ servers, with each server storing a fraction $(1/\omegaR)$ of the bits of the database; here $\omegaR$ is a fixed rational number with $\omegaR > 1$. We study the maximum PIR rate of a PIR array code with the $k$ -PIR property (which enables a $k$ -server PIR protocol to be emulated on the $m$ servers), where the PIR rate is defined to be $k/m$ . We present upper bounds on the achievable rate, some constructions, and ideas how to obtain PIR array codes with the highest possible PIR rate. In particular, we present constructions that asymptotically meet our upper bounds, and the exact largest PIR rate is obtained when $1 < \omegaR \leq 2$.

preprint2015arXiv

Maximum likelihood decoding for multilevel channels with gain and offset mismatch

K.A.S. Immink and J.H. Weber recently defined and studied a channel with both gain and offset mismatch, modelling the behaviour of charge-leakage in flash memory. They proposed a decoding measure for this channel based on minimising Pearson distance (a notion from cluster analysis). The paper derives a formula for maximum likelihood decoding for this channel, and also defines and justifies a notion of minimum distance of a code in this context.

preprint2015arXiv

Non-overlapping codes

We say that a $q$ -ary length $n$ code is \emph{non-overlapping} if the set of non-trivial prefixes of codewords and the set of non-trivial suffices of codewords are disjoint. These codes were first studied by Levenshtein in 1964, motivated by applications in synchronisation. More recently these codes were independently invented (under the name \emph{cross-bifix-free} codes) by Bajić and Stojanović. We provide a simple construction for a class of non-overlapping codes which has optimal cardinality whenever $n$ divides $q$ . Moreover, for all parameters $n$ and $q$ we show that a code from this class is close to optimal, in the sense that it has cardinality within a constant factor of an upper bound due to Levenshtein from 1970. Previous constructions have cardinality within a constant factor of the upper bound only when $q$ is fixed. Chee, Kiah, Purkayastha and Wang showed that a $q$ -ary length $n$ non-overlapping code contains at most $q^n/(2n-1)$ codewords; this bound is weaker than the Levenshtein bound. Their proof appealed to the application in synchronisation: we provide a direct combinatorial argument to establish the bound of Chee \emph{et al}. We also consider codes of short length, finding the leading term of the maximal cardinality of a non-overlapping code when $n$ is fixed and $q\rightarrow \infty$ . The largest cardinality of non-overlapping codes of lengths $3$ or less is determined exactly.

preprint2015arXiv

Pearson codes

The Pearson distance has been advocated for improving the error performance of noisy channels with unknown gain and offset. The Pearson distance can only fruitfully be used for sets of $q$ -ary codewords, called Pearson codes, that satisfy specific properties. We will analyze constructions and properties of optimal Pearson codes. We will compare the redundancy of optimal Pearson codes with the redundancy of prior art $T$ -constrained codes, which consist of $q$ -ary sequences in which $T$ pre-determined reference symbols appear at least once. In particular, it will be shown that for $q\le 3$ the $2$ -constrained codes are optimal Pearson codes, while for $q\ge 4$ these codes are not optimal.

preprint2015arXiv

Probabilistic existence results for separable codes

Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, $\overline{t}$ -separable codes lie somewhere between $t$ -frameproof and $(t-1)$ -frameproof codes: all $t$ -frameproof codes are $\overline{t}$ -separable, and all $\overline{t}$ -separable codes are $(t-1)$ -frameproof. Results for frameproof codes show that (when $q$ is large) there are $q$ -ary $\overline{t}$ -separable codes of length $n$ with approximately $q^{\lceil n/t\rceil}$ codewords, and that no $q$ -ary $\overline{t}$ -separable codes of length $n$ can have more than approximately $q^{\lceil n/(t-1)\rceil}$ codewords. The paper provides improved probabilistic existence results for $\overline{t}$ -separable codes when $t\geq 3$ . More precisely, for all $t\geq 3$ and all $n\geq 3$ , there exists a constant $κ$ (depending only on $t$ and $n$ ) such that there exists a $q$ -ary $\overline{t}$ -separable code of length $n$ with at least $κq^{n/(t-1)}$ codewords for all sufficiently large integers $q$ . This shows, in particular, that the upper bound (derived from the bound on $(t-1)$ -frameproof codes) on the number of codewords in a $\overline{t}$ -separable code is realistic. The results above are more surprising after examining the situation when $t=2$ . Results due to Gao and Ge show that a $q$ -ary $\overline{2}$ -separable code of length $n$ can contain at most $\frac{3}{2}q^{2\lceil n/3\rceil}-\frac{1}{2}q^{\lceil n/3\rceil}$ codewords, and that codes with at least $κq^{2n/3}$ codewords exist. So optimal $\overline{2}$ -separable codes behave neither like $2$ -frameproof nor $1$ -frameproof codes. Also, the Gao--Ge bound is strengthened to show that a $q$ -ary $\overline{2}$ -separable code of length $n$ can have at most $q^{\lceil 2n/3\rceil}+\tfrac{1}{2}q^{\lfloor n/3\rfloor}(q^{\lfloor n/3\rfloor}-1)$ codewords.

preprint2014arXiv

Counting Additive Decompositions of Quadratic Residues in Finite Fields

We say that a set $S$ is additively decomposed into two sets $A$ and $B$ if $S = \{a+b : a\in A, \ b \in B\}$ . A. Sárközy has recently conjectured that the set $Q$ of quadratic residues modulo a prime $p$ does not have nontrivial decompositions. Although various partial results towards this conjecture have been obtained, it is still open. Here we obtain a nontrivial upper bound on the number of such decompositions.

preprint2013arXiv

Triangulations of the sphere, bitrades and abelian groups

Let $G$ be a triangulation of the sphere with vertex set $V$ , such that the faces of the triangulation are properly coloured black and white. Motivated by applications in the theory of bitrades, Cavenagh and Wanless defined $A_W$ to be the abelian group generated by the set $V$ , with relations $r+c+s=0$ for all white triangles with vertices $r$ , $c$ and $s$ . The group $A_B$ can be defined similarly, using black triangles. The paper shows that $A_W$ and $A_B$ are isomorphic, thus establishing the truth of a well-known conjecture of Cavenagh and Wanless. Connections are made between the structure of $A_W$ and the theory of asymmetric Laplacians of finite directed graphs, and weaker results for orientable surfaces of higher genus are given. The relevance of the group $A_W$ to the understanding of the embeddings of a partial latin square in an abelian group is also explained.

preprint2012arXiv

Enumerating finite racks, quandles and kei

A rack of order $n$ is a binary operation $\rack$ on a set $X$ of cardinality $n$ , such that right multiplication is an automorphism. More precisely, $(X,\rack)$ is a rack provided that the map $x\mapsto x\rack y$ is a bijection for all $y\in X$ , and $(x\rack y)\rack z=(x\rack z)\rack (y\rack z)$ for all $x,y,z\in X$ . The paper provides upper and lower bounds of the form $2^{cn^2}$ on the number of isomorphism classes of racks of order $n$ . Similar results on the number of isomorphism classes of quandles and kei are obtained. The results of the paper are established by first showing how an arbitrary rack is related to its operator group (the permutation group on $X$ generated by the maps $x\mapsto x\rack y$ for $y\in Y$ ), and then applying some of the theory of permutation groups. The relationship between a rack and its operator group extends results of Joyce and of Ryder; this relationship might be of independent interest.

preprint2012arXiv

The probability that a pair of elements of a finite group are conjugate

Let $G$ be a finite group, and let $κ(G)$ be the probability that elements $g$ , $h\in G$ are conjugate, when $g$ and $h$ are chosen independently and uniformly at random. The paper classifies those groups $G$ such that $κ(G) \geq 1/4$ , and shows that $G$ is abelian whenever $κ(G)|G| < 7/4$ . It is also shown that $κ(G)|G|$ depends only on the isoclinism class of $G$ . Specialising to the symmetric group $S_n$ , the paper shows that $κ(S_n) \leq C/n^2$ for an explicitly determined constant $C$ . This bound leads to an elementary proof of a result of Flajolet \emph{et al}, that $κ(S_n) \sim A/n^2$ as $n\rightarrow \infty$ for some constant $A$ . The same techniques provide analogous results for $ρ(S_n)$ , the probability that two elements of the symmetric group have conjugates that commute.

preprint2011arXiv

On the Distribution of the Subset Sum Pseudorandom Number Generator on Elliptic Curves

Given a prime $p$ , an elliptic curve $\E/\F_p$ over the finite field $\F_p$ of $p$ elements and a binary \lrs\ $$u(n)$_{n =1}^\infty$ of order~ $r$ , we study the distribution of the sequence of points $\sum_{j=0}^{r-1} u(n+j)P_j, \qquad n =1,..., N,$ on average over all possible choices of $\F_p$-rational points $P_1,..., P_r$ on~$\E$. For a sufficiently large $N$ we improve and generalise a previous result in this direction due to E.~El~Mahassni.

preprint2011arXiv

The asymptotic behavior of Grassmannian codes

The iterated Johnson bound is the best known upper bound on a size of an error-correcting code in the Grassmannian $\mathcal{G}_q(n,k)$ . The iterated Schönheim bound is the best known lower bound on the size of a covering code in $\mathcal{G}_q(n,k)$ . We use probabilistic methods to prove that both bounds are asymptotically attained for fixed $k$ and fixed radius, as $n$ approaches infinity. We also determine the asymptotics of the size of the best Grassmannian codes and covering codes when $n-k$ and the radius are fixed, as $n$ approaches infinity.

preprint2010arXiv

Constructing k-radius sequences

An n-ary k-radius sequence is a finite sequence of elements taken from an alphabet of size n such that any two distinct elements of the alphabet occur within distance k of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc to model a caching strategy for computing certain functions on large data sets such as medical images. Let f_k(n) be the shortest length of any k-radius sequence. We improve on earlier estimates for f_k(n) by using tilings and logarithms. The main result is that f_k(n) ~ n^2/(2k) as n tends to infinity whenever a certain tiling of Z^r exists. In particular this result holds for infinitely many k, including all k < 195 and all k such that k+1 or 2k+1 is prime. For certain k, in particular when 2k+1 is prime, we get a sharper error term using the theory of logarithms.

preprint2010arXiv

Group theory in cryptography

This paper is a guide for the pure mathematician who would like to know more about cryptography based on group theory. The paper gives a brief overview of the subject, and provides pointers to good textbooks, key research papers and recent survey papers in the area.

preprint2010arXiv

Putting Dots in Triangles

Given a right-angled triangle of squares in a grid whose horizontal and vertical sides are $n$ squares long, let N(n) denote the maximum number of dots that can be placed into the cells of the triangle such that each row, each column, and each diagonal parallel to the long side of the triangle contains at most one dot. It has been proven that $N(n) = \lfloor \frac{2n+1}{3} \rfloor$ . In this note, we give a new proof of this result using linear programming techniques.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Simon R. Blackburn

Research overview

Is this your work?

18 publications

The enumeration of finite rings

Block-avoiding point sequencings

A Practical Cryptanalysis of the Algebraic Eraser

On the security of the Algebraic Eraser tag authentication protocol

PIR Array Codes with Optimal PIR Rates

Maximum likelihood decoding for multilevel channels with gain and offset mismatch

Non-overlapping codes

Pearson codes

Probabilistic existence results for separable codes

Counting Additive Decompositions of Quadratic Residues in Finite Fields

Triangulations of the sphere, bitrades and abelian groups

Enumerating finite racks, quandles and kei

The probability that a pair of elements of a finite group are conjugate

On the Distribution of the Subset Sum Pseudorandom Number Generator on Elliptic Curves

The asymptotic behavior of Grassmannian codes

Constructing k-radius sequences

Group theory in cryptography

Putting Dots in Triangles

See the researcher in context

Building this map preview