Binarized Neural Networks (BNN) provide efficient implementations of Convolutional Neural Networks (CNN). This makes them particularly suitable to perform fast and memory-light inference of neural networks running on resource-constrained devices. Motivated by the growing interest in CNN-based biometric recognition on potentially insecure devices, or as part of strong multi-factor authentication for sensitive applications, the protection of BNN inference on edge devices is rendered imperative. We propose a new method to perform secure inference of BNN relying on secure multiparty computation. While preceding papers offered security in a semi-honest setting for BNN or malicious security for standard CNN, our work yields security with abort against one malicious adversary for BNN by leveraging on Replicated Secret Sharing (RSS) for an honest majority with three computing parties. Experimentally, we implement BaNNeRS on top of MP-SPDZ and compare it with prior work over binarized models trained for MNIST and CIFAR10 image classification datasets. Our results attest the efficiency of BaNNeRS as a privacy-preserving inference technique.

Metadata from voice calls, such as the knowledge of who is communicating with whom, contains rich information about people’s lives. Indeed, it is a prime target for powerful adversaries such as nation states. Existing systems that hide voice call metadata either require trusted intermediaries in the network or scale to only tens of users. This paper describes the design, implementation, and evaluation of Addra, the first system for voice communication that hides metadata over fully untrusted infrastructure and scales to tens of thousands of users. At a high level, Addra follows a template in which callers and callees deposit and retrieve messages from private mailboxes hosted at an untrusted server. However, Addra improves message latency in this architecture, which is a key performance metric for voice calls. First, it enables a caller to push a message to a callee in two hops, using a new way of assigning mailboxes to users that resembles how a post office assigns PO boxes to its customers. Second, it innovates on the underlying cryptographic machinery and constructs a new private information retrieval scheme, FastPIR, that reduces the time to process oblivious access requests for mailboxes. An evaluation of Addra on a cluster of 80 machines on AWS demonstrates that it can serve 32K users with a 99-th percentile message latency of 726 ms—a 7× improvement over a prior system for text messaging in the same threat model.

In this paper, we show how to apply Montgomery multiplication to the tag tracing variant of the Pollard's rho algorithm applied to prime order fields. This combines the advantages of tag tracing with those of Montgomery multiplication. In particular, compared to the previous version of tag tracing, the use of Montgomery multiplication entirely eliminates costly modular reductions and replaces these with much more efficient divisions by a suitable power of two.

The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes. In this paper, we focus on the basic problem of correcting faulty—or adversarially corrupted—random oracles, so that they can be confidently applied for such cryptographic purposes. We prove that a simple construction can transform a “subverted” random oracle—which disagrees with the original one at a small fraction of inputs—into an object that is indifferentiable from a random function, even if the adversary is made aware of all randomness used in the transformation. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., those permitting adversaries that subvert or replace basic cryptographic algorithms) to use random oracles as a trusted black box.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. This would jeopardize IT security as we know it. In this work, we investigate two quantum-safe, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-case in question and we prove that post-quantum signatures with less than one second signing and less than 10ms verification would not have material impact (less than1‰) on secure boot. We evaluate the hierarchical design of these signatures in hardware-based and virtual secure boot. In addition, we develop Hardware Description Language code and show that the code footprint is just a few kilobytes in size which would fit easily in almost all modern FPGAs. We also analyze and evaluate potential challenges for integration in existing technologies and we discuss considerations for vendors embarking on a journey of image signing with hash-based signatures.

Tropical linear algebra has been recently put forward by Grigoriev and Shpilrain ~\cite{grigoriev2014tropical,grigoriev2018tropical} as a promising platform for the implementation of protocols of Diffie-Hellman and Stickel type. Based on the CSR expansion of tropical matrix powers, we suggest a simple algorithm for the following tropical discrete logarithm problem: ``Given that $A=V\otimes F^{\otimes t}$ for a unique $t$ and matrices $A$, $V$, $F$ of appropriate dimensions, find this $t$.'' We then use this algorithm to suggest a simple attack on a protocol based on the tropical semidirect product. The algorithm and the attack are guaranteed to work in some important special cases and are shown to be efficient in our numerical experiments.

We give secure parameter suggestions to use sparse secret vectors in LWE based encryption schemes. This should replace existing security parameters, because homomorphic encryption(HE) schemes use quite different variables from the existing parameters. In particular HE schemes using sparse secrets should be supported by experimental analysis, here we summarize existing attacks to be considered and security levels for each attacks. Based on the analysis and experiments, we compute optimal scaling factors for CKKS.

We describe the binary numeral tree—a type of binary tree uniquely suited to processing unbounded streams of data—and present a number of algorithms for efficiently constructing and verifying Merkle proofs within such trees. Specifically, we present existence proofs for single leaves, for a contiguous range of leaves, and for multiple disjoint ranges. We also introduce Merkle "diff" proofs, which assert that an arbitrary modification was correctly applied to an existing tree. Each algorithm, operating on a tree with $n$ leaves and $k$ disjoint proof ranges, requires $\mathcal{O}(\log_2(n))$ space and $\mathcal{O}(n)$ time, and yields proofs of size $\mathcal{O}(k\log_2 (n))$. Furthermore, each algorithm operates in streaming fashion, requiring only a single in-order pass over the leaf data.

Being based on a sound theoretical basis, masking schemes are commonly applied to protect cryptographic implementations against Side-Channel Analysis (SCA) attacks. Constructing SCA-protected AES, as the most widely deployed block cipher, has been naturally the focus of several research projects, with a direct application in industry. The majority of SCA-secure AES implementations introduced to the community opted for low area and latency overheads considering Application-Specific Integrated Circuit (ASIC) platforms. Albeit a few, those which particularly targeted Field Programmable Gate Arrays (FPGAs) as the implementation platform yield either a low throughput or a not-highly secure design. In this work, we fill this gap by introducing first-order glitch-extended probing secure masked AES implementations highly optimized for FPGAs, which support both encryption and decryption. Compared to the state of the art, our designs efficiently map the critical non-linear parts of the masked S-box into the built-in Block RAMs (BRAMs). The most performant variant of our constructions accomplishes five first-order secure AES encryptions/decryptions simultaneously in 50 clock cycles. Compared to the equivalent state-of-the-art designs, this leads to at least 70% reduction in utilization of FPGA resources (slices) at the cost of occupying BRAMs. Last but not least, we provide a wide range of such secure and efficient implementations supporting a large set of applications, ranging from low-area to high-throughput.

The modern financial world has seen a significant rise in the use of cryptocurrencies in recent years, partly due to the convincing lures of anonymity promised by these schemes. Bitcoin, despite being considered as the most widespread among all, is claimed to have significant lapses in relation to its anonymity. Unfortunately, studies have shown that many cryptocurrency transactions can be traced back to their corresponding participants through the analysis of publicly available data, to which the cryptographic community has responded by proposing new constructions with improved anonymity claims. Nevertheless, the absence of a common metric for evaluating the level of anonymity achieved by these schemes has led to a number of disparate ad hoc anonymity definitions, making comparisons difficult. The multitude of these notions also hints at the surprising complexity of the overall anonymity landscape. In this study, we introduce such a common framework to evaluate the nature and extent of anonymity in (crypto)currencies and distributed transaction systems, irrespective of their implementation. As such, our work lays the foundation for formalising security models and terminology across a wide range of anonymity notions referenced in the literature, while showing how ``anonymity'' itself is a surprisingly nuanced concept.

Blockchains suffer from a critical scalability problem where traditionally each network node maintains all network state, including records since the establishment of the blockchain. Sketches are popular hash-based data structures used to represent a large amount of data while supporting particular queries such as on set membership, cardinality estimation and identification of large elements. Often, to achieve time and memory savings, sketches allow potential inaccuracies in answers to the queries. The design of popular blockchain networks such as Bitcoin and Ethereum makes use of sketches for various tasks such as summarization of transaction blocks or declaring the interests of light nodes. Similarly, they seem natural to deal with the size of the state in blockchains. In this paper, we study existing and potential future applications of sketches in blockchains. We first summarize current blockchain use cases of sketches. Likewise, we explore how this coupling can be generalized to a wider range of sketches and additional functionalities. In particular, we explain how sketches can detect anomalies based on efficient an summary of the state or traffic.

In $2$-party Circuit-based Private Set Intersection (Circuit-PSI), $P_0$ and $P_1$ hold sets $\mathsf{S}_{0}$ and $\mathsf{S}_{1}$ respectively and wish to securely compute a function $f$ over the set $\mathsf{S}_{0} \cap \mathsf{S}_{1}$ (e.g., cardinality, sum over associated attributes, or threshold intersection). Following a long line of work, Pinkas et al. ($\mathsf{PSTY}$, Eurocrypt 2019) showed how to construct a concretely efficient Circuit-PSI protocol with linear communication complexity. However, their protocol requires super-linear computation. In this work, we construct concretely efficient Circuit-PSI protocols with linear computational and communication cost. Further, our protocols are more performant than the state-of-the-art, $\mathsf{PSTY}$ -- we are $\approx 2.3\times$ more communication efficient and are up to $2.8\times$ faster. We obtain our improvements through a new primitive called Relaxed Batch Oblivious Programmable Pseudorandom Functions ($\mathsf{RBOPPRF}$) that can be seen as a strict generalization of Batch $\mathsf{OPPRF}$s that were used in $\mathsf{PSTY}$. We believe that this primitive could be of independent interest.

