The Shortest Vector Problem (SVP) is a cornerstone of lattice-based cryptography, underpinning the security of numerous cryptographic schemes like NTRU. Given its NP-hardness, efficient solutions to SVP have profound implications for both cryptography and computational complexity theory. This paper presents an innovative framework that integrates concepts from quantum gravity, noncommutative geometry, spectral theory, and post-SUSY particle physics to address SVP. By mapping high-dimensional...

PeaceFounder is a centralised E2E verifiable e-voting system that leverages pseudonym braiding and history trees. The immutability of the bulletin board is maintained replication-free by voter’s client devices with locally stored consistency-proof chains. Meanwhile, pseudonym braiding done via an exponentiation mix before the vote allows anonymisation to be transactional with a single braider at a time. In contrast to existing E2E verifiable e-voting systems, it is much easier to deploy as...

Cumplido, María et al. have recently shown that the Wang-Hu digital signature is not secure and has presented a potential attack on the root extraction problem. The effectiveness of generic attacks on solving this problem for braids is still uncertain and it is unknown if it is possible to create braids that require exponential time to solve these problems. In 2023, Lin and al. has proposed a post-quantum signature scheme similar to the Wang-Hu scheme that is proven to be able to withstand...

The Walnut Digital Signature Algorithm (WalnutDSA) brings together methods in group theory, representation theory, and number theory, to yield a public-key method that provides a means for messages to be signed and signatures to be verified, on platforms where traditional approaches cannot be executed. After briefly reviewing the various heuristic/practical attacks that have be posited by Hart et al, Beullens-Blackburn, Kotov-Menshov-Ushakov, and Merz-Petit, we detail the parameter choices...

Braid groups are infinite non-abelian groups naturally arising from geometric braids. For two decades they have been proposed for cryptographic use. In braid group cryptography public braids often contain secret braids as factors and it is hoped that rewriting the product of braid words hides individual factors. We provide experimental evidence that this is in general not the case and argue that under certain conditions parts of the Garside normal form of factors can be found in the Garside...

We analyze security properties of a two-party key-agreement protocol recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels, called Kayawood protocol. At the core of the protocol is an action (called E-multiplication) of a braid group on some finite set. The protocol assigns a secret element of a braid group to each party (private key). To disguise those elements, the protocol uses a so-called cloaking method that multiplies private keys on the left and on the right by...

Braid group is a very important non-commutative group. It is also an important tool of quantum field theory, and has good topological properties. This paper focuses on the provable security research of cryptosystem over braid group, which consists of two aspects: One, we prove that the Ko's cryptosystem based on braid group is secure against chosen-plaintext-attack which proposed in CRYPTO 2000, while it dose not resist active attack. The other is to propose a new public key cryptosystem...

In this paper, we consider the conjugacy separation search problem in braid groups. We deeply redesign the algorithm presented in (Myasnikov & Ushakov, 2009) and provide an experimental evidence that the problem can be solved for $100\%$ of very long randomly generated instances. The lengths of tested randomly generated instances is increased by the factor of two compared to the lengths suggested in the original proposal for $120$ bits of security. An implementation of our attack is...

In this paper, we analyze security properties of the WalnutDSA, a digital signature algorithm recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels,that has been accepted by the National Institute of Standards and Technology for evaluation as a standard for quantum-resistant public-key cryptography. At the core of the algorithm is an action, named E-multiplication, of a braid group on some finite set. The protocol assigns a pair of braids to the signer as a private key. A...

Public-key solutions based on number theory, including RSA, ECC, and Diffie-Hellman, are subject to various quantum attacks, which makes such solutions less attractive long term. Certain group theoretic constructs, however, show promise in providing quantum-resistant cryptographic primitives because of the infinite, non-cyclic, non-abelian nature of the underlying mathematics. This paper introduces Kayawood Key Agreement protocol (Kayawood, or Kayawood KAP), a new group-theoretic key...

We present a practical cryptanalysis of WalnutDSA, a digital signature algorithm trademarked by SecureRF. WalnutDSA uses techniques from permutation groups, matrix groups, and braid groups, and is designed to provide post-quantum security in lightweight IoT device contexts. The attack given in this paper bypasses the E-Multiplication and cloaked conjugacy search problems at the heart of the algorithm and forges signatures for arbitrary messages in approximately two minutes. We also discuss...

