Abstract Integral cryptanalysis is a pivotal technique in symmetric-key cryptography. This paper enhances the integral key-recovery analysis of the Feistel-based cipher Zodiac by introducing a systematic framework for identifying optimal key recovery attack paths. This framework leverages the conversion relationship between zero-correlation linear and integral distinguishers, seamlessly integrating distinguisher construction with key recovery into a coherent process. During the key recovery phase, we apply the partial-sum technique to reduce computational complexity and adaptively adjust the number of distinguisher rounds to optimize performance. We reduce the computational complexity of the full-round attack on Zodiac-192 from $$2^{190}$$ 2 190 to $$2^{87}$$ 2 87 . Our analysis also identifies two 14-round integral distinguishers: the longest known for Zodiac. Interestingly, we identify that the optimal full-round key recovery is achieved by pairing the partial-sum technique with the 13-round distinguisher, not the longer 14-round one. This result clearly demonstrates that the longest distinguisher does not guarantee the most efficient key recovery attack. Also we performed a non-standard extension (adding one round) on Zodiac, achieving the first 17-round key recovery attack on Zodiac-192.

Abstract In lightweight block cipher designs, involutory components are often employed to minimize circuit area. However, these components can also introduce security vulnerabilities. Loong is a family of lightweight block ciphers based on the Substitution-Permutation Network (SPN) structure. Each round of Loong incorporates two involutory MDS matrices and two involutory S-boxes, resulting in a fully involutory round function. While these operations provide high diffusion and a substantial algebraic degree, the involutory nature of the design makes Loong vulnerable to weak-key attacks. In this paper, we present several notable observations regarding the round function of Loong. By exploiting the unique properties of its involutory round function, we identify weak-key differential characteristics for all three full-round variants of Loong. Specifically, the probabilities of weak-key differential characteristics for Loong-64, Loong-80, and Loong-128 are $$2^{-26.83}$$ 2 - 26.83 , $$2^{-37.42}$$ 2 - 37.42 and $$2^{-46.66}$$ 2 - 46.66 , respectively. The corresponding weak-key spaces are of sizes $$2^{36}$$ 2 36 , $$2^{52}$$ 2 52 and $$2^{96}$$ 2 96 . These findings effectively compromise the security of Loong. Furthermore, we conducted experiments on a personal computer and identified practical differential characteristics for Loong-64. Additionally, we analyze the security of block ciphers with involutory round functions in general. Our findings indicate that such designs are more prone to weak-key attacks and are even more vulnerable to general differential cryptanalysis. While the use of involutory round functions reduces circuit area and improves cipher efficiency, it also introduces significant security weaknesses.

Abstract Recently, the concept of committing message authentication codes (MACs) was proposed at Crypto 2024, following the definition of committing authenticated encryption (AE). A secure committing MAC requires that it is infeasible for any adversary to find two different key and message pairs that generate the same tag. In this paper, we present committing attacks against PMAC, LightMAC, and UMAC, demonstrating that these MACs are not CMT secure. We also provide a CMT-K security proof for UMAC. Furthermore, we introduce two general methods for constructing one-key and two-key MACs with CMT-K security.

Abstract Lattice-based commitment schemes and their associated zero-knowledge proofs are essential building blocks for advanced lattice-based cryptographic protocols. In particular, proofs of algebraic relations among committed messages are widely used in privacy-preserving protocols such as range proofs. At CRYPTO 2020, Attema et al. proposed practical proofs for valid openings and multiplicative relations among committed values using the BDLOP commitment scheme. In their work, all commitments are generated using the same short randomness. In this paper, we consider a batch setting where commitments are generated using $$\ell$$ ℓ independent random vectors and present a batch valid opening proof. Our construction generalizes the approach of Baum et al. by supporting a larger challenge set and removing the requirement for invertible challenge differences. As a result, the proof size scales logarithmically with $$\ell$$ ℓ , rather than linearly. Furthermore, we introduce a product proof for committed messages with shared randomness across these $$\ell$$ ℓ commitment groups. Compared to the naive approach of applying Attema’s product proof once and repeating the opening proof $$\ell -1$$ ℓ - 1 times, our method achieves significantly better communication efficiency.

