Any $d$-regular graph on $n$ vertices with spectral expansion $\lambda$ satisfying $n = \Omega(d^3\log(d)/\lambda)$ yields a $O\left(\frac{\lambda^{3/2}}{d}\right)$-non-malleable code for single-bit messages in the split-state model.

We propose FO-AKE a generic construction of two-message authenticated key exchange (AKE) from any passively secure public key encryption (PKE) in the quantum random oracle model (QROM). Whereas previous AKE constructions relied on a Diffie-Hellman key exchange or required the underlying PKE scheme to be perfectly correct, our transformation allows arbitrary PKE schemes with non-perfect correctness. Furthermore, we avoid the use of (quantum-secure) digital signature schemes which are considerably less efficient than their PKE counterparts. As a consequence, we can instantiate our AKE transformation with any of the submissions to the recent NIST post-quantum competition, e.g., ones based on codes and lattices. FO-AKE can be seen as a generalization of the well known Fujisaki-Okamoto transformation (for building actively secure PKE from passively secure PKE) to the AKE setting. Therefore, as a helper result, we also provide a security proof for the Fujisaki-Okamoto transformation in the QROM for PKE with non-perfect correctness. Our reduction fixes several gaps in a previous proof (CRYPTO 2018), is tighter, and tolerates a larger correctness error.

In distributed pseudorandom functions (DPRFs), a PRF secret key $SK$ is secret shared among $N$ servers so that each server can locally compute a partial evaluation of the PRF on some input $X$. A combiner that collects $t$ partial evaluations can then reconstruct the evaluation $F(SK,X)$ of the PRF under the initial secret key. So far, all non-interactive constructions in the standard model are based on lattice assumptions. One caveat is that they are only known to be secure in the static corruption setting, where the adversary chooses the servers to corrupt at the very beginning of the game, before any evaluation query. In this work, we construct the first fully non-interactive adaptively secure DPRF in the standard model. Our construction is proved secure under the LWE assumption against adversaries that may adaptively decide which servers they want to corrupt. We also extend our construction in order to achieve robustness against malicious adversaries.

We initiate the study of computational problems on elliptic curve isogeny graphs defined over RSA moduli. We conjecture that several variants of the neighbor-search problem over these graphs are hard, and provide a comprehensive list of cryptanalytic attempts on these problems. Moreover, based on the hardness of these problems, we provide a construction of groups with infeasible inversion, where the underlying groups are the ideal class groups of imaginary quadratic orders. Recall that in a group with infeasible inversion, computing the inverse of a group element is required to be hard, while performing the group operation is easy. Motivated by the potential cryptographic application of building a directed transitive signature scheme, the search for a group with infeasible inversion was initiated in the theses of Hohenberger and Molnar (2003). Later it was also shown to provide a broadcast encryption scheme by Irrer et al. (2004). However, to date the only case of a group with infeasible inversion is implied by the much stronger primitive of self-bilinear map constructed by Yamakawa et al. (2014) based on the hardness of factoring and indistinguishability obfuscation (iO). Our construction gives a candidate without using iO.

Today’s blockchains do not scale in a meaningful sense. As more nodes join the system, the efficiency of the system (computation, communication, and storage) degrades, or at best stays constant. A leading idea for enabling blockchains to scale efficiency is the notion of sharding: different subsets of nodes handle different portions of the blockchain, thereby reducing the load for each individual node. However, existing sharding proposals achieve efficiency scaling by compromising on trust - corrupting the nodes in a given shard will lead to the permanent loss of the corresponding portion of data. We observe that sharding is similar to replication coding, which is known to be inefficient and fragile in the coding theory community. In this paper, we demonstrate a new protocol for coded storage and computation in blockchains. In particular, we propose PolyShard: “polynomially coded sharding” scheme that achieves information-theoretic upper bounds on the efficiency of the storage, system throughput, as well as on trust, thus enabling a truly scalable system. We provide simulation results that numerically demonstrate the performance improvement over state of the arts, and the scalability of the PolyShard system. Finally, we discuss potential enhancements, and highlight practical considerations in building such a system.

We introduce the forward secure signature scheme XMSS$^{+}$ and present an implementation for smart cards. It is based on the hash-based signature scheme XMSS. In contrast to the only previous implementation of a hash-based signature scheme on smart cards by Rohde et al., we solve the problem of on-card key generation. Compared to XMSS, we reduce the key generation time from $\mathcal{O}(n)$ to $\mathcal{O}(\sqrt{n})$, where $n$ is the number of signatures that can be created with one key pair. To the best of our knowledge this is the first implementation of a forward secure signature scheme and the first full implementation of a hash-based signature scheme on smart cards. The resulting runtimes are comparable to those of RSA and ECDSA on the same device. This shows the practicality of forward secure signature schemes, even on constrained devices.

In a delegatable anonymous credential system, participants may use their credentials anonymously as well as anonymously delegate them to other participants. Such systems are more usable than traditional anonymous credential systems because a popular credential issuer can delegate some of its responsibilities without compromising users' privacy. They also provide stronger privacy guarantees than traditional anonymous credential systems because the identities of credential issuers are hidden. The identity of a credential issuer may convey information about a user's identity even when all other information about the user is concealed. The only previously known constructions of delegatable anonymous credentials were prohibitively inefficient. They were based on non-interactive zero-knowledge (NIZK) proofs. In this paper, we provide a simple construction of delegatable anonymous credentials and prove its security in the generic group model. Our construction is direct, not based on NIZK proofs, and is therefore considerably more efficient. In fact, in our construction, only five group elements are needed per link to represent an anonymous credential chain. Our main building block is a new type of signature scheme, a mercurial signature, which allows a signature $\sigma$ on a message $M$ under public key $\mathsf{pk}$ to be transformed into a signature $\sigma'$ on an equivalent but unlinkable message $M'$ under an equivalent but unlinkable public key $\mathsf{pk}'$.

Threshold implementations have emerged as one of the most popular masking countermeasures for hardware implementations of cryptographic primitives. In the original version of TI, the number of input shares was dependent on both security order $d$ and algebraic degree of a function $t$, namely $td + 1$. At CRYPTO 2015, a new method was presented yielding to a $d$-th order secure implementation using $d+1$ input shares. In this work, we first provide a construction for $d+1$ TI sharing which achieves the minimal number of output shares for any $n$-input Boolean function of degree $t=n-1$. Furthermore, we present a heuristic for minimizing the number of output shares for higher order $td + 1$ TI. Finally, we demonstrate the applicability of our results on $d+1$ and $td+1$ TI versions, for first- and second-order secure, low-latency and low-energy implementations of the PRINCE block cipher.

Motivatedbytheoreticalandpracticalconsiderations,anim- portant line of research is to design secure computation protocols that only make black-box use of cryptography. An important component in nearly all the black-box secure computation constructions is a black- box commit-and-prove protocol. A commit-and-prove protocol allows a prover to commit to a value and prove a statement about this value while guaranteeing that the committed value remains hidden. A black- box commit-and-prove protocol implements this functionality while only making black-box use of cryptography. In this paper, we build several tools that enable constructions of round- optimal, black-box commit and prove protocols. In particular, assuming injective one-way functions, we design the first round-optimal, black- box commit-and-prove arguments of knowledge satisfying strong privacy against malicious verifiers, namely: – Zero-knowledge in four rounds and, – Witness indistinguishability in three rounds. Prior to our work, the best known black-box protocols achieving commit- and-prove required more rounds. We additionally ensure that our protocols can be used, if needed, in the delayed-input setting, where the statement to be proven is decided only towards the end of the interaction. We also observe simple applications of our protocols towards achieving black-box four-round constructions of extractable and equivocal commitments. We believe that our protocols will provide a useful tool enabling several new constructions and easy round-efficient conversions from non-black- box to black-box protocols in the future.

We pursue to formalize and instantiate a secure bidirectional channel with message franking properties. Under this model a sender may send an abusive message to the receiver and the latter wish to open it in a verifiable way to a third party. Potential malicious behavior of a sender requires message franking protocols resistant to sending messages that cannot be opened later by the receiver. An adversary impersonated by the receiver may also try to open messages that have not been sent by the sender. Wrapping a message franking protocol in a secure channel requires a more delicate treatment in order to avoid drops or replay of messages and out-of-order delivery. To the best of our knowledge we are the first to model the security of a message franking channel, which apart from integrity, confidentiality, resistance to drops, relays and out-of-order delivery is sender and receiver binding: a sender cannot send a message which cannot be opened in a verifiable way later by the receiver, and the receiver cannot claim a message that had not been truly sent by the receiver. Finally, we instantiate a bidirectional message franking channel from symmetric primitives and analyze its security.

In this work, we introduce the notion of registration-based encryption (RBE for short) with the goal of removing the trust parties need to place in the private-key generator in an IBE scheme. In an RBE scheme, users sample their own public and secret keys. There will also be a ``key curator'' whose job is only to aggregate the public keys of all the registered users and update the short public parameter whenever a new user joins the system. Encryption can still be performed to a particular ecipient using the recipient's identity and any public parameters released subsequent to the recipient's registration. Decryption requires some auxiliary information connecting users' public (and secret) keys to the public parameters. Because of this, as the public parameters get updated, a decryptor may need to obtain a few additional auxiliary information for decryption. More formally, if $n$ is the total number of identities and $\kappa$ is the security parameter, we require the following. Efficiency requirements: (1) A decryptor only needs to obtain updated auxiliary information for decryption at most $O(\log n)$ times in its lifetime, (2) each of these updates are computed by the key curator in time $poly(\kappa,\log n)$, and (3) the key curator updates the public parameter upon the registration of a new party in time $poly(\kappa,\log n)$. Properties (2) and (3) require the key curator to have \emph{random} access to its data. Compactness requirements: (1) Public parameters are always at most $poly(\kappa,\log n)$ bit, and (2) the total size of updates a user ever needs for decryption is also at most $poly(\kappa,\log n)$ bits. We present feasibility results for constructions of RBE based on indistinguishably obfuscation. We further provide constructions of \emph{weakly efficient} RBE, in which the registration step is done in $poly(\kappa, n)$, based on CDH, Factoring or LWE assumptions. Note that registration is done only once per identity, and the more frequent operation of generating updates for a user, which can happen more times, still runs in time $poly(\kappa,\log n)$. We leave open the problem of obtaining standard RBE (with $poly(\kappa,\log n)$ registration time) from standard assumptions.

Bitcoin, the most popular blockchain system, does not scale even under very optimistic assumptions. Lightning networks, a layer on top of Bitcoin, composed of one-to-one lightning channels make it scale to up to 105 Million users. Recently, Duplex Micropayment Channel factories have been proposed based on opening multiple one-to-one payment channels at once. Duplex Micropayment Channel factories rely on time-locks to update and close their channels. This mechanism yields to situation where users funds time-locking for long periods increases with the lifetime of the factory and the number of users. This makes DMC factories not applicable in real-life scenarios. In this paper, we propose the first channel factory construction, the Lightning Factory that offers a constant collateral cost, independent of the lifetime of the channel and members of the factory. We compare our proposed design with Duplex Micropayment Channel factories, obtaining better performance results by a factor of more than 3000 times in terms of the worst-case constant collateral cost incurred when malicious users use the factory. The message complexity of our factory is $n$ where Duplex Micropayment Channel factories need $n^2$ messages where $n$ is the number of users. Moreover, our factory copes with an infinite number of updates while in Duplex Micropayment Channel factories the number of updates is bounded by the initial time-lock. Finally, we discuss the necessity for our Lightning Factories of BNN, a non-interactive aggregate signature cryptographic scheme, and compare it with Schnorr and ECDSA schemes used in Bitcoin and Duplex Micropayment Channels.

