International Association
for Cryptologic Research

ChaCha has been one of the prominent ARX designs of the last few years because of its use in several systems. The cryptanalysis of ChaCha involves a differential attack which exploits the idea of Probabilistic Neutral Bits (PNBs). For a long period, the single-bit distinguisher in this differential attack was found up to 3 rounds. At Crypto $2020$, Beierle et. al. introduced for the first time single bit distinguishers for $3.5$ rounds, which contributed significantly in regaining the flow of research work in this direction. This discovery became the primary factor behind the huge improvement in the key recovery attack complexity in that work. This was followed by another work at Eurocrypt 2021, where a single bit distinguisher of $3.5$-th round helped to produce a 7-round distinguisher of ChaCha and a further improvement in key recovery.

In the first part of this paper, we provide the theoretical framework for the distinguisher given by Beierle et. al. We mathematically derive the observed differential correlation for the particular position where the output difference is observed at $3.5$ rounds. Also, Beierle et. al. mentioned the issue of the availability of proper IVs to produce such distinguishers, and pointed out that not all keys have such IVs available. Here we provide a theoretical insight of this issue.

Next we revisit the work of Coutinho et. al. (Eurocrypt 2021). Using Differential-Linear attacks against ChaCha, they claimed distinguisher and key recovery with complexities $2^{218}$ and $2^{228.51}$ respectively. We show that the differential correlation for $3.5$ rounds is much smaller than the claim of Coutinho et. al. This makes the attack complexities much higher than their claim.

Recently, artificial intelligence-based cryptanalysis techniques have been researched. In this paper, we find the key of the Caesar cipher, which is a classical cipher, by using a quantum machine learning algorithm that learns by parameterized quantum circuit instead of a classical neural network. In the case of 4-bit plaintext and key, results could not be obtained due to the limitations of the cloud environment. But in the case of 2-bit plaintext and key, an accuracy of 1.0 was achieved, and in the case of 3-bit plaintext and key, an accuracy of 0.84 was achieved. In addition, as a result of cryptanalysis for a 2-bit dataset on IBM's real quantum processor, a classification accuracy of 0.93 was achieved. In the future, we will research a qubit reduction method for cryptanalysis of longer-length plaintext and key, and a technique for maintaining accuracy in real quantum hardware.

As Internet of Things (IoT) thriving over the whole world, more and more IoT devices and IoT-based protocols have been designed and proposed in order to meet people's needs. Among those protocols, message queueing telemetry transport (MQTT) is one of the most emerging and promising protocol, which provides many-to-many message transmission based on the ``publish/subscribe'' mechanism. It has been widely used in industries such as the energy industry, chemical engineering, self-driving, etc. While transporting important messages, MQTT specification recommends the use of TLS protocol. However, computation cost of TLS is too heavy. Since topics in a broker are stored with a hierarchical structure, In this manuscript, we propose a novel data protection protocol for MQTT from hierarchical ID-based encryption. Our protocol adopts the intrinsic hierarchical structures of MQTT, and achieves constant-size keys, i.e. independent of the depth in hierarchical structures.

With the rapid advancement of cloud computing, users upload their files to the cloud server so that any user can access it remotely. To assure the data security, the data owner, typically, encrypts the data before outsourcing them to the cloud server. In addition, an encryption mechanism needs to enable the consumers to perform efficient searches of such encrypted data in the cloud storages through keywords, i.e. searchable encryption. However, most of searchable encryption is improper due to several limitations, such as the requirement of an on-line fully trusted third party, poor efficiency, high-overhead in user revocation, support of a single keyword search, etc. To mitigate such limitations, an attribute-based encryption scheme with fine-grained multi-keyword search is proposed. The new scheme supports the user revocation. In addition, the length of the ciphertext as well as the secret key do not grow linearly under the influence of the size of attribute set. The performance of the proposed scheme is better as compared to other related schemes. Hence, one can easily adopt the proposed scheme for the real life applications due to its flexibility in terms of its features, security and efficiency.

Schnorr's signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major attack vector in practice. Sources of randomness in deployments are frequently either unreliable, or require state continuity, i.e. reliable fresh state resilient to rollbacks. State continuity is a notoriously difficult guarantee to achieve in practice, due to system crashes caused by software errors, malicious actors, or power supply interruptions (Parno et al., S&P '11). This is a non-issue for Schnorr variants such as EdDSA, which is specified to derive nonces deterministically as a function of the message and the secret key. However, it is challenging to translate these benefits to the threshold setting, specifically to construct a threshold Schnorr scheme where signing neither requires parties to consume fresh randomness nor update long-term secret state.

