International Association
for Cryptologic Research

We present an oblivious transfer scheme that extends the proposal made by Barreto, Oliveira and Benits, based in supersingular isogenies, to the setting of principally polarized supersingular abelian surfaces.

We present EverCrypt: a comprehensive collection of verified, high-performance cryptographic functionalities available via a carefully designed API. The API provably supports agility (choosing between multiple algorithms for the same functionality) and multiplexing (choosing between multiple implementations of the same algorithm). Through a combination of abstraction and zero-cost generic programming, we show how agility can simplify verification without sacrificing performance, and we demonstrate how C and assembly can be composed and verified against shared specifications. We substantiate the effectiveness of these techniques with new verified implementations (including hashes, Curve25519, and AES-GCM) whose performance matches or exceeds the best unverified implementations. We validate the API design with two high-performance verified case studies built atop EverCrypt, resulting in line-rate performance for a secure network protocol and a Merkle tree library, used in a production blockchain, that supports 2.5+ million insertions/sec. Altogether, EverCrypt consists of over 100K verified lines of specs, code, and proofs, and it produces over 45K lines of C and assembly code.

We describe SKIVA, a customized 32-bit processor enabling the design of software countermeasures for a broad range of implementation attacks covering fault injection and side-channel analysis of timing-based and power-based leakage. We design the countermeasures as variants of bitslice programming. Our protection scheme is flexible and modular, allowing us to combine higher-order masking -- fending off side-channel analysis -- with complementary spatial and temporal redundancy -- protecting against fault injection. Multiple configurations of side-channel and fault protection enable the programmer to select the desired number of shares and the desired redundancy level for each slice. Recurring and security-sensitive operations are supported in hardware through a custom instruction set extension. The new instructions support bitslicing, secret-share generation, redundant logic computation, and fault detection. We demonstrate and analyze multiple versions of AES from a side-channel analysis and a fault-injection perspective, in addition to providing a detailed performance evaluation of the protected designs.

Cryptographic Hardware and Embedded Systems (CHES) 2019

Atlanta, GA, August 25-28, 2019

https://ches.iacr.org/2019/

The Cryptographic Hardware and Embedded Systems (CHES) conference is the premier venue for research on design and evaluation of cryptographic implementations and secure embedded systems. CHES 2019 marks the 20th anniversary of the CHES conference and will take place in the city of Atlanta, U.S.A., August 25–28, 2019, immediately following CRYPTO 2019.

Registration
CHES 2019 registrations are now open at https://ches.iacr.org/2019/registration.shtml
The early registration deadline ends on July 24, 2019.

Program
CHES 2019 offers a broad collection of events:

• Three days of conference with top-notch paper presentations, with papers accepted and published by TCHES;
• Two invited keynote talks;
• Six half-day tutorials by experts in the field;
• Two co-located pre-conference events, FDTC and PROOFS
• A banquet at Sundial Restaurant, a 70th-floor prime location in downtown Atlanta
• A social event at the Martin Luther King National Historical Park

Hotel
The conference venue is the Sheraton Hotel in downtown Atlanta. The hotel provides a time-limited rate to CHES 2019 attendees.

• Book a hotel room at the regular CHES 2019 rate ($159/night and up; in June, a limited number of rooms at a special $139/night rate are available for reservation for CHES 2019)
• Book a hotel room at the student CHES 2019 rate ($99/night)

These rates are cancellable – but if you want even lower nonrefundable rates, use the main Sheraton-Atlanta website. Please let us know in your registration form that you plan to stay at the Sheraton.

Travel
CHES 2019 is organized in Downtown Atlanta and is easily reachable from the Atlanta International Airport (ATL). Consult the CHES 2019 Travel Information Page for additional guidelines.

Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) combiner $H1(M) \oplus H2(M)$ and the concatenation combiner $H1(M) \parallel H2(M)$. Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice $H2(H1(IV,M),M)$ and the Zipper hash $H2(H1(IV,M),\overleftarrow{M})$, where $\overleftarrow{M}$ is the reverse of the message $M$.

