Code update is a very useful tool commonly used in low-end embedded devices to improve the existing functionalities or patch discovered bugs or vulnerabilities. If the update protocol itself is not secure, it will only bring new threats to embedded systems. Thus, a secure code update mechanism is required. However, existing solutions either rely on strong security assumptions, or result in considerable storage and computation consumption, which are not practical for resource-constrained embedded devices (e.g., in the context of Internet of Things). In this work, we propose to use intrinsic device characteristics (i.e., Physically Unclonable Functions or PUF) to design a practical and lightweight secure code update scheme. Our scheme can not only ensure the freshness, integrity, confidentiality and authenticity of code update, but also verify that the update is installed correctly on a specific device without any malicious software. Cloned or counterfeit devices can be excluded as the code update is bound to the unpredictable physical properties of underlying hardware. Legitimate devices in an untrustworthy software state can be restored by filling suspect memory with PUF-derived random numbers. After update installation, the initiator of the code update is able to obtain the verifiable software state from device, and the device can maintain a sustainable post-update secure check by enforcing a secure call sequence. To demonstrate the practicality and feasibility, we also implement the proposed scheme on a low-end MCU platform (TI MSP430) by using onboard SRAM and Flash resources.

Nonlinear permutations (S-boxes) are key components in block ciphers. The differential branch number measures the diffusion power of a permutation, whereas the linear branch number measures resistance against linear cryptanalysis. There has not been much analysis done on the differential branch number of nonlinear permutations of $\mathbb{F}_2^n$, although it has been well studied in case of linear permutations. Similarly upper bounds for the linear branch number have also not been studied in general. In this paper we obtain bounds for both the differential and the linear branch number of permutations (both linear and nonlinear) of $\mathbb{F}_2^n$. We also prove that in the case of $\mathbb{F}_2^4$, the maximum differential branch number can be achieved only by affine permutations.

We consider a situation where multiple parties, owning data that have to be frequently updated, agree to share weighted sums of these data with some aggregator, but where they do not wish to reveal their individual data, and do not trust each other. We combine techniques from Private Stream Aggregation (PSA) and Functional Encryption (FE), to introduce a primitive we call Decentralized Multi-Client Functional Encryption (DMCFE), for which we give a practical instantiation for Inner Product functionalities. This primitive allows various senders to non-interactively generate ciphertexts which support inner-product evaluation, with functional decryption keys that can also be generated non-interactively, in a distributed way, among the senders. Interactions are required during the setup phase only. We prove adaptive security of our constructions, while allowing corruptions of the clients, in the random oracle model.

Lattice-based cryptography has been accepted as a promising candidate for public key cryptography in the age of quantum computing. Discrete Gaussian sampling is one of fundamental operations in many lattice-based cryptosystems. In this paper, we discuss a sub-problem of discrete Gaussian sampling, which is to sample from a centered discrete Gaussian distribution over the integers with positive standard deviation and zero center. We propose three alternative rejection sampling algorithms for centered discrete Gaussian distributions with standard deviation in two specific forms. The first algorithm is designed for the case where the standard deviation is an positive integer, and it requires neither pre-computation storage nor floating-point arithmetic. While the other two algorithms are fit for a standard deviation that is an integer multiple of a fixed real number (approximately equal to 0.849). These two algorithms require fixed look-up tables of very small size (e.g. 128 bits and 320 bits respectively), but they are much more efficient than the first algorithm. The experimental results show that our algorithms have better performance than that of two rejection sampling algorithms proposed by Karney in 2016 and by Ducas et al.\ in 2013 respectively. The expected numbers of random bits used in our algorithms are significantly smaller than that of random bits used in Karney's rejection sampling algorithm.

We construct two identity-based encryption (IBE) schemes. The first one is IBE satisfying key dependent message (KDM) security for user secret keys. The second one is IBE satisfying simulation-based receiver selective opening (RSO) security. Both schemes are secure against adaptive-ID attacks and do not have any a-priori bound on the number of challenge identities queried by adversaries in the security games. They are the first constructions of IBE satisfying such levels of security. Our constructions of IBE are very simple. We construct our KDM secure IBE by transforming KDM secure secret-key encryption using IBE satisfying only ordinary indistinguishability against adaptive-ID attacks (IND-ID-CPA security). Our simulation-based RSO secure IBE is based only on IND-ID-CPA secure IBE. We also demonstrate that our construction technique for KDM secure IBE is used to construct KDM secure public-key encryption. More precisely, we show how to construct KDM secure public-key encryption from KDM secure secret-key encryption and public-key encryption satisfying only ordinary indistinguishability against chosen plaintext attacks.

Cryptosystems based on supersingular isogenies have been proposed recently for use in post-quantum cryptography. Three problems have emerged related to their hardness: computing an isogeny between two curves, computing the endomorphism ring of a curve, and computing a maximal order associated to it. While some of these problems are believed to be polynomial-time equivalent based on heuristics, their relationship is still unknown. We give the first reduction between these problems, with the aid of one more problem which we call Action-on-$\ell$-Torsion. We show that computing $\ell$-power isogenies reduces to computing maximal orders and Action-on-$\ell$-Torsion. We also define the notion of a compact representation of an endomorphism, and use this to show that endomorphism rings always have polynomial representation size. We then reduce the endomorphism ring problem to computing maximal orders and Action-on-$\ell$-Torsion, thus laying the foundation for analysis of the hardness of endomorphism ring computation. This identifies these last two problems as one possible way to attack some systems, such as hash functions based on the $\ell$-isogeny graph of supersingular elliptic curves. This gives the potential to use algebraic tools in quaternion algebras to solve the problems. We also discuss how these reductions apply to attacks on a hash function of Charles, Goren, and Lauter.

Ed25519 is an instance of the Elliptic Curve based signature scheme EdDSA that was recently introduced to solve an inconvenience of the more established ECDSA. Namely, both schemes require the generation of a random value (scalar of the ephemeral key pair) during the signature generation process and the secrecy of this random value is critical for security: knowledge of one such a random value, or partial knowledge of a series of them, allows reconstructing the signer's private key. In ECDSA it is not specified how to generate this random value and hence implementations critically rely on the quality of random number generators and are challenging to implement securely. EdDSA removes this dependence by deriving the secret deterministically from the message and a long-term auxiliary key using a cryptographic hash function. The feature of determinism has received wide support as enabling secure implementations and in particular deployment of Ed25519 is spectacular. Today Ed25519 is used in numerous security protocols, networks and both software and hardware security products e.g. OpenSSH, Tor, GnuPG etc. In this paper we show that in use cases where power or electromagnetic leakage can be exploited, exactly the mechanism that makes EdDSA deterministic complicates its secure implementation. In particular, we break an Ed25519 implementation in WolfSSL, which is a suitable use case for IoT applications. We apply differential power analysis (DPA) on the underlying hash function, SHA-512, requiring only 4000 traces. Finally, we present a tweak to the EdDSA protocol that is cheap and effective against the described attack while keeping the claimed advantage of EdDSA over ECDSA in terms of featuring less things that can go wrong e.g. the required high-quality randomness. However, we do argue with our countermeasure that some randomness (that need not be perfect) might be hard to avoid.

We put forward the notion of self-guarding cryptographic protocols as a countermeasure to algorithm substitution attacks. Such self-guarding protocols can prevent undesirable leakage by subverted algorithms if one has the guarantee that the system has been properly working in an initialization phase. Unlike detection-based solutions they thus proactively thwart attacks, and unlike reverse firewalls they do not assume an online external party. We present constructions of basic primitives for (public-key and private-key) encryption and for signatures. We also argue that the model captures attacks with malicious hardware tokens and show how to self-guard a PUF-based key exchange protocol.

Attribute-based encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. In this paper, we propose, implement, and evaluate fully automated methods for proving security of ABE in the Generic Bilinear Group Model (Boneh, Boyen, and Goh, 2005, Boyen, 2008), an idealized model which admits simpler and more efficient constructions, and can also be used to find attacks. Our method is applicable to Rational-Fraction Induced ABE, a large class of ABE that contains most of the schemes from the literature, and relies on a Master Theorem, which reduces security in the GGM to a (new) notion of symbolic security, which is amenable to automated verification using constraint- based techniques. We relate our notion of symbolic security for Rational-Fraction Induced ABE to prior notions for Pair Encodings. Finally, we present several applications, including automated proofs for new schemes.

Secure messaging apps have enjoyed huge uptake, and with the headline figure of one billion active WhatsApp users there has been a corresponding burst of academic research on the topic. One might therefore wonder: how far is the academic community from providing concrete, applicable guarantees about the apps that are currently in widespread use? We argue that there are still significant gaps between the security properties that users might expect from a communication app, and the security properties that have been formally proven. These gaps arise from dubious technical assumptions, tradeoffs in the name of reliability, or simply features out of scope of the analyses. We survey these gaps, and discuss where the academic community can contribute. In particular, we encourage more transparency about analyses' restrictions: the easier they are to understand, the easier they are to solve.

A crucial issue, that mostly affects the performance of actively secure computation of RAM programs, is the task of reading/writing from/to memory in a private and authenticated manner. Previous works in the active security and multiparty settings are based purely on the SPDZ (reactive) protocol, hence, memory accesses are treated just like any input to the computation. However, a garbled-circuit-based construction (such as BMR), which benefits from a lower round complexity, must resolve the issue of converting memory data bits to their corresponding wire keys and vice versa. In this work we propose three techniques to construct a secure memory access, each appropriates to a different level of abstraction of the underlying garbling functionality. We provide a comparison between the techniques by several metrics. To the best of our knowledge, we are the first to construct, prove and implement a concretely efficient garbled-circuit-based actively secure RAM computation with dishonest majority. Our construction is based on our third (most efficient) technique, cleverly utilizing the underlying SPDZ authenticated shares (Damgård et al., Crypto 2012), yields lean circuits and a constant number of communication rounds per physical memory access. Specifically, it requires no additional circuitry on top of the ORAM's, incurs only two rounds of broadcasts between every two memory accesses and has a multiplicative overhead of 2 on top of the ORAM's storage size. Our protocol outperforms the state of the art in this settings when deployed over WAN. Even when simulating a very conservative RTT of 100ms our protocol is at least one order of magnitude faster than the current state of the art protocol of Keller and Scholl (Asiacrypt 2015).

In this paper we present new fundamental properties of SPNs. These properties turn out to be particularly useful in the adaptive chosen ciphertext/plaintext setting and we show this by introducing for the first time key-independent yoyo-distinguishers for 3- to 5-rounds of AES. All of our distinguishers beat previous records and require respectively $3, 4$ and $2^{25.8}$ data and essentially zero computation except for observing differences. In addition, we present the first key-independent distinguisher for 6-rounds AES based on yoyos that preserve impossible zero differences in plaintexts and ciphertexts. This distinguisher requires an impractical amount of $2^{122.83}$ plaintext/ciphertext pairs and essentially no computation apart from observing the corresponding differences. We then present a very favorable key-recovery attack on 5-rounds of AES that requires only $2^{11.3}$ data complexity and $2^{31}$ computational complexity, which as far as we know is also a new record. All our attacks are in the adaptively chosen plaintext/ciphertext scenario. Our distinguishers for AES stem from new and fundamental properties of generic SPNs, including generic SAS and SASAS, that can be used to preserve zero differences under the action of exchanging values between existing ciphertext and plaintext pairs. We provide a simple distinguisher for 2 generic SP-rounds that requires only 4 adaptively chosen ciphertexts and no computation on the adversaries side. We then describe a generic and deterministic yoyo-game for 3 generic SP-rounds which preserves zero differences in the middle but which we are not capable of exploiting in the generic setting.

Linear regression with 2-norm regularization (i.e., ridge regression) is an important statistical technique that models the relationship between some explanatory values and an outcome value using a linear function. In many applications (e.g., predictive modelling in personalised health care), these values represent sensitive data owned by several different parties who are unwilling to share them. In this setting, training a linear regression model becomes challenging and needs specific cryptographic solutions. This problem was elegantly addressed by Nikolaenko et al. in S&P (Oakland) 2013. They suggested a two-server system that uses linearly-homomorphic encryption (LHE) and Yao’s two-party protocol (garbled circuits). In this work, we propose a novel system that can train a ridge linear regression model using only LHE (i.e., without using Yao’s protocol). This greatly improves the overall performance (both in computation and communication) as Yao’s protocol was the main bottleneck in the previous solution. The efficiency of the proposed system is validated both on synthetically-generated and real-world datasets.

