International Association
for Cryptologic Research

Cryptographic accumulators are a common solution to proving information about a large set $S$. They allow to compute a short digest of $S$ and short certificates of some of its basic properties, notably membership of an element. Accumulators also allow to track set updates: a new accumulator is obtained by inserting/deleting a given element. In this work we consider the problem of generating membership and update proofs for {\em batches} of elements so that we can succinctly prove additional properties of the elements (i.e., proofs are of constant size regardless of the batch size), and we can preserve privacy. Solving this problem would allow to obtain blockchain systems with improved privacy and scalability. The state-of-the-art approach to achieve this goal is to combine accumulators (typically Merkle trees) with zkSNARKs. This solution is however expensive for provers and does not scale for large batches of elements. In particular, there is no scalable solution for proving batch membership proofs when we require zero-knowledge (a standard definition of privacy-preserving protocols). In this work we propose new techniques to efficiently use zkSNARKs with RSA accumulators. We design and implement two main schemes: 1) HARiSA, which proves batch membership in zero-knowledge; 2) B-INS-HARiSA, which proves batch updates. For batch membership, the prover in HARiSA is orders of magnitude faster than existing approaches based on Merkle trees (depending on the hash function). For batch updates we get similar cost savings compared to approaches based on Merkle tree; we also improve

This paper introduces IronMask, a new versatile verification tool for masking security. IronMask is the first to offer the verification of standard simulation-based security notions in the probing model as well as recent composition and expandability notions in the random probing model. It supports any masking gadgets with linear randomness (e.g. addition, copy and refresh gadgets) as well as quadratic gadgets (e.g. multiplication gadgets) that might include non-linear randomness (e.g. by refreshing their inputs), while providing complete verification results for both types of gadgets. We achieve this complete verifiability by introducing a new algebraic characterization for such quadratic gadgets and exhibiting a complete method to determine the sets of input shares which are necessary and sufficient to perform a perfect simulation of any set of probes. We report various benchmarks which show that IronMask is competitive with state-of-the-art verification tools in the probing model (maskVerif, scVerif, SILVER, matverif). IronMask is also several orders of magnitude faster than VRAPS --the only previous tool verifying random probing composability and expandability-- as well as SILVER --the only previous tool providing complete verification for quadratic gadgets with non-linear randomness. Thanks to this completeness and increased performance, we obtain better bounds for the tolerated leakage probability of state-of-the-art random probing secure compilers.

The solving degree of a system of multivariate polynomial equations provides an upper bound for the complexity of computing the solutions of the system via Groebner basis methods. In this paper, we consider polynomial systems that are obtained via Weil restriction of scalars. The latter is an arithmetic construction which, given a finite Galois field extension $k\hookrightarrow K$, associates to a system $\mathcal{F}$ defined over $K$ a system $\mathrm{Weil}(\mathcal{F})$ defined over $k$, in such a way that the solutions of $\mathcal{F}$ over $K$ and those of $\mathrm{Weil}(\mathcal{F})$ over $k$ are in natural bijection. In this paper, we find upper bounds for the complexity of solving a polynomial system $\mathrm{Weil}(\mathcal{F})$ obtained via Weil restriction in terms of algebraic invariants of the system $\mathcal{F}$.

The rise of blockchain technology has boosted interest in privacy-enhancing technologies, in particular, anonymous transaction authentication. Permissionless blockchains realize transaction anonymity through one-time pseudonyms, whereas permissioned blockchains leverage anonymous credentials. Earlier solutions of anonymous credentials assume a single issuer; as a result, they hide the identity of users but still reveal the identity of the issuer. A countermeasure is delegatable credentials, which support multiple issuers as long as a root authority exists. Assuming a root authority however, is unsuitable for blockchain technology and decentralized applications. This paper introduces a solution for anonymous credentials that guarantees user anonymity, even without a root authority. The proposed solution is secure in the universal composability framework and allows users to produce anonymous signatures that are logarithmic in the number of issuers and constant in the number of user attributes.

Publish-subscribe protocols enable real-time multi-point-to-multi-point communications for many dispersed computing systems like Internet of Things (IoT) applications. Recent interest has focused on adding processing to such publish-subscribe protocols to enable computation over real-time streams such that the protocols can provide functionalities such as sensor fusion, compression, and other statistical analysis on raw sensor data. However, unlike pure publish-subscribe protocols, which can be easily deployed with end-to-end transport layer encryption, it is challenging to ensure security in such publish-process-subscribe protocols when the processing is carried out on an untrusted third party. In this work, we present XYZ, a secure publish-process-subscribe system that can preserve the confidentiality of computations and support multi-publisher-multi-subscriber settings. Within XYZ, we design two distinct schemes: the first using Yao's garbled circuits (the GC-Based Scheme) and the second using homomorphic encryption with proxy re-encryption (the Proxy-HE Scheme). We build implementations of the two schemes as an integrated system atop the Message Queue Telemetry Transport (MQTT) pub-sub protocol. We evaluate our system on several functions and also demonstrate real-world applications based on it. The evaluation shows that the GC-Based Scheme can finish most tasks two orders of magnitude times faster than the Proxy-HE Scheme while Proxy-HE can still securely complete tasks within an acceptable time for most functions but with a different security assumption and a simpler system structure.

We consider the problem of constructing an unconditionally secure cipher for the case when the key length is less than the length of the encrypted message. (Unconditional security means that a computationally unbounded adversary cannot obtain information about the encrypted message without the key.) In this article, we propose data compression and randomization techniques combined with entropically-secure encryption. The resulting cipher can be used for encryption in such a way that the key length does not depend on the entropy or the length of the encrypted message; instead, it is determined by the required security level.

We introduce distance-comparison-preserving symmetric encryption (DCPE), a new type of property-preserving encryption (PPE) that preserves relative distance between plaintext vectors. DCPE is naturally suited for nearest-neighbor search on encrypted data. To achieve meaningful security, we divert from prior work on PPE and ask for approximate correctness, which is natural given the prevalence of approximate nearest neighbor (ANN) search. We conduct a thorough study of what security approximate DCPE can provide and how to construct it.

Based on a relation we prove between approximate DCP and approximate distance-preserving functions, we design our core approximate DCPE scheme we call Scale-And-Perturb ($\mathsf{SAP}$). The encryption algorithm of $\mathsf{SAP}$ processes data on-the-fly. To boost security, we also introduce two preprocessing techniques: (1) normalizing the plaintext distribution, and (2) shuffling, wherein the component-wise encrypted dataset is randomly permuted. We prove (under suitable restrictions) that $\mathsf{SAP}$ achieves an indistinguishability-based security notion we call Real-or-Replaced ($\mathsf{RoR}$). In particular, our $\mathsf{RoR}$ result implies that our scheme prevents membership inference attacks by Yeom et al. (CSF 2018). Moreover, we show for i.i.d. multivariate normal plaintexts, we get security against approximate frequency-finding attacks, the main line of attacks against property-preserving encryption. This follows from a one-wayness $(\mathsf{OW})$ analysis. Finally, carefully combining our $\mathsf{OW}$ and $\mathsf{RoR}$ results, we are able characterize bit-security of $\mathsf{SAP}$.

Our overall findings are that our scheme not only has superior bit-security to OPE but resists specific attacks that even ideal order-revealing encryption (Boneh et al., EUROCRYPT 2015) does not. This suggests it could be sufficient for certain ANN applications, a subject on which we encourage further study.

We derive the first adaptively secure IBE and ABE for t-CNF, and selectively secure ABE for general circuits from lattices, with $1-o(1)$ leakage rates, in the both relative leakage model and bounded retrieval model (BRM).

To achieve this, we first identify a new fine-grained security notion for ABE -- partially adaptive/selective security, and instantiate this notion from LWE. Then, by using this notion, we design a new key compressing mechanism for identity-based/attributed-based weak hash proof system (IB/AB-wHPS) for various policy classes, achieving (1) succinct secret keys and (2) adaptive/selective security matching the existing non-leakage resilient lattice-based designs. Using the existing connection between weak hash proof system and leakage resilient encryption, the succinct-key IB/AB-wHPS can yield the desired leakage resilient IBE/ABE schemes with the optimal leakage rates in the relative leakage model. Finally, by further improving the prior analysis of the compatible locally computable extractors, we can achieve the optimal leakage rates in the BRM.

As a building block, gadgets and associated algorithms are widely used in advanced lattice cryptosystems. The gadget algorithms for power-of-base moduli are very efficient and simple, however the current algorithms for arbitrary moduli are still complicated and practically more costly despite several efforts. Considering the necessity of arbitrary moduli, developing simpler and more practical gadget algorithms for arbitrary moduli is crucial to improving the practical performance of lattice based applications.