In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows: 1. Several generic preimage attacks on the XOR combiner: -- A first attack with a best-case complexity of $2^{5n/6}$ obtained for messages of length $2^{n/3}$. It relies on a novel technical tool named Interchange Structure. It is applicable for combiners whose underlying hash functions follow the Merkle-Damgård construction or the HAIFA framework. -- A second attack with a best-case complexity of $2^{2n/3}$ obtained for messages of length $ 2^{n/2} $. It exploits properties of functional graphs of random mappings. It achieves a significant improvement over the first attack but is only applicable when the underlying hash functions use the Merkle-Damgård construction. -- An improvement upon the second attack with a best-case complexity of $2^{5n/8}$ obtained for messages of length $2^{5n/8}$. It further exploits properties of functional graphs of random mappings and uses longer messages. These attacks show a rather surprising result: regarding preimage resistance, the sum of two $n$-bit narrow-pipe hash functions following the considered constructions can never provide $ n $-bit security. 2. A generic second-preimage attack on the concatenation combiner of two Merkle Damgård hash functions. This attack finds second preimages faster than $2^n$ for challenges longer than $2^{2n/7}$ and has a best-case complexity of $2^{3n/4}$ obtained for challenges of length $2^{3n/4}$. It also exploits properties of functional graphs of random mappings. 3. The first generic second-preimage attack on the Zipper hash with underlying hash functions following the Merkle-Damgård construction. The best-case complexity is $2^{3n/5}$, obtained for challenge messages of length $2^{2n/5}$. 4. An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle-Damgård construction. The best-case complexity is $2^{13n/22}$, obtained for challenge messages of length $2^{13n/22}$. The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two $n$-bit narrow-pipe Merkle-Damgård hash functions do not provide much more security than that can be provided by a single $n$-bit hash function.

Our main technical contributions include the following: 1. The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input. 2. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multi-collision for both of the underlying hash functions. 3. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.

Consider the following two fundamental open problems in complexity theory: 1) Does a hard-on-average language in $\mathsf{NP}$ imply the existence of one-way functions? 2) Does a hard-on-average language in $\mathsf{NP}$ imply a hard problem in $\mathsf{TFNP}$ (i.e., the class of \emph{total} $\mathsf{NP}$ search problem)?

We show that the answer to (at least) one of these questions is yes. In other words, in Impagliazzo's Pessiland (where $\mathsf{NP}$ is hard-on-average, but one-way functions do not exist), $\mathsf{TFNP}$ is unconditionally hard (on average).

This result follows from a more general theory of interactive average-case complexity, and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols. As another consequence of this treatment, we show that the existence of $O(1)$-round public-coin non-trivial arguments (i.e., argument systems that are not proofs) imply the existence of a hard-on-average problem in $\mathsf{NP}/\mathsf{poly}$.

Permissioned Blockchain has become quite popular with enterprises forming consortium since it prioritizes trust over privacy. One of the popular platforms for distributed ledger solution, Hyperledger Fabric, requires a transaction to be endorsed or approved by a group of special members known as endorsers before undergoing validation. To endorse a transaction, an endorser mentions its identity along with the signature so that it can be verified later. However, for certain transactions, difference in opinion may exist among endorsers. Disclosing the identity of an endorser may lead to conflict within the consortium. In such cases, an endorsement policy which not only allows an endorser to support a transaction discreetly, but at the same time takes into account the decision of the majority is preferred. Thus we propose an Anonymous Endorsement System which uses a threshold endorsement policy in order to address the issue. To realize a t-out-of-n endorsement policy, using any of the existing threshold ring signature for our endorsement system would have violated the privacy of endorsers as either the identity or the secret key of the endorsers get revealed to the party who recombines the signature after collecting each signature share. All these factors motivated us to design a new ring signature scheme, called Fabric's Constant-Sized Linkable Ring Signature (FCsLRS) with Transaction-Oriented linkability for hiding identity of the endorsers. We have implemented the signature scheme in Golang and analyzed its security and performance by varying the RSA (Rivest-Shamir-Adleman) modulus size. Feasibility of implementation is supported by experimental analysis. Signature and tag generation time is quite fast and remains constant irrespective of change in message length or endorsement set size for a given RSA modulus value, assuming all the endorsers generates their signature in parallel. Each verifier is required to count and check individual valid ring signature. If the aggregate is above the threshold value, stated by the endorsement policy, then it confirms that the transaction is valid. This increases the verification time depending on the threshold value, but has very little effect on the scalability since generally $t<<n$. Lastly, we also discuss the integration of the scheme on v1.2 Hyperledger Fabric.

Honest majority is a vital assumption of Bitcoin-style blockchains. However, recent 51% attacks render this assumption unrealistic in practice. In this paper, we analyse two possible 51% attacks launched by a rational miner, who is profit driven. The first attack considers a rational miner, who moves his mining power from a stronger blockchain to a weaker blockchain to launch 51% attacks, provided that (1) the mining power is compatible in both blockchains, and (2) the transferred mining power dominates the weaker blockchain. We say a blockchain is stronger if the total mining power of this blockchain is higher than other (weaker) blockchains. The second attack considers a rational miner, who rents cloud mining power to launch 51% attacks. The former attack is new, and we name it mining power migration attack; the latter is called cloud mining attack, and it was initially covered by the bribery attack (FC’ 16). We formalise the two attacks by using Markov Decision Process. We then test the feasibility of launching both attacks on leading blockchains in the wild by using our model. We show that both attacks are feasible and profitable. For example, our result shows that with 12.5% mining power of Bitcoin, a rational miner can gain approximately 6% (18,946.5 USD) extra profit than honest mining, by launching mining power migration attack to double spend a transaction of 3000 BCH (equivalent to $378,930) on BitcoinCash. We also investigate the 51% attack on Ethereum Classic happened in Jan. 2019, by applying our model into this attack to provide some insights to understand more about it.

