Fundamenta Informaticae - Volume 169, issue 4

Authors: Kula, Mieczysław | Niwiński, Damian | Pomykała, Jacek

Article Type: Other

DOI: 10.3233/FI-2019-1846

Citation: Fundamenta Informaticae, vol. 169, no. 4, pp. i-i, 2019

Authors: Dryło, Robert | Pomykała, Jacek

Article Type: Research Article

Abstract: E. Bach showed that factorization of an integer n can be reduced in probabilistic polynomial time to the problem of computing exponents of elements in ℤ n * (in particular the group order of ℤ n * ). It is also known that factorization of square-free integer n can be reduced to the problem of computing the group order of an elliptic curve E /ℤn . In this paper we describe the analogous reduction for computing the orders of Jacobians over ℤn of hyperelliptic curves C …over ℤn using the Mumford representation of divisor classes and Cantor’s algorithm for addition. These reductions are based on the group structure of the Jacobian. We also propose other reduction of factorization to the problem of determining the number of points |C (ℤn )|, which makes use of elementary properties of twists of hyperelliptic curves. Show more

Keywords: factoring algorithms, abelian varieties, Jacobians, hyperelliptic curves

DOI: 10.3233/FI-2019-1847

Citation: Fundamenta Informaticae, vol. 169, no. 4, pp. 275-283, 2019

Authors: Dryło, Robert | Kijko, Tomasz | Wroński, Michał

Article Type: Research Article

Abstract: Let E be an elliptic curve given by any model over a field K . A rational function f : E → K of degree 2 such that f (P ) = f (Q ) ⇔ Q = ±P can be used as a point compression on E . Then there exists induced from E multiplication of values of f by integers given by [n ]f (P ) := f ([n ]P ), which can be computed using the Montgomery ladder algorithm. For this algorithm one needs the generalized Montgomery formulas for …differential addition and doubling that is rational functions A (X 1 , X 2 , X 3 ) ∈ K (X 1 , X 2 , X 3 ) and [2] ∈ K (X ) such that f (P + Q ) = A (f (P ), f (Q ), f (Q − P )) and [2]f (P ) = f ([2]P ) for generic P ,Q ∈ E . For most standard models of elliptic curves generalized Montgomery formulas are known. To use compression for scalar multiplication [n ]P for P ∈ E , one can compute after compression [n ]f (P ), which is followed by [n + 1]f (P ) in the Montgomery ladder algorithm, then one can recover [n ]P on E , since there exists a rational map B such that [n ]P = B (P , [n ]f (P ), [n + 1]f (P )) for generic P ∈ E and n ∈ Z . Such a map B is known for Weierstrass and Edwards curves, but to our knowledge it seems that it was not given for other models of elliptic curves. In this paper for an elliptic curve E and the above compression function f we give an algorithm to search for generalized Montgomery formulas, functions on K induced after compression by endomorphisms of E , and the above map B for point recovering. All these tasks require searching for solutions of similar type problems for which we describe an algorithm based on Gröbner bases. As applications we give formulas for differential addition, doubling and the above map B for Jacobi quartic, Huff curves, and twisted Hessian curves. Show more

Keywords: alternative models of elliptic curves, scalar multiplication, Montgomery ladder, point compression, Gröbner bases

DOI: 10.3233/FI-2019-1848

Citation: Fundamenta Informaticae, vol. 169, no. 4, pp. 285-294, 2019

Authors: Hanzlik, Lucjan | Kluczniak, Kamil | Kutyłowski, Mirosław

Article Type: Research Article

Abstract: Security of many cryptographic protocols is conditioned by the quality of the random elements generated in the course of the protocol execution. On the other hand, cryptographic devices implementing these protocols are designed given technical limitations, usability requirements and cost constraints. This frequently results in a black box solution. Unfortunately, black box random number generators may enable creating backdoors for stealing signing keys, breaking authentication protocols and encrypted communication. In this paper we deal with this problem and extend our approach proposed during MYCRYPT’2016. The solution discussed is generating random parameters so that: (a) the protocols are backwards compatible …(a user gets additional data that can be simply ignored), (b) verification of randomness might be executed any time without notice, so a device is forced to behave honestly, (c) the solution makes almost no intrusion in the existing protocols and is easy to implement, (d) the owner of a cryptographic device becomes secured against its designer and manufacturer that may even predict the output of the generator. In this paper we focus on a case when Diffie-Hellman protocol is executed for a generator that itself is a secret – this case has not been solved in our paper from MYCRYPT’2016. On the other hand, exactly this case occurs for the PACE protocol from the ICAO standard specifying electronic travel documents. For the sake of the proof we develop a framework of nested security games that aims to enable security proofs of modified protocols without redoing the proofs designed for their original versions. Show more

Keywords: cryptographic device, pseudorandom number generator, backdoor, provable security, security game, PACE, Diffie-Hellman key exchange

DOI: 10.3233/FI-2019-1849

Citation: Fundamenta Informaticae, vol. 169, no. 4, pp. 295-330, 2019

Authors: Morawiecki, Paweł

Article Type: Research Article

Abstract: In this paper, we investigate Keccak — the cryptographic hash function adopted as the SHA-3 standard. We propose a malicious variant of the function, where new round constants are introduced. We show that for such a variant, collision and preimage attacks are possible. We also identify a class of weak keys for malicious Keccak working in the MAC mode. Ideas presented in the paper were verified by implementing the attacks on the function with the 128-bit hash. Additionally, we show how the idea of malicious Keccak could be used in differential fault analysis against real Keccak working in the keyed …mode such as the authenticated encryption mode. Show more

Keywords: cryptanalysis, Keccak, SHA-3, differential fault analysis

DOI: 10.3233/FI-2019-1850

Citation: Fundamenta Informaticae, vol. 169, no. 4, pp. 331-343, 2019

Authors: Zajac, Pavol

Article Type: Research Article

Abstract: We propose a new hybrid encryption scheme to use with McEliece cryptosystem. The hybrid scheme uses specific authenticated encryption scheme for the encryption of the plaintext. The symmetric key is embedded in reversible way into the error vector of the McEliece cryptosystem. CCA2 security is provided by the symmetric part of the scheme. The embedding is done in such a way, that the error vector cannot be distinguished from a randomly chosen one. An eXtensible Output Function can be used to enable variable length conversion from (pseudo-random) bit strings to error vectors. The encryption part can be implemented in a …streamed way, so the sender does not have to store the whole message in the memory. Show more

Keywords: post-quantum cryptography, McEliece, hybrid schemes, CCA2

DOI: 10.3233/FI-2019-1851

Citation: Fundamenta Informaticae, vol. 169, no. 4, pp. 345-360, 2019