In 2005 I. Anshel, M. Anshel, D. Goldfeld, and S. Lemieux introduced E-Multiplication(TM), a quantum-resistant, group-theoretic, one-way function which can be used as a basis for many different cryptographic applications. This one-way function was specifically designed for constrained devices, running extremely quickly and requiring very little code. This paper introduces WalnutDSA, a new E-Multiplication-based public-key method which provides efficient verification, allowing low-power and...

Recently a novel family of braid based cryptographic hash function candidates was published, claiming to be suitable for use in low resource environments. It was shown that the new hash function family performed extremely well on a range of cryptographic test suites. In this paper we instantiate an instance of the hash family, called Hickory Hash, fix a set of parameters, implement it on a Texas Instruments MSP430 16-bit microcontroller, and compare its performance characteristics to SHA2....

The Algebraic Eraser Diffie-Hellman (AEDH) protocol, first introduced in 2005 as a key agreement and authentication protocol, has been proposed as a standard in ISO JTC-1/SC-31 (29167-20) to protect various communication protocols like RFID, NFC, or Bluetooth for devices associated with ISO-18000 and the Internet of Things. A recent paper by M.J.B. Robshaw and Simon R Blackburn claims to recover sufficient data to impersonate a device or, with a bit more work, recover the private keys of a...

The \emph{Algebraic Eraser Diffie--Hellman} (AEDH) protocol was introduced in 2005 and published in 2006 by I.~Anshel, M.~Anshel, D.~Goldfeld, and S.~Lemieux as a protocol suitable for use on platforms with constrained computational resources, such as FPGAs, ASICs, and wireless sensors. It is a group-theoretic cryptographic protocol that allows two users to construct a shared secret via a Diffie--Hellman-type scheme over an insecure channel. Building on the refuted 2012 permutation-based...

Anshel, Anshel, Goldfeld and Lemieaux introduced the Colored Burau Key Agreement Protocol (CBKAP) as the concrete instantiation of their Algebraic Eraser scheme. This scheme, based on techniques from permutation groups, matrix groups and braid groups, is designed for lightweight environments such as RFID tags and other IoT applications. It is proposed as an underlying technology for ISO/IEC~29167-20. SecureRF, the company owning the trademark Algebraic Eraser, has presented the scheme to the...

By introducing extra shields on Shpilrain and Ushakov's Ko-Lee-like protocol based on the decomposition problem of group elements we propose two new key exchange schemes and then a number of public key cryptographic protocols. We show that these protocols are free of known attacks. Particularly,if the entities taking part in our protocols create their private keys composed by the generators of the Mihailova subgroups of Bn, we show that the safety of our protocols are very highly guarantied...

A presentation of a group with two generators having unsolvable word problem and an explicit countable presentation of Mihailova subgroup of F_2×F_2 with finite number of generators are given. Where Mihailova subgroup of F_2×F_2 enjoys the unsolvable subgroup membership problem.One then can use the presentation to create entities' private key in a public key cryptsystem.

We introduce a method for obtaining provable polynomial time solutions of problems in nonabelian algebraic cryptography. This method is widely applicable, easier to apply, and more efficient than earlier methods. After demonstrating its applicability to the major classic nonabelian protocols, we use this method to cryptanalyze the Triple Decomposition key exchange protocol, the only classic group theory based key exchange protocol that could not be cryptanalyzed by earlier methods.

We introduce the \emph{linear centralizer method}, and use it to devise a provable polynomial time solution of the Commutator Key Exchange Problem, the computational problem on which, in the passive adversary model, the security of the Anshel--Anshel--Goldfeld 1999 \emph{Commutator} key exchange protocol is based. We also apply this method to the computational problem underlying the \emph{Centralizer} key exchange protocol, introduced by Shpilrain and Ushakov in 2006. This is the first...

In this note, we define a cryptosystem based on non-commutative properties of groups. The cryptosystem is based on the hardness of the problem of factoring over these groups. This problem, interestingly, boils down to discrete logarithm problem on some Abelian groups. Further, we illustrate this method in three different non-Abelian groups GL$_n({{\mathbb{F}}_q})$, UT$_n({{\mathbb{F}}_q})$ and the Braid Groups.