We prove that the discrete logarithm problem can be solved in quasi-polynomial expected time in the multiplicative group of finite fields of fixed characteristic. More generally, we prove that it can be solved in the field of cardinality $p^n$ in expected time $(pn)^{2\log_2(n) + O(1)}$.

We report on a simple technique that supports some recent developments on AES by Grassi and Rechberger and Bao, Guo and List. We construct a weight transition probability matrix related to AES that characterises fixed configurations of active bytes in differences of ciphertexts when plaintext differences are fixed to some (possibly other) configuration of active bytes. The construction is very simple and one might even consider it to be a little naive. However, the derived probabilities match recent results on 5- and 6-rounds AES derived through more sophisticated means, indicating that it might be worth a further investigation.

TLS (Transport Layer Security) is a widely deployed protocol that plays a vital role in securing Internet trafic. Given the numerous known attacks for TLS 1.2, it was imperative to change and even redesign the protocol in order to address them. In August 2018, a new version of the protocol, TLS 1.3, was standardized by the IETF (Internet Engineering Task Force). TLS 1.3 not only benefits from stronger security guarantees, but aims to protect the identities of the server and client by encrypting messages as soon as possible during the authentication. In this paper, we model the privacy guarantees of TLS 1.3 when parties execute a full handshake or use a session resumption, covering all the handshake modes of TLS. We build our privacy models on top of the one defined by Hermans et al. for RFIDs (Radio Frequency Identification Devices) that mostly targets authentication protocols. The enhanced models share similarities to the Bellare-Rogaway AKE (Authenticated Key Exchange) security model and consider adversaries that can compromise both types of participants in the protocol. In particular, modeling session resumption is non-trivial, given that session resumption tickets are essentially a state transmitted from one session to another and such link reveals information on the parties. On the positive side, we prove that TLS 1.3 protects the privacy of its users at least against passive adversaries, contrary to TLS 1.2, and against more powerful ones.

Smart contracts allow for exchange of coins according to program rules. While it is well known that so called bribery contracts can influence the incentive mechanism of a Nakamotostyle consensus, we present a more fine-grained bribery attack incentivizing a temporary censorship against a specific account. To this end, we introduce three different bribery contracts on the blockchain where each uniquely manipulates the rewards that a rational miner would receive. Additionally, we formalize the established bribery mechanisms as a Markov game and show for each game the existence of equilibria leading to successful censorships. Finally, we compare the bribery mechanisms with respect to the scalability of the attack costs and the strategic dominance. Our work is motivated by off-chain protocols including payment and state channels which require to publish transactions within a certain amount of time. In such off-chain protocols a temporary censorship attack can result into significant financial damage.

We provide new zero-knowledge argument of knowledge systems that work directly for a wide class of language, namely, ones involving the satisfiability of matrix-vector relations and integer relations commonly found in constructions of lattice-based cryptography. Prior to this work, practical arguments for lattice-based relations either have a constant soundness error ( 2/3 ), or consider a weaker form of soundness, namely, extraction only guarantees that the prover is in possession of a witness that “approximates” the actual witness. Our systems do not suffer from these limitations.

The core of our new argument systems is an efficient zero-knowledge argument of knowledge of a solution to a system of linear equations, where variables of this solution satisfy a set of quadratic constraints. This argument enjoys standard soundness, a small soundness error ( 1/poly ), and a complexity linear in the size of the solution. Using our core argument system, we construct highly efficient argument systems for a variety of statements relevant to lattices, including linear equations with short solutions and matrix-vector relations with hidden matrices.

Based on our argument systems, we present several new constructions of common privacy-preserving primitives in the standard lattice setting, including a group signature, a ring signature, an electronic cash system, and a range proof protocol. Our new constructions are one to three orders of magnitude more efficient than the state of the art (in standard lattice). This illustrates the efficiency and expressiveness of our argument system.

We construct public-key function-private predicate encryption for the ``small superset functionality,'' recently introduced by Beullens and Wee (PKC 2019). This functionality captures several important classes of predicates:

- Point functions. For point function predicates, our construction is equivalent to public-key function-private anonymous identity-based encryption.

- Conjunctions. If the predicate computes a conjunction, our construction is a public-key function-private hidden vector encryption scheme. This addresses an open problem posed by Boneh, Raghunathan, and Segev (ASIACRYPT 2013).

