Change search
Refine search result
12 1 - 50 of 97
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Chabloz, Jean-Michel
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Sharif Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    An Algorithm for Constructing a Fastest Galois NLFSR Generating a Given Sequence2010In: SEQUENCES AND THEIR APPLICATIONS-SETA 2010 / [ed] Carlet C; Pott A, 2010, Vol. 6338, p. 41-54Conference paper (Refereed)
    Abstract [en]

    The problem of efficient implementation of security mechanisms for advanced contactless technologies like RFID is gaining increasing attention. Severe constraints on resources such as area, power consumption, and production cost make the application of traditional cryptographic techniques to these technologies a challenging task. Non-Linear Feedback Shift Register (NLFSR)-based stream ciphers are promising candidates for cryptographic primitives for RFIDs because they have the smallest hardware footprint of all existing cryptographic systems. This paper presents a heuristic algorithm for constructing a fastest Galois NLFSR generating a given sequence. The algorithm takes an NLFSR in the Fibonacci configuration and transforms it to an equivalent Galois NLFSR which has the minimal delay. Our key idea is to find a best position for a given feedback connection without changing the positions of the other feedback connections. We use a technology dependent cost function which approximates the delay of an NLFSR after the technology mapping. The experimental results on 57 NLFSRs used in existing stream ciphers show that, on average, the presented algorithm allows us to decrease the delay by 25.5% as well as to reduce the area by 4.1%.

  • 2.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    A List of Maximum-Period NLFSRs2012Report (Other academic)
    Abstract [en]

    Non-Linear Feedback Shift Registers (NLFSRs) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a nonlinear function of the previous state. While the theory behind LFSRs is wellunderstood, many fundamental problems related to NLFSRs remain open. Probably the most important one is finding a systematic procedure for constructing NLFSRs with a guaranteed long period. Available algorithms either consider some special cases, or are applicable to small NLFSRs only. In this paper, we present a complete list of n-bit NLFSRs with the period 2n − 1, n < 25, for three different types of feedback functions with algebraic degree two. We hope that the presented experimental data might help analysing feedback functions of maximum-period NLFSRs and finding a supporting theory characterizing them.

  • 3.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A Method for Generating Full Cycles by a Composition of NLFSRs2014In: Designs, Codes and Cryptography, ISSN 0925-1022, E-ISSN 1573-7586, Vol. 73, no 2, p. 469-486Article in journal (Refereed)
    Abstract [en]

    Non-linear feedback shift registers (NLFSRs) are a generalization of linear feedback shift registers in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are typically hard to break with existing cryptanalytic methods. However, it is still not known how to construct large -stage NLFSRs which generate full cycles of possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an -stage register with period can be constructed from NLFSRs with -stages by adding to their feedback functions a logic block of size , for . This logic block implements Boolean functions representing pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size O(nk).

  • 4.
    Dubrova, Elena
    KTH, Superseded Departments, Electronic Systems Design.
    A polynomial time algorithm for non-disjoint decomposition of multiple-valued functions2004In: 34th International Symposium On Multiple-Valued Logic, Proceedings, 2004, p. 309-314Conference paper (Refereed)
    Abstract [en]

    This paper addresses the problem of non-disjoint decomposition of multiple-valued functions. First, we show that the problem of computing non-disjoint decompositions of a multiple-valued function is related to the problem of finding multiple-vertex dominators of a logic circuit, representing the function. Second, we present an O(n(k)) algorithm for computing all multiple-vertex dominators of a fixed size k, where n is the number of gates of the logic circuit. Our result is important because no polynomial-time algorithm for finding all possible non-disjoint decompositions of multiple-valued functions is known. The presented approach allows us computing a certain subset of non-disjoint decompositions (all reflected in a given circuit structure) in polynomial time. A set of experiments on benchmark circuits illustrates the efficiency of our approach.

  • 5.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A Scalable Method for Constructing Galois NLFSRs With Period 2(n)-1 Using Cross-Join Pairs2013In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 59, no 1, p. 703-709Article in journal (Refereed)
    Abstract [en]

    A method for constructing n-stage Galois NLFSRs with period 2(n) - 1 from n-stage maximum length LFSRs is presented. Nonlinearity is introduced into state cycles by adding a non-linear Boolean function to the feedback polynomial of the LFSR. Each assignment of variables for which this function evaluates to 1 acts as a crossing point for the LFSR state cycle. The effect of non-linearity is cancelled and state cycles are joined back by adding a copy of the same function to a later stage of the register. The presented method requires no extra time steps and it has a smaller area overhead compared to the previous approaches based on cross-join pairs. It is feasible for large n.

  • 6.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    A Transformation From the Fibonacci to the Galois NLFSRs2009In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 55, no 11, p. 5263-5271Article in journal (Refereed)
    Abstract [en]

    Conventional nonlinear feedback shift registers (NLFSRs) use the Fibonacci configuration in which the feedback is applied to the last bit only. In this paper, we show how to transform a Fibonacci NLFSR into an equivalent NLFSR in the Galois configuration, in which the feedback can be applied to every bit. Such a transformation can potentially reduce the depth of the circuits implementing feedback functions, thus decreasing the propagation time and increasing the throughput.

  • 7.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    An equivalence-preserving transformation of shift registers2014In: Sequences and Their Applications - SETA 2014: 8th International Conference, Melbourne, VIC, Australia, November 24-28, 2014, Proceedings, Springer, 2014, p. 187-199Conference paper (Refereed)
    Abstract [en]

    The Fibonacci-to-Galois transformation is useful for reducing the propagation delay of feedback shift register-based stream ciphers and hash functions. In this paper, we extend it to handle Galois-to-Galois case as well as feedforward connections. This makes possible transforming Trivium stream cipher and increasing its keystream data rate by 27% without any penalty in area. The presented transformation might open new possibilities for cryptanalysis of Trivium, since it induces a class of stream ciphers which generate the same set of keystreams as Trivium, but have a different structure.

  • 8.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Bio-Inspired Fault-Tolerance2008In: Proceedings of IEEE/ACM International Conference on Bio-Inspired Models of Network, Information, and Computing Systems (BIONETICS'2008), ICST , 2008Conference paper (Refereed)
    Abstract [en]

    In the last decade, there has been a considerable increase of interest in fault-tolerant computing due to dependability problems related to process scaling, embedded software, and ubiquitous computing. In this paper, we consider an approach to fault-tolerance which is inspired by gene regulatory networks of living cells. Living cells are capable of maintaining their functionality under a variety of genetic changes and external perturbations. They have natural self-healing, self-maintaining, self-replicating and self-assembling mechanisms. The fault-tolerance of living cells is due to the intrinsic robustness of attractors' landscapes of their gene regulatory networks. Previously, we introduced a technique which exploits the stability of attractors to achieve a fault-tolerant computation. In this paper, we evaluate this technique on the example of a gene regulatory network model of Arabidopsis thaliana and show that it can tolerate 70% single-point mutations in the outputs of the defining tables of gene functions.

  • 9.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Fault-tolerant design2013Book (Other academic)
    Abstract [en]

    This textbook serves as an introduction to fault-tolerance, intended for upper-division undergraduate students, graduate-level students and practicing engineers in need of an overview of the field. Readers will develop skills in modeling and evaluating fault-tolerant architectures in terms of reliability, availability and safety. They will gain a thorough understanding of fault tolerant computers, including both the theory of how to design and evaluate them and the practical knowledge of achieving fault-tolerance in electronic, communication and software systems. Coverage includes fault-tolerance techniques through hardware, software, information and time redundancy. The content is designed to be highly accessible, including numerous examples and exercises. Solutions and powerpoint slides are available for instructors.

  • 10.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Finding Matching Initial States for Equivalent NLFSRs in the Fibonacci and the Galois Configurations2010In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 56, no 6, p. 2961-2966Article in journal (Refereed)
    Abstract [en]

    The Fibonacci and the Galois configurations of nonlinear feedback shift registers (NLFSRs) are considered. In the former, the feedback is applied to the input bit of the shift register only. In the latter, the feedback can potentially be applied to every bit. The sufficient conditions for equivalence of NLFSRs in the Fibonacci and the Galois configurations have been formulated previously. The equivalent NLFSRs in different configurations normally have to be initialized to different states to generate the same output sequences. The mapping between the initial states of two equivalent NLFSRs in the Fibonacci and the Galois configurations is derived in this paper.

  • 11.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    How to Speed-Up Your NLFSR-Based Stream Cipher2009In: DATE: 2009 DESIGN, AUTOMATION & TEST IN EUROPE CONFERENCE & EXHIBITION, 2009, p. 878-881Conference paper (Refereed)
    Abstract [en]

    Non-Linear Feedback Shift Registers (NLFSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for generating pseudo-random sequences for stream ciphers. Conventional NLFSRs use the Fibonacci configuration in which the feedback is applied to the last bit only. In this paper, we show how to transform a Fibonacci NLFSR into an equivalent NLFSR in the Galois configuration, in which the feedback can be applied to every bit. Such a transformation can potentially reduce the depth of the circuits implementing feedback functions, thus decreasing the propagation time and increasing the throughput.

  • 12.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Learning Fault-Tolerance from Nature2008In: BEC 2008: 2008 INTERNATIONAL BIENNIAL BALTIC ELECTRONICS CONFERENCE, PROCEEDINGS, 2008, p. 51-58Conference paper (Refereed)
    Abstract [en]

    In the last decade, there has been a considerable increase of interest in fault-tolerant computing due to dependability problems related to process scaling, embedded software, and ubiquitous computing. In this paper, we discuss an approach to fault-tolerance which is inspired by biological systems. Biological systems are capable of maintaining their functionality tinder a variety of genetic changes and external perturbations. They have natural self-healing, self-maintaining, self-replicating and self-assembling mechanisms. We present experimental and numerical evidence that the intrinsic fault-tolerance of biological systems is due to the dynamical phase in which the gene regulatory network operates. The dynamical phase is, in turn, determined by the subtle way in which redundancy is allocated in the network. By understanding the principles of redundancy allocation at the genetic level, we may find ways to build chips that possess the inherent fault-tolerance of biological systems.

  • 13.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Linear-time algorithm for computing minimum checkpoint sets for simulation-based verification of HDL programs2005In: 2005 IEEE International Symposium On Circuits And Systems (ISCAS), Conference Proceedings, IEEE , 2005, p. 2212-2215Conference paper (Refereed)
    Abstract [en]

    Simulation-based verification is a popular method for functional validation of hardware. It is performed by applying a set of tests to the system under consideration and to its reference model, and comparing the results. The effectiveness of a test suite is measured by the fraction of the system covered by the tests. In this paper, we present a technique for selecting a part of the system, called checkpoints, with the property that any set of tests which covers the checkpoints covers the entire system. Thus, by constructing a test suit for the checkpoints, a 100% coverage can be achieved. We present a linear-time algorithm for computing a minimum checkpoint set based on pre- and post-dominator relations of the control flow graph of the HDL program representing the system.

  • 14.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Modeling gene regulatory systems by random Boolean networks2005In: Bioengineered and Bioinspired Systems II / [ed] Carmona, RA; LinanCembrano, G, SPIE - International Society for Optical Engineering, 2005, Vol. 5839, p. 56-65Conference paper (Refereed)
    Abstract [en]

    A random Boolean network is a synchronous Boolean automaton with n vertices. The parameters of an RBN can be tuned so that its statistical features match the characteristics of the gene regulatory system. The number of vertices of the RBN represents the number of genes in tile cell. The number of cycles in the RBN's state space, called attractors, corresponds the number of different cell types. Attractor's length corresponds to the cell cycle time. Sensitivity of the attractors to different kind of perturbations, modeled by changing the state of a particular vertex, associated Boolean function, or network edge, reflects the stability of the cell to damage, mutations and virus attacks. In order to evaluate the attractors, their number and length have to be re-computed repeatedly. For large RBN's, searching for attractors in the O(2(n)) state space is an infeasible task. Fortunately, only a subset of vertices of an RBN, called relevant vertices, determines its dynamics. The remaining vertices are redundant. In this paper, we present an algorithm for identifying redundant vertices in RBNs which allows us to reduce the search space for computing at.tractors from O(2(n)) to Theta(2 root n). We also show how RBNs can be used for studying evolution.

  • 15.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Multiple-Valued Logic in VLSI: Challenges and Opportunities1999In: Proceedings of NORCHIP'99, IEEE conference proceedings, 1999Conference paper (Refereed)
  • 16.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Multiple-Valued Logic Synthesis and Optimization2002In: Logic Synthesis and Verification / [ed] S. Hassoun and T. Sasao, Springer, 2002, 1st, p. 89-114Chapter in book (Refereed)
  • 17.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    On Constructing Secure and Hardware-Efficient Invertible Mappings2016In: Proceedings of IEEE International Symposium on Multiple-Valued Logic, IEEE Computer Society, 2016Conference paper (Refereed)
    Abstract [en]

    Our society becomes increasingly dependent on wireless communications. The tremendous growth in the number and type of wirelessly connected devices in a combination with the dropping cost for performing cyberattacks create new challenges for assuring security of services and applications provided by the next generation of wireless communication networks. The situation is complicated even further by the fact that many end-point Internet of Things (IoT) devices have very limited resources for implementing security functionality. This paper addresses one of the aspects of this important, many-faceted problem - the design of hardware-efficient cryptographic primitives suitable for the protection of resource-constrained IoT devices. We focus on cryptographic primitives based on the invertible mappings of type {0,1,…,2n−1}→{0,1,…,2n−1}. In order to check if a given mapping is invertible or not, we generally need an exponential in n number of steps. In this paper, we derive a sufficient condition for invertibility which can be checked in O(n2N) time, where N is the size of representation of the largest function in the mapping. Our results can be used for constructing cryptographically secure invertible mappings which can be efficiently implemented in hardware.

  • 18.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Phylogenetic networks with edge-disjoint recombination cycles2005In: Bioengineered and Bioinspired Systems II / [ed] Carmona, RA; LinanCembrano, G, SPIE - International Society for Optical Engineering, 2005, Vol. 5839, p. 381-388Conference paper (Refereed)
    Abstract [en]

    Phylogenetic analysis is a branch of biology that establishes the evolutionary relationships between living organisms. The goal of phylogenetic analysis is to determine the order and approximate timing of speciation events in the evolution of a given set of species. Phylogenetic networks allow to represent evolutionary histories that include events like recombination and hybridization. In this paper, we introduce a class of phylogenetic networks called extended galled-trees in which recombination cycles share no edge. We show that the site consistency problem, which is NP-hard in general, can be solved in polynomial time for this class of phylogenetic networks.

  • 19.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Random Multiple-Valued Networks: Theory and Applications2006In: Proceedings of The International Symposium on Multiple-Valued Logic, New York: IEEE , 2006, p. 159-164Conference paper (Refereed)
    Abstract [en]

    A living cell is essentially a molecular digital computer that configures itself as part of the execution of its code. By understanding how cells direct the assembly, of their Molecules, we can find ways to build computer Chips that can self-organize, evolve and adapt to a changing environment, In this paper we consider a model of the gene regulatory, network of living cells called random multiple-valued network (RMN). An RMN can be tuned so that its statistical features match the characteristics of living cells. We present a set of algorithms for redundancy removal, partitioning and computation of attractors in RMNs. We also discuss how RMNs can be used for implementing logic functions.

  • 20.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Self-Organization for Fault-Tolerance2008In: SELF-ORGANIZING SYSTEMS, PROCEEDINGS / [ed] Hummel KA; Sterbenz JPG, 2008, Vol. 5343, p. 145-156Conference paper (Refereed)
    Abstract [en]

    In the last decade, there has been a considerable increase of interest in fault-tolerant computing due to dependability problems related to process scaling, embedded systems, and ubiquitous Computing, In this paper, we present an approach to fault-tolerance inspired by gene regulatory networks of living cells. Living cells are capable of maintaining their functionality under a variety of genetic changes and external perturbations. They have natural self-healing, self-maintaining, self-replicating, and self-assembling mechanisms. The fault-tolerance of living cells is due to the ability of their gene regulatory network to self-organize and produce a stable attractors' landscape. We introduce a computational scheme which exploits the intrinsic stability of attractors to achieve fault.-tolerant computation. We also test fault-tolerance of the presented scheme on the example of a gene regulatory network model of Arabidopsis thaliana and show that it can tolerate 68% single-point mutations in the outputs of the defining tables of gene functions.

  • 21.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Structural testing based on minimum kernels2005In: Proceedings -Design, Automation and Test in Europe, DATE '05 / [ed] Wehn, N; Benini, L, IEEE Computer Society, 2005, p. 1168-1173Conference paper (Refereed)
    Abstract [en]

    Structural testing techniques, such as statement and branch coverage, play an important role in improving dependability of software systems. However, finding a set of tests which guarantees high coverage is a time-consuming task. In this paper we present a technique for structural testing based on kernel computation. A kernel satisfies the property that any set of tests which executes all vertices (edges) of the kernel executes all vertices (edges) of the program's flowgraph. We present a linear-time algorithm for computing minimum kernels based on pre- and post-dominator relations of a flowgraph.

  • 22.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Synthesis of Binary Machines2011In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 57, no 10, p. 6890-6893Article in journal (Refereed)
    Abstract [en]

    The problem of constructing a binary machine with the minimum number of stages generating a given binary sequence is addressed. Binary machines are a generalization of nonlinear feedback shift registers (NLFSRs) in which both connections, feedback and feedforward, are allowed and no chain connection between the register stages is required. An algorithm for constructing a shortest binary machine generating a given periodic binary sequence is presented.

  • 23.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Synthesis of NLFSR-based pseudo-random sequence generators for stream ciphers2008In: Proceedings of International Symposium on Applied Computing (IADIS’2008), 2008Conference paper (Refereed)
  • 24.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Synthesis of parallel binary machines2011In: Computer-Aided Design (ICCAD), 2011 IEEE/ACM International Conference on, 2011, p. 200-206Conference paper (Refereed)
    Abstract [en]

    Binary machines are a generalization of Feedback Shift Registers (FSRs) in which both, feedback and feedforward, connections are allowed and no chain connection between the register stages is required. In this paper, we present an algorithm for synthesis of binary machines with the minimum number of stages for a given degree of parallelization. Our experimental results show that for sequences with high linear complexity such as complementary, Legendre, or truly random, parallel binary machines are an order of magnitude smaller than parallel FSRs generating the same sequence. The presented approach can potentially be of advantage for many applications including wireless communication, cryptography, and testing.

  • 25.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments, Electronic Systems Design.
    Ellervee, P.
    Miller, D. M.
    Muzio, J. C.
    Sullivan, A. J.
    TOP: an algorithm for three-level combinational logic optimisation2004In: IEE Proceedings - Circuits Devices and Systems, ISSN 1350-2409, E-ISSN 1359-7000, Vol. 151, no 4, p. 307-314Article in journal (Refereed)
    Abstract [en]

    Three-level logic is shown to have a potential for reducing the area over two-level implementations, as well as for a gain in speed over multilevel implementations. A heuristic algorithm TOP is presented, targeting a three-level logic expression of type g(1degrees)g(2), where g(1) and g(2) are sum-of-products expressions and '(degrees)' is a binary operation. For the first time, to the authors' knowledge, this problem is addressed for an arbitrary operation '(degrees)', although several algorithms for specified cases of '(degrees)' have been presented in the past. The experimental results show that, on average, the total number of product-terms in the expression obtained by TOP is about one third of the number of product-terms in the expression obtained by a two-level AND-OR minimiser.

  • 26.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Hell, Martin
    Lund University, Sweden.
    Espresso: A stream cipher for 5G wireless communication systems2017In: Cryptography and Communications, ISSN 1936-2447, E-ISSN 1936-2455, Vol. 9, no 2, p. 273-289Article in journal (Refereed)
    Abstract [en]

    The demand for more efficient ciphers is a likely to sharpen with new generation of products and applications. Previous cipher designs typically focused on optimizing only one of the two parameters - hardware size or speed, for a given security level. In this paper, we present a methodology for designing a class of stream ciphers which takes into account both parameters simultaneously. We combine the advantage of the Galois configuration of NLFSRs, short propagation delay, with the advantage of the Fibonacci configuration of NLFSRs, which can be analyzed formally. According to our analysis, the presented stream cipher Espresso is the fastest among the ciphers below 1500 GE, including Grain-128 and Trivium.

  • 27.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Liu, Ming
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking2012In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 19, no 1-3, p. 109-131Article in journal (Refereed)
    Abstract [en]

    Synchronous multiple-valued networks are a discrete-space discrete-time model of the gene regulatory network of living cells. In this model, cell types are represented by the cycles in the state transition graph of a network, called attractors. When the effect of a disease or a mutation on a cell is studied, attractors have to be re-computed each time a fault is injected in the model. This motivates research on algorithms for finding attractors. Existing decision diagram-based approaches have limited capacity due to the excessive memory requirements of decision diagrams. Simulation-based approaches can be applied to larger networks, however, they are incomplete. We present an algorithm for finding attractors which uses a SAT-based bounded model checking. Our model checking approach exploits the deterministic nature of the network model to reduce runtime. Although the idea of applying model checking to the analysis of gene regulatory networks is not new, to our best knowledge, we are the first to use it for computing all attractors in a model. The efficiency of the presented algorithm is evaluated by analyzing 7 networks models of real biological processes as well as 35.000 randomly generated 4-valued networks. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

  • 28.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A BDD-Based Method for LFSR Parellelization with Application to Fast CRC Encoding2013In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 21, no 5, p. 561-575Article in journal (Refereed)
    Abstract [en]

    Galois Fields of order $2^k$, $GF(2^k)$, provide a unified theoretical framework for constructing parallel devices generating $k$ output bits per clock cycle. In this paper, we use $GF(2^k)$ for constructing Linear Feedback Shift Registers (LFSRs) for the parallel encoding of Cyclic Redundancy Check (CRC) codes.CRC codes are widely used in data communication and storage for detecting burst errors. Traditional methods for the parallel encoding of CRC are based on computing the $k$th power of the connection matrix of the LFSR. We propose an alternative method based on computing the $k$th power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation in a partitioned form. This allows us to bound the size of BDDs by $O(n^2)$, where $n$ is the size of the LFSR. The presented algorithm is asymptotically faster than previous algorithms for LFSR parallelization.

  • 29.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Muzio, J. C.
    Easily testable multiple-valued logic circuits derived from Reed-Muller circuits2000In: I.E.E.E. transactions on computers (Print), ISSN 0018-9340, E-ISSN 1557-9956, Vol. 49, no 11, p. 1285-1289Article in journal (Refereed)
    Abstract [en]

    In 1972, Reddy showed that the binary circuits realizing Reed-Muller canonical form are easily testable. In this paper, we extend Reddy's result to multiple-valued logic circuits. employing more than two discrete levels of signal, The electronic fabrication of such circuits became feasible due to the recent advances in integrated circuit technology. We show that, in the multiple-valued case, several new phenomena occur which allow us to asymptotically reduce the upper bound on the number of tests required for fault detection, but make the generation of tests harder.

  • 30.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson AB.
    Carlsson, Gunnar
    Ericsson AB.
    Fornehed, John
    Ericsson AB.
    Smeets, Ben
    Ericsson AB.
    Two Countermeasures Against Hardware Trojans Exploiting Non-Zero Aliasing Probability of BIST2016In: Journal of Signal Processing Systems, ISSN 1939-8018, E-ISSN 1939-8115Article in journal (Refereed)
    Abstract [en]

    The threat of hardware Trojans has been widely recognized by academia, industry, and government agencies. A Trojan can compromise security of a system in spite of cryptographic protection. The damage caused by a Trojan may not be limited to a business or reputation, but could have a severe impact on public safety, national economy, or national security. An extremely stealthy way of implementing hardware Trojans has been presented by Becker et al. at CHES’2012. Their work have shown that it is possible to inject a Trojan in a random number generator compliant with FIPS 140-2 and NIST SP800-90 standards by exploiting non-zero aliasing probability of Logic Built-In-Self-Test (LBIST). In this paper, we present two methods for modifying LBIST to prevent such an attack. The first method makes test patterns dependent on a configurable key which is programed into a chip after the manufacturing stage. The second method uses a remote test management system which can execute LBIST using a different set of test patterns at each test cycle.

  • 31.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson, Sweden.
    Carlsson, Gunnar
    Ericsson, Sweden.
    Smeets, Ben
    Ericsson, Sweden.
    Keyed Logic BIST for Trojan Detection in SoC2014In: Proceedings of IEEE International Symposium on System-on-Chip (SOC'2014), IEEE conference proceedings, 2014Conference paper (Refereed)
    Abstract [en]

    As demonstrated by the recent attack on Intel’s Ivy Bridge processor, the traditional Logic Built-In Self-Test (LBIST) methods do not provide adequate protection of SoC against malicious modifications known as hardware Trojans. In this paper, we introduce a simple but efficient countermeasure against hardware Trojans which exploits non-zero aliasing probability of LBIST. We propose to generate LBIST test patterns based on a configurable key which is decided and programed into the circuit after the manufacturing stage. Since the key and hence expected LBIST signature are unknown at the manufacturing stage, an attack based on selecting suitable values for the Trojan which result in the same signature as a fault-free circuit signature becomes infeasible.

  • 32.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson AB.
    Selander, Göran
    Ericsson AB.
    CRC-Based Message Authentication for 5G Mobile Technology2015In: Proceedings of 2015 IEEE Trustcom/BigDataSE/ISPA, IEEE , 2015, Vol. 1, p. 1186-1191Conference paper (Refereed)
    Abstract [en]

    Our society greatly depends on mobile technologies. As wirelessly connected devices take over the control of the electricity in our homes, the water we drink and the transportation we use, it becomes increasingly important to guarantee the security of interactions of all players involved in a network. Apart from the high security needs, 5G will require utmost efficiency in the use of bandwidth and energy. In this paper, we show how to make the type of CRC checksum used in current LTE standards cryptographically secure with minimum extra resources. We present a new CRC-based message authentication method and provide a quantitative analysis of the achieved security as a function of message and CRC sizes. The presented method retains most of the implementation simplicity of the traditional CRC except that the LFSR implementing the encoding and decoding is required to have re-programmable connections. Similarly to previously proposed cryptographically secure CRCs, the presented CRC enables combining the detection of random and malicious errors without increasing bandwidth. Its main advantage is the ability to detect all double-bit errors in a message, which is of special importance for systems using Turbo codes, including LTE.

  • 33.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    Ericsson Research, Sweden .
    Selander, Göran
    Ericsson Research, Sweden .
    Secure and Efficient LBIST for Feedback Shift Register-Based Cryptographic Systems2014In: Proceedings of 19th IEEE European Test Symposium (ETS'2014), IEEE conference proceedings, 2014Conference paper (Refereed)
    Abstract [en]

    Cryptographic methods are used to protect confidential information against unauthorised modification or disclo-sure. Cryptographic algorithms providing high assurance exist, e.g. AES. However, many open problems related to assuring security of a hardware implementation of a cryptographic algorithm remain. Security of a hardware implementation can be compromised by a random fault or a deliberate attack. The traditional testing methods are good at detecting random faults, but they do not provide adequate protection against malicious alterations of a circuit known as hardware Trojans. For example, a recent attack on Intel's Ivy Bridge processor demonstrated that the traditional Logic Built-In Self-Test (LBIST) may fail even the simple case of stuck-at fault type of Trojans. In this paper, we present a novel LBIST method for Feedback Shift Register (FSR)-based cryptographic systems which can detect such Trojans. The specific properties of FSR-based cryptographic systems allow us to reach 100% single stuck-at fault coverage with a small set of deterministic tests. The test execution time of the proposed method is at least two orders of magnitude shorter than the one of the pseudo-random pattern-based LBIST. Our results enable an efficient protection of FSR-based cryptographic systems from random and malicious stuck-at faults.

  • 34.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Näslund, Mats
    KTH, School of Information and Communication Technology (ICT), Electronics and Embedded Systems.
    Selander, Göran
    Tsiatsis, Vlasios
    Energy-Efficient Message Authentication for IEEE 802.15.4-Based Wireless Sensor Networks2014In: Proceedings of 32nd Nordic Microelectronics Conference NORCHIP , IEEE conference proceedings, 2014Conference paper (Refereed)
    Abstract [en]

    The number of wirelessly connected devices is expected to increase to a few tens of billions by the year 2020. Newer generations of products and applications will sharpen demands for ultra-low energy consuming wireless devices. Various techniques for energy saving based on Discontinuous Reception (DRX) are known. However, DRX is vulnerable to unauthorized or fake trigger requests by malicious adversaries aiming to drain a device's battery. Existing message authentication methods can identify spoofed messages, but they require the reception of a complete message before its authenticity can be verified. In this paper, we present a method which inserts authentication checkpoints at several positions within a message. This enables a device to identify that a message is unauthorized and turn its radio receiver off as soon as the first checkpoint fails. The presented method has a low complexity with respect to the computational and memory resources and does not slow down the receiver. It can maintain the packet format prescribed by the IEEE 802.15.4 specification, which provides for backward compatibility. Finally, it incorporates authentication checkpoints at the MAC layer, which allows nodes that do not employ the presented method to participate in the communication.

  • 35.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments, Electronic Systems Design.
    Sack, H.
    Probabilistic equivalence checking of multiple-valued functions2004In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 10, no 4, p. 395-414Article in journal (Refereed)
    Abstract [en]

    This paper describes a probabilistic method for verifying the equivalence of two multiple-valued functions. Each function is hashed to an integer code by transforming it to a integer-valued polynomial and evaluating it for values of variables taken independently and uniformly at random from a finite field. Since the polynomial is unique for a given function, if two hash codes are different, then the functions are not equivalent. However, if two hash codes are the same, the functions may or may not be equivalent, because different polynomials may happen to hash to the same code. Thus, the method presented in this paper determines the equivalence of two functions with a known (small) probability of error, arising from collisions between inequivalent functions. Such a method seems to be an attractive alternative for verifying functions that are too large to be handled by deterministic equivalence checking methods.

  • 36.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Sarif Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A BDD-based approach to constructing LFSRs for parallel CRC encoding2012In: Proceedings, IEEE 42nd International Symposium on Multiple-Valued Logic. ISMVL 2012, IEEE Computer Society, 2012, p. 128-133Conference paper (Refereed)
    Abstract [en]

    Cyclic Redundancy Check codes (CRC) are widely used in data communication and storage devices for detecting burst errors. In applications requiring high-speed data transmission, multiple bits of an CRC are computed in parallel. Traditional methods for constructing an Linear Feedback Shift Register (LFSR) generating k bits of an CRC in parallel are based on computing kth power of the connection matrix of the LFSR. We propose an alternative method which is based on computing kth power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation and we keep the transition relation partitioned. This allows us to bound the size of BDDs by O(n(2)), where n is the size of the LFSR. Our experimental results show that the presented algorithm asymptotically improves the complexity of previous approaches.

  • 37.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Sharif Mansouri, Shohreh
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    A BDD-Based Method for LFSR Parallelization with Application to Fast CRC Encoding2013In: Journal of Multiple-Valued Logic and Soft Computing, ISSN 1542-3980, E-ISSN 1542-3999, Vol. 21, no 5-6, p. 561-574Article in journal (Refereed)
    Abstract [en]

    Galois Fields of order 2(k), GF(2(k)), provide a unified theoretical framework for constructing parallel devices generating k output bits per clock cycle. In this paper, we use GF(2(k)) for constructing Linear Feedback Shift Registers (LFSRs) for the parallel encoding of Cyclic Redundancy Check (CRC) codes. CRC codes are widely used in data communication and storage for detecting burst errors. Traditional methods for the parallel encoding of CRC are based on computing the kth power of the connection matrix of the LFSR. We propose an alternative method based on computing the kth power of the transition relation of the LFSR. We use Binary Decision Diagrams (BDDs) for representing the transition relation in a partitioned form. This allows us to bound the size of BDDs by O(n(2)), where it is the size of the LFSR. The presented algorithm is asymptotically faster than previous algorithms for LFSR parallelization.

  • 38.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Tenhunen, Hannu
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    A Computational Scheme Based on Random Boolean Networks on the Critical Line2006In: International Symposium on Applied Computing (IADIS’2006), 2006, p. 273-281Conference paper (Refereed)
  • 39.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    A SAT-Based Algorithm for Finding Attractors in Synchronous Boolean Networks2011In: IEEE/ACM Transactions on Computational Biology & Bioinformatics, ISSN 1545-5963, E-ISSN 1557-9964, Vol. 8, no 5, p. 1393-1399Article in journal (Refereed)
    Abstract [en]

    This paper addresses the problem of finding attractors in synchronous Boolean networks. The existing Boolean decision diagram-based algorithms have limited capacity due to the excessive memory requirements of decision diagrams. The simulation-based algorithms can be applied to larger networks, however, they are incomplete. We present an algorithm, which uses a SAT-based bounded model checking to find all attractors in a Boolean network. The efficiency of the presented algorithm is evaluated by analyzing seven networks models of real biological processes, as well as 150,000 randomly generated Boolean networks of sizes between 100 and 7,000. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

  • 40.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Compositional properties of random Boolean networks2005In: Physical Review E. Statistical, Nonlinear, and Soft Matter Physics, ISSN 1539-3755, E-ISSN 1550-2376, Vol. 71, no 5, p. 056116-Article in journal (Refereed)
    Abstract [en]

    Random Boolean networks (RBNs) are used in a number of applications, including cell differentiation, immune response, evolution, gene regulatory networks, and neural networks. This paper addresses the problem of computing attractors in RBNs. An RBN with n vertices has up to 2(n) states. Therefore, for large n, computing attractors by full enumeration of states is not feasible. The state space can be reduced by removing irrelevant vertices, which have no influence on the network's dynamics. In this paper, we show that attractors of an RBN can be computed compositionally from the attractors of the independent components of the subgraph induced by the relevant vertices of the network. The presented approach reduces the complexity of the problem from O(2(n)) to O(2(l)), where l is the number of relevant vertices in the largest component.

  • 41.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Martinelli, Andrés
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Kauffman networks: Analysis and applications2005In: ICCAD-2005: INTERNATIONAL CONFERENCE ON COMPUTER AIDED DESIGN, DIGEST OF TECHNICAL PAPERS, 2005, p. 479-484Conference paper (Refereed)
    Abstract [en]

    A Kauffman network is an abstract model of gene regulatory networks. Each gene is represented by a vertex. An edge from one vertex to another implies that the former gene regulates the latter. Statistical features of Kauffman networks match the characteristics of living cells. The number of cycles in the network's state space, called attractors, corresponds to the number of different cell types. The attractor's length corresponds to the cell cycle time. The sensitivity of attractors; to different kinds of disturbances, modeled by changing a network connection, the state of a vertex, or the associated function, reflects the stability of the cell to damage, mutations and virus attacks. In order to evaluate attractors, their number and lengths have to be computed. This problem is the major open problem related to Kauffman networks. Available algorithms can only handle networks with less than a hundred vertices. The number of genes in a cell is often larger. In this paper, we present a set of efficient algorithms for computing attractors in large Kauffman networks. The resulting software package is hoped to be of assistance in understanding the principles of gene interactions and discovering a computing scheme operating on these principles.

  • 42.
    Dubrova, Elena
    et al.
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Teslenko, Maxim
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    Martinelli, Andrés
    KTH, Superseded Departments, Microelectronics and Information Technology, IMIT.
    On relation between non-disjoint decomposition and multiple-vertex dominators2004In: 2004 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOL 4, PROCEEDINGS, IEEE , 2004, p. 493-496Conference paper (Refereed)
    Abstract [en]

    This paper addresses the problem of non-disjoint decomposition of Boolean functions. Decomposition has multiple applications in logic synthesis, testing and formal verification. First, we show that the problem of computing non-disjoint decompositions of Boolean functions can be reduced to the problem of finding multiple-vertex dominators of circuit graphs. Then, we prove that there exists an algorithm for computing all multiple-vertex dominators of a fixed size in polynomial time. Our result is important because no polynomial-time algorithm for non-disjoint decomposition of Boolean functions is known. A set of experiments on benchmark circuits illustrates our approach.

  • 43.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Teslenko, Maxim
    Ming, Liu
    Finding Attractors in Synchronous Multiple-Valued Networks Using SAT-based Bounded Model Checking2010In: 40TH IEEE INTERNATIONAL SYMPOSIUM ON MULTIPLE-VALUED LOGIC ISMVL 2010, Los Alamitos: IEEE COMPUTER SOC , 2010, p. 144-149Conference paper (Refereed)
    Abstract [en]

    Synchronous multiple-valued networks are a discrete-space discrete-time model of the gene regulatory network of living cells. In this model, cell types are represented by the cycles in the state transition graph of a network, called attractors. When the effect of a disease or a mutation on a cell is studied, attractors have to be re-computed each time a fault is injected in the model. This motivates research on algorithms for finding attractors. Existing decision diagram-based approaches have limited capacity due to the excessive memory requirements of decision diagrams. Simulation-based approaches can be applied to larger networks, however, they are incomplete. We present an algorithm for finding attractors which uses a SAT-based bounded model checking. Our model checking approach exploits the deterministic nature of the network model to reduce runtime. Although the idea of applying model checking to the analysis of gene regulatory networks is not new, to our best knowledge, we are the first to use it for computing all attractors in a model. The efficiency of the presented algorithm is evaluated by analyzing 7 networks models of real biological processes as well as 35.000 randomly generated 4-valued networks. The results show that our approach has a potential to handle an order of magnitude larger models than currently possible.

  • 44.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Tenhunen, Hannu
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    A Computational Model Based on Random Boolean Networks2007In: 2007 2ND BIO-INSPIRED MODELS OF NETWORKS, INFORMATION AND COMPUTING SYSTEMS (BIONETICS), NEW YORK: IEEE , 2007, p. 24-31Conference paper (Refereed)
    Abstract [en]

    For decades, the size of silicon CMOS transistors has decreased steadily while their performance has improved. As the devices approach their physical limits, the need for alternative materials, structures and computation schemes becomes evident. This paper considers a computation scheme based on an abstract model of gene regulatory networks called Random Boolean Networks. Our interest in Random Boolean Networks is due to their attractive fault-tolerant features. The parameters of a network can be tuned so that it exhibits a robust behavior in which minimal changes in network's connections, values of state variables, or associated functions, typically cause no variation in the network's dynamics. A computation scheme based on random networks also seems to be appealing for emerging technologies in which it is difficult to control the growth direction or precise alignment, e.g. carbon nanotubes.

  • 45.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Tenhunen, Hannu
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    A Computational Scheme Based on Random Boolean Networks2008In: TRANSACTIONS ON COMPUTATIONAL SYSTEMS BIOLOGY X / [ed] Priami C; Akan OB; Dressler F; Ngom A, 2008, Vol. 5410, p. 41-58Conference paper (Refereed)
    Abstract [en]

    For decades, the size of silicon CMOS transistors has decreased steadily while their performance has improved. As the devices approach their physical limits, the need for alternative materials, structures and computational schemes becomes evident. This paper considers a computational scheme based oil ail abstract model of the gene regulatory network called Random Boolean Network (RBN). On one hand, our interest in RBNs is due to their attractive fault-tolerant features. The parameters of an RBN can be tuned so that it exhibits a robust behavior in which minimal changes in network's connections, values of state variables, or associated functions, typically cause no variation in the network's dynamics. On the other hand, a computational scheme based on RBNs seems appealing for emerging technologies in which it is difficult to control the growth direction or precise alignment, e.g, carbon nanotubes.

  • 46.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Tenhunen, Hannu
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Computing attractors in complex dynamic networks2005Conference paper (Refereed)
  • 47.
    Dubrova, Elena
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Teslenko, Maxim
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    Tenhunen, Hannu
    KTH, School of Information and Communication Technology (ICT), Electronic, Computer and Software Systems, ECS.
    On analysis and synthesis of (n, k)-Non-Linear Feedback Shift Registers2008In: 2008 Design, Automation And Test In Europe: Vols 1-3, 2008, p. 1128-1133Conference paper (Refereed)
    Abstract [en]

    Non-Linear Feedback Shift Registers (NLFSRs) have been proposed as an alternative to Linear Feedback Shift Registers (LFSRs) for generating pseudo-random sequences for stream ciphers. In this paper, we introduce (n, k)-NLFSRs which can be considered a generalization of the Galois type of LFSR. In an (n, k)-NLFSR, the feedback can be taken from any of the n bits, and the next state functions can be any Boolean function of up to k variables. Our motivation for considering this type NLFSRs is that their Galois configuration makes it possible to compute each next state function in parallel, thus increasing the speed of output sequence generation. Thus, for stream cipher application where the encryption speed is important, (n,k)-NLFSRs may be a better alternative than the traditional Fibonacci ones. We derive a number of properties of (n,k)NLFSRs. First, we demonstrate that they are capable of generating output sequences with good statistical properties which cannot be generated by the Fibonacci type of NLFSRs. Second, we show that the period of the output sequence of an (n, k)-NLFSR is not necessarily equal to the length of the largest cycle of its states. Third, we compute the period of an (n,k)-NLFSR constructed from several parallel NLFSRs whose outputs are XOR-ed and show how to maximize this period. We also present an algorithm for estimating the length of cycles of states of (n, k)-NLFSRs which uses Binary Decision Diagrams for representing the set of states and the transition relation on this set.

  • 48.
    Färm, Petra
    et al.
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Electronic Systems.
    Kuehlmann, Andreas
    Cadence Berkeley Labs, Berkeley, CA 94704, United States .
    Integrated logic synthesis using simulated annealing2011In: Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI, 2011, p. 407-410Conference paper (Refereed)
    Abstract [en]

    Conventional logic synthesis flows are composed of three separate phases: technology independent optimization, technology mapping, and technology dependent optimization. A fundamental problem with such a three-phased approach is that the global logic structure is decided during the first phase without any knowledge of the actual technology parameters considered during later phases. Although technology dependent optimization algorithms perform some limited logic restructuring, they cannot recover from fundamental mistakes made during the first phase, which often results in non-satisfiable solutions. In this paper, we present a method for integrating the three synthesis phases using an annealing algorithm as optimization framework. The annealing-based search is driven by a complex objective function, combining both technology independent as well as technology dependent optimization criteria. Our experimental results shown that, on average, the presented approach can improve the area and delay of circuits optimized with script rugged of SIS by 11.2% and 32.5% respectively.

  • 49.
    Färm, Petra
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Kuehlmann, Andreas
    Logic optimization using rule-based randomized search2005In: ASP-DAC 2005: Proceedings Of The Asia And South Pacific Design Automation Conference, IEEE , 2005, p. 998-1001Conference paper (Refereed)
    Abstract [en]

    In this paper we describe a new logic synthesis approach based on rule-based randomized search using simulated annealing. Our work is motivated by two observations: (1) Traditional logic synthesis applies literal count as the primary quality metric during the technology independent optimization phase. This simplistic metric often leads to poor circuit structures as it cannot foresee the impact of early choices on the final area, delay, power consumption, etc. (2) Although powerful, global Boolean optimization is not robust and corresponding algorithms cannot be used in practice without artificially restricting the application window. Other techniques, such as algebraic methods scale well but provide weaker optimization power To address both problems, we use randomized search that is based on a simple circuit graph representation and a complete set of local transformations that include algebraic and Boolean optimization steps. The objective of the search process can be tuned to complex cost functions, combining area, timing, routability, and power Our experimental results on benchmark functions demonstrate the significant potential of the presented approach.

  • 50.
    Färm, Petra
    et al.
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Dubrova, Elena
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Tenhunen, Hannu
    KTH, School of Information and Communication Technology (ICT), Microelectronics and Information Technology, IMIT.
    Logic optimization technique for molecular cascades2005In: Nanotechnology II / [ed] Lugli, P; Kish, LB; Mateos, J, SPIE - International Society for Optical Engineering, 2005, Vol. 5838, p. 95-104Conference paper (Refereed)
    Abstract [en]

    Molecular cascades introduced in(1) provide new ways to exploit the motion of individual molecules in nanometer-scale structures. Computation is performed by purely mechanical means similarly to the toppling of a row of standing domino. A specific feature of molecular cascades is that an inverter cannot be build, because it would require that all molecules in the inverter's output untopple when the input cascade topples. This is not possible because an untoppled state has higher energy than a toppled one. As a solution, we propose to avoid the need for inverters by representing signals by the dual-rail convention. As a basic building block we use a molecular block, which has four inputs x(1),...,x(4) such that x(3) = x(1)', x(4) = x(2)', and two outputs f(1) = x(1) . x(2) and f(2) = x(3) + x(4). If input variables are available in both complemented and non-complemented form, then any Boolean function can be implemented by a composition of such molecular blocks. We present an experimental tool which first uses a rule-based randomized search to optimize a Boolean network and then maps it into a network of interconnected molecular blocks.

12 1 - 50 of 97
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf