International Association
for Cryptologic Research

Blockchains such as bitcoin rely on reaching global consensus for the distributed ledger, and suffer from a well know scalability problem. We propose an algorithm which can avoid double spending in the short term with just $O(\sqrt{n})$ messages, relying on the fact that the velocity of money in the real world has coins generally circulating through at most a few wallets per day. The algorithm should be practical to avoid double spending with arbitrarily high probability, while feasibly coping with all the commerce in the world. This k-root-n algorithm is less effective in the long term once money circulates through a significant proportion of the world’s wallets, and should therefore be used as a complement to a global consensus. Thus, global consensus can be reached periodically and with a considerable lag, while money can be safely spent with quick transactions in-between.

Modular multiplication is one of the most compute-intensive arithmetic operations. Most public-key cryptosytems utilize modular multiplications of integers of various lengths, depending on security requirements. Efficient algorithms and implementations are required to realize a practical public-key cryptosystem. Different parameters, such as area, power and time, can be optimized for different implementation requirements. Low latency was not as important as high throughput requirement for modular multiplication implementations before. However, with recent work on Verifiable Delay Functions (VDFs), a necessity for lowest possible latency for modular multiplication implementations emerged. VDFs are designed to take a prescribed time to realize the underlying computation that can be publicly verified. VDF constructions are required to utilize inherently sequential arithmetic operations. Efficient VDF constructions have been proposed recently, based on time-lock puzzles constructed by Rivest, Shamir and Wagner. An exponentiation operation in an RSA group needs to be realized for these VDF constructions. For these VDF constructions to be practical, low-latency modular multiplication algorithms and implementations are required. In this paper, a modular multiplication algorithm suitable for low-latency circuit implementations is proposed and an FPGA-optimized variant of this algorithm is presented.

XTS is an encryption scheme for storage devices standardized by IEEE and NIST. It is based on Rogaway's XEX tweakable block cipher and is known to be secure up to the collisions between the blocks, thus up to around $2^{n/2}$ blocks for $n$-bit blocks. However this only implies that the theoretical indistinguishability notion is broken with $O(2^{n/2})$ queries and does not tell the practical risk against the plaintext recovery if XTS is targeted. We show several plaintext recovery attacks against XTS beyond collisions, and evaluate their practical impacts.

Security in the Internet of Things (IoT) is challenging. The need for lightweight yet robust cryptographic solutions suitable for the IoT calls for improved design and implementation of constructs such as Authenticated Encryption with Associated Data (AEAD) which can ensure confidentiality, integrity and authenticity of data in one algorithm. The U.S. National Institute of Standards and Technology (NIST) has embarked on a multi-year effort called the Lightweight Cryptography (LWC) Standardization Process to evaluate lightweight AEAD and optional hash algorithms for inclusion in U.S. federal standards. As candidates are evaluated for many characteristics including hardware resources and performance, obtaining results of hardware implementations as early as possible, i.e., even in round 1, is preferable. In this research, we implement three NIST LWC round 1 candidate ciphers, SpoC, Spook, and GIFT-COFB, in the Artix-7 FPGA. Implementations are compliant with the previously-validated CAESAR Hardware Applications Programming Interface (API) for Authenticated Ciphers, and are tested in actual hardware. Implementations show that GIFT-COFB has the highest Throughput-to-Area (TPA) ratio, by a 4.4 factor margin over Spook. Additionally, the results illustrate hardware implementation challenges associated with integrating multiple cryptographic primitives into one design, as well as complexities due to padding and truncation.

We design an efficient method for sampling a large batch of $d$ independent coins with a given bias $p \in [0,1]$. The folklore secure computation method for doing so requires $O(\lambda + \log d)$ communication an computation per coin to achieve sampling error $2^{-\lambda}$. We present an exponential improvement over the folklore method that uses just $O(\log(\lambda+\log d))$ gates per coin when sampling $d$ coins with total sampling error $2^{-\lambda}$. We present a variant of our work that also concretely beats the folklore method for $\lambda \leq 2^{-60}$ which are parameters that are often used in practice. Our new technique relies on using specially designed oblivious data structures to achieve biased coin samples that take an expected $2$ random bits to sample.

Using our new sampling technique, we present an implementation of the differentially private report-noisy-max mechanism (a more practical implementation of the celebrated exponential mechanism) as a secure multi-party computation. Our benchmarks show that one can run this mechanism on a domain of size $d=2^{12}$ in 6 seconds and up to $d=2^{19}$ in 14 minutes. As far as we know, this is the first complete distributed implementation of either of these mechanisms.

We explore definitions of coercion resistance in the computational model of cryptography; discovering all but one are too weak (i.e., satisfiable by voting systems that are not coercion resistant) and the other is too strong (i.e., unsatisfiable by voting systems that are). Hence, we show that coercion resistance has not been adequately formalised. Our results cast doubt over the security of voting systems that have been proven secure with respect to those definitions; a new definition is necessary.

Forward Secrecy (FS) is a security property in key-exchange algorithms which guarantees that a compromise in the secrecy of a long-term private-key does not compromise the secrecy of past session keys. With a growing awareness of long-term mass surveillance programs by governments and others, FS has become widely regarded as a highly desirable property. This is particularly true in the TLS protocol, which is used to secure Internet communication. In this paper, we investigate FS in pre-TLS 1.3 protocols, which do not mandate FS, but still widely used today. We conduct an empirical analysis of over 10 million TLS servers from three different datasets using a novel heuristic approach. Using a modern TLS client handshake algorithms, our results show 5.37% of top domains, 7.51% of random domains, and 26.16% of random IPs do not select FS key-exchange algorithms. Surprisingly, 39.20% of the top domains, 24.40% of the random domains, and 14.46% of the random IPs that do not select FS, do support FS. In light of this analysis, we discuss possible paths toward forward secure Internet traffic. As an improvement of the current state, we propose a new client-side mechanism that we call "Best Effort Forward Secrecy" (BEFS), and an extension of it that we call "Best Effort Forward Secrecy and Authenticated Encryption" (BESAFE), which aims to guide (force) misconfigured servers to FS using a best effort approach. Finally, within our analysis, we introduce a novel adversarial model that we call "discriminatory" adversary, which is applicable to the TLS protocol.

Location data is an important piece of contextual information in location-driven features for geosocial and pervasive computing applications. In this paper, we propose to geo-hash locations using space-filling curves, which are dimension reduction techniques that preserve locality. The proposed location referencing method is agnostic to specific maps or precoded location models and can effectively preserve users’ location privacy based on user preferences. We employ post-quantum-secure encryption on location data and privacy preferences to minimize the risk of data leakage. We also design three algorithms to homomorphically compute geospatial queries on the encrypted location data without revealing either user locations or user preferences. One of the three proposed algorithms reduces the multiplicative depth by more than half; thus, significantly speeding up homomorphic computations. We then present a prototype of the proposed system and algorithms using a somewhat homomorphic encryption scheme and our optimization techniques. A systematic evaluation of the prototype demonstrates its utility in spatial cloaking.

Decision tree and its generalization of random forests are a simple yet powerful machine learning model for many classification and regression problems. Recent works propose how to privately evaluate a decision tree in a two-party setting where the feature vector of the client or the decision tree model (such as the threshold values of its nodes) is kept a secret from another party. However, these works cannot be extended trivially to support the outsourcing setting where a third-party who should not have access to the model or the query. Furthermore, their use of an interactive comparison protocol does not support branching program, hence requires interactions with the client to determine the comparison result before resuming the evaluation task. In this paper, we propose the first secure protocol for collaborative evaluation of random forests contributed by multiple owners. They outsource evaluation tasks to a third-party evaluator. Upon receiving the client’s encrypted inputs, the cloud evaluates obliviously on individually encrypted random forest models and calculates the aggregated result. The system is based on our new secure comparison protocol, secure counting protocol, and a multi-key somewhat homomorphic encryption on top of symmetric-key encryption. This allows us to reduce communication overheads while achieving round complexity lower than existing work.

This article, for the first time, demonstrates Cross-device Deep Learning Side-Channel Attack (X-DeepSCA), achieving an accuracy of $>99.9\%$, even in presence of significantly higher inter-device variations compared to the inter-key variations. Augmenting traces captured from multiple devices for training and with proper choice of hyper-parameters, the proposed 256-class Deep Neural Network (DNN) learns accurately from the power side-channel leakage of an AES-128 target encryption engine, and an N-trace ($N\leq10$) X-DeepSCA attack breaks different target devices within seconds compared to a few minutes for a correlational power analysis (CPA) attack, thereby increasing the threat surface for embedded devices significantly. Even for low SNR scenarios, the proposed X-DeepSCA attack achieves $\sim10\times$ lower minimum traces to disclosure (MTD) compared to a traditional CPA.

Event date: 6 December to 9 December 2019
Submission deadline: 1 August 2019
Notification: 1 September 2019

Non-zero inner product encryption (NIPE) allows a user to encrypt a message with its attribute vector and decryption is possible using a secret-key associated with a predicate vector if the inner product of the vectors is non-zero. The concept of NIPE was put forth by Katz, Sahai and Waters (EUROCRYPT 2008). Following that many NIPE constructions were proposed along with interesting applications. The security of all these works is based on hardness assumptions in pairing-friendly groups. Recently, Katsumata and Yamada (PKC 2019) built a NIPE relying on the Learning-with-Errors (LWE) problems, however, their system practically lags behind for providing only selective security with significantly large sizes of master public-key, secret-keys and ciphertexts. Despite its cryptographic importance, past history of NIPE is not convincing in terms of both security and practical efficiency as the schemes are either selectively secure or depend on bilinear maps.

In this paper, our goal is to construct adaptively secure efficient NIPEs. Firstly, we provide adaptively secure public-key NIPE under the standard Decision Diffie-Hellman (DDH) assumption that enables one to encrypt messages of sufficiently small length. To overcome this limitation we rely on the Decision Diffie-Hellman-f (DDH-f) and the Hard Subgroup Membership (HSM) assumptions proposed by Castagnos et al. in ASIACRYPT 2018. Consequently, we construct two pNIPEs, adaptively secure under the DDH-f and HSM assumptions respectively, both are capable of encrypting large messages with inner products over integers. We upgrade these two pNIPEs so that it can encrypt messages with unbounded inner products modulo an arbitrary large prime p. In addition, utilizing inner product functional encryptions we provide attribute-hiding public-key NIPEs depending on the DDH, DDH-f, HSM, LWE, Decision Composite Reciprocity assumptions and establish full-hiding private-key NIPEs based on the Decision linear and Symmetric External Diffie-Hellman assumptions.

A framework for asynchronous, signature free, fully local and probabilistically converging total order algorithms is developed, that may survive in high entropy, unstructured Peer-to-Peer networks with near optimal communication efficiency. Regarding the natural boundaries of the CAP-theorem, the protocol chooses different compromises for consistency and availability, depending on the severity of the attack.

The family is parameterized by a few constants and external functions called voting-weight, incentivation and punishement, difficulty oracle and quorum-selector. These functions are necessary to fine tune the dynamics and very different long term behavior might appear, depending on any actual choice.

The basic Supersingular Isogeny Diffie-Hellman (SIDH) key agreement protocol is insecure due to an attack described by Galbraith, Petit, Shani and Ti. In this note we present two variants of SIDH that are immune to this attack.

Pairing-friendly elliptic curve constructions provide two elliptic curve groups which are both of prime order $q$ and usually each have a nontrivial cofactor $h$. Due to the way these curves are typically constructed, endomorphisms can be applied to perform fast cofactor multiplication. However, cofactor multiplication is sometimes insufficient for dealing with cofactors, such as with malleability attacks.

In this brief note, we describe efficient techniques for checking that points exist within the correct $q$-order subgroups of the BLS12-381 elliptic curve construction, which is the focus of standardization for pairing-based protocols. Instead of multiplying by $q$ and comparing the point with the identity, we use endomorphisms to eliminate the $q$-torsion while modifying (but not killing) the $h$-torsion components. The result can then be compared against the identity.

Symmetric Searchable encryption (SSE) is an encryption technique that allows users to search directly on their outsourced encrypted data, in a way that the privacy of both the files and the search queries is preserved. Naturally, with every search query, some information is leaked. The leakage becomes even bigger when the scheme is dynamic (i.e. supports file insertions and deletions). To deal with this problem we design a forward private dynamic SSE scheme where file insertions do not leak any information about previous queries. Moreover, our construction supports the multi-client model, in the sense that every user that holds the secret key can perform search queries. Finally, our scheme also focuses on the problem of synchronization by utilizing the functionality offered by Intel SGX.

Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-$129/129$ with $38$ rounds with time and data complexity $2^{65.5}$ and $2^{60.2}$ respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-$129/129$ the full $82$ rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC.

Building expressive encrypted databases that can scale to large volumes of data while enjoying formal security guarantees has been one of the holy grails of security and cryptography research. Searchable Encryption (SE) is considered to be an attractive implementation choice for this goal: It naturally supports basic database queries such as point, join and range, and is very practical at the expense of well-defined leakage such as search and access pattern. Nevertheless, recent attacks have exploited these leakages to recover the plaintext database or the posed queries, casting doubt to the usefulness of SE in encrypted systems. Defenses against such leakage-abuse attacks typically require the use of Oblivious RAM or worst-case padding---such countermeasures are however quite impractical. In order to efficiently defend against leakage-abuse attacks on SE-based systems, we propose SEAL, a family of new SE schemes with adjustable leakage. In SEAL, the amount of privacy loss is expressed in leaked bits of search or access pattern and can be defined at setup. As our experiments show, when protecting only a few bits of leakage (e.g., three to four bits of access pattern), enough for existing and even new more aggressive attacks to fail, SEAL query execution time is within the realm of practical for real-world applications (a little over one order of magnitude slowdown compared to traditional SE-based encrypted databases). Our findings therefore show that SEAL could be a promising approach for building efficient and robust encrypted databases.

In an article from CHES 2015, which appears in extended form in the Journal of Cryptology in 2019, Bernard, Haddad, Fischer, and Nicolai modeled the physical behavior of a transient effect ring oscillator (TERO), thereby providing a means to certify its operation as a true random number generator (TRNG). In this work, we disprove the physical assumption on which the whole model is based. Moreover, we show that the convenient use of tractable, closed-form equations stems from a mathematical error. On a more constructive note, we are the first to point out that TEROs and Bistable Ring physically unclonable functions (PUFs) are closely related, thereby not only laying the foundations of a more accurate physical model but also revealing a new design trade-off between throughput, entropy, and reliability. Furthermore, we demonstrate that most TERO implementations in the literature are prone to counter value corruptions, and propose a solution to this problem. Measurements performed on a field-programmable gate array (FPGA) substantiate our claims.

Many cryptographers have focused on lightweight cryptography, and a huge number of lightweight block ciphers have been proposed. On the other hand, designing lightweight stream ciphers is a challenging task due to the well-known security criteria, i.e., the state size of stream ciphers must be at least twice the key size. The designers of Sprout addressed this issue by involving the secret key not only in the initialization but also in the keystream generation, and the state size of such stream ciphers can be smaller than twice the key size. After the seminal work, some small-state stream ciphers have been proposed such as Fruit, Plantlet, and LIZARD. Unlike conventional stream ciphers, these small-state stream ciphers have the limitation of keystream bits that can be generated from the same key and IV pair. In this paper, our motivation is to show whether the data limitation claimed by the designers is proper or not. The correlation attack is one of the attack methods exploiting many keystream bits generated from the same key and IV pair, and we apply it to Fruit-80 and Plantlet. As a result, we can break the full Fruit-80, i.e., the designers' data limitation is not sufficient. We can also recover the secret key of Plantlet if it allows about $2^{53}$ keystream bits from the same key and IV pair.