International Association
for Cryptologic Research

A Leakage Resilient Secret Sharing (LRSS) is a secure secret sharing scheme, even when the adversary obtains some (bounded) leakage on honest shares. Ideally, such schemes must be secure against adaptive and joint leakage queries - i.e., the adversary can make a sequence of adaptive leakage queries where each query can be a joint function of many of the shares. The most important parameters of interest are the rate (= $\frac{|secret|}{|longest share|}$) and the leakage rate (ratio of the total allowable leakage from a single leakage query to the size of a share). None of the prior works tolerating such adaptive and joint leakage could attain a constant rate and constant leakage rate, even for the threshold access structure. An LRSS is non-malleable (LRNMSS) when an adversary cannot tamper shares in a way that the reconstructed secret is related to the original secret. Similar to LRSSs, none of the prior LRNMSS schemes in the information theoretic setting could attain a constant rate, even for the threshold access structure.

In this work, we provide the first constant rate LRSS (for the general access structure) and LRNMSS (for the threshold access structure) schemes that tolerate such joint and adaptive leakage in the information-theoretic setting. We show how to make use of our constructions to also provide constant rate constructions of leakage-resilient (and non-malleable) secure message transmission.

We obtain our results by introducing a novel object called Adaptive Extractors. Adaptive extractors can be seen as a generalization of the notion of exposure-resilient extractors (Zimand, CCC 2006). Such extractors provide security guarantees even when an adversary obtains leakage on the source of the extractor after observing the extractor output. We make a compelling case for the study of such extractors by demonstrating their critical use for obtaining adaptive leakage and believe that such an object will be of independent interest.

In this paper, various quantitative information-theoretic security reductions which correlate statistical difference between two probability distributions with security level’s gap between two cryptographic schemes are proposed. Security is the most important prerequisite for cryptographic primitives. In general, there are two kinds of security; one is computational security, and the other is information-theoretic security. We focus on latter one in this paper, especially the view point of bit security which is a convenient notion to indicate the quantitative security level. We propose tighter and more generalized version of information-theoretic security reductions than those of the previous works [1,2]. More specifically, we obtain about 2.5-bit tighter security reduction than that in previous work [2], and we devise a further generalized version of security reduction in the previous work [1] by relaxing the constraint on the upper bound of the information-theoretic measure, that is, λ-efficient. Through this work, we propose the methodology to estimate the affects on security level when κ-bit secure original scheme is implemented on p-bit precision system. (Here, p can be set to any value as long as certain condition is satisfied.) In the previous work [1], p was fixed as κ/2, but our result is generalized to make it possible to security level κ and precision p variate independently. Moreover, we provide diverse types of security reduction formulas for the five kinds of information-theoretic measures. We are expecting that our results could provide an information-theoretic guideline for how much the two identical cryptographic schemes (i.e., the only difference is probability distribution) may show the difference in their security level when extracting their randomness from two different probability distributions. Especially, our results can be used to obtain the quantitative estimation of how much the statistical difference between the ideal distribution and the real distribution affects the security level.

We present a signature scheme for Hamming metric random linear codes via the Schnorr-Lyubashevsky framework that employs the rejection sampling on appropriate probability distributions instead of using trapdoors. Such an approach has been widely believed to be more challenging for linear codes as compared to lattices with Gaussian distributions. We prove that our signature scheme achieves EUF-CMA security under the assumption of the decoding one out of many problem or achieves strong EUF-CMA security under the assumption of the codeword finding problem under relaxed parameters. We provide an instantiation of the signature scheme based on Ring-LPN instances as well as quasi-cyclic codes and present some concrete parameters. In addition, a proof of concept implementation of the scheme is provided. We compare our scheme with previous unsuccessful similar attempts and provide a rigorous security analysis of our scheme.

Our construction primarily relies on an efficient rejection sampling lemma for binary linear codes with respect to suitably defined variants of the binomial distribution. Essentially, the rejection sampling lemma indicates that adding a small weight vector to a large weight vector has no significant effect on the distribution of the large weight vector. Concretely, we prove that if the large weight is at least the square of the small weight and the large weight vector admits binomial distribution, the sum distribution of the two vectors can be efficiently adjusted to a binomial distribution via the rejection step and independent from the small weight vector. As a result, our scheme outputs a signature distribution that is independent of the secret key.

