In this paper, we provide a security analysis of the Full-State Keyed Sponge (FKS), Full-State Keyed Duplex (FKD) and Keyak, one of the third-round CAESAR candidates, in the classic setting and the quantum model, respectively. In the classic setting, we present an universal forgery attack that can be implemented in $O(2^{c/2})$ queries, where $c$ is the capacity. In the quantum model, by utilizing the Simon's algorithm, we propose an efficient universal forgery attack to FKS, FKD and Keyak with complexity of $O(c)$. Moreover, we also propose an efficient key recovery attack that can be implemented in $O(c)$. Such attacks show that FKS, FKD and Keyak is completely broken in the quantum model.

Lattice-based cryptography is a highly potential candidate that protects against the threat of quantum attack. At Usenix Security 2016, Alkim, Ducas, Pöpplemann, and Schwabe proposed a post-quantum key exchange scheme called NewHope, based on a variant of lattice problem, the ring-learning-with-errors (RLWE) problem. In this work, we propose a high performance hardware architecture for NewHope. Our implementation requires 6,680 slices, 9,412 FFs, 18,756 LUTs, 8 DSPs and 14 BRAMs on Xilinx Zynq-7000 equipped with 28mm Artix-7 7020 FPGA. In our hardware design of NewHope key exchange, the three phases of key exchange costs 51.9, 78.6 and 21.1 microseconds, respectively. It achieves more than 4.8 times better in terms of area-time product comparing to previous results of hardware implementation of NewHope-Simple from Oder and Güneysu at Latincrypt 2017.

In this short report, we study the security of the new multivariate signature scheme HMFEv proposed at PQCrypto 2017.

We give a complete characterization of quantum attacks for finding a collision in a non- uniform random function whose outputs are drawn according to a distribution of min-entropy k. This can be viewed as showing generic security of hash functions under relaxed assumptions in contrast to the standard heuristic of assuming uniformly random outputs. It also has ap- plications in analyzing quantum security of the Fujisaki-Okamoto transformation [TU TCC16B]. In particular, our results close a gap in the lower bound left open in [TTU PQCrypto16]. Specifically, let $D$ be a min-entropy $k$ distribution on a set $Y$ of size $N$. Let $f: X\to Y$ be a function whose output $f(x)$ is drawn according to $D$ for each $x \in X$ independently. We show that $\Omega(2^{k/3})$ quantum queries are necessary to find a collision in $f$, improving the previous bound $\Omega(2^{k/9})$. In fact we show a stronger lower bound $2^{k/2}$ in some special case. For all cases, we also describe explicit quantum algorithms that find a collision with a number of queries matching the corresponding lower bounds.

Suppose $n$ parties have respective inputs $x_1, \ldots, x_n \in \mathbb{G}$, where $\mathbb{G}$ is a finite group. The parties would like to privately compute $x_1 x_2 \cdots x_n$ (where multiplication refers to the group operation in $\mathbb{G}$). There is a well-known secure protocol that works for any number of parties $n$ when $\mathbb{G}$ is abelian. In this note we consider private group-product protocols for non-abelian groups. We show that such protocols are possible for if and only if $n$ (the number of parties) is less than 4.

Bitcoin has not only attracted many users but also been considered as a technical breakthrough by academia. However, the expanding potential of Bitcoin is largely untapped due to its limited throughput. The Bitcoin community is now facing its biggest crisis in history as the community splits on how to increase the throughput. Among various proposals, Bitcoin Unlimited recently became the most popular candidate, as it allows miners to collectively decide the block size limit according to the real network capacity. However, the security of BU is heatedly debated and no consensus has been reached as the issue is discussed in different miner incentive models. In this paper, we systematically evaluate BU's security with three incentive models via testing the two major arguments of BU supporters: the block validity consensus is not necessary for BU's security; such consensus would emerge in BU out of economic incentives. Our results invalidate both arguments and therefore disprove BU's security claims. Our paper further contributes to the field by addressing the necessity of a prescribed block validity consensus for cryptocurrencies.

Leveled authentication allows resource-constrained IoT devices to be authenticated at different strength levels according to the particular types of communication. To achieve efficient leveled authentication, we propose a lightweight public key encryption scheme that can produce very short ciphertexts without sacrificing its security. The security of our scheme is based on the Learning With Secretly Scaled Errors in Dense Lattice (referred to as Compact-LWE) problem. We prove the hardness of Compact-LWE by reducing Learning With Errors (LWE) to Compact-LWE. However, unlike LWE, even if the closest vector problem (CVP) in lattices can be solved, Compact-LWE is still hard, due to the high density of lattices constructed from Compact-LWE samples and the relatively longer error vectors. By using a lattice-based attack tool, we verify that the attacks, which are successful on LWE instantly, cannot succeed on Compact-LWE, even for a small dimension parameter like $n=13$, hence allowing small dimensions for short ciphertexts. On the Contiki operating system for IoT, we have implemented our scheme, with which a leveled Needham-Schroeder-Lowe public key authentication protocol is implemented. On a small IoT device with 8MHZ MSP430 16-bit processor and 10KB RAM, our experiment shows that our scheme can complete 50 encryptions and 500 decryptions per second at a security level above 128 bits, with a public key of 2368 bits, generating 176-bit ciphertexts for 16-bit messages. With two small IoT devices communicating over IEEE 802.15.4 and 6LoWPAN, the total time of completing an authentication varies from 640ms (the 1st authentication level) to 8373ms (the 16th authentication level), in which the execution of our encryption scheme takes only a very small faction from 46ms to 445ms.

Decentralized ledger-based cryptocurrencies like Bitcoin present a way to construct payment systems without trusted banks. However, the anonymity of Bitcoin is fragile. Many altcoins and protocols are designed to improve Bitcoin on this issue, among which Zerocash is the first full-fledged anonymous ledger-based currency, using zero-knowledge proof, specifically zk-SNARK, to protect privacy. However, Zerocash suffers two problems: poor scalability and low efficiency. In this paper, we address the above issues by constructing a micropayment system in Zerocash called Z-Channel. First, we improve Zerocash to support multisignature and time lock functionalities, and prove that the reconstructed scheme is secure. Then we construct Z-Channel based on the improved Zerocash scheme. Our experiments demonstrate that Z-Channel significantly improves the scalability and reduces the confirmation time for Zerocash payments.

Edit distance is an important non-linear metric that has many applications ranging from matching patient genomes to text-based intrusion detection. Depends on the application, related string-comparison metrics, such as weighted edit distance, Needleman-Wunsch distance, longest common subsequences, and heaviest common subsequences, can usually fit better than the basic edit distance. When these metrics need to be calculated on sensitive input strings supplied by mutually distrustful parties, it is more desirable but also more challenging to compute them in privacy-preserving ways. In this paper, we propose efficient secure computation protocols for private edit distance as well as several generalized applications including weighted edit distance (with potentially content-dependent weights), longest common subsequence, and heaviest common subsequence. Our protocols run 20+ times faster and use an order-of-magnitude less bandwidth than their best previous counterparts. Along- side, we propose a garbling scheme that allows free arithmetic addition, free multiplication with constants, and low-cost comparison/minimum for inputs of restricted relative-differences. Moreover, the encodings (i.e. wire-labels) in our garbling scheme can be converted from and to encodings used by traditional binary circuit garbling schemes with light to moderate costs. Therefore, while being extremely efficient on certain kinds of computations, the new garbling scheme remains composable and capable of handling generic computational tasks.

We propose a novel cryptographic primitive called conditional blind signatures. Our primitive allows a user to request blind signatures on messages of her choice. The signer has a secret Boolean input which determines if the supplied signature is valid or not. The user should not be able to distinguish between valid and invalid signatures. A designated verifier, however, can tell which signatures verify correctly, and is in fact the only entity who can learn the secret input associated with the (unblinded) signed message. We instantiate our primitive as an extension of the Okamoto-Schnorr blind signature scheme and provide variations to fit different usage scenarios. Finally, we analyze and prove the security properties of the new scheme and explore potential applications

In this note, we will provide an information-theoretic framework for the random 3-bit sequence {111, 110, 101, 100, 011, 010, 001, 000} that demonstrates (by using Wigner’s inequality) a logical loophole in the Bell-CHSH inequality [1, 2, 3], as also has recently been found experimentally for triples measurements [4]. As a consequence of this, both classical and quantum regimes can share their bounds within the same environment, which shows that maximally entangled states used in cryptography secure systems can be critically subverted via EPR (Einstein-Podolsky-Rosen) paradox [5].

We propose SOFIA, the first MQ-based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh's transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM. Based on a detailed security analysis, we provide concrete parameters for SOFIA that achieve 128 bit post-quantum security. The result is SOFIA-4-128 with parameters that are carefully optimized to minimize signature size and maximize performance. SOFIA-4-128 comes with an implementation targeting recent Intel processors with the AVX2 vector-instruction set; the implementation is fully protected against timing attacks.

Outsourcing data to the cloud is becoming increasingly prevalent. To ensure data confidentiality, encrypting the data before outsourcing it is advised. While encryption protects the secrets in the data, it also prevents operations on the data. For example in a multi-user setting, data is often accessed via search, but encryption prevents search. Searchable encryption solves this dilemma. However, in a multi-user setting not all users may be allowed to access all data, requiring some means of access control. We address the question how searchable encryption and access control can be combined. Combining these technologies is required to achieve strong notions of confidentiality: if a ciphertext occurs as a search result, we learn something about the underlying document, even if access control does not let us access the document. This illustrates a need to link search and access control, so that search results presented to users only feature data the users are allowed to access. Our searchable encryption scheme with access control establishes that link.

