Loading…
A genetic algorithm for computing the k-error linear complexity of cryptographic sequences
Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear complexity and also a large k-error linear comple...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Default Text |
| Published: |
2007
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/2134/3205 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1818175442531647488 |
|---|---|
| author | Alexandra Alecu Ana Salagean |
| author_facet | Alexandra Alecu Ana Salagean |
| author_sort | Alexandra Alecu (7169297) |
| collection | Figshare |
| description | Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear complexity and also a large k-error linear complexity. Efficient algorithms for computing the kerror linear complexity of a sequence over a finite field only exist for sequences of period equal to a power of the characteristic of the field. It is therefore useful to find a general and efficient algorithm to compute a good approximation of the k-error linear complexity. In this paper we investigate the design of a genetic algorithm to approximate the k-error linear complexity of a sequence. Our preliminary experiments show that the genetic algorithm approach is suitable to the problem and that a good scheme would use a medium sized population, an elitist type of selection, a special design of the two point random crossover and a standard random mutation. The algorithm outputs an approximative value of the k-error linear complexity which is on average only 19.5% higher than the exact value. This paper intends to be a proof of concept that the genetic algorithm technique is suitable for the problem in hand and future research will further refine the choice of parameters. |
| format | Default Text |
| id | rr-article-9403802 |
| institution | Loughborough University |
| publishDate | 2007 |
| record_format | Figshare |
| spelling | rr-article-94038022007-01-01T00:00:00Z A genetic algorithm for computing the k-error linear complexity of cryptographic sequences Alexandra Alecu (7169297) Ana Salagean (1257498) Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified Some cryptographical applications use pseudorandom sequences and require that the sequences are secure in the sense that they cannot be recovered by only knowing a small amount of consecutive terms. Such sequences should therefore have a large linear complexity and also a large k-error linear complexity. Efficient algorithms for computing the kerror linear complexity of a sequence over a finite field only exist for sequences of period equal to a power of the characteristic of the field. It is therefore useful to find a general and efficient algorithm to compute a good approximation of the k-error linear complexity. In this paper we investigate the design of a genetic algorithm to approximate the k-error linear complexity of a sequence. Our preliminary experiments show that the genetic algorithm approach is suitable to the problem and that a good scheme would use a medium sized population, an elitist type of selection, a special design of the two point random crossover and a standard random mutation. The algorithm outputs an approximative value of the k-error linear complexity which is on average only 19.5% higher than the exact value. This paper intends to be a proof of concept that the genetic algorithm technique is suitable for the problem in hand and future research will further refine the choice of parameters. 2007-01-01T00:00:00Z Text Online resource 2134/3205 https://figshare.com/articles/online_resource/A_genetic_algorithm_for_computing_the_k-error_linear_complexity_of_cryptographic_sequences/9403802 CC BY-NC-ND 4.0 |
| spellingShingle | Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified Alexandra Alecu Ana Salagean A genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| title | A genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| title_full | A genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| title_fullStr | A genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| title_full_unstemmed | A genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| title_short | A genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| title_sort | genetic algorithm for computing the k-error linear complexity of cryptographic sequences |
| topic | Other information and computing sciences not elsewhere classified untagged Information and Computing Sciences not elsewhere classified |
| url | https://hdl.handle.net/2134/3205 |