Identity-based encryption (IBE), introduced by Shamir, eliminates the need for public-key infrastructure. The sender can simply encrypt a message by using the recipient's identity (such as email or IP address) without needing to look up the public key. In particular, when ciphertexts of an IBE do not reveal recipient's identity, this scheme is known as an anonymous IBE scheme. Recently, Blazy et al. (ARES '19) analyzed the trade-off between public safety and unconditional privacy in anonymous IBE and introduced a new notion that incorporates traceability into anonymous IBE, called anonymous IBE with traceable identities (AIBET). However, their construction is based on the discrete logarithm assumption, which is insecure in the quantum era. In this paper, we first formalize the consistency of tracing key of the AIBET scheme to ensure that a ciphertext cannot be traced with the use of wrong tracing keys. Subsequently, we present a generic formulation concept that can be used to transform structure-specific lattice-based anonymous IBE schemes into an AIBET. Finally, we apply this concept to Katsumata and Yamada's compact anonymous IBE scheme (Asiacrypt '16) to obtain the first quantum-resistant AIBET scheme that is adaptively secure under the ring learning with errors assumption without random oracle.

Protecting secrets is a key challenge in our contemporary information-based era. In common situations, however, revealing secrets appears unavoidable, for instance, when identifying oneself in a bank to retrieve money. In turn, this may have highly undesirable consequences in the unlikely, yet not unrealistic, case where the bank’s security gets compromised. This naturally raises the question of whether disclosing secrets is fundamentally necessary for identifying oneself, or more generally for proving a statement to be correct. Developments in computer science provide an elegant solution via the concept of zero-knowledge proofs: a prover can convince a verifier of the validity of a certain statement without facilitating the elaboration of a proof at all. In this work, we report the experimental realisation of such a zero-knowledge protocol involving two separated verifier-prover pairs. Security is enforced via the physical principle of special relativity, and no computational assumption (such as the existence of one-way functions) is required. Our implementation exclusively relies on off-the-shelf equipment and works at both short (60 m) and long distances (400 m) in about one second. This demonstrates the practical potential of multi-prover zero-knowledge protocols, promising for identification tasks and blockchain-based applications such as cryptocurrencies or smart contracts.

Key distribution protocols deal with generating, exchanging, and storing information (especially shared keys). In this paper, we compare three different types of protocols: classical, quantum key distribution, and blockchain-based protocols, with examples from each category, presenting the particularities and challenges of each one, including solutions and the impact of these protocols.

This paper studies zero-knowledge SNARKs for NP, where the prover incurs $O(N)$ finite field operations to prove the satisfiability of an $N$-sized R1CS instance. We observe that recent work of Bootle, Chiesa, and Groth (BCG, TCC 20) provides a polynomial commitment scheme that, when combined with the linear-time interactive proof system of Spartan~(CRYPTO 20), yields linear-time IOPs and SNARKs for R1CS. Specifically, for security parameter $\lambda$, and for an $N$-sized R1CS instance over a field of size $\exp(\lambda)$ and fixed $\epsilon > 0$, the prover incurs $O(N)$ finite field operations to produce a proof of size $O_\lambda(N^\epsilon)$ that can be verified in $O_\lambda(N^\epsilon)$---after a one-time preprocessing step, which requires $O(N)$ finite field operations. This reestablishes the main result of BCG. Arguably, our approach is conceptually simpler and more direct. Additionally, the polynomial commitment scheme that we distill from BCG is of independent interest; it improves over the prior state of the art by offering the first scheme where the time to commit to an $N$-sized polynomial is $O(N)$ finite field operations. We further observe that one can render the aforementioned SNARK zero knowledge and reduce the proof size and verifier time to polylogarithmic---while maintaining a linear-time prover---by outsourcing the verifier's work via one layer of proof composition with an existing zkSNARK as the ``outer'' proof system. A similar result can be derived from recent work of Bootle, Chiesa, and Liu (ePrint 2020/1527). We implement the aforementioned polynomial commitment scheme with $\epsilon = 1/2$ and combine it with Spartan’s interactive proof system to obtain a SNARK for R1CS. We refer to this combination as Cerberus. It uses Reed-Solomon codes in the polynomial commitment scheme, and hence the prover is not asymptotically linear-time. Nonetheless, Cerberus features the fastest known prover (the only exception is Spartan when proving large instances over 256-bit fields), and is plausibly post-quantum secure.

Nowadays, genomic sequencing has become much more affordable for many people and, thus, many people own their genomic data in a digital format. Having paid for genomic sequencing, they want to make use of their data for different tasks that are possible only using genomics, and they share their data with third parties to achieve these tasks, e.g., to find their relatives in a genomic database. As a consequence, more genomic data get collected worldwide. The upside of the data collection is that unique analyses on these data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive data about his/her risk for getting particular diseases, and even sensitive information about his/her family members. In this paper, we introduce EPISODE - a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database, i.e., securely aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we further optimize and extend to the outsourcing scenario. We improve their protocol by using more efficient building blocks and achieve a 5-6x run-time improvement compared to their work in the same two-party scenario. Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our new protocol outperforms theirs by more than factor 24000x in terms of run-time in the same setting and guarantees the same level of security. In addition, we show that our algorithm scales for practical database sizes by querying a database that contains up to a million short sequences within a few minutes, and a database with hundreds of whole-genome sequences containing 75 million alleles each within a few hours.

The Google Titan Security Key is a FIDO U2F hardware device proposed by Google (available since July 2018) as a two-factor authentication token to sign in to applications (e.g. your Google account). We present here a side-channel attack that targets the Google Titan Security Key’s secure element (the NXP A700X chip) by the observation of its local electromagnetic radiations during ECDSA signatures (the core cryptographic operation of the FIDO U2F protocol). This work shows that an attacker can clone a legitimate Google Titan Security Key. To understand the NXP ECDSA implementation, find a vulnerability and design a key-recovery attack, we had to make a quick stop on Rhea (NXP J3D081 JavaCard smartcard). Freely available on the web, this product looks very much like the NXP A700X chip and uses the same cryptographic library. Rhea, as an open JavaCard platform, gives us more control to study the ECDSA implementation. We could then show that the electromagnetic side-channel signal bears partial information about the ECDSA ephemeral key. The sensitive information is recovered with a non-supervised machine learning method and plugged into a customized lattice-based attack scheme. Finally, 4000 ECDSA observations were enough to recover the (known) secret key on Rhea and validate our attack process. It was then applied on the Google Titan Security Key with success (this time with 6000 observations) as we were able to extract the long term ECDSA private key linked to a FIDO U2F account created for the experiment. Cautionary Note: Two-factor authentication tokens (like FIDO U2F hardware devices) primary goal is to fight phishing attacks. Our attack requires physical access to the Google Titan Security Key, expensive equipment, custom software, and technical skills. Thus, as far as the work presented here goes, it is still safer to use your Google Titan Security Key or other impacted products as FIDO U2F two-factor authentication token to sign in to applications rather than not using one. Nevertheless, this work shows that the Google Titan Security Key (and other impacted products) would not avoid unnoticed security breach by attackers willing to put enough effort into it. Users that face such a threat should probably switch to other FIDO U2F hardware security keys, where no vulnerability has yet been discovered.

Electronic voting consists of the methods that use an electronic system in the process of recording, counting or transmitting votes. It is relatively a new concept used in the democratic processes and especially in the context of COVID19. It’s aim is to reduce errors and to improve the integrity of the election process. In this paper, we provide a review of the existing systems used in Europe. Initially, we mention the factors that influence the adoption of such systems at a large scale. We further describe the systems used in Russia (Moscow’s primary) and in Romania (for counting the ballots). These systems are analyzed in order to find out if they respect technical challenges such as verifiability, dependability, security, anonymity and trust.

Cramer and Shoup introduced at Eurocrypt’02 the concept of hash proof system, also designated as smooth projective hash functions. Since then, they have found several applications, from building CCA-2 encryption as they were initially created for, to being at the core of several authenticated key exchange or even allowing witness encryption. In the post-quantum setting, the very few candidates use a language based on ciphertexts to build their hash proof system. This choice seems to inherently introduce a gap, as some elements outside the language could not be distinguish from those in the language. This creates a lawless zone, where an adversary can possibly mount an undetectable attack, particularly problematic when trying to prove security in the UC framework. We show that this gap could be completely withdrawn using code-based cryptography. Starting from RQC, a candidate selected for the second round of the National Institute of Standards and Technology (NIST) post-quantum cryptography standardization project, we show how to build such a hash proof system from code-based cryptography and present a way, based on a proof of knowledge, to fully negate the gap. We propose two applications of our construction, a witness encryption scheme and a password authenticated key exchange (PAKE).

Federated Learning (FL) is a collaborative machine learning approach allowing participants to jointly train a model without having to share their private, potentially sensitive local datasets with others. Despite its benefits, FL is vulnerable to so-called backdoor attacks, in which an adversary injects manipulated model updates into the federated model aggregation process so that the resulting model will provide targeted false predictions for specific adversary-chosen inputs. Proposed defenses against backdoor attacks based on detecting and filtering out malicious model updates consider only very specific and limited attacker models, whereas defenses based on differential privacy-inspired noise injection significantly deteriorate the benign performance of the aggregated model. To address these deficiencies, we introduce FLAME, a defense framework that estimates the sufficient amount of noise to be injected to ensure the elimination of backdoors. To minimize the required amount of noise, FLAME uses a model clustering and weight clipping approach. This ensures that FLAME can maintain the benign performance of the aggregated model while effectively eliminating adversarial backdoors. Our evaluation of FLAME on several datasets stemming from application areas including image classification, word prediction, and IoT intrusion detection demonstrates that FLAME removes backdoors effectively with a negligible impact on the benign performance of the models.

Post-quantum cryptography (PQC) is a trend that has a deserved NIST status, and which aims to be resistant to quantum computer attacks like Shor and Grover algorithms. NIST is currently leading the third-round search of a viable set of standards, all based on traditional approaches as code-based, lattice-based, multi quadratic-based, or hash-based cryptographic protocols [1]. We choose to follow an alternative way of replacing all numeric field arithmetic with GF(2^8) field operations [2]. By doing so, it is easy to implement R-propped asymmetric systems as the present paper shows [3,4]. Here R stands for Rijndael as we work over the AES field. This approach yields secure post-quantum protocols since the resulting multiplicative monoid is immune against quantum algorithms and resist classical linearization attacks like Tsaban’s Algebraic Span [5] or Roman’kov linearization attacks [6]. The Burmester-Desmedt (B-D) conference key distribution protocol [7] has been proved to be secure against passive adversaries if the computational Diffie-Hellman problem remains hard. The authors refer that the proposed scheme could also be secure against active adversaries under the same assumptions as before if an authentication step is included to foil attacks like MITM (man in the middle). Also, this protocol proved to be semantical secure against adaptative IND-CPA2 [8, 9] if the discrete log problem is intractable. We discuss the features of our present work and a practical way to include an authentication step. Classical and quantum security levels are also discussed. Finally, we present a numerical example of the proposed R-Propped protocol.

The term permissionless has established itself within the context of blockchain and distributed ledger research to characterize protocols and systems that exhibit similar properties to Bitcoin. However, the notion of what is meant by permissionlessness is often vague or left implicit within the various literature, rendering it imprecise and hard to compare. We hereby shed light onto this topic by revising research that either incorporates or defines the term permissionless and systematically expose the properties and characteristics that its utilization intends to capture. Based on this review, we highlight current shortcomings and blind spots within the available definitions. In particular, the ability to freely perform transactions between users is often not adequately incorporated and different actor roles are left unspecified. Furthermore, the topics of privacy and governance appear to be largely overlooked.

In this paper we propose new techniques related to division property. We describe for the first time a practical algorithm for computing the propagation tables of 16-bit Super-Sboxes, increasing the precision of the division property by removing a lot of false division trails. We also improve the complexity of the procedure introduced by Lambin et al. (Design, Codes and Cryptography, 2020) to extend a cipher with linear mappings and show how to decrease the number of transitions to look for. While search procedures for integral distinguishers most often rely on MILP or SAT solvers for their ease of programming the propagation constraints, such generic solvers can only handle small 4/8-bit Sboxes. Thus we developed an ad-hoc tool handling larger Sboxes and all the improvements described in the paper. As a result, we found new integral distinguishers on SKINNY-64, HIGHT and Midori-64.

Fast Near collision attacks on the stream ciphers Grain v1 and A5/1 were presented at Eurocrypt 2018 and Asiacrypt 2019 respectively. They use the fact that the entire internal state can be split into two parts so that the second part can be recovered from the first one which can be found using the keystream prefix and some guesses of the key materials. In this paper we reevaluate the complexity of these attacks and show that actually they are inferior to previously known results. Basically, we show that their complexity is actually much higher and we point out the main problems of these papers based on information theoretic ideas. We also check that some distributions do not have the predicted entropy loss claimed by the authors. Checking cryptographic attacks with galactic complexity is difficult in general. In particular, as these attacks involve many steps it is hard to identify precisely where the attacks are flawed. But for the attack against A5/1, it could have been avoided if the author had provided a full experiment of its attack since the overall claimed complexity was lower than 232 in both time and memory

In this paper we describe a new tool to search for boomerang distinguishers. One limitation of the MILP model of Liu et al. is that it handles only one round for the middle part while Song et al. have shown that dependencies could affect much more rounds, for instance up to 6 rounds for SKINNY. Thus we describe a new approach to turn an MILP model to search for truncated characteristics into an MILP model to search for truncated boomerang characteristics automatically handling the middle rounds. We then show a new CP model to search for the best possible instantiations to identify good boomerang distinguishers. Finally we systematized the method initiated by Song et al. to precisely compute the probability of a boomerang. As a result, we found many new boomerang distinguishers up to 24 rounds in the TK3 model. In particular, we improved by a factor $2^{30}$ the probability of the best known distinguisher against 18-round SKINNY-128/256.

This paper makes a comprehensive comparison of the efficiencies of vectorized implementations of Kummer lines and Montgomery curves at various security levels. For the comparison, nine Kummer lines are considered, out of which eight are new, and new assembly implementations of all nine Kummer lines have been made. Seven previously proposed Montgomery curves are considered and new vectorized assembly implementations have been made for five of them. Our comparisons show that for all security levels, Kummer lines are consistently faster than Montgomery curves, though the speed-up gap is not much.

To maintain the secure information sharing among vehicles in the Internet of Vehicles, various message authentication schemes were proposed. Recently, Sutrala et al. proposed a conditional privacy preserving authentication scheme (``On the Design of Conditional Privacy Preserving Batch Verification-Based Authentication Scheme for Internet of Vehicles Deployment,'' IEEE Trans. Veh. Technol., vol. 69, no. 5, pp. 5535-5548, May 2020.) to against various potential attacks. However, our observations show that, contrary to what is claimed, the scheme is insecure. Any (malicious) vehicle can forge signature for any message, which can be validated successfully and cannot be traceable. Our observations also show that, the security proof based on the standard random oracle model is wrong.

This paper presents Poplar, a new system for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use Poplar to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients. Poplar uses two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Poplar protects client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions. A limitation of Poplar is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, Poplar could compute heavy hitters over ten million clients in just over one hour of computation.

Black-box separations have been successfully used to identify the limits of a powerful set of tools in cryptography, namely those of black-box reductions. They allow proving that a large set of techniques are not capable of basing one primitive $\mathcal{P}$ on another $\mathcal{Q}$. Such separations, however, do not say anything about the power of the combination of primitives $\mathcal{Q}_1,\mathcal{Q}_2$ for constructing $\mathcal{P}$, even if $\mathcal{P}$ cannot be based on $\mathcal{Q}_1$ or $\mathcal{Q}_2$ alone. By introducing and formalizing the notion of black-box uselessness, we develop a framework that allows us to make such conclusions. At an informal level, we call primitive $\mathcal{Q}$ black-box useless (BBU) for primitive $\mathcal{P}$ if $\mathcal{Q}$ cannot help constructing $\mathcal{P}$ in a black-box way, even in the presence of another primitive $\mathcal{Z}$. This is formalized by saying that $\mathcal{Q}$ is BBU for $\mathcal{P}$ if for any auxiliary primitive $\mathcal{Z}$, whenever there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, then there must already also exist a black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We also formalize various other notions of black-box uselessness, and consider in particular the setting of efficient black-box constructions when the number of queries to $\mathcal{Q}$ is below a threshold. Impagliazzo and Rudich (STOC'89) initiated the study of black-box separations by separating key agreement from one-way functions. We prove a number of initial results in this direction, which indicate that one-way functions are perhaps also black-box useless for key agreement. In particular, we show that OWFs are black-box useless in any construction of key agreement in either of the following settings: (1) the key agreement has perfect correctness and one of the parties calls the OWF a constant number of times; (2) the key agreement consists of a single round of interaction (as in Merkle-type protocols). We conjecture that OWFs are indeed black-box useless for general key agreement protocols. We also show that certain techniques for proving black-box separations can be lifted to the uselessness regime. In particular, we show that known lower bounds for assumptions behind black-box constructions of indistinguishability obfuscation (IO) can be extended to derive black-box uselessness of a variety of primitives for obtaining (approximately correct) IO. These results follow the so-called "compiling out" technique, which we prove to imply black-box uselessness. Eventually, we study the complementary landscape of black-box uselessness, namely black-box helpfulness. Formally, we call primitive $\mathcal{Q}$ black-box helpful (BBH) for $\mathcal{P}$, if there exists an auxiliary primitive $\mathcal{Z}$ such that there exists a black-box construction of $\mathcal{P}$ from $(\mathcal{Q},\mathcal{Z})$, but there exists no black-box construction of $\mathcal{P}$ from $\mathcal{Z}$ alone. We put forth the conjecture that one-way functions are black-box helpful for building collision-resistant hash functions. We define two natural relaxations of this conjecture, and prove that both of these conjectures are implied by a natural conjecture regarding random permutations equipped with a collision finder oracle, as defined by Simon (Eurocrypt'98). This conjecture may also be of interest in other contexts, such as hardness amplification.

In recent years, numerous attacks have appeared that aim to steal secret information from their victim using the power side-channel vector, yet without direct physical access. These attacks are called Remote Power Attacks or Remote Power Analysis, utilizing resources that are natively present inside the victim environment. However, there is no unified definition about the limitations that a power attack requires to be defined as remote. This paper aims to propose a unified definition and concrete threat models to clearly differentiate remote power attacks from non-remote ones. Additionally, we collect the main remote power attacks performed so far from the literature, and the principal proposed countermeasures to avoid them. The search of such countermeasures denoted a clear gap in preventing remote power attacks at the technical level. Thus, the academic community must face an important challenge to avoid this emerging threat, given the clear room for improvement that should be addressed in terms of defense and security of devices that work with private information.

Though the multilinear maps have many cryptographic applications, secure and efficient construction of such maps is an open problem. Many multilinear maps like GGH, GGH15, CLT, and CLT15 have been and are being proposed, while none of them is both secure and efficient. The construction of some multilinear maps is based on the Graded Encoding Scheme (GES), where, the necessity of announcing zero-testing parameter and encoding of zero has destroyed the security of the multilinear map. Attempt is made to propose a new GES, where, instead of encoding an element, the users can obtain the encoding of an associated but unknown random element. In this new setting, there is no need to publish the encodings of zero and one. This new GES provides the actual functionality of the usual GES and can be applied in constructing a secure and efficient multilinear map and a multi-party non-interactive key exchange (MP-NIKE) scheme. We also improve the MP-NIKE scheme and turn it into an ID-based MP-NIKE scheme.

We describe and illustrate the local neighbourhoods of vertices and edges in the (2, 2)-isogeny graph of principally polarized abelian surfaces, considering the action of automorphisms. Our diagrams are intended to build intuition for number theorists and cryptographers investigating isogeny graphs in dimension/genus 2, and the superspecial isogeny graph in particular.

We investigate special structures due to automorphisms in isogeny graphs of principally polarized abelian varieties, and abelian surfaces in particular. We give theoretical and experimental results on the spectral and statistical properties of (2, 2)-isogeny graphs of superspecial abelian surfaces, including stationary distributions for random walks, bounds on eigenvalues and diameters, and a proof of the connectivity of the Jacobian subgraph of the (2, 2)-isogeny graph. Our results improve our understanding of the performance and security of some recently-proposed cryptosystems, and are also a concrete step towards a better understanding of general superspecial isogeny graphs in arbitrary dimension.

The problem of solving explicitly the equation $P_a(X):=X^{q+1}+X+a=0$ over the finite field $\GF{Q}$, where $Q=p^n$, $q=p^k$ and $p$ is a prime, arises in many different contexts including finite geometry, the inverse Galois problem \cite{ACZ2000}, the construction of difference sets with Singer parameters \cite{DD2004}, determining cross-correlation between $m$-sequences \cite{DOBBERTIN2006} and to construct error correcting codes \cite{Bracken2009}, cryptographic APN functions \cite{BTT2014,Budaghyan-Carlet_2006}, designs \cite{Tang_2019}, as well as to speed up the index calculus method for computing discrete logarithms on finite fields \cite{GGGZ2013,GGGZ2013+} and on algebraic curves \cite{M2014}. Subsequently, in \cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019,KCM19}, the $\GF{Q}$-zeros of $P_a(X)$ have been studied. In \cite{Bluher2004}, it was shown that the possible values of the number of the zeros that $P_a(X)$ has in $\GF{Q}$ is $0$, $1$, $2$ or $p^{\gcd(n, k)}+1$. Some criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ were found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}. However, while the ultimate goal is to explicit all the $\GF{Q}$-zeros, even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}. In this article, we discuss this equation without any restriction on $p$ and $\gcd(n,k)$. In \cite{KCM19}, for the cases of one or two $\GF{Q}$-zeros, explicit expressions for these rational zeros in terms of $a$ were provided, but for the case of $p^{\gcd(n, k)}+1$ $\GF{Q}-$ zeros it was remained open to explicitly compute the zeros. This paper solves the remained problem, thus now the equation $X^{p^k+1}+X+a=0$ over $\GF{p^n}$ is completely solved for any prime $p$, any integers $n$ and $k$.

