Anonymous communication networks have emerged as crucial tools for obfuscating communication pathways and concealing user identities. However, their practical deployment faces several critical challenges, including vulnerability to artificial intelligence-powered metadata analysis, difficulties in fitting decentralized architectures, and the lack of provable security guarantees. To address these limitations, this paper proposes a novel decentralized anonymous routing protocol that resists both traceability and traffic analysis. The proposed protocol is fully decentralized and eliminates reliance on the threshold model and trusted third-party setups, ensuring indistinguishable identity privacy. Different from traditional empirical or heuristic security analysis of anonymous networks, this paper rigorously proves indistinguishable identity privacy for users even in extremely adversarial environments. Furthermore, simulation results validate the protocol’s practical feasibility, demonstrating both security and efficiency. By enabling secure information exchange while preserving user privacy, the proposed protocol offers a provably secure solution for privacy-preserving communication in modern digital infrastructures.

In this paper, several infinite families of codes over the extension of non-unital non-commutative rings are constructed utilizing general simplicial complexes. Thanks to the special structure of the defining sets, the principal parameters of these codes are characterized. Specially, when the employed simplicial complexes are generated by a single maximal element, we determine their Lee weight distributions completely. Furthermore, by considering the Gray image codes and the corresponding subfield-like codes, numerous of linear codes over Fqare also obtained, whereqis a prime power. Certain conditions are given to ensure the above linear codes are (Hermitian) self-orthogonal in the case ofq= 2; 3; 4. It is noteworthy that most of the derived codes over Fqsatisfy the Ashikhmin-Barg’s condition for minimality. Besides, we obtain two infinite families of distanceoptimal codes over Fqwith respect to the Griesmer bound. By puncturing the Gray image codes and subfield-like codes, several classes of projective codes are presented.

Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security, and it is widely believed that the algebraic structure will help us solve the hard problems in ideal lattices more efficiently. In this paper, we study the additional algebraic structure of ideal lattices further and find that a given ideal lattice in a polynomial ring can be embedded as an ideal into infinitely many different polynomial rings by the coefficient embedding. We design an algorithm to verify whether a given full-rank lattice in <?TeX $\mathbb {Z}^n$?> Math 1 is an ideal lattice and output all the polynomial rings that the given lattice can be embedded into as an ideal with bit operations <?TeX $\mathcal {O}(n^3(\log n + B)^2(\log n)^2)$?> Math 2 , where n is the dimension of the lattice and B is the upper bound of the bit length of the entries of the input lattice basis. We would like to point out that Ding and Lindner proposed an algorithm for identifying ideal lattices and outputting a single polynomial ring of which the input lattice can be regarded as an ideal with bit operations <?TeX $\mathcal {O}(n^5B^2)$?> Math 3 in 2007. However, we find a flaw in Ding and Lindner’s algorithm, and it causes some ideal lattices can’t be identified by their algorithm.

The Modular Inversion Hidden Number Problem (MIHNP), which was proposed at Asiacrypt 2001 by Boneh, Halevi, and Howgrave-Graham, is summarized as follows: Assume that the$\delta $most significant bits of$z$are denoted by${\mathrm {MSB}}_{\delta }(z)$. The goal is to retrieve the hidden number$\alpha \in \mathbb {Z}_{p}$given many samples$\left ({t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})}\right)$for random$t_{i} \in \mathbb {Z}_{p}$. MIHNP is a significant subset of Hidden Number Problems. Eichenauer and Lehn introduced the Inversive Congruential Generator (ICG) in 1986. It is basically characterized as follows: For iterated relations$v_{i+1}=(av^{-1}_{i}+b)\bmod {p}$with a secret seed$v_{0} \in \mathbb {Z}_{p}$, each iteration produces$\mathrm {MSB}_{\delta }(v_{i+1})$where$i \geq 0$. The ICG family of pseudorandom number generators is a significant subclass of number-theoretic pseudorandom number generators. Sakai-Kasahara scheme is an identity-based encryption (IBE) system proposed by Sakai and Kasahara. It is one of the few commercially implemented identity-based encryption schemes. We explore the Coppersmith approach for solving a class of modular polynomial equations, which is derived from the recovery issue for the hidden number$\alpha $in MIHNP and the secret seed$v_{0}$in ICG, respectively. Take a positive integer$n=d^{3+o(1)}$for some positive integer constant$d$. We propose a heuristic technique for recovering the hidden number$\alpha $or secret seed$v_{0}$with a probability close to 1 when$\delta /\log _{2} p>\frac {1}{d+1}+o\left({\frac {1}{d}}\right)$. The attack’s total time complexity is polynomial in the order of$\log _{2} p$, with the complexity of the LLL algorithm increasing as$d^{\mathcal {O}(d)}$and the complexity of the Gröbner basis computation increasing as$d^{\mathcal {O}(n)}$. When$d> 2$, this asymptotic bound surpasses the asymptotic bound$\delta /\log _{2} p>\frac {1}{3}$established by Boneh, Halevi, and Howgrave-Graham at Asiacrypt 2001. This is the first time a more precise constraint for solving MIHNP is established, implying that the claim that MIHNP is difficult is violated whenever$\delta /\log _{2} p < \frac {1}{3}$. Then we study ICG. To our knowledge, we achieve the best performance for attacking ICG to date. Finally, we provide an MIHNP-based lattice approach that recovers the signer’s secret key in the Sakai-Kasahara type signatures when the most (least) significant bits of the signing exponents are exposed. This improves the existing work in this direction.