Abstract Verifiable encryption enables the decryption to be taken on properly generated ciphertexts, by making the encryptor provide a zero-knowledge proof. To meet the quantum-safe application requirements, such as key escrow, Lyubashevsky et al. proposed a one-shot verifiable encryption (LN17 scheme) based on the hardness of lattice problems. In their scheme, the FSwA-type zero-knowledge proof was obtained using rejection sampling on a discrete Gaussian distribution. In this paper, we present a construction of verifiable encryption that utilizes rejection sampling on bimodal Gaussian to get the associated zero-knowledge proof. Our new construction, while exhibiting a weaker soundness property than LN17 scheme, benefits from a smaller proof size, leading to a reduced size of the verifiable ciphertext. As for the weaker soundness property, it supports some applications such as key escrow where honestly generated verifiable ciphertexts are more useful to be decrypted out in the hope of doing some further computation tasks. We provide the efficiency comparison of the new construction by instantiating it with several sets of concrete parameters.

Abstract Bootle et al. in CRYPTO 2019 proposed a zero knowledge proof for an $\mathrm{ISIS}_{m,n,q,\beta }$ instance $A\vec{s} = \vec{u} \bmod q$ with $\|\vec{s}\|_{\infty }\leq \beta $ (BLS scheme). It was implemented by transforming the instance into the form $A^{\prime }\vec{s}^{\prime } =\vec{u}\bmod q$, where the coefficients of $\vec{s}^{\prime}$ are in $\{0,1,2\}$, and proved the latter in an exact way. With the concrete parameters $m=1024,n=2048,\beta =1,q\approx 2^{32}$, their proof is of length 384.03KB. In this paper, we decrease the proof size of BLS scheme by two techniques. The first one takes effect on some special parameters. For these parameters, using the binary basic set instead of the ternary one results in a shorter proof. The second one deals with the repetition of the lower half in BLS scheme. Observing that what the lower half proves is of form $\mathbf{B}\vec{\mathbf{r}}=\vec{\mathbf{t}}$ with a short vector $\vec{\mathbf{r}}$ of polynomials, a variant of parallel repetition can be used to shorten the proof size. Combining these two techniques together, the proof size of the above-mentioned instance can be reduced to 220.01KB, only 57.3$\%$ of BLS scheme.

Abstract BORON is a lightweight substitution–permutation network cipher proposed in 2017. We reduce the number of guessed key bits by key-bridging technology and first utilize Fast Walsh Transform on BORON to minimize the time complexity. Finally, this paper gives the better key-recovery attack against block cipher BORON than previously proposed by 2 rounds: we realize a 11-round key-recovery attack on BORON-80 and 13-round key-recovery attack on BORON-128. The attacks proposed in this paper are the best attacks against BORON-80/128 to date.

Abstract This paper proposes a new method to find high-probability truncated differentials using matrix muliplication. For Markov cipher with similar round function, suppose that the transition probability matrix of round function is $\mathcal{D}$, then $\mathcal{D}^{r}$ contains all the differential probabilities of an $r$-round block cipher. To reduce the matrix dimension, we consider the word-oriented truncated differential and the truncated transition probability matrix $\mathcal{T}$. Regardless of the effect of the $S$-box, we focus on whether there is a non-zero difference on one cell instead of the value of the difference. In this case, the matrix dimension reduces significantly and we can calculate $\mathcal{T}^{r}$ using a workstation. Then all the $r$-round truncated differential probabilities can be found from $\mathcal{T}^{r}$. And the probability in $\mathcal{T}^{r}$ is the probability of the whole truncated differential hull but not a single or several truncated differential characteristics. Besides, we make a more accurate probability estimation of the truncated differential of lightweight block cipher. Combined with the truncated differential hull, we found some longer truncated differential distinguishers. And as $\mathcal{T}^{r}$ stores all the truncated differential probabilities, we can also find all the impossible truncated differentials.