Compression is widely used in Internet communication to save communication time and bandwidth. Recently invented by Jarek Duda asymmetric numeral system (ANS) offers an improved efficiency and a close to optimal compression. The ANS algorithm has been deployed by major IT companies such as Facebook, Google and Apple. Compression by itself does not provide any security (such as confidentiality or authentication of transmitted data). An obvious solution to this problem is an encryption of compressed bitstream. However, it requires two algorithms: one for compression and the other for encryption. In this work, we investigate natural properties of ANS that allow to incorporate authenticated encryption using as little cryptography as possible. We target low-level security communication such as transmission of data from IoT devices/sensors. In particular, we propose three solutions for joint compression and encryption (compcrypt). All of them use a pseudorandom bit generator (PRGB) based on lightweight stream ciphers. The first solution applies state jumps controlled by PRGB. The second one employs two ANS algorithms, where compression switches between the two. The switch is controlled by a PRGB bit. The third compcrypt modifies the encoding function of ANS depending on PRGB bits. Security and efficiency of the proposed compcrypt algorithms are evaluated.

Abstract: Off-chain is a common approach to deal with the scalability problem of blockchain networks. It enables users toexecute multiple payments without committing each of them to the blockchain by relying on predefined payment channels. Apair of users can employ a payment even without a direct channel between them, via routing the payment through off-chainchannels involving other intermediate users. Users together with the off-chain channels form a graph, known as the off-chainnetwork topology. The off-chain topology and the payment characteristics affect network performance such as the averagenumber of intermediate users a payment is routed through, the amount of fees, or channel capacities needed to successfullyroute payments. In this paper, we study two basic problems in off-chain network design. First, efficiently mapping users toan off-chain topology with a known structure. Second, constructing a topology of a bounded number of channels that canserve well users with associated payments. We design algorithms for both problems and evaluate them based on real datafrom Raiden, the off-chain extension for Ethereum. Keywors:

Nonlinear diffusion layers are less studied in cryptographic literature, up to now. In 2018, Liu, Rijmen and Leander studied nonlinear non-MDS diffusion layers and mentioned some advantages of them. As they stated, nonlinear diffusion layers could make symmetric ciphers more resistant against statistical and algebraic cryptanalysis. In this paper, with the aid of some special maps over the finite field $\mathbb{F}_{2^n}$, we examine nonlinear MDS mappings and present a family of $4 \times 4$ nonlinear MDS diffusion layers. Next, we determine the Walsh and differential spectrum as well as the algebraic degree of the proposed diffusion layers.

Zhang et al. recently proposed a lattice-based proxy-oriented identity-based encryption with keyword search (PO-IBEKS) at Information Sciences in 2019. They claimed that their scheme can resist insider keyword guessing attacks by preventing cloud server from generating ciphertext. In this note, we provide a cryptanalysis of their PO-IBEKS and demonstrate that their scheme cannot resist outsider/insider keyword guessing attacks, even though they satisfy unforgeability requirement. Furthermore, we uncover the root cause of the attack and provide a possible solution for Zhang et al.'s scheme to aid future designs of secure PO-IBEKS schemes.

Many web-based and mobile applications and services allow users to indicate their preferences regarding whether and how their personal information can be used or reused by the application itself, by the service provider, and/or by third parties. The number of possible configurations that constitute a user's preference profile can be overwhelming to a typical user. This report describes a practical, privacy-preserving technique for reducing the burden users face when specifying their preferences by offering users data-driven recommendations for fully-specified preference profiles based on their inputs for just a few settings. The feasibility of the approach is demonstrated by a browser-based prototype application that relies on secure multi-party computation and uses the web-compatible JIFF library as the backbone for managing communications between the client application and the recommendation service. The principal algorithms used for generating proposed preference profiles are $k$-means clustering (for privacy-preserving analysis of preference profile data across multiple users) and $k$-nearest neighbors (for selecting a proposed preference profile to recommend to the user).

