Slope packings and coverings, and generic algorithms for the discrete logarithm problem.

*(English)*Zbl 1020.11082This paper studies some problems about certain subsets of points in the Desarguesian affine plane \(AG(2,p)\), where \(p\) is a prime, and its connection with the discrete logarithm problem.

After recalling the concepts of slope packing and slope covering (a subset \(S\) of the plane \(AG(2,p)\) is called slope packing if the slopes of lines obtained by joining all pairs of points in \(S\) are distinct and non-infinite; \(S\) is called slope covering if every non-infinite slope occurs), the paper shows the connections of these objects with weak Sidon sets and sum covers.

The paper also presents two tables with explicit examples of slope packings and slope coverings for the 25 primes \(p\) smaller than 100, tables found by computer searches.

Finally, in section 4, the authors discuss the announced relationship between slope packings and coverings and a generic algorithm for the DLP in a group of prime order \(p\). As it is well known given an element \(a\) in a cyclic group \(<g>\) of order \(n\), the discrete logarithm problem (DLP) asks for the unique integer \(x\), \(0\leq x \leq n-1\), such that \(a = g^x\). The DLP is used as a one-way function in many public-key encryption and signature schemes. An algorithm for the DLP is generic if it works for arbitrary groups in opposition to algorithms that exploit some specific property of the group, as is the case of the well-known index-calculus method.

The authors show that any slope covering \(S\in AG(2,p)\) of size \(w\) leads to a construction for a deterministic generic algorithm and also a Las Vegas type algorithm for the DLP in a group \(<g>\) of order \(p\), both algorithms with computational complexity \(O(w)\). Reciprocally the authors show that a generic algorithm for the DLP imply the existence of a set \(S\) with a certain lower bound for the cardinality of the set of slopes of \(S\). As a corollary they obtain the Nechaev-Shoup lower bound for the complexity of a generic algorithm for the DLP [Proceedings Eurocrypt’97, Lect. Notes Comput. Sci. 1223, 256-266 (1997)].

After recalling the concepts of slope packing and slope covering (a subset \(S\) of the plane \(AG(2,p)\) is called slope packing if the slopes of lines obtained by joining all pairs of points in \(S\) are distinct and non-infinite; \(S\) is called slope covering if every non-infinite slope occurs), the paper shows the connections of these objects with weak Sidon sets and sum covers.

The paper also presents two tables with explicit examples of slope packings and slope coverings for the 25 primes \(p\) smaller than 100, tables found by computer searches.

Finally, in section 4, the authors discuss the announced relationship between slope packings and coverings and a generic algorithm for the DLP in a group of prime order \(p\). As it is well known given an element \(a\) in a cyclic group \(<g>\) of order \(n\), the discrete logarithm problem (DLP) asks for the unique integer \(x\), \(0\leq x \leq n-1\), such that \(a = g^x\). The DLP is used as a one-way function in many public-key encryption and signature schemes. An algorithm for the DLP is generic if it works for arbitrary groups in opposition to algorithms that exploit some specific property of the group, as is the case of the well-known index-calculus method.

The authors show that any slope covering \(S\in AG(2,p)\) of size \(w\) leads to a construction for a deterministic generic algorithm and also a Las Vegas type algorithm for the DLP in a group \(<g>\) of order \(p\), both algorithms with computational complexity \(O(w)\). Reciprocally the authors show that a generic algorithm for the DLP imply the existence of a set \(S\) with a certain lower bound for the cardinality of the set of slopes of \(S\). As a corollary they obtain the Nechaev-Shoup lower bound for the complexity of a generic algorithm for the DLP [Proceedings Eurocrypt’97, Lect. Notes Comput. Sci. 1223, 256-266 (1997)].

Reviewer: Juan Tena Ayuso (Valladolid)

##### MSC:

11Y16 | Number-theoretic algorithms; complexity |

05B40 | Combinatorial aspects of packing and covering |

##### Keywords:

slope packings; slope coverings; discrete logarithm problem; Sidon set; deterministic generic algorithm; Las Vegas type algorithm
PDF
BibTeX
XML
Cite

\textit{M. Chateauneuf} et al., J. Comb. Des. 11, No. 1, 36--50 (2003; Zbl 1020.11082)

Full Text:
DOI

##### References:

[1] | Blokhuis, Linear Algebra and its Applications pp 226– (1995) |

[2] | Brouwer, IEEE Trans Inform Theory 36 pp 1334– (1990) |

[3] | Haanpää, Discrete Appl Math |

[4] | and Combinatorial algorithms: Generation, enumeration and search, CRC Press, 1999. · Zbl 0911.05002 |

[5] | Nechaev, Math Notes 55 pp 165– (1994) |

[6] | Odlyzko, Designs, Codes and Cryptography 19 pp 129– (2000) |

[7] | Roth, IEEE Trans Inform Theory 42 pp 554– (1996) |

[8] | Schnorr, Inform Process Letters 79 pp 93– (2001) |

[9] | Shoup, Lecture Notes Comp Sci 1223 pp 256– (1997) |

[10] | Square-root algorithms for the discrete logarithm problem (a survey). Public key cryptography and computational number theory, Walter de Gruyter, 2001, pp. 283-301. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.