Abstract Demirci–Selçuk meet-in-the-middle (DS-MITM) attack is an effective method for cryptanalysis. As far as we know, the published automatic results of DS-MITM attack are all for byte-oriented ciphers. In this article, we first propose the automatic analysis method of DS-MITM attack for bit-oriented ciphers based on constraint programming, which is integrated with key-bridging technique. Based on the automatic modeling method, we propose the first result of DS-MITM attack on SIMON, which is a family of lightweight block ciphers proposed by the National Security Agency (NSA) in 2013.

Abstract LowMC is a family of block ciphers proposed by Albrecht et al. at EUROCRYPT 2015, which is tailored specifically for FHE and MPC applications. At ToSC 2018, a difference enumeration attack was given for the cryptanalysis of low-data instances of full LowMCv2 with few applied S-boxes per round. Recently at CRYPTO 2021, an efficient algebraic technique was proposed to attack 4-round LowMC adopting a full S-box layer. Following these works, we present a new difference enumeration attack framework, which is based on our new observations on the LowMC S-box, to analyze LowMC instances with a full S-box layer. As a result, with only 3 chosen plaintexts, we can attack 4-round LowMC instances which adopt a full S-box layer with block size of 129, 192, and 255 bits, respectively. We show that all these attacks have either a lower time complexity or a higher success probability than those reported in the CRYPTO paper.

Abstract The differential-linear attack, combining the power of the two most effective techniques for symmetric-key cryptanalysis, was proposed by Langford and Hellman at CRYPTO 1994. From the exact formula for evaluating the bias of a differential-linear distinguisher (JoC 2017), to the differential-linear connectivity table technique for dealing with the dependencies in the switch between the differential and linear parts (EUROCRYPT 2019), and to the improvements in the context of cryptanalysis of ARX primitives (CRYPTO 2020, EUROCRYPT 2021), we have seen significant development of the differential-linear attack during the last four years. In this work, we further extend this framework by replacing the differential part of the attack by rotational-XOR differentials. Along the way, we establish the theoretical link between the rotational-XOR differential and linear approximations and derive the closed formula for the bias of rotational differential-linear distinguishers, completely generalizing the results on ordinary differential-linear distinguishers due to Blondeau, Leander, and Nyberg (JoC 2017) to the case of rotational differential-linear cryptanalysis. We then revisit the rotational cryptanalysis from the perspective of differential-linear cryptanalysis and generalize Morawiecki et al.’s technique for analyzing , which leads to a practical method for estimating the bias of a (rotational) differential-linear distinguisher in the special case where the output linear mask is a unit vector. Finally, we apply the rotational differential-linear technique to the cryptographic permutations involved in , , , and . This gives significant improvements over existing cryptanalytic results, or offers explanations for previous experimental distinguishers without a theoretical foundation. To confirm the validity of our analysis, all distinguishers with practical complexities are verified experimentally. Moreover, we discuss the possibility of applying the rotational differential-linear technique to S-box-based designs or keyed primitives, and propose some open problems for future research.

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.

Zero-knowledge proof for any relation amongst committed values is crucial and widely applicable in the design of high level cryptographic schemes, especially in privacy-preserving protocols. Besides quantum resistance, efficiency is what we are most concerned about, including asymptotic efficiency and concrete efficiency. Jain et al. proposed a simple string commitment scheme based on the Learning Parity with Noise (LPN) problem (JKPT12), and then designed zero-knowledge proofs for valid opening, linear relation and multiplicative relation of committed values. As a result, they got an efficient zero-knowledge proof for any circuit C, with communication complexity $\mathcal{O}(t|C|\ell \log \ell )$, where t is a security parameter measuring soundness and ℓ is the secret length of the LPN problem. In this work, we improve the concrete communication complexity by combining some commitments in JKPT12 together. The proofs of linear relation and multiplicative relation are shortened by (6α + 4)ℓ and (42α+28)ℓ respectively, where ℓ is the size of LPN secret. As a result, the communication cost of the protocol proving arbitrary relation is reduced by a constant level.