In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from $O(n^2)$ to $O(n log(n))$, where $n$ denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity. We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. % Finally, we experimentally evaluate our DKG and show that the per-party overheads scale linearly and are practical. For $64$ parties, it takes $71$ms to share and $359$ms to verify the overall transcript, while for $8192$ parties, it takes $8$s and $42.2$s respectively.

This study presents a method to perform low-latency modular multiplication operation based on both Montgomery and Ozturk methods. The design space exploration of the proposed method on a latest FPGA device is also given. Through series of experiments on the FPGA using an high-level synthesis tool, optimal parameter selection of the proposed method for the low-latency constraint is also presented for the proposed technique.

Applying access structure to encrypted sensitive data is one of the challenges in communication networks and cloud computing. Various methods have been proposed to achieve this goal, one of the most interesting of which is Attribute-Based Encryption (ABE). In ABE schemes, the access structure, which is defined as a policy, can be applied to the key or ciphertext. Thus, if the policy is applied to the key, it is called the Key Policy Attribute-Based Encryption (KP-ABE), and on the other hand, if it is applied to the ciphertext, it is called the Ciphertext Policy Attribute-Based Encryption (CP-ABE). Since in the KP-ABE, the policy is selected once by a trusted entity and is fixed then, they are not suitable for applications where the policy needs to change repeatedly. This problem is solved in CP-ABE, where the policy is selected by the sender and changed for each message. Furthermore, the access structure should present a strong fine-grained access control. The arithmetic access structure can supply fine-grained access structures stronger than Boolean access structures. We present the first CP-ABE scheme with an arithmetic circuit access policy based on the multilinear maps. First, we outline a basic design and then two improved versions of this scheme, with or without the property of hidden attributes, are introduced. We also define the concept of Hidden Result Attribute Based Encryption (HR-ABE) which means that the result of the arithmetic function will not be revealed to the users. We define a new hardness assumption, called the (k-1)-Distance Decisional Diffie-Hellman assumption, which is at least as hard as the k-multilinear decisional Diffie-Hellman assumption. Under this assumption, we prove the adaptive security of the proposed scheme.

Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a construction of comparable efficiency with lattice encryption that avoids sampling using structured secrets together with temporary keys. Structured secrets (and randoms) also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signature scheme allows the same parameters of any encryption schemes (a variation of the basic form is needed when the modulus is as small as 1-byte) and has comparable efficiency with our extreme encryption efficiency. For lightweight implementation, our techniques allow integrating of public-key encryption and signature in a simple circuit which only needs to do small integer additions as the main part of the computation.

In this paper, we present a multi-client quadratic functional encryption (MCQFE) scheme from function-hiding inner-product (FHIP). The main challenge in such construction is that all the clients require the access to the master secret key of the underlying FHIP scheme, which clearly breaches the security. To overcome this challenge, we present an efficient decentralized version of FHIP scheme of Lin (Crypto 16). This leads to a 2-step MCQFE (2-MCQFE) scheme. In a 2-step MCQFE scheme, the encryption phase is a (non-interactive) protocol among clients and a set of honest-but-curious authorities. More precisely, clients are the owner of messages and the master secret-key of the underlying FHIP is shared among authorities. In the first step, the client publishes a pre-ciphertext ``pct'' associated with its message. Then in the second step, each authority generates its share ``ct_i'' extracted from the pre-ciphertext. The public aggregation of these shares ``ct_i'' will generate the target ciphertext ``ct'' which then would be applied on the functional key ``sk_F'' to compute the quadratic functionality. The security model is strong enough to consider no trust among clients and authorities, and also the revelation of some secret keys (of clients or authorities) through corruptions. We instantiate our 2-MCQFE scheme and prove its security in the random-oracle model based on the SXDH assumption. Moreover, we show that its security holds as long as at least one of the authorities is not corrupted.

In Crypto’19, Gohr proposed the first deep learning-based key recovery attack on 11-round Speck32/64, which opens the direction of neural aided cryptanalysis. Until now, neural aided cryptanalysis still faces two problems: (1) the attack complexity estimations rely purely on practical experiments. There is no theoretical framework for estimating theoretical complexity. (2) it does not work when there are not enough neutral bits that exist in the prepended differential. To the best of our knowledge, we are the first to solve these two problems. In this paper, we propose a Neural Aided Statistical Attack (NASA) that has the following advantages: (1) NASA supports estimating the theoretical complexity. (2) NASA does not rely on any special properties including neutral bits. (3) NASA is applicable to large-size ciphers. Moreover, we propose three methods for reducing the attack complexity of NASA. One of the methods is based on a newly proposed concept named Informative Bit that reveals an important phenomenon. Four attacks on 9-round or 10-round Speck32/64 are executed to verify the correctness of NASA. To further highlight the advantages of NASA, we have performed a series of experiments. At first, we apply NASA and Gohr’s attack to round reduced DES. Since NASA does not rely on neutral bits, NASA breaks 10-round DES while Gohr’s attack breaks 8-round DES. Then, we compare the time consumption of attacks on 11-round Speck32/64. When the newly proposed three methods are used, the time consumption of NASA is almost the same as that of Gohr’s attack. Besides, NASA is applied to 13-round Speck32/64. At last, we introduce how to analyze the resistance of large-size ciphers with respect to NASA, and apply NASA to 14-round Speck96/96. The code of this paper is available at https://github.com/AI-Lab-Y/NASA. Our work arguably raises a new direction for neural aided cryptanalysis.

We revisit some well-known cryptographic problems in a black box modular ring model of computation. This model allows us to compute with black box access to the ring $\mathbb{Z}/m\mathbb{Z}$. We develop new generic ring algorithms to recover $m$ even if it is unknown. At the end, Maurer's generic algorithm allows to recover an element from its black box representation. However, we avoid Maurer's idealized model with CDH oracle for the multiplication in the hidden ring by introducing a new representation compatible with ring operations. An element is encoded by its action over the factor basis. Consequently, we can multiply two elements with classical descent computations in sieving algorithms. As the algorithms we propose work without using an expensive linear algebra computation at the end, even though they manipulate large sparse matrices, we can exploit a high-level of parallelism. Then, we consider general groups such as imaginary quadratic class group and the Jacobian of a hyperelliptic curve, and obtain new methods for group order computation. The repeated squaring problem and the adaptive root problem used in the construction of Verifiable Delay Functions are particularly easy to solve in the black box modular ring, the high degree of parallelism provided by our method allows a reduction in the time to solve them. We improve the smoothing time, and as a result, we break Verifiable Delay Functions and factorize weak keys with lower Area-Time cost. Finally, we show new AT costs for computing a discrete logarithm over an adversarial basis in finite fields.

Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size arguments) that has a *split accumulation scheme*, which is a weak form of accumulation that we introduce. Moreover, we construct a transparent non-interactive argument of knowledge for R1CS whose split accumulation is verifiable via a (small) *constant number of group and field operations*. Our construction is proved secure in the random oracle model based on the hardness of discrete logarithms, and it leads, via the random oracle heuristic and our result above, to concrete efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for Hadamard products under Pedersen commitments and for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.

We study non-interactive arguments of knowledge (AoKs) for commitments in groups of hidden order. We provide protocols whereby a Prover can demonstrate certain properties of and relations between committed sets/multisets, with succinct proofs that are publicly verifiable against the constant-sized commitments. In particular, we provide AoKs for the disjointness of committed sets/multisets in cryptographic accumulators, with a view toward applications to verifiably outsourcing data storage and sharded stateless blockchains. Recent work ([DGS20]) suggests that the hidden order groups need to be substantially larger in size that previously thought, in order to ensure the desired security level. Thus, in order to keep the communication complexity between the Prover and the the Verifier to a minimum, we have designed the protocols so that the proofs entail a constant number of group elements, independent of the number of the committed sets/multisets rather than just independent of the sizes of these sets/multisets. If the underlying group of hidden order is an appropriate imaginary quadratic class group or a genus three Jacobian, the argument systems are transparent. Furthermore, since all challenges are public coin, the protocols can be made non-interactive using the Fiat-Shamir heuristic. We build on the techniques from [BBF19] and [Wes18].

In Chen-Cramer Crypto 2006 paper \cite{cc} algebraic geometric secret sharing schemes were proposed such that the ``Fundamental Theorem in Information-Theoretically Secure Multiparty Computation" by Ben-Or, Goldwasser and Wigderson \cite{BGW88} and Chaum, Crépeau and Damgård \cite{CCD88} can be established over constant-size base finite fields. These algebraic geometric secret sharing schemes defined by a curve of genus $g$ over a constant size finite field ${\bf F}_q$ is quasi-threshold in the following sense, any subset of $u \leq T-1$ players (non qualified) has no information of the secret and any subset of $u \geq T+2g$ players (qualified) can reconstruct the secret. It is natural to ask that how far from the threshold these quasi-threshold secret sharing schemes are? How many subsets of $u \in [T, T+2g-1]$ players can recover the secret or have no information of the secret? In this paper it is proved that almost all subsets of $u \in [T,T+g-1]$ players have no information of the secret and almost all subsets of $u \in [T+g,T+2g-1]$ players can reconstruct the secret when the size $q$ goes to the infinity and the genus satisfies $\lim \frac{g}{\sqrt{q}}=0$. Then algebraic geometric secretsharing schemes over large finite fields are asymptotically threshold in this case. We also analyze the case when the size $q$ of the base field is fixed and the genus goes to the infinity.

Multipartite secret sharing schemes are those that have multipartite access structures. The set of the participants in those schemes is divided into several parts, and all the participants in the same part play the equivalent role. One type of such access structure is the compartmented access structure. We propose an ideal and efficient compartmented multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations. In the construction phase, the shared secrets are hidden in some terms of the linear homogeneous recurrence sequence. In the recovery phase, the shared secrets are obtained by solving those terms in which the shared secrets are hidden. When the global threshold is $t$, our scheme can reduce the computational complexity from $O(n^{t-1})$ to $O(n^{\max(t_i-1)}\log n)$, where $t_i<t$. The security of the proposed scheme is based on Shamir's threshold scheme. Moreover, it is efficient to share the multi-secret and to change the shared secrets in the proposed scheme. That is, the proposed scheme can improve the performances of the key management and the distributed system.

A long standing question in the context of cryptocurrencies based on Nakamoto consensus is whether such constructions are incentive compatible, i.e., the intended properties of the system emerge from the appropriate utility model for participants. Bribing and other related attacks, such as front-running or Goldfinger attacks, aim to directly influence the incentives of actors within (or outside) of the targeted cryptocurrency system. The theoretical possibility of bribing at tacks on cryptocurrencies was discussed early on in the cryptocurrency community and various different techniques and approaches have since been proposed. Some of these attacks are designed to gain in-band profits, while others intend to break the mechanism design and render the cryptocurrency worthless. In this paper, we systematically expose the large but scattered body of research in this area which has accumulated over the years. We summarize these bribing attacks and similar techniques that leverage on programmatic execution and verification under the term algorithmic incentive manipulation (AIM) attacks, and show that the problem space is not yet fully explored. Based on our analysis we present several research gaps and opportunities that warrant further investigation. In particular, we highlight no- and near-fork attacks as a powerful, yet largely underestimated, AIM category that raises serious security concerns not only for smart contract platforms.