In this work, we construct a dishonest majority threshold Schnorr protocol that enables such stateless deterministic nonce derivation using standardized block ciphers. Our core technical ingredients are new tools for the zero-knowledge from garbled circuits (ZKGC) paradigm to aid in verifying correct nonce derivation: - A mechanism based on UC Commitments that allows a prover to commit once to a witness, and prove an unbounded number of statements online with only cheap symmetric key operations. - A garbling gadget to translate intermediate garbled circuit wire labels to arithmetic encodings.

Our scheme prioritizes computation cost, with each proof requiring only a small constant number of exponentiations.

A ring signature allows a party to sign messages anonymously on behalf of a group, which is called ring. Traceable ring signatures are a variant of ring signatures that limits the anonymity guarantees, enforcing that a member can sign anonymously at most one message per tag. Namely, if a party signs two different messages for the same tag, it will be de-anomymized. This property is very useful in decentralized platforms to allow members to anonymously endorse statements in a controlled manner. In this work we introduce one-time traceable ring signatures, where a member can sign anonymously only one message. This natural variant suffices in many applications for which traceable ring signatures are useful, and enables us to design a scheme that only requires a few hash evaluations and outperforms existing (non one-time) schemes.

Our one-time traceable ring signature scheme presents many advantages: it is fast, with a signing time of less than 1 second for a ring of $2^{10}$ signers (and much less for smaller rings); it is {\em post-quantum resistant}, as it only requires hash evaluations; it is extremely simple, as it requires only a black-box access to a generic hash function (modeled as a random oracle) and no other cryptographic operation is involved. From a theoretical standpoint our scheme is also the first anonymous signature scheme based on a black-box access to a symmetric-key primitive. All existing anonymous signatures are either based on specific hardness assumptions (e.g., LWE, SIS, etc.) or use the underlying symmetric-key primitive in a non-black-box way, i.e., they leverage the circuit representation of the primitive.

Side-channel analysis (SCA) attacks pose a major threat to embedded systems due to their ease of accessibility. Realising SCA resilient cryptographic algorithms on embedded systems under tight intrinsic constraints, such as low area cost, limited computational ability, etc., is extremely challenging and often not possible. We propose a seamless and effective approach to realise a generic countermeasure against SCA attacks. XDIVINSA, an extended diversifying instruction agent, is introduced to realise the countermeasure at the microarchitecture level based on the combining concept of diversified instruction set extension (ISE) and hardware diversification. XDIVINSA is developed as a lightweight co-processor that is tightly coupled with a RISC-V processor. The proposed method can be applied to various algorithms without the need for software developers to undertake substantial design efforts hardening their implementations against SCA. XDIVINSA has been implemented on the SASEBO G-III board which hosts a Kintex-7 XC7K160T FPGA device for SCA mitigation evaluation. Experimental results based on non-specific t-statistic tests show that our solution can achieve leakage mitigation on the power side channel of different cryptographic kernels, i.e., Speck, ChaCha20, AES, and RSA with an acceptable performance overhead compared to existing countermeasures.

In this report we analyse and compare the complexity of solving the Bounded Distance Decoding problem in two families for discrete logarithm lattices. Our algorithm uses the internal structure of the lattice to decode an error close to Minkowski’s bound efficiently. This procedure can be used as a decryption algorithm of an encryption scheme, where the internal structure of the lattice serves as a secret key. In addition, one of these lattices was used in [1] to construct a family of one way functions. We present cryptanalysis of the mentioned scheme and we prove that the stated size of the keys is insufficient for a required security level.

The digital signatures that have been proposed so far in the setting of the Supersingular Isogeny Diffie-Hellman scheme (SIDH) were obtained by applying the Fiat-Shamir transform - and a quantum-resistant analogous, the Unruh transform - to an interactive identification protocol introduced by De Feo, Jao and Pl$\hat{\mbox{u}}$t. The security of the resulting schemes is therefore deduced from that of the base identification protocol. In this paper, we revisit the proofs that have appeared in the literature for the special soundness property of the above mentioned SIDH-based identification protocol. All such proofs consider the same extraction algorithm, which is claimed to always extract a valid witness for a statement $\statement$ when given two valid transcripts, with the same commitment and different challenges, relative to $\statement$ itself. We show that this is not always the case, with some explicit counterexamples. The general argument fails due to some special cycles in supersingular isogeny graphs. The existence of these special cycles not only enjoys a theoretical interest, but is generally relevant for the Isogeny-based Cryptography. We provide some theoretical results on their presence in supersingular isogeny graphs, and discuss the relevance of the obtained results for some known cryptographic applications.

