Publication
- V. Arvind, Bireswar Das, Johannes Köbler: A Logspace Algorithm for Partial 2-Tree Canonization.. CSR'08
- V. Arvind, Bireswar Das, Johannes Köbler: The Space Complexity of
k-tree Isomorphism.. ISAAC'07
- V. Arvind, Bireswar Das, Partha Mukhopadhyay: On Isomorphism and
Canonization of Tournaments and Hypertournaments. ISAAC'06
- V. Arvind, Bireswar Das, Partha Mukhopadhyay: The Complexity of Black-Box
Ring Problems. COCOON'06
- V. Arvind, Bireswar Das: SZK Proofs for Black-Box Group Problems.
CSR 2006: 6-17.
- Rani Siromoney, Bireswar Das: Plasmids to Solve #3SAT. Aspects of
Molecular Computing 2004: 361-366
- Rani Siromoney, Bireswar Das: DNA algorithm for breaking a
propositional logic based cryptosystem. Bulletin of the EATCS 79:
170-177 (2003)
MTech Dissertation
DNA Cryptology: A Brief Survey And A DNA Algorithm For Breaking A
Propositional Logic Based Cryptosystem.
The Space Complexity of k-tree Isomorphism.
Abstract
We show that isomorphism testing of k-trees is in the class
StUSPACE(log n) (strongly unambiguous logspace). This bound follows
from a deterministic logspace algorithm that accesses a strongly
unambiguous logspace oracle for canonizing k-trees. Further we
give a logspace canonization algorithm for k-paths.
Postscript
Pdf
On Isomorphism and
Canonization of Tournaments and Hypertournaments.
Abstract
We give a polynomial-time oracle algorithm for Tournament
Canonization that accesses oracles for Tournament Isomorphism and
Rigid-Tournament Canonization. Extending the Babai-Luks Tournament
Canonization algorithm, we give an $n^{O(k + \log n)}$ algorithm for
canonization and isomorphism testing of $k$-hypertournaments, where
$n$ is the number of vertices and $k$ is the size of hyperedges.
Postscript
Pdf
The Complexity of Black-Box Ring Problems.
Abstract
We study the complexity of some computational problems on finite
black-box rings whose elements are encoded as strings of a given
length and the ring operations are performed by a black-box oracle.
We give a polynomial-time quantum algorithm to compute a basis
representation for a given black-box ring. Using this result we
obtain polynomial-time quantum algorithms for several natural
computational problems over black-box rings.
Postscript
Pdf
SZK Proofs for Black-Box Group Problems.
Abstract
In this paper we classify several algorithmic problems in group
theory in the classes PZK and SZK (problems with perfect/statistical
zero-knowledge proofs respectively). Prior to this, these problems
were known to be in $AM\cap coAM$. As
$PZK \subseteq SZK \subseteq AM \cap coAM$, we have a tighter upper
bound for these problems. Specifically:
- We show that the permutation group problems Coset Intersection,
Double Coset Membership, Group Conjugacy are in PZK. Further, the
complements of these problems also have perfect zero knowledge
proofs (in the liberal sense). We also show that permutation group
isomorphism for solvable groups is in PZK. As an ingredient of this
protocol, we design a randomized algorithm for sampling short
presentations of solvable permutation groups.
- We show that the complement of all the above problems have
concurrent zero knowledge proofs.
- We prove that the above problems for black-box groups are
in SZK.
- Finally, we also show that some of the problems have SZK
protocols with efficient provers in the sense of D. Micciancio, S. Vadhan (CRYPTO'03).
Postscript
Pdf
DNA algorithm for breaking a
propositional logic based cryptosystem.
Abstract
A public-key cryptosystem based on propositional logic was presented in \cite{kn:karij} and was shown
to be optimal in the sense that any cryptanalytic attack against it can be used to break other
cryptosystems as well. Such a cryptanalytic method could also be used to solve in polynomial
time, the membership problem of any language in $NP\cap coNP$. Only worstcase complexities are
considered. Tom Head has given an elegant and simple DNA algorithm to solve the SAT and other
hard problems. Artificial plasmids are created, which are circular double-stranded DNA molecules.
The DNA computation is done by initializing with this single molecular variety combining the
operations of cut and paste into a single compound operation.
In this paper, we modify this algorithm to present a cryptanalytic attack on
the cryptosystem based on propositional logic.
Postscript
Pdf
MTech Dissertation
Description
My Mtech Dissertation consists of a survey of DNA Cryptology and the paper DNA algorithm for breaking a
propositional logic based cryptosystem.
Postscript
Pdf