In this work, we propose two new gadget sampling algorithms for arbitrary moduli. Our first algorithm is for gadget Gaussian sampling. It is simple and efficient. One distinguishing feature of our Gaussian sampler is that it does not need floating-point arithmetic, which makes it better compatible with constrained environments. Our second algorithm is for gadget subgaussian sampling. Compared with the existing algorithm, it is simpler, faster, and requires asymptotically less randomness. In addition, our subgaussian sampler achieves an almost equal quality for different practical parameters. Overall these two algorithms provide simpler options for gadget algorithms and enhance the practicality of the gadget toolkit.

Pseudorandom states, introduced by Ji, Liu and Song (Crypto'18), are efficiently-computable quantum states that are computationally indistinguishable from Haar-random states. One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist. Motivated by this, we study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states.

We construct, assuming the existence of pseudorandom state generators that map a $\lambda$-bit seed to a $\omega(\log\lambda)$-qubit state, (a) statistically binding and computationally hiding commitments and (b) pseudo one-time encryption schemes. A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty computation protocols in the dishonest majority setting.

Our constructions are derived via a new notion called pseudorandom function-like states (PRFS), a generalization of pseudorandom states that parallels the classical notion of pseudorandom functions. Beyond the above two applications, we believe our notion can effectively replace pseudorandom functions in many other cryptographic applications.

Information security plays a major role in the dynamics of today’s interconnected world. Despite the successful implementation and effectiveness of modern cryptographic techniques, their inherent limitations can be exploited by quantum computers. In this article we discuss Grover’s quantum searching algorithm and its impact on the security of modern symmetric ciphers. More specifically, we present its formal description and give an implementation of the algorithm using IBM’s Qiskit framework, which allows us to simulate and run the program on a real device.

Applications today rely on cloud databases for storing and querying time-series data. While outsourcing storage is convenient, this data is often sensitive, making data breaches a serious concern. We present Waldo, a time-series database with rich functionality and strong security guarantees: Waldo supports multi-predicate filtering, protects data contents as well as query filter values and search access patterns, and provides malicious security in the 3-party honest-majority setting. In contrast, prior systems such as Timecrypt and Zeph have limited functionality and security: (1) these systems can only filter on time, and (2) they reveal the queried time interval to the server. Oblivious RAM (ORAM) and generic multiparty computation (MPC) are natural choices for eliminating leakage from prior work, but both of these are prohibitively expensive in our setting due to the number of roundtrips and bandwidth overhead, respectively. To minimize both, Waldo builds on top of function secret sharing, enabling Waldo to evaluate predicates non-interactively. We develop new techniques for applying function secret sharing to the encrypted database setting where there are malicious servers, secret inputs, and chained predicates. With 32-core machines, Waldo runs a query with 8 range predicates over $2^{18}$ records in 3.03s, compared to 12.88s for an MPC baseline and 16.56s for an ORAM baseline. Compared to Waldo, the MPC baseline uses 9 − 82× more bandwidth between servers (for different numbers of records), while the ORAM baseline uses 20 − 152× more bandwidth between the client and server(s) (for different numbers of predicates).

Identity-based matchmaking encryption (IB-ME) is a generalization of identity-based encryption where the sender and the receiver can both specify a target identity: if both the chosen target identities match the one of the other party, the plaintext is revealed, and otherwise the sender’s identity, the target identity, and the plaintext remain hidden. Previous work showed how to construct IB-ME in the random oracle model. We give the first construction in the plain model, based on standard assumptions over bilinear groups.

At the turn of the century, 80-bit security was the standard. When considering discrete-log based cryptosystems, it could be achieved using either subgroups of 1024-bit finite fields or using (hyper)elliptic curves. The latter would allow more compact and efficient arithmetic, until Lenstra and Verheul invented XTR. Here XTR stands for 'ECSTR', itself an abbreviation for Efficient and Compact Subgroup Trace Representation. XTR exploits algebraic properties of the cyclotomic subgroup of sixth degree extension fields, allowing representation only a third of their regular size, making finite field DLP-based systems competitive with elliptic curve ones. Subsequent developments, such as the move to 128-bit security and improvements in finite field DLP, rendered the original XTR and closely related torus-based cryptosystems no longer competitive with elliptic curves. Yet, some of the techniques related to XTR are still relevant for certain pairing-based cryptosystems. This chapter describes the past and the present of XTR and other methods for efficient and compact subgroup arithmetic.

This paper presents an Identifiable Cheating Entity (ICE) FROST signature protocol that is an improvement over the FROST signature scheme (Komlo and Godberg, SAC 2020) since it can identify cheating participants in its Key Generation protocol. The proposed threshold signature protocol achieves robustness in theKey Generation phase of the threshold signature protocol by introducing a cheating identification mechanism and then excluding cheating participants from the protocol. By enabling the cheating identification mechanism, we remove the need to abort the Key Generation protocol every time cheating activity is suspected. Our cheating identification mechanism allows every participant to individually check the validity of complaints issued against possibly cheating participants. Then, after all of the cheating participants are eliminated, the Key Generation protocol is guaranteed to finish successfully. On the other hand, the signing process only achieves a weak form of robustness, as in the original FROST. We then introduce static public key variant of ICE FROST. Our work is the first to consider static private/public keys for a round-optimized Schnorr-based signature scheme. With static public keys, the group’s established public and private keys remain constant for the lifetime of signers, while the signing shares of each participant are updated overtime, as well as the set of group members, which ensures the long-term security of the static keys and facilitates the verification process of the generated threshold signature because a group of signers communicates their public key to the verifier only once during the group’s lifetime. Our implementation benchmarks demonstrate that the runtime of the protocol is feasible for real-world applications.

Blockchain systems, as append-only ledgers, are typically associated with linearly growing participation costs. Therefore, for a blockchain client to interact with the system (query or submit a transaction), it can either pay these costs by downloading, storing and verifying the blockchain history, or forfeit blockchain security guarantees and place its trust on third party intermediary servers.

With this problem becoming apparent from early works in the blockchain space, the concept of a light client has been proposed, where a resource-constrained client such as a browser or mobile device can participate in the system by querying and/or submitting transactions without holding the full blockchain but while still inheriting the blockchain's security guarantees. A plethora of blockchain systems with different light client frameworks and implementations have been proposed, each with different functionalities, assumptions and efficiencies. In this work we provide a systematization of such light client designs. We unify the space by providing a set of definitions on their properties in terms of provided functionality, efficiency and security, and provide future research directions based on our findings.

Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness $w$ corresponding to a secret element $x$ of a public set, such that they jointly satisfy a given NP relation, {\em i.e.} $\mathcal{R}(w,x)=1$ and $x$ is a member of a public set $\{x_1, \ldots, x_\ell\}$. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies.

In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOC'07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCS'18]. We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.