Solving quadratic congruence equations is an expensive operation widely employed in cryptographic constructions for secure Internet of Things applications. Recently, two outsourcing algorithms were proposed by Zhanget al.to solve quadratic congruence equations by employing Cippolla’s algorithm. It was claimed that all the inputs and outputs can be obscured in these two algorithms. However, we present two passive attacks in this article to show that all the inputs and outputs can be recovered efficiently by just a curious server, which implies the two outsourcing algorithms are insecure. To fix them, we further propose an improved outsourcing algorithm to solve quadratic congruence equations, which is more efficient and the privacy of actual inputs and outputs can be protected very well.

In a (Ring-)LWE-based key exchange scheme, the error reconciliation technique is usually employed to help the two parties establish the exactly same shared key. In an error reconciliation mechanism, a hint should be produced and sent by one party, which makes the key exchange scheme sequential and the two parties asymmetrical. There is an alternative approach to realize key exchange, the encryption-based key encapsulation mechanism (KEM), where a message is encrypted by one party and the other party decrypts the corresponding ciphertext to derive the shared key from the recovered message. In this paper, we try to unify the two approaches and show that the two mainstream reconciliation instantiations, Ding et. al's branch and Peikert's branch, can both be derived by just choosing a certain message in some encryption-based KEMs we constructed, in which the compressed ciphertext is just the hint and the certain message is exactly the reconciled value. This explains why reconciliation-based key exchange scheme must be sequential and have two asymmetrical parties and will bring more generalization for reconciliation mechanism. As a byproduct, a new (Ring-)LWE-based encryption structure is proposed.

Kleptography introduced by Young and Yung is about using an embedded backdoor to perform attacks on a cryptosystems. At SAC'17, Kwantet al. proposed a kleptographic backdoor on NTRU encryption scheme and thought that the backdoor can not be detected. However, in this paper we show that the user can detect the backdoor very efficiently and hence the problem of constructing a kleptographic backdoor on NTRU stays open. Moreover, we also design a universal method to embed a kleptographic backdoor for RLWE-based scheme, such as NewHope. Our construction is shown to be strongly undetectable, which reveals the threats of the kleptographic attacks on lattice-based schemes.

Hamming quasi‐cyclic (HQC) cryptosystem, proposed by Aguilar Melchor et al ., is a code‐based key encapsulation mechanism (KEM) submitted for the NIST standardisation process of post‐quantum cryptography (PQC). Under the assumption that the s ‐decision quasi‐cyclic syndrome decoding ( s ‐DQCSD) problem is hard for s = 2 and 3, HQC, viewed as a public‐key encryption scheme, is proven to be indistinguishability under chosen plaintext attack (IND‐CPA) secure, and can be transformed into an IND‐Adaptive chosen ciphertext attack secure KEM. However, the authors will show that the s ‐DQCSD problem is actually not intractable and HQC cannot attain IND‐CPA security with all the proposed parameter sets. As HQC was selected as one of the second‐round candidates by NIST, it was also updated to resist attack. The underlying s ‐DQCSD problem was replaced by the s ‐DQCSD with a parity problem and they claimed that the updated HQC could attain IND‐CPA security under the hardness of the new problem. However, they find that there is some flaw in their security proof and the updated HQC is still vulnerable to attack. To fix it, they define a new problem called s ‐DQCSD with variable weight and present revised scheme HQC‐ β , which finally attains the IND‐CPA security under the hardness assumption of the new problem.

In November 2017, Hecht and Kamlofsky submitted HK17, a quaternion(octonion)-based Diffie-Hellman key exchange protocol, to NIST post-quantum cryptography project, and thought that at least O(p8) arithmetic operations are needed for a passive adversary to recover the shared key where p is the modulo used in the scheme. Later, Bernstein and Lange pointed out that the shared key can be recovered with O(p) arithmetic operations, which implies that HK17 with small p is not secure. However, their attack does not work in practice for the scheme with sufficiently large p, although the scheme is still efficient. In this paper, we propose an attack to show that just constant arithmetic operations, or Õ(log p) bit operations, are enough to recover the shared key for a passive adversary. Note that even the legal party in the protocol needs at least Õ(log p) bit operations to establish the shared key. We break HK17 completely in the practical sense.

As a canonical form for integer matrices, Hermite Normal Form (HNF) has been widely used in various fields such as computational number theory and cryptography. In previous algorithms, arithmetic modulo the determinant is usually used to control the intermediate numbers. In this paper, we propose a new technique to compute the HNF for integer matrices via solving a system of linear equations, with which we can control the intermediate numbers more tightly. Based on the technique, we present two new HNF algorithms. First we present a conceptually simpler algorithm. This algorithm is slow in practical and is intended only for illustrating the idea. Then we propose a practical hybrid algorithm. Under some reasonable assumption, the new algorithm has expected time complexity \widetildeO (n^ømegałog M). Here n^ømega is the number of arithmetic operations required to multiply two n\times n matrices and the currently best known value for ømega is approximately 2.373.

The NTRU cryptosystem is the most practical scheme known to date and has drawn considerable interest, which depends on three integer parameters (N, p, q) and four sets Lf, Lg, Lr, Lm of polynomials of degree N − 1 with small integer coefficients. We choose p, q such that gcd(p, q) = 1 and p is much smaller than q, denote the ring Z[x]/(xN -- 1) by R and the multiplication in R by *.

In 1998, Cai and Cusick proposed a lattice-based public-key cryptosystem based on the similar ideas of the Ajtai-Dwork cryptosystem, but with much less data expansion. However, they didn't give any security proof. In our paper, we present an efficient ciphertext-only attack which runs in polynomial time against the cryptosystem to recover the message, so the Cai-Cusick lattice-based public-key cryptosystem is not secure.