- $d$-CNFs and read-once conjunctions of $d$-disjunctions for constant-size $d$.

Our construction extends the group-based obfuscation schemes of Bishop et al. (CRYPTO 2018), Beullens and Wee (PKC 2019), and Bartusek et al. (EUROCRYPT 2019) to the setting of public-key function-private predicate encryption. We achieve an average-case notion of function privacy, which guarantees that a decryption key $sk_f$ reveals nothing about $f$ as long as $f$ is drawn from a distribution with sufficient entropy. We formalize this security notion as a generalization of the (enhanced) real-or-random function privacy definition of Boneh, Raghunathan, and Segev (CRYPTO 2013). Our construction relies on bilinear groups, and we prove security in the generic bilinear group model.

In this paper we put forth new one-message proof systems for several practical applications, like proving that an El Gamal ciphertext decrypts to a given value and correctness of a shuffle. Our proof systems are not based on any setup/trust assumption like the RO or the common reference string model and are perfectly sound, that is they are written proofs in the sense of mathematics.

Our proof systems satisfy a generalization of zero-knowledge (ZK) that we call harmless zero-knowledge (HZK). The simulator of an $O$-HZK proof for a relation over a language $L$ is given the additional capability of invoking an oracle $O$ relative to which $L$ is hard to decide. That is, the proof does not leak any knowledge that an adversary might not compute by itself interacting with an oracle $O$ that does not help to decide the language.

Unlike ZK, non-interactivity or perfect soundness do not contradict HZK and HZK can replace ZK in any application in which, basically, the computational assumptions used in the application hold even against adversaries with access to $O$. An $O$-HZK proof is WH, assuming some computational problem to be hard for adversaries with access to $O$, and strong-WI when quantifying over distributions that are indistinguishable by adversaries with access to $O$.

We provide a specific oracle $O$ that is enough powerful to make our main proof systems $O$-HZK but not trivial: indeed, we show concrete and practical cryptographic protocols that can be proven secure employing an $O$-HZK proof in the reduction and that are instead not achievable using traditional ZK (unless assuming a CRS/RO).

Efficient one-message proof systems with perfect soundness were only known for relations over bilinear groups and were proven only witness indistinguishable.

As byproduct, we also obtain a perfectly sound non-interactive ZAP and HZK proof for NP from a number-theoretic assumption over multiplicative groups of hidden order.

Classification of personal text messages has many useful applications in surveillance, e-commerce, and mental health care, to name a few. Giving applications access to personal texts can easily lead to (un)intentional privacy violations. We propose the first privacy-preserving solution for text classification that is provably secure. Our method, which is based on Secure Multiparty Computation (SMC), encompasses both feature extraction from texts, and subsequent classification with logistic regression and tree ensembles. We prove that when using our secure text classification method, the application does not learn anything about the text, and the author of the text does not learn anything about the text classification model used by the application beyond what is given by the classification result itself. We perform end-to-end experiments with an application for detecting hate speech against women and immigrants, demonstrating excellent runtime results without loss of accuracy.

In this paper, we introduce a new construction of lattice-based reusable fuzzy signature for remote user authentication that is secure against quantum computers. We define formal security models for the proposed construction, and we prove that it can achieve user authenticity, biometrics reusability and user privacy. In particular, the proposed new construction ensures that: 1) biometrics reusability is achieved such that fuzzy signatures remain secure even when the same biometrics is reused multiple times; 2) a third party having access to the communication channel between an authorized user and the authentication server cannot identify the authorized user.

Embedded microprocessors are an important component of reconfigurable architectures. Fine-grain (e.g., cycle-accurate) power analysis of such processors has been used to improve power and energy efficiency, and detect implementation vulnerabilities, in embedded applications. However, such analysis is difficult to conduct; it requires either specialized and often expensive equipment, or construction of test architectures using disparate acquisition and analysis tools. In this research, we expand the Flexible Open-source workBench fOr Side-channel analysis (FOBOS) to facilitate exact time-domain correlation of clock cycle and device state to power measurements, and to perform power analysis on a soft core processor. We first validate the fine-grain power analysis capabilities of FOBOS through cycle-accurate analysis of power consumption of AES encryption running on a soft core processor in the Spartan-6 FPGA. We then analyze the results in the context of Simple Power Analysis side-channel attacks, and confirm power correlation of certain instructions with Hamming Weight or Hamming Distance of secret key bytes. Finally, we show that an assumption of a pure Hamming Distance power model for load-to-register instructions is not sufficient for this embedded processor architecture, and that power models using both Hamming Distance and Hamming Weight should be considered for Differential Power Analysis.

Event date: 1 December 2020
Submission deadline: 2 December 2019

Event date: 31 August 2020
Submission deadline: 31 October 2019
Notification: 30 April 2020