Collaboration between financial institutions helps to improve detection of fraud. However, exchange of relevant data between these institutions is often not possible due to privacy constraints and data confidentiality. An important example of relevant data for fraud detection is given by a transaction graph, where the nodes represent bank accounts and the links consist of the transactions between these accounts. Previous works show that features derived from such graphs, like PageRank, can be used to improve fraud detection. However, each institution can only see a part of the whole transaction graph, corresponding to the accounts of its own customers.In this research a new method is described, making use of secure multiparty computation (MPC) techniques, allowing multiple parties to jointly compute the PageRank values of their combined transaction graphs securely, while guaranteeing that each party only learns the PageRank values of its own accounts and nothing about the other transaction graphs. In our experiments this method is applied to graphs containing up to tens of thousands of nodes. The execution time scales linearly with the number of nodes, and the method is highly parallelizable. Secure multiparty PageRank is feasible in a realistic setting with millions of nodes per party by extrapolating the results from our experiments.

Highly efficient encryption and authentication of short messages has been identified as an essential requirement for enabling security in constrained computation and communication scenarios such as the CAN FD in automotive systems (with maximum message length of 64 bytes), massive IoT and critical communication domains of 5G, and Narrowband IoT (NB-IoT), to mention some. Accordingly, NIST has specified, as a design requirement in the lightweight cryptography project, that AEAD submissions shall be “optimized to be efficient for short messages (e.g., as short as 8 bytes)”. We propose AEAD schemes that exceed in efficiency over all previous general-purpose modular AEAD designs at processing (very) short inputs. The main ingredient in our solution is a new low-level primitive, called a tweakable forkcipher, which we introduce and formalize in this paper. We give an instance of the tweakable forkcipher and dub it ForkAES. It is based on the tweakable blockcipher KIASU, which relies on the round function of AES and uses the TWEAKEY framework to derive round keys from a 128-bit secret key and a 64-bit tweak. Finally, we demonstrate the applicability of a tweakable forkcipher by designing several provably secure nonce-based AEAD modes of operation, optimized to be efficient for short messages. Considering the AES block size (16 bytes) as a reference, our new AE schemes can beat all known schemes for single-block messages while still performing better than majority of the existing schemes for combined message and associated data lengths up to 4 blocks. While ForkAES as a concrete instantiation for a forkcipher is based on KIASU, we note that our solution provides a general recipe for lightweight AEAD for short messages, even for very resource-constrained scenarios in which AES may not be considered a lightweight option. In those environments, our schemes can be instantiated using a forkcipher that is realized based on the best off-the-shelf lightweight blockcipher, following the TWEAKEY framework.

Recently, Chen et al. proposed the first non-delegatable certificateless strong designated verifier signature scheme and claimed that their scheme achieves all security requirements. However, in this paper, we disprove their claim and present a concrete attack which shows that their proposed scheme is forgeable. More precisely, we show that there exist adversaries who are able to forge any signer's signature for any designated verifier on any message of his choice.

Constrained pseudorandom functions (CPRFs) are a type of PRFs that allows one to derive a constrained key $\mathsf{K}_C$ from the master key $\mathsf{K}$. While the master key $\mathsf{K}$ allows one to evaluate on any input as a standard PRF, the constrained key $\mathsf{K}_C$ only allows one to evaluate on inputs $x$ such that $C(x) = 1$. Since the introduction of CPRFs by Boneh and Waters (ASIACRYPT'13), Kiayias et al. (CCS'13), and Boyle et al. (PKC'14), there have been various constructions of CPRFs. However, thus far, almost all constructions (from standard assumptions and non-trivial constraints) are only proven to be secure if at most one constrained key $\mathsf{K}_C$ is known to the adversary, excluding the very recent work of Davidson and Nishimaki (EPRINT'18). Considering the interesting applications of CPRFs such as ID-based non-interactive key exchange, we desire CPRFs that are collusion resistance with respect to the constrained keys. In this work, we make progress in this direction and construct a CPRF for the bit-fixing predicates that are collusion resistance for a constant number of constrained keys. Surprisingly, compared to the heavy machinery that was used by previous CPRF constructions, our construction only relies on the existence of one-way functions.

We reconsider the security guarantee that can be achieved by general protocols for secure multiparty computation in the most basic of settings: information-theoretic security against a semi-honest adversary. Since the 1980s, we have elegant solutions to this problem that offer full security, as long as the adversary controls a minority of the parties, but fail completely when that threshold is crossed. In this work, we revisit this problem, questioning the optimality of the standard notion of security. We put forward a new notion of information-theoretic security which is strictly stronger than the standard one, and which we argue to be ``best possible.'' Our new notion still requires full security against dishonest minority in the usual sense, but also requires a meaningful notion of information-theoretic security against dishonest majority. We present protocols for useful classes of functions that satisfy this new notion of security. Our protocols have the unique feature of combining the efficiency benefits of protocols for an honest majority and (most of) the security benefits of protocols for dishonest majority. We further extend some of the solutions to the malicious setting.

In this paper, we revisit the round complexity of designing zero-knowledge (ZK) arguments via a black-box construction from minimal assumptions. Our main result implements a 4-round ZK argument for any language in NP, based on injective one-way functions, that makes black-box use of the underlying function. As a corollary, we also obtain the first 4-round perfect zero-knowledge argument for NP based on claw-free permutations via a black-box construction and 4-round input-delayed commit-and-prove zero-knowledge argument based on injective one-way functions.

Fairness in classification has become an increasingly relevant and controversial issue as computers replace humans in many of today’s classification tasks. In particular, a subject of much recent debate is that of finding, and subsequently achieving, suitable definitions of fairness in an algorithmic context. In this work, following the work of Hardt et al. (NIPS’16), we consider and formalize the task of sanitizing an unfair classifier C into a classifier C' satisfying an approximate notion of "equalized odds", or fair treatment. Our main result shows how to take any (possibly unfair) classifier C over a finite outcome space, and transform it—-by just perturbing the output of C—according to some distribution learned by just having black-box access to samples of labeled, and previously classified, data, to produce a classifier C' that satisfies fair treatment; we additionally show that our derived classifier is near-optimal in terms of accuracy. We also experimentally evaluate the performance of our method.

We investigate sampling procedures that certify that an arbitrary quantum state on $n$ subsystems is close to an ideal mixed state $\varphi^{\otimes n}$ for a given reference state $\varphi$, up to errors on a few positions. This task makes no sense classically: it would correspond to certifying that a given bitstring was generated according to some desired probability distribution. However, in the quantum case, this is possible if one has access to a prover who can supply a purification of the mixed state. In this work, we introduce the concept of mixed-state certification, and we show that a natural sampling protocol offers secure certification in the presence of a possibly dishonest prover: if the verifier accepts then he can be almost certain that the state in question has been correctly prepared, up to a small number of errors. We then apply this result to two-party quantum coin-tossing. Given that strong coin tossing is impossible, it is natural to ask ``how close can we get". This question has been well studied and is nowadays well understood from the perspective of the bias of individual coin tosses. We approach and answer this question from a different---and somewhat orthogonal---perspective, where we do not look at individual coin tosses but at the global entropy instead. We show how two distrusting parties can produce a common high-entropy source, where the entropy is an arbitrarily small fraction below the maximum.

