Garuda - Garba Rujukan Digital

Elementary Algorithms Analysis of Megrelishvili Protocol Muhammad Arzaki
Indonesia Journal on Computing (Indo-JC) Vol. 1 No. 1 (2016): March, 2016
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.21108/INDOJC.2016.1.1.52

This article presents an investigation of asymptotic time complexities of several algorithms related to Megrelishvili protocol. The analysis are carried out for the private keys computations and public exchange of values, public key constructions, as well as an elementary exhaustive search attack algorithm. We show that the complexities of these algorithms are higher than the complexities of elementary algorithms involved in the conventional Diffie - Hellman protocol (DHP) or its variant on elliptic curves (ECDHP). This condition also implies that Megrelishvili protocol is more secure than DHP and ECDHP against exhaustive search attack.

On the Generalizations of Megrelishvili Protocol for Group Key Distribution Muhammad Arzaki
Indonesia Journal on Computing (Indo-JC) Vol. 2 No. 2 (2017): September, 2017
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.21108/INDOJC.2017.2.2.179

This article presents an extension of our previous research in <cite>AW17</cite> where we propose two variants of Megrelishvili key distribution schemes and investigate some of their elementary theoretical security analysis. We briefly discuss the two protocols in <cite>AW17</cite> and propose another two schemes which are more efficient than the preceding ones. Additionally, we also devise efficient procedures for constructing a new mutual key if the group membership is altered. Furthermore, we discuss the security of the protocols rigorously and we provide a sufficient condition for breaking the protocols by way of solving several instances of Megrelishvili vector-matrix problems (MVMP). We prove that the secret group key can be recovered easily if an attacker can express the sum of the secret exponents of the participants as a linear combination of the secret exponents excerpted from the transmission. Based on this result, we reason that our Megrelishvili key distribution schemes are theoretically at least as secure as the standard two-party Megrelishvili key exchange procedure.

Solving Tatamibari Puzzle Using Exhaustive Search Approach Enrico Christopher Reinhard; Muhammad Arzaki; Gia Septiana Wulandari
Indonesia Journal on Computing (Indo-JC) Vol. 7 No. 3 (2022): December, 2022
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2022.7.3.675

Tatamibari is a puzzle that was first published in 2004 and was proven to be NP-complete in 2020. However, to the best of our knowledge, algorithmic investigation of the Tatamibari puzzle is relatively new and limited. There are discussions about an approach for solving the Tatamibari puzzle using the Z3 SMT solver, but there are no details regarding the steps of the algorithm as well as its explicit asymptotic upper bound. In addition, this solver requires an additional library that cannot be directly executed using standard libraries in an arbitrary imperative programming language. Hence, this paper discusses an exhaustive search approach for solving an arbitrary Tatamibari puzzle. We show that this algorithm can find all solutions to an $m \times n$ Tatamibari instance with $h$ hints in $O(\max\{m^2 n^2, h^{mn-h} \cdot hmn\})$ time. We also use this algorithm to find the number of possible Tatamibari solutions in an $m \times n$ grid for some small values of $m$ and $n$.

Elementary Search-based Algorithms for Solving Tilepaint Puzzles Vincentius Arnold Fridolin; Muhammad Arzaki; Gia Septiana Wulandari
Indonesia Journal on Computing (Indo-JC) Vol. 8 No. 2 (2023): August, 2023
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2023.8.2.750

This paper discusses the elementary computational aspects of Tilepaint puzzles, single-player logic puzzles introduced in 1995 and confirmed NP-complete in 2022. Two elementary search-based algorithms are proposed: the complete search technique with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning optimization. This paper shows that the asymptotic running time of these algorithms for solving an $m \times n$ Tilepaint instance containing $p$ tiles are respectively $O(2^{p} \cdot p \cdot mn)$ and $O(2^{p} \cdot mn)$, implying that the latter method is asymptotically faster by a factor of $p$. This paper also discusses tractable and intractable variants of Tilepaint puzzles. This paper shows that an $m \times n$ Tilepaint instance containing $mn$ tiles of size $1 \times 1$ is solvable in polynomial time. In contrast, this paper shows that solving general $m \times 1$ and $1 \times n$ Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.

Solving Tatamibari Puzzle Using Exhaustive Search Approach Reinhard, Enrico Christopher; Arzaki, Muhammad; Wulandari, Gia Septiana
Indonesian Journal on Computing (Indo-JC) Vol. 7 No. 3 (2022): December, 2022
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2022.7.3.675

Tatamibari is a puzzle that was first published in 2004 and was proven to be NP-complete in 2020. However, to the best of our knowledge, algorithmic investigation of the Tatamibari puzzle is relatively new and limited. There are discussions about an approach for solving the Tatamibari puzzle using the Z3 SMT solver, but there are no details regarding the steps of the algorithm as well as its explicit asymptotic upper bound. In addition, this solver requires an additional library that cannot be directly executed using standard libraries in an arbitrary imperative programming language. Hence, this paper discusses an exhaustive search approach for solving an arbitrary Tatamibari puzzle. We show that this algorithm can find all solutions to an $m \times n$ Tatamibari instance with $h$ hints in $O(\max\{m^2 n^2, h^{mn-h} \cdot hmn\})$ time. We also use this algorithm to find the number of possible Tatamibari solutions in an $m \times n$ grid for some small values of $m$ and $n$.

Elementary Search-based Algorithms for Solving Tilepaint Puzzles Fridolin, Vincentius Arnold; Arzaki, Muhammad; Wulandari, Gia Septiana
Indonesian Journal on Computing (Indo-JC) Vol. 8 No. 2 (2023): August, 2023
Publisher : School of Computing, Telkom University

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.34818/INDOJC.2023.8.2.750

This paper discusses the elementary computational aspects of Tilepaint puzzles, single-player logic puzzles introduced in 1995 and confirmed NP-complete in 2022. Two elementary search-based algorithms are proposed: the complete search technique with a bitmasking approach and the prune-and-search technique with a backtracking approach and pruning optimization. This paper shows that the asymptotic running time of these algorithms for solving an $m \times n$ Tilepaint instance containing $p$ tiles are respectively $O(2^{p} \cdot p \cdot mn)$ and $O(2^{p} \cdot mn)$, implying that the latter method is asymptotically faster by a factor of $p$. This paper also discusses tractable and intractable variants of Tilepaint puzzles. This paper shows that an $m \times n$ Tilepaint instance containing $mn$ tiles of size $1 \times 1$ is solvable in polynomial time. In contrast, this paper shows that solving general $m \times 1$ and $1 \times n$ Tilepaint puzzles remains intractable by reducing such problems from the subset-sum problem.

Title

Found 6 Documents
Search
Journal : Indonesian Journal on Computing (Indo-JC)

Abstract

Abstract

Abstract

Abstract

Abstract

Abstract

Title Search

Found 6 Documents Search Journal : Indonesian Journal on Computing (Indo-JC)

Abstract

Abstract

Abstract

Abstract

Abstract

Abstract

Title

Found 6 Documents
Search
Journal : Indonesian Journal on Computing (Indo-JC)