Payment Channel Networks (PCNs) have given a huge boost to the scalability of blockchain-based cryptocurrencies: Beyond improving the transaction rate, PCNs enabled cheap cross-currency payments and atomic swaps. However, current PCNs proposals either heavily rely on special scripting features of the underlying blockchain (e.g. Hash Time Lock Contracts) or are tailored to a handful of digital signature schemes, such as Schnorr or ECDSA signatures. This leaves us in an unsatisfactory situation where many currencies that are being actively developed and use different signature schemes cannot enjoy the benefits of a PCN. In this work, we investigate whether we can construct PCNs assuming the minimal ability of a blockchain to verify a digital signature, for any signature scheme. In answering this question in the affirmative, we introduce the notion of lockable signatures, which constitutes the cornerstone of our PCN protocols. Our approach is generic and the PCN protocol is compatible with any digital signature scheme, thus inheriting all favorable properties of the underlying scheme that are not offered by Schnorr/ECDSA (e.g.\ aggregatable signatures or post-quantum security). While the usage of generic cryptographic machinery makes our generic protocol impractical, we view it as an important feasibility result as it may serve as the basis for constructing optimized protocols for specific signature schemes. To substantiate this claim, we design a highly efficient PCN protocol for the special case of Boneh-Lynn-Shacham (BLS) signatures. BLS signatures enjoy many unique features that make it a viable candidate for a blockchain, e.g. short, unique, and aggregatable signatures. Yet, prior to our work, no PCN was known to be compatible with it (without requiring an advanced scripting language). The cost of our PCN is dominated by a handful of calls to the BLS algorithms. Our concrete evaluation of these basic operations shows that users with commodity hardware can process payments with minimal overhead.

Hierarchical secret sharing is an important key management technique since it is specially customized for hierarchical organizations with different departments allocated with different privileges, such as the government agencies or companies. Hierarchical access structures have been widely adopted in secret sharing schemes, where efficiency is the primary consideration for various applications. How to design an efficient hierarchical secret sharing scheme is an important issue. In 2007, a famous hierarchical secret sharing (HSS) scheme was proposed by Tassa based on Birkhoff interpolation, and later, based on the same method, many other HSS schemes were proposed. However, these schemes all depend on Polya's condition, which is a necessary condition not a sufficient condition. It cannot guarantee that Tassa's HSS scheme always exists. Furthermore, this condition needs to check the non-singularity of many matrices. We propose a hierarchical multi-secret sharing scheme based on the linear homogeneous recurrence (LHR) relations and the one-way function. In our scheme, we select $m$ linearly independent homogeneous recurrence relations. The participants in the highly-ranked subsets $\gamma_1, \gamma_2 ,\cdots, \gamma_{j-1}$ join in the $j$-th subset to construct the $j$-th LHR relation. In addition, the proposed hierarchical multi-secret sharing scheme just requires one share for each participant, and keeps the same computational complexity. Compared with the state-of-the-art hierarchical secret sharing schemes, our scheme has high efficiency.

Private Stream Aggregation (PSA) protocols allow for the secure aggregation of time-series data, affording security and privacy to users' private data, with significantly better efficiency than general secure computation such as homomorphic encryption, multiparty computation, and secure hardware based approaches. Earlier PSA protocols face limitations including needless complexity, a lack of post-quantum security, or other practical issues. In this work, we present SLAP, a Simple Lattice-based Private Stream Aggregation Protocol. SLAP features two variants with post-quantum security, with simpler and more efficient computations enabled by (1) our white-box approach that builds the encryption directly from the Ring Learning With Errors assumption and (2) application of state-of-the-art algorithmic optimizations in lattice-based cryptography. We prove that SLAP with differentially private inputs is an aggregator oblivious PSA scheme. We implement SLAP, and show experimentally the improvements of SLAP over similar work. We show a speedup of 20.76x over the previous state-of-the-art RLWE-based PSA work's aggregation, and apply techniques including RNS, NTT, and batching to obtain a throughput of 390,691 aggregations per second for 1000 users. The communication overhead of SLAP is less than in previous work, with decreases of up to 99.96% in ciphertext sizes as compared to previous work in RLWE-based PSA. We also show the improvement of SLAP over other state-of-the-art post-quantum PSA with regards to throughput, and compare and contrast our RLWE-based approach with other work based upon secret sharing and Learning-With-Rounding.

Ransomware is a type of malware that blocks an user’s access to files and requests him/her a ransom. The main approach of an attacker is to encrypt the user’s files and give him/her the decrypting tool only after he/she pays the requested amount of money. The payment is usually done in difficult to trace currencies. In this paper, we provide a review of the ransomware phenomenon, making a clear distinction between the threats before and after WannaCry (which appeared in May 2017). Initially, we give two taxonomy examples from the literature and one designed by us. The first two taxonomies use ”Platform”, ”Cryptosystem”/”Crypto”, ”Severity”, ”Attack” and ”Target” as criteria (the terms appear in one of them or both), but we have chosen ”Target Zone”, ”Propagation”, ”Payment” and ”Weakness”. We further describe/compare ransomware programs, taking into account several aspects including how they work (e.g., encryption methods), whom they target (e.g., individuals/organizations), what impact they have and what weaknesses can be used to provide countermeasures (besides the general prevention techniques that we mention briefly).

In 2017, Tang et al. have introduced a generic construction for bent functions of the form $f(x)=g(x)+h(x)$, where $g$ is a bent function satisfying some conditions and $h$ is a Boolean function. Recently, Zheng et al. generalized this result to construct large classes of bent vectorial Boolean function from known ones in the form $F(x)=G(x)+h(X)$, where $G$ is a bent vectorial and $h$ a Boolean function. In this paper we further generalize this construction to obtain vectorial bent functions of the form $F(x)=G(x)+\mathbf{H}(X)$, where $\mathbf{H}$ is also a vectorial Boolean function. This allows us to construct new infinite families of vectorial bent functions, EA-inequivalent to $G$, which was used in the construction. Most notably, specifying $\mathbf{H } (x)=\mathbf{h} (Tr_1^n(u_1x),\ldots,Tr_1^n(u_tx))$, the function $\mathbf{h} :\mathbb{F}_2^t \rightarrow \mathbb{F}_{2^t}$ can be chosen arbitrary which gives a relatively large class of different functions for a fixed function $G$. We also propose a method of constructing vectorial $(n,n)$-functions having maximal number of bent components.

Competitions are widely viewed as the safest way to select cryptographic algorithms. This paper surveys procedures that have been used in cryptographic competitions, and analyzes the extent to which those procedures reduce security risks.

Cryptocurrencies and decentralized ledger technology has been widely adopted over the last decades. However, there isn’t yet a decentralized exchange that protects users’ privacy from end to end. In this paper, we construct the first ledger-based decentralized token exchange with strong privacy guarantees. We propose the first Decentralized Anonymous eXchange scheme (DAX scheme) based on automated market maker (AMM) and zkSNARK and present a formal definition of its security and privacy properties.

Homomorphic encryption (HE) is considered as one of the most important primitives for privacy-preserving applications. However, an efficient approach to evaluate both polynomial and non-polynomial functions on encrypted data is still absent, which hinders the deployment of HE to real-life applications. To address this issue, we propose a practical framework PEGASUS. PEGASUS can efficiently switch back and forth between a packed CKKS ciphertext and FHEW ciphertexts without decryption, allowing us to evaluate arithmetic functions efficiently on the CKKS side, and to evaluate look-up tables on FHEW ciphertexts. Our FHEW ! CKKS conversion algorithm is more practical than the existing methods. We improve the computational complexity from linear to sublinear. Moreover, the size of our conversion key is significantly smaller, e.g., reduced from 80 gigabytes to 12 megabytes. We present extensive benchmarks of PEGASUS, including sigmoid/ReLU/min/max/division, sorting and max-pooling. To further demonstrate the capability of PEGASUS, we developed two more applications. The first one is a private decision tree evaluation whose communication cost is about two orders of magnitude smaller than the previous HE-based approaches. The second one is a secure K-means clustering that is able to run on thousands of encrypted samples in minutes that outperforms the best existing system by 14 – 20. To the best of our knowledge, this is the first work that supports practical K-means clustering using HE in a single server setting.

$P_4$-free graphs-- also known as cographs, complement-reducible graphs, or hereditary Dacey graphs--have been well studied in graph theory. Motivated by computer science and information theory applications, our work encodes (flat) joint probability distributions and Boolean functions as bipartite graphs and studies bipartite $P_4$-free graphs. For these applications, the graph properties of edge partitioning and covering a bipartite graph using the minimum number of these graphs are particularly relevant. Previously, such graph properties have appeared in leakage-resilient cryptography and (variants of) coloring problems. Interestingly, our covering problem is closely related to the well-studied problem of product/Prague dimension of loopless undirected graphs, which allows us to employ algebraic lower-bounding techniques for the product/Prague dimension. We prove that computing these numbers is \npol-complete, even for bipartite graphs. We establish a connection to the (unsolved) Zarankiewicz problem to show that there are bipartite graphs with size-$N$ partite sets such that these numbers are at least ${\epsilon\cdot N^{1-2\epsilon}}$, for $\epsilon\in\{1/3,1/4,1/5,\dotsc\}$. Finally, we accurately estimate these numbers for bipartite graphs encoding well-studied Boolean functions from circuit complexity, such as set intersection, set disjointness, and inequality. For applications in information theory and communication \& cryptographic complexity, we consider a system where a setup samples from a (flat) joint distribution and gives the participants, Alice and Bob, their portion from this joint sample. Alice and Bob's objective is to non-interactively establish a shared key and extract the left-over entropy from their portion of the samples as independent private randomness. A genie, who observes the joint sample, provides appropriate assistance to help Alice and Bob with their objective. Lower bounds to the minimum size of the genie's assistance translate into communication and cryptographic lower bounds. We show that (the $\log_2$ of) the $P_4$-free partition number of a graph encoding the joint distribution that the setup uses is equivalent to the size of the genie's assistance. Consequently, the joint distributions corresponding to the bipartite graphs constructed above with high $P_4$-free partition numbers correspond to joint distributions requiring more assistance from the genie. As a representative application in non-deterministic communication complexity, we study the communication complexity of nondeterministic protocols augmented by access to the equality oracle at the output. We show that (the $\log_2$ of) the $P_4$-free cover number of the bipartite graph encoding a Boolean function $f$ is equivalent to the minimum size of the nondeterministic input required by the parties (referred to as the communication complexity of $f$ in this model). Consequently, the functions corresponding to the bipartite graphs with high $P_4$-free cover numbers have high communication complexity. Furthermore, there are functions with communication complexity close to the \naive protocol where the nondeterministic input reveals a party's input. Finally, the access to the equality oracle reduces the communication complexity of computing set disjointness by a constant factor in contrast to the model where parties do not have access to the equality oracle. To compute the inequality function, we show an exponential reduction in the communication complexity, and this bound is optimal. On the other hand, access to the equality oracle is (nearly) useless for computing set intersection.

Contemporary libraries and frameworks that make it possible to incorporate secure multi-party computation protocols and capabilities into production software systems and applications must sometimes deliver underlying capabilities (such as logical circuit synthesis) to new kinds of environments (such as web browsers or serverless cloud computing platforms). In order to illustrate some of the benefits of addressing this challenge by building a solution from the ground up that leverages the features of a contemporary and widely used programming language, we present an embedded domain-specific language that allows programmers to describe and synthesize logical circuits. Notably, this approach allows programmers to employ many of the language features and any of the programming paradigms supported by the host language. We illustrate this flexibility by considering two use cases: synthesizing circuits for relational operations and synthesizing circuits corresponding to the SHA-256 cryptographic hash function.

Delegation of signing rights can be useful to promote effective resource sharing and smooth cooperation among participants in distributed systems, and in many situations, we often need restricted delegation such as one-timeness and unlinkability rather than simple full delegation. Particularly, one-timesness cannot be achieved just by deploying cryptographic measures, and one needs to resort to some form of tamper-proofness or the assistance from external cloud servers for ``key-disabling''. In this work, we extend the latter such that a delegatee can sign a message without the delegator's involvement with the assumption that there exists at least one honest cloud server with secure erasure to achieve one-timeness. In this setting, if the delegator just shares their signing key between the delegatee and cloud servers, it may be problematic. It is because in the worst case, the delegator cannot know whether or not a signing key theft occurred because the signatures generated illegally are indistinguishable from the ones generated legally. To solve this, first we propose an efficient one-time delegation scheme of Okamoto-Schnorr signing. Further we combine the basic delegation scheme with anonymous credentials such that the delegator can detect the signing key theft even if one-time delegation is broken while also achieving unlinkability for both the delegator and cloud servers. Further we show its application to an e-cash scheme, which can prevent double-spending.