In this work, we present cost analysis for mounting Grover's key search on Present block cipher. Reversible quantum circuits for Present are designed taking into consideration several decompositions of toffoli gate. This designs are then used to produce Grover oracle for Present and their implementations cost is compared using several metrics. Resource estimation for Grover's search is conducted by employing these Grover oracles. Finally, gate cost for these designs are estimated considering NIST's depth restrictions.

Hardware vulnerabilities are generally considered more difficult to fix than software ones because of their persistent nature after fabrication. Thus, it is crucial to assess the security and fix the potential vulnerabilities in the earlier design phases, such as Register Transfer Level (RTL), gate-level or physical layout. The focus of the existing security assessment techniques is mainly twofold. First, they check the security of Intellectual Property (IP) blocks separately (they can be applied on a single module). Second, they aim to assess the security against individual threats considering the threats are orthogonal. We argue that IP-level security assessment is not sufficient. Eventually, the IPs are placed in a platform, such as a system-on-chip (SoC), where each IP is surrounded by other IPs connected through glue logic and shared/private buses. This has a substantial impact on the platform's security. Hence, we must develop a methodology to assess the platform-level security by considering both the IP-level security and the impact of the additional parameters introduced during the transition from IP to the platform. Another important factor to consider is that the threats are not always orthogonal. Improving security against one threat may affect the security against other threats. Hence, to build a secure platform, we must first fully understand the impact of IP communications on security while considering the following questions: What type of additional parameters are introduced during the platform integration? How to define and characterize the impact of these parameters on security? How do the mitigation techniques of one threat impact others? This paper aims to answer these important questions and proposes techniques for quantifiable assurance by quantitatively estimating and measuring the security of a platform at pre-silicon stages. We also touch upon the term security optimization and present the challenges towards future research directions.

A recent paper by Zhang and Zhang claims to construct the first code-based non-interactive key exchange protocol, using a modified version of the Code Equivalence problem. We explain why this approach is flawed, and consequently debunk this claim. A simple Magma script confirms our results.