The rapid development of quantum computing makes public key cryptosystems not based on commutative algebraic systems hot topic. Because of the non-commutativity property, the braid group with braid index more than two becomes a new candidate for constructing cryptographic protocols. A strong blind signature scheme is proposed based on the difficulty of the one-more matching conjugacy problem in the braid groups, in which the signer can not relate the signature of the blinded message to that...

We propose new cryptosystems based on self-distributive systems that are defined by conjugator searching problems (CSP) in noncommutative groups. Under the newly developed cryptographic assumptions, our basic construction is proven IND-CPA secure in the standard model. Then, we describe two extensions: The first is proven IND-CCA secure in the random oracle model, while the second achieves the IND-CCA security in the standard model. Moreover, our proposal is instantiated with braid groups,...

The braid groups have attracted much attention as a new platform of constructing cryptosystems. This paper firstly analyzes the security vulnerabilities of existing proxy signature schemes over braid groups and presents feasible attacks. Then a new proxy signature scheme is proposed based on the difficulty of the conjugacy search problem and the multiple conjugacy search problem. Security analysis shows that the proposed scheme satisfies the security requirements of proxy signature.

A proxy blind signature scheme is the combination of proxy signature and blind signature scheme. In 2009,Verma proposed a proxy blind signature scheme over braid groups. Verma claimed that the proposed scheme is secure against all possible security lapses and also satisfy all essential security attributes.This paper analyzes Verma’s proposed scheme and found that this scheme suffers with the serious security vulnerabilities. This paper show that the proposed scheme does not satisfy...

Blindness and unforgeability are two essential security requirements of a secure blind signature scheme. Blindness means that after interacting with various users, the signer can never be able to link a valid message pair. Blindness is meaningless if after interacting with various users, the signer is able to link a valid message signature pair. This security vulnerability is known as linkability attack. Recently, Verma proposed two blind signature schemes over braid groups. Verma claimed...

Delegation of powers is a common practice in the real world. To realized the delegation of powers electronically, Mambo,Usuda and Okamoto proposed the first proxy signature scheme in 1996. Since then a number of new schemes and their improvements have been proposed. In 2008, Verma proposed a proxy signature scheme over braid groups. This paper analyzes Vermas scheme and found that this scheme suffers with the serious security flaws. In this scheme,the proxy signer is able to misuse his...

Proxy Signatures, introduced by Mambo, Usuda and Okamoto, allow a designated person to sign on behalf of an original signer. Braid groups has been playing an important role in the theory of cryptography as these are non commutative groups used in cryptography. Some digital signature schemes have been given but no proxy signature scheme has been introduced over braid groups. In this paper we have proposed proxy signature scheme using conjugacy search problem over braid groups. Our proxy...

A blind signature scheme is a cryptographic protocol for obtaining a signature from a signer such that the signer's view of the protocol cannot be linked to the resulting message signature pair. In this paper we have proposed two blind signature schemes using Braid groups. The security of given schemes depends upon conjugacy search problem in Braid groups.

Braid cryptosystem was proposed in CRYPTO 2000 as an alternate public-key cryptosystem. The security of this system is based upon the conjugacy problem in braid groups. Since then, there have been several attempts to break the braid cryptosystem by solving the conjugacy problem in braid groups. In this paper, we first survey all the major attacks on the braid cryptosystem and conclude that the attacks were successful because the current ways of random key generation almost always result in...

We present a new key exchange primitive based on the decomposition problem over non-commutative groups. Different from the key establishment schemes that rely on the decomposition problem where the problem is decomposing an element into three parts where the middle piece is known, our scheme relies on decomposing an element into three parts, all unknown. We call this problem "Triple Decomposition Problem". This seems to be a harder problem because it requires quadratic systems to be...

Artin's braid groups have been recently suggested as a new source for public-key cryptography. In this paper we first propose the designated verifier group signature scheme based on the conjugacy search problem and the root problem in the braid groups which are believed to be hard problems. Furthermore, our scheme can conceal the message to be signed so that it can be applied to E-voting and calling for tenders

