114(1) 2012


  1. Finite-valued Logics for Information Processing
    Arnon Avron,  Beata Konikowska 1-30
    We examine the issue of collecting and processing information from various sources, which involves handling incomplete and inconsistent information. Inspired by the framework first proposed by Belnap, we consider structures consisting of information sources which provide information about the values of formulas of classical propositional logic, and a processor which collects that information and extends it by deriving conclusions following from it according to the truth tables of classical logic, applied forward and backward. Our model extends Belnap's in allowing the sources to provide information also about complex formulas. As that framework cannot be captured using finite ordinary logical matrices, if we want to represent each of the relevant logics with a single matrix, we employ Nmatrices for that purpose. In opposition to the approach proposed in our earlier work, we assume that the information sources are reasonable, i.e. that they provide information consistent with certain coherence rules.
    We provide sound and complete sequent calculi admitting strong cut elimination for the logic of a single information source, and (several variants of) the logic generated by the source and processor structures described above. In doing this, we also provide new characterizations for some known logics. We prove that, in opposition to the variant with unconstrained information sources considered earlier, the latter logic cannot be generated by structures with any bounded number of sources.
  2. A Note on the Model Theory for Positive Modal Logic
    Sergio Celani  Ramon Jansana 31-54
    The minimum system of Positive Modal Logic SK+ is the (Ù,Ú,[¯],\Diamond,^,T)-fragment of the minimum normal modal logic K with local consequence. In this paper we develop some of the model theory for SK+ along the yet standard lines of the model theory for classical normal modal logic. We define the notion of positive bisimulation between two models, and we study the notions of m-saturated models and replete models. We investigate the positive maximal Hennessy-Milner classes. Finally, we present a Keisler-Shelah type theorem for positive bisimulations, a characterization of the first-order formulas invariant for positive bisimulations, and two definability theorems by positive modal sequents for classes of pointed models.
  3. Pseudopower Avoidance
    Ehsan Chiniforooshan, Lila Kari,  Zhi Xu 55-72
    Repetition avoidance has been intensely studied since Thue's work in the early 1900's. In this paper, we consider another type of repetition, called pseudopower, inspired by the Watson-Crick complementarity property of DNA sequences. A DNA single strand can be viewed as a string over the four-letter alphabet {A, C, G, T}, wherein A is the complement of T, while C is the complement of G. Such a DNA single strand will bind to a reverse complement DNA single strand, called its Watson-Crick complement, to form a helical double-stranded DNA molecule. The Watson-Crick complement of a DNA strand is deducible from, and thus informationally equivalent to, the original strand. We use this fact to generalize the notion of the power of a word by relaxing the meaning of "sameness" to include the image through an antimorphic involution, the model of DNA Watson-Crick complementarity. Given a finite alphabet S, an antimorphic involution is a function q: S* ® S* which is an involution, i.e., q2 equals the identity, and an antimorphism, i.e., q(u v) = q(v) q(u), for all u Î S*. For a positive integer k, we call a word w a pseudo-kth-power with respect to q if it can be written as w = u1 ... uk, where for 1 £ i, j £ k we have either ui = uj or ui = q(uj). The classical kth-power of a word is a special case of a pseudo-kth-power, where all the repeating units are identical. We first classify the alphabets S and the antimorphic involutions q for which there exist arbitrarily long pseudo-kth-power-free words. Then we present efficient algorithms to test whether a finite word w is pseudo-kth-power-free.
  4. An Algebraic Semantics for QVT-Relations Check-only Transformations
    Esther Guerra,  Juan de Lara 73-101
    QVT is the standard for model transformation defined by the OMG in the context of the Model-Driven Architecture. It is made of several transformation languages. Among them, QVT-Relations is the one with the highest level of abstraction, as it permits developing bidirectional transformations in a declarative, relational style. Unfortunately, the standard only provides a semiformal description of its semantics, which hinders analysis and has given rise to ambiguities in existing tool implementations.
    In order to improve this situation, we propose a formal, algebraic semantics for QVT-Relations check-only transformations, defining a notion of satisfaction of QVT-Relations specifications by models.
  5. Erratum to the paper: Forward-Secure Identity-Based Public-Key Encryption without Random Oracles
    Jia Yu, Fanyu Kong, Xiangguo Cheng, Rong Hao, and Jianxi Fan   103-103
    published in Fundamenta Informaticae no. 111 (2), 2011, pages 241-256.
     