Differential Fault Attack (DFA) is presently a very well known technique to evaluate security of a stream cipher. This considers that the stream cipher can be weakened by injection of the fault. In this paper we study DFA on three ciphers, namely Grain v1, Lizard and ACORN v3. We show that Grain v1 (an eStream cipher) can be attacked with injection of only 5 faults instead of 10 that has been reported in 2012. For the first time, we have mounted the fault attack on Lizard, a very recent design and show that one requires only 5 faults to obtain the state. ACORN v3 is a third round candidate of CAESAR and there is only one hard fault attack on an earlier version of this cipher. However, the `hard fault' model requires a lot more assumption than the generic DFA. In this paper, we mount a DFA on ACORN v3 that requires 9 faults to obtain the state. In case of Grain v1 and ACORN v3, we can obtain the secret key once the state is known. However, that is not immediate in case of Lizard. While we have used the basic framework of DFA that appears in literature quite frequently, specific tweaks have to be explored to mount the actual attacks that were not used earlier. To the best of our knowledge, these are the best known DFA on these three ciphers.

Protocols for Private Set Intersection (PSI) are important cryptographic primitives that perform joint operations on datasets in a privacy-preserving way. They allow two parties to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. Unfortunately, PSI implementations in the literature do not usually employ the best possible cryptographic implementation techniques. This results in protocols presenting computational and communication complexities that are prohibitive, particularly in the case when one of the participants is a low-powered device and there are bandwidth restrictions. This paper builds on modern cryptographic engineering techniques and proposes optimizations for a promising one-way PSI protocol based on public-key cryptography. For the case when one of the parties holds a set much smaller than the other (a realistic assumption in many scenarios) we show that our improvements and optimizations yield a protocol that outperforms the communication complexity and the run time of previous proposals by around one thousand times.

Outsourcing data storage to the cloud securely and retrieving the remote data in an efficient way is a very significant research topic, with high relevance to secure cloud deployment. With the ever growing security and privacy concerns, encrypting the data stored remotely is inevitable but using traditional encryption thwarts performing search operation on the encrypted data. Encrypted keyword search is a cryptographic setting, which offers search functionality and at the same time, ensures security and privacy of the remotely stored data. Searchable Symmetric Encryption (SSE) is a technique to securely outsource the data, which is encrypted using symmetric key primitives, while maintaining search functionality. While several solutions have been proposed to realize SSE over various data structures, the efficient solution using inverted index is due to Curtmola et.al. Hwang et.al. introduced a SSE scheme based on bitmaps in-order to reduce the index size. In this paper, we consider Searchable Symmetric Encryption (SSE) in the presence of a Semi-Honest-But-Curious Cloud Service Provider (SHBC-CSP). We have defined a new security notion for SSE in presence of SHBC-CSP, contrived two new SSE schemes and proved their security formally in the proposed security notion. Dynamic Verifiable Encrypted Keyword Search (DVSSE), is the first SSE scheme to the best of our knowledge, which is both dynamic and verifiable. We have implemented our schemes, compared their performance and complexity with existing schemes.

Cryptographic reductions typically aim to be tight by transforming an adversary A into an algorithm that uses essentially the same resources as A. In this work we initiate the study of memory efficiency in reductions. We argue that the amount of working memory used (relative to the initial adversary) is a relevant parameter in reductions, and that reductions that are inefficient with memory will sometimes yield less meaningful security guarantees. We then point to several common techniques in reductions that are memory-inefficient and give a toolbox for reducing memory usage. We review common cryptographic assumptions and their sensitivity to memory usage. Finally, we prove an impossibility result showing that reductions between some assumptions must unavoidably be either memory- or time-inefficient. This last result follows from a connection to data streaming algorithms for which unconditional memory lower bounds are known.

Security features of modern (SoC) FPAGs permit to protect the confidentiality of hard- and software IP when the devices are powered off as well as to validate the authenticity of IP when being loaded at startup. However, these approaches are insufficient since attackers with physical access can also perform attacks during runtime, demanding for additional security measures. In particular, RAM used by modern (SoC) FPGAs is under threat since RAM stores software IP as well as all kinds of other sensitive information during runtime. To solve this issue, we present an open-source framework for building transparent RAM encryption and authentication pipelines, suitable for both FPGAs and ASICs. The framework supports various ciphers and modes of operation as shown by our comprehensive evaluation on a Xilinx Zynq-7020 SoC. For encryption, the ciphers Prince and AES are used in the ECB, CBC and XTS mode. Additionally, the authenticated encryption cipher Ascon is used both standalone and within a TEC tree. Our results show that the data processing of our encryption pipeline is highly efficient with up to 94% utilization of the read bandwidth that is provided by the FPGA interface. Moreover, the use of a cryptographically strong primitive like Ascon yields highly practical results with 54% bandwidth utilization.

Characterization of all possible faults in a cryptosystem exploitable for fault attacks is a problem which is of both theoretical and practical interest for the cryptographic community. The complete knowledge of exploitable fault space is desirable while designing optimal countermeasures for any given crypto-implementation. In this paper, we address the exploitable fault characterization problem in the context of Differential Fault Analysis (DFA) attacks on block ciphers. The formidable size of the fault spaces demands an automated albeit fast mechanism for verifying each individual fault instance and neither the traditional, cipher-specific, manual DFA techniques nor the generic and au- tomated Algebraic Fault Attacks (AFA) [10] fulfill these criteria. Further, the diversified structures of different block ciphers suggest that such an automation should be equally applicable to any block cipher. This work presents an automated framework for DFA identification, fulfilling all aforemen- tioned criteria, which, instead of performing the attack just estimates the attack complexity for each individual fault instance. A generic and extendable data-mining assisted dynamic analysis frame- work capable of capturing a large class of DFA distinguishers is devised, along with a graph-based complexity analysis scheme. The framework significantly outperforms another recently proposed one [6], in terms of attack class coverage and automation effort. Experimental evaluation on AES and PRESENT establishes the effectiveness of the proposed framework in detecting most of the known DFAs, which eventually enables the characterization of the exploitable fault space.

We revisit the setting of coding for interactive communication, CIC, (initiated by Schulman 96') for non-threshold tampering functions. In a nutshell, in the (special case of) the communication complexity setting, Alice and Bob holding inputs $x,y$ wish to compute a function $g(x,y)$ on their inputs over the identity channel using an interactive protocol. The goal here is to minimize the total communication complexity (CC). A "code" for interactive communication is a compiler transforming any $\pi_0$ working in the communication complexity setting into a protocol $\pi$ evaluating the same function over any channel $f$ picked from a family $\mathcal{F}$. Here $f$ is a function modifying the entire communication transcript. The goal here is to minimize the code's \emph{rate}, which is the CC overhead $CC(\pi)/CC(\pi_0)$ incurred by the compiler. All previous work in coding for interactive communication considered error correction (that is, $g(x,y)$ must be recovered correctly with high probability), which puts a limit of corrupting up to a $1/4$ of the symbols (Braverman and Rao 11'). In this work, we initiate the study of CIC for non-threshold families. We first come up with a robustness notion both meaningful and achievable by CIC for interesting non-threshold families. As a test case, we consider $\mathcal{F}_{\text{bit}}$, where each bit of the codeword is modified independently of the other bits (and all bits can be modified). Our robustness notion is an enhanced form of error-detection, where the output of the protocol is distributed over $\{\bot,f(x,y)\}$, and the distribution does not depend on $x,y$. This definition can be viewed as enhancing error detection by non malleability (as in the setting of non-malleable codes introduced by Dzembowski et. al. 10'). We devise CIC for several interesting tampering families (including $\mathcal{F}_{\text{bit}}$). As a building block, we introduce the notion of MNMC (non malleable codes for multiple messages), which may be of independent interest.

In this paper we describe how to couple reputation systems with distributed consensus protocols to provide high-throughput highly-scalable consensus for large peer-to-peer networks of untrusted validators. We introduce reputation module Guru, which can be laid on top of various consensus protocols such as PBFT or HoneyBadger. It ranks nodes based on the outcomes of consensus rounds run by a small committee, and adaptively selects the committee based on the current reputation. The protocol can also take external reputation ranking as input. Guru can tolerate larger threshold of malicious nodes (up to slightly above 1/2) compared to the 1/3 limit of BFT consensus algorithms.

Private set intersection (PSI) is a cryptographic technique that is applicable to many privacy-sensitive scenarios. For decades, researchers have been focusing on improving its efficiency in both communication and computation. However, most of the existing solutions are inefficient for an unequal number of inputs, which is common in conventional client-server settings. In this paper, we analyze and optimize the efficiency of existing PSI protocols to support precomputation so that they can efficiently deal with such input sets. We transform four existing PSI protocols into the precomputation form such that in the setup phase the communication is linear only in the size of the larger input set, while in the online phase the communication is linear in the size of the smaller input set. We implement all four protocols and run experiments between two PCs and between a PC and a smartphone and give a systematic comparison of their performance. Our experiments show that a protocol based on securely evaluating a garbled AES circuit achieves the fastest setup time by several orders of magnitudes, and the fastest online time in the PC setting where AES-NI acceleration is available. In the mobile setting, the fastest online time is achieved by a protocol based on the Diffie-Hellman assumption.

This paper presents a series of Montgomery scalar multiplication algorithms on general short Weierstrass curves over odd characteristic fields, which need only 12 field multiplications plus 12 ~ 20 field additions per scalar bit using 8 ~ 10 field registers, thus significantly outperform the binary NAF method on average. Over binary fields, the Montgomery scalar multiplication algorithm which was presented at the first CHES workshop by L´opez and Dahab has been a favorite of ECC implementors, due to its nice properties such as high efficiency outperforming the binary NAF, natural SPA-resistance, generality coping with all ordinary curves and implementation easiness. Over odd characteristic fields, the new scalar multiplication algorithms are the first ones featuring all these properties. Building-blocks of our contribution are new efficient differential addition-and-doubling formulae and a novel conception of on-the-fly adaptive coordinates which softly represent points occurring during a scalar multiplication not only in accordance with the basepoint but also bits of the given scalar. Importantly, the new algorithms are equipped with built-in countermeasures against known side-channel attacks, while it is shown that previous Montgomery ladder algorithms with the randomized addressing countermeasure fail to thwart attacks exploiting address-dependent leakage.

The advent of cloud computing offers clients with the opportunity to outsource storage and processing of large volumes of shared data to third party service providers, thereby enhancing overall accessibility and operational productivity. However, security concerns arising from the threat of insider and external attacks often require the data to be stored in an encrypted manner. Secure and efficient keyword searching on such large volumes of encrypted data is an important and yet one of the most challenging services to realize in practice. Even more challenging is to incorporate fine-grained client-specific access control - a commonly encountered requirement in cloud applications - in such searchable encryption solutions. Existing searchable encryption schemes in literature tend to focus on the use of specialized data structures for efficiency, and are not explicitly designed to address controlled access scenarios. In this paper, we propose a novel controlled access searchable encryption (CASE) scheme. As the name suggests, CASE inherently embeds access control in its key management process, and scales efficiently with increase in the volume of encrypted data handled by the system. We provide a concrete construction for CASE that is privacy-preserving under well-known cryptographic assumptions. We then present a prototype implementation for our proposed construction on an ensemble of Artix 7 FPGAs. The architecture for our implementation exploits the massively parallel capabilities provided by hardware, especially in the design of data structures for efficient storage and retrieval of data. The implementation requires a total of 192 FPGAs to support a document collection comprising of 100 documents with a dictionary of 1000 keywords. In addition, the hardware implementation of CASE is found to outperform its software counterpart in terms of both search efficiency and scalability. To the best of our knowledge, this is the first hardware implementation of a searchable encryption scheme to be reported in the literature.

This paper presents software demonstrating that the 20-year-old NTRU cryptosystem is competitive with more recent lattice-based cryptosystems in terms of speed, key size, and ciphertext size. We present a slightly simplified version of textbook NTRU, select parameters for this encryption scheme that target the 128-bit post-quantum security level, construct a KEM that is CCA2-secure in the quantum random oracle model, and present highly optimized software targeting Intel CPUs with the AVX2 vector instruction set. This software takes only 307914 cycles for the generation of a keypair, 48646 for encapsulation, and 67338 for decapsulation. It is, to the best of our knowledge, the first NTRU software with full protection against timing attacks.

In the past few years secure messaging has become mainstream, with over a billion active users of end-to-end encryption protocols through apps such as WhatsApp, Signal, Facebook Messenger, Google Allo, Wire and many more. While these users' two-party communications now enjoy very strong security guarantees, it turns out that many of these apps provide, without notifying the users, a weaker property for group messaging: an adversary who compromises a single group member can intercept communications indefinitely. One reason for this discrepancy in security guarantees is that most existing group messaging protocols are fundamentally synchronous, and thus cannot be used in the asynchronous world of mobile communications. In this paper we show that this is not necessary, presenting a design for a tree-based group key exchange protocol in which no two parties ever need to be online at the same time, which we call Asynchronous Ratcheting Tree (ART). ART achieves strong security guarantees, in particular including post-compromise security. We give a computational security proof for ART's core design as well as a proof-of-concept implementation, showing that ART scales efficiently even to large groups. Our results show that strong security guarantees for group messaging are achievable even in the modern, asynchronous setting, without resorting to using inefficient point-to-point communications for large groups. By building on standard and well-studied constructions, our hope is that many existing solutions can be applied while still respecting the practical constraints of mobile devices.

The present report contains a proof of a linear lower bound for a typical three-party secure computation scheme of $n$ independent $AND$ functions. The goal is to prove some linear communication lower bound for a maximally broad definition of «typical». The article [DNPR] contains various communications lower bounds for unconditionally secure multiparty computation. In particular, it contains a linear lower bound for communication complexity of a regular parallel multiplication protocol using an ideal secret sharing scheme. These conditions mean that the protocol starts with the input being secret-shared with each share of each input field element being a field element, all combinations are used, and the output is shared in the same way as input. In this report a weaker property of the secret sharing scheme that still allows to prove a linear (w.r.t. the number of multiplications) lower bound on communication is presented. Namely, if we have two (out of three) sides and two options for each party's shares and three possible combinations decode as the same value, the remaining combination should also be a valid pair of shares and reveal the same value.

We initiate the study of message franking, recently introduced in Facebook’s end-to-end encrypted message system. It targets verifiable reporting of abusive messages to Facebook without compromising security guarantees. We capture the goals of message franking via a new cryptographic primitive: compactly committing authenticated encryption with associated data (AEAD). This is an AEAD scheme for which a small part of the ciphertext can be used as a cryptographic commitment to the message contents. Decryption provides, in addition to the message, a value that can be used to open the commitment. Security for franking mandates more than that required of traditional notions associated with commitment. Nevertheless, and despite the fact that AEAD schemes are in general not committing (compactly or otherwise), we prove that many in-use AEAD schemes can be used for message franking by using secret keys as openings. An implication of our results is the first proofs that several in-use symmetric encryption schemes are committing in the traditional sense. We also propose and analyze schemes that retain security even after openings are revealed to an adversary. One is a generalization of the scheme implicitly underlying Facebook’s message franking protocol, and another is a new construction that offers improved performance.

Memory encryption is used in many devices to protect memory content from attackers with physical access to a device. However, many current memory encryption schemes can be broken using Differential Power Analysis (DPA). In this work, we present MEAS---the first Memory Encryption and Authentication Scheme providing security against DPA attacks. The scheme combines ideas from fresh re-keying and authentication trees by storing encryption keys in a tree structure to thwart first-order DPA without the need for DPA-protected cryptographic primitives. Therefore, the design strictly limits the use of every key to encrypt at most two different plaintext values. MEAS prevents higher-order DPA without changes to the cipher implementation by using masking of the plaintext values. MEAS is applicable to all kinds of memory, e.g., NVM and RAM, and has memory overhead comparable to existing memory authentication techniques without DPA protection, e.g., 7.3% for a block size fitting standard disk sectors.

There is a serious problem with one of the assumptions made in the security proof of the SURF scheme. This problem turns out to be easy in the regime of parameters needed for the SURF scheme to work. We give afterwards the old version of the paper for the reader's convenience.

In this paper we tackle the practical challenges of searching encrypted multimodal data (i.e., data containing multiple media formats simultaneously), stored in public cloud servers, with reduced information leakage. To this end we propose MuSE, a Multimodal Searchable Encryption scheme that, by combining only standard cryptographic primitives and symmetric-key block ciphers, allows cloud-backed applications to dynamically store, update, and search multimodal datasets with privacy and efficiency guarantees. As searching encrypted data requires a tradeoff between privacy and efficiency, we also propose a variant of MuSE that resorts to partially homomorphic encryption to further reduce information leakage, but at the cost of additional computational overhead. Both schemes are formally proven secure and experimentally evaluated regarding performance and search precision. Experiments with realistic datasets show that our contributions achieve interesting levels of efficiency and privacy, making MuSE particularly suitable for practical application scenarios.

Leakage model plays a very important role in side channel attacks. An accurate leakage model greatly improves the efficiency of attacks. However, how to profile a "good enough" leakage model, or how to measure the accuracy of a leakage model, is seldom studied. Durvaux et al. proposed leakage certification tests to profile "good enough" leakage model for unmasked implementations. However, they left the leakage model profiling for protected implementations as an open problem. To solve this problem, we propose the first practical higher-order leakage model certification tests for masked implementations. First and second order attacks are performed on the simulations of serial and parallel implementations of a first-order fixed masking. A third-order attack is performed on another simulation of a second-order random masked implementation. The experimental results show that our new tests can profile the leakage models accurately.

Forward privacy is a trending security notion of dynamic searchable symmetric encryption (DSSE). It guarantees the privacy of newly added data against the server who has knowledge of previous queries. The notion was very recently formalized by Bost (CCS '16) independently, yet the definition given is imprecise to capture how forward secure a scheme is. We further the study of forward privacy by proposing a generalized definition parametrized by a set of updates and restrictions on them. We then construct two forward private DSSE schemes over labeled bipartite graphs, as a generalization of those supporting keyword search over text files. The first is a generic construction from any DSSE, and the other is a concrete construction from scratch. For the latter, we designed a novel data structure called cascaded triangles, in which traversals can be performed in parallel while updates only affect the local regions around the updated nodes. Besides neighbor queries, our schemes support flexible edge additions and intelligent node deletions: The server can delete all edges connected to a given node, without having the client specify all the edges.

In the past two decades, targeted online advertising has led to massive data collection, aggregation, and exchange. This infrastructure raises significant privacy concerns. While several prominent theories of data privacy have been proposed over the same period of time, these notions have limited application to advertising ecosystems. Differential privacy, the most robust of them, is inherently inapplicable to queries about particular individuals in the dataset. We therefore formulate a new definition of privacy for accessing private information about unknown individuals identified by some random token. Unlike most current privacy definitions, our's takes probabilistic prior information into account and is intended to reflect the use of aggregated web information for targeted advertising. We explain how our theory captures the natural expectation of privacy in the advertising setting and avoids the limitations of existing alternatives. However, although we can construct artificial databases which satisfy our notion of privacy together with reasonable utility, we do not have evidence that real world databases can be sanitized to preserve reasonable utility. In fact we offer real world evidence that adherence to our notion of privacy almost completely destroys utility. Our results suggest that a significant theoretical advance or a change in infrastructure is needed in order to obtain rigorous privacy guarantees in the digital advertising ecosystem.

Attrapadung (Eurocrypt 2014) proposed a generic framework called pair encoding to simplify the design and proof of security of CPA-secure predicate encryption (PE) in composite order groups. Later Attrapadung (Asiacrypt 2016) extended this idea in prime order groups. Yamada et al. (PKC 2011, PKC 2012) and Nandi et al. (ePrint Archive: 2015/457, AAECC 2017) proposed generic conversion frameworks to achieve CCA-secure PE from CPA-secure PE provided the encryption schemes have properties like delegation or verifiability. The delegation property is harder to achieve and verifiability based conversion degrades the decryption performance due to a large number of additional pairing evaluations. Blömer et al. (CT-RSA 2016) proposed a direct fully CCA-secure predicate encryption in composite order groups but it was less efficient as it needed a large number of pairing evaluations to check ciphertext consistency. As an alternative, Nandi et al. (ePrint Archive: 2015/955) proposed a direct conversion technique in composite order groups. We extend the direct conversion technique of Nandi et al. in the prime order groups on the CPA-secure PE construction by Attrapadung (Asiacrypt 2016) and prove our scheme to be CCA-secure in a quite different manner. Our first direct CCA-secure predicate encryption scheme requires exactly one additional ciphertext component and three additional units of pairing evaluation during decryption. The second construction requires exactly three additional ciphertext components but needs only one additional unit pairing evaluation during decryption. This is a significant improvement over conventional approach for CPA-to-CCA conversion in prime order groups.

Bitcoin and blockchain technologies have proven to be a phenomenal success. The underlying techniques hold huge promise to change the future of financial transactions, and eventually the way people and companies compute, collaborate, and interact. At the same time, the current Bitcoin-like proof-of-work based blockchain systems are facing many challenges. For example, a huge amount of energy/electricity is needed for maintaining the Bitcoin blockchain. We propose a new approach to constructing energy-efficient blockchain protocols. More concretely, we develop proof-of-stake based, scalable blockchain protocols in the open network setting. Our contributions are as follows: -- We for the first time identify a new security property called chain soundness, for proof-of-stake based protocols, which captures the intuition of ensuring new players to join the protocol execution securely. -- We for the first time formally investigate greedy strategies for proof-of-stake based protocols; via a greedy strategy, the protocol players may extend the best blockchain faster by attempting to extend multiple positions, instead of only the latest block, in the blockchain. We demonstrate a very useful upper bound of extending blockchain by greedy players, which enables us to give the first natural mimic of Bitcoin blockchain via proof-of-stake mechanism (without using any form of Byzantine fault tolerance). -- Our design is very simple, using only standard hash functions and unique digital signatures, which makes our design very appealing in practice. Our blockchain achieves important security properties including common prefix, chain quality, chain growth, and chain soundness, and is adaptively secure without assuming secure erasure.

The GMR-2 cipher is a type of stream cipher currently being used in some Inmarsat satellite phones. It has been proven that such a cipher can be cracked using only one single-frame (15 bytes) known keystream but with a moderate executing times. In this paper, we present a new thorough security analysis of the GMR-2 cipher. We first study the inverse properties of the cipher's components to reveal a bad one-way character of the cipher. By then introducing a new concept called ``valid key chain" according to the cipher's key schedule, we propose an unprecedented real-time inversion attack using a single-frame keystream. This attack comprises three phases: (1) table generation; (2) dynamic table look-up, filtration and combination; and (3) verification. Our analysis shows that, using the proposed attack, the size of the exhaustive search space for the 64-bit encryption key can be reduced to approximately $2^{13}$ when a single-frame keystream is available. Compared with previous known attacks, this inversion attack is much more efficient. Finally, the proposed attack is carried out on a 3.3-GHz PC, and the experimental results thus obtained demonstrate that the 64-bit encryption-key could be recovered in approximately 0.02 s on average.

Traditional utility metering is to be replaced by smart metering. Smart metering enables very fine grained utility consumption measurements. These fine grained measurements raise privacy concerns due to the lifestyle information which can be inferred from the precise time at which utilities were consumed. This paper outlines two privacy respecting time of use billing protocols for smart metering. These protocols protect the privacy of customers by never transmitting the fine grained utility readings outside of the customer’s home network. One protocol favours complexity on the trusted smart meter hardware while the other uses homorphic commitments to offload computation to a third device. Both protocols are designed to operate on top of existing cryptographic secure channel protocols in place on smart meters. Proof of concept software implementations of these protocols have been written and their suitability for real world application to low performance smart meter hardware is discussed. These protocols may also have application to other privacy conscious aggregation systems such as electronic voting.

An universal forgery attack means that for any given message $M$, an adversary without the key can forge the corresponding Message Authentication Code (MAC) tag $\tau$, and the pair $(M,\tau)$ can be verified with probability 1. For a idea MAC, the universal forgery attack should be infeasible to be implemented, whose complexity is believed to be min{$(2^n, 2^k)$} queries in the classic setting, where $n$ is the tag length and $k$ is the key length of the MAC, respectively. In this paper, we launch a general universal forgery attack to some blockcipher-based MACs and authenticated encryptions (AEs) using birthday attack, whose complexity is about $O(2^{n/2})$ queries in the classic setting. The attack shows that such MACs and AEs are totally insecure. However, this attack is not applicable in the quantum model, since no inclusion of period in the input messages is guaranteed. We also propose other generic universal forgery attacks using collision finding with structural input messages with complexity of $O(2^{n/2})$, by birthday paradox in the classic setting. Since our attacks are based on the collision finding with fixed but unknown differences (or period), such attacks can also be implemented with only $O(n)$ queries using \textit{Simon's} algorithm in the quantum model, which shows that such MACs and AEs are completely broken in the quantum model. Our attacks can be applied to CBC-MAC, XCBC, EMAC, OMAC, CMAC, PC-MAC, MT-MAC, PMAC, PMAC with parity, LightMAC and some of their variants. Moreover, such attacks are also applicable to the authenticated encryptions of the third round of the CAESAR candidates: CLOC, SILC, AEZ, COLM (including COPA and ELmD) and Deoxys.

In 1984, Goldreich, Goldwasser and Micali formalized the concept of pseudorandom functions and proposed a construction based on any length-doubling pseudorandom generator. Since then, pseudorandom functions have turned out to be an extremely influential abstraction, with applications ranging from message authentication to barriers in proving computational complexity lower bounds. In this tutorial we survey various incarnations of pseudorandom functions, giving self-contained proofs of key results from the literature. Our main focus is on feasibility results and constructions, as well as on limitations of (and induced by) pseudorandom functions. Along the way we point out some open questions that we believe to be within reach of current techniques.

LoRaWAN is a worldwide deployed IoT security protocol. We provide an extensive analysis of the current 1.0 version and show that the protocol suffers from several weaknesses allowing to perform attacks, including practical ones. These attacks lead to breaches in the network availability, data integrity, and data confidentiality. Based on the inner weaknesses of the protocol, these attacks do not lean on potential implementation or hardware bugs. Likewise they do not entail a physical access to the targeted equipment and are independent from the means used to protect secret parameters. Finally we propose practical recommendations aiming at thwarting the attacks, while at the same time being compliant with the specification, and keeping the interoperability between patched and unmodified equipments.

We provide efficient constructions for trace-and-revoke systems with public traceability in the black-box confirmation model. Our constructions achieve adaptive security, are based on standard assumptions and achieve significant efficiency gains compared to previous constructions. Our constructions rely on a generic transformation from inner product functional encryption (IPFE) schemes to trace-and-revoke systems. Our transformation requires the underlying IPFE scheme to only satisfy a very weak notion of security -- the attacker may only request a bounded number of random keys -- in contrast to the standard notion of security where she may request an unbounded number of arbitrarily chosen keys. We exploit the much weaker security model to provide a new construction for bounded collusion and random key IPFE from the learning with errors assumption (LWE), which enjoys improved efficiency compared to the scheme of Agrawal et al. [CRYPTO'16]. Together with IPFE schemes from Agrawal et al., we obtain trace and revoke from LWE, Decision Diffie Hellman and Decision Quadratic Residuosity.

This paper presents a lightweight blockcipher based authenticated encryption mode mainly focusing on minimizing the implementation size, i.e., hardware gates or working memory on software. The mode is called COFB, for COmbined FeedBack. COFB uses an $n$-bit blockcipher as the underlying primitive and relies on the use of a nonce for security. In addition to the state required for executing the underlying blockcipher, COFB needs only $n/2$ bits state as a mask. To date, for all existing constructions in which masks have been applied, at least $n$ bit masks have been used. Thus, we have shown the possibility of reducing the size of a mask without degrading the security level much. Moreover, it requires one blockcipher call to process one input block. We show COFB is provably secure up to $O(2^{n/2}/n)$ queries which are almost up to the standard birthday bound. We first present an idealized mode iCOFB along with the details of its provable security analysis. Next, we extend the construction to the practical mode COFB. We instantiate COFB with two 128-bit blockciphers, AES-128 and GIFT-128, and present their implementation results on FPGAs. We present two implementations, with and without CAESAR hardware API. When instantiated with AES-128 and implemented without CAESAR hardware API, COFB achieves only a few more than $1000$ Look-Up-Tables (LUTs) while maintaining almost the same level of provable security as standard AES-based AE, such as GCM. When instantiated with GIFT-128, COFB performs much better in hardware area. It consumes less than $1000$ LUTs while maintaining the same security level. However, when implemented with CAESAR hardware API, there are significant overheads both in the hardware area and throughput. COFB with AES-128 achieves about $1475$ LUTs. COFB with GIFT-128 achieves a few more than $1000$ LUTs. Though there are overheads, still both these figures show competitive implementation results compared to other authenticated encryption constructions.

Software-update mechanisms are critical to the security of modern systems, but their typically centralized design presents a lucrative and frequently attacked target. In this work, we propose CHAINIAC, a decentralized software-update framework that eliminates single points of failure, enforces transparency, and provides efficient verifiability of integrity and authenticity for software-release processes. Independent $\textit{witness servers}$ collectively verify conformance of software updates to release policies, $\textit{build verifiers}$ validate the source-to-binary correspondence, and a tamper-proof release log stores collectively signed updates, thus ensuring that no release is accepted by clients before being widely disclosed and validated. The release log embodies a $\textit{skipchain}$, a novel data structure, enabling arbitrarily out-of-date clients to efficiently validate updates and signing keys. Evaluation of our CHAINIAC prototype on reproducible Debian packages shows that the automated update process takes the average of 5 minutes per release for individual packages, and only 20 seconds for the aggregate timeline. We further evaluate the framework using real-world data from the PyPI package repository and show that it offers clients security comparable to verifying every single update themselves while consuming only one-fifth of the bandwidth and having a minimal computational overhead.

Lizard is a very recently proposed lightweight stream cipher that claims 60 bit security against distinguishing (related to state recovery) and 80 bit security against key recovery attack. This cipher has 121 bit state size. In this paper, we first note that using $\psi$ key stream bits one can recover $\psi$ unknown bits of the state when $\tau$ state bits are fixed to a specific pattern. This is made possible by guessing the remaining state bits. This helps us in mounting a TMDTO attack with preprocessing complexity $2^{67}$, and the maximum of Data, Time and Memory complexity during the online phase as $2^{54}$. The parameters in the online phase are significantly less than $2^{60}$.

Trust models are widely used in various computer science disciplines. The main purpose of a trust model is to continuously measure trustworthiness of a set of entities based on their behaviors. In this article, the novel notion of rational trust modeling is introduced by bridging trust management and game theory. Note that trust models/reputation systems have been used in game theory (e.g., repeated games) for a long time, however, game theory has not been utilized in the process of trust model construction; this is where the novelty of our approach comes from. In our proposed setting, the designer of a trust model assumes that the players who intend to utilize the model are rational/selfish, i.e., they decide to become trustworthy or untrustworthy based on the utility that they can gain. In other words, the players are incentivized (or penalized) by the model itself to act properly. The problem of trust management can be then approached by game theoretical analyses and solution concepts such as Nash equilibrium. Although rationality might be built-in in some existing trust models, we intend to formalize the notion of rational trust modeling from the designer's perspective. This approach will result in two fascinating outcomes. First of all, the designer of a trust model can incentivize trustworthiness in the first place by incorporating proper parameters into the trust function, which can be later utilized among selfish players in strategic trust-based interactions (e.g., e-commerce scenarios). Furthermore, using a rational trust model, we can prevent many well-known attacks on trust models. These two prominent properties also help us to predict behavior of the players in subsequent steps by game theoretical analyses.

We introduce SPHINCS-Simpira, which is a variant of the SPHINCS signature scheme with Simpira as a building block. SPHINCS was proposed by Bernstein et al. at EUROCRYPT 2015 as a hash-based signature scheme with post-quantum security. At ASIACRYPT 2016, Gueron and Mouha introduced the Simpira family of cryptographic permutations, which delivers high throughput on modern 64-bit processors by using only one building block: the AES round function. The Simpira family claims security against structural distinguishers with a complexity up to 2^128 using classical computers. In this document, we explain why the same claim can be made against quantum computers as well. Although Simpira follows a very conservative design strategy, our benchmarks show that SPHINCS-Simpira provides a 1.5x speed-up for key generation, a 1.4x speed-up for signing 59-byte messages, and a 2.0x speed-up for verifying 59-byte messages compared to the originally proposed SPHINCS-256.

In this paper we study space-scarce economy in massively replicated open blockchain systems. In these systems, such as Bitcoin, memory to hold a current state snapshot needed to validate transactions becomes the most scarce resource eventually. The issue is even more critical for blockchain systems used to store data~(votes, certificates, logs etc.). Uncontrolled state size growth could lead to security issues, such as denial-of-service attacks. Only technical solutions, not economic, have been proposed to tackle this problem to the moment. In contrast, we propose to add a new component to a transaction fee scheme based on how much additional space will be needed for new objects created in result of transaction processing and for how long they will live in the state. We provide three possible options towards implementing the new fee component, namely prepaid outputs, postpaid outputs and scheduled payments. We provide an analysis of the model with respect to all the three options. We show that the state growth could be bounded by a fee factor, miners are getting additional stable rewards and lost coins are being taken back into circulation eventually.

We provide a practical solution to performing cross-user machine learning through aggregation on a sensitive dataset distributed among privacy-concerned users. We focus on a scenario in which a single company wishes to obtain the distribution of aggregate features, while ensuring a high level of privacy for the users. We are interested in the case where users own devices that are not necessarily powerful or online at all times, like smartphones or web browsers. This premise makes general solutions, such as general multiparty computation (MPC), less applicable. We design an efficient special-purpose MPC protocol that outputs aggregate features to the company, while keeping online presence and computational complexity on the users’ side at a minimum. This basic protocol is secure against a majority of corrupt users, as long as they do not collude with the company. If they do, we still guarantee security, as long as the fraction of corrupt users is lower than a certain, tweakable, parameter. We propose different enhancements of this solution: one guaranteeing some degree of active security, and one that additionally ensures differential privacy. Finally, we report on the performance of our implementation on several realistic real-world use-cases across different devices.

The aim of a secret sharing scheme is to share a secret among a group of participants in such a way that while authorized subsets of participants are able to recover the secret, non-authorized subsets of them obtain no information about it. Multi-secret sharing is the natural generalization of secret sharing for situations in which the simultaneous protection of more than one secret is required. However, there exist some secret sharing schemes for which there are no secure or efficient multi-secret sharing counterparts. In this paper, using cellular automata, an efficient general method is proposed to reduce the problem of sharing k secrets (all assigned with the same access structure and needed to be reconstructed at once) under a certain secret sharing scheme (S), to the problem of sharing one secret under S such that none of the properties of S are violated. Using the proposed approach, any secret sharing scheme can be converted to a multi-secret sharing scheme. We provide examples to show the applicability of the proposed approach.

In this work, we describe an integer version of ring-LWE over the polynomial rings and prove that its hardness is equivalent to one of the polynomial ring-LWE. Moreover, we also present a public key cryptosystem using this variant of the polynomial ring-LWE.

RSA public keys are central to many cryptographic applications; hence their validity is of primary concern to the scrupulous cryptographer. The most relevant properties of an RSA public key $(n,e)$ depend on the factors of $n$: are they properly generated primes? are they large enough? is ee co-prime with $\phi(n)$? etc. But of course, it is out of question to reveal nn's factors. Generic non-interactive zero-knowledge (NIZK) proofs can be used to prove such properties. However, generic NIZK proofs are not practical at all. For some very specific properties, specialized proofs exist but such ad hoc proofs are naturally hard to generalize. This paper proposes a new type of general-purpose compact non-interactive proofs, called attestations, allowing the key generator to convince any third party that nn was properly generated. The proposed construction applies to any prime generation algorithm, and is provably secure in the Random Oracle Model. As a typical implementation instance, for a 138-bit security, verifying or generating an attestation requires $k=1024$ prime generations. For this instance, each processed message will later need to be signed or encrypted 14 times by the final users of the attested moduli.

The Trusted Platform Module (TPM) is an international standard for a security chip that can be used for the management of cryptographic keys and for remote attestation. The specification of the most recent TPM 2.0 interfaces for direct anonymous attestation unfortunately has a number of severe shortcomings. First of all, they do not allow for security proofs (indeed, the published proofs are incorrect). Second, they provide a Diffie-Hellman oracle w.r.t. the secret key of the TPM, weakening the security and preventing forward anonymity of attestations. Fixes to these problems have been proposed, but they create new issues: they enable a fraudulent TPM to encode information into an attestation signature, which could be used to break anonymity or to leak the secret key. Furthermore, all proposed ways to remove the Diffie-Hellman oracle either strongly limit the functionality of the TPM or would require significant changes to the TPM 2.0 interfaces. In this paper we provide a better specification of the TPM 2.0 interfaces that addresses these problems and requires only minimal changes to the current TPM 2.0 commands. We then show how to use the revised interfaces to build q-SDH- and LRSW-based anonymous attestation schemes, and prove their security. We finally discuss how to obtain other schemes addressing different use cases such as key-binding for U-Prove and e-cash.

We show how to construct secret-key functional encryption (SKFE) supporting unbounded polynomially many functional decryption keys, that is, collusion-resistant SKFE solely from SKFE supporting only one functional decryption key. The underlying single-key SKFE needs to be weakly succinct, that is, the size of its encryption circuit is sub-linear in the size of functions. We show we can transform any quasi-polynomially secure single-key weakly-succinct SKFE into quasi-polynomially secure collusion-resistant one. In addition, if the underlying single-key SKFE is sub-exponentially secure, then so does the resulting scheme in our construction. Some recent results show the power and usefulness of collusion-resistant SKFE. From our result, we see that succinct SKFE is also a powerful and useful primitive. In particular, by combining our result and the result by Kitagawa, Nishimaki, and Tanaka (ePrint 2017), we can obtain indistinguishability obfuscation from sub-exponentially secure weakly succinct SKFE that supports only a single functional decryption key.

In this paper, we study the performances and security of recent masking algorithms specialized to parallel implementations in a 32-bit embedded software platform, for the standard AES Rijndael and the bitslice cipher Fantomas. By exploiting the excellent features of these algorithms for bitslice implementations, we first extend the recent speed records of Goudarzi and Rivain (presented at Eurocrypt 2017) and report realistic timings for masked implementations with 32 shares. We then observe that the security level provided by such implementations is uneasy to quantify with current evaluation tools. We therefore propose a new ``multi-model" evaluation methodology which takes advantage of different (more or less abstract) security models introduced in the literature. This methodology allows us to both bound the security level of our implementations in a principled manner and to assess the risks of overstated security based on well understood parameters. Concretely, it leads us to conclude that these implementations withstand worst-case adversaries with >2^64 measurements under falsifiable assumptions.

Multivariate Public Key Cryptosystems (MPKCs) are often touted as future-proofing against Quantum Computers. In 2009, it was shown that hardware advances do not favor just ``traditional'' alternatives such as ECC and RSA, but also makes MPKCs faster and keeps them competitive at 80-bit security when properly implemented. These techniques became outdated due to emergence of new instruction sets and higher requirements on security. In this paper, we review how MPKC signatures changes from 2009 including new parameters (from a newer security level at 128-bit), crypto-safe implementations, and the impact of new AVX2and AESNI instructions. We also present new techniques on evaluating multivariate polynomials, multiplications of large finite fields by additive Fast Fourier Transforms, and constant time linear solvers.

Payment channels emerged recently as an efficient method for performing cheap \emph{micropayments} in cryptocurrencies. In contrast to traditional on-chain transactions, payment channels have the advantage that they allow for nearly unlimited number of transactions between parties without involving the blockchain. In this work, we introduce \emph{Perun}, an off-chain channel system that offers a new method for connecting channels that is more efficient than the existing technique of ``routing transactions'' over multiple channels. To this end, Perun introduces a technique called ``virtual payment channels'' that avoids involvement of the intermediary for each individual payment. In this paper we formally model and prove security of this technique in the case of one intermediary, who can be viewed as a ``payment hub'' that has direct channels with several parties. Our scheme works over any cryptocurrency that provides Turing-complete smart contracts. As a proof of concept, we implemented Perun's smart contracts in \emph{Ethereum}.

Rapid advances in quantum computing, together with the announcement by the National Institute of Standards and Technology (NIST) to define new standards for digital-signature, encryption, and key-establishment protocols, have created significant interest in post-quantum cryptographic schemes. This paper introduces Kyber (part of CRYSTALS -- Cryptographic Suite for Algebraic Lattices -- a package submitted to NIST post-quantum standardization effort in November 2017), a portfolio of post-quantum cryptographic primitives built around a key-encapsulation mechanism (KEM),based on hardness assumptions over module lattices. Our KEM is most naturally seen as a successor to the NewHope KEM (Usenix 2016). In particular, the key and ciphertext sizes of our new construction are about half the size, the KEM offers CCA instead of only passive security, the security is based on a more general (and flexible) lattice problem, and our optimized implementation results in essentially the same running time as the aforementioned scheme. We first introduce a CPA-secure public-key encryption scheme, apply a variant of the Fujisaki--Okamoto transform to create a CCA-secure KEM, and eventually construct, in a black-box manner, CCA-secure encryption, key exchange, and authenticated-key-exchange schemes. The security of our primitives is based on the hardness of Module-LWE in the classical and quantum random oracle models, and our concrete parameters conservatively target more than $128$ bits of post-quantum security.

This paper presents Dilithium, a lattice-based signature scheme that is part of the CRYSTALS (Cryptographic Suite for Algebraic Lattices) package that will be submitted to the NIST call for post-quantum standards. The scheme is designed to be simple to securely implement against side-channel attacks and to have comparable efficiency to the currently best lattice-based signature schemes. Our implementation results show that Dilithium is competitive with lattice schemes of the same security level and outperforms digital signature schemes based on other post-quantum assumptions.

Masking is a widespread countermeasure to protect implementations of block-ciphers against side-channel attacks. Several masking schemes have been proposed in the literature that rely on the efficient decomposition of the underlying s-box(es). We propose a generalized decomposition method for s-boxes that encompasses several previously proposed methods while providing new trade-offs. It allows to evaluate $n\lambda$-bit to $m\lambda$-bit s-boxes for any integers $n,m,\lambda \geq 1$ by seeing it a sequence of $m$ $n$-variate polynomials over $\mathbb{F_{2^\lambda}}$ and by trying to minimize the number of multiplications over $\mathbb{F_{2^\lambda}}$.

The modeling of trapdoor permutations has evolved over the years. Indeed, finding an appropriate abstraction that bridges between the existing candidate constructions and the needs of applications has proved to be challenging. In particular, the notions of certifying permutations (Bellare and Yung, 96), enhanced and doubly enhanced trapdoor permutations (Goldreich, 04, 08, 11, Goldreich and Rothblum, 13) were added to bridge the gap between the modeling of trapdoor permutations and needs of applications. We identify an additional gap in the current abstraction of trapdoor permutations: Previous works implicitly assumed that it is easy to recognize elements in the domain, as well as uniformly sample from it, even for illegitimate function indices. We demonstrate this gap by using the (Bitansky-Paneth-Wichs, 16) doubly-enhanced trapdoor permutation family to instantiate the Feige-Lapidot-Shamir (FLS) paradigm for constructing non-interactive zero-knowledge (NIZK) protocols, and show that the resulting proof system is unsound. To close the gap, we propose a general notion of certifiably injective doubly enhanced trapdoor functions (DECITDFs), which provides a way of certifying that a given key defines an injective function over the domain defined by it, even when that domain is not efficiently recognizable and sampleable. We show that DECITDFs suffice for instantiating the FLS paradigm; more generally, we argue that certifiable injectivity is needed whenever the generation process of the function is not trusted. We then show two very different ways to construct DECITDFs: One is via the traditional method of RSA/Rabin with the Bellare-Yung certification mechanism, and the other using indistinguishability obfuscation and injective pseudorandom generators. In particular the latter is the first candidate injective trapdoor function, from assumptions other than factoring, that suffices for the FLS paradigm. Finally we observe that a similar gap appears also in other paths proposed in the literature for instantiating the FLS paradigm, specifically via verifiable pseudorandom generators and verifiable pseudorandom functions. Closing the gap there can be done in similar ways to the ones proposed here.

This paper presents Gimli, a 384-bit permutation designed to achieve high security with high performance across a broad range of platforms, including 64-bit Intel/AMD server CPUs, 64-bit and 32-bit ARM smartphone CPUs, 32-bit ARM microcontrollers, 8-bit AVR microcontrollers, FPGAs, ASICs without side-channel protection, and ASICs with side-channel protection.

The wide number and variety of side-channel attacks against scalar multiplication algorithms makes their security evaluations complex, in particular in case of time constraints making exhaustive analyses impossible. In this paper, we present a systematic way to evaluate the security of such implementations against horizontal attacks. As horizontal attacks allow extracting most of the information in the leakage traces of scalar multiplications, they are suitable to avoid risks of overestimated security levels. For this purpose, we additionally propose to use linear regression in order to accurately characterize the leakage function and therefore approach worst-case security evaluations. We then show how to apply our tools in the contexts of ECDSA and ECDH implementations, and validate them against two targets: a Cortex-M4 and a Cortex-A8 micro-controllers.

We introduce a new variant $\MPLWE$ of the Learning With Errors problem ($\LWE$) making use of the Middle Product between polynomials modulo an integer~$q$. We exhibit a reduction from the Polynomial-$\LWE$ problem ($\PLWE$) parametrized by a polynomial~$f$, to $\MPLWE$ which is defined independently of any such~$f$. The reduction only requires~$f$ to be monic with constant coefficient coprime with~$q$. It incurs a noise growth proportional to the so-called expansion factor of~$f$. We also describe a public-key encryption scheme with quasi-optimal asymptotic efficiency (the bit-sizes of the keys and the run-times of all involved algorithms are quasi-linear in the security parameter), which is secure against chosen plaintext attacks under the $\MPLWE$ hardness assumption. The scheme is hence secure under the assumption that $\PLWE$ is hard for at least one polynomial~$f$ of degree~$n$ among a family of~$f$'s which is exponential in~$n$.

It is well known that constant-time implementations of modular exponentiation cannot use sliding windows. However, software libraries such as Libgcrypt, used by GnuPG, continue to use sliding windows. It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40\% of the bits, and 5-bit sliding windows leak only 33\% of the bits. In this paper we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion. We show for the first time that the direction of the encoding matters: the pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about exponent bits than for right-to-left. We show how to incorporate this additional information into the Heninger-Shacham algorithm for partial key reconstruction, and use it to obtain very efficient full key recovery for RSA-1024. We also provide strong evidence that the same attack works for RSA-2048 with only moderately more computation.

Cyclic logic encryption is a newly proposed circuit obfuscation technique in hardware security. It was claimed to be SAT-unresolvable because feedback cycles were intentionally inserted under keys into the encryption. We show in the paper that even though feedback cycles introduce extra difficulty for an attacker, they can still be overcome with SAT- based techniques. Specifically, we propose CycSAT Algorithms based on SAT with different acyclic conditions that can efficiently decrypt cyclic encryptions. Experimental results have shown that our CycSAT is efficient and effective to decrypt cyclic encryptions, and we need to develop new encryptions with better security properties.

Embedded IoT devices are often built upon large system on chip computing platforms running a significant stack of software. For certain computation-intensive operations such as signal processing or encryption and authentication of large data, chips with integrated FPGAs, FPGA SoCs, which provide high performance through configurable hardware designs, are used. In this contribution, we demonstrate how an FPGA hardware design can compromise the important secure boot process of the main software system to boot from a malicious network source instead of an authentic signed kernel image. This significant and new threat arises from the fact that the CPU and FPGA are connected to the same memory bus, so that FPGA hardware designs can interfere with secure boot routines on FPGA SoCs that are without any interruption on regular SoCs. An enabling factor is that integrated hardware designs are likely bought from external partners and there is a realistic lack of security review at the system integrators. This facilitates flaws or even unwanted functionality in such hardware designs. We perform a proof of concept on a Xilinx Zynq-7000 FPGA SoC, and the threat can be generalized to other devices. We also present as effective mitigation, an easy-to-review and re-usable wrapper module which prevents any unauthorized memory access by included hardware designs.

We describe a fast technique for performing the computationally heavy part of leakage assessment, in any statistical moment (or other property) of the leakage samples distributions. The proposed technique outperforms by orders of magnitude the approach presented at CHES 2015 by Schneider and Moradi. We can carry out evaluations that before took 90 CPU-days in 4 CPU-hours (about a 500-fold speed-up). As a bonus, we can work with exact arithmetic, we can apply kernel-based density estimation methods, we can employ arbitrary pre-processing functions such as absolute value to power traces, and we can perform information-theoretic leakage assessment. Our trick is simple and elegant, and lends itself to an easy and compact implementation. We fit a prototype implementation in about 130 lines of C code.

None of the existing rank estimation algorithms can scale to large cryptographic keys, such as 4096-bit (512 bytes) RSA keys. In this paper, we present the first solution to estimate the guessing entropy of arbitrarily large keys, based on mathematical bounds, resulting in the fastest and most scalable security evaluation tool to date. Our bounds can be computed within a fraction of a second, with no memory overhead, and provide a margin of only a few bits for a full 128-bit AES key.

In this article, we revisit the design strategy of PRESENT, leveraging all the advances provided by the research community in construction and cryptanalysis since its publication, to push the design up to its limits. We obtain an improved version, named GIFT, that provides a much increased efficiency in all domains (smaller and faster), while correcting the well-known weakness of PRESENT with regards to linear hulls. GIFT is a very simple and clean design that outperforms even SIMON or SKINNY for round-based implementations, making it one of the most energy efficient ciphers as of today. It reaches a point where almost the entire implementation area is taken by the storage and the Sboxes, where any cheaper choice of Sbox would lead to a very weak proposal. In essence, GIFT is composed of only Sbox and bit-wiring, but its natural bitslice data flow ensures excellent performances in all scenarios, from area-optimised hardware implementations to very fast software implementation on high-end platforms. We conducted a thorough analysis of our design with regards to state-of-the-art cryptanalysis, and we provide strong bounds with regards to differential/linear attacks.

Logic locking has emerged as a promising technique for protecting gate-level semiconductor intellectual property. However, recent work has shown that such gate-level locking techniques are vulnerable to Boolean satisfiability (SAT) attacks. In order to thwart such attacks, several SAT-resistant logic locking techniques have been proposed, which minimize the discriminating ability of input patterns to rule out incorrect keys. In this work, we show that such SAT-resistant logic locking techniques have their own set of unique vulnerabilities. In particular, we propose a novel ``bypass attack" that ensures the locked circuit works even when an incorrect key is applied. Such a technique makes it possible for an adversary to be oblivious to the type of SAT-resistant protection applied on the circuit, and still be able to restore the circuit to its correct functionality. We show that such a bypass attack is feasible on a wide range of benchmarks and SAT-resistant techniques, while incurring minimal run-time and area/delay overhead. Binary decision diagrams (BDDs) are utilized to analyze the proposed bypass attack and assess tradeoffs in security vs overhead of various countermeasures.

One of the most important tools for assessing hardness assumptions in cryptography is the Generic Group Model (GGM). Over the past two decades, numerous assumptions have been analyzed within this model. While a proof in the GGM can certainly provide some measure of confidence in an assumption, its scope is rather limited since it does not capture group-specific algorithms that make use of the representation of the group. To overcome this limitation, we propose the Algebraic Group Model (AGM), a model that lies in between the standard model and the GGM. It is the first restricted model of computation covering group-specific algorithms yet allowing to derive simple and meaningful security statements. We show that several important assumptions, among them the Computational Diffie-Hellman, the Strong Diffie-Hellman, and the interactive LRSW assumptions, are equivalent to the Discrete Logarithm (DLog) assumption in the AGM. On the more practical side, we prove tight security reductions for two important schemes in the AGM to DLog or a variant thereof: the BLS signature scheme and Groth's zero-knowledge SNARK (Eurocrypt '16), which is the most efficient SNARK for which only a proof in the GGM was known. Moreover, in combination with known lower bounds on the Discrete Logarithm assumption in the GGM, our results can be used to derive lower bounds for all the above-mentioned results in the GGM.

To simplify the certificate management procedures, Shamir introduced the concept of identity-based cryptography (IBC). However, the key escrow problem is inherent in IBC. To get rid of it, Al-Riyami and Paterson introduced in 2003 the notion of certificateless cryptography (CLC). However, if a cryptosystem is not perfectly implemented, adversaries would be able to obtain part of the system's secret state via side-channel attacks, and thus may break the system. This is not considered in the security model of traditional cryptographic primitives. Leakage-resilient cryptography was then proposed to prevent adversaries from doing so. There are fruitful works on leakage-resilient encryption schemes, while there are not many on signature schemes in the leakage setting. In this work, we review the folklore generic constructions of identity-based signature and certificateless signature, and show that if the underlying primitives are leakage-resilient, so are the resulting identity-based signature scheme and certificateless signature scheme. The leakage rate follows the minimum one of the underlying primitives. We also show some instantiations of these generic constructions.

In modern computing environments, hardware resources are commonly shared, and parallel computation is widely used. Parallel tasks can cause privacy and security problems if proper isolation is not enforced. Intel proposed SGX to create a trusted execution environment within the processor. SGX relies on the hardware, and claims runtime protection even if the OS and other software components are malicious. However, SGX disregards side-channel attacks. We introduce a powerful cache side-channel attack that provides system adversaries a high resolution channel. Our attack tool named CacheZoom is able to virtually track all memory accesses of SGX enclaves with high spatial and temporal precision. As proof of concept, we demonstrate AES key recovery attacks on commonly used implementations including those that were believed to be resistant in previous scenarios. Our results show that SGX cannot protect critical data sensitive computations, and efficient AES key recovery is possible in a practical environment. In contrast to previous works which require hundreds of measurements, this is the first cache side-channel attack on a real system that can recover AES keys with a minimal number of measurements. We can successfully recover AES keys from T-Table based implementations with as few as ten measurements.

We study the complexity of securely evaluating an arithmetic circuit over a finite field $F$ in the setting of secure two-party computation with semi-honest adversaries. In all existing protocols, the number of arithmetic operations per multiplication gate grows either linearly with $\log |F|$ or polylogarithmically with the security parameter. We present the first protocol that only makes a *constant* (amortized) number of field operations per gate. The protocol uses the underlying field $F$ as a black box, and its security is based on arithmetic analogues of well-studied cryptographic assumptions. Our protocol is particularly appealing in the special case of securely evaluating a ``vector-OLE'' function of the form $\vec{a}x+\vec{b}$, where $x\in F$ is the input of one party and $\vec{a},\vec{b}\in F^w$ are the inputs of the other party. In this case, which is motivated by natural applications, our protocol can achieve an asymptotic rate of $1/3$ (i.e., the communication is dominated by sending roughly $3w$ elements of $F$). Our implementation of this protocol suggests that it outperforms competing approaches even for relatively small fields $F$ and over fast networks. Our technical approach employs two new ingredients that may be of independent interest. First, we present a general way to combine any linear code that has a fast encoder and a cryptographic (``LPN-style'') pseudorandomness property with another linear code that supports fast encoding and *erasure-decoding*, obtaining a code that inherits both the pseudorandomness feature of the former code and the efficiency features of the latter code. Second, we employ local *arithmetic* pseudo-random generators, proposing arithmetic generalizations of boolean candidates that resist all known attacks.

The existing (election) voting systems, e.g., representative democracy, have many limitations and often fail to serve the best interest of the people in a collective decision-making process. To address this issue, the concept of liquid democracy has been emerging as an alternative decision-making model to make better use of ``the wisdom of crowds''. However, there is no known cryptographically secure e-voting implementation that supports liquid democracy. In this work, we propose a new voting concept called \emph{statement voting}, which can be viewed as a natural extension of the conventional voting approaches. In the statement voting, instead of defining a concrete election candidate, each voter can define a statement in his/her ballot but leave the vote ``undefined'' during the voting phase. During the tally phase, the (conditional) actions expressed in the statement will be carried out to determine the final vote. We initiate the study of statement voting under the Universal Composability (UC) framework, and propose several construction frameworks together with their instantiations. As an application, we show how statement voting can be used to realize a UC-secure liquid democracy voting system. We remark that our statement voting can be extended to enable more complex voting and generic ledger-based non-interactive multi-party computation. We believe that the statement voting concept opens a door for constructing a new class of e-voting schemes.

Selecting parameters in lattice-based cryptography is a challenging task, which is essentially accomplished using one of two approaches. The first (very common) approach is to derive parameters assuming that the desired security level is equivalent to the bit hardness of the underlying lattice problem, ignoring the gap implied by available security reductions. The second (barely used) approach takes the gap and thus the security reduction into account. In this work, we investigate how efficient lattice-based schemes are if they respect existing security reductions. Thus, we present a framework to systematically select parameters for any lattice-based scheme using either approaches. We apply our methodology to the schemes by Lindner and Peikert (LP), by El Bansarkhani (LARA), and by Ducas et al. (BLISS). We analyze their security reductions and derive a gap of 2, 3, and 63 bits, respectively. We show how parameters impact the schemes' efficiency when involving these gaps.

Recently, a new template attack on the DES key scheduling was demonstrated that allows recovery of a sufficiently large portion of the DES key of a widely deployed certified smart card chip using a single EM (electromagnetic) trace during the Exploitation Phase. Firstly, in this paper we show how the results can be improved upon when combining them with the analysis of another leakage channel, the total Hamming distance. Remaining rest entropies as low as approx 13 bits have been found for some single-trace attacks, meaning that effectively 42 bits of a single-key DES were recovered in a single trace. The nature of single-trace attacks has it that conventional software countermeasures are rendered useless by this attack, and thus the only remaining remedy is a hardware redesign. Secondly, various brute-force search strategies are compared with each other and an extensive analysis of the statistics of the rest entropy is presented. The analysis is also extended to two-key TDES. Moreover, the amount of brute-force effort can be drastically reduced when having more than one trace available for the attack. Already as few as N=8 traces during the Exploitation Phase bring about a reduction of the average brute-force effort of the order of 10 bits for single DES, and 22 bits for two-key TDES. For N approx 100 we achieve an average brute-force effort of less than 50 bits for two-key TDES. Further analysis reveals that this attack is not equally strong for all DES keys, but that quite a number of weaker DES keys exist where the attack is much stronger. Naturally, any assessment of the severity of this attack will have to be made based on the weakest keys. [This last part constitutes an update to a previous version of this paper.]

With the advancement in computing, sensing, and vehicle electronics, autonomous vehicles are being realized. For autonomous driving, environment perception sensors such as radars, lidars, and vision sensors play core roles as the eyes of a vehicle; therefore, their reliability cannot be compromised. In this work, we present a spoofing by relaying attack, which can not only induce illusions in the lidar output but can also cause the illusions to appear closer than the location of a spoofing device. In a recent work, the former attack is shown to be effective, but the latter one was never shown. Additionally, we present a novel saturation attack against lidars, which can completely incapacitate a lidar from sensing a certain direction. The effectiveness of both the approaches is experimentally verified against Velodyne's VLP-16.

We present a reduction from the module learning with errors problem (MLWE) in dimension \(d\) and with modulus \(q\) to the ring learning with errors problem (RLWE) with modulus \(q^{d}\). Our reduction increases the LWE error rate \(\alpha\) by a factor of \( n^{c+1/2} \cdot \sqrt{d} \) for ring dimension \(n\), module rank \(d\) and any constant \(c>0\) in the case of power-of-two cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomial-time equivalent. As a corollary, we obtain that the RLWE instance described above is equivalent to solving lattice problems on module lattices. We also present a self reduction for power-of-two cyclotomic RLWE that reduces the ring dimension \(n\) by a power-of-two factor \(2^i\), while increasing the modulus by a power of \(2^i\) and the error rate by a factor of \( 2^{i\cdot (1-c)} \cdot n^{c+1/2} \) for any constant \(c>0\). Our results suggest that when discussing hardness to drop the RLWE/MLWE distinction in favour of distinguishing problems by the module rank required to solve them.

A standard method to protect data and secrets is to apply threshold cryptography in the form of secret sharing. This is motivated by the acceptance that adversaries will compromise systems at some point; and hence using threshold cryptography provides a defence in depth. The existence of such powerful adversaries has also motivated the introduction of game theoretic techniques into the analysis of systems, e.g. via the FlipIt game of van Dijk et al. This work further analyses the case of FlipIt when used with multiple resources, dubbed FlipThem in prior papers. We examine two key extensions of the FlipThem game to more realistic scenarios; namely separate costs and strategies on each resource, and a learning approach obtained using so-called fictitious play in which players do not know about opponent costs, or assume rationality.

Is it possible that a block cipher apparently immune to classical differential cryptanalysis can be attacked considering a different operation on the message space? Recently Calderini and Sala showed how to effectively compute alternative operations on a vector space which can serve as message space for a block cipher such that the resulting structure is still a vector space. The latter were used to mount a linearisation attack against a toy cipher. Here we investigate the possibility to design a block cipher which appears to be secure w.r.t. classical differential cryptanalysis, but weaker with respect to our attack which make use of alternative operations. Furthermore we compare the success probabilities of a distinguishing attack.

In recent years several papers have appeared investigating the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. However, with a notable exception by Petit et al. in 2016, all numerous papers have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach for the prime-field case. Our proposal outperforms both the original Semaev's method and Petit et al. specialized algorithm. The improvement is reached by reducing the necessary Groebner basis computations to only one basis calculation.

Protecting cryptographic implementations against side-channel attacks is a must to prevent leakage of processed secrets. As a cell-level countermeasure, so called DPA-resistant logic styles have been proposed to prevent a data-dependent power consumption. As most of the DPA-resistant logic is based on dual-rails, properly implementing them is a challenging task on FPGAs which is due to their fixed architecture and missing freedom in the design tools. While previous works show a significant security gain when using such logic on FPGAs, we demonstrate this only holds for power-analysis. In contrast, our attack using high-resolution electromagnetic analysis is able to exploit local characteristics of the placement and routing such that only a marginal security gain remains, therefore creating a severe threat. To further analyze the properties of both attack and implementation, we develop a custom placer to improve the default placement of the analyzed AES S-box. Different cost functions for the placement are tested and evaluated w.r.t. the resulting side-channel resistance on a Spartan-6 FPGA. As a result, we are able to more than double the resistance of the design compared to cases not benefiting from the custom placement.

Digital signatures constructed solely from hash functions offer competitive signature sizes and fast signing and verifying times. Moreover, the security of hash functions against a quantum adversary is believed to be well understood. This means that hash-based signatures are strong candidates for standard use in a post-quantum world. The Leighton-Micali signature scheme (LMS) is one such scheme being considered for standardization. However all systematic analyses of LMS have only considered a classical adversary. In this work we close this gap by showing a proof of the security of LMS in the quantum random-oracle model. Our results match the bounds imposed by Grover's search algorithm within a constant factor, and remain tight in the multi-user setting.

Practical hardness results are necessary to select parameters for cryptographic schemes. Cryptographic challenges proved to be useful for determining the practical hardness of computational problems that are used to build public-key cryptography. However, several of these problems have the drawback that it is not known how to create a challenge for them without knowing the solutions. Hence, for these problems the creators of the challenges are excluded from participating. In this work, we present a method to create cryptographic challenges without excluding anyone from participating. This method is based on secure multi-party computation (MPC). We demonstrate that the MPC-based approach is indeed feasible by using it to build a challenge for the learning with errors (LWE) problem. The LWE problem is one of the most important problems in lattice-based cryptography. The security of many cryptographic schemes that have been proposed in the last decade is directly based on it. We identify parameters for LWE instances that provide the appropriate hardness level for a challenge while representing instances used to instantiate encryption schemes as close as possible. The LWE challenge is designed to determine the practical hardness of LWE, to gain an overview of the best known LWE solvers, and to motivate additional research effort in this direction.

A Unlinkable Sanitizable Signature scheme (USS) allows a sanitizer to modify some parts of a signed message such that nobody can link the modified signature to the original one. A Verifiable Ring Signature scheme (VRS) allows the users to sign messages anonymously within a group such that a user can prove a posteriori to a verifier that he is the signer of a given message. In this paper, we first revisit the notion of VRS: we improve the proof capabilities of the users, we give a complete security model for VRS and we give an efficient and secure scheme called EVeR. Our main contribution is GUSS , a generic USS based on a VRS scheme and an unforgeable signature scheme. We show that GUSS instanciated with EVeR and the Schnorr's signature is twice as efficient as the best USS scheme of the literature. Moreover, we propose a stronger definition of accountability: a USS is accountable when the signer can prove whether a signature is sanitized. We formally define the notion of strong accontability when the sanitizer can also prove the origin of a signature. We show that the notion of strong accountability is important in practice. Finally, we prove the security properties of GUSS (including the strong accountability) and EVeR under the Decisional Diffie-Hellman assumption in the random oracle model.

The Fujisaki-Okamoto (FO) transformation (CRYPTO 1999 and Journal of Cryptology 2013) turns any weakly secure public-key encryption scheme into a strongly (i.e., IND-CCA) secure one in the random oracle model. Unfortunately, the FO analysis suffers from several drawbacks, such as a non-tight security reduction, and the need for a perfectly correct scheme. While several alternatives to the FO transformation have been proposed, they have stronger requirements, or do not obtain all desired properties. In this work, we provide a fine-grained and modular toolkit of transformations for turning weakly secure into strongly secure public-key encryption schemes. All of our transformations are robust against schemes with correctness errors, and their combination leads to several tradeoffs among tightness of the reduction, efficiency, and the required security level of the used encryption scheme. For instance, one variant of the FO transformation constructs an IND-CCA secure scheme from an IND-CPA secure one with a tight reduction and very small efficiency overhead. Another variant assumes only an OW-CPA secure scheme, but leads to an IND-CCA secure scheme with larger ciphertexts. We note that we also analyze our transformations in the quantum random oracle model, which yields security guarantees in a post-quantum setting.

A cryptanalytic technique known as time-memory tradeoff (TMTO) was proposed by Hellman for finding the secret key of a block cipher. This technique allows sharing the effort of key search between the two extremes of exhaustively enumerating all keys versus listing all possible ciphertext mappings produced by a given plaintext (i.e. table lookups). The TMTO technique has also been used as an effective cryptanalytic approach for password hashing schemes (PHS). Increasing threat of password leakage from compromised password hashes demands a resource consuming algorithm to prevent the precomputation of the password hashes. A class of password hashing designs provide such a defense against TMTO attack by ensuring that any reduction in the memory leads to exponential increase in runtime. These are called \textit{Memory hard} designs. However, it is generally difficult to evaluate the ``memory hardness" of a given PHS design.\\ In this work, we present a simple technique to analyze TMTO for any password hashing schemes which can be represented as a directed acyclic graph (DAG). The nodes of the DAG correspond to the storage required by the algorithm and the edges correspond to the flow of the execution. Our proposed technique provides expected run-times at varied levels of available storage for the DAG. Although our technique is generic, we show its efficacy by applying it on three designs from the ``Password Hashing Competition" (PHC) - Argon2i (the PHC winner), Catena and Rig. Our analysis shows that Argon2i fails to maintain the claimed memory hardness. In a recent work Corrigan-Gibbs et al. indeed showed an attack highlighting the weak memory hardening of Argon2i. We also analyze these PHS for performance under various settings of time and memory complexities.

Recent efficient constructions of zero-knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs), require a setup phase in which a common-reference string (CRS) with a certain structure is generated. This CRS is sometimes referred to as the public parameters of the system, and is used for constructing and verifying proofs. A drawback of these constructions is that whomever runs the setup phase subsequently possesses trapdoor information enabling them to produce fraudulent pseudoproofs. Building on a work of Ben-Sasson, Chiesa, Green, Tromer and Virza [BCGTV15], we construct a multi-party protocol for generating the CRS of the Pinocchio zk-SNARK [PHGR16], such that as long as at least one participating party is not malicious, no party can later construct fraudulent proofs except with negligible probability. The protocol also provides a strong zero-knowledge guarantee even in the case that all participants are malicious. This method has been used in practice to generate the required CRS for the Zcash cryptocurrency blockchain.

In this paper, we report on our implementation of a lattice-based Key-Policy Attribute-Based Encryption (KP-ABE) scheme, which uses short secret keys. The particular KP-ABE scheme can be used directly for Attribute-Based Access Control (ABAC) applications, as well as a building block in more involved applications and cryptographic schemes such as audit log encryption, targeted broadcast encryption, functional encryption, and program obfuscation. We adapt a recently proposed KP-ABE scheme [1] based on the Learning With Errors (LWE) problem to a more efficient scheme based on the Ring Learning With Errors (RLWE) problem, and demonstrate an implementation that can be used in practical applications. Our state-of-the-art implementation on graphics processing units (GPUs) shows that the homomorphic public key and ciphertext evaluation operations, which dominate the execution time of the KP-ABE scheme, can be performed in a reasonably short amount of time. Our practicality results also hold when scaled to a relatively large number of attributes. To the best of our knowledge, this is the first KP-ABE implementation that supports both ciphertext and public key homomorphism and the only experimental practicality results reported in the literature.

Area minimization is one of the main efficiency criterion for lightweight encryption primitives. While reducing the implementation data path is a natural strategy for achieving this goal, Substitution-Permutation Network (SPN) ciphers are usually hard to implement in a bit-serial way (1-bit data path). More generally, this is hard for any data path smaller than its Sbox size, since many scan flip-flops would be required for storage, which are more area-expensive than regular flip-flops. In this article, we propose the first strategy to obtain extremely small bit-serial ASIC implementations of SPN primitives. Our technique, which we call bit-sliding, is generic and offers many new interesting implementation trade-offs. It manages to minimize the area by reducing the data path to a single bit, while avoiding the use of many scan flip-flops. Following this general architecture, we could obtain the first bit-serial and the smallest implementation of AES-128 to date (1563 GE for encryption only, and 1744 GE for encryption and decryption with IBM 130nm standard-cell library), greatly improving over the smallest known implementations (about 30% decrease), making AES-128 competitive to many ciphers specifically designed for lightweight cryptography. To exhibit the generality of our strategy, we also applied it to the PRESENT and SKINNY block ciphers, again offering the smallest implementations of these ciphers thus far, reaching an area as low as 1054 GE for a 64-bit block 128-bit key cipher. It is also to be noted that our bit-sliding seems to obtain very good power consumption figures, which makes this implementation strategy a good candidate for passive RFID tags.

While succinct non-interactive zero-knowledge arguments of knowledge (zk-SNARKs) are widely studied, the question of what happens when the CRS has been subverted has received little attention. In ASIACRYPT 2016, Bellare, Fuchsbauer and Scafuro showed the first negative and positive results in this direction, proving also that it is impossible to achieve subversion soundness and (even non-subversion) zero knowledge at the same time. On the positive side, they constructed an involved sound and subversion zero-knowledge argument system for NP. We show that Groth's zk-SNARK for \textsc{Circuit-SAT} from EUROCRYPT 2016 can be made computationally knowledge-sound and perfectly composable Sub-ZK with minimal changes. We just require the CRS trapdoor to be extractable and the CRS to be publicly verifiable. To achieve the latter, we add some new elements to the CRS and construct an efficient CRS verification algorithm. We also provide a definitional framework for sound and Sub-ZK SNARKs and describe implementation results of the new Sub-ZK SNARK.

We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.

In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We obtain the following results: – Three-round concurrent MPC with SPS security against Byzantine adversaries, assuming sub-exponentially secure DDH and LWE. – Two-round concurrent MPC with SPS security against Byzantine adversaries for input-less randomized functionalities, assuming sub- exponentially secure indistinguishability obfuscation and DDH. In particular, this class includes sampling functionalities that allow parties to jointly sample a secure common reference string for cryptographic applications. Prior to our work, to the best of our knowledge, concurrent MPC with SPS security required roughly 20 rounds, although we are not aware of any work that even gave an approximation of the constant round complexity sufficient for the multi-party setting. We also improve over the previous best round complexity for the two-party setting, where 5 rounds were needed (Garg, Kiyoshima, and Pandey, Eurocrypt 2017). To obtain our results, we compile protocols that already achieve security against “semi-malicious” adversaries, to protocols secure against fully malicious adversaries, additionally assuming sub-exponential DDH. Our protocols develop new techniques to use two-round zero-knowledge with super-polynomial strong simulation, defined by Pass (Eurocrypt 2003) and very recently realized by Khurana and Sahai (FOCS 2017). These remain zero-knowledge against adversaries running in time larger than the running time of the simulator.

QcBits is a code-based public key algorithm based on a problem thought to be resistant to quantum computer attacks. It is a constant time implementation for a quasi-cyclic moderate density parity check (QC-MDPC) Niederreiter encryption scheme, and has excellent performance and small key sizes. In this paper, we present a key recovery attack against QcBits. We first used differential power analysis (DPA) against the syndrome computation of the decoding algorithm to recover partial information about one half of the private key. We then used the recovered information to set up a system of noisy binary linear equations. Solving this system of equations gave us the entire key. Finally, we propose a simple but effective countermeasure against the power analysis used during the syndrome calculation.

This paper presents a post-quantum secure, efficient, and tunable FPGA implementation of the key-generation algorithm for the Niederreiter cryptosystem using binary Goppa codes. Our key-generator implementation requires as few as 896,052 cycles to produce both public and private portions of a key, and can achieve an estimated frequency Fmax of over 240 MHz when synthesized for Stratix V FPGAs. To the best of our knowledge, this work is the first hardware-based implementation that works with parameters equivalent to, or exceeding, the recommended 128-bit ``post-quantum security'' level. The key generator can produce a key pair for parameters $m=13$, $t=119$, and $n=6960$ in only $3.7$ ms when no systemization failure occurs, and in $3.5 \cdot 3.7$ ms on average. To achieve such performance, we implemented an optimized and parameterized Gaussian systemizer for matrix systemization, which works for any large-sized matrix over any binary field GF$(2^m)$. Our work also presents an FPGA-based implementation of the Gao-Mateer additive FFT, which only takes about 1000 clock cycles to finish the evaluation of a degree-119 polynomial at $2^{13}$ data points. The Verilog HDL code of our key generator is parameterized and partly code-generated using Python and Sage. It can be synthesized for different parameters, not just the ones shown in this paper. We tested the design using a Sage reference implementation, iVerilog simulation, and on real FPGA hardware.

Although lattice-based cryptography has proven to be a particularly efficient approach to post-quantum cryptography, its security against side-channel attacks is still a very open topic. There already exist some first works that use masking to achieve DPA security. However, for public-key primitives SPA attacks that use just a single trace are also highly relevant. For lattice-based cryptography this implementation-security aspect is still unexplored. In this work, we present the first single-trace attack on lattice-based encryption. As only a single side-channel observation is needed for full key recovery, it can also be used to attack masked implementations. We use leakage coming from the Number Theoretic Transform, which is at the heart of almost all efficient lattice-based implementations. This means that our attack can be adapted to a large range of other lattice-based constructions and their respective implementations. Our attack consists of 3 main steps. First, we perform a template matching on all modular operations in the decryption process. Second, we efficiently combine all this side-channel information using belief propagation. And third, we perform a lattice-decoding to recover the private key. We show that the attack allows full key recovery not only in a generic noisy Hamming-weight setting, but also based on real traces measured on an ARM Cortex-M4F microcontroller.

The complexity of computing the solutions of a system of multivariate polynomial equations by means of Groebner bases computations is upper bounded by a function of the solving degree. In this paper, we discuss how to rigorously estimate the solving degree of a system, focusing on systems arising within public-key cryptography. In particular, we show that it is upper bounded by, and often equal to, the Castelnuovo-Mumford regularity of the ideal generated by the homogenization of the equations of the system, or by the equations themselves in case they are homogeneous. We discuss the underlying commutative algebra and clarify under which assumptions the commonly used results hold. In particular, we discuss the assumption of being in generic coordinates (often required for bounds obtained following this type of approach) and prove that systems that contain the field equations or their fake Weil descent are in generic coordinates. We also compare the notion of solving degree with that of degree of regularity, which is commonly used in the literature. We complement the paper with some examples of bounds obtained following the strategy that we describe.

Major substep in a lattice sieve algorithm which solves the Euclidean shortest vector problem (SVP) is the computation of sums and Euclidean norms of many vector pairs. Finding a solution to the SVP is the foundation of an attack against many lattice based crypto systems. We optimize the main subfunction of a sieve for the regular main processor and for the co-processor to speed up the algorithm in total. Furthermore, we show that the co-processor can provide a significant performance improvement for highly parallel tasks in the lattice sieve. Four-fold speed up achieved, compared to the CPU, indicates that co-processors are a viable choice for implementation of lattice sieve algorithms.