This works studies the use of the AES block-cipher for Picnic-style signatures, which work in the multiparty-computation-in-the-head model. It applies advancements to arithmetic circuits for the computation of the AES S-box over multiparty computation in the preprocessing model to obtain an improvement of signature sizes of 40\% on average compared to using binary circuits for AES-128, AES-192 and AES-256 in combination with previous techniques. This work also discusses other methods for the computation of the S-box and provides insights into the reaches and limits of the multiparty-computation-in-the-head paradigm.

Dwork and Naor (FOCS’00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives. However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming the learning with errors (LWE) assumption holds with an explicit, efficently computable upper bound on the adversary’s advantage. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

The standard definition of security for digital signatures---existential unforgeability---does not ensure certain properties that protocol designers might expect. For example, in many modern signature schemes, one signature may verify against multiple distinct public keys. It is left to protocol designers to ensure that the absence of these properties does not lead to attacks. Modern automated protocol analysis tools are able to provably exclude large classes of attacks on complex real-world protocols such as TLS 1.3 and 5G. However, their abstraction of signatures (implicitly) assumes much more than existential unforgeability, thereby missing several classes of practical attacks. We give a hierarchy of new formal models for signature schemes that captures these subtleties, and thereby allows us to analyse (often unexpected) behaviours of real-world protocols that were previously out of reach of symbolic analysis. We implement our models in the Tamarin Prover, yielding the first way to perform these analyses automatically, and validate them on several case studies. In the process, we find new attacks on DRKey and SOAP's WS-Security, both protocols which were previously proven secure in traditional symbolic models.

The high latency and low throughput of blockchain protocols constitute one of the fundamental barriers for their wider adoption.Overlay protocols, notably the lightning network, have been touted as the most viable direction for rectifying this in practice. In this work we present for the first time a full formalisation and security analysis of the lightning network in the (global) universal composition setting that takes into account a global ledger functionality for which previous work [Badertscher et al., Crypto’17] has demonstrated its realisability by the Bitcoin blockchain protocol. As a result, our treatment delineates exactly how the security guarantees of the protocol depend on the properties of the underlying ledger. Moreover, we provide a complete and modular description of the core of the lightning protocol that highlights precisely its dependency to underlying basic cryptographic primitives such as digital signatures, pseudorandom functions, identity-based signatures and a less common two-party primitive, which we term a combined digital signature, that were originally hidden within the lightning protocol’s implementation.

Kerberos is one of the earliest network security protocols, providing authentication between clients and servers with the assistance of trusted servers. It remains widely used, notably as the default authentication protocol in Microsoft Active Directory (thus shipped with every major operating system), and is the ancestor of modern single sign-on protocols like OAuth and OpenID Connect. There have been many analyses of Kerberos in the symbolic (Dolev--Yao) model, which is more amenable to computer-aided verification tools than the computational model, but also idealizes messages and cryptographic primitives more. Reduction-based proofs in the computational model can provide assurance against a richer class of adversaries, and proofs with concrete probability analyses help in picking security parameters, but Kerberos has had no such analyses to date. We give a reduction-based security proof of Kerberos authentication and key establishment, focusing on the mandatory 3-party mode. We show that it is a secure authentication protocol under standard assumptions on its encryption scheme; our results can be lifted to apply to quantum adversaries as well. As has been the case for other real-world authenticated key exchange (AKE) protocols, the standard AKE security notion of session key indistinguishability cannot be proven for Kerberos since the session key is used in the protocol itself, breaking indistinguishability. We provide two positive results despite this: we show that the standardized but optional sub-session mode of Kerberos does yield secure session keys, and that the hash of the main session key is also a secure session key under Krawczyk's generalization of the authenticated and confidential channel establishment (ACCE) model.

We present a new efficient protocol for computing private set union (PSU). Here two semi-honest parties, each holding a dataset of known size (or of a known upper bound), wish to compute the union of their sets without revealing anything else to either party. Our protocol is in the OT hybrid model. Beyond OT extension, it is fully based on symmetric-key primitives. We motivate the PSU primitive by its direct application to network security and other areas. At the technical core of our PSU construction is the reverse private membership test RPMT protocol. In RPMT, the sender with input $x^*$ interacts with a receiver holding a set $X$. As a result, the receiver learns (only) the bit indicating whether $x^*$ is in $X$, while the sender learns nothing about the set $X$. (Previous similar protocols provide output to the opposite party, hence the term "reverse'' private membership.) We believe our RPMT abstraction and constructions may be a building block in other applications as well. We demonstrate the practicality of our proposed protocol with an implementation. For input sets of size $2^{20}$ and using a single thread, our protocol requires 238 seconds to securely compute the set union, regardless of the bit length of the items. Our protocol is amenable to parallelization. Increasing the number of threads from 1 to 32, our protocol requires only 13.1 seconds, a factor of $18.25 \times$ improvement. To the best of our knowledge, ours is the first protocol that reports on large-size experiments, makes code available, and avoids extensive use of computationally expensive public-key operations. (No PSU code is publicly available for prior work, and the only prior symmetric-key-based work reports on small experiments and focuses on the simpler 3-party, 1-corruption setting.)Our work improves reported PSU state of the art by factor up to $7,600\times$ for large instances.

In this paper we extend the attack landscape of bribing attacks on cryptocurrencies by presenting a new method, which we call Pay-To-Win (P2W). To the best of our knowledge, it is the first approach capable of facilitating double-spend collusion across different blockchains. Moreover, our technique can also be used to specifically incentivize transaction exclusion or (re)ordering. For our construction we rely on smart contracts to render the payment and receipt of bribes trustless for the briber as well as the bribee. Attacks using our approach are operated and financed out-of-band i.e., on a funding cryptocurrency, while the consequences are induced in a different target cryptocurrency. Hereby, the main requirement is that smart contracts on the funding cryptocurrency are able to verify consensus rules of the target. For a concrete instantiation of our P2W method, we choose Bitcoin as a target and Ethereum as a funding cryptocurrency. Our P2W method is designed in a way that reimburses collaborators even in the case of an unsuccessful attack. Interestingly, this actually renders our approach approximately one order of magnitude cheaper than comparable bribing techniques (e.g., the whale attack). We demonstrate the technical feasibility of P2W attacks through publishing all relevant artifacts of this paper, ranging from calculations of success probabilities to a fully functional proof-of-concept implementation, consisting of an Ethereum smart contract and a Python client.

Consider the representative task of designing a distributed coin-tossing protocol for $n$ processors such that the probability of heads is $X_0\in[0,1]$. This protocol should be robust to an adversary who can reset one processor to change the distribution of the final outcome. For $X_0=1/2$, in the information-theoretic setting, no adversary can deviate the probability of the outcome of the well-known Blum's ``majority protocol'' by more than $\frac1{\sqrt{2\pi n}}$, i.e., it is $\frac1{\sqrt{2\pi n}}$ insecure. In this paper, we study discrete-time martingales $(X_0,X_1,\dotsc,X_n)$ such that $X_i\in[0,1]$, for all $i\in\{0,\dotsc,n\}$, and $X_n\in\{0,1\}$. These martingales are commonplace in modeling stochastic processes like coin-tossing protocols in the information-theoretic setting mentioned above. In particular, for any $X_0\in[0,1]$, we construct martingales that yield $\frac12\sqrt{\frac{X_0(1-X_0)}{n}}$ insecure coin-tossing protocols. For $X_0=1/2$, our protocol requires only 40\% of the processors to achieve the same security as the majority protocol. The technical heart of our paper is a new inductive technique that uses geometric transformations to precisely account for the large gaps in these martingales. For any $X_0\in[0,1]$, we show that there exists a stopping time $\tau$ such that $$\mathbb{E}[\left\vert X_\tau-X_{\tau-1} \right\vert] \geq \frac2{\sqrt{2n-1}}\cdot X_0(1-X_0)$$ The inductive technique simultaneously constructs martingales that demonstrate the optimality of our bound, i.e., a martingale where the gap corresponding to any stopping time is small. In particular, we construct optimal martingales such that \textit{ any} stopping time $\tau$ has $$\mathbb{E}[\left\vert X_\tau-X_{\tau-1} \right\vert] \leq \frac1{\sqrt{n}}\cdot \sqrt{X_0(1-X_0)}$$ Our lower-bound holds for all $X_0\in[0,1]$; while the previous bound of Cleve and Impagliazzo (1993) exists only for positive constant $X_0$. Conceptually, our approach only employs elementary techniques to analyze these martingales and entirely circumvents the complex probabilistic tools inherent to the approaches of Cleve and Impagliazzo (1993) and Beimel, Haitner, Makriyannis, and Omri (2018). By appropriately restricting the set of possible stopping-times, we present representative applications to constructing distributed coin-tossing/dice-rolling protocols, discrete control processes, fail-stop attacking coin-tossing/dice-rolling protocols, and black-box separations.

In this paper we present a practical protocol for secure ridge regression. We develop the necessary secure linear algebra tools, using only basic arithmetic over prime fields. In particular, we will show how to solve linear systems of equations and compute matrix inverses efficiently, using appropriate secure random self-reductions of these problems. The distinguishing feature of our approach is that the use of secure fixed-point arithmetic is avoided entirely, while circumventing the need for rational reconstruction at any stage as well. We demonstrate the potential of our protocol in a standard setting for information-theoretically secure multiparty computation, tolerating a dishonest minority of passively corrupt parties. Using the MPyC framework, which is based on threshold secret sharing over finite fields, we show how to handle large datasets efficiently, achieving practically the same root-mean-square errors as Scikit-learn. Moreover, we do not assume that any (part) of the datasets is held privately by any of the parties, which makes our protocol much more versatile than existing solutions.

In this work, we present new low-data secret-key distinguishers and key-recovery attacks on reduced-round AES. The starting point of our work is “Mixture Differential Cryptanalysis” recently introduced at FSE/ToSC 2019, a way to turn the “multiple-of-8” 5-round AES secret-key distinguisher presented at Eurocrypt 2017 into a simpler and more convenient one (though, on a smaller number of rounds). By reconsidering this result on a smaller number of rounds, we present as our main contribution a new secret-key distinguisher on 3-round AES with the smallest data complexity in the literature (that does not require adaptive chosen plaintexts/ciphertexts), i.e. approximately half of the data necessary to set up a 3-round truncated differential distinguisher (which is currently the distinguisher in the literature with the lowest data complexity). E.g. for a probability of success of 95%, our distinguisher requires just 10 chosen plaintexts versus 20 chosen plaintexts necessary to set up the truncated differential one. Besides that, we present new competitive low-data key-recovery attacks on 3- and 4-round AES, both in the case in which the S-Box is known and in the case in which it is secret.

A multisignature scheme allows a group of signers to produce a joint signature on a common message, which is more compact than a collection of distinct signatures from all signers. Given this signature and the list of signers' public keys, a verifier is able to check if every signer in the group participated in signing. Recently, a multisignature scheme with public key aggregation has drawn a lot of attention due to their applications into the blockchain technology. Such multisignatures provide not only a compact signature, but also a compact aggregated public key, that is both the signature size and the public key size used to verify the correctness of the signature are independent from the number of signers. This is useful for a blockchain because of its duplication over a distributed network, and thus it is required to be as compact as possible. In this paper, we introduce a new multisignature scheme with such a feature. Our scheme is proven secure under the Decisional Diffie-Hellman assumption. In addition, in the presence of rogue key attacks, the security of our scheme is proven in the plain public key model.

In this paper we investigate the security of 5-round AES against two different attacks in an adaptive setting. We present a practical key-recovery attack on 5-round AES with a secret s-box that requires $2^{32}$ adaptively chosen ciphertexts, which is as far as we know a new record. In addition, we present a new and practical key-independent distinguisher for 5-round AES which requires $2^{27.2}$ adaptively chosen ciphertexts. While the data complexity of this distinguisher is in the same range as the current best 5-round distinguisher, it exploits new structural properties of 5-round AES.

In this paper, we analyze the implementation level fault vulnerabilities of deterministic lattice-based signature schemes. In particular, we extend the practicality of skip-addition fault attacks through exploitation of determinism in certain variants of Dilithium (Deterministic variant) and qTESLA signature scheme (originally submitted deterministic version), which are two leading candidates for the NIST standardization of post-quantum cryptography. We show that single targeted faults injected in the signing procedure allow to recover an important portion of the secret key. Though faults injected in the signing procedure do not recover all the secret key elements, we propose a novel forgery algorithm that allows the attacker to sign any given message with only the extracted portion of the secret key. We perform experimental validation of our attack using Electromagnetic fault injection on reference implementations taken from the pqm4 library, a benchmarking and testing framework for post quantum cryptographic implementations for the ARM Cortex-M4 microcontroller. We also show that our attacks break two well known countermeasures known to protect against skip-addition fault attacks. We further propose an efficient mitigation strategy against our attack that exponentially increases the attacker's complexity at almost zero increase in computational complexity.

We show how to perform a full-threshold $n$-party actively secure MPC protocol over a subgroup of order $p$ of an elliptic curve group $E(K)$. This is done by utilizing a full-threshold $n$-party actively secure MPC protocol over $\mathbb{F}_p$ in the pre-processing model (such as SPDZ), and then locally mapping the Beaver triples from this protocol into equivalent triples for the elliptic curve. This allows us to transform essentially any one-party protocol over an elliptic curve, into an $n$-party one. As an example we show how to transform the shuffle protocol of Abe into an $n$-party protocol. This application requires us to also give an MPC protocol to derive the switches in a Waksman network from a generic permutation, which may be of independent interest.

The differential uniformity, the boomerang uniformity, and the extended Walsh spectrum etc are important parameters to evaluate the security of S(substitution)-box. In this paper, we introduce efficient formulas to compute these cryptographic parameters of permutation polynomials of the form $x^rh(x^{(q-1)/d})$ over a finite field of $q=2^n$ elements, where $r$ is a positive integer and $d$ is a positive divisor of $q-1$. The computational cost of those formulas is proportional to $d$. We investigate differentially 4-uniform permutation polynomials of the form $x^rh(x^{(q-1)/3})$ and compute the boomerang spectrum and the extended Walsh spectrum of them using the suggested formulas when $4\le n\le 10$ is even, where $d=3$ is the smallest nontrivial $d$ for even $n$. We also investigate the differential uniformity of some permutation polynomials introduced in some recent papers for the case $d=2^{n/2}+1$

Estimating entropy of random processes is one of the fundamental problems of machine learning and property testing. It has numerous applications to anything from DNA testing and predictability of human behaviour to modeling neural activity and cryptography. We investigate the problem of Renyi entropy estimation for sources that form Markov chains. Kamath and Verdú (ISIT’16) showed that good mixing properties are essential for that task. We show that even with very good mixing time, estimation of min-entropy requires $\Omega(K^2)$ sample size, while collision entropy requires $\Omega(K^{3/2})$ samples, where K is the size of the alphabet. Our results hold both in asymptotic and non-asymptotic regimes. We achieve the results by applying Le Cam’s method to two Markov chains which differ by an appropriately chosen sparse perturbation; the discrepancy between these chains is estimated with help of perturbation theory. Our techniques might be of independent interest.

The past few decades have seen significant progress in practically realizable quantum technologies. It is well known since the work of Peter Shor that large scale quantum computers will threaten the security of most of the currently used public key cryptographic algorithms. This has spurred the cryptography community to design algorithms which will remain safe even with the emergence of large scale quantum computing systems. An effort in this direction is the currently ongoing post-quantum cryptography (PQC) competition, which has led to the design and analysis of many concrete cryptographic constructions. Among these, Lattice based algorithms have emerged to be promising candidates. Therefore, we focus on the efficient implementation of Ring-LWE based quantum-safe key-exchange algorithms. Further, deployment of hardware implementing such algorithms in critical applications requires security against implementation attacks. In this work, we design a side channel resistant post-quantum cryptoprocessor which supports NewHope-NIST, NewHope-USENIX and HILA5 key-exchange schemes. The implemented cryptoprocessor is highly optimized with minimal overhead due to the countermeasures. It requires about 13,500 LUTs and 8,100 FFs. Due to a significantly pipelined architecture, an operating speed of 406 MHz could be achieved on the latest 16nm FPGAs; resulting in a key-exchange time of only 158uS, 157uS and 148uS for the above mentioned designs respectively. We also present detailed area and performance metrics for different modules required for all the designs. To the best of our knowledge, this work presents the first side-channel leakage resistant post quantum accelerator. Furthermore, this is also the fastest hardware implementation of NewHope-NIST.

Random sampling is a fundamental primitive in modern algorithms, statistics, and machine learning, used as a generic method to obtain a small yet ``representative'' subset of the data. In this work, we investigate the robustness of sampling against adaptive adversarial attacks in a streaming setting: An adversary sends a stream of elements from a universe $U$ to a sampling algorithm (e.g., Bernoulli sampling or reservoir sampling), with the goal of making the sample ``very unrepresentative'' of the underlying data stream. The adversary is fully adaptive in the sense that it knows the exact content of the sample at any given point along the stream, and can choose which element to send next accordingly, in an online manner. Well-known results in the static setting indicate that if the full stream is chosen in advance (non-adaptively), then a random sample of size $\Omega(d / \varepsilon^2)$ is an $\varepsilon$-approximation of the full data with good probability, where $d$ is the VC-dimension of the underlying set system $(U, \mathcal{R})$. Does this sample size suffice for robustness against an adaptive adversary? The simplistic answer is \emph{negative}: We demonstrate a set system where a constant sample size (corresponding to a VC-dimension of $1$) suffices in the static setting, yet an adaptive adversary can make the sample very unrepresentative, as long as the sample size is (strongly) sublinear in the stream length, using a simple and easy-to-implement attack. However, this attack is ``theoretical only'', requiring the set system size to (essentially) be exponential in the stream length. This is not a coincidence: We show that in order to make the sampling algorithm robust against adaptive adversaries, the modification required is solely to replace the VC-dimension term $d$ in the sample size with the cardinality term $\log |\mathcal{R}|$. That is, the Bernoulli and reservoir sampling algorithms with sample size $\Omega(\log |\mathcal{R}|/\varepsilon^2)$ output a representative sample of the stream with good probability, even in the presence of an adaptive adversary. This nearly matches the bound imposed by the attack.

The fast correlation attack (FCA) is one of the most important cryptanalytic techniques against LFSR-based stream ciphers. In CRYPTO 2018, Todo et al. found a new property for the FCA and proposed a novel algorithm which was successfully applied to the Grain family of stream ciphers. Nevertheless, these techniques can not be directly applied to Grain-like small state stream ciphers with keyed update, such as Plantlet, Fruit-v2, and Fruit80. In this paper, we study the security of Grain-like small state stream ciphers by the fast correlation attack. We first observe that the number of required parity-check equations can be reduced when there are multiple different parity-check equations. With exploiting the Skellam distribution, we introduce a sufficient condition to identify the correct LFSR initial state and derive a new relationship between the number and bias of the required parity-check equations. Then a modified algorithm is presented based on this new relationship, which can recover the LFSR initial state no matter what the round key bits are. Under the condition that the LFSR initial state is known, an algorithm is given against the degraded system and to recover the NFSR state at some time instant, along with the round key bits. As cases study, we apply our cryptanalytic techniques to Plantlet, Fruit-v2 and Fruit-80. As a result, for Plantlet our attack takes $ 2^{73.75} $ time complexity and $ 2^{73.06} $ keystream bits to recover the full 80-bit key. Regarding Fruit-v2, $ 2^{55.34} $ time complexity and $ 2^{55.62} $ keystream bits are token to determine the secret key. As for Fruit-80, $2^{64.47}$ time complexity and $2^{62.82}$ keystream bits are required to recover the secret key. More flexible attacks can be obtained with lower data complexity at cost of increasing attack time. Especially, for Fruit-v2 a key recovery attack can be launched with data complexity of $2^{42.38}$ and time complexity of $2^{72.63}$. Moreover, we have implemented our attack methods on a toy version of Fruit-v2. The attack matches the expected complexities predicted by our theoretical analysis quite well, which proves the validity of our cryptanalytic techniques.

Verifiable computing (VC) is a complexity-theoretic method to secure the integrity of computations. The need is increasing as more computations are outsourced to untrusted parties, e.g., cloud platforms. Existing techniques, however, only deal with exact computations, without the capability of rounding (e.g., "$1.11 \times 2.22 = 2.4642$" is verifiable, but $1.11 \times 2.22 \simeq 2.46$" is not). Hence, in a long sequence of calculations (e.g., multiplications), the number of digits of the result keeps increasing and will quickly exceed the precision limit of the underlying system. Because of this limitation, VC is currently missing the opportunity in the whole AI space where approximate computations are unavoidable. In pursuit of the vision of verifiable AI computing, a solution to support the rounding operation is necessary. In this paper, we present an efficient verifiable computing scheme to achieve it. The main idea is to reduce the rounding operation into an efficient arithmetic circuit representation, and reuse the machinery of the Goldwasser, Kalai, and Rothblum's protocol (also known as the GRK protocol), the state-of-the-art interactive proof protocol. Specifically, we shift the algebraic structure from a field to a ring to better deal with the notion of "digits", and generalize the original GKR protocol over a ring. Then, we reduce the rounding operation to a low-degree polynomial in a ring, and present a novel, optimal circuit construction of an arbitrary polynomial to transform the rounding polynomial to an optimal arithmetic circuit representation. Moreover, we further optimize the proof generation cost for rounding by employing a Galois ring. We provide experimental results that show the efficiency of our scheme for approximate computations. For example, our implementation performed two orders of magnitude better than the existing GKR protocol for a nested 128x128 matrix multiplication of depth 12 on the 16-bit fixed-point arithmetic.

Seminal work by Juels, Catalano & Jakobsson delivered a verifiable, coercion-resistant voting system with quadratic complexity. This manuscript attempts to advance the state-of-the-art by delivering a voting system with equivalent security and linear complexity.

In recent literature, there has been a particular interest in studying nonce based AE schemes in the light of fault based attacks as they seem to present an automatic protection against Differential Fault Attacks (DFA). In this work, we present the first DFA on nonce based CAESAR scheme NORX. We demonstrate a scenario when faults introduced in NORX in parallel mode can be used to collide the internal state to produce an \emph{all-zero} state. We later show how this can be used to replay NORX despite being instantiated by different nonces, messages. Once replayed, we show how the key of NORX can be recovered using secondary faults and using the faulty tags. We use different fault models to showcase the versatility of the attack strategy. A detailed theoretical analysis of the expected number of faults required under various models is also furnished. Under the random bit flip model, around 1384 faults are to be induced to reduce the key space from $2^{128}$ to $2^{32}$ while the random byte flip model requires 136 faults to uniquely identify the key. To the best of our knowledge, this is the first fault attack that uses \emph{both internal} and \emph{classical differentials} to mount a DFA on a nonce based authenticated cipher which is otherwise believed to be immune to DFA.

The two-terminal key agreement problem with biometric or physical identifiers is considered. Two linear code constructions based on Wyner-Ziv coding are developed. The first construction uses random linear codes and achieves all points of the key-leakage-storage regions of the generated-secret and chosen-secret models. The second construction uses nested polar codes for vector quantization during enrollment and error correction during reconstruction. Simulations show that the nested polar codes achieve privacy-leakage and storage rates that improve on existing code designs. One proposed code achieves a rate tuple that cannot be achieved by existing methods.

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 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.7 million insertions/sec. Altogether, EverCrypt consists of over 124K verified lines of specs, code, and proofs, and it produces over 29K lines of C and 14K lines of 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.

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 $H_1(M) \oplus H_2(M)$ and the concatenation combiner $H_1(M) \parallel H_2(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 $H_2(H_1(IV,M),M)$ and the Zipper hash $H_2(H_1(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: (a) Does a hard-on-average language in NP imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes. Both one-way functions and problems in TFNP can be interpreted as promise-true distributional NP search problems---namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words,” It is no easier to find witnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true.” 
 This result follows from a more general study of interactive puzzles---a generalization of average-case hardness in NP—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 NP/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 the key security assumption of Proof-of-Work (PoW) based blockchains. However, the recent 51% attacks render this assumption unrealistic in practice. In this paper, we challenge this assumption against rational miners in the PoW-based blockchains in reality. In particular, we show that the current incentive mechanism may encourage rational miners to launch 51% attacks in two cases. In the first case, we consider a miner of a stronger blockchain launches 51% attacks on a weaker blockchain, where the two blockchains share the same mining algorithm. In the second case, we consider a miner rents mining power from cloud mining services to launch 51% attacks. As 51% attacks lead to double-spending, the miner can profit from these two attacks. If such double-spending is more profitable than mining, miners are more intended to launch 51% attacks rather than mine honestly. We formally model such behaviours as a series of actions through a Markov Decision Process. Our results show that, for most mainstream PoW-based blockchains, 51% attacks are feasible and profitable, so profit-driven miners are incentivised to launch 51% attacks to gain extra profit. In addition, we leverage our model to investigate the recent 51% attack on Ethereum Classic (on 07/01/2019), which is suspected to be an incident of 51% attacks. We provide insights on the attacker strategy and expected revenue, and show that the attacker’s strategy is near-optimal.

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 requires only a little bit of linear algebra. The derived probabilities are essentially identical to 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 efficient one-message proof systems for several practical applications, like proving that an El Gamal ciphertext (over a multiplicative group) decrypts to a given value and correctness of a shuffle. Our proof systems are built from multiplicative groups of hidden order, 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 and 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 witness hiding (WH) for distributions hard against adversaries with access to $O$, and strong-WI when quantifying over distributions that are indistinguishable by adversaries with access to $O$. Moreover, an $O$-HZK proof is witness indistinguishable (and the property does not depend on the oracle). We provide a specific oracle DHInvO that is enough powerful to make our main proof systems DHInvO-HZK but not trivial: indeed, we show concrete and practical cryptographic protocols that can be proven secure employing a DHInvO-HZK proof in the reduction and that are instead not achievable using traditional ZK (unless resorting to the CRS/RO models). 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, WH and HZK proof system for $NP$ relations from number-theoretic assumptions over multiplicative groups of hidden order. No non-interactive WH proof system for $NP$ (neither for simpler non-trivial relations) was previously known.

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.

CRAFT is a lightweight block cipher, designed to provide efficient protection against differential fault attacks. It is a tweakable cipher that includes 32 rounds to produce a ciphertext from a 64-bit plaintext using a 128-bit key and 64-bit public tweak. In this paper, compared to the designers' analysis, we provide a more detailed analysis of CRAFT against differential and zero-correlation cryptanalysis, aiming to provide better distinguishers for the reduced rounds of the cipher. Our distinguishers for reduced-round CRAFT cover a higher number of rounds compared to the designers' analysis. In our analysis, we observed that, for any number of rounds, the differential effect of CRAFT has an extremely higher probability compared to any differential trail. As an example, while the best trail for 11 rounds of the cipher has a probability of at least $2^{-80}$, we present a differential with probability $2^{-49.79}$, containing $2^{29.66}$ optimal trails, all with the same optimum probability of $2^{-80}$. Next, we use a partitioning technique, based on optimal expandable truncated trails to provide a better estimation of the differential effect on CRAFT. Thanks to this technique, we are able to find differential distinguishers for 9, 10, 11, 12, 13, and 14 rounds of the cipher in single tweak model with the probabilities of at least $2^{-40.20}$, $ 2^{-45.12} $, $ 2^{-49.79}$, $ 2^{-54.49}$, $ 2^{-59.13}$, and $ 2^{-63.80}$, respectively. These probabilities should be compared with the best distinguishers provided by the designers in the same model for 9 and 10 rounds of the cipher with the probabilities of at least $ 2^{-54.67}$ and $ 2^{-62.61}$, respectively. In addition, we consider the security of CRAFT against the new concept of related tweak zero-correlation (ZC) linear cryptanalysis and present a new distinguisher which covers 14 rounds of the cipher, while the best previous ZC distinguisher covered 13 rounds. Thanks to the related tweak ZC distinguisher for 14 rounds of the cipher, we also present 14 rounds integral distinguishers in related tweak mode of the cipher. Although the provided analysis does not compromise the cipher, we think it provides a better insight into the designing of CRAFT.

The basic concept behind the emergence of Internet of Things (IoT) is to connect as many objects to the Internet as possible in an attempt to make our lives better in some way. However, connecting everyday objects like your car or house to the Internet can open up major security concerns. In this paper, we present a novel security framework for the Message Queue Transport Telemetry (MQTT) protocol based on publish/subscribe messages in order to enhance secure and privacy-friendly Internet of Things services. MQTT has burst onto the IoT scene in recent years due to its lightweight design and ease of use implementation necessary for IoT. Our proposed solution provides 3 security levels. The first security level suits for lightweight data exchanges of non-tampered messages. The second security level enhances the privacy protection of data sources and data receivers. The third security level offers robust long-term security with mutual authentication for all parties. The security framework is based on light cryptographic schemes in order to be suitable for constrained and small devices that are widely used in various IoT use cases. Moreover, our solution is tailored to MQTT without using additional security overhead.

Authenticated encryption (AE) has been a vital operation in cryptography due to its ability to provide confidentiality, integrity, and authenticity at the same time. Its use has soared in parallel with widespread use of the Internet and has led to several new schemes. There have been studies investigating software performance of various schemes. However, the same is yet to be done for hardware. We present a comprehensive survey of hardware (specifically ASIC) performance of the most commonly used AE schemes in the literature. These schemes include encrypt-then-MAC combination, block cipher based AE modes, and the recently-introduced permutation-based AE scheme. For completeness, we implemented each scheme with various standardized block ciphers and/or hash algorithms, and their lightweight versions. Our evaluation targets minimizing the time-area product while maximizing the throughput on an ASIC platform. We used 45nm NANGATE Open Cell Library for syntheses. We present area, speed, time-area product, throughput, and power figures for both standard and lightweight versions of each scheme. We also provide an unbiased discussion on the impact of the structure and complexity of each scheme on hardware implementation. Our results reveal 13-30% performance boost in permutation-based AE compared to conventional schemes and they can be used as a benchmark in the ongoing AE competition CAESAR.

The tower field implementation of the $\mathbb{F}_{2^8}$ inverter is not only the key technique for compact implementations of the S-boxes of several internationally standardized block ciphers such as AES, Camellia, and SM4, but also the underlying structure many side-channel attack resistant AES implementations rely on. In this work, we conduct an exhaustive study of the tower field representations of the $\mathbb{F}_{2^8}$ inverter with normal bases by applying several state-of-the-art combinatorial logic minimization techniques. As a result, we achieve improved implementations of the AES, Camellia and SM4 S-boxes in terms of area footprint. Surprisingly, we are still able to improve the currently known most compact implementation of the AES S-box from CHES 2018 by 5.5 GE, beating the record again (Excluding this work, the latest improvement was proposed at CHES 2018, which achieves 11.75 GE improvement over the optimal implementation at the time). For Camellia and SM4, the improvements are even more significant. The Verilog codes of our implementations of the AES, Camellia and SM4 S-boxes are openly available.

In this paper we give nearly tight reductions for modern implicitly authenticated Diffie-Hellman protocols in the style of the Signal and Noise protocols, which are extremely simple and efficient. Unlike previous approaches, the combination of nearly tight proofs and efficient protocols enables the first real-world instantiations for which the parameters can be chosen in a theoretically sound manner, i.e., according to the bounds of the reductions. Specifically, our reductions have a security loss which is only linear in the number of users $\mu$ and constant in the number of sessions per user $\ell$. This is much better than most other key exchange proofs which are typically quadratic in the product $\mu \ell$. Combined with the simplicity of our protocols, this implies that our protocols are more efficient than the state of the art when soundly instantiated. We also prove that our security proofs are optimal: a linear loss in the number of users is unavoidable for our protocols for a large and natural class of reductions.

Oblivious RAM (ORAM) is a cryptographic primitive that allows a client to hide access pattern to its data encrypted and stored at a remote server. Traditionally, ORAM algorithms assume the server acts purely as a storage device. Under this assumption, ORAM has at least $\log(N)$ bandwidth blowup for $N$ data entries. After three decades of improvements, ORAM algorithms have reached the optimal logarithmic bandwidth blowup. Nonetheless, in many practical use-cases, a constant bandwidth overhead is desirable. To this purpose, Devadas et al. (TCC 2016) formalized the server computation model for ORAM and proposed Onion ORAMwhich relies on homomorphic computation to achieve constant worst-case bandwidth blowup. This line of work is generally believed to be purely theoretical, due to the large overheads of homomorphic computation. In this paper, we present Onion Ring ORAM, the first efficient constant bandwidth ORAM scheme in the single server model, based on the Onion ORAM construction and the leveled version of the TFHE scheme by Chillotti et al.. We propose a series of improvements, most notably including a more efficient homomorphic permutation protocol. We implement Onion Ring ORAM and show that it can outperform state-of-the-art logarithmic-bandwidth ORAM like Path ORAMs and Ring ORAM when the network throughput is limited. Under one setting, our construction reduces monetary cost per access by 40\% and end-to-end latency by 35\% over Ring ORAM.

The underlying fundaments of blockchain are cryptography and cryptographic concepts that provide reliable and secure decentralized solutions. Although many recent papers study the use-cases of blockchain in different industrial areas, such as finance, health care, legal relations, IoT, information security, and consensus building systems, only few studies scrutinize the cryptographic concepts used in blockchain. To the best of our knowledge, there is no Systematization of Knowledge (SoK) that gives a complete picture of the existing cryptographic concepts which have been deployed or have the potential to be deployed in blockchain. In this paper, we thoroughly review and systematize all cryptographic concepts which are already used in blockchain. Additionally, we give a list of cryptographic concepts which have not yet been applied but have big potentials to improve the current blockchain solutions. We also include possible instantiations of these cryptographic concepts in the blockchain domain. Last but not least, we explicitly postulate 21 challenging problems that cryptographers interested in blockchain can work on.

Secure multi-party computation (MPC) allows multiple parties to jointly compute the output of a function while preserving the privacy of any individual party's inputs to that function. As MPC protocols transition from research prototypes to real-world applications, the usability of MPC-enabled applications is increasingly critical to their successful deployment and wide adoption. Our Web-MPC platform, designed with a focus on usability, has been deployed for privacy-preserving data aggregation initiatives with the City of Boston and the Greater Boston Chamber of Commerce. After building and deploying an initial version of this platform, we conducted a heuristic evaluation to identify additional usability improvements and implemented corresponding application enhancements. However, it is difficult to gauge the effectiveness of these changes within the context of real-world deployments using traditional web analytics tools without compromising the security guarantees of the platform. This work consists of two contributions that address this challenge: (1) the Web-MPC platform has been extended with the capability to collect web analytics using existing MPC protocols, and (2) this capability has been leveraged to conduct a usability study comparing the two version of Web-MPC (before and after the heuristic evaluation and associated improvements). While many efforts have focused on ways to enhance the usability of privacy-preserving technologies, this study can serve as a model for using a privacy-preserving data-driven approach in evaluating or enhancing the usability of privacy-preserving websites and applications deployed in real-world scenarios. The data collected in this study yields insights about the interplay between usability and security that can help inform future implementations of applications that employ MPC.

Homomorphic encryption (HE) is often viewed as impractical, both in communication and computation. Here we provide an additively homomorphic encryption scheme based on (ring) LWE with nearly optimal rate ($1-\epsilon$ for any $\epsilon>0$). Moreover, we describe how to compress many FHE ciphertexts that may have come from a homomorphic evaluation (e.g., of the Gentry-Sahai-Waters (GSW) scheme), into fewer high-rate ciphertexts. Using our high-rate HE scheme, we are able for the first time to describe a single-server private information retrieval (PIR) scheme with sufficiently low computational overhead so as to be practical for large databases. Single-server PIR inherently requires the server to perform at least one bit operation per database bit, and we describe a rate-(4/9) scheme with computation which is not so much worse than this inherent lower bound. In fact it is probably faster than whole-database AES encryption -- specifically under 1.8 mod-$q$ multiplication per database byte, where $q$ is about 50 to 60 bits. Asymptotically, the computational overhead of our PIR scheme is $\tilde{O}(\log \log \secparam + \log \log \log N)$, where $\secparam$ is the security parameter and $N$ is the number of database files, which are assumed to be sufficiently large.

In this work, we define and construct fully homomorphic non-interactive zero knowledge (FH-NIZK) and non-interactive witness-indistinguishable (FH-NIWI) proof systems. We focus on the NP complete language $L$, where, for a boolean circuit $C$ and a bit $b$, the pair $(C,b) \in L$ if there exists an input $w$ such that $C(w)=b$. For this language, we call a non-interactive proof system 'fully homomorphic' if, given instances $(C_i,b_i) \in L$ along with their proofs $\Pi_i$, for $i \in \{1,\ldots,k\}$, and given any circuit $D:\{0,1\}^k \rightarrow \{0,1\}$, one can efficiently compute a proof $\Pi$ for $(C^*,b) \in L$, where $C^*(w^{(1)}, \ldots,w^{(k)})=D(C_1(w^{(1)}),\ldots,C_k(w^{(k)}))$ and $D(b_1,\ldots,b_k)=b$. The key security property is 'unlinkability': the resulting proof $\Pi$ is indistinguishable from a fresh proof of the same statement. Our first result, under the Decision Linear Assumption (DLIN), is an FH-NIZK proof system for L in the common random string model. Our more surprising second result (under a new decisional assumption on groups with bilinear maps) is an FH-NIWI proof system that requires no setup.

The Minrank (MR) problem is a computational problem closely related to attacks on code- and multivariate-based schemes. In this paper we revisit the so-called Kipnis-Shamir (KS) approach to this problem. We extend previous complexity analysis by exposing non-trivial syzygies through the analysis of the Jacobian of the resulting system, with respect to a group of variables. We focus on a particular set of instances that yield a very overdetermined system which we refer to as ``superdetermined''. We provide a tighter complexity estimate for such instances and discuss its implications for the key recovery attack on some multivariate schemes. For example, in HFE the speedup is roughly a square root.

We present a post-quantum key agreement scheme that does not require distinguishing between the initiator and the responder. This scheme is based on elliptic curve isogenies and can be viewed as a variant of the well-known SIDH protocol. Then, we present an efficient countermeasure against a side-channel attack that applies to both static and ephemeral versions of SIDH and our scheme. Finally, we show how to obtain an isogeny-based password-authenticated key exchange protocol based on our scheme by applying a construction based on SIDH. Security and computational complexities summaries are also presented.

We first introduce a family of binary $pq^2$ -periodic sequences based on the Euler quotients modulo $pq$, where $p$ and $q$ are two distinct odd primes and $p$ divides $q - 1$. The minimal polynomials and linear complexities are determined for the proposed sequences provided that $2^{q-1} \not \equiv 1 \pmod q^2$ . The results show that the proposed sequences have high linear complexities.

A key step in Regev's (2009) reduction of the Discrete Gaussian Sampling (DGS) problem to that of solving the Learning With Errors (LWE) problem is a statistical test required for verifying possible solutions to the LWE problem. In this work, we work out a concrete lower bound on the success probability and its effect in determining an upper bound on the tightness gap of the reduction. The success probability is determined by the value of the rejection threshold $t$ of the statistical test. Using a particular value of $t$, Regev showed that asymptotically, the success probability of the test is exponentially close to one for all values of the LWE error $\alpha\in(0,1)$. From the concrete analysis point of view, the value of the rejection threshold used by Regev is sub-optimal. It leads to considering the lattice dimension to be as high as 400000 to obtain somewhat meaningful tightness gap. We show that by using a different value of the rejection threshold and considering $\alpha$ to be at most $1/\sqrt{n}$ results in the success probability going to 1 for small values of the lattice dimension. Consequently, our work shows that it may be required to modify values of parameters used in an asymptotic analysis to obtain much improved and meaningful concrete security.

TRIFLE is a Round 1 candidate of the NIST Lightweight Cryptography Standardization process. In this paper, we present an interesting 1-round iterative differential characteristic of the underlying block cipher TRIFLE-BC used in TRIFLE, which holds with probability of $2^{-3}$. Consequently, it allows to mount distinguishing attack on TRIFLE-BC for up to 43 (out of 50) rounds with data complexity $2^{124}$ and time complexity $2^{124}$. Most importantly, with such an iterative differential characteristic, the forgery attack on TRIFLE can reach up to 21 (out of 50) rounds with data complexity $2^{63}$ and time complexity $2^{63}$. Finally, to achieve key recovery attack on reduced TRIFLE, we construct a differential characteristic covering three blocks by carefully choosing the positions of the iterative differential characteristic. As a result, we can mount key-recovery attack on TRIFLE for up to 11 rounds with data complexity $2^{63}$ and time complexity $2^{104}$. Although the result in this paper cannot threaten the security margin of TRIFLE, we hope it can help further understand the security of TRIFLE.

Oblivious transfer is one of the main pillars of modern cryptography and plays a major role as a building block for other more complex cryptographic primitives. In this work, we present an efficient and versatile framework for oblivious transfer (OT) using one-round key-exchange (ORKE), a special class of key exchange (KE) where only one message is sent from each party to the other. Our contributions can be summarized as follows: i) We carefully analyze ORKE schemes and introduce new security definitions. Namely, we introduce a new class of ORKE schemes, called Alice-Bob one-round key-exchange (A-B ORKE), and the definitions of message and key indistinguishability. ii) We show that OT can be obtained from A-B ORKE schemes fulfilling message and key indistinguishability. We accomplish this by designing a new efficient, versatile and universally composable framework for OT in the Random Oracle Model (ROM). The efficiency of the framework presented depends almost exclusively on the efficiency of the A-B ORKE scheme used since all other operations are linear in the security parameter. Universally composable OT schemes in the ROM based on new hardness assumptions can be obtained from instantiating our framework. Examples are presented using the classical Diffie-Hellman KE, RLWE-based KE and Supersingular Isogeny Diffie-Hellman KE.

Recently, Castryck, Lange, Martindale, Panny, and Renes proposed CSIDH (pronounced "sea-side") as a candidate post-quantum "commutative group action." It has attracted much attention and interest, in part because it enables noninteractive Diffie--Hellman-like key exchange with quite small communication. Subsequently, CSIDH has also been used as a foundation for digital signatures. In 2003--04, Kuperberg and then Regev gave asymptotically subexponential quantum algorithms for "hidden shift" problems, which can be used to recover the CSIDH secret key from a public key. In late 2011, Kuperberg gave a follow-up quantum algorithm called the collimation sieve ("c-sieve" for short), which improves the prior ones, in particular by using exponentially less quantum memory and offering more parameter tradeoffs. While recent works have analyzed the concrete cost of the original algorithms (and variants) against CSIDH, nothing of this nature was previously available for the c-sieve. This work fills that gap. Specifically, we generalize Kuperberg's collimation sieve to work for arbitrary finite cyclic groups, provide some practical efficiency improvements, give a classical (i.e., non-quantum) simulator, run experiments for a wide range of parameters up to the actual CSIDH-512 group order, and concretely quantify the complexity of the c-sieve against CSIDH. Our main conclusion is that the proposed CSIDH parameters provide relatively little quantum security beyond what is given by the cost of quantumly evaluating the CSIDH group action itself (on a uniform superposition). For example, the cost of CSIDH-512 key recovery is only about $2^{16}$ quantum evaluations using $2^{40}$ bits of quantumly accessible classical memory (plus relatively small other resources). This improves upon a prior estimate of $2^{32.5}$ evaluations and $2^{31}$ qubits of quantum memory, for a variant of Kuperberg's original sieve. Under the plausible assumption that quantum evaluation does not cost much more than what is given by a recent "best case" analysis, CSIDH-512 can therefore be broken using significantly less than $2^{64}$ quantum T-gates. This strongly invalidates its claimed NIST level 1 quantum security, especially when accounting for the MAXDEPTH restriction. Moreover, under analogous assumptions for CSIDH-1024 and -1792, which target higher NIST security levels, except near the high end of the MAXDEPTH range even these instantiations fall short of level 1.

We show the applicability of Simon's period finding quantum algorithm to the cryptanalysis of several tweakable enciphering schemes (TESs), namely, CMC, EME, XCB, TET and FAST. For all of the five TESs, we show distinguishing attacks, while for XCB, TET and FAST, the attacks reveal portions of the secret keys.

In this work, we discuss our successful efforts for industry deployment of a cryptographic secure computation protocol. The problem we consider is privately computing aggregate conversion rate of advertising campaigns. This underlying functionality can be abstracted as Private Intersection-Sum (PI-Sum) with Cardinality. In this setting two parties hold datasets containing user identifiers, and one of the parties additionally has an integer value associated with each of its user identifiers. The parties want to learn the number of identifiers they have in common and the sum of the integer values associated with these users without revealing any more information about their private inputs. We identify the major properties and enabling factors which make the deployment of a cryptographic protocol possible, practical, and uniquely positioned as a solution for the task at hand. We describe our deployment setting and the most relevant efficiency measure, which in our setting is communication overhead rather than computation. We also present a monetary cost model that can be used as a unifying cost measure and the computation model which reflect out use-case: a low-priority batch computing. We present three PI-Sum with cardinality protocols: our currently deployed protocol, which relies on a Diffie-Hellman style double masking, and two new protocols which leverage more recent techniques for private set intersection (PSI) that use Random Oblivious Transfer and encrypted Bloom filters. We compare the later two protocol with our original solution when instantiated with different additively homomorphic encryption schemes. We implement our constructions and compare their costs. We also compare with recent generic approaches for computing on the intersection of two datasets and show that our best protocol has monetary cost that is 20× less than the best known generic approach.

Leakage assessment of cryptographic implementations with side-channel analysis relies on two important assumptions: leakage model and the number of side-channel traces. In the context of profiled side-channel attacks, having these assumptions correctly defined is a sufficient first step to evaluate the security of a crypto implementation with template attacks. This method assumes that the features (leakages or points of interest) follow a univariate or multi-variate Gaussian distribution for the estimation of the probability density function. When trained machine learning or neural network models are employed as classifiers for profiled attacks, a third assumption must be taken into account that it the correctness of the trained model or learning parameters. It was already proved that convolutional neural networks have advantages for side-channel analysis like bypassing trace misalignments and defeating first-order masking countermeasures in software implementations. However, if this trained model is incorrect and the test classification accuracy is close to random guessing, the correctness of the two first assumptions (number of traces and leakage model) will be insufficient and the security of the target under evaluation can be overestimated. This could lead to wrong conclusions in leakage certifications. One solution to verify if the trained model is acceptable relies on the identifying of input features that the neural network considers as points of interest. In this paper, we implement the assessment of neural network models by using the proposed backward propagation path method. Our method is employed during the profiling phase as a tool to verify what the neural network is learning from side-channel traces and to support the optimization of hyper-parameters. The method is tested against masked AES implementation. One of the main results highlights the importance of L2 regularization for the automated points of interest selection from a neural network.

In this work, we present the rst highly-optimized implementation of Supersingular Isogeny Key Encapsulation (SIKE) submitted to NIST's second round of post quantum standardization process, on 64-bit ARMv8 processors. To the best of our knowledge, this work is the rst optimized implementation of SIKE round 2 on 64-bit ARM over SIKEp434 and SIKEp610. The proposed library is explicitly optimized for these two security levels and provides constant-time implementation of the SIKE mechanism on ARMv8-powered embedded devices. We adapt dierent optimization techniques to reduce the total number of underlying arithmetic operations on the led level. In particular, the benchmark results on embedded processors equipped with ARM Cortex- [email protected] show that the entire SIKE round 2 key encapsulation mechanism takes only 84 ms at NIST's security level 1. Considering SIKE's extremely small key size in comparison to other candidates, our result implies that SIKE is one of the promising candidates for key encapsulation mechanism on embedded devices in the quantum era.

We show how to combine a fully-homomorphic encryption scheme with linear decryption and a linearly-homomorphic encryption schemes to obtain constructions with new properties. Specifically, we present the following new results. (1) Rate-1 Fully-Homomorphic Encryption: We construct the first scheme with message-to-ciphertext length ratio (i.e., rate) $1-\sigma$ for $\sigma = o(1)$. Our scheme is based on the hardness of the Learning with Errors (LWE) problem and $\sigma$ is proportional to the noise-to-modulus ratio of the assumption. Our building block is a construction of a new high-rate linearly-homomorphic encryption. One application of this result is the first general-purpose secure function evaluation protocol in the preprocessing model where the communication complexity is within additive factor of the optimal insecure protocol. (2) Fully-Homomorphic Time-Lock Puzzles: We construct the first time-lock puzzle where one can evaluate any function over a set of puzzles without solving them, from standard assumptions. Prior work required the existence of sub-exponentially hard indistinguishability obfuscation.

Logic locking has been proposed as an obfuscation technique to protect outsourced IC designs from Intellectual Property (IP) piracy by untrusted entities in the design and fabrication process. It obfuscates the netlist by adding extra key-gates, to mislead an adversary, whose aim is to reverse engineer the netlist. The correct functionality will be obtained only if a correct key is applied to the key-gates. The key is written into a nonvolatile memory (NVM) after the fabrication by the IP owner. In the past several years, the focus of the research community has been mostly on Oracle-guided attacks, such as SAT attacks, on logic locking and proposing proper countermeasures against such attacks. However, none of the reported researches in the literature has ever challenged a more fundamental assumption of logic locking, which is the security of the key itself. In other words, if an adversary can read out the correct key after insertion, the security of the entire scheme is broken, no matter how robust is the logic-locking scheme. In this work, we first review possible adversaries for the locked circuits and their capabilities. Afterward, we demonstrate that even with the assumption of having a tamper and read-proof memory for the key storage, which is not vulnerable to any physical attacks, the key transfer between the memory and the key-gates through registers and buffers make the key extraction by an adversary possible. To support our claim, we implemented a proof-of-concept locked circuit as well as one of the common logic locking benchmarks on a 28 nm Flash-based FPGA and extract their keys using optical probing. Finally, we discuss the feasibility of the proposed attack in different scenarios and propose potential countermeasures.

Secure multi-party computation permits evaluation of any desired functionality on private data without disclosing the data to the participants and is gaining its popularity due to increasing collection of user, customer, or patient data and the need to analyze data sets distributed across different organizations without disclosing them. Because adoption of secure computation techniques depends on their performance in practice, it is important to continue improving their performance. In this work, we focus on common non-trivial operations used by many types of programs, and any advances in their performance would impact the runtime of programs that rely on them. In particular, we treat the operation of reading or writing an element of an array at a private location and integer multiplication. The focus of this work is secret sharing setting with honest majority in the semi-honest security model. We demonstrate improvement of the proposed techniques over prior constructions via analytical and empirical evaluation.

We present a framework for the study of a learning problem over abstract groups, and introduce a new technique which allows for public-key encryption using generic groups. We proved, however, that in order to obtain a quantum resistant encryption scheme, commutative groups cannot be used to instantiate this protocol.

The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor's celebrated algorithm. Successful solutions to this problems over various commutative groups allow to efficiently perform number-theoretic tasks such as factoring or finding discrete logarithms. The latest successful generalization (Eisentraeger et al. STOC 2014) considers the problem of finding a full-rank lattice as the hidden subgroup of the continuous vector space $\mathbb{R}^m$, even for large dimensions $m$. It unlocked new cryptanalytic algorithms (Biasse-Song SODA 2016, Cramer et al. EUROCRYPT 2016 and 2017), in particular to find mildly short vectors in ideal lattices. The cryptanalytic relevance of such a problem raises the question of a more refined and quantitative complexity analysis. In the light of the increasing physical difficulty of maintaining a large entanglement of qubits, the degree of concern may be different whether the above algorithm requires only linearly many qubits or a much larger polynomial amount of qubits. This is the question we start addressing with this work. We propose a detailed analysis of (a variation of) the aforementioned HSP algorithm, and conclude on its complexity as a function of all the relevant parameters. Our modular analysis is tailored to support the optimization of future specialization to cases of cryptanalytic interests. We suggest a few ideas in this direction.

Leakages during the signing process, including partial key exposure and partial (or complete) randomness exposure, may be devastating for the security of digital signatures. In this work, we investigate the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage. To this end, we present a generic key recovery attack that relies on minimum leakage of randomness, and then theoretically connect it to a variant of Integer-LWE (ILWE) problem. The ILWE problem, introduced by Bootle et al. at Asiacrypt 2018, is to recover the secret vector ${\bf s}$ given polynomially many samples of the form $({\bf a}, \langle {\bf a}, {\bf s} \rangle + e) {\color{black}\in \mathbb{Z}^{n+1}}$, and it is solvable if the error $e {\color{black}\in \mathbb{Z}}$ is not superpolynomially larger than the inner product $\langle {\bf a}, {\bf s} \rangle$. However, in our variant (we call the variant FS-ILWE problem in this paper), ${\bf a}{\color{black}\in \mathbb{Z}^{n}}$ is a sparse vector whose coefficients are NOT independent any more, and $e$ is related to ${\bf a}$ and ${\bf s}$ as well. We prove that the FS-ILWE problem can be solved in polynomial time, and present an efficient algorithm to solve it. Our generic key recovery method directly implies that many lattice-based Fiat-Shamir signatures will be totally broken with one (deterministic or probabilistic) bit of randomness leakage per signature. Our attack has been validated by experiments on two NIST PQC signatures Dilithium and qTESLA. For example, as to Dilithium-III of $125$-bit quantum security, the secret key will be recovered within $10$ seconds over an ordinary PC desktop, with about one million signatures. Similarly, key recovery attacks on Dilithium under other parameters and qTESLA will be completed within $20$ seconds and $31$ minutes respectively. In addition, we also present a non-profiled attack to show how to obtain the required randomness bit in practice through power analysis attacks on a proof-of-concept implementation of polynomial addition. The experimental results confirm the practical feasibility of our method.

This paper gives a new generalized key-recovery model of related-key rectangle attacks on block ciphers with linear key schedules. The model is quite optimized and applicable to various block ciphers with linear key schedule. As a proof of work, we apply the new model to two very important block ciphers, i.e. SKINNY and GIFT, which are basic modules of many candidates of the Lightweight Cryptography (LWC) standardization project by NIST. For SKINNY, we reduce the complexity of the best previous 27-round related-tweakey rectangle attack on SKINNY-128-384 from $2^{331}$ to $2^{294}$. In addition, the first 28-round related-tweakey rectangle attack on SKINNY-128-384 is given, which gains one more round than before. For the case of GIFT-64, we give the first 24-round related-key rectangle attack with a time complexity $2^{91.58}$, while the best previous attack on GIFT-64 only reaches 23 rounds at most.

Satoshi Nakamoto's Blockchain allows to build publicly verifiable and almost immutable ledgers, but sometimes privacy has to be factored in. In this work an original protocol is presented that allows sensitive data to be stored on a ledger where its integrity may be publicly verified, but its privacy is preserved and owners can tightly manage the sharing of their information with efficient revocation.

Block cipher modes of operation provide a way to securely encrypt using a block cipher, and different modes of operation achieve different tradeoffs of security, performance and simplicity. In this paper, we present a new authenticated encryption scheme that is designed for the lightweight cryptography setting, but can be used in standard settings as well. Our mode of encryption is extremely simple, requiring only a single block cipher primitive (in forward direction) and minimal padding, and supports streaming (online encryption). In addition, our mode achieves very strong security bounds, and can even provide good security when the block size is just 64 bits. As such, it is highly suitable for lightweight settings, where the lifetime of the key and/or overall amount encrypted may be high. Our new scheme can be seen as an improved version of CCM that supports streaming, and provides much better bounds.

In this work, we present a fast parallel architecture to perform supersingular isogeny key encapsulation (SIKE). We propose and implement a fast isogeny accelerator architecture that uses fast and parallelized isogeny formulas. On top of our isogeny accelerator, we build a novel architecture for the SIKE primitive, which provides both quantum and IND-CCA security. Since SIKE can support static keys, we propose and implement additional differential power analysis countermeasures. We synthesized this architecture on the Xilinx Artix-7, Virtex-7, and Kintex UltraScale+ FPGA families. Over Virtex-7 FPGA's, our constant-time implementations are roughly 14% faster than the state-of-the-art with a better area-time product. At the NIST security level 5 on a Kintex UltraScale+ FPGA, we can execute the entire SIKE protocol in 15.3 ms. This work continues to improve the speed of isogeny-based computations and also features all parameter sets of the SIKE round 2 specification, with results applicable to NIST's post-quantum standardization process.

The Trusted Platform Module (TPM) version 2.0, which has been demonstrated as a key element of Industry 4.0, presents a two-phase key exchange primitive for secure communications between Industry 4.0 components. The key exchange primitive of TPM 2.0 can be used to implement three widely-standardized authenticated key exchange protocols: the Full Unified Model, the Full MQV, and the SM2 key exchange protocols. However, vulnerabilities have been found in all of these protocols. Fortunately, it seems that the protections offered by TPM chips can mitigate these vulnerabilities. In this paper, we present a security model which captures TPM's protections on keys and protocols' computation environments and in which multiple protocols can be analyzed in a unified way. Based on the unified security model, we give the first formal security analysis of the key exchange primitive of TPM 2.0, and the analysis results show that, with the help of hardware protections of TPM chips, the key exchange primitive indeed satisfies the well-defined security property of our security model, but unfortunately under some impractical limiting conditions, which would prevent the application of the key exchange primitive in real-world networks. To make TPM 2.0 applicable to real-world networks, we present a revision of the key exchange primitive of TPM 2.0, which can keep secure without the limiting conditions. We give a rigorous analysis of our revision, and the results show that our revision achieves not only the basic security property of modern AKE security models but also some further security properties.

One of the main goals of securing data transmission is focused on the security of cloud data storage. In this paper, we describe several cryptographic techniques which can be used to address the relevant threats and security goals for analyzing cloud computing security. Private semi-trusted clouds, allow researchers to design private clouds by using cryptographic techniques, to protect the semi-trusted ones. Finally, we elaborate on semi-trusted clouds which are related to real-world deployments of cloud resources, and how optimizing cryptographic protocols, would indeed lead to the usage of this certain cloud and therefore practical ways of securing this type of data.

A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and by Boyar and Peralta in 2008. We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions $\Sigma^n_k$ and counting functions $E^n_k$ with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric $\Sigma^8_4$ and the counting $E^8_4$ functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.

Since the seminal result of Kilian, Oblivious Transfer has proven to be a fundamental primitive in cryptography. In such a scheme, a user is able to gain access to an element owned by a server, without learning more than this single element, and without the server learning which element the user has accessed. This primitive has received a lot of study in the literature, among which very few schemes are based on lattices. The recent NIST call for post-quantum encryption and signature schemes has revived the interest for cryptographic protocols based on post-quantum assumptions and the need for a secure post-quantum oblivious transfer scheme. In this paper, we show how to construct an oblivious transfer scheme based on lattices, from a collision-resistant chameleon hash scheme (CH) and a CCA encryption scheme accepting a smooth projective hash function (SPHF). Note that our scheme does not rely on random oracles and provides UC security against adaptive corruptions assuming reliable erasures.

Oblivious Transfer has played a crucial role in the design of secure multi party computation. Nevertheless, there are not many practical solutions that achieve simulation based security and at the same time instantiable based on different assumptions. In this work, we consider a simulation based security notion that we call endemic security. We show how to construct highly efficient oblivious transfer in the random oracle model that achieves endemic security under a wide range of assumptions, among them DDH, CDH, LWE and coding based assumptions. We construct a secure oblivious transfer based on DDH that takes only a single communication round which allows significant performance gains. We also instantiate our oblivious transfer with the Crystals.Kyber key agreement. Our implementation shows that both instantiations can be computed in under one millisecond. Further, we revisit, correct and improve existing oblivious transfer extension techniques. We provide an implementation of an oblivious transfer extension protocol in the ideal cipher model that is actively secure, processing up to 23 million OTs per second and up to 10 times faster than previous secure implementations. We also show that our framework can compute endemically secure OT extension and the base OTs in just two rounds.

We revisit the framework of Commodity-based Cryptography presented by Beaver (STOC'97) with a focus on updating the framework to fit with modern multiparty computation (MPC) protocols. We study the possibility of replacing the well-known preprocessing model with a commodity-based setting, where a set of independent servers (some of which may be corrupt) provide clients with correlated randomness. From this, the clients then distill correct and secure correlated randomness that they can use during the online phase of the MPC protocol. Beaver showed how to do OT with semi-honest security in the commodity setting. We improve on Beaver's result as follows: In a model where one of two clients and a constant fraction of the servers may be maliciously corrupted, we obtain unconditionally secure multiplication triples and oblivious linear evaluations (OLEs) such that the amortized communication cost of one triple/OLE is a constant number of field elements (when the field is sufficiently large). We also report on results from an implementation of the OLE protocol. Finally, we suggest an approach to practical realization of a commodity based system where servers need no memory and can be accessed asynchronously by clients, but still a maliciously corrupt client cannot get data he should not have access to.

This work presents Arcula, a new design for hierarchical deterministic wallets that brings identity-based addresses to the blockchain. Arcula is built on top of provably secure cryptographic primitives. It generates all its cryptographic secrets from a user-provided seed and enables the derivation of new public keys based on the identities of users, without requiring any secret information. Unlike other wallets, it achieves all these properties while being secure against privilege escalation. We formalize the security model of hierarchical deterministic wallets and prove that an attacker compromising an arbitrary number of users within an Arcula wallet cannot escalate his privileges and compromise users higher in the access hierarchy. Our design works out-of-the-box with any blockchain that enables the verification of signatures on arbitrary messages. We evaluate its usage in a real-world scenario on the Bitcoin Cash network.

An established ingredient in the security evaluation of cryptographic devices is leakage detection, whereby physically observable characteristics such as the power consumption are measured during operation and statistically analysed in search of sensitive data dependencies. However, depending on its precise execution, this approach potentially suffers several drawbacks: a risk of false positives, a difficulty interpreting negative outcomes, and the infeasibility of covering every possible eventuality. Moreover, efforts to mitigate for these drawbacks can be costly with respect to the data complexity of the testing procedures. In this work, we clarify the (varying) goals of leakage detection and assess how well-geared current practice is towards meeting each of those goals. We introduce some new innovations on existing methodologies and make recommendations for best practice. Ultimately, though, we find that many of the obstacles cannot be fully overcome according to existing statistical procedures, so that it remains to be highly cautious and to clearly state the limitations of the methods used when reporting outcomes.

Plantlet is a lightweight stream cipher designed by Mikhalev, Armknecht and Müller in \texttt{IACR ToSC} 2017. It has a Grain-like structure with two state registers of size $40$ and $61$ bits. In spite of this, the cipher does not seem to lose in security against generic Time-Memory-Data Tradeoff attacks due to the novelty of its design. The cipher uses a 80-bit secret key and a 90-bit IV. In this paper, we first present a key recovery attack on Plantlet that requires around $2^{76.26}$ Plantlet encryptions. The attack leverages the fact that two internal states of Plantlet that differ in the 43rd LFSR location are guaranteed to produce keystream that are either equal or unequal in 45 locations with probability 1. Thus an attacker can with some probability guess that when 2 segments of keystream blocks possess the 45 bit difference just mentioned, they have been produced by two internal states that differ only in the 43rd LFSR location. Thereafter by solving a system of polynomial equations representing the keystream bits, the attacker can find the secret key if his guess was indeed correct, or reach some kind of contradiction if his guess was incorrect. In the latter event, he would repeat the procedure for other keystream blocks with the given difference. We show that the process when repeated a finite number of times, does indeed yield the value of the secret key. In the second part of the paper, we observe that the previous attack was limited to internal state differences that occurred at time instances that were congruent to $0\bmod 80$. We further observe that by generalizing the attack to include internal state differences that are congruent to all equivalence classed modulo 80, we lower the total number of keystream bits required to perform the attack and in the process reduce the attack complexity to $2^{69.98}$ Plantlet encryptions.

A decentralized multi-authority anonymous authentication scheme that is suitable for IoT and blockchains is proposed, in which a prover and a verifier are non-interactive. The proposed scheme can treat dynamically increasing/decreasing independent attribute authorities. When an entity wants the authorities to issue attribute credentials, the authorities only have to generate digital signatures on her global identity. Two security definitions are given; resistance against eavesdrop-and-collude attacks that cause misauthentication, and anonymity for privacy protection. Then a construction of our scheme is described under a principle of ``commit-to-ID'' to attain resistance against the collusion attacks. There are two building blocks; the structure-preserving signature scheme and the Groth-Sahai non-interactive proof system, the both of which are in the setting of bilinear groups. The proposed scheme is proved to be secure in the standard model.

Lightweight cryptography in computationally constrained devices is actively studied. In contrast to advances of lightweight blockcipher in the last decade, lightweight mode of operation is seemingly not so mature, yet it has large impact in performance. Therefore, there is a great demand for lightweight mode of operation, especially that for authenticated encryption with associated data (AEAD). Among many known properties of conventional modes of operation, the following four properties are essential for constrained devices: 1. Minimum State Size: the state size equals to a block size of a blockcipher. 2. Inverse Free: no need for a blockcipher decryption. 3. XOR Only: only XOR is needed in addition to a blockcipher encryption. 4. Online: a data block is processed only once. The properties 1 and 4 contribute to small memory usage, and the properties 2 and 3 contribute to small program/circuit footprint. On top of the above properties, the fifth property regarding associated data (AD) is also important for performance: 5. Efficient Handling of Static AD: static AD can be precomputed. We design a lightweight blockcipher-based AEAD mode of operation called SAEB: the first mode of operation that satisfies all the five properties to the best of our knowledge. Performance of SAEB is evaluated in various software and hardware platforms. The evaluation results show that SAEB outperforms conventional blockcipher-based AEAD modes of operation in various performance metrics for lightweight cryptography.

Applying the Fiat-Shamir transform on identification schemes is one of the main ways of constructing signature schemes. While the classical security of this transformation is well understood, it is only very recently that generic results for the quantum case have been proposed [DFMS19,LZ19]. These results are asymptotic and therefore can't be used to derive the concrete security of these signature schemes without a significant loss in parameters. In this paper, we show that if we start from a commit-and-open identification scheme, where the prover first commits to several strings and then as a second message opens a subset of them depending on the verifier's message, then there is a tight quantum reduction for the the Fiat-Shamir transform to special soundness notions. Our work applies to most 3 round schemes of this form and can be used immediately to derive quantum concrete security of signature schemes. We apply our techniques to several identification schemes that lead to signature schemes such as Stern's identification scheme based on coding problems, the [KTX08] identification scheme based on lattice problems, the [SSH11] identification schemes based on multivariate problems, closely related to the NIST candidate MQDSS, and the PICNIC scheme based on multiparty computing problems, which is also a NIST candidate.

In cryptocurrencies such as Bitcoin or Ethereum, users control funds via secret keys. To transfer funds from one user to another, the owner of the money signs a new transaction that transfers the funds to the new recipient. This makes secret keys a highly attractive target for attacks and has led to prominent examples where millions of dollars worth in cryptocurrency were stolen. To protect against these attacks, a widely used approach are so-called hot/cold wallets. In a hot/cold wallet system, the hot wallet is permanently connected to the network, while the cold wallet stores the secret key and is kept without network connection. In this work, we propose the first comprehensive security model for hot/cold wallets and develop wallet schemes that are provably secure within these models. At the technical level, our main contribution is to provide a new, provably secure ECDSA-based hot/cold wallet scheme that can be integrated into legacy cryptocurrencies such as Bitcoin. Our scheme makes several subtle changes to the BIP32 proposal and requires a technically involved security analysis.

Assuring security of the Internet of Things (IoT) is much more challenging than assuring security of centralized environments, like the cloud. A reason for this is that IoT devices are often deployed in domains that are remotely managed and monitored. Thus, their physical security cannot be guaranteed as reliably as physical security of data centers. Some believe that physical security becomes less important if all data processed and stored within a device is encrypted. However, an attacker with a physical access to a device implementing an encryption algorithm may be able to extract the encryption key and decrypt data. As a demonstration, in this paper we attack ACORN stream cipher, a finalist of CESAR competition for authenticated encryption. By injecting a single stuck-at-0 fault into ACORN's implementation, we reduce its non-linear feedback function to a linear one. Since this obviously makes ACORN weaker, many known attacks can be applied to break it. We apply an algebraic attack which recovers the key from $2^{15.34}$ keystream bits using $2^{35.46}$ operations.

Highly efficient non-interactive zero-knowledge arguments (NIZK) are often constructed for limited languages and it is not known how to extend them to cover wider classes of languages in general. In this paper we initiate a study on black-box language extensions for conjunctive and disjunctive relations, that is, building a NIZK system for ${\cal L} \diamond \hat{{\cal L}}$ (with $\diamond \in \{\land, \lor\}$) based on NIZK systems for languages ${\cal L}$ and $\hat{{\cal L}}$. While the conjunctive extension of NIZKs is straightforward by simply executing the given NIZKs in parallel, it is not known how disjunctive extensions could be achieved in a black-box manner. Besides, observe that the simple conjunctive extension does not work in the case of simulation-sound NIZKs (SS-NIZKs), as pointed out by Sahai (Sahai, FOCS 1999). Our main contribution is an impossibility result that negates the existence of the above extensions and implies other non-trivial separations among NIZKs, SS-NIZKs, and labelled SS-NIZKs. Motivated by the difficulty of such transformations, we additionally present an efficient construction of signature schemes based on unbounded simulation-sound NIZKs (USS-NIZKs) for any language without language extensions.

We present a novel three-party sorting protocol secure against passive adversaries in the honest majority setting. The protocol can be easily combined with other secure protocols which work on shared data, and thus enable different data analysis tasks, such as data deduplication, set intersection, and computing percentiles. The new sorting protocol is based on radix sort. It is asymptotically better compared to previous sorting protocols since it does not need to shuffle the entire length of the items after each comparison step. We further improve the concrete efficiency by using not only optimizations but also novel protocols, which are independent of interest. We implemented our sorting protocol with those optimizations and protocols. Our experiments show that our implementation is concretely fast. For example, sorting one million $20$-bit items takes 4.6 seconds in 1G connection. It enables a new set of applications on large-scale datasets since the known implementations handle thousands of items about 10 seconds.

Ratcheting, an umbrella term for certain techniques for achieving secure messaging with strong guarantees, has spurred much interest in the cryptographic community, with several novel protocols proposed as of lately. Most of them are composed from several sub-protocols, often sharing similar ideas across different protocols. Thus, one could hope to reuse the sub-protocols to build new protocols achieving different security, efficiency, and usability trade-offs. This is especially desirable in view of the community's current aim for group messaging, which has a significantly larger design space. However, the underlying ideas are usually not made explicit, but rather implicitly encoded in a (fairly complex) security game, primarily targeted at the overall security proof. This not only hinders modular protocol design, but also makes the suitability of a protocol for a particular application difficult to assess. In this work we demonstrate that ratcheting components can be modeled in a composable framework, allowing for their reuse in a modular fashion. To this end, we first propose an extension of the Constructive Cryptography framework by so-called global event histories, to allow for a clean modularization even if the component modules are not fully independent but actually subtly intertwined, as in most ratcheting protocols. Second, we model a unified, flexibly instantiable type of strong security statement for secure messaging within that framework. Third, we show that one can phrase strong guarantees for a number of sub-protocols from the existing literature in this model with only minor modifications, slightly stronger assumptions, and reasonably intuitive formalizations. When expressing existing protocols' guarantees in a simulation-based framework, one has to address the so-called commitment problem. We do so by reflecting the removal of access to certain oracles under specific conditions, appearing in game-based security definitions, in the real world of our composable statements. We also propose a novel non-committing protocol for settings where the number of messages a party can send before receiving a reply is bounded.

Besides their security, the efficiency of searchable encryption schemes is a major criteria when it comes to their adoption: in order to replace an unencrypted database by a more secure construction, it must scale to the systems which rely on it. Unfortunately, the relationship between the efficiency and the security of searchable encryption has not been widely studied, and the minimum cost of some crucial security properties is still unclear. In this paper, we present new lower bounds on the tradeoffs between the size of the client state, the efficiency and the security for searchable encryption schemes. These lower bounds target two kinds of schemes: schemes hiding the repetition of search queries, and forward-private dynamic schemes, for which updates are oblivious. We also show that these lower bounds are tight, by either constructing schemes matching them, or by showing that even a small increase in the amount of leaked information allows for constructing schemes breaking the lower bounds.

Typically, protocols for Byzantine agreement (BA) are designed to run in either a synchronous network (where all messages are guaranteed to be delivered within some known time $\Delta$ from when they are sent) or an asynchronous network (where messages may be arbitrarily delayed). Protocols designed for synchronous networks are generally insecure if the network in which they run does not ensure synchrony; protocols designed for asynchronous networks are (of course) secure in a synchronous setting as well, but in that case tolerate a lower fraction of faults than would have been possible if synchrony had been assumed from the start. Fix some number of parties $n$, and $0 < t_a < n/3 \leq t_s < n/2$. We ask whether it is possible (given a public-key infrastructure) to design a BA protocol that (1) is resilient to $t_s$ corruptions when run in a synchronous network and (2) remains resilient to $t_a$ faults even if the network happens to be asynchronous. We show matching feasibility and infeasibility results demonstrating that this is possible if and only if $t_a + 2\cdot t_s < n$.

This paper describes the limits of various "security proofs", using 36 lattice-based KEMs as case studies. This description allows the limits to be systematically compared across these KEMs; shows that some previous claims are incorrect; and provides an explicit framework for thorough security reviews of these KEMs.

Several combined attacks have shown promising results in recovering cryptographic keys by introducing collision information into divide-and-conquer attacks to transform a part of the best key candidates within given thresholds into a much smaller collision space. However, these Collision-Optimized Divide-and-Conquer Attacks (CODCAs) uniformly demarcate the thresholds for all sub-keys, which is unreasonable. Moreover, the inadequate exploitation of collision information and backward fault tolerance mechanisms of CODCAs also lead to low attack efficiency. Finally, existing CODCAs mainly focus on improving collision detection algorithms but lack theoretical basis. We exploit Correlation-Enhanced Collision Attack (CECA) to optimize Template Attack (TA). To overcome the above-mentioned problems, we first introduce guessing theory into TA to enable the quick estimation of success probability and the corresponding complexity of key recovery. Next, a novel Multiple-Differential mechanism for CODCAs (MD-CODCA) is proposed. The first two differential mechanisms construct collision chains satisfying the given number of collisions from several sub-keys with the fewest candidates under a fixed probability provided by guessing theory, then exploit them to vote for the remaining sub-keys. This guarantees that the number of remaining chains is minimal, and makes MD-CODCA suitable for very high thresholds. Our third differential mechanism simply divides the key into several large non-overlapping ``blocks'' to further exploit intra-block collisions from the remaining candidates and properly ignore the inter-block collisions, thus facilitating the latter key enumeration. The experimental results show that MD-CODCA significantly reduces the candidate space and lowers the complexity of collision detection, without considerably reducing the success probability of attacks.

Side-channel power analysis is a powerful method of breaking secure cryptographic algorithms, but typically power analysis is considered to require specialized measurement equipment on or near the device. Assuming an attacker first gained the ability to run code on the unsecure side of a device, they could trigger encryptions and use the on-board ADC to capture power traces of that hardware encryption engine. This is demonstrated on a SAML11 which contains a M23 core with a TrustZone-M implementation as the hardware security barrier. This attack requires 160 million traces, or approximately 5 GByte of data. This attack does not use any external measurement equipment, entirely performing the power analysis using the ADC on-board the microcontroller under attack. The attack is demonstrated to work both from the non-secure and secure environment on the chip, being a demonstration of a cross-domain power analysis attack. To understand the effect of noise and sample rate reduction, an attack is mounted on the SAML11 hardware AES peripheral using classic external equipment, and results are compared for various sample rates and hardware setups. A discussion on how users of this device can help prevent such remote attacks is also presented, along with metrics that can be used in evaluating other devices. Complete copies of all recorded power traces and scripts used by the authors are publicly presented.

After Cheon et al. (Asiacrypt' 17) proposed an approximate homomorphic encryption scheme, Heaan, for operations between encrypted real (or complex) numbers, the scheme is widely used in a variety of fields with needs on privacy-preserving in data analysis. After that, a bootstrapping method for Heaan is proposed by Cheon et al. (Eurocrypt' 18) with modulus reduction being replaced by a sine function. In this paper, we generalize the Full-RNS variant of Heaan proposed by Cheon et al. (SAC, 19) to reduce the number of temporary moduli used in key-switching. As a result, our scheme can support more depth computations without bootstrapping while ensuring the same level of security. We also propose a new polynomial approximation method to evaluate a sine function in an encrypted state, which is specialized for the bootstrapping for Heaan. Our method considers a ratio between the size of a plaintext and the size of a ciphertext modulus. Consequently, it requires a smaller number of non-scalar multiplications, which is about half of the Chebyshev method. With our variant of the Full-RNS scheme and a new sine evaluation method, we firstly implement bootstrapping for a Full-RNS variant of approximate homomorphic encryption scheme. Our method enables bootstrapping for a plaintext in the space $\mathbb{C}^{16384}$ to be completed in 52 seconds while preserving 11 bit precision of each slot.

Starting from the one-way group action framework of Brassard and Yung (Crypto '90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm). We propose the general linear group action on tensors as a new candidate to build cryptography based on group actions. Recent works (Futorny--Grochow--Sergeichuk, Lin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, the tensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, and hardness results, as well as quantum algorithms. We then introduce a new notion called pseudorandom group actions to further develop group-action based cryptography. Briefly speaking, given a group G acting on a set S, we assume that it is hard to distinguish two distributions of (s,t) either uniformly chosen from S×S, or where s is randomly chosen from S and t is the result of applying a random group action of g on s. This subsumes the classical decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support the general linear group action on tensors as a candidate for this assumption. Finally, we establish the quantum security of several cryptographic primitives based on the one-way group action assumption and the pseudorandom group action assumption.

The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate that constructions from one-way functions are unlikely. Indeed, theoretical constructions of collision-resistant hash functions are based on rather structured assumptions. We make two contributions to this study: 1. A New Separation: We show that collision-resistant hashing does not imply hard problems in the class Statistical Zero Knowledge in a black-box way. 2. New Proofs: We show new proofs for the results of Simon, ruling out black-box reductions of collision-resistant hashing to one-way permutations, and of Asharov and Segev, ruling out black-box reductions to indistinguishability obfuscation. The new proofs are quite different from the previous ones and are based on simple coupling arguments.

Most NIST Post-Quantum Cryptography (PQC) candidate algorithms use symmetric primitives internally for various purposes such as ``seed expansion'' and CPA to CCA transforms. Such auxiliary symmetric operations constituted only a fraction of total execution time of traditional RSA and ECC algorithms, but with faster lattice algorithms the impact of symmetric algorithm characteristics can be very significant. A choice to use a specific PQC algorithm implies that its internal symmetric components must also be implemented on all target platforms. This can be problematic for lightweight, embedded (IoT), and hardware implementations. It has been widely observed that current NIST-approved symmetric components (AES, GCM, SHA, SHAKE) form a major bottleneck on embedded and hardware implementation footprint and performance for many of the most efficient NIST PQC proposals. Meanwhile, a separate NIST effort is ongoing to standardize lightweight symmetric cryptography (LWC). Therefore it makes sense to explore which NIST LWC candidates are able to efficiently support internals of post-quantum asymmetric cryptography. We discuss R5Sneik, a variant of Round5 that internally uses SNEIK 1.1 permutation-based primitives instead of SHAKE and AES-GCM. The SNEIK family includes parameter selections specifically designed to support lattice cryptography. R5Sneik is up to 40\% faster than Round5 for some parameter sets on ARM Cortex M4, and has substantially smaller implementation footprint. We introduce the concept of a fast Entropy Distribution Function (EDF), a lightweight diffuser that we expect to have sufficient security properties for lattice seed expansion and many types of sampling, but not for plain encryption or hashing. The same SNEIK 1.1 permutation core (but with a different number of rounds) can also be used to replace AES-GCM as an AEAD when building lightweight cryptographic protocols, halving typical flash footprint on Cortex M4, while boosting performance.

We reveal Revelio, a new privacy-preserving proof of reserves protocol for Grin exchanges. By design, Revelio allows the detection of collusion between exchanges while hiding the identities of the outputs owned by the exchange in a larger anonymity set of outputs.

We revisit the definition of Transparency Order (TO) and that of Modified Transparency Order (MTO) as well, which were proposed to measure the resistance of an S-box against Differential Power Analysis (DPA). We spot a definitional flaw in original TO, which is proved to have significantly affected the soundness of TO and hinder it to be a good quantitative security criterion. Regretfully, the flaw itself remains virtually undiscovered in MTO, either. Surprisingly, MTO overlooks this flaw and yet it happens to incur no bad effects on the correctness of its formulation, even though the start point of this formulation is highly questionable. It is also this neglect of the flaw that made MTO take a variant of multi-bit DPA attack into consideration, which was mistakenly thought to appropriately serve as an alternative powerful attack. Based on this observation, we also find that MTO introduces such an alternative adversary that it might overestimate the resistance of an S-box in some cases, as the variant of multi-bit DPA attack considered in MTO is not that powerful as one may think. This implies the soundness of MTO is also more or less arguable. Consequently, we fix this definitional flaw, and provide a revised definition in which a powerful adversary is also involved. For demonstrating validity and soundness of our revised TO (RTO), we adopt both optimal $4\times4$ S-boxes and $8\times8$ S-boxes as study cases, and present simulated and practical DPA attacks as well on implementations of those S-boxes. The results of our attacks verify our findings and analysis as well. Furthermore, as a concrete application of the revised TO, we also present the distribution of RTO values for sixteen optimal affine equivalence classes of $4\times4$ S-boxes. Finally, we give some recommended guidelines on how to select optimal $4\times4$ S-boxes in practical implementations.

Secure cloud storage is considered as one of the most important issues that both businesses and end-users take into account before moving their private data to the cloud. Lately, we have seen some interesting approaches that are based either on the promising concept of Symmetric Searchable Encryption (SSE) or on the well-studied field of Attribute-Based Encryption (ABE). In the first case, researchers are trying to design protocols where users' data will be protected from both internal and external attacks without paying the necessary attention to the problem of user revocation. In the second case, existing approaches address the problem of revocation. However, the overall efficiency of these systems is compromised since the proposed protocols are solely based on ABE schemes and the size of the produced ciphertexts and the time required to decrypt grows with the complexity of the access formula. In this paper, we propose a hybrid encryption scheme that combines both SSE and ABE by utilizing the advantages of both these techniques. In contrast to many approaches, we design a revocation mechanism that is completely separated from the ABE scheme and solely based on the functionality offered by SGX.