In the last decades, several signcryption schemes have been proposed for different privacy-enhancing purposes. In this paper, we propose a new privacy-enhancing group signcryption scheme that provides: unforgeability, confidentiality, ciphertext and sender anonymity, traceability, unlinkability, exculpability, coalition-resistance, and unforgeable tracing verification. It is important to notice that the proposed scheme allows a signer to anonymously signcryt a message on the group's behalf (i.e., sender's anonymity). Security analysis of the scheme is also provided. Our proposal is proven to be strongly existentially unforgeable under an adaptive chosen message attack, indistinguishable under an adaptive chosen ciphertext attack, and to provide ciphertext anonymity under an adaptive chosen ciphertext attack. Furthermore, the scheme is extended to work in a multi-receiver scenario, where an authorized group of receivers is able to unsigncrypt the ciphertext. The experimental results show that our scheme is efficient even on computationally restricted devices and can be therefore used in many IoT applications. Signcrypt protocol on smart cards takes less than 1~s (including communication overhead). The time of Unsigncrypt protocol on current ARM devices is negligible (less than 40 ms).

Binary search is one of the most popular algorithms in computer science. Realizing it in the context of secure multiparty computation which demands data-oblivious execution, however, is extremely non-trivial. It has been previously implemented only using oblivious RAM (ORAM) for secure computation and in this work we initiate the study of this topic using conventional secure computation techniques based on secret sharing. We develop a suite of protocols with different properties and of different structure for searching a private dataset of $m$ elements by a private numeric key. Our protocols result in $O(m)$ and $O(\sqrt{m})$ communication using only standard and readily available operations based on secret sharing. We further extend our protocols to support write operations, namely, binary search that obliviously updates the selected element, and realize two variants: updating non-key fields and updating the key field. Our implementation results indicate that even after applying known and our own optimizations to the fastest ORAM constructions, our solutions are faster than optimized ORAM schemes for datasets of up to $2^{30}$ elements and by up to two orders of magnitude. We hope that this work will prompt further interest in seeking efficient realizations of this important problem.

This work presents an approach for compressing regular hash-based signatures using STARKs (Ben-Sasson et. al.'18). We focus on constructing a hash-based t-of-n threshold signature scheme, as well as an aggregate signature scheme. In both constructions, an aggregator collects individual one-time hash-based signatures and outputs a STARK proof attesting that the signatures are valid and meet the required thresholds. This proof then serves the role of the aggregate or threshold signature. We demonstrate the concrete performance of such constructions, having implemented the algebraic intermediate representations (AIR) for them, along with an experimental evaluation over our implementation of the STARK protocol.

We find that, even when we aggregate thousands of signatures, the final aggregated size ranges between 100KB and 200KB, making our schemes attractive when there exist at least 50 one-or-few-times hash-based signatures. We also observe that for STARK-based signature aggregation, the size of individual signatures is less important than the number of hash invocations and the complexity of the signature verification algorithm. This implies that simple hash-based signature variants (e.g. Lamport, HORST, BPQS) are well-suited for aggregation, as their large individual signatures serve only as witnesses to the ZKP circuit and are not needed for aggregate signature verification.

Our constructions are directly applicable as scalable solutions for post-quantum secure blockchains which typically employ blocks of hundreds or thousands of signed transactions. Moreover, stateful hash-based one-or-few-times signatures are already used in some PQ-ready blockchains, as address reuse is typically discouraged for privacy reasons.

In this paper, a method for searching correlations between the binary stream of LFSR and the keystream of SNOW-V and SNOW-Vi is presented based on the techniques of composite function. With the aid of the linear relationship between the four taps of LFSR inputting to FSM at three consecutive clocks, we present an automatic search model based on the SAT/SMT technique and search out a binary linear approximation with a correlation 2^{-49.54}. Applying such approximation, we provide a correlation attack on SNOW-V with an expected time complexity 2^{248.81}, a memory complexity 2^{240} and 2^{240} keystream words generated by the same key and IV. For SNOW-Vi, we provide a binary linear approximation with the same correlation and mount a correlation attack with the same complexity as that of SNOW-V. The results indicate that neither of SNOW-V and SNOW-Vi can guarantee the 256-bit security level if the design constraint that the maximum of keystream length for a single pair of key and IV is less than 2^{64} is ignored.

At PQCrypto 2021, Smith-Tone proposed a new modifier, called ``Q'', to construct a fast multivariate signature scheme from a known scheme. In the present paper, we propose an idea to weaken the security of this modifier.

There have been several works on solving an under-defined system of multivariate quadratic equations over a finite field, e.g. Kipnis et al. (Eurocrypt'98), Courtois et al. (PKC'02), Tomae-Wolf (PKC'12), Miura et al. (PQC'13), Cheng et al. (PQC'14) and Furue et al. (PQC'21). This paper presents two minor improvements of Furue's aproach.

In 2019, Tao proposed a new variant of UOV with small keys, called Hufu-UOV. This paper studies its security.

This paper introduces Brakedown, the first built system that provides linear-time SNARKs for NP, meaning the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. Brakedown’s prover is faster, both concretely and asymptotically, than prior SNARK implementations. Brakedown does not require a trusted setup and is plausibly post-quantum secure. Furthermore, it is compatible with arbitrary finite fields of sufficient size; this property is new amongst implemented arguments with sublinear proof sizes.

To design Brakedown, we observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 2020) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan (CRYPTO 2020), yields linear-time IOPs and SNARKs for R1CS (a similar theoretical result was previously established by BCG, but our approach is conceptually simpler, and crucial for achieving high-speed SNARKs). A core ingredient in the polynomial commitment scheme that we distill from BCG is a linear-time encodable code. Existing constructions of such codes are believed to be impractical. Nonetheless, we design and engineer a new one that is practical in our context.

