On the linear complexity of the Naor-Reingold sequence with elliptic curves
type: Item
instance of: scholarly article
title: On the linear complexity of the Naor-Reingold sequence with elliptic curves
zbMATH Open document ID: 1248.11053
author: Marcos Cruz
author: Daniel Sadornil
author: Domingo Gomez
published in: Finite Fields and their Applications
publication date: 2010-10-11T00:00:00Z
review text: The Naor-Reingold sequences with elliptic curves are used in cryptography due to their nice construction and good theoretical properties. Here the authors give a new bound on the linear complexity of these sequences thereby improving the previous one obtained by \textit{I. E. Shparlinski} and \textit{J. H. Silverman} [Des. Codes Cryptography 24, No. 3, 279--289 (2001; Zbl 1077.11504)] and holding in more cases. The following theorem is the main result: For \(0<\delta <1\) and \(n<\tfrac 43 \log l+6\), the linear complexity \(L_{\mathbf a}\) of the sequence \((u_k)_{k=0}^{2^n-1}\) satisfies \[ L_{\mathbf a}\geq 2^{n/2} l^{-2/3-\delta}/8 \] for all but at most \(O((l-1)^{n-\delta}\) vectors \(\mathbf a\in(\mathbb F_l^*)^n\). The implied constant is absolute.
reviewed by: Olaf Ninnemann
Mathematics Subject Classification ID: 11K45
Mathematics Subject Classification ID: 14G50
Mathematics Subject Classification ID: 11G20
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 5798563
zbMATH Keywords: Naor-Reingold pseudo-random function
zbMATH Keywords: linear complexity
zbMATH Keywords: elliptic curves
MaRDI profile type: Publication
full work available at URL: j.ffa.2010.05.005
OpenAlex ID: W2009308345
cites work: New directions in cryptography
cites work: Character sums with exponential functions
cites work: On the period of the Naor-Reingold sequence
cites work: Number-theoretic constructions of efficient pseudo-random functions
cites work: Progress in Cryptology - INDOCRYPT 2003
cites work: On the Naor-Reingold pseudo-random function from elliptic curves
cites work: Linear complexity of the Naor-Reingold pseudo-random function
cites work: On the linear complexity of the Naor-Reingold pseudo-random function from elliptic curves.
cites work: Q5297487
cites work: Q3062108
DOI: 10.1016/J.FFA.2010.05.005
Recommended article: On the linear complexity profile of some sequences derived from elliptic curves
Recommended article: On the linear complexity of the Naor-Reingold sequence
Recommended article: On the linear complexity of the Naor-Reingold pseudo-random function from elliptic curves.
Recommended article: Linear complexity of some sequences derived from hyperelliptic curves of genus 2
Recommended article: On the linear complexity of Sidel'nikov sequences over nonprime fields
Recommended article: Constructions of sequences with almost perfect linear complexity profile from curves over finite fields
Recommended article: Q4400352
Recommended article: On the linear complexity of bounded integer sequences over different moduli
Recommended article: On the linear complexity and multidimensional distribution of congruential generators over elliptic curves
Recommended article: ON THE LINEAR COMPLEXITY OF SOME GENERALIZED CYCLOTOMIC SEQUENCES
description: scientific article; zbMATH DE number 5798563