Polynomial multiplication is one of the most costly operations of ideal lattice-based cryptosystems. In this work, we study its optimization when one of the operand has coefficients close to 0. We focus on this structure since it is at the core of lattice-based Key Exchange Mechanisms submitted to the NIST call for post-quantum cryptography. In particular, we propose optimization of this operation for embedded devices by using a RSA/ECC coprocessor that provides efficient large-integer arithmetic. In this context, we compare Kronecker Substitution, already studied by Albrecht et al. in TCHES 2019, with two specific algorithms that we introduce: KSV, a variant of this substitution, and an adaptation of the schoolbook multiplication, denoted Shift&Add. All these algorithms rely on the transformation of polynomial multiplication to large-integer arithmetic. Then, thanks to these algorithms, existing coprocessors dedicated to large-integer can be re-purposed in order to speed-up post-quantum schemes. The efficiency of these algorithms depends on the component specifications and the cryptosystem parameters set. Thus, we establish a methodology to determine which algorithm to use, for a given component, by only implementing basic large-integer operations. Moreover, the three algorithms are assessed on a chip ensuring that the theoretical methodology matches with practical results. They are also compared to reference software implementations such as NTT or schoolbook multiplication.

Second-layer or off-chain protocols increase the throughput of permissionless blockchains by enabling parties to lock funds into smart-contracts and perform payments through peer-to-peer communication, only resorting to the smart-contracts for protection against fraud. Current protocols have fixed time periods during which participants can dispute any fraud attempts. However, current blockchains have limited transaction processing capacity, so a fixed dispute period will not always be sufficient to deter all fraudulent behaviour in an off-chain protocol. In this work, we describe how to set adaptive dispute periods that accommodate the congestion and capacity of the underlying blockchain. Adaptive dispute periods ensure that users retain the opportunity to dispute fraudulent behaviours during blockchain congestion, while increasing second-layer protocol efficiency by reducing dispute period lengths when the number of disputes is low. We describe a non-interactive argument system for setting adaptive dispute periods under the current Ethereum Virtual Machine, and discuss how to efficiently integrate built-in support for adaptive dispute periods in any blockchain. We empirically demonstrate that an adaptive-dispute second-layer protocol can handle a larger number of disputes and prevent more fraud than its non-adaptive counterparts even when users are slow to issue disputes, due to denial of service or blockchain congestion.

Due to the constant increase and versatility of IoT devices that should keep sensitive information private, Side-Channel Analysis (SCA) attacks on embedded devices are gaining visibility in the industrial field. The integration and validation of countermeasures against SCA can be an expensive and cumbersome process, especially for the less experienced ones, and current certification procedures require to attack the devices under test using multiple SCA techniques and attack vectors, often implying a high degree of complexity. The goal of this paper is to ease one of the most crucial and tedious steps of profiling attacks i.e. the points of interest (POI) selection and hence assist the SCA evaluation process. To this end, we introduce the usage of Estimation of Distribution Algorithms (EDAs) in the SCA field in order to automatically tune the point of interest selection. We showcase our approach on several experimental use cases, including attacks on unprotected and protected AES implementations over distinct copies of the same device, dismissing in this way the portability issue.

In this work we describe a token-based solution to Contact Tracing via Distributed Point Functions (DPF) and, more generally, Function Secret Sharing (FSS). The key idea behind the solution is that FSS natively supports secure keyword search on raw sets of keywords without a need for processing the keyword sets via a data structure for set membership. Furthermore, the FSS functionality enables adding up numerical payloads associated with multiple matches without additional interaction. These features make FSS an attractive tool for lightweight privacy-preserving searching on a database of tokens belonging to infected individuals.

WARP is proposed by S. Banik et al. in SAC 2020. It is a 128-bit lightweight block cipher with 128-bit key. WARP is based on the 32-nibble type-2 Generalised Feistel Network (GFN) structure. It uses a permutation over nibbles which is designed to optimize the security and efficiency. The designers have provided a lower bound for the number of differentially active S-boxes but the detailed differential characteristics are not provided. In this paper, we discuss the MILP based search technique and present the differential characteristics for the 18-round and 19-round WARP with probability of 2^(-122) and 2^(-132) respectively. We also present a key recovery attack on the 21-round WARP with data complexity of 2^(113 )chosen plaintexts. To the best of our knowledge, these detailed differential characteristics are presented for the first time and this is the first key recovery attack on the 21-round WARP.

The Advanced Encryption Standard (AES) is the most widely used symmetric encryption algorithm. Its security is mainly based on the structure of the S-box. In this paper, we present a new way to create S-boxes for AES and exhibit an S-box with improved cryptographic properties such as Bit Independence Criterion (BIC), periodicity, algebraic complexity, Strict Avalanche Criterion (SAC) and Distance to SAC.

Private Information Retrieval (PIR) allows several clients to query a database held by one or more servers, such that the contents of their queries remain private. Prior PIR schemes have achieved sublinear communication and computation by leveraging computational assumptions, federating trust among many servers, relaxing security to permit differentially private leakage, refactoring effort into an offline stage to reduce online costs, or amortizing costs over a large batch of queries. In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database and constant client work. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol achieves speed-ups up to and exceeding $10$x in practical settings compared to state of the art PIR protocols, and can scale to batches with hundreds of millions of queries on cheap commodity AWS machines. Our protocol builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.

We systematically study the security of twelve Beyond-Birthday-Bound Message Authentication Codes (BBB MACs) in the Q2 model where attackers have quantum-query access to MACs. Assuming the block size of the underlying (tweakable) block cipher is $n$ bits, the security proofs show that they are secure at least up to $\mathcal{O}(2^ {2n/3}) $ queries in the classical setting. The best classical attacks need $\mathcal{O}(2^ {3n/4}) $ queries. We consider secret state recovery against SUM-ECBC-like and PMAC_Plus-like MACs and key recovery against PMAC_Plus-like MACs. Both attacks lead to successful forgeries. The first attack costs $\mathcal{O}(2^{n/2}n)$ quantum queries by applying Grover-meet-Simon algorithm. The second attack costs $\mathcal{O}(2^{m/2})$ quantum queries by applying Grover's algorithm, assuming the key size of (tweakable) block cipher is $m$ bits. As far as we know, these are the first quantum attacks against BBB MACs. It is remarkable that our attacks are suitable even for some optimally secure MACs, such as mPMAC+-f, mPMAC+-p1, and mPMAC+-p2.

We implement bootstrapping of RNS-CKKS on SEAL, a homomorphic encryption library released by Microsoft. And we measure the accuracy of encrypted data after bootstrapping for various parameters, which allows us to do more than thousands of homomorphic operations.

We present the first post-quantum secure Key-Updatable Public-Key Encryption (UPKE) construction. UPKE has been proposed as a mechanism to improve the forward secrecy and post-compromise security of secure messaging protocols, but the hardness of all existing constructions rely on discrete logarithm assumptions. We focus our assessment on isogeny-based cryptosystems due to their suitability for performing a potentially unbounded number of update operations, a practical requirement for secure messaging where user conversations can occur over months, if not years. We begin by formalizing two UPKE variants in the literature as Symmetric and Asymmetric UPKE, which differ in how encryption and decryption keys are updated. We argue that Asymmetric UPKE constructions in the literature cannot be straightforwardly instantiated using SIDH nor CSIDH. We then describe a SIDH construction that partially achieves the required security notions for Symmetric UPKE, but due to existing mathematical limitations, cannot provide fine-grained forward secrecy. Finally, we present a CSIDH Symmetric UPKE construction that requires a parameter set in which the class group structure is fully known. We discuss open problems which are applicable to any cryptosystem with similar requirements for continuous operations over the secret domain.

Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a significant barrier towards deployment. Several recent works showed, however, that by introducing a one-time, per-client, off-line preprocessing phase, an \emph{unbounded} number of client queries can be subsequently served with sublinear online computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Existing preprocessing PIR schemes (supporting unbounded queries), unfortunately, make undesirable tradeoffs to achieve sublinear online computation: they are either significantly non-optimal in online time or bandwidth, %they either require %$\sqrt{n}$ or more bandwidth per query, which is asymptotically %worse than classical PIR schemes, or require the servers to store a linear amount of state per client or even per query, or require polylogarithmically many non-colluding servers. We propose a novel 2-server preprocessing PIR scheme that achieves $\widetilde{O}(\sqrt{n})$ online computation per query and $\widetilde{O}(\sqrt{n})$ client storage, while preserving the polylogarithmic online bandwidth of classical PIR schemes. Both the online bandwidth and computation are optimal up to a poly-logarithmic factor. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.

Suppose that $n$ players want to elect a random leader and they communicate by posting messages to a common broadcast channel. This problem is called leader election, and it is fundamental to the distributed systems and cryptography literature. Recently, it has attracted renewed interests due to its promised applications in decentralized environments. In a game theoretically fair leader election protocol, roughly speaking, we want that even majority coalitions cannot increase its own chance of getting elected, nor hurt the chance of any honest individual. The folklore tournament-tree protocol, which completes in logarithmically many rounds, can easily be shown to satisfy game theoretic security. To the best of our knowledge, no sub-logarithmic round protocol was known in the setting that we consider. We show that by adopting an appropriate notion of approximate game-theoretic fairness, and under standard cryptographic assumption, we can achieve $(1-1/2^{\Theta(r)})$-fairness in $r$ rounds for $\Theta(\log \log n) \leq r \leq \Theta(\log n)$, where $n$ denotes the number of players. In particular, this means that we can approximately match the fairness of the tournament tree protocol using as few as $O(\log \log n)$ rounds. We also prove a lower bound showing that logarithmically many rounds is necessary if we restrict ourselves to ``perfect'' game-theoretic fairness and protocols that are ``very similar in structure'' to the tournament-tree protocol. Although leader election is a well-studied problem in other contexts in distributed computing, our work is the first exploration of the round complexity of {\it game-theoretically fair} leader election in the presence of a possibly majority coalition. As a by-product of our exploration, we suggest a new, approximate game-theoretic fairness notion, called ``approximate sequential fairness'', which provides a more desirable solution concept than some previously studied approximate fairness notions.

Random beacon protocols provide a continuous public source of randomness and their applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols in the bounded synchronous model sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (publicly) verifiable secret sharing (PVSS/VSS) protocols. We first design a new Byzantine fault-tolerant state machine replication protocol with $O(\kappa n^2)$ bits communication per consensus decision without using threshold signatures. Next, we design GRandPiper (Good Pipelined Random beacon), a random beacon protocol with bias-resistance and unpredictability, that uses PVSS and has a communication complexity of $O(\kappa n^2)$ always (best and worst cases), for a static adversary. However, GRandPiper allows an adaptive adversary to predict beacon values up to $t+1$ epochs into the future. Therefore, we design BRandPiper (Better RandPiper), that uses VSS and has a communication complexity of $O(\kappa fn^2)$, where $f$ is the actual number of faults, while offering a strong unpredictability with an advantage of only a single round even for an adaptive adversary.