Abstract Subterranean 2.0 is a cipher suite that can be used for hashing, authenticated encryption, MAC computation, etc. It was designed by Daemen, Massolino, Mehrdad, and Rotella, and has been selected as a candidate in the second round of NIST’s lightweight cryptography standardization process. Subterranean 2.0 is a duplex-based construction and utilizes a single-round permutation in the duplex. It is the simplicity of the round function that makes it an attractive target of cryptanalysis. In this paper, we examine the single-round permutation in various phases of Subterranean 2.0 and specify three related attack scenarios that deserve further investigation: keystream biases in the keyed squeezing phase, state collisions in the keyed absorbing phase, and one-round differential analysis in the nonce-misuse setting. To facilitate cryptanalysis in the first two scenarios, we novelly propose a set of size-reduced toy versions of Subterranean 2.0: Subterranean-m. Then we make an observation for the first time on the resemblance between the non-linear layer in the round function of Subterranean 2.0 and SIMON’s round function. Inspired by the existing work on SIMON, we propose explicit formulas for computing the exact correlation of linear trails of Subterranean 2.0 and other ciphers utilizing similar non-linear operations. We then construct our models for searching trails to be used in the keystream bias evaluation and state collision attacks. Our results show that most instances of Subterranean-m are secure in the first two attack scenarios but there exist instances that are not. Further, we find a flaw in the designers’ reasoning of Subterranean 2.0’s linear bias but support the designers’ claim that there is no linear bias measurable from at most $$2^{96}$$ 2 96 data blocks. Due to the time-consuming search, the security of Subterranean 2.0 against the state collision attack in keyed modes still remains an open question. Finally, we observe that one-round differentials allow to recover state bits in the nonce-misuse setting. By proposing nested one-round differentials, we obtain a sufficient number of state bits, leading to a practical state recovery with only 20 repetitions of the nonce and 88 blocks of data. It is noted that our work does not threaten the security of Subterranean 2.0.

GIMLI is a 384-bit permutation proposed by Bernstein et al. at CHES 2017. It is designed with the goal of achieving both high security and high performance across a wide range of hardware and software platforms. Since GIMLI can be used as a building block for many cryptographic schemes, it is important to understand its concrete security. To the best of our knowledge, third party cryptanalysis of GIMLI is limited. In this paper, we identify some zero-sum distinguishers for 14-round GIMLI with the inside-out technique, which are one-round longer than the integral distinguishers presented by the designers. Although we obtain improved cryptanalysis results, these zero-sum distinguishers are far from threatening the full version of GIMLI.

An involution over finite fields is a permutation polynomial whose inverse is itself. Owing to this property, involutions over finite fields have been widely used in applications, such as cryptography and coding theory. Following the idea by Wang to characterize the involutory behavior of the generalized cyclotomic mappings, this paper gives a more concise criterion for$x^{r}h(x^{s})\in {\mathbb F} _{q}[x]$being involutions over the finite field${\mathbb F}_{q}$, where$r\geq 1$and$s\,|\, (q-1)$. By using this criterion, we propose a general method to construct involutions of the form$x^{r}h(x^{s})$over${\mathbb F}_{q}$from given involutions over some subgroups of${\mathbb F}_{q}^{*}$by solving congruent and linear equations over finite fields. Then, many classes of explicit involutions of the form$x^{r}h(x^{s})$over${\mathbb F}_{q}$are obtained.

