Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard
Feedback shift registers (FSRs) are used as a fundamental component in electronics and confidential communication. A FSR f is said to be reducible if all the output sequences of another FSR g can also be generated by f and the FSR g costs less memory than f. A FSR is said to be decomposable if it ha...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Hindawi-IET
2024-01-01
|
| Series: | IET Information Security |
| Online Access: | http://dx.doi.org/10.1049/2024/3219604 |
| _version_ | 1797262002843811840 |
|---|---|
| author | Lin Wang |
| author_facet | Lin Wang |
| author_sort | Lin Wang |
| collection | DOAJ |
| description | Feedback shift registers (FSRs) are used as a fundamental component in electronics and confidential communication. A FSR f is said to be reducible if all the output sequences of another FSR g can also be generated by f and the FSR g costs less memory than f. A FSR is said to be decomposable if it has the same set of output sequences as a cascade connection of two FSRs. Two polynomial-time computable transformations from Boolean circuits to FSRs are proposed such that the output FSR of the first (resp. second) transformation is irreducible (resp. indecomposable) if and only if the input Boolean circuit is satisfiable. Through the two transformations, it is proved that deciding irreducibility (indecomposability) of FSRs is NP-hard. Additionally, FSRs are constructed to show that there exist infinitely many irreducible (resp. indecomposable) FSRs which are decomposable (resp. reducible). |
| first_indexed | 2024-04-24T23:50:11Z |
| format | Article |
| id | doaj.art-cc15cb6aa13145c68f11dd9f4a3e4bdd |
| institution | Directory Open Access Journal |
| issn | 1751-8717 |
| language | English |
| last_indexed | 2024-04-24T23:50:11Z |
| publishDate | 2024-01-01 |
| publisher | Hindawi-IET |
| record_format | Article |
| series | IET Information Security |
| spelling | doaj.art-cc15cb6aa13145c68f11dd9f4a3e4bdd2024-03-15T00:00:03ZengHindawi-IETIET Information Security1751-87172024-01-01202410.1049/2024/3219604Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-HardLin Wang0Science and Technology on Communication Security LaboratoryFeedback shift registers (FSRs) are used as a fundamental component in electronics and confidential communication. A FSR f is said to be reducible if all the output sequences of another FSR g can also be generated by f and the FSR g costs less memory than f. A FSR is said to be decomposable if it has the same set of output sequences as a cascade connection of two FSRs. Two polynomial-time computable transformations from Boolean circuits to FSRs are proposed such that the output FSR of the first (resp. second) transformation is irreducible (resp. indecomposable) if and only if the input Boolean circuit is satisfiable. Through the two transformations, it is proved that deciding irreducibility (indecomposability) of FSRs is NP-hard. Additionally, FSRs are constructed to show that there exist infinitely many irreducible (resp. indecomposable) FSRs which are decomposable (resp. reducible).http://dx.doi.org/10.1049/2024/3219604 |
| spellingShingle | Lin Wang Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard IET Information Security |
| title | Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard |
| title_full | Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard |
| title_fullStr | Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard |
| title_full_unstemmed | Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard |
| title_short | Deciding Irreducibility/Indecomposability of Feedback Shift Registers Is NP-Hard |
| title_sort | deciding irreducibility indecomposability of feedback shift registers is np hard |
| url | http://dx.doi.org/10.1049/2024/3219604 |
| work_keys_str_mv | AT linwang decidingirreducibilityindecomposabilityoffeedbackshiftregistersisnphard |