Fundamenta Informaticae - Volume 114, issue 3-4

Authors: Jaworski, Jerzy | Kula, Mieczysław | Niwiński, Damian | Urbanowicz, Jerzy

Article Type: Other

DOI: 10.3233/FI-2012-625

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. i-ii, 2012

Authors: Biryukov, Alex | Großschädl, Johann

Article Type: Research Article

Abstract: 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. Show more

Keywords: Advanced Encryption Standard, Cryptanalysis, Cryptanalytic Hardware, Graphics Processing Unit, Performance and Energy Evaluation

DOI: 10.3233/FI-2012-626

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 221-237, 2012

Authors: Chmiel, Krzysztof | Grocholewska-Czurylo, Anna | Stoklosa, Janusz

Article Type: Research Article

Abstract: 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.

Keywords: block cipher, S-box construction, cryptanalysis, differential approximation, linear approximation

DOI: 10.3233/FI-2012-627

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 239-269, 2012

Authors: Gangopadhyay, Sugata | Singh, Brajesh Kumar

Article Type: Research Article

Abstract: 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.

Keywords: Second-order nonlinearity, bent functions, Maiorana-McFarland type bents, ${\rm D}_0$ type bents

DOI: 10.3233/FI-2012-628

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 271-285, 2012

Authors: Grześkowiak, Maciej

Article Type: Research Article

Abstract: 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.

Keywords: The Giuliani-Gong Public Key System, primes of special form

DOI: 10.3233/FI-2012-629

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 287-299, 2012

Authors: Mérai, László

Article Type: Research Article

Abstract: 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.

Keywords: pseudorandom, binary sequence, elliptic curve, character

DOI: 10.3233/FI-2012-630

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 301-308, 2012

Authors: Mroczkowski, Piotr | Szmidt, Janusz

Article Type: Research Article

Abstract: 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. Show more

DOI: 10.3233/FI-2012-631

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 309-318, 2012

Authors: Rjaško, Michal | Stanek, Martin

Article Type: Research Article

Abstract: 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.

DOI: 10.3233/FI-2012-632

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 319-323, 2012

Authors: Roettger, Eric | Williams, Hugh C.

Article Type: Research Article

Abstract: 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. Show more

Keywords: linear recurrence, Lucas functions, public-key, cryptography

DOI: 10.3233/FI-2012-633

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 325-344, 2012

Authors: Spież, Stanisław | Srebrny, Marian | Urbanowicz, Jerzy

Article Type: Research Article

Abstract: 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ż 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. MSC: primary 94A62; secondary 11T71; 11C20 Show more

Keywords: Secret sharing, finite fields, generalized Vandermonde determinants, elementary symmetric polynomials, Gaussian elimination, threshold access structure, MDS codes, (k − 1, k)-bases

DOI: 10.3233/FI-2012-634

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 345-357, 2012

Authors: Zajac, Pavol

Article Type: Research Article

Abstract: 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.

Keywords: Boolean equations, algebraic cryptanalysis, method of syllogisms, Trivium

DOI: 10.3233/FI-2012-635

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 359-373, 2012

Article Type: Other

Citation: Fundamenta Informaticae, vol. 114, no. 3-4, pp. 375-376, 2012