Recently, Döttling and Garg (CRYPTO 2017) showed how to build identity-based encryption (IBE) from a novel primitive termed Chameleon Encryption, which can, in turn, be realized from simple number theoretic hardness assumptions such as the computational Diffie-Hellman assumption (in groups without pairings) or the factoring assumption. In a follow-up work (TCC 2017), the same authors showed that IBE can also be constructed from a slightly weaker primitive called One-Time Signatures with Encryption (OTSE). In this work, we show that OTSE can be instantiated from hard learning problems such as the Learning With Errors (LWE) and the Learning Parity with Noise (LPN) problems. This immediately yields the first IBE construction from the LPN problem and a construction based on a weaker LWE assumption compared to previous works. Finally, we show that the notion of one-time signatures with encryption is also useful for the construction of key-dependent-message (KDM) secure public-key encryption. In particular, our results imply that a KDM-secure public key encryption can be constructed from any KDM-secure secret-key encryption scheme and any public-key encryption scheme.

In this paper, quantum attacks against symmetric-key schemes are presented in which adversaries only make classical queries but use quantum computers for offline computations. Our attacks are not as efficient as polynomial-time attacks making quantum superposition queries, while our attacks use the realistic model and overwhelmingly improve the classical attacks. Our attacks convert a type of classical meet-in-the-middle attacks into quantum ones. The attack cost depends on the number of available qubits and the way to realize the quantum hardware. The tradeoff between data complexity $D$ and time complexity $T$ against the problem of cardinality $N$ is $D^2 \cdot T^2 =N$ and $D \cdot T^6 = N^3$ in the best and worst case scenarios to the adversary respectively, while the classic attack requires $D\cdot T = N$. This improvement is meaningful from an engineering aspect because several existing schemes claim beyond-birthday-bound security for $T$ by limiting the maximum $D$ to be below $2^{n/2}$ according to the classical tradeoff $D\cdot T = N$. Those schemes are broken if quantum offline computations are performed by adversaries. The attack can be applied to many schemes such as a tweakable block-cipher construction TDR, a dedicated MAC scheme Chaskey, an on-line authenticated encryption scheme McOE-X, a hash function based MAC H$^2$-MAC and a permutation based MAC keyed-sponge. The idea is then applied to the FX-construction to discover new tradeoffs in the classical query model.

Garbled circuits have been highly optimized for practice over the last several years. Today's most efficient constructions treat different types of gates (e.g., AND vs XOR) differently; as such, they leak the type of each gate. In many applications of garbled circuits, the circuit itself is public, so such leakage is tolerable. In other settings, however, it is desirable to hide the type of each gate. In this paper we consider optimizing garbled circuits for the gate-hiding case. We observe that the best state-of-the-art constructions support only a limited class of gate functions, which turns out to undermine their improvements in several settings. These state-of-the-art constructions also require a non-minimal hardness assumption. We introduce two new gate-hiding constructions of garbled circuits. Both constructions achieve the same communication complexity as the best state-of-the-art schemes, but support a more useful class of boolean gates and use only the minimal assumption of a secure PRF.

Deterministic signature schemes are becoming more popular, as illustrated by the deterministic variant of ECDSA and the popular EdDSA scheme, since eliminating the need for high-quality randomness might have some advantages in certain use-cases. In this paper we outline a range of differential fault attacks and a differential power analysis attack against such deterministic schemes. This shows, contrary to some earlier works, that such signature schemes are not naturally protected against such advanced attacks. We discuss different countermeasures and propose to include entropy for low-cost protection against these attacks in scenarios where these attack vectors are a real threat: this does not require to change the key generation or the verification methods and results in a signature scheme which offers high performance and security for a wide range of use-cases.

Bitcoin provides only pseudo-anonymous transactions, which can be exploited to link payers and payees – defeating the goal of anonymous payments. To thwart such attacks, several Bitcoin mixers have been proposed, with the objective of providing unlinkability between payers and payees. However, existing Bitcoin mixers can be regarded as either insecure or inefficient. We present Obscuro, a highly efficient and secure Bitcoin mixer that utilizes trusted execution environments (TEEs). With the TEE’s confidentiality and integrity guarantees for code and data, our mixer design ensures the correct mixing operations and the protection of sensitive data (i.e., private keys and mixing logs), ruling out coin theft and address linking attacks by a malicious service provider. Yet, the TEE-based implementation does not prevent the manipulation of inputs (e.g., deposit submissions, blockchain feeds) to the mixer, hence Obscuro is designed to overcome such limitations: it (1) offers an indirect deposit mechanism to prevent a malicious service provider from rejecting benign user deposits; and (2) scrutinizes blockchain feeds to prevent deposits from being mixed more than once (thus degrading anonymity) while being eclipsed from the main blockchain branch. In addition, Obscuro provides several unique anonymity features (e.g., minimum mixing set size guarantee, resistant to dropping user deposits) that are not available in existing centralized and decentralized mixers. Our prototype of Obscuro is built using Intel SGX and we demonstrate its effectiveness in Bitcoin Testnet. Our implementation mixes 1000 inputs in just 6.49 seconds, which vastly outperforms all of the existing decentralized mixers.

We consider Symmetric Searchable Encryption with Sharing and Unsharing (SSEwSU), a notion that models Symmetric Searchable Encryption (SSE) in a multi-user setting in which documents can be dynamically shared and unshared among users. Previous works on SSE involving multiple users have assumed that all users have access to the same set of documents and/or their security models assume that all users in the system are trusted. As in SSE, every construction of a SSEwSU will be a trade-off between efficiency and security, as measured by the amount of leakage. In multi-user settings, we must also consider cross-user leakage (x-user leakage) where a query performed by one user would leak information about the content of documents shared with a different user. We start by presenting two strawman solutions that are at the opposite side of the efficiency-leakage bidimensional space: x-uz, that has zero x-user leakage but is very inefficient, and x-uL, that is very efficient but highly insecure with very large x-user leakage. We give a third construction, x-um, that is as efficient as x-uL and more efficient than x-uz. At the same time, x-um is considerably more secure than x-uL. Construction x-um is based on the concept of a Re-writable Deterministic Hashing (RDH), which can be thought of as a two-argument hash function with tokens that add re-writing capabilities. Sharing and unsharing in x-um is supported in constant (in the number of users, documents, and keywords) time. We give a concrete instantiation whose security is based on the Decisional Diffie-Hellman assumption. We provide a rigorous analysis of x-um and show a tight bound on the leakage in the presence of an active adversary that corrupts a subset of the users. We report on experimental work that show that x-um is very efficient and x-user leakage grows very slowly as queries are performed by the users. Additionally, we present extensions of x-um. We modify x-um to support a finer grained access granularity, so a document can be shared to a user either only for reading (i.e., searching) or for writing (i.e., editing). We also extend x-um to the bilinear setting to further reduce leakage.

We present new constructions of multi-input functional encryption (MIFE) schemes for the inner-product functionality that improve the state of the art solution of Abdalla et al. (Eurocrypt 2017) in two main directions. First, we put forward a novel methodology to convert single-input functional encryption for inner products into multi-input schemes for the same functionality. Our transformation is surprisingly simple, general, and efficient. In particular, it does not require pairings and it can be instantiated with all known single-input schemes. This leads to two main advances. First, we enlarge the set of assumptions this primitive can be based on, notably obtaining new MIFEs for inner products from plain DDH, LWE and Composite Residuosity. Second, we obtain the first MIFE schemes from standard assumptions where decryption works efficiently even for messages of super-polynomial size. Our second main contribution is the first function-hiding MIFE scheme for inner products based on standard assumptions. To this end, we show how to extend the original, pairing-based, MIFE by Abdalla et al. in order to make it function hiding, thus obtaining a function-hiding MIFE from the MDDH assumption.

We present a simple and fast protocol to securely solve the (single source) Shortest Path Problem, based on Dijkstra's algorithm over Secure Multiparty Computation. Our protocol improves current state of the art by Aly et al. [FC 2013 & ICISC 2014] and can offer perfect security against both semi-honest and malicious adversaries. Furthermore, it is the first data oblivious protocol to achieve quadratic complexity in the number of communication rounds. Moreover, our protocol can be easily be adapted to form a subroutine in other combinatorial mechanisms. Our focus is usability; hence, we provide an open source implementation and exhaustive benchmarking under different adversarial settings and players setups.

Functional encryption, which emerges in the community recently, is a generalized concept of traditional encryption (e.g. RSA and AES). In traditional encryption scheme, decrypting a ciphertext with a correct decryption key will output the original plaintext associated to the ciphertext. In contrast, in functional encryption scheme, decrypting a ciphertext with a correct decryption key will output a value that is derived from both the plaintext and the decryption key, and the decryption output would change when different correct decryption key is used to decrypt the same ciphertext. We propose a new functional encryption scheme for multidimensional range query. Given a ciphertext that is the encryption of some secret plaintext under a public attribute (a multidimensional point), and a decryption key corresponding to a query range and a function key. If the public attribute point is within the query range, a user is able to decrypt the ciphertext with the decryption key to obtain a value, which is the output of a pre-defined \emph{one-way} function with the secret plaintext and the function key as input. In comparison, in previous functional encryption for range query, a decryption will simply output the original secret plaintext when the attribute point is within the query range.

Indistinguishability obfuscation (iO) is a powerful cryptographic tool often employed to construct a variety of core cryptographic primitives such as public key encryption and signatures. In this paper, we focus on the employment of iO in order to construct short signatures with strong security guarantees (i.e., adaptive security) that provide a very efficient signing process for resource constrained devices. Sahai and Waters (SW) (STOC 2014) initially explored the construction of iO-based short signature schemes but their proposal provides selective security. Ramchen and Waters (RW) (CCS 2014) attempted to provide stronger security guarantees (i.e., adaptive security) but their proposal is much more computationally expensive than the SW proposal. In this work, we propose an iO-based short signature scheme that provides adaptive security, fast signing for resource-constrained devices and is much more cost-efficient than the RW signature scheme. More precisely, we employ a puncturable PRF with a fixed length input to get a fast and adaptively secure signature scheme without any additional hardness assumption as in the SW signature scheme. To achieve this goal, we employ the technique of Hofheinz et al. called "delayed backdoor programming" using a random oracle, which allows to embed an execution thread that will only be invoked by special inputs generated using secret key information. Furthermore, we compare the cost of our signature scheme in terms of the cost of the underlying PRG used by the puncturable PRF. Our scheme has a much lower cost than the RW scheme, while providing strong security guarantees (i.e., adaptive security).

In recent years, performance counters have been used as a side channel source for the branch mispredictions which has been used to attack ciphers with user privileges. However, existing research considers blinding techniques, like scalar blinding, scalar splitting as a mechanism of thwarting such attacks. In this endeavour, we reverse engineer the undisclosed model of Intel’s Broadwell and Sandybridge branch predictor and further utilize the largely unexplored perf ioctl calls in sampling mode to granularly monitor the branch prediction events asynchronously when a victim cipher is executing. With these artifacts in place, we target scalar blinding and splitting countermeasures to develop a key retrieval process using what is called as Deduce & Remove. The Deduce step uses template based on the number of branch misses as expected from the 3-bit model of the BPU to infer the matched candidate values. In the Remove step, we correct any erroneous conclusions that are made, by using the properties of the blinding technique under attack. It may be emphasized that as in iterated attacks the cost of a mistaken deduction could be significant, the blinding techniques actually aids in removing wrong guesses and in a way auto-corrects the key retrieval process. Finally, detailed experimental results have been provided to illustrate all the above steps for point blinding, scalar blinding, and scalar splitting to show that the secret scalar can be correctly recovered with high confidence. The paper concludes with recommendation on some suitable countermeasure at the algorithm level to thwart such attacks.

In anonymous identity-based encryption (IBE), ciphertexts not only hide their corresponding messages, but also their target identity. We construct an anonymous IBE scheme based on the Computational Diffie-Hellman (CDH) assumption in general groups (and thus, as a special case, based on the hardness of factoring Blum integers). Our approach extends and refines the recent tree-based approach of Cho et al. (CRYPTO '17) and Döttling and Garg (CRYPTO '17). Whereas the tools underlying their approach do not seem to provide any form of anonymity, we introduce two new building blocks which we utilize for achieving anonymity: blind garbled circuits (which we construct based on any one-way function), and blind batch encryption (which we construct based on CDH). We then further demonstrate the applicability of our newly-developed tools by showing that batch encryption implies a public-key encryption scheme that is both resilient to leakage of a $(1-o(1))$-fraction of its secret key, and KDM secure (or circular secure) with respect to all linear functions of its secret key (which, in turn, is known to imply KDM security for bounded-size circuits). These yield the first high-rate leakage-resilient encryption scheme and the first KDM-secure encryption scheme based on the CDH or Factoring assumptions. Finally, relying on our techniques we also construct a batch encryption scheme based on the hardness of the Learning Parity with Noise (LPN) problem, albeit with very small noise rate $\Omega(\log^2(n)/n)$. Although this batch encryption scheme is not blind, we show that it still implies standard (i.e., non-anonymous) IBE, leakage resilience and KDM security. IBE and high-rate leakage resilience were not previously known from LPN, even with extremely low noise.