We continue the study of protocols for secure multiparty computation (MPC) that require only two rounds of interaction. The recent works of Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) essentially settle the question by showing that such protocols are implied by the minimal assumption that a two-round oblivious transfer (OT) protocol exists. However, these protocols inherently make a non-black-box use of the underlying OT protocol, which results in poor concrete efficiency. Moreover, no analogous result was known in the information-theoretic setting, or alternatively based on one-way functions, given an OT correlations setup or an honest majority. Motivated by these limitations, we study the possibility of obtaining information-theoretic and ``black-box'' implementations of two-round MPC protocols. We obtain the following results: - Two-round MPC from OT correlations. Given an OT correlations setup, we get protocols that make a black-box use of a pseudorandom generator (PRG) and are secure against a malicious adversary corrupting an arbitrary number of parties. For a semi-honest adversary, we get similar information-theoretic protocols for branching programs. - New NIOT constructions. Towards realizing OT correlations, we extend the DDH-based non-interactive OT (NIOT) protocol of Bellare and Micali (Crypto '89) to the malicious security model, and present new NIOT constructions from the Quadratic Residuosity Assumption (QRA) and the Learning With Errors (LWE) assumption. - Two-round black-box MPC with strong PKI setup. Combining the two previous results, we get two-round MPC protocols that make a black-box use of any DDH-hard or QRA-hard group. The protocols can offer security against a malicious adversary, and require a PKI setup that depends on the number of parties and the size of computation, but not on the inputs or the identities of the participating parties. - Two-round honest-majority MPC from secure channels. Given secure point-to-point channels, we get protocols that make a black-box use of a pseudorandom generator (PRG), as well as information-theoretic protocols for branching programs. These protocols can tolerate a semi-honest adversary corrupting a strict minority of the parties, where in the information-theoretic case the complexity is quasi-polynomial in the number of parties.

We construct Indistinguishability Obfuscation (iO) and Functional Encryption (FE) schemes in the Turing machine model from the minimal assumption of compact FE for circuits (CktFE). Our constructions overcome the barrier of sub-exponential loss incurred by all prior work. Our contributions are: 1. We construct iO in the Turing machine model from the same assumptions as required in the circuit model, namely, sub-exponentially secure FE for circuits. The previous best constructions [KLW15, AJS17] require sub-exponentially secure iO for circuits, which in turn requires sub-exponentially secure FE for circuits [AJ15, BV15]. 2. We provide a new construction of single input FE for Turing machines with unbounded length inputs and optimal parameters from polynomially secure, compact FE for circuits. The previously best known construction by Ananth and Sahai [AS16] relies on iO for circuits, or equivalently, sub-exponentially secure FE for circuits. 3. We provide a new construction of multi-input FE for Turing machines. Our construction supports a fixed number of encryptors (say k), who may each encrypt a string xi of unbounded length. We rely on sub-exponentially secure FE for circuits, while the only previous construction [BGJS15] relies on a strong knowledge type assumption, namely, public coin differing inputs obfuscation. Our techniques are new and from first principles, and avoid usage of sophisticated iO specific machinery such as positional accumulators and splittable signatures that were used by all relevant prior work [KLW15, AS16, AJS17].

This paper introduces Spice, a system for building verifiable state machines (VSMs). A VSM is a request-processing service that produces proofs establishing that requests were executed correctly according to a specification. Such proofs are succinct (a verifier can check them efficiently without reexecution) and zero-knowledge (a verifier learns nothing about the content of the requests, responses, or the internal state of the service). Recent systems for proving the correct execution of stateful computations---Pantry, Geppetto, CTV, vSQL, etc.--implicitly implement VSMs, but they incur prohibitive costs. Spice reduces these costs significantly with a new storage primitive. More notably, Spice’s storage primitive supports multiple writers, making Spice the first system that can succinctly prove the correct execution of concurrent services. We find that Spice running on a cluster of 16 servers achieves 488--1167 transactions/second for a variety of applications including inter-bank transactions, cloud-hosted ledgers, and dark pools. This represents an 18,000--685,000× higher throughput than prior work.

A software watermarking scheme can embed some information called a mark into a program while preserving its functionality. No adversary can remove the mark without damaging the functionality of the program. Cohen et al. (STOC '16) gave the first positive results for watermarking, showing how to watermark certain pseudorandom function (PRF) families using indistinguishability obfuscation (iO). Their scheme has a secret marking procedure to embed marks in programs and a public extraction procedure to extract the marks from programs; security holds even against an attacker that has access to a marking oracle. Kim and Wu (CRYPTO '17) later constructed a PRF watermarking scheme under only the LWE assumption. In their scheme, both the marking and extraction procedures are secret, but security only holds against an attacker with access to a marking oracle but not an extraction oracle. In fact, it is possible to completely break the security of the latter scheme using extraction queries, which is a significant limitation in any foreseeable application. In this work, we construct a new PRF watermarking scheme with the following properties. * The marking procedure is public and therefore anyone can embed marks in PRFs from the family. Previously we had no such construction even using obfuscation. * The extraction key is secret, but marks remain unremovable even if the attacker has access to an extraction oracle. Previously we had no such construction under standard assumptions. * Our scheme is simple, uses generic components and can be instantiated under many different assumptions such as DDH, Factoring or LWE. The above benefits come with one caveat compared to prior work: the PRF family that we can watermark depends on the public parameters of the watermarking scheme and the watermarking authority has a secret key which can break the security of all of the PRFs in the family. Since the watermarking authority is usually assumed to be trusted, this caveat appears to be acceptable.

We consider the question of whether the security of unique digital signature schemes can be based on game-based cryptographic assumptions using linear-preserving black-box security reductions—that is, black-box reductions for which the security loss (i.e., the ratio between "work" of the adversary and the "work" of the reduction) is some a priori bounded polynomial. A seminal result by Coron (Eurocrypt'02) shows limitations of such reductions; however, his impossibility result and its subsequent extensions all suffer from two notable restrictions: (1) they only rule out so-called "simple" reductions, where the reduction is restricted to only sequentially invoke "straight-line" instances of the adversary; and (2) they only rule out reductions to non-interactive (two-round) assumptions. In this work, we present the first full impossibility result: our main result shows that the existence of any linear-preserving black-box reduction for basing the security of unique signatures on some bounded-round assumption implies that the assumption can be broken in polynomial time.

We present an improved version of the one-way to hiding (O2H) Theorem by Unruh, J ACM 2015. Our new O2H Theorem gives higher flexibility (arbitrary joint distributions of oracles and inputs, multiple reprogrammed points) as well as tighter bounds (removing square-root factors, taking parallelism into account). The improved O2H Theorem makes use of a new variant of quantum oracles, semi-classical oracles, where queries are partially measured. The new O2H Theorem allows us to get better security bounds in several public-key encryption schemes.

Concerns about the impact of quantum computers on currently deployed public key cryptography have instigated research into not only quantum-resistant cryptographic primitives but also how to transition applications from classical to quantum-resistant solutions. One approach to mitigate the risk of quantum attacks and to preserve common security guarantees are hybrid schemes, which combine classically secure and quantum-resistant schemes. Various academic and industry experiments and draft standards related to the Transport Layer Security (TLS) protocol already use some form of hybrid key exchange; however sound theoretical approaches to substantiate the design and security of such hybrid key exchange protocols are missing so far. We initiate the modeling of hybrid authenticated key exchange protocols. We consider security against adversaries with varying levels of quantum power over time, such as adversaries who may become quantum in the future or are quantum in the present. We reach our goal using a three-step approach: First, we introduce security notions for key encapsulation mechanisms (KEMs) that enable a fine-grained distinction between different quantum scenarios. Second, we propose several combiners for constructing hybrid KEMs that correspond closely to recently proposed Internet-Drafts for hybrid key exchange in TLS 1.3. Finally, we present a provably sound design for hybrid key exchange using KEMs as building blocks.

Intel SGX enables protected enclaves on untrusted computing platforms. An important part of SGX is its remote attestation mechanism that allows a remote verifier to check that the expected enclave was correctly initialized before provisioning secrets to it. However, SGX attestation is vulnerable to relay attacks where the attacker, using malicious software on the target platform, redirects the attestation and therefore the provisioning of confidential data to a platform that he physically controls. Although relay attacks have been known for a long time, their consequences have not been carefully examined. In this paper, we analyze relay attacks and show that redirection increases the adversary's abilities to compromise the enclave in several ways, enabling for instance physical and digital side-channel attacks that would not be otherwise possible. %We also explain why commonly suggested solutions like trust on first use (TOFU) are inadequate to prevent relay attacks. We propose ProximiTEE, a novel solution to prevent relay attacks. Our solution is based on a trusted embedded device that is attached to the target platform. Our device verifies the proximity of the attested enclave, thus allowing attestation to the intended enclave regardless of malicious software, such as a compromised OS, on the target platform. The device also performs periodic proximity verification which enables secure enclave revocation by detaching the device. Although proximity verification has been proposed as a defense against relay attacks before, this paper is the first to experimentally demonstrate that it can be secure and reliable for TEEs like SGX. Additionally, we consider a stronger adversary that has obtained leaked SGX attestation keys and emulates an enclave on the target platform. To address such emulation attacks, we propose a second solution where the target platform is securely initialized by booting it from the attached embedded device.

A two-party coin-flipping protocol is $\epsilon$-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\epsilon$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript '85] constructed a $\Theta(1/\sqrt{r})$-fair coin-flipping protocol, assuming the existence of one-way functions. Moran et al. [Journal of Cryptology '16] constructed an $r$-round coin-flipping protocol that is $\Theta(1/r)$-fair (thus matching the aforementioned lower bound of Cleve [STOC '86]), assuming the existence of oblivious transfer. The above gives rise to the intriguing question of whether oblivious transfer, or more generally ``public-key primitives'', is required for an $o(1/\sqrt r)$-fair coin flipping. This question was partially answered by Dachman-Soled et al. [TCC '11] and Dachman-Soled et al. [TCC '14], who showed that restricted types of fully black-box reductions cannot establish $o(1/\sqrt r)$-fair coin-flipping protocols from one-way functions. In particular, for constant-round coin-flipping protocols, Dachman-Soled et al. showed that black-box techniques from one-way functions can only guarantee fairness of order $1/\sqrt{r}$. We make progress towards answering the above question by showing that, for any constant $r\in \mathbb N$, the existence of an $1/(c\cdot \sqrt{r})$-fair, $r$-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where $c$ denotes some universal constant (independent of $r$). Our reduction is non black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [FOCS '18] to facilitate a two-party variant of the recent attack of Beimel et al. [FOCS '18] on multi-party coin-flipping protocols.

Trapdoor permutations (TDP) are a fundamental primitive in cryptography. Over the years, several variants of this notion have emerged as a result of various applications. However, it is not clear whether these variants may be based on the standard notion of TDPs. We study the question of whether enhanced trapdoor permutations can be based on classical trapdoor permutations. The main motivation of our work is in the context of existing TDP-based constructions of oblivious transfer and non-interactive zero-knowledge protocols, which require enhancements to the classical TDP notion. We prove that these enhancements are non-trivial, in the sense that there does not exist fully blackbox constructions of enhanced TDPs from classical TDPs. At a technical level, we show that the enhanced TDP security of any construction in the random TDP oracle world can be broken via a polynomial number of queries to the TDP oracle as well as a weakening oracle, which provides inversion with respect to randomness. We also show that the standard one-wayness of a random TDP oracle stays intact in the presence of this weakening oracle.

In this paper, we propose a new algorithm inspired by Nested to find a differential path in ARX ciphers. In order to enhance the decision process of our algorithm and to reduce the search space of our heuristic nested tool, we use the concept of partial difference distribution table (pDDT) along with the algorithm. The algorithm itself is applied on reduced round variants of the SPECK block cipher family. In our previous paper, we applied a naive algorithm with a large search space of values and presented the result only for one block size variant of SPECK. In this new approach, we provide the results within a simpler framework and within a very short period of time for all bigger block size variants of SPECK. More specifically, we report the differential path for up to 8, 9, 11, 10 and 11 rounds of SPECK32, SPECK48, SPECK64, SPECK96 and SPECK128, respectively. To construct a differential characteristics for large number of rounds, we divide long characteristics into short ones, by easily constructing a large characteristic from two short ones. Instead of starting from the first round, we start from the middle and run the experiments forwards as well as in the reverse direction. Using this method, we were able to improve our previous results and report the differential path for up to 9, 10, 12, 13 and 15 rounds of SPECK32, SPECK48, SPECK64, SPECK96 and SPECK128, respectively.

In this paper we focus on differential cryptanalysis dedicated to a particular class of cryptographic algorithms, namely ARX ciphers. We propose a new algorithm inspired by the Nested Monte-Carlo Search algorithm to find a differential path in ARX ciphers. We apply our algorithm to a round reduced variant of the block cipher LEA. We use the concept of a partial difference distribution table (pDDT) in our algorithm to reduce the search space. This methodology reduced the search space of the algorithm by using only those differentials whose probabilities are greater than or equal to pre-defined threshold. Using this concept we removed many differentials which are not valid or whose probabilities are very low. By doing this we decreased the time of finding a differential path by our nested algorithm due to a smaller search space. This partial difference distribution table also made our nested algorithm suitable for bigger block size ARX ciphers. Finding long differential characteristics is one of the hardest problems where we have seen other algorithms take many hours or days to find differential characteristics in ARX ciphers. Our algorithm finds the differential characteristics in just a few minutes with a very simple framework. We report the differential path for up to 9 rounds in LEA. To construct differential characteristics for a large number of rounds, we divide long characteristics into short ones, by constructing a large characteristic from two short characteristics. Instead of starting from the first round, we start from the middle and run experiments in forward as well as in the reverse direction. Using this method we improved our results and report the differential path for up to 12 rounds. Overall, the best property of our algorithm is that it has potential to provide state-of-the-art results but within a simpler framework as well as less time. Our algorithm is also very interesting for future aspect of research, as it could be applied to other ARX ciphers with a very easy going framework.

A traitor tracing scheme is a public key encryption scheme for which there are many secret decryption keys. Any of these keys can decrypt a ciphertext; moreover, even if a coalition of users collude, put together their decryption keys and attempt to create a new decryption key, there is an efficient algorithm to trace the new key to at least one the colluders. Recently, Goyal, Koppula and Waters (GKW, STOC 18) provided the first traitor tracing scheme from LWE with ciphertext and secret key sizes that grow polynomially in $\log n$, where $n$ is the number of users. The main technical building block in their construction is a strengthening of (bounded collusion secure) secret-key functional encryption which they refer to as mixed functional encryption (FE). In this work, we improve upon and extend the GKW traitor tracing scheme: - We provide simpler constructions of mixed FE schemes based on the LWE assumption. Our constructions improve upon the GKW construction in terms of expressiveness, modularity, and security. - We provide a construction of attribute-based traitor tracing for all circuits based on the LWE assumption.

We consider the following paradoxical question: Can one prove lack of knowledge? We define the notion of 'Proofs of Ignorance', construct such proofs, and use these proofs to construct a 2-message witness hiding protocol for all of NP. More specifically, we define a proof of ignorance (PoI) with respect to any language L in NP and distribution D over instances in L. Loosely speaking, such a proof system allows a prover to generate an instance x according to D along with a proof that she does not know a witness corresponding to x. We construct construct a PoI protocol for any random self-reducible NP language L that is hard on average. Our PoI protocol is non-interactive assuming the existence of a common reference string. We use such a PoI protocol to construct a 2-message witness hiding protocol for NP with adaptive soundness. Constructing a 2-message WH protocol for all of NP has been a long standing open problem. We construct our witness hiding protocol using the following ingredients (where T is any super-polynomial function in the security parameter): 1. T-secure PoI protocol, 2. T-secure non-interactive witness indistinguishable (NIWI) proofs, 3. T-secure rerandomizable encryption with strong KDM security with bounded auxiliary input, where the first two ingredients can be constructed based on the $T$-security of DLIN. At the heart of our witness-hiding proof is a new non-black-box technique. As opposed to previous works, we do not apply an efficiently computable function to the code of the cheating verifier, rather we resort to a form of case analysis and show that the prover's message can be simulated in both cases, without knowing in which case we reside.

The round complexity of zero-knowledge protocols is a long-standing open question, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box. We introduce a new non-black-box technique and use it to obtain the first protocols that cross this barrier under standard assumptions. Our main results are: \begin{itemize} \item Weak zero-knowledge for $NP $in two messages, assuming quasipolynomially-secure fully-homomorphic encryption and other standard primitives (known from quasipolynomial hardness of Learning with Errors), as well as subexponentially-secure one-way functions. \item Weak zero-knowledge for $NP$ in three messages under standard polynomial assumptions (following for example from fully-homomorphic encryption and factoring). \end{itemize} We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language $L \in NP$ that has a witness encryption scheme. This protocol is also publicly verifiable. Our technique is based on a new {\em homomorphic trapdoor paradigm}, which can be seen as a non-black-box analog of the classic Feige-Lapidot-Shamir trapdoor paradigm.

We show that any multi-party functionality can be evaluated using a two-round protocol with perfect correctness and perfect semi-honest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semi-honest MPC, resolving a longstanding open question (cf. Ishai and Kushilevitz, FOCS 2000). The protocol is efficient for $NC^1$ functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security. Our results are based on a new notion of \emph{multi-party randomized encoding} which extends and relaxes the standard notion of randomized encoding of functions (Ishai and Kushilevitz, FOCS 2000). The property of a multi-party randomized encoding (MPRE) is that if the functionality $g$ is an encoding of the functionality $f$, then for any (permitted) coalition of players, their respective outputs and inputs in $g$ allow them to simulate their respective inputs and outputs in $f$, without learning anything else, including the other outputs of $f$. We further introduce a new notion of effective algebraic degree, and show that the round complexity of a functionality $f$ is characterized by the degree of its MPRE. We construct degree-2 MPREs for general functionalities in several settings under different assumptions, and use these constructions to obtain two-round protocols. Our constructions also give rise to new protocols in the client-server model with optimal round complexity.

One approach for blockchain based applications to provide a proof-of-work is the computation of hash-values. In our opinion these computations are a waste of energy. It would be highly desirable to find an alternative method that generates useful output. We show how to substitute hashing by performing multiplications on Elliptic Curves in order to find distinguished points that can then be used to solve the discrete logarithm problem on a chosen curve. Today's digital infrastructures rely on only a few curves. We argue that the advent of blockchain based technologies makes the use of only few standardised curves questionable. In principle all cryptanalytic algorithms that use Rabin's idea of distinguished points can be used in blockchain based attacks. Similar ideas can be used for the number field sieve.

Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC '87 and J. ACM '96) is a technique for provably obfuscating programs' access patterns, such that the access patterns leak no information about the programs' secret inputs. To compile a general program to an oblivious counterpart, it is well-known that $\Omega(\log N)$ amortized blowup is necessary, where $N$ is the size of the logical memory. This was shown in Goldreich and Ostrovksy's original ORAM work for statistical security and in a somewhat restricted model (the so called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO '18) for computational security. A long standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this paper, we resolve this problem and present the first secure ORAM with $O(\log N)$ amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS '18) who gave a construction with $O(\log N\cdot \log\log N)$ amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of $n$ elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our $O(n)$ algorithm improves the previously best known deterministic or randomized algorithms whose running time is $O(n \cdot\log n)$ or $O(n \cdot\log \log n)$, respectively.

The concept of the Industrial Internet of Things (IIoT) can be defined as the integration of smart sensor networks and the Internet of Things (IoT). This technology can be employed in various industries such as agriculture, food processing industry, environmental monitoring, security surveillance, and so on. Generally, a smart sensor is a resource-constrained device which is responsible for gathering data from the monitored area. Machine-to-Machine (M2M) communication is one of the most important technologies to exchange information between entities in industrial areas. However, due to the insecure wireless communication channel and the smart sensor’s limitations, security and privacy concerns are the important challenges in IIoT environments. The goal of this paper is to address the security flaws of a recent M2M authentication protocol proposed for employing in IIoT including DoS, router impersonation and smart sensor traceability attacks. Moreover, we showed that an untrusted smart sensor can obtain the secret key of the router and the session key which another sensor establishes with the target router.

Constrained pseudorandom functions (CPRFs) allow learning modified PRF keys that can evaluate the PRF on a subset of the input space, or based on some sort of predicate. First introduced by Boneh and Waters [Asiacrypt 2013], they have been shown to be a useful cryptographic primitive with many applications. The full security definition of CPRFs requires the adversary to learn multiple constrained keys, a requirement for all of these applications. Unfortunately, existing constructions of CPRFs satisfying this security notion are only known from exceptionally strong cryptographic assumptions, such as indistinguishability obfuscation and the existence of multilinear maps, even for very weak predicates. CPRFs from more standard assumptions only satisfy security when one key is learnt. In this work, we give the first construction of a CPRF that can issue a constant number of constrained keys for bit-fixing predicates, from learning with errors (LWE). It also satisfies \(1\)-key privacy (otherwise known as constraint-hiding). Finally, our construction achieves fully adaptive security with polynomial security loss; the only construction to achieve such security under a standard assumption. Our technique represents a noted departure existing for CPRF constructions. We hope that it may lead to future constructions that can expose a greater number of keys, or consider more expressive predicates (such as circuit-based constraints).

Following up mass surveillance and privacy issues, modern secure communication protocols now seek more security such as forward secrecy and post-compromise security. They cannot rely on an assumption such as synchronization, predictable sender/receiver roles, or online availability. Ratcheting was introduced to address forward secrecy and post-compromise security in real-world messaging protocols. At CSF 2016 and CRYPTO 2017, ratcheting was studied either without zero round-trip time (0-RTT) or without bidirectional communication. At CRYPTO 2018, ratcheting with bidirectional communication was done using heavy key-update primitives. At EUROCRYPT 2019, another protocol was proposed. All those protocols use random oracles. Furthermore, exchanging $n$ messages has complexity $O(n^2)$. In this work, we define the bidirectional asynchronous ratcheted key agreement (BARK) with formal security notions. We provide a simple security model and design a secure BARK scheme using no key-update primitives, no random oracle, and with $O(n)$ complexity. It is based on a cryptosystem, a signature scheme, one-time symmetric encryption, and a collision-resistant hash function family. We further show that BARK (even unidirectional) implies public-key cryptography, meaning that it cannot solely rely on symmetric cryptography.

Servers with many cores cost a lot of money and consume large amounts of energy. The developments in hardware for mobile devices has resulted in a surge in relatively cheap, powerful, and low-energy CPUs. In this paper we show how to build a low-energy, eighty-core cluster built around twenty ODROID-C2 development boards for under 1500 USD. The ODROID-C2 is a 46 USD microcomputer that provides a 1.536 GHz quad-core Cortex-A53-based CPU and 2 GB of RAM. We investigate the cluster's application to cryptanalysis by implementing Pollard's Rho method to tackle the Certicom ECC2K-130 elliptic curve challenge. We optimise software from the "Breaking ECC2K-130" technical report for the Cortex-A53. To do so, we show how to use microbenchmarking to derive the needed instruction characteristics which ARM neglected to document for the public. The implementation of the ECC2K-130 attack finally allows us to compare the proposed platform to various other platforms, including “classical” desktop CPUs, GPUs and FPGAs. Although it may still be slower than for example FPGAs, our cluster still provides a lot of value for money.

Hash functions are of fundamental importance in theoretical and in practical cryptography, and with the threat of quantum computers possibly emerging in the future, it is an urgent objective to understand the security of hash functions in the light of potential future quantum attacks. To this end, we reconsider the collapsing property of hash functions, as introduced by Unruh, which replaces the notion of collision resistance when considering quantum attacks. Our contribution is a formalism and a framework that offers significantly simpler proofs for the collapsing property of hash functions. With our framework, we can prove the collapsing property for hash domain extension constructions entirely by means of decomposing the iteration function into suitable elementary composition operations. In particular, given our framework, one can argue purely classically about the quantum-security of hash functions; this is in contrast to previous proofs which are in terms of sophisticated quantum-information-theoretic and quantum-algorithmic reasoning.

Password authenticated key establishment (PAKE) is a cryptographic primitive that allows two parties who share a low-entropy secret (a password) to securely establish cryptographic keys in the absence of public key infrastructure. We propose the first quantum-resistant password-authenticated key exchange scheme based on supersingular elliptic curve isogenies. The scheme is built upon supersingular isogeny Diffie-Hellman, and uses the password to generate permutations which obscure the auxiliary points. We include elements of a security proof, and discuss roadblocks to obtaining a proof in the BPR model. We also include some performance results.

Token-based authentication is commonly used to enable a single-sign-on experience on the web, in mobile applications and on enterprise networks using a wide range of open standards and network authentication protocols: clients sign on to an identity provider using their username/password to obtain a cryptographic token generated with a master secret key, and store the token for future accesses to various services and applications. The authentication server(s) are single point of failures that if breached, enable attackers to forge arbitrary tokens or mount offline dictionary attacks to recover client credentials. Our work is the first to introduce and formalize the notion of password-based threshold token-based authentication which distributes the role of an identity provider among $n$ servers. Any t servers can collectively verify passwords and generate tokens, while no t-1 servers can forge a valid token or mount offline dictionary attacks. We then introduce PASTA, a general framework that can be instantiated using any threshold token generation scheme, wherein clients can "sign-on" using a two-round (optimal) protocol that meets our strong notions of unforgeability and password-safety. We instantiate and implement our framework in C++ using two threshold message authentication codes (MAC) and two threshold digital signatures with different trade-offs. Our experiments show that the overhead of protecting secrets and credentials against breaches in PASTA, i.e. compared to a naive single server solution, is extremely low (1-5%) in the most likely setting where client and servers communicate over the internet. The overhead is higher in case of MAC-based tokens over a LAN (though still only a few milliseconds) due to public-key operations in PASTA. We show, however, that this cost is inherent by proving a symmetric-key only solution impossible.

A multitude of post-quantum key encapsulation mechanisms (KEMs) and public key encryption (PKE) schemes implicitly rely on a protocol by which Alice and Bob exchange public messages and converge on secret values that are identical up to some small noise. By our count, 24 out of 49 KEM or PKE submissions to the NIST Post-Quantum Cryptography Standardization project follow this strategy. Yet the notion of a noisy key agreement (NKA) protocol lacks a formal definition as a primitive in its own right. We provide such a formalization by defining the syntax and security for an NKA protocol. This formalization brings out four generic problems, called A and B State Recovery, Noisy Key Search and Noisy Key Distinguishing, whose solutions must be hard in the quantum computing model. Informally speaking, these can be viewed as noisy, quantum-resistant counterparts of the problems arising from the classical Diffie-Hellman type protocols. We show that many existing proposals contain an NKA component that fits our formalization and we reveal the induced concrete hardness assumptions. The question arises whether considering NKA as an independent primitive can help provide modular designs with improved efficiency and/or proofs. As the second contribution of this paper, we answer this question positively by presenting a generic transform from a secure NKA protocol to an IND-CCA secure KEM in the quantum random oracle model, with a security bound tightly related to the NKD problem. This transformation is essentially the same as that of the NIST candidate Ramstake. While establishing the security of Ramstake was our initial objective, the collection of tools that came about as a result of this journey is of independent interest.

In this paper, we introduce a new framework for constructing public-key encryption (PKE) schemes resilient to joint post-challenge/after-the-fact leakage and tampering attacks in the bounded leakage and tampering (BLT) model, introduced by Damgård et al. (Asiacrypt 2013). All the prior formulations of PKE schemes considered leakage and tampering attacks only before the challenge ciphertext is made available to the adversary. However, this restriction seems necessary, since achieving security against post-challenge leakage and tampering attacks in its full generality is impossible as shown in previous works. In this paper, we study the post-challenge/after-the-fact security for PKE schemes against bounded leakage and tampering under a restricted yet meaningful and reasonable notion of security, namely, the split-state leakage and tampering model. We show that it is possible to construct secure PKE schemes in this model, tolerating arbitrary (but bounded) leakage and tampering queries; thus overcoming the previous impossibility results. To this end, we formulate a new notion of security, which we call entropic post-challenge IND-CCA-BLT secure PKE. We first define a weaker notion called entropic restricted post-challenge IND-CCA-BLT secure PKE, which can be instantiated using the (standard) DDH assumption. We then show a generic compiler from our entropic restricted notion to the entropic notion of security using a simulation-extractable non-interactive zero-knowledge argument system. This requires an untamperable common reference string as in previous works. Finally, we demonstrate the usefulness of our entropic notion of security by giving a simple and generic construction of post-challenge IND-CCA-BLT secure PKE scheme in the split-state leakage and tampering model. This also settles the open problem posed by Faonio and Venturi (Asiacrypt 2016).

Diffie--Hellman key exchange is at the foundations of public-key cryptography, but conventional group-based Diffie--Hellman is vulnerable to Shor's quantum algorithm. A range of ``post-quantum Diffie--Hellman'' protocols have been proposed to mitigate this threat, including the Couveignes, Rostovtsev--Stolbunov, SIDH, and CSIDH schemes, all based on the combinatorial and number-theoretic structures formed by isogenies of elliptic curves. Pre- and post-quantum Diffie--Hellman schemes resemble each other at the highest level, but the further down we dive, the more differences emerge---differences that are critical when we use Diffie--Hellman as a basic component in more complicated constructions. In this survey we compare and contrast pre- and post-quantum Diffie--Hellman algorithms, highlighting some important subtleties.

The current practice in board-level integration is to incorporate chips and components from numerous vendors. A fully trusted supply chain for all used components and chipsets is an important, yet extremely difficult to achieve, prerequisite to validate a complete board-level system for safe and secure operation. An increasing risk is that most chips nowadays run software or firmware, typically updated throughout the system lifetime, making it practically impossible to validate the full system at every given point in the manufacturing, integration and operational life cycle. This risk is elevated in devices that run 3rd party firmware. In this paper we show that an FPGA used as a common accelerator in various boards can be reprogrammed by software to introduce a sensor, suitable as a remote power analysis side-channel attack vector at the board-level. We show successful power analysis attacks from one FPGA on the board to another chip implementing RSA and AES cryptographic modules. Since the sensor is only mapped through firmware, this threat is very hard to detect, because data can be exfiltrated without requiring inter-chip communication between victim and attacker. Our results also prove the potential vulnerability in which any untrusted chip on the board can launch such attacks on the remaining system.

Recent publications, such as [10] and [13], exploit the advantages of deep-learning techniques in performing Side-Channel Attacks. One example of the Side-Channel community interest for such techniques is the release of the public ASCAD database, which provides power consumption traces of a masked 128-bit AES implementation, and is meant to be a common benchmark to compare deep-learning techniques performances. In this paper, we propose two ways of improving the effectiveness of such attacks. The first one is as new kind of layer for neural networks, called "Spread" layer, which is efficient at tackling side-channel attacks issues, since it reduces the number of layers required and speeds up the learning phase. Our second proposal is an efficient way to correct the neural network predictions, based on its confusion matrix. We have validated both methods on ASCAD database, and conclude that they reduce the number of traces required to succeed attacks. In this article, we show their effectiveness for first-order and second-order attacks.

Group signature is a useful cryptographic primitive, which makes every group member sign messages on behalf of a group they belong to. Namely group signature allows that group member anonymously signs any message without revealing his/her specific identity. However, group signature may make the signers abuse their signing rights if there are no measures of keeping them from abusing signing rights in the group signature schemes. So, group manager must be able to trace (or reveal) the identity of the signer by the signature when the result of the signature needs to be arbitrated, and some revoked group members must fully lose their capability of signing a message on behalf of the group they belong to. A practical model meeting the requirement is verifier-local revocation, which supports the revocation of group member. In this model, the verifiers receive the group member revocation messages from the trusted authority when the relevant signatures need to be verified. Although currently many group signature schemes have been proposed, most of them are constructed on pairings. In this paper, we present an efficient group signature scheme without pairings under the model of verifier-local revocation, which is based on the modified EDL signature (first proposed by D. Chaum et al. in Crypto 92). Compared with other group signature schemes, the proposed scheme does not employ pairing computation and has the constant signing time and signature size, whose security can be reduced to the computational Diffie-Hellman (CDH) assumption in the random oracle model. Also, we give a formal security model for group signature and prove that the proposed scheme has the properties of traceability and anonymity.

We would like to compute RSA signatures with the help of a Hardware Security Module (HSM). But what can we do when we want to use a certain public exponent that the HSM does not allow or support? Surprisingly, this scenario comes up in real-world settings such as code-signing of Intel SGX enclaves. Intel SGX enclaves have to be signed in order to execute in release mode, using 3072-bit RSA signature scheme with a particular public exponent. However, we encountered commercial hardware security modules that do not support storing RSA keys corresponding to this exponent. We ask whether it is possible to overcome such a limitation of an HSM and answer it in the affirmative (under stated assumptions). We show how to convert RSA signatures corresponding to one public exponent, to valid RSA signatures corresponding to another exponent. We define security and show that it is not compromised by the additional public knowledge available to an adversary in this setting.

Recently, Bellare et al. defined subversion-resistance (security in the case the CRS creator may be malicious) for NIZK. In particular, a Sub-ZK NIZK is zero-knowledge, even in the case of subverted CRS. We study Sub-ZK QA-NIZKs, where the CRS can depend on the language parameter. First, we observe that subversion zero-knowledge (Sub-ZK) in the CRS model corresponds to no-auxiliary-string non-black-box NIZK in the Bare Public Key model, and hence, the use of non-black-box techniques is needed to obtain Sub-ZK. Second, we give a precise definition of Sub-ZK QA-NIZKs that are (knowledge-)sound if the language parameter but not the CRS is subverted and zero-knowledge even if both are subverted. Third, we prove that the most efficient known QA-NIZK for linear subspaces by Kiltz and Wee is Sub-ZK under a new knowledge assumption that by itself is secure in (a weaker version of) the algebraic group model. Depending on the parameter setting, it is (knowledge-)sound under different non-falsifiable assumptions, some of which do not belong to the family of knowledge assumptions.

The 3rd Generation Partnership Project (3GPP) recently proposed a standard for 5G telecommunications, containing an identity protection scheme meant to address the long-outstanding privacy problem of permanent subscriber-identity disclosure. The proposal is essentially two disjoint phases: an identification phase, followed by an establishment of security context between mobile subscribers and their service providers via symmetric-key based authenticated key agreement. Currently, 3GPP proposes to protect the identification phase with a public-key based solution, and while the current proposal is secure against a classical adversary, the same would not be true of a quantum adversary. 5G specifications target very long-term deployment scenarios (well beyond the year 2030), therefore it is imperative that quantum-secure alternatives be part of the current specification. In this paper, we present such an alternative scheme for the problem of private identification protection. Our solution is compatible with the current 5G specifications, depending mostly on cryptographic primitives already specified in 5G, adding minimal performance overhead and requiring minor changes in existing message structures. Finally, we provide a detailed formal security analysis of our solution in a novel security framework.

Secure message transmission and Byzantine agreement have been studied extensively in incomplete networks. However, information theoretically secure multiparty computation (MPC) in incomplete networks is less well understood. In this paper, we characterize the conditions under which a pair of parties can compute oblivious transfer (OT) information theoretically securely against a general adversary structure in an incomplete network of reliable, private channels. We provide characterizations for both semi-honest and malicious models. A consequence of our results is a complete characterization of networks in which a given subset of parties can compute any functionality securely with respect to an adversary structure in the semi-honest case and a partial characterization in the malicious case.

Despite the recent advances in attribute-based signatures (ABS), no schemes have yet been considered under a strong privacy definition. We enhance the security of ABS by presenting a strengthened simulation-based privacy definition and the first attribute-based signature functionality in the framework of universal composability (UC). Additionally, we show that the UC definition is equivalent to our strengthened experiment-based security definitions. To achieve this we rely on a general unforgeability and a simulation-based privacy definition that is stronger than standard indistinguishability-based privacy. Further, we show that two extant concrete ABS constructions satisfy this simulation-based privacy definition and are therefore UC secure. The two concrete constructions are the schemes by Sakai et al. (PKC'16) and by Maji et al. (CT-RSA'11). Additionally, we identify the common feature that allows these schemes to meet our privacy definition, giving us further insights into the security requirements of ABS.

We introduce a simple, yet efficient digital signature scheme which offers post-quantum security promise. Our scheme, named $\texttt{TACHYON}$, is based on a novel approach for extending one-time hash-based signatures to (polynomially bounded) many-time signatures, using the additively homomorphic properties of generalized compact knapsack functions. Our design permits $\texttt{TACHYON}$ to achieve several key properties. First, its signing and verification algorithms are the fastest among its current counterparts with a higher level of security. This allows $\texttt{TACHYON}$ to achieve the lowest end-to-end delay among its counterparts, while also making it suitable for resource-limited signers. Second, its private keys can be as small as $\kappa$ bits, where $\kappa$ is the desired security level. Third, unlike most of its lattice-based counterparts, $\texttt{TACHYON}$ does not require any Gaussian sampling during signing, and therefore, is free from side-channel attacks targeting this process. We also explore various speed and storage trade-offs for $\texttt{TACHYON}$, thanks to its highly tunable parameters. Some of these trade-offs can speed up $\texttt{TACHYON}$ signing in exchange for larger keys, thereby permitting $\texttt{TACHYON}$ to further improve its end-to-end delay.

We develop techniques for constructing trapdoor functions (TDFs) with short image size and advanced security properties. Our approach builds on the recent framework of Garg and Hajiabadi [CRYPTO 2018]. As applications of our techniques, we obtain -- The first construction of deterministic-encryption schemes for block-source inputs (both for the CPA and CCA cases) based on the Computational Diffie-Hellman (CDH) assumption. Moreover, by applying our efficiency-enhancing techniques, we obtain CDH-based schemes with ciphertext size linear in plaintext size. -- The first construction of lossy TDFs based on the Decisional Diffie-Hellman (DDH) assumption with image size linear in input size, while retaining the lossiness rate of [Peikert-Waters STOC 2008]. Prior to our work, all constructions of deterministic encryption based even on the stronger DDH assumption incurred a quadratic gap between the ciphertext and plaintext sizes. Moreover, all DDH-based constructions of lossy TDFs had image size quadratic in the input size. At a high level, we break the previous quadratic barriers by introducing a novel technique for encoding input bits via hardcore output bits with the use of erasure-resilient codes. All previous schemes used group elements for encoding input bits, resulting in quadratic expansions.

As one of the most prevalent SCA countermeasures, masking schemes are designed to defeat a broad range of side channel attacks. An attack vector that is suitable for low-order masking schemes is to try and directly determine the mask(s) (for each trace) by utilising the fact that often an attacker has access to several leakage points of the respectively used mask(s). Good examples for implementations of low order masking schemes are the based on table re-computations and also the masking scheme in DPAContest V4.2. We propose a novel approach based on Independent Component Analysis (ICA) to efficiently utilise the information from several leakage points to reconstruct the respective masks (for each trace) and show it is a competitive attack vector in practice.

We present two simple backdoors that can be implemented into Maurer's unified zero-knowledge protocol. Thus, we show that a high level abstraction can replace individual backdoors embedded into protocols for proving knowledge of a discrete logarithm (e.g. the Schnorr and Girault protocols), protocols for proving knowledge of an $e^{th}$-root (e.g. the Fiat-Shamir and Guillou-Quisquater protocols), protocols for proving knowledge of a discrete logarithm representation (e.g. the Okamoto protocol) and protocols for proving knowledge of an $e^{th}$-root representation.

At CHES 2016, Bos et al. introduced $\textit{differential computational analysis}$ (DCA) as an attack on white-box software implementations of block ciphers. This attack builds on the same principles as DPA in the classical side-channel context, but uses computational traces consisting of plain values computed by the implementation during execution. This attack was shown to be able to recover the key of many existing AES white-box implementations. The DCA adversary is $\textit{passive}$, and so does not exploit the full power of the white-box setting, implying that many white-box schemes are insecure even in a weaker setting than the one they were designed for. It is therefore important to develop implementations which are resistant to this attack. We investigate the approach of applying standard side-channel countermeasures such as $\textit{masking}$ and $\textit{shuffling}$. Under some necessary conditions on the underlying randomness generation, we show that these countermeasures provide resistance to standard (first-order) DCA. Furthermore, we introduce $\textit{higher-order DCA}$, along with an enhanced $\textit{multivariate}$ version, and analyze the security of the countermeasures against these attacks. We derive analytic expressions for the complexity of the attacks -- backed up through extensive attack experiments -- enabling a designer to quantify the security level of a masked and shuffled implementation in the (higher-order) DCA setting.

Nowadays, mobile banking becomes a popular tool which consumers can conduct financial transactions such as shopping, monitoring accounts balance, transferring funds and other payments. Consumers dependency on mobile needs, make people take a little bit more interest in mobile banking. The use of the one-time password which is sent to the user mobile phone by short message service (SMS) is a vulnerability which we want to solve with proposing a new scheme called S-Mbank. We replace the authentication using the one-time password with the contactless smart card to prevent attackers to use the unencrypted message which is sent to the user's mobile phone. Moreover, it deals vulnerability of spoofer to send an SMS pretending as a bank's server. The contactless smart card is proposed because of its flexibility and security which easier to bring in our wallet than the common passcode generators. The replacement of SMS-based authentication with contactless smart card removes the vulnerability of unauthorized users to act as a legitimate user to exploit the mobile banking user's account. Besides that, we use public-private key pair and PIN to provide two factors authentication and mutual authentication. We use signcryption scheme to provide the efficiency of the computation. Pair based text authentication is also proposed for the login process as a solution to shoulder-surfing attack. We use Scyther tool to analyze the security of authentication protocol in S-Mbank scheme. From the proposed scheme, we are able to provide more security protection for mobile banking service.

Rank estimation is an important tool for a side-channel evaluations laboratories. It allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over $d$ subkeys (usually key bytes). These estimations are particularly useful where the key is not reachable with exhaustive search. We propose ESrank, the first rank estimation algorithm that enjoys provable poly-logarithmic time- and space-complexity, which also achieves excellent practical performance. Our main idea is to use exponential sampling to drastically reduce the algorithm's complexity. Importantly, ESrank is simple to build from scratch, and requires no algorithmic tools beyond a sorting function. After rigorously bounding the accuracy, time and space complexities, we evaluated the performance of ESrank on a real SCA data corpus, and compared it to the currently-best histogram-based algorithm. We show that ESrank gives excellent rank estimation (with roughly a 1-bit margin between lower and upper bounds), with a performance that is on-par with the Histogram algorithm: a run-time of under 1 second on a standard laptop using 6.5 MB RAM.

In this work, we study the fascinating notion of output-compressing randomized encodings for Turing Machines, in a shared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct output- compressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the set {LWE, DDH, Nth Residuosity}. We then show interesting implications of the above result to basic feasibility questions in the areas of secure multiparty computation (MPC) and indistinguishability obfuscation (iO): 1. Compact MPC for Turing Machines in the Random Oracle Model: In the context of MPC, we consider the following basic feasibility question: does there exist a malicious-secure MPC protocol for Turing Machines whose communication complexity is independent of the running time and output length of the Turing Machine when executed on the combined inputs of all parties? We call such a protocol as a compact MPC protocol. Hubacek and Wichs [HW15] showed via an incompressibility argument, that, even for the restricted setting of circuits, it is impossible to construct a malicious secure two party computation protocol in the plain model where the communication complexity is independent of the output length. In this work, we show how to evade this impossibility by compiling any (non-compact) MPC protocol in the plain model to a compact MPC protocol for Turing Machines in the Random Oracle Model, assuming output-compressing randomized encodings in the shared randomness model. 2. Succinct iO for Turing Machines in the Shared Randomness Model: In all existing constructions of iO for Turing Machines, the size of the obfuscated program grows with a bound on the input length. In this work, we show how to construct an iO scheme for Turing Machines in the shared randomness model where the size of the obfuscated program is independent of a bound on the input length, assuming iO for circuits and any assumption in the set {LWE, DDH, Nth Residuosity}.

Hardware masked AES designs usually rely on Boolean masking and perform the computation of the S-box using the tower-field decomposition. On the other hand, splitting sensitive variables in a multiplicative way is more amenable for the computation of the AES S-box, as noted by Akkar and Giraud. However, multiplicative masking needs to be implemented carefully not to be vulnerable to first-order DPA with a zero-value power model. Up to now, sound higher-order multiplicative masking schemes have been implemented only in software. In this work, we demonstrate the first hardware implementation of AES using multiplicative masks. The method is tailored to be secure even if the underlying gates are not ideal and glitches occur in the circuit. We detail the design process of first- and second-order secure AES-128 cores, which result in the smallest die area to date among previous state-of-the-art masked AES implementations with comparable randomness cost and latency. The first- and second-order masked implementations improve resp. 29% and 18% over these designs. We deploy our construction on a Spartan-6 FPGA and perform a side-channel evaluation. No leakage is detected with up to 50 million traces for both our first- and second-order implementation. For the latter, this holds both for univariate and bivariate analysis.

Mixing Networks are protocols that allow a set of senders to send messages anonymously. Such protocols are fundamental building blocks to achieve privacy in a variety of applications, such as anonymous e-mail, anonymous payments, and electronic voting. Back in 2002, Golle et al. proposed a new concept of mixing network, called optimistic mixing, that allows for fast mixing when all the parties execute the protocol honestly. If, on the other hand, one or more mix-servers cheat, then the attack is recognized and one can back up to a different, slow mix-net. Unfortunately, Abe and Imai (ACISP'03) and independently Wikström (SAC'03) showed several major flaws in the optimistic protocol of Golle et al. In this work, we give another look at optimistic mixing networks. Our contribution is mainly threefold. First, we give formal definitions for optimistic mixing in the UC model. Second, we propose a compiler for obtaining a UC-secure mixing network by combining an optimistic mixing with a traditional mixing protocol as backup mixing. Third, we propose an efficient UC-secure realization of optimistic mixing based on the DDH assumption in the non-programmable random oracle model. As a key ingredient of our construction, we give a new randomizable replayable-CCA secure public key encryption (PKE) that outperforms in efficiency all previous schemes. We believe this result is of independent interest.

We present Helix, a Byzantine fault tolerant and scalable consensus algorithm for fair ordering of transactions among nodes in a distributed network. In Helix, one among the network nodes proposes a potential set of successive transactions (block). The known PBFT protocol is then run within a bounded-size committee in order to achieve agreement and commit the block to the blockchain indefinitely. In Helix, transactions are encrypted via a threshold encryption scheme in order to hide information from the ordering nodes, limiting censorship and front-running. The encryption is further used to realize a verifiable source of randomness, which in turn is used to elect the committees in an unpredictable way, as well as to introduce a correlated sampling scheme of transactions included in a proposed block. The correlated sampling scheme restricts nodes from promoting their own transactions over those of others. Nodes are elected to participate in committees in proportion to their relative reputation. Reputation, attributed to each node, serves as a measure of obedience to the protocol's instructions. Committees are thus chosen in a way that is beneficial to the protocol.

This paper studies the security of Ring Oscillator Physically Unclonable Function (PUF) with Enhanced Challenge-Response Pairs as proposed by Delavar et al. We present an attack that can predict all PUF responses after querying the PUF with n+2 attacker-chosen queries. This result renders the proposed RO-PUF with Enhanced Challenge-Response Pairs inapt for most typical PUF use cases, including but not limited to all cases where an attacker has query access.

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as a central problem in cryptography, with a flurry of recent activity in both theory and practice. In all of these works, the main bottleneck is the overhead incurred by the server, both in time and in space. Assuming (sub-exponential) LWE, we construct a one-round argument-system for proving the correctness of any time $T$ and space $S$ RAM computation, in which both the verifier and prover are highly efficient. The verifier runs in time $n \cdot polylog(T)$ and space $polylog(T)$, where $n$ is the input length. Assuming $S \geq \max(n,polylog(T))$, the prover runs in time $\tilde{O}(T)$ and space $S + o(S)$, and in many natural cases even $S+polylog(T)$. Our solution uses somewhat homomorphic encryption but, surprisingly, only requires homomorphic evaluation of arithmetic circuits having multiplicative depth (which is a main bottleneck in homomorphic encryption) $\log_2\log(T)+O(1)$. Prior works based on standard assumptions had a $T^c$ time prover, where $c \geq 3$ (at the very least). As for the space usage, we are unaware of any work, even based on non-standard assumptions, that has space usage $S+polylog(T)$. Along the way to constructing our delegation scheme, we introduce several technical tools that we believe may be useful for future work.

The problem of privatizing statistical databases is a well-studied topic that has culminated with the notion of differential privacy. The complementary problem of securing these databases, however, has---as far as we know---not been considered in the past. While the security of private databases is in theory orthogonal to the problem of private statistical analysis (e.g., in the central model of differential privacy the curator is trusted) the recent real-world deployments of differentially-private systems suggest that it will become a problem of increasing importance. In this work, we consider the problem of designing encrypted databases (EDB) that support differentially-private statistical queries. More precisely, these EDBs should support a set of encrypted operations with which a curator can securely query and manage its data, and a set of private operations with which an analyst can privately analyze the data. Using such an EDB, a curator can securely outsource its database to an untrusted server (e.g., on-premise or in the cloud) while still allowing an analyst to privately query it. We show how to design an EDB that supports private histogram queries. As a building block, we introduce a differentially-private encrypted counter based on the binary mechanism of Chan et al. (ICALP, 2010). We then carefully combine multiple instances of this counter with a standard encrypted database scheme to support differentially-private histogram queries.

LowMC is a family of block ciphers designed for a low multiplicative complexity. The specification allows a large variety of instantiations, differing in block size, key size, number of S-boxes applied per round and allowed data complexity. The number of rounds deemed secure is determined by evaluating a number of attack vectors and taking the number of rounds still secure against the best of these. In this paper, we demonstrate that the attacks considered by the designers of LowMC in the version 2 of the round-formular were not sufficient to fend off all possible attacks. In the case of instantiations of LowMC with one of the most useful settings, namely with few applied S-boxes per round and only low allowable data complexities, efficient attacks based on difference enumeration techniques can be constructed. We show that it is most effective to consider tuples of differences instead of simple differences, both to increase the range of the distinguishers and to enable key recovery attacks. All applications for LowMC we are aware of, including signature schemes like Picnic and more recent (ring/group) signature schemes have used version 3 of the round formular for LowMC, which takes our attack already into account.

Sanitizable signature schemes (SSS) enable a designated party (called the sanitizer ) to alter admissible blocks of a signed message. This primitive can be used to remove or alter sensitive data from already signed messages without involvement of the original signer. Current state-of-the-art security definitions of SSSs only dene a \weak" form of security. Namely, the unforgeability, accountability and transparency definitions are not strong enough to be meaningful in certain use-cases. We identify some of these use-cases, close this gap by introducing stronger definitions, and show how to alter an existing construction to meet our desired security level. Moreover, we clarify a small yet important detail in the state-of-the-art privacy definition. Our work allows to deploy this primitive in more and different scenarios.

We present Raptor, the first practical lattice-based (linkable) ring signature scheme with implementation. Raptor is as fast as classical solutions; while the size of the signature is roughly $1.3$ KB per user. Prior to our work, all existing lattice-based solutions are analogues of their discrete-log or pairing-based counterparts. We develop a generic construction of (linkable) ring signatures based on the well-known generic construction from Rivest et al., which is not fully compatible with lattices. We show that our generic construction is provably secure in random oracle model. We also give instantiations from both standard lattice, as a proof of concept, and NTRU lattice, as an efficient instantiation. We showed that the latter construction, called Raptor, is almost as efficient as the classical RST ring signatures and thus may be of practical interest.

The Blockwise-Korkine-Zolotarev (BKZ) lattice reduction algorithm is central in cryptanalysis, in particular for lattice-based cryptography. A precise understanding of its practical behavior in terms of run-time and output quality is necessary for parameter selection in cryptographic design. As the provable worst-case bounds poorly reflect the practical behavior, cryptanalysts rely instead on the heuristic BKZ simulator of Chen and Nguyen (Asiacrypt'11). It fits better with practical experiments, but not entirely. In particular, it over-estimates the norm of the first few vectors in the output basis. Put differently, BKZ performs better than its Chen-Nguyen simulation. In this work, we first report experiments providing more insight on this shorter-than-expected phenomenon. We then propose a refined BKZ simulator by taking the distribution of short vectors in random lattices into consideration. We report experiments suggesting that this refined simulator more accurately predicts the concrete behavior of BKZ. Furthermore, we design a new BKZ variant that exploits the shorter-than-expected phenomenon. For the same cost assigned to the underlying SVP-solver, the new BKZ variant produces bases of better quality. We further illustrate its potential impact by testing it on the SVP-120 instance of the Darmstadt lattice challenge.

The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the most recent version of PKCS#1 (RFC 8017) even recommends a replacement the more complex and less efficient scheme RSA-PSS, as it is provably secure and therefore considered more robust. The main obstacle is that RSA PKCS#1 v1.5 signatures use a deterministic padding scheme, which makes standard proof techniques not applicable. We introduce a new technique that enables the first security proof for RSA-PKCS#1 v1.5 signatures. We prove full existential unforgeability against adaptive chosen-message attacks (EUF-CMA) under the standard RSA assumption. Furthermore, we give a tight proof under the Phi-Hiding assumption. These proofs are in the random oracle model and the parameters deviate slightly from the standard use, because we require a larger output length of the hash function. However, we also show how RSA-PKCS#1 v1.5 signatures can be instantiated in practice such that our security proofs apply. In order to draw a more complete picture of the precise security of RSA PKCS#1 v1.5 signatures, we also give security proofs in the standard model, but with respect to weaker attacker models (key-only attacks) and based on known complexity assumptions. The main conclusion of our work is that from a provable security perspective RSA PKCS#1 v1.5 can be safely used, if the output length of the hash function is chosen appropriately.

In this work, we demonstrate universal multi-party poisoning attacks that adapt and apply to any multi-party learning process with arbitrary interaction pattern between the parties. More generally, we introduce and study $(k,p)$-poisoning attacks in which an adversary controls $k\in[m]$ of the parties, and for each corrupted party $P_i$, the adversary submits some poisoned data $T'_i$ on behalf of $P_i$ that is still "$(1-p)$-close" to the correct data $T_i$ (e.g., $1-p$ fraction of $T'_i$ is still honestly generated). We prove that for any "bad" property $B$ of the final trained hypothesis $h$ (e.g., $h$ failing on a particular test example or having "large" risk) that has an arbitrarily small constant probability of happening without the attack, there always is a $(k,p)$-poisoning attack that increases the probability of $B$ from $\mu$ to by $\mu^{1-p \cdot k/m} = \mu + \Omega(p \cdot k/m)$. Our attack only uses clean labels, and it is online. More generally, we prove that for any bounded function $f(x_1,\dots,x_n) \in [0,1]$ defined over an $n$-step random process $x = (x_1,\dots,x_n)$, an adversary who can override each of the $n$ blocks with \emph{even dependent} probability $p$ can increase the expected output by at least $\Omega(p \cdot \mathrm{Var}[f(x)])$.

Public-key infrastructures (PKIs) are an integral part of the security foundations of digital communications. Their widespread deployment has allowed the growth of important applications, such as, internet banking and e-commerce. Centralized PKIs (CPKIs) rely on a hierarchy of trusted Certification Authorities (CAs) for issuing, distributing and managing the status of digital certificates, i.e., unforgeable data structures that attest to the authenticity of an entity's public key. Unfortunately, CPKIs have many downsides in terms of security and fault tolerance and there have been numerous security incidents throughout the years. Decentralized PKIs (DPKIs) were proposed to deal with these issues as they rely on multiple, independent nodes. Nevertheless, decentralization raises other concerns such as what are the incentives for the participating nodes to ensure the service's availability. In our work, we leverage the scalability, as well as, the built-in incentive mechanism of blockchain systems and propose a smart contract-based DPKI. The main barrier in realizing a smart contract-based DPKI is the size of the contract's state which, being its most expensive resource to access, should be minimized for a construction to be viable. We resolve this problem by proposing and using in our DPKI a public-state cryptographic accumulator with constant size, a cryptographic tool which may be of independent interest in the context of blockchain protocols. We also are the first to formalize the DPKI design problem in the Universal Composability (UC) framework and formally prove the security of our construction under the strong RSA assumption in the Random Oracle model and the existence of an ideal smart contract functionality.

In the context of fault attacks on nonce-based authenticated encryption, an attacker faces two restrictions. The first is the uniqueness of the nonce for each new encryption that prevents the attacker from collecting pairs of correct and faulty outputs to perform, e.g., differential fault attacks. The second restriction concerns the verification/decryption, which releases only verified plaintext. While many recent works either exploit misuse scenarios (e.g. nonce-reuse, release of unverified plaintext), we turn the fact that the decryption/verification gives us information on the effect of a fault (whether a fault changed a value or not) against it. In particular, we extend the idea of statistical ineffective fault attacks (SIFA) to target the initialization performed in nonce-based authenticated encryption schemes. By targeting the initialization performed during decryption/verification, most nonce-based authenticated encryption schemes provide the attacker with an oracle whether a fault was ineffective or not. This information is all the attacker needs to mount statistical ineffective fault attacks. To demonstrate the practical threat of the attack, we target software implementations of the authenticated encryption schemes Keyak and Ketje. The presented fault attacks can be carried out without the need of sophisticated equipment. In our practical evaluation the inputs corresponding to 24 ineffective fault inductions were required to reveal large parts of the secret key in both scenarios.

The problem of Oblivious RAM (ORAM) has traditionally been studied in the single-server setting, but more recently the multi-server setting has also been considered. Yet it is still unclear whether the multi-server setting has any inherent advantages, e.g., whether the multi-server setting can be used to achieve stronger security goals or provably better efficiency than is possible in the single-server case. In this work, we construct a perfectly secure 3-server ORAM scheme that outperforms the best known single-server scheme by a logarithmic factor. In the process we also show, for the first time, that there exist specific algorithms for which multiple servers can overcome known lower bounds in the single-server setting.

We apply Scholten's construction to give explicit isogenies between the Weil restriction of supersingular Montgomery curves with full rational 2-torsion over $GF(p^2)$ and corresponding abelian surfaces over $GF(p)$. Subsequently, we show that isogeny-based public key cryptography can exploit the fast Kummer surface arithmetic that arises from the theory of theta functions. In particular, we show that chains of 2-isogenies between elliptic curves can instead be computed as chains of Richelot (2,2)-isogenies between Kummer surfaces. This gives rise to new possibilities for efficient supersingular isogeny-based cryptography.

We construct the first (almost) tightly-secure unbounded-simulation-sound quasi-adaptive non-interactive zero-knowledge arguments (USS-QA-NIZK) for linear-subspace languages with compact (number of group elements independent of the security parameter) common reference string (CRS) and compact proofs under standard assumptions in bilinear-pairings groups. Specifically, our construction has $ O(\log Q) $ reduction to the SXDH, DLIN and matrix-DDH assumptions, where $ Q $ is the number of simulated proofs given out. The USS-QA-NIZK primitive has many applications, including structure-preserving signatures (SPS), CCA2-secure publicly-verifiable public-key encryption (PKE), which in turn have applications to CCA-anonymous group signatures, blind signatures and unbounded simulation-sound Groth-Sahai NIZK proofs. We show that the almost tight security of our USS-QA-NIZK translates into constructions of all of the above applications with (almost) tight-security to standard assumptions such as SXDH and, more generally, $\D_k$-MDDH. Thus, we get the first publicly-verifiable (almost) tightly-secure multi-user/multi-challenge CCA2-secure PKE with practical efficiency under standard bilinear assumptions. Our (almost) tight SPS construction is also improved in the signature size over previously known constructions.

Email communication is amongst the most prominent online activities, and as such, can put sensitive information at risk. It is thus of high importance that internet email applications are designed in a privacy-aware manner and analyzed under a rigorous threat model. The Snowden revelations (2013) suggest that such a model should feature a global adversary, in light of the observational tools available. Furthermore, the fact that protecting metadata can be of equal importance as protecting the communication context implies that end-to-end encryption may be necessary, but it is not sufficient. With this in mind, we utilize the Universal Composability framework [Canetti, 2001] to introduce an expressive cryptographic model for email ``ecosystems'' that can formally and precisely capture various well-known privacy notions (unobservability, anonymity, unlinkability, etc.), by parameterizing the amount of leakage an ideal-world adversary (simulator) obtains from the email functionality. Equipped with our framework, we present and analyze the security of two email constructions that follow different directions in terms of the efficiency vs. privacy tradeoff. The first one achieves optimal security (only the online/offline mode of the users is leaked), but it is mainly of theoretical interest; the second one is based on parallel mixing [Golle and Juels, 2004] and is more practical, while it achieves anonymity with respect to users that have similar amount of sending and receiving activity.

We provide generic and black box transformations from any chosen plaintext secure Attribute-Based Encryption (ABE) or One-sided Predicate Encryption system into a chosen ciphertext secure system. Our transformation requires only the IND-CPA security of the original ABE scheme coupled with a pseudorandom generator (PRG) with a special security property. In particular, we consider a PRG with an $n$ bit input $s \in {0,1}^n$ and $n\cdot \ell$ bit output $y_1, ..., y_n$ where each $y_i$ is an $\ell$ bit string. Then for a randomly chosen $s$ the following two distributions should be computationally indistinguishable. In the first distribution $r_{i,s_i} = y_i$ and $r_{i, \bar{s}_i}$ is chosen randomly for $i \in [n]$. In the second distribution all $r_{i,b}$ are chosen randomly for $i \in [n], b \in {0,1}$.

Leakage-resilient encryption is a powerful tool to protect data confidentiality against side channel attacks. In this work, we introduce a new and strong leakage setting to counter backdoor (or Trojan horse) plus covert channel attack, by relaxing the restrictions on leakage. We allow \emph{bounded} leakage at \emph{anytime} and \emph{anywhere} and over \emph{anything}. Our leakage threshold (e.g. 10000 bits) could be much larger than typical secret key (e.g. AES key or RSA private key) size. Under such a strong leakage setting, we propose an efficient encryption scheme which is semantic secure in standard setting (i.e. without leakage) and can tolerate strong continuous leakage. We manage to construct such a secure scheme under strong leakage setting, by hiding partial (e.g. $1\%$) ciphertext as secure as we hide the secret key using a small amount of more secure hardware resource, so that it is almost equally difficult for any adversary to steal information regarding this well-protected partial ciphertext or the secret key. We remark that, the size of such well-protected small portion of ciphertext is chosen to be much larger than the leakage threshold. We provide concrete and practical examples of such more secure hardware resource for data communication and data storage. Furthermore, we also introduce a new notion of computational entropy, as a sort of computational version of Kolmogorov complexity. Our quantitative analysis shows that, hiding partial ciphertext is a powerful countermeasure, which enables us to achieve higher security level than existing approaches in case of backdoor plus covert channel attacks. We also show the relationship between our new notion of computational entropy and existing relevant concepts, including Shannon-Entropy, Yao-Entropy, Hill-Entropy, All-or-Nothing Transform, and Exposure Resilient Function. This new computation entropy formulation may have independent interests.

We propose a framework for achieving a public-key encryption (PKE) scheme that satisfies key dependent message security against chosen ciphertext attacks (KDM-CCA security) based on projective hash function. Our framework can be instantiated under the decisional diffie-hellman (DDH), quadratic residuosity (QR), and decisional composite residuosity (DCR) assumptions. The constructed schemes are KDM-CCA secure with respect to affine functions and compatible with the amplification method shown by Applebaum (EUROCRYPT 2011). Thus, they lead to PKE schemes satisfying KDM-CCA security for all functions computable by a-priori bounded size circuits. They are the first PKE schemes satisfying such a security notion in the standard model using neither non-interactive zero knowledge proof nor bilinear pairing. The above framework based on projective hash function captures only KDM-CCA security in the single user setting. However, we can prove the KDM-CCA security in the multi user setting of our concrete instantiations by using their algebraic structures explicitly. Especially, we prove that our DDH based scheme satisfies KDM-CCA security in the multi user setting with the same parameter setting as in the single user setting.

Ever since the foundational work of Goldwasser and Micali, simulation has proven to be a powerful and versatile construct for formulating security in various areas of cryptography. However security definitions based on simulation are generally harder to work with than game based definitions, often resulting in more complicated proofs. In this work we challenge this viewpoint by proposing new simulation-based security definitions for secure channels that in many cases lead to simpler proofs of security. We are particularly interested in definitions of secure channels which reflect real-world requirements, such as, protecting against the replay and reordering of ciphertexts, accounting for leakage from the decryption of invalid ciphertexts, and retaining security in the presence of ciphertext fragmentation. Furthermore we show that our proposed notion of channel simulatability implies a secure channel functionality that is universally composable. To the best of our knowledge, we are the first to study universally composable secure channels supporting these extended security goals. We conclude, by showing that the Dropbear implementation of SSH-CTR is channel simulatable in the presence of ciphertext fragmentation, and therefore also realises a universally composable secure channel. This is intended, in part, to highlight the merits of our approach over prior ones in admitting simpler security proofs in comparable settings.

In this work we develop a new theory for concretely efficient, large-scale MPC with active security. Current practical techniques are mostly in the strong setting of all-but-one corruptions, which leads to protocols that scale badly with the number of parties. To work around this issue, we consider a large-scale scenario where a small minority out of many parties is honest and design scalable, more efficient MPC protocols for this setting. Our results are achieved by introducing new techniques for information-theoretic MACs with short keys and extending the work of Hazay et al. (CRYPTO 2018), which developed new passively secure MPC protocols in the same context. We further demonstrate the usefulness of this theory in practice by analyzing the concrete communication overhead of our protocols, which improve upon the most efficient previous works.

Attribute-based signature (ABS) schemes are advanced signature schemes that simultaneously provide fine-grained authentication while protecting privacy of the signer. Previously known expressive ABS schemes support either the class of deterministic finite automata and circuits from standard assumptions or Turing machines from the existence of indistinguishability obfuscations. In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turin machines, from a standard assumption, namely, the Symmetric External Diffie-Hellman (SXDH) assumption. We also propose the first ABS scheme that allows nondeterministic finite automata (NFA) to be used as policies. Although the expressiveness of NFAs are more restricted than Turing machines, this is the first scheme that supports nondeterministic computations as policies. Our main idea lies in abstracting ABS constructions and presenting the concept of history of computations; this allows a signer to prove possession of a policy that accepts the string associated to a message in zero-knowledge while also hiding the policy, regardless of the computational model being used. With this abstraction in hand, we are able to construct ABS for Turing machines and NFAs using a surprisingly weak NIZK proof system. Essentially we only require a NIZK proof system for proving that a (normal) signature is valid. Such a NIZK proof system together with a base signature scheme are, in turn, possible from bilinear groups under the SXDH assumption, and hence so are our ABS schemes.

We present hash functions that are almost optimally one-way in the quantum setting. Our hash functions are based on the Merkle-Damgård construction iterating a Davies-Meyer compression function, which is built from a block cipher. The quantum setting that we use is a natural extention of the classical ideal cipher model. Recent work has revealed that symmetric-key schemes using a block cipher or a public permutation, such as CBC-MAC or the Even-Mansour cipher, can get completely broken with quantum superposition attacks, in polynomial time of the block size. Since many of the popular schemes are built from a block cipher or a permutation, the recent findings motivate us to study such schemes that are provably secure in the quantum setting. Unfortunately, no such schemes are known, unless one relies on certain algebraic assumptions. In this paper we present hash constructions that are provably one-way in the quantum setting without algebraic assumptions, solely based on the assumption that the underlying block cipher is ideal. To do this, we reduce one-wayness to a problem of finding a fixed point and then bound its success probability with a distinguishing advantage. We develop a generic tool that helps us prove indistinguishability of two quantum oracle distributions.

We put forward the notion of universal proxy re-encryption (UPRE). A UPRE scheme enables a proxy to convert a ciphertext under a (delegator) public key of any existing public-key encryption (PKE) scheme into another ciphertext under a (delegatee) public key of any existing PKE scheme (possibly different from the delegator one). The proxy has a re-encryption key generated from the delegator's secret key and the delegatee public key. Thus UPRE generalizes proxy re-encryption by supporting arbitrary PKE schemes and allowing to convert ciphertexts into ones of possibly different PKE schemes. In this work, we - provide syntax and definitions for both UPRE and a variant we call relaxed UPRE. The relaxed variant means that decryption algorithms for re-encrypted ciphertexts are slightly modified but still only use the original delegatee secret keys for decryption. - construct a UPRE based on probabilistic indistinguishability obfuscation (PIO). It allows us to re-encrypt ciphertexts polynomially many times. - construct relaxed UPRE from garbled circuits (GCs). We provide two variants of this construction, one which allows us to re-encrypt ciphertexts polynomially many times, and a second one which satisfies a stronger security requirement but only allows us to re-encrypt ciphertexts a constant number of times.

A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus one, by observing that its SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this paper we extend this work and significantly simplify their treatment. We show that their Kummer line is the x-line of a Montgomery curve translated by a point of order two, and exhibit a natural isomorphism to a twisted Edwards curve. Moreover, we show that the Kummer line presented by Gaudry and Lubicz can be obtained via the action of a point of order two on the y-line of an Edwards curve. The maps connecting these curves and lines are all very simple. As an example, we present the first implementation of the qDSA signature scheme based on the squared Kummer line. Finally we present close estimates on the number of isomorphism classes of Kummer lines.

This paper studies indistinguishability against quantum chosen-ciphertext attacks (IND-qCCA security) of key-encapsulation mechanisms (KEMs) in quantum random oracle model (QROM). We show that the SXY conversion proposed by Saito, Yamakawa, and Xagawa (EUROCRYPT 2018) and the HU conversion proposed by Jiang, Zhang, and Ma (PKC 2019) turn a weakly-secure deterministic public-key encryption scheme into an IND-qCCA-secure KEM scheme in the QROM. The proofs are very similar to those for the IND-CCA security in the QROM, easy to understand, and as tight as the original proofs.

Since $(t,n)$-threshold secret sharing (SS) was initially proposed by Shamir and Blakley separately in 1979, it has been widely used in many aspects. Later on, Asmuth and Bloom presented a $(t,n)$-threshold SS scheme based on the Chinese Remainder Theorem(CRT) for integers in 1983. However, compared with the most popular Shamir's $(t,n)$-threshold SS scheme, existing CRT based schemes have a lower information rate, moreover, they are harder to construct. To overcome these shortcomings of the CRT based scheme, 1) we first propose a generalized $(t,n)$-threshold SS scheme based on the CRT for the polynomial ring over a finite field. We show that our scheme is ideal, i.e., it is perfect in security and has the information rate 1. By comparison, we show that our scheme has a better information rate and is easier to construct compared with existing threshold SS schemes based on the CRT for integers. 2) We show that Shamir's scheme, which is based on the Lagrange interpolation polynomial, is a special case of our scheme. Therefore, we establish the connection among threshold schemes based on the Lagrange interpolation, schemes based on the CRT for integers and our scheme. 3) As a natural extension of our threshold scheme, we present a weighted threshold SS scheme based on the CRT for polynomial rings, which inherits the above advantages of our threshold scheme over existing weighted schemes based on the CRT for integers.