Auxiliary-input (AI) idealized models, such as auxiliary-input random oracle model (AI-ROM) and auxiliary-input random permutation model (AI-PRM), play a critical role in assessing non-uniform security of symmetric key and hash function constructions. However, obtaining security bounds in these models is often much more challenging. The presampling technique, initially introduced by Unruh (CRYPTO' 07) for AI-ROM and later exported to several other models by Coretti et al. (EUROCRYPT' 18). It generically reduces security proofs in AI models to much simpler bit-fixing (BF) models, making it much easier to obtain concrete bounds in AI models. As a result, the presampling technique has leads to simpler proofs for many known bounds (e.g. one-way functions), and has been applied to many settings where the compression technique appears intractable (e.g., Merkle-Damgard hashing). We study the possibility of leveraging the presampling technique to the quantum world. To this end, * We show that such leveraging will resolve a major open problem in quantum computing, which is closely related to the famous Aaronson-Ambainis conjecture (ITCS' 11). * Faced with this barrier, we give a new but equivalent bit-fixing model and a simple proof of presampling techniques for arbitrary oracle distribution in the classical setting, including AI-ROM and AI-PRM. Our theorem matches the best-known security loss and unifies previous presampling techniques by Coretti et al. (EUROCRYPT' 18) and Coretti et al. (CRYPTO' 18). * Finally, we leverage our new classical presampling techniques to a novel ``quantum bit-fixing'' version of presampling. It matches the optimal security loss of the classical presampling. Using our techniques, we give the first post-quantum non-uniform security for salted Merkle-Damgard hash functions and reprove the tight non-uniform security for function inversion by Chung et al. (FOCS' 20).

We define and construct Deniable Fully Homomorphic Encryption based on the Learning With Errors (LWE) polynomial hardness assumption. Deniable FHE enables storing encrypted data in the cloud to be processed securely without decryption, maintaining deniability of the encrypted data, as well the prevention of vote-buying in electronic voting schemes where encrypted votes can be tallied without decryption. Our constructions achieve compactness independently of the level of deniability- both the size of the public key and the size of the ciphertexts are bounded by a fixed polynomial, independent of the detection probability achieved by the scheme. This is in contrast to all previous constructions of deniable encryption schemes (even without requiring homomorphisms) which are based on polynomial hardness assumptions, originating with the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) in which the ciphertext size grows with the inverse of the detection probability. Canetti et al. argued that this dependence ``seems inherent'', but our constructions illustrate this is not the case. We note that the Sahai-Waters (STOC 2014) construction of deniable encryption from indistinguishability-obfuscation achieves compactness and can be easily modified to achieve deniable FHE as well, but it requires multiple, stronger sub-exponential hardness assumptions, which are furthermore not post-quantum secure. In contrast, our constructions rely only on the LWE polynomial hardness assumption, as currently required for FHE even without deniability. The running time of our encryption algorithm depends on the inverse of the detection probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability and polynomial encryption time. Yet, we believe that achieving compactness is a fundamental step on the way to achieving all properties simultaneously as has been the historical journey for other primitives such as functional encryption. Our constructions support large message spaces, whereas previous constructions were bit by bit, and can be run in online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. This results in an efficient online phase whose running time is independent of the detection probability. At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.

The notion of almost perfect nonlinear (APN) function is important, mathematically and cryptographically. Much still needs to be understood on the structure and the properties of APN functions. For instance, finding an APN permutation in an even number of variables larger than 6 would be an important theoretical and practical advance. A way to progress on a notion is to introduce and study generalizations making sense from both theoretical and practical points of view. The introduction and study of differentially uniform functions has brought more knowledge on APN functions themselves. Their notion is directly related to one of the classical characterizations of APN functions and presents an important practical interest for cryptography. In this paper we introduce and study two other generalizations of almost perfect nonlinearity, that are also related to classical characterizations of APN functions. The resulting notions are significantly different (and behave differently) from differential uniformity; they also behave differently from each other, despite the apparent similarity between their definitions. We study their satisfiability, their invariance under classical equivalence relations, their monotonicity and we characterize one of them by the Walsh transform; our results give more insight on the almost perfect nonlinearity notion itself.\\ We study the behavior of the multiplicative inverse function (which plays an important role in cryptography and in the study of finite fields) with respect to these two notions. To this aim, we find a rather simple expression of the sum of the values of this function over any affine subspace $A$ of $F_{2^n}$ not containing 0. The expression shows that such sum never vanishes (which is a remarkable property of the inverse function, which may represent a tool for attacking block ciphers using it in its S-boxes). We show that, for every $k$ not co-prime with $n$, the multiplicative inverse function sums to zero over at least one $k$-dimensional $F_2$-subspace of $F_{2^n}$. We study the behavior of the inverse function over direct sums of vector spaces and we deduce that the property of the inverse function to sum to zero over at least one $k$-dimensional $F_2$-subspace of $F_{2^n}$ happens for $k$ if and only if it happens for $n-k$. We derive several results on the sums of values of the inverse function over vector spaces and we address the cases of dimension at most 3 (equivalently, of co-dimension at most 3). We leave the other cases open.

Cryptographic tools like proof systems, multi-party computation, and fully homomorphic encryption are usually applied to computations expressed as systems of arithmetic constraints. In practice, this means that these applications rely on compilers from high-level programming languages (like C) to such constraints. This compilation task is challenging, but not entirely new: the software verification community has a rich literature on compiling programs to logical constraints (like SAT or SMT). In this work, we show that building shared compiler infrastructure for compiling to constraint representations is possible, because these representations share a common abstraction: stateless, non-uniform, non-deterministic computations that we call existentially quantified circuits, or EQCs. Moreover, we show that this shared infrastructure is useful, because it allows compilers for proof systems to benefit from decades of work on constraint compilation techniques for software verification. To make our approach concrete we create CirC, an infrastructure for building compilers to EQCs. CirC makes it easy to compile to new EQCs: we build support for three, R1CS (used for proof systems), SMT (used for verification and bug-finding), and ILP (used for optimization), in ≈2000 LOC. It's also easy to extend CirC to support new source languages: we build a feature-complete compiler for a cryptographic language in one week and ≈900 LOC, whereas the reference compiler for the same language took years to write, comprises ≈24000 LOC, and produces worse-performing output than our compiler. Finally, CirC enables novel applications that combine multiple EQCs. For example, we build the first pipeline that (1) automatically identifies bugs in programs, then (2) automatically constructs cryptographic proofs of the bugs' existence.

Semi-regular sequences over $\mathbb{F}_2$ are sequences of homogeneous elements of the algebra $ B^{(n)}=\mathbb{F}_2[X_1,...,X_n]/(X_1^2,...,X_n^2) $, which have a given Hilbert series and can be thought of as having as few relations between them as possible. It is believed that most such systems are semi-regular and this property has important consequences for understanding the complexity of Grobner basis algorithms such as F4 and F5 for solving such systems. We investigate the case where the sequence has length two and give an almost complete description of the number of semi-regular sequences for each $n$.

The potential development of large-scale quantum computers is raising concerns among IT and security research professionals due to their ability to solve (elliptic curve) discrete logarithm and integer factorization problems in polynomial time. All currently used, public-key cryptography algorithms would be deemed insecure in a post-quantum setting. In response, the United States National Institute of Standards and Technology has initiated a process to standardize quantum-resistant cryptographic algorithms, focusing primarily on their security guarantees. Additionally, the Internet Engineering Task Force has published two quantum-secure signature schemes and has been looking into adding quantum-resistant algorithms in protocols. In this work, we investigate two post-quantum, hash-based signature schemes published by the Internet Engineering Task Force and submitted to the National Institute of Standards and Technology for use in secure boot. We evaluate various parameter sets for the use-cases in question and we prove that post-quantum signatures would not have material impact on image signing. We also study the hierarchical design of these signatures in different scenarios of hardware secure boot.

We propose HERMES, a scalable, secure, and privacy-enhancing system for users to share and access vehicles. HERMES securely outsources operations of vehicle access token generation to a set of untrusted servers. It builds on an earlier proposal, namely SePCAR [1], and extends the system design for improved efficiency and scalability. To cater to system and user needs for secure and private computations, HERMES utilizes and combines several cryptographic primitives with secure multiparty computation efficiently. It conceals secret keys of vehicles and transaction details from the servers, including vehicle booking details, access token information, and user and vehicle identities. It also provides user accountability in case of disputes. Besides, we provide semantic security analysis and prove that HERMES meets its security and privacy requirements. Last but not least, we demonstrate that HERMES is efficient and, in contrast to SePCAR, scales to a large number of users and vehicles, making it practical for real-world deployments. We build our evaluations with two different multiparty computation protocols: HtMAC-MiMC and CBC-MAC-AES. Our results demonstrate that HERMES with HtMAC-MiMC requires only approx 1,83 ms for generating an access token for a single-vehicle owner and approx 11,9 ms for a large branch of rental companies with over a thousand vehicles. It handles 546 and 84 access token generations per second, respectively. This results in HERMES being 696 (with HtMAC-MiMC) and 42 (with CBC-MAC-AES) times faster compared to in SePCAR for a single-vehicle owner access token generation. Furthermore, we show that HERMES is practical on the vehicle side, too, as access token operations performed on a prototype vehicle on-board unit take only approx 62,087 ms.

Bit permutations are efficient linear functions often used for lightweight cipher designs. However, they have low diffusion effects, compared to word-oriented binary and MDS matrices. Thus, the security of bit permutation-based ciphers is significantly affected by differential and linear branch numbers (DBN and LBN) of nonlinear functions. In this paper, we introduce a widely applicable method for constructing S-boxes with high DBN and LBN. Our method exploits constructions of S-boxes from smaller S-boxes and it derives/proves the required conditions for smaller S-boxes so that the DBN and LBN of the constructed S-boxes are at least 3. These conditions enable us to significantly reduce the search space required to create such S-boxes. In order to make cryptographically good and efficient S-boxes, we propose a unbalanced-Bridge structure that accepts one 3-bit and two 5-bit S-boxes, and produces 8-bit S-boxes. Using the proposed structure, we develop a variety of new lightweight S-boxes that provide not only both DBN and LBN of at least 3 but also efficient bitsliced implementations including at most 11 nonlinear bitwise operations. The new S-boxes are the first that exhibit these characteristics. Moreover, we propose a block cipher PIPO based on one of the new S-boxes, which supports a 64-bit plaintext and a 128 or 256-bit key. Our implementations demonstrate that PIPO outperforms existing block ciphers (for the same block and key lengths) in both side-channel protected and unprotected environments, on an 8-bit AVR. The security of PIPO has been scrutinized with regards to state-of-the-art cryptanalysis.

Recently, Li and Micciancio (ePrint 2020/1533) have proposed a passive attack on the CKKS approximate homomorphic encryption (HE) scheme, which allows an adversary to query decryption on valid ciphertexts. In this paper, we discuss for which applications such attack is applicable, and introduce an extension of the HEaaN library. In addition, we investigate the mitigation strategies of other HE libraries that support the CKKS scheme including HElib, PALISADE, Lattigo and SEAL.

Existing standards for player characterisation in tokenised state machine replication protocols depend on honest players who will always follow the protocol, regardless of possible token increases for deviating. Given the ever-increasing market capitalisation of these tokenised protocols, honesty is becoming more expensive and more unrealistic. As such, this out-dated player characterisation must be removed to provide true guarantees of safety and liveness in a major stride towards universal trust in state machine replication protocols and a new scale of adoption. As all current state machine replication protocols are built on these legacy standards, it is imperative that a new player model is identified and utilised to reflect the true nature of players in tokenised protocols, now and into the future. To this effect, we propose the ByRa player model for state machine replication protocols. In the ByRa model, players either attempt to maximise their tokenised rewards, or behave adversarially. This merges the fields of game theory and distributed systems, an intersection in which tokenised state machine replication protocols exist, but on which little formalisation has been carried out. In the ByRa model, we identify the properties of strong incentive compatibility in expectation and fairness that all protocols must satisfy in order to achieve state machine replication. We then provide Tenderstake, a protocol which provably satisfies these properties, and by doing so, achieves state machine replication in the ByRa model.