114(2) 2012


  1. Dynamic Coloring of Graphs
    Piotr Borowiecki,  Elżbieta Sidorowicz 105-128
    Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm's input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problem of dynamic coloring with discoloring constraints for which the performance of the dynamic algorithm Time-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.
  2. Unambiguous Functions in Logarithmic Space
    Grzegorz Herman,  Michael Soltys 129-147
    We investigate different variants of unambiguity in the context of computing multi-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.
  3. A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part I.
    Anna Paszyńska,  Ewa Grabska,  Maciej Paszyński 149-182
    The first part of our paper presents a composite programmable graph grammar model for the self-adaptive two dimensional hp Finite Element Method algorithms (2D hp-FEM) with mixed triangular and rectangular finite elements. The two dimensional model is a starting point for the three dimensional model of self-adaptive hp-FEM presented in the second part of this paper. A computational mesh is represented by a composite graph. The operations performed over the mesh are expressed by the graph grammar rules. The three dimensional model is based on the extension of the two dimensional model with rectangular finite elements. In the second part of this paper, we conclude the presentation with numerical examples concerning the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL).
  4. A Graph Grammar Model of the hp Adaptive Three Dimensional Finite Element Method. Part II.
    Anna Paszyńska,  Ewa Grabska,  Maciej Paszyński 183-201
    This paper presents a composite programmable graph grammar model of the three dimensional self-adaptive hp Finite Element Method (hp-FEM) algorithms. The computational mesh composed of hexahedral finite elements is represented by a composite graph. The operations performed over the mesh are expressed by composite graph grammar productions. The three dimensional model is based on the extension of the two dimensional model for rectangular finite elements. This paper is concluded with numerical examples, presenting the generation of the optimal mesh for simulation of the Step-and-Flash Imprint Lithography (SFIL), the modern patterning process.
  5. Ellipse Invariant Algorithm for Texture Classification
    Chih-Chia Yao,  Kang Lee 203-220
    The classification of texture images, especially those with spatial rotation and region shift, is a challenge and important problem in image analysis and classification. This paper proposes a novel algorithm design, an ellipse invariant algorithm, to improve the capability of texture classification for spatial rotation and region shift. The principle of an ellipse invariant algorithm is to use a minimum ellipse to enclose specific representative pixels extracted by the subtracting clustering method. After translating the coordinates, the ellipse in the rotated texture would be formulated as the ellipse in original texture. Also in this paper a hybrid texture filter is proposed. In the hybrid texture filter the scheme of texture feature extraction include Gabor wavelet, neighboring grey level dependence matrix and the ellipse invariant algorithm. Support vector machines (SVMs) are introduced as the classifier. The proposed hybrid texture filter can classify both the stochastic textures and structural textures. Experimental results reveal that this proposed algorithm outperforms existing design algorithms.