The increasing number of cryptocurrencies, as well as the rising number of actors within each single cryptocurrency, inevitably leads to tensions between the respective communities. As with open source projects, (protocol) forks are often the result of broad disagreement. Usually, after a permanent fork both communities ``mine'' their own business and the conflict is resolved. But what if this is not the case? In this paper, we outline the possibility of malicious forking and consensus techniques that aim at destroying the other branch of a protocol fork. Thereby, we illustrate how merged mining can be used as an attack method against a permissionless PoW cryptocurrency, which itself involuntarily serves as the parent chain for an attacking merge mined branch of a hard fork.

We present $\mathsf{CLARC}$ (Cryptographic Library for Anonymous Reputation and Credentials), an anonymous credentials system (ACS) combined with an anonymous reputation system. Using $\mathsf{CLARC}$, users can receive attribute-based credentials from issuers. They can efficiently prove that their credentials satisfy complex (access) policies in a privacy-preserving way. This implements anonymous access control with complex policies. Furthermore, $\mathsf{CLARC}$ is the first ACS that is combined with an anonymous reputation system where users can anonymously rate services. A user who gets access to a service via a credential, also anonymously receives a review token to rate the service. If a user creates more than a single rating, this can be detected by anyone, preventing users from spamming ratings to sway public opinion. To evaluate feasibility of our construction, we present an open-source prototype implementation.

