The Battery-Discharge-Model: A Class of Stochastic Finite Automata to Simulate Multidimensional Continued Fraction Expansion

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We define an infinite stochastic state machine, the Battery-Discharge-Model (BDM), which simulates the behaviour of linear and jump complexity of the continued fraction expansion of multidimensional formal power series, a relevant security measure in the cryptanalysis of stream ciphers. We also obtain finite approximations to the infinite BDM, where polynomially many states suffice to approximate with an exponentially small error the probabilities and averages for linear and jump complexity of M-multisequences of length n over the finite field F_q, for any M, n, q.
12 pages

Keywords

Information Theory, Computational Complexity, Cryptography and Security

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/133669

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0705.4134
 http://arxiv.org/abs/0705.4134

Collections

arXiv