We also implement a variant of Brakedown that uses Reed-Solomon codes instead of our linear-time encodable codes; we refer to this variant as Shockwave. Shockwave is not a linear-time SNARK, but it provides shorter proofs and lower verification times than Brakedown (it also provides a faster prover than prior plausibly post-quantum SNARKs).

As a modest additional contribution, we observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time from $O(\sqrt{N})$ to $polylog(N)$---while maintaining a linear-time prover---by outsourcing the verifier’s work via one layer of proof composition with an existing zkSNARK as the "outer" proof system.

At ITCS 2010, Dziembowski, Pietrzak and Wichs introduced Non-malleable Codes (NMCs). Non-malleability is one of the strongest and most challenging notions of security considered in cryptography and protects against tampering attacks. In the context of coding schemes, non-malleability requires that it be infeasible to tamper the codeword of a message into the codeword of a related message. A natural and well-studied model of tampering is the 2-split-state model where the codeword consists of two independently tamperable states. As with standard error-correcting codes, it is of great importance to build codes with high rates. Cheraghchi and Guruswami (ITCS 2014) showed that one cannot obtain NMCs in the 2-split state model with rate better than 1/2. Since its inception, this area has witnessed huge strides leading to the construction of a constant-rate NMC in the 2-split state model due to Aggarwal and Obremski (FOCS 2020). However, the rate of this construction -- roughly 1/1,500,000 -- is nowhere close to the best achievable rate of 1/2! In this work, we dramatically improve this status quo by building a rate booster that converts any augmented non-malleable code into an augmented non-malleable code with a rate of 1/3. Using similar, but simpler techniques we also obtain rate boosters that convert any unbalanced (with sources of unequal length) non-malleable 2-source extractor into an unbalanced non-malleable 2-source extractor with rate 1/2. The beauty of our construction lies in its simplicity. In particular, if we apply our rate booster to the non-malleable code construction by Aggarwal, Dodis and Lovett (STOC 2014), then all we need is one instance of the inner-product extractor, one instance of a seeded extractor, and an affine-evasive function for the construction to work.

Multiplicative complexity is a relevant complexity measure for many advanced cryptographic protocols such as multi-party computation, fully homomorphic encryption, and zero-knowledge proofs, where processing AND gates is more expensive than processing XOR gates. For Boolean functions, multiplicative complexity is defined as the minimum number of AND gates that are sufficient to implement a function with a circuit over the basis (AND, XOR, NOT). In this paper, we study the multiplicative complexity of cubic Boolean functions. We propose a method to implement a cubic Boolean function with a small number of AND gates and provide upper bounds on the multiplicative complexity that are better than the known generic bounds.

The increasing adoption of machine learning inference in applications has led to a corresponding increase in concerns surrounding the privacy guarantees offered by existing mechanisms for inference. Such concerns have motivated the construction of efficient secure inference protocols that allow parties to perform inference without revealing their sensitive information. Recently, there has been a proliferation of such proposals, rapidly improving efficiency. However, most of these protocols assume that the client is semi-honest, that is, the client does not deviate from the protocol; yet in practice, clients are many, have varying incentives, and can behave arbitrarily. To demonstrate that a malicious client can completely break the security of semi-honest protocols, we first develop a new model-extraction attack against many state-of-the-art secure inference protocols. Our attack enables a malicious client to learn model weights with 22x-312x fewer queries than the best black-box model-extraction attack and scales to much deeper networks.

Motivated by the severity of our attack, we design and implement MUSE, an efficient two-party secure inference protocol resilient to malicious clients. MUSE introduces a novel cryptographic protocol for conditional disclosure of secrets to switch between authenticated additive secret shares and garbled circuit labels, and an improved Beaver's triple generation procedure which is 8x-12.5x faster than existing techniques.

These protocols allow MUSE to push a majority of its cryptographic overhead into a preprocessing phase: compared to the equivalent semi-honest protocol (which is close to state-of-the-art), MUSE's online phase is only 1.7x-2.2x slower and uses 1.4x more communication. Overall, MUSE is 13.4x-21x faster and uses 2x-3.6x less communication than existing secure inference protocols which defend against malicious clients.