114(3-4) 2012


  1. Cryptology in Progress: 10th Central European Conference on Cryptology, Będlewo, Poland, 2010. Prefacei-ii
  2. Cryptanalysis of the Full AES Using GPU-Like Special-Purpose Hardware
    Alex Biryukov,  Johann Großschädl 221-237
    The block cipher Rijndael has undergone more than ten years of extensive cryptanalysis since its submission as a candidate for the Advanced Encryption Standard (AES) in April 1998. To date, most of the publicly-known cryptanalytic results are based on reduced-round variants of the AES (respectively Rijndael) algorithm. Among the few exceptions that target the full AES are the Related-Key Cryptanalysis (RKC) introduced at ASIACRYPT 2009 and attacks exploiting Time-Memory-Key (TMK) trade-offs such as demonstrated at SAC 2005. However, all these attacks are generally considered infeasible in practice due to their high complexity (i.e. 299.5 AES operations for RKC, 280 for TMK). In this paper, we evaluate the cost of cryptanalytic attacks on the full AES when using special-purpose hardware in the form of multi-core AES processors that are designed in a similar way as modern Graphics Processing Units (GPUs) such as the NVIDIA GT200b. Using today's VLSI technology would allow for the implementation of a GPU-like processor reaching a throughput of up to 1012 AES operations per second. An organization able to spend one trillion US$ for designing and building a supercomputer based on such processors could theoretically break the full AES in a time frame of as little as one year when using RKC, or in merely one month when performing a TMK attack. We also analyze different time-cost trade-offs and assess the implications of progress in VLSI technology under the assumption that Moore's law will continue to hold for the next ten years. These assessments raise some concerns about the long-term security of the AES.
  3. Evaluation of PP-1 Cipher Resistance against Differential and Linear Cryptanalysis in Comparison to a DES-like Cipher
    Krzysztof Chmiel,  Anna Grocholewska-Czurylo,  Janusz Stoklosa 239-269
    In the paper we present an involutional block cipher PP-1, which is a scalable SPN. The cipher has very low memory requirements and uses only simple and fast arithmetic operations. The paper discusses in detail the PP-1 cipher design, including the S-box construction, the permutation and the round key scheduling. The quality of the PP-1 cipher is evaluated with respect to differential and linear cryptanalysis. Its quality is compared to the quality of a comparative algorithm with the same block length, as well as to the quality of the class of balanced Feistel ciphers, and in particular to DES quality.
  4. On Second-order Nonlinearities of Some D0 Type Bent Functions
    Sugata Gangopadhyay,  Brajesh Kumar Singh 271-285
    In this paper we study the lower bounds of second-order nonlinearities of bent functions in the class D0 constructed by modifying certain cubic Maiorana-McFarland (MMF) type bent functions. We also obtain improvements on existing results on second-order nonlinearities of some cubic MMF type bent functions having no affine derivative.
  5. Algorithm for Generating Primes p and q Such that q Divides p4±p3+ p2±p+1
    Maciej Grze¶kowiak 287-299
    In the paper we propose an algorithm for generating large primes p and q such that q divides p4+ p3+ p2+ p+1 or p4− p3+p2−p+1, and p, q are key parameters for Giuliani-Gong's Public Key System. We analyze the computational complexity of considered methods.
  6. Remarks on Pseudorandom Binary Sequences Over Elliptic Curves
    László Mérai 301-308
    In the paper the pseudorandomness of binary sequences defined over elliptic curves is studied and both the well-distribution and correlation measures are estimated. The paper is based on the Kohel-Shparlinski bound and the Erdös-Turán-Koksma inequality.
  7. The Cube Attack on Stream Cipher Trivium and Quadraticity Tests
    Piotr Mroczkowski,  Janusz Szmidt 309-318
    In 2008 I. Dinur and A. Shamir presented a new type of algebraic attack on symmetric ciphers named cube attack. The method has been applied to reduced variants of stream ciphers Trivium and Grain-128, reduced variants of the block ciphers Serpent and CTC and to a reduced version of the keyed hash function MD6. Previously, a very similar attack named AIDA was introduced by M. Vielhaber, in 2007. In this paper we develop quadraticity tests within the cube attack and apply them to a variant of stream cipher Trivium reduced to 709 initialization rounds. Using this method we obtain the full 80-bit secret key. In this way it eliminates the stage of brute force search of some secret key bits which occured in previous cube attacks.
  8. Attacking M&M Collective Signature Scheme
    Michal Rjasko,  Martin Stanek 319-323
    A collective signature scheme aims to solve the problem of signing a message by multiple signers. Recently, Moldovyan and Moldovyan proposed a scheme for collective signatures based on Schnorr signatures. We show some security weaknesses of the scheme.
  9. Public-Key Cryptography Based on a Cubic Extension of the Lucas Functions
    Eric Roettger,  Hugh C. Williams 325-344
    One of the goals of public-key cryptography is to securely exchange a key by use of a public channel without the users previously communicating with one another. In 1976 W. Diffie and M. Hellman had an idea how to do this by exploiting mathematically difficult one-way problems. Diffie-Hellman key exchange is based on the believed difficulty of the discrete log problem. This paper presents a new key exchange protocol based on functions that were developed to generalize the Lucas functions. Relevant results about this generalization of the Lucas functions are provided that provide the machinery for the Diffie-Hellman-like key exchange presented here. Lastly, there is a brief discussion about the efficiency of our system versus Diffie-Hellman key exchange and LUCDIF.
  10. Remarks on the Classical Threshold Secret Sharing Schemes
    Stanisaw Spież,  Marian Srebrny,  Jerzy Urbanowicz 345-357
    We survey some results related to classical secret sharing schemes defined in Shamir [10] and Blakley [1], and developed in Brickell [2] and Lai and Ding [4]. Using elementary symmetric polynomials, we describe in a unified way which allocations of identities to participants define Shamir's threshold scheme, or its generalization by Lai and Ding, with a secret placed as a fixed coefficient of the scheme polynomial. This characterization enabled proving in Schinzel et al. [8], [9] and Spie\.z et al. [13] some new and non-trivial properties of such schemes.
    Also a characterization of matrices corresponding to the threshold secret sharing schemes of Blakley and Brickell's type is given. Using Gaussian elimination we provide an algorithm to construct all such matrices which is efficient in the case of relatively small matrices. The algorithm may be useful in constructing systems where dynamics is important (one may generate new identities using it). It can also be used to construct all possible MDS codes.
  11. Solving Trivium-based Boolean Equations Using the Method of Syllogisms
    Pavol Zajac 359-373
    The article examines a practical application of the method of syllogisms to solve a system of Boolean equations arising in the cryptanalysis of the stream cipher Trivium. Experimental results show that different guessing strategies lead to significantly different complexities of generic attacks. A new experimental approach is presented that can be used to estimate lower bounds on the complexity of such attacks.