While impossible differential attack is one of the most well-known and familiar techniques for symmetric-key cryptanalysts, its subtlety and complicacy make the construction and verification of such attacks difficult and error-prone. We introduce a new set of notations for impossible differential analysis. These notations lead to unified formulas for estimation of data complexities of ordinary impossible differential attacks and attacks employing multiple impossible differentials. We also identify an interesting point from the new formulas: in most cases, the data complexity is only related to the form of the underlying distinguisher and has nothing to do with how the differences at the beginning and the end of the distinguisher propagate in the outer rounds. We check the formulas with some examples, and the results are all matching. Since the estimation of the time complexity is flawed in some situations, in this work, we show under which condition the formula is valid and give a simple time complexity estimation for impossible differential attack which is always achievable.

Abstract Zorro is a 24‐round block cipher presented at the CHES 2013 conference. In this paper, we propose a differential fault attack on Zorro under a byte fault model, in which faults are injected in the 20th round of Zorro at arbitrary positions. With two fault injections on average, a candidate set for the key of the cipher with at most 224 elements can be efficiently obtained in a low time complexity with a probability of at least 96.29%. In this attack, the position of the fault can be easily determined by the difference of the correct and faulty ciphertexts. Copyright © 2015 John Wiley & Sons, Ltd.

Two public key cryptosystems based on the two intractable number‐theoretic problems, integer factorisation and simultaneous Diophantine approximation, were proposed in 2005 and 2009, respectively. In this study, the authors break these two cryptosystems for the recommended minimum parameters by solving the corresponding modular linear equations with small unknowns. For the first scheme, the public modulus is factorised and the secret key is recovered with the Gauss algorithm. By using the LLL basis reduction algorithm for a seven‐dimensional lattice, the public modulus in the second scheme is also factorised and the plaintext is recovered from a ciphertext. The author's attacks are efficient and verified by experiments which were done within 5s.

The original Number Theory Research Unit (NTRU) public key cryptosystem is vulnerable to multiple transmission attacks, and the designers of NTRU presented two countermeasures to prevent such attacks. In this study, the authors show that the first countermeasure is still not secure, the plaintext can be revealed by a linearisation attack technique. Moreover, they demonstrate that the first countermeasure is even not secure for broadcast attacks, a class of more general attacks than multiple transmission attacks. For the second countermeasure, they show that one special case of its padding function for the plaintext is also insecure and the original plaintext can be obtained by lattice methods.

In this paper, the cycle structure and adjacency graphs of a class of linear feedback shift registers (LFSRs) are determined. By recursively applying the D-morphism to the maximum-length LFSRs and representing the cycles by generating functions, a new family of maximum-length nonlinear feedback shift registers (NFSRs) are proposed based on the properties of these LFSRs. The number of NFSRs in the proposed family is also considered.

Two knapsack‐based public key cryptosystems were proposed recently, in which the entries of the secret knapsack sequences are composed of products of random integers and the knapsack problems have nonbinary solutions. These features make the cryptosystems to be secure against low density attacks. In this study, the authors present lattice‐based complete private key recovery attacks on these two schemes. The authors attacks firstly find short vectors related to the public key and with some orthogonality to the secret knapsack sequences and then recover some components of the private key by computing common factors of the entries of the short vectors. Especially, the authors attack can both completely recover the unique key for these two schemes. The attacks are of practical complexities and verified by experiments.

Recently, new optimal Families${\cal S}$and${\cal U}$of quaternary sequences have been presented, and the optimal binary sequence Family${\cal V}$obtained from Family${\cal S}$under Gray map has been investigated as well. The two sequence Families${\cal U}$and${\cal V}$are optimal with respect to the well-known Sidelnikov bound and Welch bound, but their exact correlation distributions are not known until now. In this paper, their exact correlation distributions are completely determined in some cases by making use of exponential sums and the theory of${\bf Z}_4$-valued quadratic forms.