Image is a visual representation of a certain fact and can be used as proof of events. As the utilization of the image increases, it is required to prove its authenticity with the protection of its sensitive personal information. In this paper, we propose a new efficient verifiable image redacting scheme based on zk-SNARKs, a commitment, and a digital signature scheme. We adopt a commit-and-prove SNARK scheme which takes commitments as inputs, in which the authenticity can be quickly verified outside the circuit. We also specify relations between the original and redacted images to guarantee the redacting correctness. Our experimental results show that the proposed scheme is superior to the existing works in terms of the key size and proving time without sacrificing the other parameters. The security of the proposed scheme is proven formally.

This paper presents an IND-CCA2 attack against the 1st- and 2nd-round versions of NTS-KEM, i.e., the versions before the update in December 2019. Our attack works against the 1st- and 2nd-round specifications, with a number of decapsulation queries upper-bounded by n &#8722; k and an advantage lower-bounded by roughly 0.5(n &#8722; k)t/n^2 , where n, k, and t stand for the code length, code dimension, and the designed decoding capacity, for all the three parameter sets of NTS-KEM. We found that the non-reference implementations are also vulnerable to our attack, even though there are bugs. There are also bugs in the reference implementations, but in a way invulnerable to our attack.

Secure multi-party computation has seen significant performance advances and increasing use in recent years. Techniques based on secret sharing offer attractive performance and are a popular choice for privacy-preserving machine learning applications. Traditional techniques operate over a field, while designing equivalent techniques for a ring $\mathbb{Z}_{2^k}$ can boost performance. In this work, we develop a suite of multi-party protocols for a ring in the honest majority setting starting from elementary operations to more complex with the goal of supporting general-purpose computation. We demonstrate that our techniques are substantially faster than their field-based equivalents when instantiated with a different number of parties and perform on par with or better than state-of-the-art techniques with designs customized for a fixed number of parties. We evaluate our techniques on machine learning applications and show that they offer attractive performance.

Secure computation is a promising privacy enhancing technology, but it is often not scalable enough for data intensive applications. On the other hand, the use of sketches has gained popularity in data mining, because sketches often give rise to highly efficient and scalable sub-linear algorithms. It is natural to ask: what if we put secure computation and sketches together? We investigated the question and the findings are interesting: we can get security, we can get scalability, and somewhat unexpectedly, we can also get differential privacy -- for free. Our study started from building a secure computation protocol based on the Flajolet-Martin (FM) sketches, for solving the Private Distributed Cardinality Estimation (PDCE) problem, which is a fundamental problem with applications ranging from crowd tracking to network monitoring. The state of art protocol for PDCE (Fenske et al. CCS'17) is computationally expensive and not scalable enough to cope with big data applications, which prompted us to design a better protocol. Our further analysis revealed that if the cardinality to be estimated is large enough, our protocol can achieve $(\epsilon,\delta)$-differential privacy automatically, without requiring any additional manipulation of the output. The result signifies a new approach for achieving differential privacy that departs from the mainstream approach (i.e. adding noise to the result). Free differential privacy can be achieved because of two reasons: secure computation minimizes information leakage, and the intrinsic estimation variance of the FM sketch makes the output of our protocol uncertain. We further show that the result is not just theoretical: the minimal cardinality for differential privacy to hold is only $10^2-10^4$ for typical parameters.

Sigfox is a popular communication and security protocol which allows setting up low-power wide-area networks for the Internet of Things. Currently, Sigfox networks operate in 72 countries, and cover 1.3 billion people. In this paper, we make an extensive analysis of the security mechanisms used to protect the radio interface. We describe news attacks against data authenticity, which is the only mandatory security property in Sigfox. Namely we describe how to replay frames, and how to compute forgeries. In addition, we highlight a flaw in the (optional) data encryption procedure. Our attacks do not exploit implementation or hardware bugs, nor do they imply a physical access to any equipment (e.g., legitimate end-device). They rely only on the peculiarities of the Sigfox security protocol. Our analysis is supported by practical experiments made in interaction with the Sigfox back-end network. These experiments validate our findings. Finally, we present efficient counter-measures which are likely straightforward to implement.

The security of PoW-based blockchains relies on the total amount of mining power and the ratio of mining power possessed by the honest miners. Loosely speaking, a system with higher mining power makes an attack more difficult. To incentivise miners joining the network and contributing their mining power, reward mechanisms are designed to provide economic profit to miners in exchange for their mining power. We identify shutdown price of mining machines as an overlooked factor that has an impact on the total mining power in the network, so the level of system security of PoW-based blockchains. We formalise the concept of shutdown price, which represents the break-even point of operating a mining machine. Once the shutdown price of a type of machines is reached, mining coins with them can be more expensive than buying coins directly in the cryptocurrency market. Therefore a rational operator would switch off these machines. This reduces the mining power in the network. However, due to the high market volatility and the coin price may recover from the break-even point quickly, the miners may delay shut down or may choose a partial shutdown strategy to hedge risk. We define and analyse such shutdown tolerance by applying real option theory. We also provide a discussion on the key factors determining shutdown price and their impact on the blockchain security.

Zero-Knowledge Proof is a crucial tool for privacy preserving and stake proving. It allows the Prover to convince the Verifier about the validity of some statement without leaking any knowledge of his own. Quantities of zero knowledge protocols have been proposed by now and one of the state-of-the-art works is Halo [1], which is brought about by Bowe, Grigg and Hopwood. Even though nested amortization technique used in Halo, the Verifier still has to compute an O(n) operation ultimately. As a result, Halo is not a fully succinct zero-knowledge scheme and infeasible to be utilized in some scenarios such as Ethereum Smart Contract applications. We propose Halo 0.9, which is an enhanced version of Halo aiming at the issue above. Specifically, we introduce the SRS in [2] as the substitute for the random vector in the inner product and thus transform the Pedersen vector commitment to Kate polynomial commitment [2]. On the premise of original Halo protocol remained, the computation of Verifier is in logarithmic time.

Zoom Meeting is an enterprise online video conferencing solution with real-time messaging and content sharing. However, they are lack of privacy protection since centralized Zoom servers are capable of monitoring user’s messages. Thereby, to solve the privacy problem, in May 2020, Zoom acquired Keybase so that Keybase’s team can help it to build end-to-end encryption meeting while remain Zoom’s current scalability and high-performance. Nonetheless, according to the latest released Zoom’s whitepaper, even with the new design of E2E(end to end) encryption meeting, the security threats can’t be erased completely since the new design is not fully decentralized. In this paper, we introduce a fully decentralized design of E2E encryption meeting via blockchain technology. With this new design, Zoom’s E2E meeting privacy can be further improved.

Hardware security tokens have now been used for several decades to store cryptographic keys. When deployed, the security of the corresponding schemes fundamentally relies on the tamper-resistance of the tokens – a very strong assumption in practice. Moreover, even secure tokens, which are expensive and cumbersome, can often be subverted. We introduce a new cryptographic primitive called Encryption schemes with Password-protected Assisted Decryption (EPAD schemes), in which a user’s decryption key is shared between a user device (or token) on which no assumption is made, and an online server. The user shares a human-memorizable password with the server. To decrypt a ciphertext, the user launches, from a public computer, a distributed protocol with the device and the server, authenticating herself to the server with her password (unknown to the device); in such a way that her secret key is never reconstructed during the interaction. We propose a strong security model which guarantees that (1) for an efficient adversary to infer any information about a user’s plaintexts, it must know her password and have corrupted her device (secrecy is guaranteed if only one of the two conditions is fulfilled), (2) the device and the server are unable to infer any information about the ciphertexts they help to decrypt (even though they could together reconstruct the secret key), and (3) the user is able to verify that device and server both performed the expected computations. These EPAD schemes are in the password-only model, meaning that the user is not required to remember a trusted public key, and her password remains safe even if she is led to interact with a wrong server and a malicious device. We then give a practical pairing-based EPAD scheme. Our construction is provably secure under standard computational assumptions, using non-interactive proof systems which can be efficiently instantiated in the standard security model, i.e., without relying on the random oracle heuristic.

We address security and privacy problems for digital devices and biometrics from an information-theoretic optimality perspective, where a secret key is generated for authentication, identification, message encryption/decryption, or secure computations. A physical unclonable function (PUF) is a promising solution for local security in digital devices and this review gives the most relevant summary for information theorists, coding theorists, and signal processing community members who are interested in optimal PUF constructions. Low-complexity signal processing methods such as transform coding that are developed to make the information-theoretic analysis tractable are discussed. The optimal trade-offs between the secret-key, privacy-leakage, and storage rates for multiple PUF measurements are given. Proposed optimal code constructions that jointly design the vector quantizer and error-correction code parameters are listed. These constructions include modern and algebraic codes such as polar codes and convolutional codes, both of which can achieve small block-error probabilities at short block lengths, corresponding to a small number of PUF circuits. Open problems in the PUF literature from a signal processing, information theory, coding theory, and hardware complexity perspectives and their combinations are listed to stimulate further advancements in the research on local privacy and security.

Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with $f < n/3$ by Berman et al. but a considerable gap remains for the authenticated setting with $n/3 \le f < n/2$. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of $f < n/2$ but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience $f \le (1/2 - \varepsilon)n$ in the standard PKI model.

We introduce compact certificate schemes, which allow any party to take a large number of signatures on a message $M$, by many signers of different weights, and compress them to a much shorter certificate. This certificate convinces the verifiers that signers with sufficient total weight signed $M$, even though the verifier will not see---let alone verify---all of the signatures. Thus, for example, a compact certificate can be used to prove that parties who jointly have a sufficient total account balance have attested to a given block in a blockchain. After defining compact certificates, we demonstrate an efficient compact certificate scheme. We then show how to implement such a scheme in a decentralized setting over an unreliable network and in the presence of adversarial parties who wish to disrupt certificate creation. Our evaluation shows that compact certificates are 50-280$\times$ smaller and 300-4000$\times$ cheaper to verify than a natural baseline approach.

Smart grid has improved the security, efficiency of the power system and balanced the supply and demand by intelligent management, which enhanced stability and reliability of power grid. The key point to achieve them is real-time data and consume data sharing by using fine-grained policies. But it will bring the leakage of the privacy of the users and losing of control over data for data owners. The reported solutions can not give the best trade-off among the privacy protection, control over the data shared and confidentiality. In addition, they can not solve the problems of large computation overhead and dynamic management such as users’ revocation. This paper aims at these problems and proposes a decentralized attribute-based data sharing scheme. The proposed scheme ensures the secure sharing of data while removing the central authority and hiding user’s identity information. It uses attribute-based signcryption(ABSC) to achieve data confidentiality and authentication. Under this model, attribute-based encryption gives the access policies for users and keeps the data confidentiality, and the attribute-based signature is used for authentication of the primary ciphertextintegrity. It is more efficient than ”encrypt and then sign” or ”sign and then encrypt”. In addition, the proposed scheme enables user’s revocation and public verifiability. Under the random oracle model, the security and the unforgeability against adaptive chosen message attack are demonstrated.

Though Mobile Cloud Computing (MCC) and Mobile Edge Computing (MEC) technologies have brought more convenience to mobile services over past few years, but security concerns like mutual authentication, user anonymity, user untraceability, etc., have yet remained unresolved. In recent years, many efforts have been made to design security protocols in the context of MCC and MEC, but most of them are prone to security threats. In this paper, we analyze Jia et al.’s scheme, one of the latest authentication protocols for MEC environment and we show this scheme is vulnerable to user impersonation and ephemeral secret leakage attacks. Further, we demonstrate that the aforementioned attacks can be similarly applied to Li et al.’s scheme which recently derived from Jia et al.’s protocol. In this paper, we propose a provably secure authenticated key agreement protocol on the basis of Jia et al.’s scheme that not only withstands security weaknesses of it, but also offers low computational and communicational costs compared to the other related schemes. As a formal security proof, we simulate our scheme with widely used AVISPA tool. Moreover, we show the scalability and practicality of our scheme in a MEC environment through NS-3 simulation.