We propose the first identity-based encryption (IBE) scheme that is (almost) tightly secure against chosen-ciphertext attacks. Our scheme is efficient, in the sense that its ciphertext overhead is only seven group elements, three group elements more than that of the state-of-the-art passively (almost) tightly secure IBE scheme. Our scheme is secure in a multi-challenge setting, i.e., in face of an arbitrary number of challenge ciphertexts. The security of our scheme is based upon the standard symmetric external Diffie-Hellman assumption in pairing-friendly groups, but we also consider (less efficient) generalizations under weaker assumptions.

In this work, we propose two IPE schemes achieving both adaptive security and full attribute-hiding in the prime-order bilinear group, which improve upon the unique existing result satisfying both features from Okamoto and Takashima [Eurocrypt '12] in terms of efficiency. - Our first IPE scheme is based on the standard $k$-Lin assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima's IPE under weaker DLIN=$2$-lin assumption. - Our second IPE scheme is adapted from the first one; the security is based on the XDLIN assumption (as Okamoto and Takashima's IPE) but now it also enjoys shorter ciphertexts. Technically, instead of starting from composite-order IPE and applying existing transformation, we start from an IPE scheme in a very restricted setting but already in the prime-order group, and then gradually upgrade it to our full-fledged IPE scheme. This method allows us to integrate Chen et al.'s framework [Eurocrypt '15] with recent new techniques [TCC '17, Eurocrypt '18] in an optimized way.

This work focuses on side-channel resilient design strategies for symmetric-key cryptographic primitives targeting lightweight applications. In light of NIST's lightweight cryptography project, design choices for block ciphers must consider not only security against traditional cryptanalysis, but also side-channel security, while adhering to low area and power requirements. In this paper, we explore design strategies for substitution-permutation network (SPN)-based block ciphers that make them amenable to low-cost threshold implementations (TI) - a provably secure strategy against side-channel attacks. The core building blocks for our strategy are cryptographically optimal 4x4 S-Boxes, implemented via repeated iterations of simple cellular automata~(CA) rules. We present highly optimized TI circuits for such S-Boxes, that consume nearly 40% less area and power as compared to popular lightweight S-Boxes such as PRESENT and GIFT. We validate our claims via implementation results on ASIC using 180nm technology. We also present a comparison of TI circuits for two popular lightweight linear diffusion layer choices - bit permutations and MixColumns using almost-maximum-distance-separable (almost-MDS) matrices. We finally illustrate design paradigms that combine the aforementioned TI circuits for S-Boxes and diffusion layers to obtain fully side-channel secure SPN block cipher implementations with low area and power requirements.

RaCoSS is a signature scheme based on the syndrome decoding problem over the random linear code and proposed by Fukushima, Roy, Xu, Kiyomoto, Morozov, and Takagi. This scheme is cryptanalyzed Bernstein, Hülsing, Lange, and Panny (pqc-forum on 23 Dec. 2017). Roy, Morozov, Fukushima, Kiyomoto, and Takagi recently gave a patch and call the patched scheme as RaCoSS-R (ISEC Conf. on 25 Jul. 2018). This short note describes how to break RaCoSS-R by modifying the forgery attack against RaCoSS.

The success rate is the most common evaluation metric for measuring the performance of a particular side channel attack scenario. We improve on an analytic formula for the success rate.