We introduce Multi Tree XMSS (XMSS^MT), a hash-based signature scheme that can be used to sign a virtually unlimited number of messages. It is provably forward and hence EU-CMA secure in the standard model and improves key and signature generation times compared to previous schemes. XMSS^MT has --- like all practical hash-based signature schemes --- a lot of parameters that control different trade-offs between security, runtimes and sizes. Using linear optimization, we show how to select provably optimal parameter sets for different use cases.

We present WOTS+, a Winternitz type one-time signature scheme (WOTS). We prove that WOTS+ is strongly unforgeable under chosen message attacks in the standard model. Our proof is exact and tight. The first property allows us to compute the security of the scheme for given parameters. The second property allows for shorter signatures than previous proposals without lowering the security. This improvement in signature size directly carries over to all recent hash-based signature schemes. I.e. we can reduce the signature size by more than 50% for XMSS+ at a security level of 80 bits. As the main drawback of hash-based signature schemes is assumed to be the signature size, this is a further step in making hash-based signatures practical.

We present Recursive Square Root ORAM (R-SQRT), a simple and flexible ORAM that can be instantiated for different client storage requirements. R-SQRT requires significantly less bandwidth than Ring and Partition ORAM, the previous two best practical constructions in their respective classes of ORAM according to client storage requirements. Specifically, R-SQRT is a 4x improvement in amortized bandwidth over Ring ORAM for similar server storage. R-SQRT is also a 1.33-1.5x improvement over Partition ORAM under the same memory restrictions. R-SQRT-AHE, a variant of R-SQRT, is a 1.67- 1.75x improvement over the reported Partition ORAM results in the same settings. All the while, R-SQRT maintains a single data roundtrip per query. We emphasize the simplicity of R-SQRT which uses straightforward security and performance proofs. Additionally, we present Twice-Recursive Square Root ORAM (TR-SQRT) with smaller client stor- age requirements. Due to its flexibility, we construct several instantiations under different memory requirements. TR-SQRT is asymptotically competitive with previous results, yet remarkably simple.

Open consensus protocols based on proof-of-work (PoW) mining are at the core of cryptocurrencies such Bitcoin and Ethereum, as well as many others. In this work, we construct a new primitive called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) that can be adapted into existing PoW-based cryptocurrencies to improve their performance and extend their functionality. Unlike a traditional blockchain client which must verify the entire linearly-growing chain of PoWs, clients based on NIPoPoWs require resources only logarithmic in the length of the blockchain. NIPoPoWs are thus succinct proofs and require only a single message between the prover and the verifier of the transaction. With our construction we are able to prove a broad array of useful predicates in the context of cross PoW-based blockchain transfers of assets, including predicates about facts buried deep within a blockchain which is necessary for the basic application of accepting payments. We provide empirical validation for NIPoPoWs through an implementation and benchmark study, in the context of two new applications: First, we consider a multi-client blockchain that supports all proof-of-work currencies rather than just one, with up to 90% reduction in bandwidth. Second, we discuss a “cross-chain ICO” application that spans multiple independent blockchains. Using our experimental data, we provide concrete parameters for our scheme.

We consider the endomorphism ring computation problem for supersingular elliptic curves, constructive versions of Deuring's correspondence, and the security of Charles-Goren-Lauter's cryptographic hash function. We show that constructing Deuring's correspondence is easy in one direction and equivalent to the endomorphism ring computation problem in the other direction. We also provide a collision attack for special but natural parameters of the hash function, and we prove that for general parameters its preimage and collision resistance are also equivalent to the endomorphism ring computation problem. Our reduction and attack techniques are of independent interest and may find further applications in both cryptanalysis and the design of new protocols.

Password Authenticated Key Exchange (PAKE) allows a user to establish a strong cryptographic key with a server, using only knowledge of a pre-shared password. One of the basic security requirements of PAKE is to prevent offline dictionary attacks. In this paper, we revisit zkPAKE, an augmented PAKE that has been recently proposed by Mochetti, Resende, and Aranha (SBSeg 2015). Our work shows that the zkPAKE protocol is prone to offline password guessing attack, even in the presence of an adversary that has only eavesdropping capabilities. Therefore, zkPAKE is insecure and should not be used as a key exchange mechanism.

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give denitions for (i.) ciphertext unforgeability , (ii.) indistinguishability under adaptive chosen-ciphertext attack, and (iii.) authenticated encryption. The restriction of each denition to the classical setting is at least as strong as the corresponding classical notion: (i) implies INT-CTXT, (ii) implies IND-CCA2, and (iii) implies AE. All of our new notions also imply QIND-CPA privacy. Combining one-time authentication and classical pseudorandomness, we construct schemes for each of these new quantum security notions, and provide several separation examples. Along the way, we also give a new denition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

Albrecht et al. at Crypto 2016 and Cheon et al. at ANTS 2016 independently presented a subfield attack on overstretched NTRU problem. Their idea is to map the public key down to the subfield (by norm and trace map respectively) and hence obtain a lattice of smaller dimension for which a lattice reduction algorithm is efficiently applicable. At Eurocrypt 2017, Kirchner and Fouque proposed another variant attack which exploits the presence of orthogonal bases within the cyclotomic number rings and instead of using the matrix of the public key in the subfield, they use the multiplication matrix by the public key in the full field and apply a lattice reduction algorithm to a suitable projected lattice of smaller dimension. They also showed a tight estimation of the parameters broken by lattice reduction and implementation results that their attack is better than the subfield attack. In this paper, we exploit technical results from Kirchner and Fouque for the relative norm of field elements in the subfield and we use Hermite factor for estimating the output of a lattice basis reduction algorithm in order to analyze general choice of parameters for the subfield attack by Albrecht et al. As a result, we obtain the estimation for better choices of the subfields for which the attack works with smaller modulus. Our experiment results show that we can attack overstretched NTRU with modulus smaller than that of Albrecht et al. and of Kirchner and Fouque.

We study the problem of two round oblivious evaluation of cryptographic functionalities. In this setting, one party P1 holds a private key sk for a provably secure instance of a cryptographic functionality F and the second party P2 wishes to evaluate F_sk on a value x. Although it has been known for 22 years that general functionalities cannot be computed securely in the presence of malicious adversaries with only two rounds of communication, we show the existence of a round-optimal protocol that obliviously evaluates cryptographic functionalities. Our protocol is provably secure against malicious receivers under standard assumptions and does not rely on heuristic (setup) assumptions. Our main technical contribution is a novel nonblack-box technique, which makes nonblack-box use of the security reduction of F_sk. Specifically, our proof of malicious receiver security uses the code of the reduction, which reduces the security of F_sk to some hard problem, in order to break that problem directly. Instantiating our framework, we obtain the first two-round oblivious pseudorandom function that is secure in the standard model. This question was left open since the invention of OPRFs in 1997.

Starting with any selectively secure identity-based encryption (IBE) scheme, we give generic constructions of fully secure IBE and selectively secure hierarchical IBE (HIBE) schemes. Our HIBE scheme allows for delegation arbitrarily many times.

We develop a general approach to adding a threshold functionality to a large class of (non- threshold) cryptographic schemes. A threshold functionality enables a secret key to be split into a number of shares, so that only a threshold of parties can use the key, without reconstructing the key. We begin by constructing a threshold fully-homomorphic encryption scheme (TFHE) from the learning with errors (LWE) problem. We next introduce a new concept, called a universal thresholdizer, from which many threshold systems are possible. We show how to construct a universal thresholdizer from our TFHE. A universal thresholdizer can be used to add threshold functionality to many systems, such as CCA-secure public key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. In particular, by applying this paradigm to a (non-threshold) lattice signature system, we obtain the first single-round threshold signature scheme from LWE.

The deployment of Genome-wide association studies (GWASs) requires genomic information of a large population to produce reliable results. This raises significant privacy concerns, making people hesitate to contribute their genetic information to such studies. We propose two provably secure solutions to address this challenge: (1) a somewhat homomorphic encryption approach, and (2) a secure multiparty computation approach. Unlike previous work, our approach does not rely on adding noise to the input data, nor does it reveal any information about the patients. Our protocols calculate the $\chi^2$ statistic in a privacy-preserving manner, without revealing any information other than the significance of the statistic; hence not even the statistic value itself. We significantly increased the efficiency of our protocols by introducing a new masking technique to perform the secure comparison. Our implementations demonstrated that both approaches are efficient. The secure multiparty computation technique completes its execution in approximately 2~ms for data contributed by one million subjects.

This work investigates the fundamental constraints of anonymous communication (AC) protocols. We analyze the relationship between bandwidth overhead, latency overhead, and sender anonymity or recipient anonymity against a global passive (network-level) adversary. We confirm the trilemma that an AC protocol can only achieve two out of the following three properties: strong anonymity (i.e., anonymity up to a negligible chance), low bandwidth overhead, and low latency overhead. We further study anonymity against a stronger global passive adversary that can additionally passively compromise some of the AC protocol nodes. For a given number of compromised nodes, we derive as a necessary constraint a relationship between bandwidth and latency overhead whose violation make it impossible for an AC protocol to achieve strong anonymity. We analyze prominent AC protocols from the literature and depict to which extent those satisfy our necessary constraints. Our fundamental necessary constraints offer a guideline not only for improving existing AC systems but also for designing novel AC protocols with non-traditional bandwidth and latency overhead choices.

In an $\ell$ out of $n$ threshold scheme, $\ell$ out of $n$ members must cooperate to recover a secret. A kleptographic attack is a backdoor which can be implemented in an algorithm and further used to retrieve a user's secret key. We combine the notions of threshold scheme and kleptographic attack to construct the first $\ell$ out of $n$ threshold kleptographic attack on discrete logarithm based digital signatures and prove its security in the standard and random oracle models.

Protocols for secure two-party computation enable a pair of mutually distrustful parties to carry out a joint computation of their private inputs without revealing anything but the output. One important security property that has been considered is that of fairness which guarantees that if one party learns the output then so does the other. In the case of two-party computation, fairness is not always possible, and in particular two parties cannot fairly toss a coin (Cleve, 1986). Despite this, it is actually possible to securely compute many two-party functions with fairness (Gordon et al., 2008 and follow-up work). However, all two-party protocols known that achieve fairness have the unique property that the effective input of the corrupted party is determined at an arbitrary point in the protocol. This is in stark contrast to almost all other known protocols that have an explicit fixed round at which the inputs are committed. In this paper, we ask whether or not the property of not having an input committal round is inherent for achieving fairness for two parties. In order to do so, we revisit the definition of security of Micali and Rogaway (Technical report, 1992), that explicitly requires the existence of such a committal round. We adapt the definition of Canetti in the two-party setting to incorporate the spirit of a committal round, and show that under such a definition, it is impossible to achieve fairness for any non-constant two-party function. This result deepens our understanding as to the type of protocol construction that is needed for achieving fairness. In addition, our result discovers a fundamental difference between the definition of security of Micali and Rogaway and that of Canetti (Journal of Cryptology, 2000) which has become the standard today. Specifically, many functions can be securely computed with fairness under the definition of Canetti but no non-constant function can be securely computed with fairness under the definition of Micali and Rogaway.

In contrast to classical signature schemes, such as RSA or ECDSA signatures, the lattice-based signature scheme ring-TESLA is expected to be resistant even against quantum adversaries. Due to a recent key recovery from a lattice-based implementation, it becomes clear that cache side channels are a serious threat for lattice-based implementations. In this article, we analyze an existing implementation of ring-TESLA against cache side channels. To reduce the effort for manual code inspection, we selectively employ automated program analysis. The leakage bounds we compute with program analysis are sound overapproximations of cache-side-channel leakage. We detect four cache-side-channel vulnerabilities in the implementation of ring-TESLA. Since two vulnerabilities occur in implementations of techniques common to lattice-based schemes, they are also interesting beyond ring-TESLA. Finally, we show how the detected vulnerabilities can be mitigated effectively.