Known proposals for key establishment schemes based on combinatorial group theory are often formulated in a rather informal manner. Typically, issues like the choice of a session identifier and parallel protocol executions are not addressed, and no security proof in an established model is provided. Successful attacks against proposed parameter sets for braid groups further decreased the attractivity of combinatorial group theory as a candidate platform for cryptography. We present a 2-round...

Using a simple heuristic approach to the root problem in braid groups, we show that cryptographic parameters proposed in this context must be considered as insecure. In our experiments we can, often within seconds, extract the secret key of an authentication system based on the root problem in braid groups.

Lal and Chaturvedi proposed two authentication sche\-mes presumably based on the difficulty of the Root Problem in the braid group. We describe a deterministic linear time algorithm to crack the first scheme, and show that the second scheme is not more secure than schemes based on the Conjugacy Search Problem, and can therefore be cracked by existing heuristic attacks with very good success probability, as long as the parameters are practical.

After some excitement generated by recently suggested public key exchange protocols due to Anshel-Anshel-Goldfeld and Ko-Lee et al., it is a prevalent opinion now that the conjugacy search problem is unlikely to provide sufficient level of security if a braid group is used as the platform. In this paper we address the following questions: (1) whether choosing a different group, or a class of groups, can remedy the situation; (2) whether some other ``hard" problem from combinatorial group...

One of the possible generalizations of the discrete logarithm problem to arbitrary groups is the so-called conjugacy search problem. The computational difficulty of this problem in some particular groups has been used in several group based cryptosystems. Recently, a few preprints have been in circulation that suggest various heuristic attacks on the conjugacy search problem. The goal of the present survey is to stress a (probably well known) fact that these heuristic attacks alone are not...

In this note, we describe a probabilistic attack on public key cryptosystems based on the word/conjugacy problems for finitely presented groups of the type proposed recently by Anshel, Anshel and Goldfeld. In such a scheme, one makes use of the property that in the given group the word problem has a polynomial time solution, while the conjugacy problem has no known polynomial solution. An example is the braid group from topology in which the word problem is solvable in polynomial time while...

Braid Groups have recently been considered for use in Public-Key Cryptographic Systems. The most notable of these system has been the Birman-Ko-Lee system presented at Crypto 2000. This article gives a brief introduction into braid groups and the hard problems on which public key systems have been defined. It suggests a canonical form max run form using the Artin generators and supplies some supporting algorithms necessary for cryptographic operations.

We propose the first polynomial time algorithm for the braid Diffie-Hellman conjugacy problem (DHCP) on which the braid key exchange scheme and the braid encryption scheme are based~\cite{KLCHKP01}. We show the proposed method solves the DHCP for the image of braids under the Lawrence-Krammer representation and the solutions play the equivalent role of the original key for the DHCP of braids. Given a braid index $n$ and a canonical length $\ell$, the complexity is about $2^{-2}\ell^3...

In this paper, we extend the 2-party key exchange protocol on braid groups to the group key agreement protocol based on the hardness of Ko-Lee problem. We also provide authenticity to the group key agreement protocol.

Artin's braid groups currently provide a promising background for cryptographical applications, since the first cryptosystems using braids were introduced in \cite{SCY,AAF, AAG, KLC}. A variety of key agreement protocols based on braids have been described, but few authentication or signature schemes have been proposed so far. We introduce three authentication schemes based on braids, two of them being zero-knowledge interactive proofs of knowledge. Then we discuss their possible...

We propose a new digital signature scheme based on a non-commutative group where the conjugacy search problem is hard and the conjugacy decision problem is feasible. We implement our signature scheme in the braid groups and prove that an existential forgery of the implementation under no message attack gives a solution to a variation of conjugacy search problem. Then we discuss performance of our scheme under suggested parameters.

The public key cryptosystems $MST_1$ and $MST_2$ make use of certain kinds of factorizations of finite groups. We show that generalizing such factorizations to infinite groups allows a uniform description of several proposed cryptographic primitives. In particular, a generalization of $MST_2$ can be regarded as a unifying framework for several suggested cryptosystems including the ElGamal public key system, a public key system based on braid groups and the MOR cryptosystem.