In this paper, three constructions of balanced Boolean functions with optimal algebraic immunity are proposed. It is checked that, at least for small numbers of input variables, these functions have good behavior against fast algebraic attacks as well. Other cryptographic properties such as algebraic degree and nonlinearity of the constructed functions are also analyzed. Lower bounds on the nonlinearity are proved, which are similar to the best bounds obtained for known Boolean functions resisting algebraic attacks and fast algebraic attacks. Moreover, it is checked that for the numbernof variables with 5 ≤n≤ 19, the proposedn-variable Boolean functions have in fact very good nonlinearity.

This paper follows the recent work of Helleseth, Kholosha, Johansen, and Ness to study the cross correlation between an m -sequence of period 2m- 1 and the d-decimation of an m-sequence of a shorter period 2n- 1 for an even number m = 2n. Assuming that d satisfies d(2l+ 1) = 2i(mod 2n- 1) for some l > 0 and i > 0, it is proved that the cross correlation takes on either exactly three or four values depending on whether I and n are coprime or not. The distribution of the cross-correlation values is also completely determined. Our results theoretically confirm the numerical data by Ness and Helleseth. It is conjectured that there are no other decimations that give at most four-valued cross correlation apart from the ones proved here.

In this paper, two new optimal families S and U of quadriphase sequences are presented. Compared to the family A constructed by Boztas and the family D investigated by Tang respectively, the proposed families have the same optimal correlation properties and family size, but larger linear spans.

In this paper, we present two optimal binary families of sequences of length 2n-1 and 2(2n-1) for odd integer n. They are obtained as the images of proposed optimal quaternary sequences under the most significant bit and the Gray maps. The first family has 2n+1 sequences of length 2n-1 and the identical correlation distribution to that of Gold sequences and Gold-like sequences, and the second family of sequences of length 2(2n-1) has 2nsequences and the same correlation values as those of Kerdock sequences.

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so that peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the security and the anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype PT-enabled P2P network. The strengths of our design include (1) no need for a centralized trusted party or CA, (2) high scalability and security, (3) low traffic and cryptography processing overheads, and (4) man-in-middle attack resistance.

Most of the current trust models in peer-to-peer (P2P) systems are identity based, which means that in order for one peer to trust another, it needs to know the other peer's identity. Hence, there exists an inherent tradeoff between trust and anonymity. To the best of our knowledge, there is currently no P2P protocol that provides complete mutual anonymity as well as authentication and trust management. We propose a zero-knowledge authentication scheme called pseudo trust (PT), where each peer, instead of using its real identity, generates an unforgeable and verifiable pseudonym using a one-way hash function. A novel authentication scheme based on zero-knowledge proof is designed so peers can be authenticated without leaking any sensitive information. With the help of PT, most existing identity-based trust management schemes become applicable in mutual anonymous P2P systems. We analyze the levels of security and anonymity in PT, and evaluate its performance using trace-driven simulations and a prototype implementation. The strengths of pseudo trust include the lack of need for a centralized trusted party or CA, high scalability and security, low traffic and cryptography processing overheads, and man-in-middle attack resistance. We aim for the pseudo trust design to be included in the P2P trust and anonymity context.

In this paper, we construct two new families S and U of optimal quadriphase sequences. Compared to the family A constructed by Boztas et al and family D investigated by Tang et al respectively, the proposed families have the same optimal correlation properties and family size, but larger linear spans.

The objective of private authentication for radio frequency identification (RFID) systems is to allow valid readers to explicitly authenticate their dominated tags without leaking tags' private information. To achieve this goal, RFID tags issue encrypted authentication messages to the RFID reader, and the reader searches the key space to locate the tags. Due to the lack of efficient key updating algorithms, previous schemes are vulnerable to many active attacks, especially the compromising attack. In this paper, we propose a strong and lightweight RFID private authentication protocol, SPA. By designing a novel key updating method, we achieve the forward secrecy in SPA with an efficient key search algorithm. We also show that, compared with existing designs, SPA is able to effectively defend against both passive and active attacks, including compromising attacks. Through prototype implementation, we observe that SPA is practical and scalable in current RFID infrastructures