Compared to two existing code based signature schemes, namely Durandal and Wave, the security of our scheme is reduced to full-fledged hard coding problems i.e., codeword finding problem and syndrome decoding problem for random linear codes. By contrast, the security of the Durandal and Wave schemes is reduced to newly introduced product spaces subspaces indistinguishability problem and the indistinguishability of generalized $(U,U+V)$ codes problem, respectively. We believe that building our scheme upon the more mature hard coding problems provides stronger confidence to the security of our signature scheme.

Adversaries in cryptography have traditionally been modeled as either semi-honest or malicious. Over the years, however, several lines of work have investigated the design of cryptographic protocols against rational adversaries. The most well-known example are covert adversaries in secure computation (Aumann & Lindell, TCC '07) which are adversaries that wish to deviate from the protocol but without being detected. To protect against such adversaries, protocols secure in the covert model guarantee that deviations are detected with probability at least $\varepsilon$ which is known as the deterrence factor.

In this work, we initiate the study of contracts in cryptographic protocol design. We show how to design, use and analyze contracts between parties for the purpose of incentivizing honest behavior from rational adversaries. We refer to such contracts as adversarial level agreements (ALA). The framework we propose can result in more efficient protocols and can enforce deterrence in covert protocols; meaning that one can guarantee that a given deterrence factor will deter the adversary instead of assuming it.

We show how to apply our framework to two-party protocols, including secure two-party computation (2PC) and proofs of storage (PoS). In the 2PC case, we integrate ALAs to publicly-verifiable covert protocols and show, through a game-theoretic analysis, how to set the parameters of the ALA to guarantee honest behavior. We do the same in the setting of PoS which are two-party protocols that allow a client to efficiently verify the integrity of a file stored in the cloud.

Private information retrieval (PIR) lets a client retrieve an entry from a database held by a server, without the server learning which entry was retrieved. Here we study a weaker variant that we call *random-index PIR* (RPIR). It differs from standard PIR in that the retrieved index is an output rather than an input of the protocol, and it is chosen at random.

Our motivation for studying RPIR comes from a recent work of Benhamouda et al. (TCC'20) about maintaining secret values on public blockchains. Their solution involves choosing a small anonymous committee from among a large universe, and here we show that RPIR can be used for that purpose.

The RPIR client must be implemented via secure MPC for this use case, stressing the need to make it as efficient as can be. Combined with recent techniques for secure-MPC with stateless parties, our results yield a new secrets-on-blockchain construction (and more generally large-scale MPC). Our solution tolerates any fraction $f \lneq 1/2$ of corrupted parties, solving an open problem left from the work of Benhamouda et al.

Considering RPIR as a primitive, we show that it is in fact equivalent to PIR when there are no restrictions on the number of communication rounds. On the other hand, RPIR can be implemented in a ``noninteractive'' setting, which is clearly impossible for PIR. We also study batch RPIR, where multiple indexes are retrieved at once. Specifically we consider a weaker security guarantee than full RPIR, which is still good enough for our motivating application. We show that this weaker variant can be realized more efficiently than standard PIR or RPIR, and we discuss one protocol in particular that may be attractive for practical implementations.

We propose a new doubly efficient interactive proof protocol for general arithmetic circuits. The protocol generalizes the doubly efficient interactive proof for layered circuits proposed by Goldwasser, Kalai and Rothblum to arbitrary circuits while preserving the optimal prover complexity that is strictly linear to the size of the circuits. The proof size remains succinct for low depth circuits and the verifier time is sublinear for structured circuits. We then construct a new zero knowledge argument scheme for general arithmetic circuits using our new interactive proof protocol together with polynomial commitments.

Not only does our new protocol achieve optimal prover complexity asymptotically, but it is also efficient in practice. Our experiments show that it only takes 1 second to generate the proof for a circuit with 600,000 gates, which is 7 times faster than the original interactive proof protocol on the corresponding layered circuit. The proof size is 229 kilobytes and the verifier time is 0.56 second. Our implementation can take general arithmetic circuits generated by existing tools directly, without transforming them to layered circuits with high overhead on the size of the circuits.

We show that noisy leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to a small statistical simulation error and a slight loss in the leakage parameter. The latter holds true in particular for one of the most used noisy-leakage models, where the noisiness is measured using the conditional average min-entropy (Naor and Segev, CRYPTO'09 and SICOMP'12).

Our reductions between noisy and bounded leakage are achieved in two steps. First, we put forward a new leakage model (dubbed the dense leakage model) and prove that dense leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to small statistical distance. Second, we show that the most common noisy-leakage models fall within the class of dense leakage, with good parameters. We also provide a complete picture of the relationships between different noisy-leakage models, and prove lower bounds showing that our reductions are nearly optimal.

Our result finds applications to leakage-resilient cryptography, where we are often able to lift security in the presence of bounded leakage to security in the presence of noisy leakage, both in the information-theoretic and in the computational setting. Additionally, we show how to use lower bounds in communication complexity to prove that bounded-collusion protocols (Kumar, Meka, and Sahai, FOCS'19) for certain functions do not only require long transcripts, but also necessarily need to reveal enough information about the inputs.

We introduce a new m-entwined ROS problem that tweaks a random inhomogeneities in an overdetermined solvable system of linear equations (ROS) problem in a scalar field using an associated group. We prove hardness of the 2-entwined ROS-like problem in AGM plus ROM, assuming DLOG hardness in the associated group.

Assuming AGM plus ROM plus KOSK and OMDL, we then prove security for a two-round trip Schnorr multi-signature protocol DWMS that creates its witness aka nonce by delinearizing two pre-witnesses supplied by each signer.

At present, DWMS and MuSig-DN are the only known provably secure two-round Schnorr multi-signatures, or equivalently threshold Schnorr signatures.

This paper analyses security of concrete instantiations of EdDSA by identifying exploitable inconsistencies between standardization recommendations and Ed25519 implementations. We mainly focus on current ambiguity regarding signature verification equations, binding and malleability guarantees, and incompatibilities between randomized batch and single verification. We give a formulation of Ed25519 signature scheme that achieves the highest level of security, explaining how each step of the algorithm links with the formal security properties. We develop optimizations to allow for more efficient secure implementations. Finally, we designed a set of edge-case test-vectors and run them by some of the most popular Ed25519 libraries. The results allowed to understand the security level of those implementations and showed that most libraries do not comply with the latest standardization recommendations. The methodology allows to test compatibility of different Ed25519 implementations which is of practical importance for consensus-driven applications.

The unbalanced oil and vinegar signature scheme (UOV) is a multivariate signature scheme that has essentially not been broken for over 20 years. However, it requires the use of a large public key, so various methods have been proposed to reduce its size. In this paper, we propose a new variant of UOV with the public key represented by block matrices whose components are represented as an element of a quotient ring. We discuss how the irreducibility of the polynomial used to generate the quotient ring affects the security of our proposed scheme. Furthermore, we propose parameters for our proposed scheme and discuss their security against currently known and possible attacks. We show that our proposed scheme can reduce the public key size without significantly increasing the signature size compared with other UOV variants. For example, the public key size of our proposed scheme is 66.7 KB for NIST's Post-Quantum Cryptography Project (security level 3), while that of cyclic Rainbow is 252.3 KB, where Rainbow is a variant of UOV and one of the third round finalists of NIST PQC project.

In this paper, we reevaluate the security of GIFT against differential cryptanalysis under both single-key scenario and related-key scenario. Firstly, we apply Matsui's algorithm to search related-key differential trails of GIFT. We add three constraints to limit the search space and search the optimal related-key differential trails on the limited search space. We obtain related-key differential trails of GIFT-64/128 for up to 15/14 rounds, which are the best results on related-key differential trails of GIFT so far. Secondly, we propose an automatic algorithm to increase the probability of the related-key boomerang distinguisher of GIFT by searching the clustering of the related-key differential trails utilized in the boomerang distinguisher. We find a 20-round related-key boomerang distinguisher of GIFT-64 with probability 2^-58.557. The 25-round related-key rectangle attack on GIFT-64 is constructed based on it. This is the longest attack on GIFT-64. We also find a 19-round related-key boomerang distinguisher of GIFT-128 with probability 2^-109.626. We propose a 23-round related-key rectangle attack on GIFT-128 utilizing the 19-round distinguisher, which is the longest related-key attack on GIFT-128. The 24-round related-key rectangle attack on GIFT-64 and 22-round related-key boomerang attack on GIFT-128 are also presented. Thirdly, we search the clustering of the single-key differential trails. We increase the probability of a 20-round single-key differential distinguisher of GIFT-128 from 2^-121.415 to 2^-120.245. The time complexity of the 26-round differential attack on GIFT-128 is improved from 2^124:415 to 2^123:245.

Differential power analysis (DPA) is a form of side-channel analysis (SCA) that performs statistical analysis on the power traces of cryptographic computations. DPA is applicable to many cryptographic primitives, including block ciphers, stream ciphers and even hash-based message authentication code (HMAC). At COSADE 2017, Dobraunig~et~al. presented a DPA on the fresh re-keying scheme Keymill to extract the bit relations of neighbouring bits in its shift registers, reducing the internal state guessing space from 128 to 4 bits. In this work, we generalise their methodology and combine with differential analysis, we called it differential analysis aided power attack (DAPA), to uncover more bit relations and take into account the linear or non-linear functions that feedback to the shift registers (i.e. LFSRs or NLFSRs). Next, we apply our DAPA on LR-Keymill, the improved version of Keymill designed to resist the aforementioned DPA, and breaks its 67.9-bit security claim with a 4-bit internal state guessing. We experimentally verified our analysis. In addition, we improve the previous DPA on Keymill by halving the amount of data resources needed for the attack. We also applied our DAPA to Trivium, a hardware-oriented stream cipher from the eSTREAM portfolio and reduces the key guessing space from 80 to 14 bits.

We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new one-round, high soundness, interactive identification protocol. Targeting the post-quantum NIST-1 level of security, our implementation results in signatures of $204$ bytes, secret keys of $16$ bytes and public keys of $64$ bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.

While the soundness of the identification protocol follows from classical assumptions, the zero-knowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zero-knowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zero-knowledge.

Authenticated dictionaries (ADs) are a key building block of many cryptographic systems, such as transparency logs, distributed file systems and cryptocurrencies. In this paper, we propose a new notion of cross-incremental proof (dis)aggregation for authenticated dictionaries, which enables aggregating multiple proofs with respect to different dictionaries into a single, succinct proof. Importantly, this aggregation can be done incrementally and can be later reversed via disaggregation. We give an efficient authenticated dictionary construction from hidden-order groups that achieves cross-incremental (dis)aggregation. Our construction also supports updating digests, updating (cross-)aggregated proofs and precomputing all proofs efficiently. This makes it ideal for stateless validation in cryptocurrencies with smart contracts. As an additional contribution, we give a second authenticated dictionary construction, which can be used in more malicious settings where dictionary digests are adversarially-generated, but features only “one-hop” proof aggregation (with respect to the same digest). We add support for append-only proofs to this construction, which gives us an append-only authenticated dictionary (AAD) that can be used for transparency logs and, unlike previous AAD constructions, supports updating and aggregating proofs.

The hardness of Entropic LWE has been studied in a number of works. However, there is not work study the hardness of algebraically structured LWE with entropic secrets. In this work, we conduct a comprehensive study on establishing hardness reductions for Entropic Module-LWE and Entropic Ring-LWE. We show an entropy bound that guarantees the security of arbitrary Entropic Module-LWE and Entropic Ring-LWE, these are the first results on the hardness of algebraically structured LWE with entropic secrets. One of our central techniques is a new generalized leftover hash lemma over ring and a new decomposition theorem for continuous Gaussian distribution on KR, which might be of independent interests.

We present the first rigorous dynamic analysis of BKZ, the most widely used lattice reduction algorithm besides LLL: previous analyses were either heuristic or only applied to variants of BKZ. Namely, we provide guarantees on the quality of the current lattice basis during execution. Our analysis extends to a generic BKZ algorithm where the SVP-oracle is replaced by an approximate oracle and/or the basis update is not necessarily performed by LLL. Interestingly, it also provides quantitative improvements, such as better and simpler bounds for both the output quality and the running time. As an application, we observe that in certain approximation regimes, it is more efficient to use BKZ with an approximate rather than exact SVP-oracle.

The round complexity of Byzantine Broadcast (BB) has been a central question in distributed systems and cryptography. In the honest majority setting, expected constant round protocols have been known for decades even in the presence of a strongly adaptive adversary. In the corrupt majority setting, however, no protocol with sublinear round complexity is known, even when the adversary is allowed to {\it strongly adaptively} corrupt only 51\% of the players, and even under reasonable setup or cryptographic assumptions. Recall that a strongly adaptive adversary can examine what original message an honest player would have wanted to send in some round, adaptively corrupt the player in the same round and make it send a completely different message instead.

In this paper, we are the first to construct a BB protocol with sublinear round complexity in the corrupt majority setting. Specifically, assuming the existence of time-lock puzzles with suitable hardness parameters and that the decisional linear assumption holds in suitable bilinear groups}, we show how to achieve BB in $(\frac{n}{n-f})^2 \cdot \poly\log \lambda$ rounds with $1-\negl(\lambda)$ probability, where $n$ denotes the total number of players, $f$ denotes the maximum number of corrupt players, and $\lambda$ is the security parameter. Our protocol completes in polylogarithmically many rounds even when 99\% of the players can be corrupt.

In this paper, we investigate the use of machine learning classiers to assess block cipher security from the perspective of differential cryptanalysis. The models are trained using the general block cipher features, making them generalizable to an entire class of ciphers. The features include the number of rounds, permutation pattern, and truncated differences whereas security labels are based on the number of differentially active substitution boxes. Prediction accuracy is further optimized by investigating the different ways of representing the cipher features in the dataset. Machine learning experiments involving six classifiers (linear and nonlinear) were performed on a simplied generalized Feistel cipher as a proof-of-concept, achieving a prediction accuracy of up to 95%. When predicting the security of unseen cipher variants, prediction accuracy of up to 77% was obtained. Our ndings show that nonlinear classiers outperform linear classiers for the prediction task due to the nonlinear nature of block ciphers. In addition, results also indicate the feasibility of using the proposed approach in assessing block cipher security or as machine learning distinguishers

In the random oracle model (ROM), it is provable from the DL assumption, whereas there is negative circumstantial evidence in the standard model. Fleischhacker, Jager, and Schr\"{o}der showed that the tight security of the Schnorr signature is unprovable from a strong cryptographic assumption, such as the One-More DL (OM-DL) assumption and the computational and decisional Diffie-Hellman assumption, in the ROM via a generic reduction as long as the underlying cryptographic assumption holds. However, it remains open whether or not the impossibility of the provable security of the Schnorr signature from a strong assumption via a non-tight and reasonable reduction. In this paper, we show that the security of the Schnorr signature is unprovable from the OM-DL assumption in the non-programmable ROM as long as the OM-DL assumption holds. Our impossibility result is proven via a non-tight Turing reduction.

A boardroom election is an election with a small number of voters carried out with public communications. We present BVOT, a self-tallying boardroom voting protocol with ballot secrecy, fairness (no tally information is available before the polls close), and dispute-freeness (voters can observe that all voters correctly followed the protocol).

BVOT works by using a multiparty threshold homomorphic encryption system in which each candidate is associated with a masked unique prime. Each voter engages in an oblivious transfer with an untrusted distributor: the voter selects the index of a prime associated with a candidate and receives the selected prime in masked form. The voter then casts their vote by encrypting their masked prime and broadcasting it to everyone. The distributor does not learn the voter's choice, and no one learns the mapping between primes and candidates until the audit phase. By hiding the mapping between primes and candidates, BVOT provides voters with insufficient information to carry out effective cheating. The threshold feature prevents anyone from computing any partial tally---until everyone has voted. Multiplying all votes, their decryption shares, and the unmasking factor yields a product of the primes each raised to the number of votes received.

In contrast to some existing boardroom voting protocols, BVOT does not rely on any zero-knowledge proof; instead, it uses oblivious transfer to assure ballot secrecy and correct vote casting. Also, BVOT can handle multiple candidates in one election. BVOT prevents cheating by hiding crucial information: an attempt to increase the tally of one candidate might increase the tally of another candidate. After all votes are cast, any party can tally the votes.