Austrin, Chung, Mahmoody, Pass and Seth (Crypto'14) studied the notion of bitwise $p$-tampering attacks over randomized algorithms in which an efficient `virus' gets to control each bit of the randomness with independent probability $p$ in an online way. The work of Austrin et al. showed how to break certain `privacy primitives' (e.g., encryption, commitments, etc.) through bitwise $p$-tampering, by giving a bitwise $p$-tampering biasing attack for increasing the average $E[f(U_n)]$ of any efficient function $f \colon \{0,1\}^n \to [-1,+1]$ by $\Omega(p \cdot Var[f(U_n)])$ where $Var[f(U_n)]$ is the variance of $f(U_n)$. In this work, we revisit and extend the bitwise tampering model of Austrin et al. to blockwise setting, where blocks of randomness becomes tamperable with independent probability $p$. Our main result is an efficient blockwise $p$-tampering attack to bias the average $E[f(X)]$ of any efficient function $f$ mapping arbitrary $X$ to $[-1,+1]$ by $\Omega(p \cdot Var[f(X)])$ regardless of how $X$ is partitioned into individually tamperable blocks $X=(X_1,\dots,X_n)$. Relying on previous works, our main biasing attack immediately implies efficient attacks against the privacy primitives as well as seedless multi-source extractors, in a model where the attacker gets to tamper with each block (or source) of the randomness with independent probability $p$. Further, we show how to increase the classification error of deterministic learners in the so called `targeted poisoning' attack model under Valiant's adversarial noise. In this model, an attacker has a `target' test data $d$ in mind and wishes to increase the error of classifying $d$ while she gets to tamper with each training example with independent probability $p$ an in an online way.

Keeping correct and informative log files is crucial for system maintenance, security and forensics. Cryptographic logging schemes offer integrity checks that protect a log file even in the case where an attacker has broken into the system. A relatively recent feature of these schemes is resistance against truncations, i.e. the deletion and/or replacement of the end of the log file. This is especially relevant as system intruders are typically interested in manipulating the later log entries that point towards their attack. However, there are not many schemes that are resistant against truncating the log file. Those that are have at least one of the following disadvantages: They are memory intensive (they store at least one signature per log entry), or fragile (i.e. a single error in the log renders the signature invalid and useless in determining where the error occurred). We obtain a publicly-verifiable secure logging scheme that is simultaneously robust, space-efficient and truncation secure with provable security under simple assumptions. Our generic construction uses forward-secure signatures, in a plain and a sequential aggregate variant, where the latter is additionally fault-tolerant, as recently formalized by Hartung et al. (PKC 2016). Fault-tolerant schemes can cope with a number of manipulated log entries (bounded a priori) and offer strong robustness guarantees while still retaining space efficiency. Our implementation and the accompanying performance measurements confirm the practicality of our scheme.

Threshold secret sharing schemes enable a dealer to share a secret among $n$ parties such that only subsets of parties of cardinality at least $k = k(n)$ can reconstruct the secret. Komargodski, Naor and Yogev (TCC 2016-B) proposed an efficient scheme for sharing a secret among an unbounded number of parties such that only subsets of $k$ parties can recover the secret, where $k$ is any fixed constant. This access structure is known as $k$-threshold. They left open the possibility of an efficient scheme for the dynamic threshold access structure, in which the qualified sets are of increasing size as the number of parties increases. We resolve this open problem and present a construction in which the share size of the $t$-th party is $O(t^4\cdot \log t)$ bits. Furthermore, we show how to generically translate any scheme for $k$-threshold into a scheme which is robust, where a shared secret can be recovered even if some parties hand-in incorrect shares. This answers another open problem of Komargodski et al. Our construction is based on the construction of robust (classical) secret sharing schemes of Cramer et al. (EUROCRYPT 2008) using algebraic manipulation detection codes.

We consider the problem of constant-round secure two-party computation in the presence of active (malicious) adversaries. We present the first protocol that has only a constant multiplicative communication overhead compared to Yao's protocol for passive adversaries, and can be implemented in the plain model by only making a black-box use of (parallel) oblivious transfer and a pseudo-random generator. This improves over the polylogarithmic overhead of the previous best protocol. A similar result could previously be obtained only in an amortized setting, using preprocessing, or by assuming bit-oblivious-transfer as an ideal primitive that has a constant cost. We present two variants of this result, one which is aimed at minimizing the number of oblivious transfers and another which is aimed at optimizing concrete efficiency. Our protocols are based on a novel combination of previous techniques together with a new efficient protocol to certify that pairs of strings transmitted via oblivious transfer satisfy a global relation. Settling for ``security with correlated abort'', the concrete communication complexity of the second variant of our protocol can beat the best previous protocols with the same kind of security even for realistic values of the circuit size and the security parameter. This variant is particularly attractive in the offline-online setting, where the online cost is dominated by a single evaluation of an authenticated garbled circuit, and can also be made non-interactive using the Fiat-Shamir heuristic.

All known multilinear map candidates have suffered from a class of attacks known as ``zeroizing'' attacks, which render them unusable for many applications. We provide a new construction of polynomial-degree multilinear maps and show that our scheme is provably immune to zeroizing attacks under a strengthening of the Branching Program Un-Annihilatability Assumption (Garg et al., TCC 2016-B). Concretely, we build our scheme on top of the CLT13 multilinear maps (Coron et al., CRYPTO 2013). In order to justify the security of our new scheme, we devise a weak multilinear map model for CLT13 that captures zeroizing attacks and generalizations, reflecting all known classical polynomial-time attacks on CLT13. In our model, we show that our new multilinear map scheme achieves ideal security, meaning no known attacks apply to our scheme. Using our scheme, we give a new multiparty key agreement protocol that is several orders of magnitude more efficient that what was previously possible. We also demonstrate the general applicability of our model by showing that several existing obfuscation and order-revealing encryption schemes, when instantiated with the CLT13 maps, are secure against known attacks. These are schemes that are actually being implemented for experimentation, but until our work had no rigorous justification for security.

Several cryptographic schemes and applications are based on functions that are both reasonably efficient to compute and moderately hard to invert, including client puzzles for Denial-of-Service protection, password protection via salted hashes, or recent proof-of-work blockchain systems. Despite their wide use, a definition of this concept has not yet been distilled and formalized explicitly. Instead, either the applications are proven directly based on the assumptions underlying the function, or some property of the function is proven, but the security of the application is argued only informally. The goal of this work is to provide a (universal) definition that decouples the efforts of designing new moderately hard functions and of building protocols based on them, serving as an interface between the two. On a technical level, beyond the mentioned definitions, we instantiate the model for four different notions of hardness. We extend the work of Alwen and Serbinenko (STOC 2015) by providing a general tool for proving security for the first notion of memory-hard functions that allows for provably secure applications. The tool allows us to recover all of the graph-theoretic techniques developed for proving security under the older, non-composable, notion of security used by Alwen and Serbinenko. As an application of our definition of moderately hard functions, we prove the security of two different schemes for proofs of effort (PoE). We also formalize and instantiate the concept of a non-interactive proof of effort (niPoE), in which the proof is not bound to a particular communication context but rather any bit-string chosen by the prover.

We present a unified framework for obtaining black-box constructions of Universal Composable (UC) protocol in trusted setup models. Our result is analogous to the unified framework of Lin, Pass, and Venkitasubramaniam [STOC'09, Asiacrypt'12] that, however, only yields non-black-box constructions of UC protocols. Our unified framework shows that to obtain black-box constructions of UC protocols, it suffices to implement a special purpose commitment scheme that is, in particular, concurrently extractable using a given trusted setup. Using our framework, we improve black-box constructions in the common reference string and tamper-proof hardware token models by weakening the underlying computational and setup assumptions.

Realizing indistinguishablility obfuscation (IO) based on well-understood computational assumptions is an important open problem. Recently, realizing functional encryption (FE) has emerged as promising directing towards that goal. This is because: (1) compact single-key FE (where the functional secret-key is of length double the ciphertext length) is known to imply IO [Anath and Jain, CRYPTO 2015; Bitansky and Vaikuntanathan, FOCS 2015] and (2) several strong variants of single-key FE are known based on various standard computation assumptions. In this work, we study when FE can be used for obtaining IO. We show any single-key FE for function families with ``short'' enough outputs (specifically the output is less than ciphertext length by a value at least $\omega(n + k)$, where $n$ is the message length and $k$ is the security parameter) is insufficient for IO even when non-black-box use of the underlying FE is allowed to some degree. Namely, our impossibility result holds even if we are allowed to plant FE sub-routines as gates inside the circuits for which functional secret-keys are issued (which is exactly how the known FE to IO constructions work). Complementing our negative result, we show that our condition of ``short'' enough is almost tight. More specifically, we show that any compact single-key FE with functional secret-key output length strictly larger than ciphertext length is sufficient for IO. Furthermore, we show that non-black-box use of the underlying FE is necessary for such a construction, by ruling out any fully black-box construction of IO from FE even with arbitrary long output.

We revisit the exact round complexity of secure two-party computation. While four rounds are known to be sufficient for securely computing general functions that provide output to one party [Katz-Ostrovsky, CRYPTO'04], Goldreich-Krawczyk [SIAM J. Computing'96] proved that three rounds are insufficient for this task w.r.t. black-box simulation. In this work, we study the feasibility of secure computation in three rounds using non-black-box simulation. Our main result is a three-round two-party computation protocol for general functions against adversaries with auxiliary inputs of bounded size. This result relies on a new two round input-extraction protocol based on succinct randomized encodings. We also provide a partial answer to the question of achieving security against non-uniform adversaries. Assuming sub-exponentially secure iO and one-way functions, we rule out three-round protocols that achieve polynomial simulation-based security against the output party and exponential indistinguishability-based security against the other party.

.

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph $G=(V,E)$ if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in $E$ (i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes. A secret-sharing scheme is linear if the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. dense) graph with $n$ vertices and at most $n^{1+\beta}$ edges (resp. at least $\binom{n}{2} - n^{1+\beta}$ edges), for some $ 0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure in which the total size of the shares is $\tilde{O} (n^{1+\beta/2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is $\tilde{O} (n^{1/4+\beta/4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size $\Omega(n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every $0 \leq \beta < 1$ there exist a graph with at most $n^{1+\beta}$ edges and a graph with at least $\binom{n}{2}-n^{1+\beta}$ edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is $\Omega (n^{1+\beta/2})$. Finally, we show that for every $0 \leq \beta < 1$ there exist a graph with at most $n^{1+\beta}$ edges and a graph with at least $\binom{n}{2}-n^{1+\beta}$ edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is $\Omega (n^{1/4+\beta/4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

An attacker or evaluator can detect more information leakages if he improves the Signal-to-Noise Ratio (SNR) of power traces in his tests. For this purpose, pre-processings such as de-noise, distribution-based traces biasing are used. However, the existing traces biasing schemes can't accurately express the characteristics of power traces with high SNR, making them not ideal for leakage detections. Moreover, if the SNR of power traces is very low, it is very difficult to use the existing de-noise schemes and traces biasing schemes to enhance leakage detection. In this paper, a known key based pre-processing tool named Traces Linear Optimal Biasing (TLOB) is proposed, which performs very well even on power traces with very low SNR. It can accurately evaluate the noise of time samples and give reliable traces optimal biasing. Experimental results show that TLOB significantly reduces number of traces used for detection; correlation coefficients in $\rho$-tests using TLOB approach 1.00, thus the confidence of tests is significantly improved. As far as we know, there is no pre-processing tool more efficient than TLOB. TLOB is very simple, and only brings very limited time and memory consumption. We strongly recommend to use it to pre-process traces in side channel evaluations.

We identify a flaw in the security proof and a flaw in the concrete security analysis of the WOTS-PRF variant of the Winternitz one-time signature scheme, and discuss the implications to its concrete security.

We revisit security proofs for various cryptographic primitives in the auxiliary-input random-oracle model (AI-ROM), in which an attacker $A$ can compute arbitrary $S$ bits of leakage about the random oracle $\mathcal O$ before attacking the system and then use additional $T$ oracle queries to $\mathcal O$ during the attack. This model has natural applications in settings where traditional random-oracle proofs are not useful: (a) security against non-uniform attackers; (b) security against preprocessing. We obtain a number of new results about the AI-ROM: Unruh (CRYPTO '07) introduced the pre-sampling technique, which generically reduces security proofs in the AI-ROM to a much simpler $P$-bit-fixing random-oracle model (BF-ROM), where the attacker can arbitrarily fix the values of $\mathcal O$ on some $P$ coordinates, but then the remaining coordinates are chosen at random. Unruh's security loss for this transformation is $\sqrt{ST/P}$. We improve this loss to the optimal value $O(ST/P)$, which implies nearly tight bounds for a variety of indistinguishability applications in the AI-ROM. While the basic pre-sampling technique cannot give tight bounds for unpredictability applications, we introduce a novel "multiplicative version" of pre-sampling, which allows to dramatically reduce the size of $P$ of the pre-sampled set to $P=O(ST)$ and yields nearly tight security bounds for a variety of unpredictability applications in the AI-ROM. Qualitatively, it validates Unruh's "polynomial pre-sampling conjecture"---disproved in general by Dodis et al. (EUROCRYPT '17)---for the special case of unpredictability applications. Using our techniques, we reprove nearly all AI-ROM bounds obtained by Dodis et al. (using a much more laborious compression technique), but we also apply it to many settings where the compression technique is either inapplicable (e.g., computational reductions) or appears intractable (e.g., Merkle-Damgard hashing). We show that for any salted Merkle-Damgard hash function with m-bit output there exists a collision-finding circuit of size $\Theta(2^{m/3})$ (taking salt as the input), which is significantly below the $2^{m/2}$ birthday security conjectured against uniform attackers. We build two general compilers showing how to generically extend the security of applications proven in the traditional ROM to the AI-ROM. One compiler simply prepends a public salt to the random oracle and shows that salting generically provably defeats preprocessing. Overall, our results make it much easier to get concrete security bounds in the AI-ROM. These bounds in turn give concrete conjectures about the security of these applications (in the standard model) against non-uniform attackers.

Quantum secure signature schemes have a lot of attention recently, in particular because of the NIST call to standardize quantum safe cryptography. However, only few signature schemes can have concrete quantum security because of technical difficulties associated with the Quantum Random Oracle Model (QROM). In this paper, we show that code-based signature schemes based on the full domain hash paradigm can behave very well in the QROM i.e. that we can have tight security reductions. We also study quantum algorithms related to the underlying code-based assumption. Finally, we apply our reduction to a concrete example: the SURF signature scheme. We provide parameters for 128 bits of quantum security in the QROM and show that the obtained parameters are competitive compared to other similar quantum secure signature schemes.

Blockchain technology has the potential to disrupt how cryptography is done. In this work, we propose to view blockchains as an "enabler", much like indistinguishability obfuscation (Barak et al., CRYPTO 2001, Garg et al., FOCS 2013, and Sahai and Waters, STOC 2014) or one-way functions, for building a variety of cryptographic systems. Our contributions in this work are as follows: 1. A Framework for Proof-of-Stake based Blockchains: We provide an abstract framework for formally analyzing and defining useful security properties for Proof-of-Stake (POS) based blockchain protocols. Interestingly, for some of our applications, POS based protocols are more suitable. We believe our framework and assumptions would be useful in building applications on top of POS based blockchain protocols even in the future. 2. Blockchains as an Alternative to Trusted Setup Assumptions in Cryptography: A trusted setup, such as a common reference string (CRS) has been used to realize numerous systems in cryptography. The paragon example of a primitive requiring trusted setup is a non-interactive zero-knowledge (NIZK) system. We show that already existing blockchains systems including Bitcoin, Ethereum etc. can be used as a foundation (instead of a CRS) to realize NIZK systems. The novel aspect of our work is that it allows for utilizing an already existing (and widely trusted) setup rather than proposing a new one. Our construction does not require any additional functionality from the miners over the already existing ones, nor do we need to modify the underlying blockchain protocol. If an adversary can violate the security of our NIZK, it could potentially also take over billions of dollars worth of coins in the Bitcoin, Ethereum or any such cryptocurrency! We believe that such a "trusted setup" represents significant progress over using CRS published by a central trusted party. Indeed, NIZKs could further serve as a foundation for a variety of other cryptographic applications such as round efficient secure computation (Katz and Ostrovsky, CRYPTO 2004 and Horvitz and Katz, CRYPTO 2007). 3. One-time programs and pay-per use programs: Goldwasser et al. (CRYPTO 2008) introduced the notion of one time program and presented a construction using tamper-proof hardware. As noted by Goldwasser et al., clearly a one-time program cannot be solely software based, as software can always be copied and run again. While there have been a number of follow up works (Goyal et al., TCC 2010, Bellare et al., ASIACRYPT 2012, and Applebaum et al., SIAM Journal on Computing 2015), there are indeed no known constructions of one-time programs which do not rely on self destructing tamper-proof hardware (even if one uses trusted setup or random oracles). Somewhat surprisingly, we show that it is possible to base one-time programs on POS based blockchain systems without relying on trusted hardware. Our ideas do not seem to translate over to Proof-of-Work (POW) based blockchains. We also introduce the notion of pay-per-use programs which is simply a contract between two parties --- service provider and customer. A service provider supplies a program such that if the customer transfers a specific amount of coins to the provider, it can evaluate the program on any input of its choice once, even if the provider is offline. This is naturally useful in a subscription based model where your payment is based on your usage.

A garbling scheme is used to garble a circuit $C$ and an input $x$ in a way that reveals the output $C(x)$ but hides everything else. An adaptively secure scheme allows the adversary to specify the input $x$ after seeing the garbled circuit. Applebaum et al. (CRYPTO '13) showed that in any garbling scheme with adaptive simulation-based security, the size of the garbled input must exceed the output size of the circuit. Here we show how to circumvent this lower bound and achieve significantly better efficiency under the minimal assumption that one-way functions exist by relaxing the security notion from simulation-based to indistinguishability-based. We rely on the recent work of Hemenway et al. (CRYPTO '16) which constructed an adaptive simulation-based garbling scheme under one-way functions. The size of the garbled input in their scheme is as large as the output size of the circuit plus a certain pebble complexity of the circuit, where the latter is (e.g.,) bounded by the space complexity of the computation. By building on top of their construction and adapting their proof technique, we show how to remove the output size dependence in their result when considering indistinguishability-based security. As an application of the above result, we get a symmetric-key functional encryption based on one-way functions, with indistinguishability-based security where the adversary can obtain an unbounded number of function secret keys and then adaptively a single challenge ciphertext. The size of the ciphertext only depends on the maximal pebble complexity of each of the functions but not on the number of functions or their circuit size.

We present several optimizations to SPHINCS, a stateless hash-based signature scheme proposed by Bernstein et al. in 2015: PORS, a more secure variant of the HORS few-time signature scheme used in SPHINCS; secret key caching, to speed-up signing and reduce signature size; batch signing, to amortize signature time and reduce signature size when signing multiple messages at once; mask-less constructions to reduce the key size and simplify the scheme; and Octopus, a technique to eliminate redundancies from authentication paths in Merkle trees. Based on a refined analysis of the subset resilience problem, we show that SPHINCS' parameters can be modified to reduce the signature size while retaining a similar security level and computation time. We then propose Gravity-SPHINCS, our variant of SPHINCS embodying the aforementioned tricks. Gravity-SPHINCS has shorter keys (32 and 64 bytes instead of $\approx1$ KB), shorter signatures ($\approx30$ KB instead of 41 KB), and faster signing and verification for a same security level as SPHINCS.

In a novel analysis, we formally prove that arbitrarily many Arbiter PUFs can be combined into a stable XOR Arbiter PUF. To the best of our knowledge, this design cannot be modeled by any known oracle access attack in polynomial time. Using majority vote of arbiter chain responses, our analysis shows that with a polynomial number of votes, the XOR Arbiter PUF stability of almost all challenges can be boosted exponentially close to 1; that is, the stability gain through majority voting can exceed the stability loss introduced by large XORs for a feasible number of votes. Considering state-of-the-art modeling attacks by Becker and Rührmair et al., our proposal enables the designer to increase the attacker's effort exponentially while still maintaining polynomial design effort. This is the first result that relates PUF design to this traditional cryptographic design principle.

In this work we start from the following two results in the state-of-the art: 1) 4-round non-malleable zero knowledge (NMZK): Goyal et al. in FOCS 2014 showed the first 4-round one-one NMZK argument from one-way functions (OWFs). Their construction requires the prover to know the instance and the witness already at the 2nd round. 2) 4-round multi-party coin tossing (MPCT): Garg et al. in Eurocrypt 2016 showed the first 4-round protocol for MPCT. Their result crucially relies on 3-round 3-robust parallel non-malleable commitments. So far there is no candidate construction for such a commitment scheme under standard polynomial-time hardness assumptions. We improve the state-of-the art on NMZK and MPCT by presenting the following two results: 1) a delayed-input 4-round one-many NMZK argument $\Pi_{nmzk}$ from OWFs; moreover $\Pi_{nmzk}$ is also a delayed-input many-many synchronous NMZK argument. 2) a 4-round MPCT protocol $\Pi_{mpcf}$ from one-to-one OWFs; $\Pi_{mpcf}$ uses $\Pi_{nmzk}$ as subprotocol and exploits the special properties (e.g., delayed input, many-many synchronous) of $\Pi_{nmzk}$. $\Pi_{mpcf}$ makes use of a special proof of knowledge that offers additional security guarantees when played in parallel with other protocols. The new technique behind such a proof of knowledge is an additional contribution of this work and is of independent interest.

Non-malleable codes (NMCs), introduced by Dziembowski, Pietrzak and Wichs (ITCS 2010), generalize the classical notion of error correcting codes by providing a powerful guarantee even in scenarios where error correcting codes cannot provide any guarantee: a decoded message is either the same or completely independent of the underlying message, regardless of the number of errors introduced into the codeword. Informally, NMCs are defined with respect to a family of tampering functions $F$ and guarantee that any tampered codeword either decodes to the same message or to an independent message, so long as it is tampered using a function $f \in F$. Nearly all known constructions of NMCs are for the $t$-split-state family, where the adversary tampers each of the $t$ blocks (also known as states), of a codeword, arbitrarily but independently. Cheraghchi and Guruswami (TCC 2014) obtain a Rate-1 non-malleable code for the case where $t = O(n)$ with $n$ being the codeword length and, in (ITCS 2014), show an upper bound of $1-1/t$ on the best achievable rate for any $t-$split state NMC. For $t=10$, Chattopadhyay and Zuckerman (FOCS 2014) achieve a constant rate construction where the constant is unknown. In summary, there is no known construction of an NMC with an explicit constant rate for any $t= o(n)$, let alone one that comes close to matching Cheraghchi and Guruswami's lowerbound! In this work, we construct an efficient non-malleable code in the $t$-split-state model, for $t=4$, that achieves a constant rate of $\frac{1}{3+\zeta}$, for any constant $\zeta > 0$, and error $2^{-\Omega(\ell / log^{c+1} \ell)}$, where $\ell$ is the length of the message and $c > 0$ is a constant.

Since their introduction in the late 90's, side-channel attacks have been considered as a major threat against cryptographic implementations. This threat has raised the need for formal leakage models in which the security of implementations can be proved. At Eurocrypt 2013, Prouff and Rivain introduced the noisy leakage model which has been argued to soundly capture the physical reality of power and electromagnetic leakages. In their work, they also provide the first formal security proof for a masking scheme in the noisy leakage model. However their work has two important limitations: (i) the security proof relies on the existence of a leak-free component, (ii) the tolerated amount of information in the leakage (aka leakage rate) is of $O(1/n)$ where $n$ is the number of shares in the underlying masking scheme. The first limitation was nicely tackled by Duc, Dziembowski and Faust one year later (Eurocrypt 2014). Their main contribution was to show a security reduction from the noisy leakage model to the conceptually simpler random-probing model. They were then able to prove the security of the well-known Ishai-Sahai-Wagner scheme (Crypto 2003) in the noisy leakage model. The second limitation was addressed last year in a paper by Andrychowicz, Dziembowski and Faust (Eurocrypt 2016). The proposed construction achieves security in the strong adaptive probing model with a leakage rate of $O(1/\log n)$ at the cost of a $O(n^2 \log n)$ complexity. The authors argue that their result can be translated into the noisy leakage model with a leakage rate of $O(1)$ by using secret sharing based on algebraic geometric codes. They further argue that the efficiency of their construction can be improved by a linear factor using packed secret sharing but no details are provided. In this paper, we show how to compute in the presence of noisy leakage with a leakage rate up to $\tilde{O}(1)$ in complexity $\tilde{O}(n)$. We use a polynomial encoding allowing quasilinear multiplication based on the fast Number Theoretic Transform (NTT). We first show that our scheme is secure in the random-probing model with leakage rate $O(1/\log n)$. Using the reduction by Duc et al. this result can be translated in the noisy leakage model with a $O(1/|\mathbb{F}|^2 \log n)$ leakage rate. However, as in the work of Andrychowicz et al., our construction also requires $|\mathbb{F}| = O(n)$. In order to bypass this issue, we refine the granularity of our computation by considering the noisy leakage model on logical instructions} that work on constant-size machine words. We provide a generic security reduction from the noisy leakage model at the logical-instruction level to the random-probing model at the arithmetic level. This reduction allows us to prove the security of our construction in the noisy leakage model with leakage rate $\tilde{O}(1)$.

Malware needs to execute on a target machine while simultaneously keeping its payload confidential from a malware analyst. Standard encryption can be used to ensure the confidentiality, but it does not address the problem of hiding the key. Any analyst can find the decryption key if it is stored in the malware or derived in plain view. One approach is to derive the key from a part of the environment which changes when the analyst is present. Such malware derives a key from the environment and encrypts its true functionality under this key. In this paper, we present a formal framework for environmental authentication. We formalize the interaction between malware and analyst in three settings: 1) blind: in which the analyst does not have access to the target environment, 2) basic: where the analyst can load a single analysis toolkit on an effected target, and 3) resettable: where the analyst can create multiple copies of an infected environment. We show necessary and sufficient conditions for malware security in the blind and basic games and show that even under mild conditions, the analyst can always win in the resettable scenario.

We study the question of minimizing the computational complexity of (robust) secret sharing schemes and error correcting codes. In standard instances of these objects, both encoding and decoding involve linear algebra, and thus cannot be implemented in the class AC0. The feasibility of non-trivial secret sharing schemes in AC0 was recently shown by Bogdanov et al. (Crypto 2016) and that of (locally) decoding errors in AC0 by Goldwasser et al. (STOC 2007). In this paper, we show that by allowing some slight relaxation such as a small error probability, we can construct much better secret sharing schemes and error correcting codes in the class AC0. In some cases, our parameters are close to optimal and would be impossible to achieve without the relaxation. Our results significantly improve previous constructions in various parameters. Our constructions combine several ingredients in pseudorandomness and combinatorics in an innovative way. Specifically, we develop a general technique to simultaneously amplify security threshold and reduce alphabet size, using a two-level concatenation of protocols together with a random permutation. We demonstrate the broader usefulness of this technique by applying it in the context of a variant of secure broadcast.

Trusted parties and devices are commonly used in the real world to securely perform computations on secret inputs. However, their security can often be compromised by side-channel attacks in which the adversary obtains partial leakage on intermediate computation values. This gives rise to the following natural question: To what extent can one protect the trusted party against leakage? Our goal is to design a hardware device $T$ that allows $m\ge 1$ parties to securely evaluate a function $f(x_1,\ldots,x_m)$ of their inputs by feeding $T$ with encoded inputs that are obtained using local secret randomness. Security should hold even in the presence of an active adversary that can corrupt a subset of parties and obtain restricted leakage on the internal computations in $T$. We design hardware devices $T$ in this setting both for zero-knowledge proofs and for general multi-party computations. Our constructions can unconditionally resist either $AC^0$ leakage or a strong form of ``only computation leaks'' (OCL) leakage that captures realistic side-channel attacks, providing different tradeoffs between efficiency and security.

In FOCS 2001 Barak et al. conjectured the existence of zero-knowledge arguments that remain secure against resetting provers and resetting verifiers. The conjecture was proven true by Deng et al. in FOCS 2009 under various complexity assumptions and requiring a polynomial number of rounds. Later on in FOCS 2013 Chung et al. improved the assumptions requiring one-way functions only but still with a polynomial number of rounds. In this work we show a constant-round resettably-sound resettable zero-knowledge argument system, therefore improving the round complexity from polynomial to constant. We obtain this result through the following steps. 1. We show an explicit transform from any $\ell$-round concurrent zero-knowledge argument system into an $O(\ell)$-round resettable zero-knowledge argument system. The transform is based on techniques proposed by Barak et al. in FOCS 2001 and by Deng et al. in FOCS 2009. Then, we make use of a recent breakthrough presented by Chung et al. in CRYPTO 2015 that solved the longstanding open question of constructing a constant-round concurrent zero-knowledge argument system from plausible polynomial-time hardness assumptions. Starting with their construction $\Gamma$ we obtain a constant-round resettable zero-knowledge argument system $\Lambda$. 2. We then show that by carefully embedding $\Lambda$ inside $\Gamma$ (i.e., essentially by playing a modification of the construction of Chung et al. against the construction of Chung et al.) we obtain the first constant-round resettably-sound concurrent zero-knowledge argument system $\Delta$. 3. Finally, we apply a transformation due to Deng et al. to $\Delta$ obtaining a resettably-sound resettable zero-knowledge argument system $\Pi$, the main result of this work. While our round-preserving transform for resettable zero knowledge requires one-way functions only, both $\Lambda, \Delta$ and $\Pi$ extend the work of Chung et al. and as such they rely on the same assumptions (i.e., families of collision-resistant hash functions, one-way permutations and indistinguishability obfuscation for P/poly, with slightly super-polynomial security).

Oblivious RAM (ORAM) is a powerful cryptographic building block that allows a program to provably hide its access patterns to sensitive data. Since the original proposal of ORAM by Goldreich and Ostrovsky, numerous improvements have been made. To date, the best asymptotic overhead achievable for general block sizes is $O(\log^2 N/\log \log N)$, due to an elegant scheme by Kushilevitz et al., which in turn relies on the oblivious Cuckoo hashing scheme by Goodrich and Mitzenmacher. In this paper, we make the following contributions: we first revisit the prior $O(\log^2 N/\log \log N)$-overhead ORAM result. We demonstrate the somewhat incompleteness of this prior result, due to the subtle incompleteness of a core building block, namely, Goodrich and Mitzenmacher's oblivious Cuckoo hashing scheme. Even though we do show how to patch the prior result such that we can fully realize Goodrich and Mitzenmacher's elegant blueprint for oblivious Cuckoo hashing, it is clear that the extreme complexity of oblivious Cuckoo hashing has made understanding, implementation, and proofs difficult. We show that there is a conceptually simple $O(\log^2 N/\log \log N)$-overhead ORAM that dispenses with oblivious Cuckoo hashing entirely. We show that such a conceptually simple scheme lends to further extensions. Specifically, we obtain the first $O(\log^2 N/\log \log N)$ Oblivious Parallel RAM (OPRAM) scheme, thus not only matching the performance of the best known sequential ORAM, but also achieving super-logarithmic improvements in comparison with known OPRAM schemes.

Traditional fully homomorphic encryption (FHE) schemes support computation on data encrypted under a single key. In STOC 2012, López-Alt et al. introduced the notion of multi-key FHE (MKFHE), which allows homomorphic computation on ciphertexts encrypted under different keys. In this work, we focus on MKFHE constructions from standard assumptions and propose a new construction of ring-LWE-based multi-hop MKFHE scheme. Our work is based on Brakerski-Gentry-Vaikuntanathan (BGV) FHE scheme where, in contrast, all the previous works on multi-key FHE with standard assumptions were based on Gentry-Sahai-Waters (GSW) FHE scheme. Therefore, our construction can encrypt ring elements rather than a single bit and naturally inherits the advantages in aspects of the ciphertext/plaintext ratio and the complexity of homomorphic operations. Moveover, the proposed MKFHE scheme supports the Chinese Remainder Theorem (CRT)-based ciphertexts packing technique, achieves $poly\left(k,L,\log n\right)$ computation overhead for $k$ users, circuits with depth at most $L$ and an $n$ dimensional lattice, and gives the first batched MKFHE scheme based on standard assumptions to our knowledge. Furthermore, the ciphertext extension algorithms of previous schemes need to perform complex computation on each ciphertext, while our extension algorithm just needs to generate evaluation keys for the extended scheme. So the complexity of ciphertext extension is only dependent on the number of associated parities but not on the number of ciphertexts. Besides, our scheme also admits a threshold decryption protocol from which a generalized two-round MPC protocol can be similarly obtained as prior works.

Zero knowledge proof systems have been widely studied in cryptography. In the statistical setting, two classes of proof systems studied are Statistical Zero Knowledge (SZK) and Non-Interactive Statistical Zero Knowledge (NISZK), where the difference is that in NISZK only very limited communication is allowed between the verifier and the prover. It is an open problem whether these two classes are in fact equal. In this paper, we rule out efficient black box reductions between SZK and NISZK. We achieve this by studying algorithms which can reverse the entropy of a function. The problem of estimating the entropy of a circuit is complete for NISZK. Hence, reversing the entropy of a function is equivalent to a black box reduction of NISZK to its complement, which is known to be equivalent to a black box reduction of SZK to NISZK [Goldreich et al, CRYPTO 1999]. We show that any such black box algorithm incurs an exponential loss of parameters, and hence cannot be implemented efficiently.

In this work, we initially study the necessary properties and security requirements of Ring Confidential Transaction (RingCT) protocol deployed in the popular anonymous cryptocurrency Monero. Firstly, we formalize the syntax of RingCT protocol and present several formal security definitions according to its application in Monero. Based on our observations on the underlying (linkable) ring signature and commitment schemes, we then put forward a new efficient RingCT protocol (RingCT 2.0), which is built upon the well-known Pedersen commitment, accumulator with one-way domain and signature of knowledge (which altogether perform the functions of a linkable ring signature). Besides, we show that it satisfies the security requirements if the underlying building blocks are secure in the random oracle model. In comparison with the original RingCT protocol, our RingCT 2.0 protocol presents a significant space saving, namely, the transaction size is independent of the number of groups of input accounts included in the generalized ring while the original RingCT suffers a linear growth with the number of groups, which would allow each block to process more transactions.

In this work we continue the study on the round complexity of secure two-party computation with black-box simulation. Katz and Ostrovsky in CRYPTO 2004 showed a 5 (optimal) round construction assuming trapdoor permutations for the general case where both players receive the output. They also proved that their result is round optimal. This lower bound has been recently revisited by Garg et al. in Eurocrypt 2016 where a 4 (optimal) round protocol is showed assuming a simultaneous message exchange channel. Unfortunately there is no instantiation of the protocol of Garg et al. under standard polynomial-time hardness assumptions. In this work we close the above gap by showing a 4 (optimal) round construction for secure two-party computation in the simultaneous message channel model with black-box simulation, assuming trapdoor permutations against polynomial-time adversaries. Our construction for secure two-party computation relies on a special 4-round protocol for oblivious transfer that nicely composes with other protocols in parallel. We define and construct such special oblivious transfer protocol from trapdoor permutations. This building block is clearly interesting on its own. Our construction also makes use of a recent advance on non-malleability: a delayed-input 4-round non-malleable zero knowledge argument.

We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

To strengthen the resistance of countermeasures based on secret sharing, several works have suggested to use the scheme introduced by Shamir in 1978, which proposes to use the evaluation of a random d-degree polynomial into n > d public points to share the sensitive data. Applying the same principles used against the classical Boolean sharing, all these works have assumed that the most efficient attack strategy was to exploit the minimum number of shares required to rebuild the sensitive value; which is d+1 if the reconstruction is made with Lagrange's interpolation. In this paper, we highlight first an important difference between Boolean and Shamir's sharings which implies that, for some signal-to-noise ratio, it is more advantageous for the adversary to observe strictly more than d+1 shares. We argue that this difference is related to the existence of so-called exact linear repairing codes, which themselves come with reconstruction formulae that need (much) less information (counted in bits) than Lagrange's interpolation. In particular, this result implies that, contrary to what was believed, the choice of the public points in Shamir's sharing has an impact on the countermeasure strength. As another contribution, we exhibit a positive impact of the existence of linear exact repairing schemes; we indeed propose to use them to improve the state-of-the-art multiplication algorithms dedicated to Shamir's sharing. We argue that the improvement can be effective when the multiplication operation in the base field is at least two times smaller than in its sub-fields.

In this paper, we present a practical password scheme due to Spilman, which is perfectly secure in the bounded retrieval model, assuming ideal hash functions. The construction is based on a hash-like function com- puted by a third party “facilitator”. The facilitator is trusted, and security derives from the facilitator’s long random secret, although the adversary is assumed to be able to retrieve a large fraction of that secret. Unlike the traditional “salted and hashed password” approach, this scheme is secure against an adversary capable of performing brute force dictionary attacks offline. The key security property for the facilitator function is a form of uncloneability, that prevents the adversary from calculating function values offline.

The Fiat-Shamir transform is a technique for combining a hash function and an identification scheme to produce a digital signature scheme. The resulting scheme is known to be secure in the random oracle model (ROM), which does not, however, imply security in the scenario where the adversary also has quantum access to the oracle. The goal of this current paper is to create a generic framework for constructing tight reductions in the QROM from underlying hard problems to Fiat-Shamir signatures. Our generic reduction is composed of two results whose proofs, we believe, are simple and natural. We first consider a security notion (UF-NMA) in which the adversary obtains the public key and attempts to create a valid signature without accessing a signing oracle. We give a tight reduction showing that deterministic signatures (i.e., ones in which the randomness is derived from the message and the secret key) that are UF-NMA secure are also secure under the standard chosen message attack (UF-CMA) security definition. Our second result is showing that if the identification scheme is “lossy”, as defined in (Abdalla et al. Eurocrypt 2012), then the security of the UF-NMA scheme is tightly based on the hardness of distinguishing regular and lossy public keys of the identification scheme. This latter distinguishing problem is normally exactly the definition of some presumably-hard mathematical problem. The combination of these components gives our main result. As a concrete instantiation of our framework, we modify the recent lattice-based Dilithium digital signature scheme (Ducas et al., TCHES 2018) so that its underlying identification scheme admits lossy public keys. The original Dilithium scheme, which is proven secure in the classical ROM based on standard lattice assumptions, has 1.5KB public keys and 2.7KB signatures. The new scheme, which is tightly based on the hardness of the Module-LWE problem in the QROM using our generic reductions, has 7.7KB public keys and 5.7KB signatures for the same security level. Furthermore, due to our proof of equivalence between the UF-NMA and UF-CMA security notions of deterministic signature schemes, we can formulate a new non-interactive assumption under which the original Dilithium signature scheme is also tightly secure in the QROM.

Inspired by the astonishing success of cryptocurrencies, most notably the Bitcoin system, several recent works have focused on the design of robust blockchain-style protocols that work in a peer-to-peer setting such as the Internet. In contrast to the setting traditionally considered in multiparty computation (MPC), in these systems, honesty is measured by computing power instead of requiring that only a certain fraction of parties is controlled by the adversary. This provides a potential countermeasure against the so-called Sybil attack, where an adversary creates fake identities, thereby easily taking over the majority of parties in the system. In this work we design protocols for Broadcast and Byzantine agreement that are secure under the assumption that the majority of computing power is controlled by the honest parties and for the first time have expected constant round complexity. This is in contrast to earlier works (Crypto'15, ePrint'14) which have round complexities that scale linearly with the number n of parties; an undesirable feature in a P2P environment with potentially thousands of users. In addition, our main protocol which runs in quasi-constant rounds, introduces novel ideas that significantly decrease communication complexity. Concretely, this is achieved by using an appropriate time-locked encryption scheme and by structuring the parties into a network of so-called cliques. Note: This article contains incorrect claims. Some of its contributions were subsumed by eprint article 2022/823

Although external-memory sorting has been a classical algorithms abstraction and has been heavily studied in the literature, perhaps somewhat surprisingly, when data-obliviousness is a requirement, even very rudimentary questions remain open. Prior to our work, it is not even known how to construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost. We make a significant step forward in our understanding of external-memory, oblivious sorting algorithms. Not only do we construct a comparison-based, external-memory oblivious sorting algorithm that is optimal in IO-cost, our algorithm is also cache-agnostic in that the algorithm need not know the storage hierarchy's internal parameters such as the cache and cache-line sizes. Our result immediately implies a cache-agnostic ORAM construction whose asymptotical IO-cost matches the best known cache-aware scheme. Last but not the least, we propose and adopt a new and stronger security notion for external-memory, oblivious algorithms and argue that this new notion is desirable for resisting possible cache-timing attacks. Thus our work also lays a foundation for the study of oblivious algorithms in the cache-agnostic model.

State machine replication, or “consensus”, is a central abstraction for distributed systems where a set of nodes seek to agree on an ever-growing, linearly-ordered log. In this paper, we propose a practical new paradigm called Thunderella for achieving state machine replication by combining a fast, asynchronous path with a (slow) synchronous “fall-back” path (which only gets executed if something goes wrong); as a consequence, we get simple state machine replications that essentially are as robust as the best synchronous protocols, yet “optimistically” (if a super majority of the players are honest), the protocol “instantly” confirms transactions. We provide instantiations of this paradigm in both permissionless (using proof-of-work) and permissioned settings. Most notably, this yields a new blockchain protocol (for the permissionless setting) that remains resilient assuming only that a majority of the computing power is controlled by honest players, yet optimistically—if 3/4 of the computing power is controlled by honest players, and a special player called the “accelerator”, is honest—transactions are confirmed as fast as the actual message delay in the network. We additionally show the 3/4 optimistic bound is tight for protocols that are resilient assuming only an honest majority.

Two-rounds are minimal for all MPC protocols in the absence of a trusted PKI, however certain protocols allow the reuse of inputs for different functions, or the re-evaluation of the same function on different inputs without the re-distribution of public key information. These can achieve an amortised round complexity of below two rounds per computation. Function rerunnable MPC has been achieved using FHE, while additive homomorphic properties of DH-based cryptosystems have been used to allow input rerunnable protocols. These differ in properties such as computational cost per execution, collusion tolerance and number of rounds supported. We discuss the characteristics of some rerunnable protocols, and present a proof of the rerunnable aggregation protocol of Kursawe, Danezis and Katz from the Decisional Bilinear Diffie Hellman Assumption.

Device-specific physical characteristics provide the foundation for PUFs, a hardware primitive for secure storage of cryptographic keys. So far, they have been implemented by either directly evaluating a binary output or by mapping outputs from a higher-order alphabet to a fixed-length bit sequence. However, the latter causes a significant bias in the derived key when combined with an equidistant quantization. To overcome this limitation, we propose a variable-length bit mapping that reflects the properties of a Gray code in a different metric, namely the Levenshtein metric instead of the classical Hamming metric. Subsequent error-correction is therefore based on a custom insertion/deletion correcting code. This new approach effectively counteracts the bias in the derived key already at the input side. We present the concept for our scheme and demonstrate its feasibility based on an empirical PUF distribution. As a result, we increase the effective output bit length of the secret by over 40% compared to state-of-the-art approaches while at the same time obtaining additional advantages, e.g., an improved tamper-sensitivity. This opens up a new direction of Error-Correcting Codes (ECCs) for PUFs that output responses with symbols of higher-order output alphabets.

A growing number of connected objects, with their high performance and low-resources constraints, are embedding lightweight ciphers for protecting the confidentiality of the data they manipulate or store. Since those objects are easily accessible, they are prone to a whole range of physical attacks, one of which are fault attacks against for which countermeasures are usually expensive to implement, especially on off-the-shelf devices. For such devices, we propose a new generic software countermeasure, called the Internal Redundancy Countermeasure (IRC), to thwart most fault attacks while preserving the performances of the targeted cipher. We report practical experiments showing that IRC successfully thwarts fault attacks on the block cipher PRIDE and on the stream cipher TRIVIUM for which we protect both the initialization and the keystream generation.

We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity $2^{270}$ instead of $2^{277}$. We propose the PRNG to obtain a random subset construction (PORS), which avoids weak messages, for a tiny computational overhead. We adapt PORS to SPHINCS to also deterministically select the HORST instance that is used to sign the input message. This new construction reduces the attack surface and increases the security level, improving the security of SPHINCS by 67 bits against classical attacks and 33 bits against quantum attacks. A version of SPHINCS using our PORS construction can work with smaller parameters that reduce the signature size by 4616 bytes and speed up signature and verification, for the same 128-bit post-quantum security as the original SPHINCS.

We present a very simple yet very powerful idea for turning any passively secure MPC protocol into an actively secure one, at the price of reducing the threshold of tolerated corruptions. Our compiler leads to a very efficient MPC protocols for the important case of secure evaluation of arithmetic circuits over arbitrary rings (e.g., the natural case of $\mathbb{Z}_{2^{\ell}}\!$) for small number of parties. We show this by giving a concrete protocol in the preprocessing model for the popular setting with three parties and one corruption. This is the first protocol for secure computation over rings that achieves active security with constant overhead.

C.~Carlet, P.~Charpin, V.~Zinoviev in 1998 defined the associated Boolean function $\gamma_F(a,b)$ in $2n$ variables for a given vectorial Boolean function $F$ from $\mathbb{F}_2^n$ to itself. It takes value~$1$ if $a\neq {\bf 0}$ and equation $F(x)+F(x+a)=b$ has solutions. This article defines the differentially equivalent functions as vectorial functions having equal associated Boolean functions. It is an open problem of great interest to describe the differential equivalence class for a given Almost Perfect Nonlinear (APN) function. We determined that each quadratic APN function $G$ in $n$ variables, $n\leq 6$, that is differentially equivalent to a given quadratic APN function $F$, can be represented as $G = F + A$, where $A$ is affine. For the APN Gold function $F$, we completely described all affine functions $A$ such that $F$ and $F+A$ are differentially equivalent. This result implies that the class of APN Gold functions up to EA-equivalence contains the first infinite family of functions, whose differential equivalence class is non-trivial.

We investigate the merits of altering the Garg, Gentry and Halevi (GGH13) graded encoding scheme to remove the presence of the ideal \(\langle g \rangle\). In particular, we show that we can alter the form of encodings so that effectively a new \(g_i\) is used for each source group \(\mathbb{G}_i\), while retaining correctness. This would appear to prevent all known attacks on indistinguishability obfuscation (IO) candidates instantiated using GGH13. However, when analysing security in simplified branching program and obfuscation security models, we present branching program (and thus IO) distinguishing attacks that do not use knowledge of \(\langle g \rangle\). This result opens a counterpoint with the work of Halevi (EPRINT 2015) which stated that the core computational hardness problem underpinning GGH13 is computing a basis of this ideal. Our attempts seem to suggest that there is a structural vulnerability in the way that GGH13 encodings are constructed that lies deeper than the presence of \(\langle g \rangle\).

Ring signatures, introduced by Rivest, Shamir and Tauman (ASIACRYPT 2001), allow to sign a message on behalf of a set of users while guaranteeing authenticity and anonymity. Groth and Kohlweiss (EUROCRYPT 2015) and Libert et al. (EUROCRYPT 2016) constructed schemes with signatures of size logarithmic in the number of users. An even shorter ring signature, of size independent from the number of users, was recently proposed by Malavolta and Schroder (ASIACRYPT 2017). However, all these short signatures are obtained relying on strong and controversial assumptions. Namely, the former schemes are both proven secure in the random oracle model while the later requires non-falsifiable assumptions. The most efficient construction under mild assumptions remains the construction of Chandran et al. (ICALP 2007) with a signature of size $\Theta(\sqrt{n})$, where $n$ is the number of users, and security is based on the Diffie-Hellman assumption in bilinear groups (the SXDH assumption in asymmetric bilinear groups). In this work we construct an asymptotically shorter ring signature from the hardness of the Diffie-Hellman assumption in bilinear groups. Each signature comprises $\Theta(\sqrt[3]{n})$ group elements, signing a message requires computing $\Theta(\sqrt[3]{n})$ exponentiations, and verifying a signature requires $\Theta(n^{2/3})$ pairing operations. To the best of our knowledge, this is the first ring signature based on bilinear groups with $o(\sqrt{n})$ signatures and sublinear verification complexity.

Iterative collision search procedures play a key role in developing combinatorial algorithms for the subset sum and learning parity with noise (LPN) problems. In both scenarios, the single-list pair-wise iterative collision search finds the most solutions and offers the best efficiency. However, due to its complex probabilistic structure, no rigorous analysis for it appears to be available to the best of our knowledge. As a result, theoretical works often resort to overly constrained and sub-optimal iterative collision search variants in exchange for analytic simplicity. In this paper, we present rigorous analysis for the single-list pair-wise iterative collision search method and its applications in subset sum and LPN. In the LPN literature, the method is known as the LF2 heuristic. Besides LF2, we also present rigorous analysis of other LPN solving heuristics and show that they work well when combined with LF2. Putting it together, we significantly narrow the gap between theoretical and heuristic algorithms for LPN.

We define and study zero-testable homomorphic encryption (ZTHE) -- a semantically secure, somewhat homomorphic encryption scheme equipped with a weak zero test that can identify trivial zeros. These are ciphertexts that result from homomorphically evaluating an arithmetic circuit computing the zero polynomial over the integers. This is a relaxation of the (strong) zero test provided by the notion of graded encodings, which identifies all encodings of zero. We show that ZTHE can suffice for powerful applications. Based on any ZTHE scheme that satisfies the additional properties of correctness on adversarial ciphertexts and multi-key homomorphism, we construct publicly verifiable non-interactive arguments for delegating computation. Such arguments were previously constructed from indistinguishability obfuscation or based on so-called knowledge assumptions. The arguments we construct are adaptively sound, based on an efficiently falsifiable assumption, and only make black-box use of the underlying cryptographic primitives. We also show that a ZTHE scheme that is sufficient for our application can be constructed based on an efficiently-falsifiable assumption over so-called "clean" graded encodings.

Structure-Preserving Signatures (SPSs) are an important tool for the design of modular cryptographic protocols. It has been proven that such schemes in the most efficient Type-3 bilinear group setting have a lower bound of 3-element signatures, which must include elements from both base groups, and a verification overhead of at least 2 Pairing-Product Equations (PPEs). Very recently, Ghadafi (ESORICS 2017) showed that by restricting the message space to the set of Diffie-Hellman pairs (which does not hinder applicability of the schemes), some of the existing lower bounds for the single message case can be circumvented. However, the case of signing multiple messages, which is required for many applications, was left as an open problem since the techniques used for signing single messages do not seem to lend themselves to the multi-message setting. In this work we investigate this setting and answer the question in the affirmative. We construct schemes that sign vectors of messages and which yield shorter signatures than optimal schemes for vectors of unilateral messages. More precisely, we construct 2 fully randomiazble schemes that sign vectors of Diffie-Hellman pairs yielding signatures consisting of only 2 elements regardless of the size of the vector signed. We also construct a unilateral scheme that signs a pair of messages yielding signatures consisting of 3 elements from the shorter base group. All of our schemes require a single PPE for verification (not counting the cost of verifying the well-formedness of the messages). Thus, all of our schemes compare favourably to all existing schemes with respect to signature size and verification overhead. Even when considering single messages, our first 2 schemes compare favourably to the best existing schemes in many aspects including the verification overhead and the key size.

This paper develops a cryptographic protocol for outsourcing arbitrary stateful computation among multiple clients to an untrusted server, while guaranteeing integrity of the data. The clients communicate only with the server and store only a short authenticator to ensure that the server does not cheat. Our contribution is two-fold. First, we extend the recent hash&prove scheme of Fiore et al. (CCS 2016) to stateful computations that support arbitrary updates by the untrusted server, in a way that can be verified by the clients. We use this scheme to generically instantiate authenticated data types. Second, we describe a protocol for multi-client verifiable computation based on an authenticated data type, and prove that it achieves a computational version of fork linearizability. This is the strongest guarantee that can be achieved in the setting where clients do not communicate directly; it ensures correctness and consistency of outputs seen by the clients individually.

In this paper we present the first proof of a shuffle for lattice-based cryptography which can be used to build a universally verifiable mix-net capable of mixing votes encrypted with a post-quantum algorithm, thus achieving long-term privacy. Universal verifiability is achieved by means of the publication of a non-interactive zero knowledge proof of a shuffle generated by each mix-node which can be verified by any observer. This published data guarantees long-term privacy since its security is based on perfectly hiding commitments and also on the hardness of solving the Ring Learning With Errors (RLWE) problem, that is widely believed to be quantum resistant.

The research on secure poker protocols without trusted intermediaries has a long history that dates back to modern cryptography's infancy. Two main challenges towards bringing it into real-life are enforcing the distribution of the rewards, and penalizing misbehaving/aborting parties. Using recent advances on cryptocurrencies and blockchain technologies, Andrychowicz et al. (IEEE S\&P 2014 and FC 2014 BITCOIN Workshop) were able to address those problems. Improving on these results, Kumaresan et al. (CCS 2015) and Bentov et al. (ASIACRYPT 2017) proposed specific purpose poker protocols that made significant progress towards meeting the real-world deployment requirements. However, their protocols still lack either efficiency or a formal security proof in a strong model. Specifically, the work of Kumaresan et al. relies on Bitcoin and simple contracts, but is not very efficient as it needs numerous interactions with the cryptocurrency network as well as a lot of collateral. Bentov et al. achieve further improvements by using stateful contracts and off-chain execution: they show a solution based on general multiparty computation that has a security proof in a strong model, but is also not very efficient. Alternatively, it proposes to use tailor-made poker protocols as a building block to improve the efficiency. However, a security proof is unfortunately still missing for the latter case: the security properties the tailor-made protocol would need to meet were not even specified, let alone proven to be met by a given protocol. Our solution closes this undesirable gap as it concurrently: (1) enforces the rewards' distribution; (2) enforces penalties on misbehaving parties; (3) has efficiency comparable to the tailor-made protocols; (4) has a security proof in a simulation-based model of security. Combining techniques from the above works, from tailor-made poker protocols and from efficient zero-knowledge proofs for shuffles, and performing optimizations, we obtain a solution that satisfies all four desired criteria and does not incur a big burden on the blockchain.

SPHINCS is a recently proposed stateless hash-based signature scheme and promising candidate for a post-quantum secure digital signature scheme. In this work we provide a comparison of the performance when instantiating SPHINCS with different cryptographic hash functions on both recent Intel and AMD platforms found in personal computers and the ARMv8-A platform which is prevalent in mobile phones. In particular, we provide a broad comparison of the performance of cryptographic hash functions utilizing the cryptographic extensions and vector instruction set extensions available on modern microprocessors. This comes with several new implementations optimized towards the specific use case of hash-based signature schemes. Further, we instantiate SPHINCS with these primitives and provide benchmarks for the costs of generating keys, signing messages and verifying signatures with SPHINCS on Intel Haswell, Intel Skylake, AMD Ryzen, ARM Cortex A57 and Cortex A72.

Masking provides a high level of resistance against side-channel analysis. However, in practice there are many possible pitfalls when masking schemes are applied, and implementation flaws are easily overlooked. Over the recent years, the formal verification of masked software implementations has made substantial progress. In contrast to software implementations, hardware implementations are inherently susceptible to glitches. Therefore, the same methods tailored for software implementations are not readily applicable. In this work, we introduce a method to formally verify the security of masked hardware implementations that takes glitches into account. Our approach does not require any intermediate modeling steps of the targeted implementation and is not bound to a certain leakage model. The verification is performed directly on the circuit’s netlist, and covers also higher-order and multivariate flaws. Therefore, a sound but conservative estimation of the Fourier coefficients of each gate in the netlist is calculated, which characterize statistical dependence of the gates on the inputs and thus allow to predict possible leakages. In contrast to existing practical evaluations, like t-tests, this formal verification approach makes security statements beyond specific measurement methods, the number of evaluated leakage traces, and the evaluated devices. Furthermore, flaws detected by the verifier are automatically localized. We have implemented our method on the basis of an SMT solver and demonstrate the suitability on a range of correctly and incorrectly protected circuits of different masking schemes and for different protection orders. Our verifier is efficient enough to prove the security of a full masked AES S-box, and of the Keccak S-box up to the third protection order.

Leakage of information between two processes sharing the same processor cache has been exploited in many novel approaches targeting various cryptographic algorithms. The software implementation of AES is an especially attractive target since it makes extensive use of cache-resident table lookups. We consider two attack scenarios where either the plaintext or ciphertext is known. We employ a multi-threaded spy process and ensure that each time slice provided to the victim (running AES) is small enough so that it makes a very limited number of table accesses. We design and implement a suite of algorithms to deduce the 128-bit AES key using as input the set of (unordered) cache line numbers captured by the spy threads in an access-driven cache-based side channel attack. Our algorithms are expressed using simple relational algebraic operations and run in under a minute. Above all, our attack is highly efficient - we demonstrate recovery of the full AES key given only about 6-7 blocks of plaintext or ciphertext (theoretically even a single block would suffice). This is a substantial improvement over previous cache-based side channel attacks that require between 100 and a million encryptions. Moreover, our attack supports varying cache hit/miss observation granularities, does not need frequent interruptions of the victim and will work even if the victim makes up to 60 cache accesses before being interrupted. Finally, we develop analytic models to estimate the number of encryptions/decryptions required as a function of access granularity and compare model results with those obtained from our experiments

Linear cryptanalysis of DES, proposed by Matsui in 1993, has had a seminal impact on symmetric-key cryptography, having seen massive research efforts over the past two decades. It has spawned many variants, including multidimensional and zero-correlation linear cryptanalysis. These variants can claim best attacks on several ciphers, including PRESENT, Serpent, and CLEFIA. For DES, none of these variants have improved upon Matsui's original linear cryptanalysis, which has been the best known-plaintext key-recovery attack on the cipher ever since. In a revisit, Junod concluded that when using $2^{43}$ known plaintexts, this attack has a complexity of $2^{41}$ DES evaluations. His analysis relies on the standard assumptions of right-key equivalence and wrong-key randomisation. In this paper, we first investigate the validity of these fundamental assumptions when applied to DES. For the right key, we observe that strong linear approximations of DES have more than just one dominant trail and, thus, that the right keys are in fact inequivalent with respect to linear correlation. We therefore develop a new right-key model using Gaussian mixtures for approximations with several dominant trails. For the wrong key, we observe that the correlation of a strong approximation after the partial decryption with a wrong key still shows much non-randomness. To remedy this, we propose a novel wrong-key model that expresses the wrong-key linear correlation using a version of DES with more rounds. We extend the two models to the general case of multiple approximations, propose a likelihood-ratio classifier based on this generalisation, and show that it performs better than the classical Bayesian classifier. On the practical side, we find that the distributions of right-key correlations for multiple linear approximations of DES exhibit exploitable asymmetries. In particular, not all sign combinations in the correlation values are possible. This results in our improved multiple linear attack on DES using 4 linear approximations at a time. The lowest computational complexity of $2^{38.86}$ DES evaluations is achieved when using $2^{42.78}$ known plaintexts. Alternatively, using $2^{41}$ plaintexts results in a computational complexity of $2^{49.75}$ DES evaluations. We perform practical experiments to confirm our model. To our knowledge, this is the best attack on DES.

We construct the most efficient known pairing-based NIZK shuffle argument. It consists of three subarguments that were carefully chosen to obtain optimal efficiency of the shuffle argument: * A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee, * A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zając, * A (simplified) consistency argument of Groth and Lu. We prove the knowledge-soundness of the first two subarguments in the generic bilinear group model, and the culpable soundness of the third subargument under a KerMDH assumption. This proves the soundness of the shuffle argument. We also discuss our partially optimized implementation that allows one to prove a shuffle of $100\,000$ ciphertexts in less than a minute and verify it in less than $1.5$ minutes.

Proofs of space (PoS) were suggested as more ecological and economical alternative to proofs of work, which are currently used in blockchain designs like Bitcoin. The existing PoS are based on rather sophisticated graph pebbling lower bounds. Much simpler and in several aspects more efficient schemes based on inverting random functions have been suggested, but they don't give meaningful security guarantees due to existing time-memory trade-offs. In particular, Hellman showed that any permutation over a domain of size $N$ can be inverted in time $T$ by an algorithm that is given $S$ bits of auxiliary information whenever $S\cdot T \approx N$ (e.g. $S=T\approx N^{1/2}$). For functions Hellman gives a weaker attack with $S^2\cdot T\approx N^2$ (e.g., $S=T \approx N^{2/3}$). To prove lower bounds, one considers an adversary who has access to an oracle $f:[N]\rightarrow [N]$ and can make $T$ oracle queries. The best known lower bound is $S\cdot T\in \Omega(N)$ and holds for random functions and permutations. We construct functions that provably require more time and/or space to invert. Specifically, for any constant $k$ we construct a function $[N]\rightarrow [N]$ that cannot be inverted unless $S^k\cdot T \in \Omega(N^k)$ (in particular, $S=T\approx N^{k/(k+1)}$). Our construction does not contradict Hellman's time-memory trade-off, because it cannot be efficiently evaluated in forward direction. However, its entire function table can be computed in time quasilinear in $N$, which is sufficient for the PoS application. Our simplest construction is built from a random function oracle $g:[N]\times[N]\rightarrow [N]$ and a random permutation oracle $f:[N]\rightarrow [N]$ and is defined as $h(x)=g(x,x')$ where $f(x)=\pi(f(x'))$ with $\pi$ being any involution without a fixed point, e.g. flipping all the bits. For this function we prove that any adversary who gets $S$ bits of auxiliary information, makes at most $T$ oracle queries, and inverts $h$ on an $\epsilon$ fraction of outputs must satisfy $S^2\cdot T\in \Omega(\epsilon^2N^2)$.

At CRYPTO 2015, Minaud and Seurin introduced and studied the iterated random permutation problem, which is to distinguish the $r$-th iterate of a random permutation from a random permutation. In this paper, we study the closely related iterated random function problem, and prove the first almost-tight bound in the adaptive setting. More specifically, we prove that the advantage to distinguish the $r$-th iterate of a random function from a random function using $q$ queries is bounded by $O(q^2r(\log r)^3/N)$, where $N$ is the size of the domain. In previous work, the best known bound was $O(q^2r^2/N)$, obtained as a direct result of interpreting the iterated random function problem as a special case of CBC-MAC based on a random function. For the iterated random function problem, the best known attack has an advantage of $\Omega(q^2r/N)$, showing that our security bound is tight up to a factor of $(\log r)^3$.