In this paper, we propose a new public-key cryptosystem based on a quasigroup with the special property of "restricted-commutativity". We argue its security empirically and present constructions for key exchange and digital signature. To the best of our knowledge, our primitive and construction have no known polynomial-time attack from quantum computers yet. We note that quasigroups with such property had been independently proposed for use in public-key cryptography and termed "entropic" quasigroups or "entropoids" by D.Gligoroski.
Publicly Verifiable Zero-Knowledge proofs are known to exist only from setup assumptions such as a trusted Common Reference String (CRS) or a Random Oracle. Unfortunately, the former requires a trusted party while the latter does not exist. Blockchains are distributed systems that already exist and provide certain security properties (under some honest majority assumption), hence, a natural recent research direction has been to use a blockchain as an alternative setup assumption. In TCC 2017 Goyal and Goyal proposed a construction of a publicly verifiable zero-knowledge (pvZK) proof system for some proof-of-stake blockchains. The zero-knowledge property of their construction however relies on some additional and not fully specified assumptions about the current and future behavior of honest blockchain players. In this paper, we provide several contributions. First, we show that when using a blockchain to design a provably secure protocol, it is dangerous to rely on demanding additional requirements on behaviors of the blockchain players. We do so by showing an “attack of the clones” whereby a malicious verifier can use a smart contract to slyly (not through bribing) clone capabilities of honest stakeholders and use those to invalidate the zero-knowledge property of the proof system by Goyal and Goyal. Second, we propose a new publicly verifiable zero-knowledge proof system that relies on non-interactive commitments and on an assumption on the min-entropy of some blocks appearing on the blockchain. Third, motivated by the fact that blockchains are a recent innovation and their resilience in the long run is still controversial, we introduce the concept of collapsing blockchain, and we prove that the zero-knowledge property of our scheme holds even if the blockchain eventually becomes insecure and all blockchain players eventually become dishonest.
This paper presents two modifications for Loidreau’s code-based cryptosystem. Loidreau’s cryptosystem is a rank metric code-based cryptosystem constructed by using Gabidulin codes in the McEliece setting. Recently a polynomial-time key recovery attack was proposed to break Loidreau’s cryptosystem in some cases. To prevent this attack, we propose the use of subcodes to disguise the secret codes in Modification I. In Modification II, we choose a random matrix of low column rank over F q to mix with the secret matrix. According to our analysis, these two modifications can both resist the existing structural attacks. Additionally, we adopt the systematic generator matrix of the public code to make a reduction in the public-key size. In additon to stronger resistance against structural attacks and more compact representation of public keys, our modifications also have larger information transmission rates.
In the final phase of the post-quantum cryptography standardization effort, the focus has been extended to include the side-channel resistance of the candidates. While some of the schemes have been already extensively analyzed in this regard, there is no such study yet of the finalist Kyber. In this work, we demonstrate the first completely masked implementation of Kyber which is protected against first- and higher-order attacks. To the best of our knowledge, this results in the first higher-order masked implementation of any post-quantum secure key encapsulation mechanism algorithm. This is realized by introducing two new techniques. First, we propose a higher-order algorithm for the one-bit compression operation. This is based on a masked bit-sliced binary-search that can be applied to prime moduli. Second, we propose a technique which enables one to compare uncompressed masked polynomials with compressed public polynomials. This avoids the costly masking of the ciphertext compression while being able to be instantiated at arbitrary orders. We show performance results for first-, second- and third-order protected implementations on the Arm Cortex-M0+. Notably, our implementation of first-order masked Kyber decapsulation requires 12.2 million cycles. This is a factor 2.2 overhead compared to an unprotected implementation. We experimentally show that the first-order implementation of our new modules is hardened against attacks using 100,000 traces and mechanically verify the security in a fine-grained leakage model using the verification tool scVerif.
The developments in the areas of strong Physical Unclonable Functions (PUFs) predicate an ongoing struggle between designers and attackers. Such a combat motivated the atmosphere of open research, hence enhancing PUF designs in the presence of Machine Learning (ML) attacks. As an example of this controversy, at CHES 2019, a novel delay-based PUF (iPUF) has been introduced and claimed to be resistant against various ML and reliability attacks. At CHES 2020, a new divide-and-conquer modeling attack (splitting iPUF) has been presented showing the vulnerability of even large iPUF variants. Such attacks and analyses are naturally examined purely in the simulation domain, where some metrics like uniformity are assumed to be ideal. This assumption is motivated by a common belief that implementation defects (such as bias) may ease the attacks. In this paper, we highlight the critical role of uniformity in the success of ML attacks, and for the first time present a case where the bias originating from implementation defects hardens certain learning problems in complex PUF architectures. We present the result of our investigations conducted on a cluster of 100 Xilinx Artix 7 FPGAs, showing the incapability of the splitting iPUF attack to model even small iPUF instances when facing a slight non-uniformity. In fact, our findings imply that non-ideal conditions due to implementation defects should also be considered when developing an attack vector on complex PUF architectures like iPUF. On the other hand, we observe a relatively low uniqueness even when following the suggestions made by the iPUF’s original authors with respect to the FPGA implementations, which indeed questions the promised physical unclonability.
Apple's offline file-sharing service AirDrop is integrated into more than 1.5 billion end-user devices worldwide. We discovered two design flaws in the underlying protocol that allow attackers to learn the phone numbers and email addresses of both sender and receiver devices. As a remediation, we study the applicability of private set intersection (PSI) to mutual authentication, which is similar to contact discovery in mobile messengers. We propose a novel optimized PSI-based protocol called PrivateDrop that addresses the specific challenges of offline resource-constrained operation and integrates seamlessly into the current AirDrop protocol stack. Using our native PrivateDrop implementation for iOS and macOS, we experimentally demonstrate that PrivateDrop preserves AirDrop's exemplary user experience with an authentication delay well below one second. We responsibly disclosed our findings to Apple and open-sourced our PrivateDrop implementation.
With the rise of lattice cryptography, (negacyclic) convolution has received increased attention. E.g., the NTRU scheme internally employs cyclic polynomial multiplication, which is equivalent to the standard convolution, on the other hand, many Ring-LWE-based cryptosystems perform negacyclic polynomial multiplication. A method by Crandall implements an efficient negacyclic convolution over a finite field of prime order using an extended Discrete Galois Transform (DGT) – a finite field analogy to Discrete Fourier Transform (DFT). Compared to DGT, the classical DFT runs faster by an order of magnitude, however, it suffers from inevitable rounding errors due to finite floating-point number representation. In a recent Fully Homomorphic Encryption (FHE) scheme by Chillotti et al. named TFHE, small errors are acceptable (although not welcome), therefore we decided to investigate the application of DFT for negacyclic convolution. The primary goal of this paper is to suggest a method for fast negacyclic convolution over integer coefficients using an extended DFT. The key contribution is a thorough analysis of error propagation, as a result of which we derive parameter bounds that can guarantee even error-free results. We also suggest a setup that admits rare errors, which allows to increase the degree of the polynomials and/or their maximum norm at a fixed floating-point precision. Finally, we run benchmarks with parameters derived from a practical TFHE setup. We achieve around 24× better times than the generic NTL library (comparable to Crandall’s method) and around 4× better times than a na&#305;&#776;ve approach with DFT, with no errors.
Side-channel attacks can break mathematically secure cryptographic systems leading to a major concern in applied cryptography. While the cryptanalysis and security evaluation of Post-Quantum Cryptography (PQC) have already received an increasing research effort, a cost analysis of efficient side-channel countermeasures is still lacking. In this work, we propose a masked HW/SW codesign of the NIST PQC finalists Kyber and Saber, suitable for their different characteristics. Among others, we present a novel masked ciphertext compression algorithm for non-power-of-two moduli. To accelerate linear performance bottlenecks, we developed a generic Number Theoretic Transform (NTT) multiplier, which, in contrast to previously published accelerators, is also efficient and suitable for schemes not based on NTT. For the critical non-linear operations, masked HW accelerators were developed, allowing a secure execution using RISC-V instruction set extensions. Our experimental results show a cycle count reduction factor of 3.18 for Kyber (K:245k/E:319k/D:339k) and 2.66 for Saber (K:229k/E:308k/D:347k) compared to the latest optimized ARM Cortex-M4 implementations. While Saber performs slightly better for the key generation and encapsulation, Kyber has slight performance advantages for the decapsulation. The masking overhead for the first-order secure decapsulation operation including randomness generation is around 4.14 for Kyber (D:1403k) and 2.63 for Saber (D:915k).
In this work we show that an adversary can attack the integrity of contact tracing systems based on Google-Apple Exposure Notications (GAEN) by leveraging blockchain technology. We show that through smart contracts there can be an on-line market where infected individuals interested in monetizing their status can upload to the servers of the GAEN-based systems some keys (i.e., TEKs) chosen by a non-infected adversary. In particular, the infected individual can anonymously and digitally trade the upload of TEKs without a mediator and without running risks of being cheated. This vulnerability can therefore be exploited to generate large-scale fake exposure notifications of at-risk contacts with serious consequences (e.g., jeopardizing parts of the health system, affecting results of elections, imposing the closure of schools, hotels or factories). As main contribution, we design a smart contract with two collateral deposits that works, in general, on GAEN-based systems. We then also suggest the design of a more sophisticated smart contract, using DECO, that could be used to attack in a different way GAEN-based systems (i.e., this second smart contract can succeed even in case GAEN systems are repaired making ineffective the first smart contract). Our work shows how to realize with GAEN-based systems (in particular with Immuni and SwissCovid), the terrorist attack to decentralized contact tracing systems envisioned by Vaudenay.
Masking is a popular technique to protect cryptographic implementations against side-channel attacks and comes in several variants including Boolean and arithmetic masking. Some masked implementations require conversion between these two variants, which is increasingly the case for masking of post-quantum encryption and signature schemes. One way to perform Arithmetic to Boolean (A2B) mask conversion is a table-based approach first introduced by Coron and Tchulkine, and later corrected and adapted by Debraize in CHES 2012. In this work, we show both analytically and experimentally that the table-based A2B conversion algorithm proposed by Debraize does not achieve the claimed resistance against differential power analysis due to a non-uniform masking of an intermediate variable. This non-uniformity is hard to find analytically but leads to clear leakage in experimental validation. To address the non-uniform masking issue, we propose two new A2B conversions: one that maintains efficiency at the cost of additional memory and one that trades efficiency for a reduced memory footprint. We give analytical and experimental evidence for their security, and will make their implementations, which are shown to be free from side-channel leakage in 100.000 power traces collected on the ARM Cortex-M4, available online. We conclude that when designing side-channel protection mechanisms, it is of paramount importance to perform both a theoretical analysis and an experimental validation of the method.
Non-interactive zero-knowledge proofs or arguments allow a prover to show validity of a statement without further interaction. For non-trivial statements such protocols require a setup assumption in form of a common random or reference string (CRS). Generally, the CRS can only be used for one statement (single-theorem zero-knowledge) such that a fresh CRS would need to be generated for each proof. Fortunately, Feige, Lapidot and Shamir (FOCS 1990) presented a transformation for any non-interactive zero-knowledge proof system that allows the CRS to be reused any polynomial number of times (multi-theorem zero-knowledge). This FLS transformation, however, is only known to work for either computational zero-knowledge or requires a structured, non-uniform common reference string. In this paper we present FLS-like transformations that work for non-interactive statistical zero-knowledge arguments in the common random string model. They allow to go from single-theorem to multi-theorem zero-knowledge and also preserve soundness, for both properties in the adaptive and non-adaptive case. Our first transformation is based on the general assumption that one-way permutations exist, while our second transformation uses lattice-based assumptions. Additionally, we define different possible soundness notions for non-interactive arguments and discuss their relationships.
Super-spreader events where one person infects many others have been a driving force of the Covid-19 pandemic. Such events often happen indoors, such as in restaurants, at choir practice or in gyms. Many systems for automated contact tracing (ACT) have been proposed, which will warn a user when they have been in proximity to an infected person. These generally fail to detect potential super-spreader events as only users who have come in close contact with the infected person, but not others who also visited the same location, are warned. Other approaches allow users to check into locations or venues, but these require user interaction. We propose two designs how broadcast-based ACT systems can be enhanced to utilize location-specific information without the need for GPS traces or scanning of QR codes. This makes it possible to alert attendees of a potential super-spreader event while still remaining private. Our first design relies on cooperating lighthouses which cover a large area and send out pseudonyms. These are recorded by visitors and published by the health authority (HA) in case of an infection. The second design has lighthouses actively communicating with HAs after retrospectively detecting an infected visitor to warn everyone whose stay overlapped.
In this work, we present a zero knowledge argument for general arithmetic circuits that is public-coin and constant rounds, so it can be made non-interactive and publicly verifiable with the Fiat-Shamir heuristic. The construction is based on the MPC-in-the-head paradigm, in which the prover jointly emulates all MPC protocol participants and can provide advice in the form of Beaver triples whose accuracy must be checked by the verifier. Our construction follows the Beaver triple sacrificing approach used by Baum and Nof [PKC 2020]. Our improvements reduce the communication per multiplication gate from 4 to 2 field elements, matching the performance of the cut-and-choose approach taken by Katz, Kolesnikov, and Wang [CCS 2018] and with lower additive overhead for some parameter settings. We implement our protocol and analyze its cost on Picnic-style post-quantum digital signatures based on the AES family of circuits.
ROLLO is a candidate to the second round of NIST Post-Quantum Cryptography standardization process. In the last update in April 2020, there was a key encapsulation mechanism (ROLLO-I) and a public-key encryption scheme (ROLLO-II). In this paper, we propose an attack to recover the syndrome during the decapsulation process of ROLLO-I. From this syndrome, we explain how to perform a private key-recovery. We target two constant-time implementations: the C reference implementation and a C implementation available on GitHub. By getting power measurements during the execution of the Gaussian elimination function, we are able to extract on a single trace each element of the syndrome. This attack can also be applied to the decryption process of ROLLO-II.
Block ciphers have been extremely predominant in the area of cryptography and due to the paradigm shift towards devices of resource constrained nature, lightweight block ciphers have totally influenced the field and has been a go-to option ever since. The growth of resource constrained devices have put forth a dire need for the security solutions that are feasible in terms of resources without taking a toll on the security that they offer. As the world is starting to move towards Internet of Things (IoT), data security and privacy in this environment is a major concern. This is due to the reason that a huge number of devices that operate in this environment are resource constrained. Because of their resource-constrained nature, advanced mainstream cryptographic ciphers and techniques do not perform as efficiently on such devices. This has led to the boom in the field of 'lightweight cryptography' which aims at developing cryptographic techniques that perform efficiently in a resource constrained environment. Over the period of past two decades or so, a bulk of lightweight block ciphers have been proposed due to the growing need and demand in lightweight cryptography. In this paper, we review the state-of-the-art lightweight block ciphers, present a comprehensive design niche, give a detailed taxonomy with multiple classifications and present future research directions.
Many central banks, as well as blockchain systems, are looking into distributed versions of interbank payment systems, in particular the netting procedure. When executed in a distributed manner this presents a number of privacy problems. This paper studies a privacy preserving netting protocol to solve the gridlock resolution problem in such Real Time Gross Settlement systems. Our solution utilizes Multi-party Computation and is implemented in the SCALE MAMBA system, using Shamir secret sharing scheme over three parties in an actively secure manner. Our experiments show that, even for large throughput systems, such a privacy preserving operation is often feasible.
Rasta and Dasta are two fully homomorphic encryption friendly symmetric-key primitives proposed at CRYPTO 2018 and ToSC 2020, respectively. We point out that the designers of Rasta and Dasta neglected an important property of the $\chi$ operation. Combined with the special structure of Rasta and Dasta, this property directly leads to significantly improved algebraic cryptanalysis. Especially, it enables us to theoretically break 2 out of 3 instances of full Agrasta, which is the aggressive version of Rasta with the block size only slightly larger than the security level in bits. We further reveal that Dasta is more vulnerable to our attacks than Rasta for its usage of a linear layer composed of an ever-changing bit permutation and a deterministic linear transform. Based on our cryptanalysis, the security margins of Dasta and Rasta parameterized with $(n,\kappa,r)\in\{(327,80,4),(1877,128,4),(3545,256,5)\}$ are reduced to only 1 round, where $n$, $\kappa$ and $r$ denote the block size, the claimed security level and the number of rounds, respectively. These parameters are of particular interest as the corresponding ANDdepth is the lowest among those that can be implemented in reasonable time and target the same claimed security level.
In modern times, data collected from multi-user distributed applications must be analyzed on a massive scale to support critical business objectives. While analytics often requires the use of personal data, it may compromise user privacy expectations if this analysis is conducted over plaintext data. Private Stream Aggregation (PSA) allows for the aggregation of time-series data, while still providing strong privacy guarantees, and is significantly more efficient over a network than related techniques (e.g. homomorphic encryption, secure multiparty computation, etc.) due to its asynchronous and efficient protocols. However, PSA protocols face limitations and can only compute basic functions, such as sum, average, etc.. We present Cryptonomial, a framework for converting any PSA scheme amenable to a complex canonical embedding into a secure computation protocol that can compute any function over time- series data that can be written as a multivariate polynomial, by combining PSA and a Trusted Execution Environment. This design allows us to compute the parallelizable sections of our protocol outside the TEE using advanced hardware, that can take better advantage of parallelism. We show that Cryptonomial inherits the security requirements of PSA, and supports fully malicious security. We implement our scheme, and show that our techniques enable performance that is orders of magnitude faster than similar work supporting polynomial calculations.
Histograms have a large variety of useful applications in data analysis, e.g., tracking the spread of diseases and analyzing public health issues. However, most data analysis techniques used in practice operate over plaintext data, putting the privacy of users’ data at risk. We consider the problem of allowing an untrusted aggregator to privately compute a histogram over multiple users’ private inputs (e.g., number of contacts at a place) without learning anything other than the final histogram. This is a challenging problem to solve when the aggregators and the users may be malicious and collude with each other to infer others’ private inputs, as existing black box techniques incur high communication and computational overhead that limit scalability. We address these concerns by building a novel, efficient, and scalable protocol that intelligently combines a Trusted Execution Environment (TEE) and the Durstenfeld-Knuth uniformly random shuffling algorithm to update a mapping between buckets and keys by using a deterministic cryptographically secure pseudorandom number generator. In addition to being provably secure, experimental evaluations of our technique indicate that it generally outperforms existing work by several orders of magnitude, and can achieve performance that is within one order of magnitude of protocols operating over plaintexts that do not offer any security.
This paper presents a unified approach to quantifying the information leakages in the most general code-based masking schemes. Specifically, by utilizing a uniform representation, we highlight first that all code-based masking schemes' side-channel resistance can be quantified by an all-in-one framework consisting of two easy-to-compute parameters (the dual distance and the number of conditioned codewords) from a coding-theoretic perspective. In particular, we use signal-to-noise ratio (SNR) and mutual information (MI) as two complementary metrics, where a closed-form expression of SNR and an approximation of MI are proposed by connecting both metrics to the two coding-theoretic parameters. Secondly, considering the connection between Reed-Solomon code and SSS (Shamir's Secret Sharing) scheme, the SSS-based masking is viewed as a particular case of generalized code-based masking. Hence as a straightforward application, we evaluate the impact of public points on the side-channel security of SSS-based masking schemes, namely the polynomial masking, and enhance the SSS-based masking by choosing optimal public points for it. Interestingly, we show that given a specific security order, more shares in SSS-based masking leak more information on secrets in an information-theoretic sense. Finally, our approach provides a systematic method for optimizing the side-channel resistance of every code-based masking. More precisely, this approach enables us to select optimal linear codes (parameters) for the generalized code-based masking by choosing appropriate codes according to the two coding-theoretic parameters. Summing up, we provide a best-practice guideline for the application of code-based masking to protect cryptographic implementations.
This article describes some approaches to bounding non-minimum weight differentials (EDP) and linear hulls (ELP) in 2-round LSX-cipher. We propose a dynamic programming algorithm to solve this problem. For 2-round Kuznyechik the nontrivial upper bounds on all differentials (linear hulls) with $18$ and $19$ active Sboxes was obtained. These estimates are also holds for other differentials (linear hulls) with a larger number of active Sboxes. We obtain a similar result for 2-round Khazad. As a consequence, the exact value of the maximum expected differential (linear) probability (MEDP/MELP) was computed for this cipher.
In this work we apply the dynamical systems analysis of Hanrot et al. (CRYPTO'11) to a class of lattice block reduction algorithms that includes (natural variants of) slide reduction and block-Rankin reduction. This implies sharper bounds on the polynomial running times (in the query model) for these algorithms and opens the door to faster practical variants of slide reduction. We give heuristic arguments showing that such variants can indeed speed up slide reduction significantly in practice. This is confirmed by experimental evidence, which also shows that our variants are competitive with state-of-the-art reduction algorithms.
In this paper I propose a new key agreement scheme applying a well-known property of powers to a particular couple of elements of the cyclic group generated by a primitive root of a prime p. The model, whose security relies on the difficulty of computing discrete logarithms when p is a “safe prime”, consists of a five-step process providing explicit key authentication.
Current permissionless cryptocurrencies such as Bitcoin suffer from a limited transaction rate and slow confirmation time, which hinders further adoption. Payment channels are one of the most promising solutions to address these problems, as they allow the parties of the channel to perform arbitrarily many payments in a peer-to-peer fashion while uploading only two transactions on the blockchain. This concept has been generalized into payment channel networks where a path of payment channels is used to settle the payment between two users that might not share a direct channel between them. However, this approach requires the active involvement of each user in the path, making the system less reliable (they might be offline), more expensive (they charge fees per payment), and slower (intermediaries need to be actively involved in the payment). To mitigate this issue, recent work has introduced the concept of virtual channels (IEEE S\&P'19), which involve intermediaries only in the initial creation of a bridge between payer and payee, who can later on independently perform arbitrarily many off-chain transactions. Unfortunately, existing constructions are only available for Ethereum, as they rely on its account model and Turing-complete scripting language. The realization of virtual channels in other blockchain technologies with limited scripting capabilities, like Bitcoin, was so far considered an open challenge. In this work, we present the first virtual channel protocols that are built on the UTXO-model and require a scripting language supporting only a digital signature scheme and a timelock functionality, being thus backward compatible with virtually every cryptocurrency, including Bitcoin. We formalize the security properties of virtual channels as an ideal functionality in the Universal Composability framework and prove that our protocol constitutes a secure realization thereof. We have prototyped and evaluated our protocol on the Bitcoin blockchain, demonstrating its efficiency: for n sequential payments, they require an off-chain exchange of 9+2n transactions or a total of 3524+695n bytes, with no on-chain footprint in the optimistic case. This is a substantial improvement compared to routing payments in a payment channel network, which requires 8n transactions with a total of 3026n bytes to be exchanged.
This paper proposes tweakable block cipher (TBC) based modes $\mathsf{PFB\_Plus}$ and $\mathsf{PFB}\omega$ that are efficient in threshold implementations (TI). Let $t$ be an algebraic degree of a target function, e.g.~$t=1$ (resp.~$t>1$) for linear (resp.~non-linear) function. The $d$-th order TI encodes the internal state into $d t + 1$ shares. Hence, the area size increases proportionally to the number of shares. This implies that TBC based modes can be smaller than block cipher (BC) based modes in TI because TBC requires $s$-bit block to ensure $s$-bit security, e.g. \textsf{PFB} and \textsf{Romulus}, while BC requires $2s$-bit block. However, even with those TBC based modes, the minimum we can reach is 3 shares of $s$-bit state with $t=2$ and the first-order TI ($d=1$). Our first design $\mathsf{PFB\_Plus}$ aims to break the barrier of the $3s$-bit state in TI. The block size of an underlying TBC is $s/2$ bits and the output of TBC is linearly expanded to $s$ bits. This expanded state requires only 2 shares in the first-order TI, which makes the total state size $2.5s$ bits. We also provide rigorous security proof of $\mathsf{PFB\_Plus}$. Our second design $\mathsf{PFB}\omega$ further increases a parameter $\omega$: a ratio of the security level $s$ to the block size of an underlying TBC. We prove security of $\mathsf{PFB}\omega$ for any $\omega$ under some assumptions for an underlying TBC and for parameters used to update a state. Next, we show a concrete instantiation of $\mathsf{PFB\_Plus}$ for 128-bit security. It requires a TBC with 64-bit block, 128-bit key and 128-bit tweak, while no existing TBC can support it. We design a new TBC by extending \textsf{SKINNY} and provide basic security evaluation. Finally, we give hardware benchmarks of $\mathsf{PFB\_Plus}$ in the first-order TI to show that TI of $\mathsf{PFB\_Plus}$ is smaller than that of \textsf{PFB} by more than one thousand gates and is the smallest within the schemes having 128-bit security.
In this short paper, we provide protocols to batch and aggregate multiple non-membership proofs into a single proof of constant size with bilinear accumulators. We subsequently use the accumulator to construct a bilinear Vector Commitment with constant sized openings and a linear public parameter. Furthermore, we have designed the protocols so that the Verifier needs a constant amount of storage for verification despite the linear public parameter. We also provide ways to speed up the verification of membership and non-membership proofs and to shift most of the computational burden from the Verifier to the Prover. Since all the protocols are public coin, they can be made non-interactive with a Fiat-Shamir heuristic.
Broadcast (BC) is a crucial ingredient for a plethora of cryptographic protocols such as secret sharing and multiparty computation. In this paper we apply \emph{gossiping} (propagating a message by sending to a few random parties who in turn do the same, until the message is delivered) to design new randomized BC protocols with improved communication complexity and which are secure against an adversary controlling the majority of parties. We make progress on two fronts. First, we propose a protocol for single-sender BC in the static model of corruption that achieves $\tilde O(n^2 \cdot \kappa^2)$ bits of communication and where no trusted setup is required---parties just need to generate their own cryptographic keys. All prior protocols in this setting exhibit $ O(n^3 \cdot \kappa)$ communication. Using insights from our single-sender BC protocol, we then propose the first adaptively-secure parallel BC protocol with $\tilde O(n^2 \cdot \kappa^4)$ communication complexity, significantly improving existing parallel BC protocols of $\tilde O(n^3)$ communication. To the best of our knowledge, our parallel BC protocol is the first non-trivial one, i.e., one that is not using a single-sender BC protocol $n$ times and in a black box fashion, thus leading to the improved complexity.
One can bootstrap LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose a fast bootstrapping method for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by Ducas and Micciancio (EUROCRYPT 2015) can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that, using around 400 MB of key material, runs in less than one second in a common personal computer.
In a recent eprint, Rahman and Shpilrain proposed a Diffie-Hellman style key exchange based on a semidirect product of $n × n$-matrices over a finite field. We show that, using public information, an adversary can recover the agreed upon secret key by solving a system of $n^2$ linear equations.
Ed25519 has significant performance benefits compared to ECDSA using Weierstrass curves such as NIST P-256, therefore it is considered a good digital signature algorithm, specially for low performance IoT devices. However, such devices often have very limited resources and thus, implementations for these devices need to be as small and as performant as possible while being secure. In this paper we describe a scenario in which an obvious strategy to aggressively optimize an Ed25519 implementation for code size leads to a small memory footprint that is functionally correct but vulnerable to side-channel attacks. This strategy serves as an example of aggressive optimizations that might be considered by cryptography engineers, developers, and practitioners unfamiliar with the power of Side-Channel Analysis (SCA). As a solution to the flawed implementation example, we use a computer-aided cryptography tool generating formally verified finite field arithmetic to generate two secure Ed25519 implementations fulfilling different size requirements. After benchmarking and comparing these implementations to other widely used implementations our results show that computer-aided cryptography is capable of generating competitive code in terms of security, speed, and size.
A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. The collection of authorized/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,1\}$. In this paper, we focus on monotone functions that all their min-terms are sets of size $a$, and on their duals -- monotone functions whose max-terms are of size $b$. We refer to these classes as $(a,n)$-upslices and $(b,n)$-downslices, and note that these natural families correspond to monotone $a$-regular DNFs and monotone $(n-b)$-regular CNFs. We derive the following results. 1. (General downslices) Every downslice can be realized with total share size of $1.5^{n+o(n)}<2^{0.585 n}$. Since every monotone function can be cheaply decomposed into $n$ downslices, we obtain a similar result for general access structures improving the previously known $2^{0.637n+o(n)}$ complexity of Applebaum, Beimel, Nir and Peter (STOC 2020). We also achieve a minor improvement in the exponent of linear secrets sharing schemes. 2. (Random mixture of upslices) Following Beimel and Farras (TCC 2020) who studied the complexity of random DNFs with constant-size terms, we consider the following general distribution $F$ over monotone DNFs: For each width value $a\in [n]$, uniformly sample $k_a$ monotone terms of size $a$, where $k=(k_1,\ldots,k_n)$ is an arbitrary vector of non-negative integers. We show that, except with exponentially small probability, $F$ can be realized with share size of $2^{0.5 n+o(n)}$ and can be linearly realized with an exponent strictly smaller than $2/3$. Our proof also provides a candidate distribution for ``exponentially-hard'' access structure. We use our results to explore connections between several seemingly unrelated questions about the complexity of secret-sharing schemes such as worst-case vs. average-case, linear vs. non-linear and primal vs. dual access structures. We prove that, in at least one of these settings, there is a significant gap in secret-sharing complexity.
Private stream aggregation (PSA) allows an untrusted data aggregator to compute statistics over a set of multiple participants' data while ensuring the data remains private. Existing works rely on a trusted third party to enable an aggregator to achieve fault tolerance, that requires interactive recovery, but in the real world this may not be practical or secure. We develop a new formal framework for PSA that accounts for user faults, and can support non-interactive recovery, while still supporting strong individual privacy guarantees. We first must define a new level of security in the presence of faults and malicious adversaries because the existing definitions do not account for faults and the security implications of the recovery. After this we develop the first protocol that provably reaches this level of security, i.e., individual inputs are private even after the aggregator's recovery, and reach new levels of scalability and communication efficiency over existing work seeking to support fault tolerance. The techniques we develop are general, and can be used to augment any PSA scheme to support non-interactive fault recovery.
The algebraic structures that are non-commutative and non-associative known as entropic groupoids that satisfy the "Palintropic" property i.e., $x^{\mathbf{A} \mathbf{B}} = (x^{\mathbf{A}})^{\mathbf{B}} = (x^{\mathbf{B}})^{\mathbf{A}} = x^{\mathbf{B} \mathbf{A}}$ were proposed by Etherington in '40s from the 20th century. Those relations are exactly the Diffie-Hellman key exchange protocol relations used with groups. The arithmetic for non-associative power indices known as Logarithmetic was also proposed by Etherington and later developed by others in the 50s-70s. However, as far as we know, no one has ever proposed a succinct notation for exponentially large non-associative power indices that will have the property of fast exponentiation similarly as the fast exponentiation is achieved with ordinary arithmetic via the consecutive rising to the powers of two. In this paper, we define ringoid algebraic structures $(G, \boxplus, *)$ where $(G, \boxplus) $ is an Abelian group and $(G, *)$ is a non-commutative and non-associative groupoid with an entropic and palintropic subgroupoid which is a quasigroup, and we name those structures as Entropoids. We further define succinct notation for non-associative bracketing patterns and propose algorithms for fast exponentiation with those patterns. Next, by an analogy with the developed cryptographic theory of discrete logarithm problems, we define several hard problems in Entropoid based cryptography, such as Discrete Entropoid Logarithm Problem (DELP), Computational Entropoid Diffie-Hellman problem (CEDHP), and Decisional Entropoid Diffie-Hellman Problem (DEDHP). We post a conjecture that DEDHP is hard in Sylow $q$-subquasigroups. Next, we instantiate an entropoid Diffie-Hellman key exchange protocol. Due to the non-commutativity and non-associativity, the entropoid based cryptographic primitives are supposed to be resistant to quantum algorithms. At the same time, due to the proposed succinct notation for the power indices, the communication overhead in the entropoid based Diffie-Hellman key exchange is very low: for 128 bits of security, 64 bytes in total are communicated in both directions, and for 256 bits of security, 128 bytes in total are communicated in both directions. Our final contribution is in proposing two entropoid based digital signature schemes. The schemes are constructed with the Fiat-Shamir transformation of an identification scheme which security relies on a new hardness assumption: computing roots in finite entropoids is hard. If this assumption withstands the time's test, the first proposed signature scheme has excellent properties: for the classical security levels between 128 and 256 bits, the public and private key sizes are between 32 and 64, and the signature sizes are between 64 and 128 bytes. The second signature scheme reduces the finding of the roots in finite entropoids to computing discrete entropoid logarithms. In our opinion, this is a safer but more conservative design, and it pays the price in doubling the key sizes and the signature sizes. We give a proof-of-concept implementation in SageMath 9.2 for all proposed algorithms and schemes in an appendix.
Modern distributed systems involve interactions between principals with limited trust, so cryptographic mechanisms are needed to protect confidentiality and integrity. At the same time, most developers lack the training to securely employ cryptography. We present Viaduct, a compiler that transforms high-level programs into secure, efficient distributed realizations. Viaduct's source language allows developers to declaratively specify security policies by annotating their programs with information flow labels. The compiler uses these labels to synthesize distributed programs that use cryptography efficiently while still defending the source-level security policy. The Viaduct approach is general, and can be easily extended with new security mechanisms. Our implementation of the Viaduct compiler comes with an extensible runtime system that includes plug-in support for multiparty computation, commitments, and zero-knowledge proofs. We have evaluated the system on a set of benchmarks, and the results indicate that our approach is feasible and can use cryptography in efficient, nontrivial ways.
We analyze the security of the TLS 1.3 key establishment protocol, as specified at the end of its rigorous standardization process. We define a core key-schedule and reduce its security to concrete assumptions against an adversary that controls client and server configurations and adaptively chooses some of their keys. Our model supports all key derivations featured in the standard, including its negotiated modes and algorithms that combine an optional Diffie-Hellman exchange for forward secrecy with optional pre-shared keys supplied by the application or recursively established in prior sessions. We show that the output keys are secure as soon as any of their input key materials are. Our compositional, code-based proof makes use of state separation to yield concrete reductions despite the complexity of the key schedule. We also discuss (late) changes to the standard that would improve its robustness and simplify its analysis.
This paper proposes the first cache timing side-channel attacks on one of Apple's mobile devices. Utilizing a recent, permanent exploit named checkm8, we reverse-engineered Apple's BootROM and created a powerful toolkit for running arbitrary hardware security experiments on Apple's in-house designed ARM systems-on-a-chip (SoC). We integrate two additional open-source tools to enhance our own toolkit, further increasing its capability for hardware security research. Using this toolkit, which is a core contribution of our work, we then implement both time-driven and access-driven cache timing attacks as proof-of-concept illustrators. In both cases, we propose statistical innovations which further the state-of-the-art in cache timing attacks. We find that our access-driven attack, at best, can reduce the security of OpenSSL AES-128 to merely 25 bits, while our time-driven attack (with a much weaker adversary) can reduce it to 48 bits. We also quantify that access-driven attacks on the A10 which do not use our statistical improvements are unable to deduce the key, and that our statistical technique reduces the traces needed by the typical time-driven attacks by 21.62 million.
Recent publications consider side-channel attacks against the key schedule of the Data Encryption Standard (DES). These publications identify a leakage model depending on the XOR of register values in the DES key schedule. Building on this leakage model, we first revisit a discrete model which assumes that the Hamming distances between subsequent round keys leak without error. We analyze this model formally and provide theoretical explanations for observations made in previous works. Next we examine a continuous model which considers more points of interest and also takes noise into account. The model gives rise to an evaluation function for key candidates and an associated notion of key ranking. We develop an algorithm for enumerating key candidates up to a desired rank which is based on the Fincke–Pohst lattice point enumeration algorithm. We derive information-theoretic bounds and estimates for the remaining entropy and compare them with our experimental results. We apply our attack to side-channel measurements of a security controler. Using our enumeration algorithm we are able to significantly improve the results reported previously for the same measurement data.
Post-quantum cryptography has known a Cambrian explosion in the last decade. What started as a very theoretical and mathematical area has now evolved into a sprawling research field, complete with side-channel resistant embedded implementations, large scale deployment tests and standardization efforts. This study systematizes the current state of knowledge on post-quantum cryptography. Compared to existing studies, we adopt a transversal point of view and center our study around three areas: (i) paradigms, (ii) implementation, (iii) deployment. Our point of view allows to cast almost all classical and post-quantum schemes into just a few paradigms. We highlight trends, common methodologies, and pitfalls to look for and recurrent challenges.
Masking schemes are among the most popular countermeasures against Side-Channel Analysis (SCA) attacks. Realization of masked implementations on hardware faces several difficulties including dealing with glitches. Threshold Implementation (TI) is known as the first strategy with provable security in presence of glitches. In addition to the desired security order d, TI defines the minimum number of shares to also depend on the algebraic degree of the target function. This may lead to unaffordable implementation costs for higher orders. For example, at least five shares are required to protect the smallest nonlinear function against second-order attacks. By cutting such a dependency, the successor schemes are able to achieve the same security level by just $d+1$ shares, at the cost of high demand for fresh randomness, particularly at higher orders. In this work, we provide a methodology to realize the second-order glitch-extended probing-secure implementation of a group of quadratic functions with three shares and no fresh randomness. This allows us to construct second-order secure implementations of several cryptographic primitives with very limited number of fresh masks, including Keccak, SKINNY, Midori, PRESENT, and PRINCE.
In recent years, deep learning has become an attractive ingredient to side-channel analysis (SCA) due to its potential to improve the success probability or enhance the performance of certain frequently executed tasks. One task that is commonly assisted by machine learning techniques is the profiling of a device's leakage behavior in order to carry out a template attack. At CHES 2019, deep learning has also been applied to non-profiled scenarios for the first time, extending its reach within SCA beyond template attacks. The proposed method, called DDLA, has some tempting advantages over traditional SCA due to merits inherited from (convolutional) neural networks. Most notably, it greatly reduces the need for pre-processing steps when the SCA traces are misaligned or when the leakage is of a multivariate nature. However, similar to traditional attack scenarios the success of this approach highly depends on the correct choice of a leakage model and the intermediate value to target. In this work we explore, for the first time in literature, whether deep learning can similarly be used as an instrument to advance another crucial (non-profiled) discipline of SCA which is inherently independent of leakage models and targeted intermediates, namely leakage assessment. In fact, given the simple classification-based nature of common leakage assessment techniques, in particular distinguishing two groups fixed-vs-random or fixed-vs-fixed, it comes as a surprise that machine learning has not been brought into this context, yet. Our contribution is the development of the first full leakage assessment methodology based on deep learning. It gives the evaluator the freedom to not worry about location, alignment and statistical order of the leakages and easily covers multivariate and horizontal patterns as well. We test our approach against a number of case studies based on FPGA, ASIC and µC implementations of the PRESENT block cipher, equipped with state-of-the-art SCA countermeasures. Our results clearly show that the proposed methodology and network structures are robust across all case studies and outperform the classical detection approaches ($t$-test and $\chi^2$-test) in all considered scenarios.
There is a difference between a system having no known attacks and the system being secure---as cryptographers know all too well. Once we begin talking about the implementations of systems this issue becomes even more prominent since the amount of material which needs to be scrutinised skyrockets. Historically, lack of transparency and low standards for e-voting system implementations have resulted in a culture where open source code is seen as a gold standard; however, this ignores the issue of the comprehensibility of that code. In this work we make concrete empirical recommendations based on our, and others, experiences and findings from examining the source code of e-voting systems. We highlight that any solution used for significant elections should be well designed, carefully analysed, deftly built, accurately documented and expertly maintained. Until e-voting system implementations are clear, comprehensible, and open to public scrutiny security standards are unlikely to improve.
Public key encryption with keyword search (PEKS) is first introduced by Boneh et al. enabling a cloud server to search on encrypted data without leaking any information of the keyword. In almost all PEKS schemes, the privacy of trapdoor is vulnerable to inside keyword guessing attacks (KGA), i.e., the server can generate the ciphertext by its own and then run the test algorithm to guess the keyword contained in the trapdoor. To sole this problem, Huang et al. proposed the public-key authenticated encryption with keyword search (PAEKS) achieving trapdoor privacy (TP) security, in which data sender not only encrypts the keyword but also authenticates it by using his/her secret key. Qin et al. introduced the notion of multi-ciphertext indistinguishability (MCI) security to capture outside chosen multi-ciphertext attacks, in which the adversary needs to distinguish two tuples of ciphertexts corresponding with two sets of keywords. They analysed that Huang's work cannot achieve MCI security, so they proposed an improved scheme to match both the MCI security and trapdoor privacy (TP) security. In addition, they also defined the notion of multi-trapdoor privacy (MTP) security, which requires to distinguish two tuples of trapdoors corresponding with two sets of keywords. Unfortunately, trapdoor generation algorithms of all above works are deterministic, which means they are unable to capture the security requirement of MTP. How to achieve MTP security against inside multi-keyword guessing attacks,i.e., designing a probabilistic trapdoor generation algorithm, is still an open problem. In this paper, we solve this problem. We initially propose two public-key authenticated encryption with keyword search schemes achieving both MCI security and MTP security simultaneously. We provide formal proof of our schemes in the random oracle model.
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.
Election verifiability is defined in the computational model of cryptography. The definition formalizes notions of voters verifying their own votes, auditors verifying the tally of votes, and auditors verifying that only eligible voters vote. The Helios (Adida et al., 2009), Helios-C (Cortier et al., 2014) and JCJ (Juels et al., 2010) election schemes are analyzed using the definition. Neither Helios nor Helios-C satisfy the definition because they do not ensure that recorded ballots are tallied in certain cases when the adversary posts malicious material on the bulletin board. A variant of Helios is proposed and shown to satisfy the definition. JCJ similarly does not ensure that recorded ballots are tallied in certain cases. Moreover, JCJ does not ensure that only eligible voters vote, due to a trust assumption it makes. A variant of JCJ is proposed and shown to satisfy a weakened definition that incorporates the trust assumption. Previous definitions of verifiability (Juels et al., 2010; Cortier et al., 2014; Kiayias et al., 2015) and definitions of global verifiability (Kuesters et al., 2010; Cortier et al., 2016) are shown to permit election schemes vulnerable to attacks, whereas the new definition prohibits those schemes. And a relationship between the new definition and a variant of global verifiability is shown.
We propose a definition of ballot secrecy as an indistinguishability game in the computational model of cryptography. Our definition improves upon earlier definitions to ensure ballot secrecy is preserved in the presence of an adversary that controls ballot collection. We also propose a definition of ballot independence as an adaptation of an indistinguishability game for asymmetric encryption. We prove relations between our definitions. In particular, we prove ballot independence is sufficient for ballot secrecy in voting systems with zero-knowledge tallying proofs. Moreover, we prove that building voting systems from non-malleable asymmetric encryption schemes suffices for ballot secrecy, thereby eliminating the expense of ballot-secrecy proofs for a class of encryption-based voting systems. We demonstrate applicability of our results by analysing the Helios voting system and its mixnet variant. Our analysis reveals that Helios does not satisfy ballot secrecy in the presence of an adversary that controls ballot collection. The vulnerability cannot be detected by earlier definitions of ballot secrecy, because they do not consider such adversaries. We adopt non-malleable ballots as a fix and prove that the fixed system satisfies ballot secrecy.
In this work, we consider executions of smart contracts for implementing secure multi-party computation (MPC) protocols on forking blockchains (e.g., Ethereum), and we study security and delay issues due to forks. In this setting, the classical double-spending problem tells us that messages of the MPC protocol should be confirmed on-chain before playing the next ones, thus slowing down the entire execution. Our contributions are twofold: - For the concrete case of fairly tossing multiple coins with penalties, we notice that the lottery protocol of Andrychowicz et al. (S&P '14) becomes insecure if players do not wait for the confirmations of several transactions. In addition, we present a smart contract that instead retains security even when all honest players immediately answer to transactions appearing on-chain. We analyze the performance using Ethereum as testbed. - We design a compiler that takes any ``digital and universally composable'' MPC protocol (with or without honest majority), and transforms it into another one (for the same task and same setup) which maintains security even if all messages are played on-chain without delays. The special requirements on the starting protocol mean that messages consist only of bits (e.g., no hardware token is sent) and security holds also in the presence of other protocols. We further show that our compiler satisfies fairness with penalties as long as honest players only wait for confirmations once. By reducing the number of confirmations, our protocols can be significantly faster than natural constructions.
To factor an integer $N$ we construct $n$ triples of $p_n$-smooth integers $u,v,|u-vN|$ for the $n$-th prime $p_n$. Denote such triple a fac-relation. We get fac-relations from a nearly shortest vector of the lattice $\mathcal{L}(\mathbf{R}_{n,f})$ with basis matrix $\mathbf{R}_{n,f} \in \mathbb{R}^{(n+1)\times (n+1)}$ where $f : [1,n] \rightarrow [1,n]$ is a permutation of $[1,2,...,n]$ and $(f(1),...,f(n), N'\ln N)$ is the diagonal and (N'\ln p_1, \ldots, N'\ln p_n, N'\ln N) for $N'=N^{\frac{1}{n+1}}$ is the last line of $\mathbf{R}_{n,f}$. An independent permutation $f'$ yields an independent fac-relation. We find sufficiently short lattice vectors by strong primal-dual reduction of $\mathbf{R}_{n,f}$. We factor $N \approx 2^{400}$ by $n = 47$ and $N \approx 2^{800}$ by $n = 95$. Our accelerated strong primal-dual reduction of [Gama, Nguyen 2008] factors integers $N \approx 2^{400}$ and $N \approx 2^{800}$ by $4.2 \cdot 10^9$ and $8.4 \cdot 10^{10}$ arithmetic operations, much faster then the quadratic sieve and the number field sieve and using much smaller primes $p_n$. This destroys the RSA cryptosystem.
Cryptocurrency exchange services are either trusted central entities that have been routinely hacked (losing over 8 billion USD), or decentralized services that make all orders public before they are settled. The latter allows market participants to ``front run'' each other, an illegal operation in most jurisdictions. We extend the ``Insured MPC'' approach of Baum et al. (FC 2020) to construct an efficient universally composable privacy preserving decentralized exchange where a set of servers run private cross-chain exchange order matching in an outsourced manner, while being financially incentivised to behave honestly. Our protocol allows for exchanging assets over multiple public ledgers, given that users have access to a ledger that supports standard public smart contracts. If parties behave honestly, the on-chain complexity of our construction is as low as that of performing the transactions necessary for a centralized exchange. In case malicious behavior is detected, users are automatically refunded by malicious servers at low cost. Thus, an actively corrupted majority can only mount a denial-of-service attack that makes exchanges fail, in which case the servers are publicly identified and punished, while honest clients do not to lose their funds. For the first time in this line of research, we report experimental results on the MPC building block, showing the approach is efficient enough to be used in practice.
In recent years, smartphones have become an increasingly important storage facility for personal sensitive data ranging from photos and credentials up to financial and medical records like credit cards and person’s diseases. Trivially, it is critical to secure this information and only provide access to the genuine and authenticated user. Smartphone vendors have already taken exceptional care to protect user data by the means of various software and hardware security features like code signing, authenticated boot chain, dedicated co-processor and integrated cryptographic engines with hardware fused keys. Despite these obstacles, adversaries have successfully broken through various software protections in the past, leaving only the hardware as the last standing barrier between the attacker and user data. In this work, we build upon existing software vulnerabilities and break through the final barrier by performing the first publicly reported physical Side-Channel Analysis (SCA) attack on an iPhone in order to extract the hardware-fused device-specific User Identifier (UID) key. This key – once at hand – allows the adversary to perform an offline brute-force attack on the user passcode employing an optimized and scalable implementation of the Key Derivation Function (KDF) on a Graphics Processing Unit (GPU) cluster. Once the passcode is revealed, the adversary has full access to all user data stored on the device and possibly in the cloud. As the software exploit enables acquisition and processing of hundreds of millions of traces, this work further shows that an attacker being able to query arbitrary many chosen-data encryption/decryption requests is a realistic model, even for compact systems with advanced software protections, and emphasizes the need for assessing resilience against SCA for a very high number of traces.
Cuckoo Hashing is a dictionary data structure in which a data item is stored in a small constant number of possible locations. It has the appealing property that the data structure size is a small constant times larger than the combined size of all inserted data elements. However, many applications, especially cryptographic applications and Oblivious RAM, require insertions, builds and accesses to have a negligible failure probability, which standard Cuckoo Hashing cannot simultaneously achieve. An alternative proposal introduced by Kirsch et al. is to store elements which cannot be placed in the main table in a ``stash'', reducing the failure probability to $O(n^{-s})$ where $n$ is the table size and $s$ any constant stash size. This failure probability is still not negligible. Goodrich and Mitzenmacher showed that the failure probability can be made negligible in some parameter $N$ when $n = \Omega(log^7(N))$ and $s = \Theta(log N)$. In this paper, I will explore these analyses, as well as the insightful alternative analysis of Aumüller et al. Following this, I present a tighter analysis which shows failure probability negligible in $N$ for all $n = \omega(\log(N))$ (which is asymptotically optimal) and I present explicit constants for the failure probability upper bound.
Leakage assessment of cryptographic implementations with side-channel analysis relies on two important assumptions: leakage model and the number of side-channel traces. In the context of profiled side-channel attacks, having these assumptions correctly defined is a sufficient first step to evaluate the security of a crypto implementation with template attacks. This method assumes that the features (leakages or points of interest) follow a univariate or multi-variate Gaussian distribution for the estimation of the probability density function. When trained machine learning or neural network models are employed as classifiers for profiled attacks, a third assumption must be taken into account that it the correctness of the trained model or learning parameters. It was already proved that convolutional neural networks have advantages for side-channel analysis like bypassing trace misalignments and defeating first-order masking countermeasures in software implementations. However, if this trained model is incorrect and the test classification accuracy is close to random guessing, the correctness of the two first assumptions (number of traces and leakage model) will be insufficient and the security of the target under evaluation can be overestimated. This could lead to wrong conclusions in leakage certifications. One solution to verify if the trained model is acceptable relies on the identifying of input features that the neural network considers as points of interest. In this paper, we implement the assessment of neural network models by using the proposed backward propagation path method. Our method is employed during the profiling phase as a tool to verify what the neural network is learning from side-channel traces and to support the optimization of hyper-parameters. The method is tested against masked AES implementation. One of the main results highlights the importance of L2 regularization for the automated points of interest selection from a neural network.
The optimization of the main key compression bottlenecks of the supersingular isogeny key encapsulation mechanism (SIKE) has been a target of research in the last few years. Significant improvements were introduced in the recent works of Costello et al. and Zanon et al. The combination of the techniques in previous works reduced the running time of binary torsion basis generation in decompression by a factor of 29 compared to previous work. On the other hand, generating such a basis still takes almost a million cycles on an Intel Core i5-6267U Skylake. In this paper, we continue the work of Zanon et al. and introduce a technique that drops the complexity of binary torsion basis generation by a factor log p in the number of underlying field multiplications. In particular, our experimental results show that a basis can be generated in about 1,300 cycles, attaining an improvement by a factor more than 600. Although this result eliminates one of the key compression bottlenecks, many other bottlenecks remain. In addition, we give further improvements for the ternary torsion generation with significant impact on the related decompression procedure. Moreover, a new trade-off between ciphertext sizes vs decapsulation speed and storage is introduced and achieves a 1.7 times faster decapsulation.
In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In S\&P 2019 the ``Ouroboros Crypsinous'' system of Kerber et al.\ (and concurrently Ganesh et al.\ in EUROCRYPT 2019) presented a mechanism that hides the identity of the stakeholder when adding blocks, hence preserving anonymity of stakeholders both during payment and mining in the Ouroboros blockchain. They focus on anonymizing the messages of the blockchain protocol, but suggest that potential identity leaks from the network-layer can be removed as well by employing anonymous broadcast channels. In this work we show that this intuition is flawed. Even ideal anonymous broadcast channels do not suffice to protect the identity of the stakeholder who proposes a block. We make the following contributions. First, we show a formal network-attack against Ouroboros Crypsinous, where the adversary can leverage network delays to distinguish who is the stakeholder that added a block on the blockchain. Second, we abstract the above attack and show that whenever the adversary has control over the network delay -- within the synchrony bound -- loss of anonymity is inherent for any protocol that provides liveness guarantees. We do so, by first proving that it is impossible to devise a (deterministic) state-machine replication protocol that achieves basic liveness guarantees and better than $(1-2\f)$ anonymity at the same time (where $\f$ is the fraction of corrupted parties). We then connect this result to the PoS setting by presenting the tagging and reverse tagging attack that allows an adversary, across several executions of the PoS protocol, to learn the stake of a target node, by simply delaying messages for the target. We demonstrate that our assumption on the delaying power of the adversary is realistic by describing how our attack could be mounted over the Zcash blockchain network (even when Tor is used). We conclude by suggesting approaches that can mitigate such attacks.
Design-hiding techniques are a central piece of academic and industrial efforts to protect electronic circuits from being reverse-engineered. However, these techniques have lacked a principled foundation to guide their design and security evaluation, leading to a long line of broken schemes. In this paper, we begin to lay this missing foundation. We establish formal syntax for design-hiding (DH) schemes, a cryptographic primitive that encompasses all known design-stage methods to hide the circuit that is handed to a (potentially adversarial) foundry for fabrication. We give two security notions for this primitive: function recovery (FR) and key recovery (KR). The former is the ostensible goal of design-hiding methods to prevent reverse-engineering the functionality of the circuit, but most prior work has focused on the latter. We then present the first provably (FR,KR)-secure DH scheme, $OneChaff_{hd}$. A side-benefit of our security proof is a framework for analyzing a broad class of new DH schemes. We finish by unpacking our main security result, to provide parameter-setting guidance.
Fully homomorphic encryption (FHE) allows to compute any function on encrypted values. However, in practice, there is no universal FHE scheme that is efficient in all possible use cases. In this work, we show that FHE schemes suitable for arithmetic circuits (e.g. BGV or BFV) have a similar performance as FHE schemes for non-arithmetic circuits (TFHE) in basic comparison tasks such as less-than, maximum and minimum operations. Our implementation of the less-than function in the HElib library is up to 3 times faster than the prior work based on BGV/BFV. It allows to compare a pair of 64-bit integers in 11 milliseconds, sort 64 32-bit integers in 19 seconds and find the minimum of 64 32-bit integers in 9.5 seconds on an average laptop without multi-threading.
The cloud changed the way we manage and store data. Today, cloud storage services offer clients an infrastructure that allows them a convenient source to store, replicate, and secure data online. However, with these new capabilities also come limitations, such as lack of transparency, limited decentralization, and challenges with privacy and security. And, as the need for more agile, private and secure data solutions continues to grow exponentially, rethinking the current structure of cloud storage is mission-critical for enterprises. By leveraging and building upon blockchain’s unique attributes, including immutability, security to the data element level, distributed (no single point of failure), we have developed a solution prototype that allows data to be reliably stored while simultaneously being secured, with tamper-evident auditability, via blockchain. The result, Audita, is a flexible solution that assures data protection and solves challenges such as scalability and privacy. Audita works via an augmented blockchain network of participants that include storage-nodes and block-creators. In addition, it provides an automatic and fair challenge system to assure that data is distributed and reliably and provably stored. While the prototype is built on Quorum, the solution framework can be used with any blockchain platform. The benefit is a system that is built to grow along with the data needs of enterprises, while continuing to build the network via incentives and solving for issues such as auditing and outsourcing.
Complex machine learning (ML) inference algorithms like recurrent neural networks (RNNs) use standard functions from math libraries like exponentiation, sigmoid, tanh, and reciprocal of square root. Although prior work on secure 2-party inference provides specialized protocols for convolutional neural networks (CNNs), existing secure implementations of these math operators rely on generic 2-party computation (2PC) protocols that suffer from high communication. We provide new specialized 2PC protocols for math functions that crucially rely on lookup-tables and mixed-bitwidths to address this performance overhead; our protocols for math functions communicate up to 423x less data than prior work. Some of the mixed bitwidth operations used by our math implementations are (zero and signed) extensions, different forms of truncations, multiplication of operands of mixed-bitwidths, and digit decomposition (a generalization of bit decomposition to larger digits). For each of these primitive operations, we construct specialized 2PC protocols that are more communication efficient than generic 2PC, and can be of independent interest. Furthermore, our math implementations are numerically precise, which ensures that the secure implementations preserve model accuracy of cleartext. We build on top of our novel protocols to build SIRNN, a library for end-to-end secure 2-party DNN inference, that provides the first secure implementations of an RNN operating on time series sensor data, an RNN operating on speech data, and a state-of-the-art ML architecture that combines CNNs and RNNs for identifying all heads present in images. Our evaluation shows that SIRNN achieves up to three orders of magnitude of performance improvement when compared to inference of these models using an existing state-of-the-art 2PC framework.
In the current crypto paradigm a single secret key transforms a plaintext into a ciphertext and vice versa, or at most a different key is doing the reverse action. Attackers exposed to the ciphertext are hammering it to extract that single key and the plaintext. This paradigm may be challenged with an alternate setup: using a particular crypto algorithm, there is an infinite number of keys that are perfectly interchangeable -- each has the same effect. Nonetheless they are hard to find. And unlike regular cryptography, the best an attacker can hope for using this new "Family Key Cryptography”, is to identify the entire infinitely large family of keys, not the actual key that executed the cryptographic action. This very fact is a cornerstone for a host of applications, mostly still to be unfolded. E.g.: (1) Community Cryptography, where each member has a different key, but the community will encrypt and decrypt as if sharing the same key; (2) 'Forever Key Cryptography': crashing the Shannon's limit, the Forever Key strategy will allow a single finite key to last indefinitely. The shared secret key will be used to derive a succession of operating keys, which will be replaced before they are being compromised. Since any cryptanalysis of usage will end up with an infinite list of key candidates, there will be equal number of candidates for the shared "Forever Key", and thus there will be no erosion in the secrecy of the Forever Key regardless of its level of use. The very idea of infinite number of interchangeable keys is so fundamentally different, that most of its applications are still unknown.
Data trading is an emerging business, in which data sellers provide buyers with, for example, their private datasets and get paid from buyers. In many scenarios, sellers prefer to sell pieces of data, such as statistical results derived from the dataset, rather than the entire dataset. Meanwhile, buyers wish to hide the results they retrieve. Since it is not preferable to rely on a trusted third party (TTP), we are wondering, in the absence of TTP, whether there exists a \emph{practical} mechanism satisfying the following requirements: the seller Sarah receives the payment if and only if she \emph{obliviously} returns the buyer Bob the \emph{correct} evaluation result of a function delegated by Bob on her dataset, and Bob can only derive the result for which he pays. Despite a lot of attention data trading has received, a \emph{desirable} mechanism for this scenario is still missing. This is due to the fact that general solutions are inefficient when the size of datasets is considerable or the evaluated function is complicated, and that existing efficient cryptographic techniques cannot fully capture the features of our scenario or can only address very limited computing tasks. In this paper, we propose the \emph{first desirable} mechanism that is practical and supports a wide variety of computing tasks --- evaluation of arbitrary functions that can be represented as polynomials. We introduce a new cryptographic notion called \emph{blind polynomial evaluation} and instantiate it with an explicit protocol. We further combine this notion with the blockchain paradigm to provide a \emph{practical} framework that can satisfy the requirements mentioned above.
Proofs of partial knowledge demonstrate the possession of certain subsets of witnesses for a given collection of statements $x_1,\dots,x_n$. Cramer, Damg{\aa}rd, and Schoenmakers (CDS), built proofs of partial knowledge, given ``atomic'' protocols for individual statements $x_i$, by having the prover randomly secret share the verifier's challenge and using the shares as challenges for the atomic protocols. This simple and highly-influential transformation has been used in numerous applications, ranging from anonymous credentials to ring signatures. We consider what happens if, instead of using the shares directly as challenges, the prover first hashes them. We show that this elementary enhancement can result in significant benefits: \begin{itemize} \item the proof contains a {\em single} atomic transcript per statement $x_i$, \item it suffices that the atomic protocols are $\kappa$-special sound for $\kappa \geq 2$, \item when compiled to a signature scheme using the Fiat-Shamir heuristic, its unforgeability can be proved in the {\em non-programmable} random oracle model. \end{itemize} None of the above features is satisfied by the CDS transformation.
In the past 30 years, lattice reduction has proved to be one powerful tool of public-key cryptanalysis. Since the advent of the Hidden Number Problem, there has been an extensive study on attacks on (EC)DSA with nonce leakage. While lattice attacks require only a few signatures, it can't deal with small nonce bias compared with Bleichenbacher attack. Prior to this work, it is unknown how to utilize more signatures to improve lattice attacks on (EC)DSA. In this paper, we propose several approaches to improve lattice attacks. The key idea is that we can guess some bits of the secret key(or the nonces) and modify the standard lattice to increase the volume, thus making the lattice attack much easier. Besides, we observe that by filtering some specific signatures we are able to modify the lattice, so we can collect a large number of signatures and construct a lattice that is much easier to attack. With a combination of these techniques, we are able to improve lattice attacks on (EC)DSA. On the one hand, we are able to attack 160-bit modulus(and other modulus as well) (EC)DSA with 2-bit leakage within $2^{15}$ BKZ-30 operations with 90 signatures. On the other hand, with $2^{27}$ signatures available, we are able to attack 160-bit (EC)DSA with 2-bit leakage in just one BKZ-30 operation. As a second contribution, we give an explanation for several questions unexplained in previous works. It was observed that SVP approaches(Kannan embedding) always outperform CVP approaches(nearest plane) and lattice attack is very sensitive to the Kannan Embedding factor, but these questions are not discussed in previous works. We give an explanation for completeness. Last, we carry out some experiments on the TPM-Fail dataset. While the original attack utilizes around 40000 signatures, with a combination of our method, we are able to recover the secret with only 800 signatures available.
We introduce a new technique called `Measure-Rewind-Measure' (MRM) to achieve tighter security proofs in the quantum random oracle model (QROM). We first apply our MRM technique to derive a new security proof for a variant of the `double-sided' quantum One-Way to Hiding Lemma (O2H) of Bindel et al. [TCC 2019] which, for the first time, avoids the square-root advantage loss in the security proof. In particular, it bypasses a previous `impossibility result' of Jiang, Zhang and Ma [IACR eprint 2019]. We then apply our new O2H Lemma to give a new tighter security proof for the Fujisaki-Okamoto transform for constructing a strong (INDCCA) Key Encapsulation Mechanism (KEM) from a weak (INDCPA) public-key encryption scheme satisfying a mild injectivity assumption.
Transparency logs are designed to help users audit untrusted servers. For example, Certificate Transparency (CT) enables users to detect when a compromised Certificate Authority (CA) has issued a fake certificate. Practical state-of-the-art transparency log systems, however, suffer from high monitoring costs when used for low-latency applications. To reduce monitoring costs, such systems often require users to wait an hour or more for their updates to take effect, inhibiting low-latency applications. We propose $\text{Merkle}^2$, a transparency log system that supports both efficient monitoring and low-latency updates. To achieve this goal, we construct a new multi-dimensional, authenticated data structure that nests two types of Merkle trees, hence the name of our system, $\text{Merkle}^2$. Using this data structure, we then design a transparency log system with efficient monitoring and lookup protocols that enables low-latency updates. In particular, all the operations in $\text{Merkle}^2$ are independent of update intervals and are (poly)logarithmic to the number of entries in the log. $\text{Merkle}^2$ not only has excellent asymptotics when compared to prior work, but is also efficient in practice. Our evaluation shows that $\text{Merkle}^2$ propagates updates in as little as 1 second and can support 100× more users than state-of-the-art transparency logs.
Cryptanalysis based on deep learning has become a hotspot in the international cryptography community since it was proposed. The key point of differential cryptanalysis based on deep learning is to find a neural differential distinguisher with longer rounds or higher probability. Therefore it is important to research how to improve the accuracy and the rounds of neural differential distinguisher. In this paper, we design SAT-based algorithms to find a good input difference so that the accuracy of the neural distinguisher can be improved as high as possible. As applications, we search and obtain the neural differential distinguishers of 9-round SIMON32/64, 10-round SIMON48/96 and 11-round SIMON64/128. For SIMON48/96, we choose $(0x0,0x100000)$ as the input difference and train 9-round and 10-round neural distinguishers of SIMON48/96. In addition, with the automatic search based on SAT, we extend the neural 9-round, 10-round distinguishers to 11-round, 12-round distinguishers by prepending the optimal 2-round differential transition $(0x400000,0x100001) \xrightarrow{2^{-4}}\left( 0x0,0x100000 \right)$. Based on the 11-round and 12-round neural distinguisher, we complete a 14-round key recovery attack of SIMON48/96. Our attack takes about 1550s to recover the final subkey. Its average time complexity is no more than $2^{22.21}$ 14-round encryption of SIMON48/96, and the data complexity is about $2^{12.8}$. Similar to 14-round key recovery attack, we perform 13-round key recovery attack for SIMON32/64 with input difference $(0x0,0x80)$ with a success rate of more than 90$\%$. It takes about 23s to complete an attack with the data complexity no more than $2^{12.5}$ and the time complexity no more than $2^{16.4}$. It is worth mentioning that the attacks are practical for 13-round SIMON32/64 and 14-round SIMON48/96.
Sharding technology is becoming a promising candidate to address the scalability issues in blockchain. The key concept behind sharding technology is to partition the network status into multiple distinct smaller committees, each of which handles a disjoint set of transactions to leverage its capability of parallel processing. However, when introducing sharding technology to blockchain, several key challenges need to be resolved, such as security and heterogeneity among the participating nodes. This paper introduces RepShard, a reputation-based blockchain sharding scheme that aims to achieve both linearly scaling efficiency and system security simultaneously. RepShard adopts a two-layer hierarchical chain structure, consisting of a reputation chain and independent transaction chains. Each transaction chain is maintained within its shard to record transactions, while the reputation chain is maintained by all shards to update the reputation score of each participating node. We leverage a novel reputation scheme to record each participating node's integrated and valid contribution to the system, in which we consider the heterogeneity of participating nodes (e.g., computational resources). The reputation score used in sharding and leader election processes maintains the balance and security of each shard. RepShard relies on verifiable relay transactions for cross-shard transactions to ensure consistency between distinct shards. By integrating reputation into the sharding protocol, our scheme can offer both scalability and security at the same time.
Reliable and verifiable public randomness is not only an essential building block in various cryptographic primitives, but also is a critical component in many distributed and decentralized protocols, e.g., blockchain sharding. A 'good' randomness generator should preserve several distinctive properties, such as public-verifiability, bias-resistance, unpredictability, and availability. However, it is a challenging task to generate such good randomness. For instance, a dishonest party may behave deceptively to bias the final randomness, which is toward his preferences. And this challenge is more serious in a distributed and decentralized system. Blockchain technology provides several promising features, such as decentralization, immutability, and trustworthiness. Due to extremely high overheads on both communication and computation, most existing solutions face an additional scalability issue. We propose a sharding-based scheme, RandChain, to obtain a practical scalable distributed and decentralized randomness attested by blockchain in large-scale applications. In RandChain, we eliminate the use of computation-heavy cryptographic operations, e.g., Publicly Verifiable Secret Sharing (PVSS), in prevalent approaches. We build a sub-routine, RandGene, which utilizes a commit-then-reveal strategy to establish local randomness, enforced by efficient Verifiable Random Function (VRF). RandGene generates the randomness based on statistical approaches, instead of cryptographic operations, to eliminate computational operations. RandChain maintains a two-layer hierarchical chain structure via a sharding scheme. The first level chain is maintained by RandGene within each shard to provide a verifiable randomness source by blockchain. The second level chain uses the randomnesses from each shard to build a randomness chain.
Process industries cover a wide set of industries, in which the processes are controlled by a combination of Distributed Control Systems (DCSs) and Programmable Logic Controllers (PLCs). These control systems utilize various measurements such as pressure, flow, and temperature to determine the state of the process and then use field devices such as valves and other actuating devices to manipulate the process. Since there are many different types of field devices and since each device is calibrated to its specific installation, when monitoring devices, it is important to be able to transfer not only the device measurement and diagnostics, but also characteristics about the device and the process in which it is installed. The current monitoring architecture however creates challenges for continuous monitoring and analysis of diagnostic data. In this paper, we present the design of an Industrial IoT system for supporting large-scale and continuous device condition monitoring and analysis in process control systems. The system design seamlessly integrates existing infrastructure (e.g., HART and WirelessHART networks, and DeltaV DCS) and newly developed hardware/software components (e.g., one-way data diode, IoT cellular architecture) together for control network data collection and streaming of the collected device diagnostic parameters to a private cloud to perform streaming data analytics designed for fault identification and prediction. A prototype system has been developed and supported by Emerson Automation Solutions and deployed in the field for design validation and long-term performance evaluation. To the best of our knowledge, this is the first ever publicly reported effort on IoT system design for process automation applications. The design can be readily extended for condition monitoring and analysis of many other industrial facilities and processes.
We study the memory-tightness of security reductions in public-key cryptography, focusing in particular on Hashed ElGamal. We prove that any straightline (i.e., without rewinding) black-box reduction needs memory which grows linearly with the number of queries of the adversary it has access to, as long as this reduction treats the underlying group generically. This makes progress towards proving a conjecture by Auerbach et al. (CRYPTO 2017), and is also the first lower bound on memory-tightness for a concrete cryptographic scheme (as opposed to generalized reductions across security notions). Our proof relies on compression arguments in the generic group model.
We investigate the efficiency of a (module-)LWR-based PRF built using the GGM design. Our construction enjoys the security proof of the GGM construction and the (module-)LWR hardness assumption which is believed to be post-quantum secure. We propose GGM-based PRFs from PRGs with larger ratio of output to input. This reduces the number of PRG invocations which improves the PRF performance and reduces the security loss in the GGM security reduction. Our construction bridges the gap between practical and provably secure PRFs. We demonstrate the efficiency of our construction by providing parameters achieving at least 128-bit post-quantum security and optimized implementations utilizing AVX2 vector instructions. Our PRF requires, on average, only 39.4 cycles per output byte.
Verifiable Secret-Sharing (VSS) is a fundamental primitive in secure distributed computing. It is used as an important building block in several distributed computing tasks, such as Byzantine agreement and secure multi-party computation. VSS has been widely studied in various dimensions over the last three decades and several important results have been achieved related to the fault-tolerance, round-complexity and communication efficiency of VSS schemes. In this article, we consider VSS schemes with perfect security, tolerating computationally unbounded adversaries. We comprehensively survey the existing perfectly-secure VSS schemes in three different settings, namely synchronous, asynchronous and hybrid communication settings and provide the full details of each of the existing schemes in these settings. The aim of this survey is to provide a clear knowledge and foundation to researchers who are interested in knowing and extending the state-of-the-art perfectly-secure VSS schemes.
Three-party key exchange, where two clients aim to agree a session key with the help of a trusted server, is prevalent in present-day systems. In this paper, we present a practical and secure three-party password-based authenticated key exchange protocol over ideal lattices. Aside from hash functions our protocol does not rely on external primitives in the construction and the security of our protocol is directly relied on the Ring Learning with Errors (RLWE) assumption. Our protocol attains provable security. A proof-of-concept implementation shows our protocol is indeed practical.
The Fiat-Shamir with Aborts paradigm of Lyubashevsky (Asiacrypt’09) has given rise to efficient lattice-based signature schemes. One popular implementation is Dilithium which is a finalist in an ongoing standardization process run by the NIST. An interesting research question is whether it is possible to combine several unrelated signatures, issued from different signing parties on different messages, into one single aggregated signature. Of course, its size should be much smaller than the trivial concatenation of all signatures. Ideally, the aggregation can be done offline by a third party, called public aggregation. Doröz et al. (IACR eprint 2020/520) proposed a first lattice-based aggregate signature scheme allowing public aggregation. However, its security is based on the hardness of the Partial Fourier Recovery problem, a structured lattice problem which neither benefits from worst-to-average reductions nor wasn’t studied extensively from a cryptanalytic point of view. In this work we give a first instantiation of an aggregate signature allowing public aggregation whose hardness is proven in the aggregate independent-chosen-key model assuming the intractability of two well-studied problems on module lattices: The Module Learning With Errors problem (M-LWE) and the Module Short Integer Solution problem (M-SIS). Both benefit from worst-case to average-case hardness reductions. The security model we use is a more restricted variant of the original aggregate chosen-key model. Our protocol can be seen as an aggregated variant of Dilithium. Alternatively, it can be seen as a transformation of the protocol from Doröz et al. to the M-LWE/M-SIS framework.
Distributed randomness is very useful for many applications, such as smart contract, proof-of-stake-based blockchain, elliptic curve generation and lottery. Randomness beacon protocols are proposed, which are aimed at continuously distributed randomness generation. However, a reliable source of distributed randomness is gained with difficulty because of Byzantine behavior, which may lead to bias for distributed randomness. These Byzantine behaviors include, but not limited to, the “last actor” problem, DoS attack and collusion attack. Various cryptography schemes have been used to generate distributed randomness. Current constructions face challenging obstacles due to high complexity and bias problems. Given these barriers, we propose a new protocol that is the first precept to utilize attribute-based encryption in a commit-and-reveal scheme for distributed randomness (ABERand). Compared to existing public distributed randomness protocols, ABERand possesses distinguished flexibility, security and efficiency. It is primarily because of trading space for time. More specifically, we resolve the “last actor” problem and make ABERand an intensive out- put randomness beacon with communication complexity O(n3), computation complexity O(1), verification complexity O(n) and communication complexity O(n) of nodes adding/removing.
SIDH/SIKE-style protocols benefit from key compression to minimize their bandwidth requirements, but proposed key compression mechanisms rely on computing bilinear pairings. Pairing computation is a notoriously expensive operation, and, unsurprisingly, it is typically one of the main efficiency bottlenecks in SIDH key compression, incurring processing time penalties that are only mitigated at the cost of trade-offs with precomputed tables. We address this issue by describing how to compress isogeny-based keys without pairings. As a bonus, we also substantially reduce the storage requirements of other operations involved in key compression.
ForkAE is a family of authenticated encryption (AE) schemes using a forkcipher as a building block. ForkAE was published in Asiacrypt'19 and is a second-round candidate in the NIST lightweight cryptography process. ForkAE comes in several modes of operation: SAEF, PAEF, and rPAEF. SAEF is optimized for authenticated encryption of short messages and processes the message blocks in a sequential and online manner. SAEF requires a smaller internal state than its parallel sibling PAEF and is better fitted for devices with smaller footprint. At SAC 2020 it was shown that SAEF is also an online nonce misuse-resistant AE (OAE) and hence offers enhanced security against adversaries that make blockwise adaptive encryption queries. It has remained an open question if SAEF resists attacks against blockwise adaptive decryption adversaries, or more generally when the decrypted plaintext is released before the verification (RUP). RUP security is a particularly relevant security target for lightweight (LW) implementations of AE schemes on memory-constrained devices or devices with stringent real-time requirements. Surprisingly, very few NIST lightweight AEAD candidates come with any provable guarantees against RUP. In this work, we show that the SAEF mode of operation of the ForkAE family comes with integrity guarantees in the RUP setting. The RUP integrity (INT-RUP) property was defined by Andreeva et~al.~in Asiacrypt'14. Our INT-RUP proof is conducted using the coefficient H technique and it shows that, without any modifications, SAEF is INT-RUP secure up to the birthday bound, i.e., up to $2^{n/2}$ processed data blocks, where $n$ is the block size of the forkcipher. The implication of our work is that SAEF is indeed RUP secure in the sense that the release of unverified plaintexts will not impact its ciphertext integrity.
ForkAE is a NIST lightweight cryptography candidate that uses the forkcipher primitive in two modes of operation -- SAEF and PAEF -- optimized for authenticated encryption of the shortest messages. SAEF is a sequential and online AEAD that minimizes the memory footprint compared to its alternative parallel mode PAEF, catering to the most constrained devices. SAEF was proven AE secure against nonce-respecting adversaries. Due to their more acute and direct exposure to device misuse and mishandling, in most use cases of lightweight cryptography, nonce reuse presents a very realistic attack vector. Furthermore, many lightweight applications mandate security for their online AEAD schemes against block-wise adversaries. Surprisingly, very few NIST lightweight AEAD candidates come with provable guarantees against these security threats. In this work, we investigate the provable security guarantees of SAEF when nonces are repeated under a refined version of the notion of online authenticated encryption OAE given by Fleischmann et al. in 2012. We apply Using the coefficient H technique we show that, with no modifications, SAEF is OAE secure up to the birthday security bound, i.e., up to $2^{n/2}$ processed blocks of data, where $n$ is the block size of the forkcipher. The implications of our work are that SAEF is safe to use in a block-wise fashion, and that if nonces get repeated, this has no impact on ciphertext integrity and confidentiality only degrades by a limited extent up to repetitions of common message prefixes.
At EUROCRYPT 2021, Bao et al. proposed an automatic method for systematically exploring the configuration space of meet-in-the-middle (MITM) preimage attacks. We further extend it into a constraint-based framework for finding exploitable MITM characteristics in the context of key-recovery and collision attacks by taking the subtle peculiarities of both scenarios into account. Moreover, to perform attacks based on MITM characteristics with nonlinear constrained neutral words, which have not been seen before, we present a procedure for deriving the solution spaces of neutral words without solving the corresponding nonlinear equations or increasing the overall time complexities of the attack. We apply our method to concrete symmetric-key primitives, including SKINNY, ForkSkinny, Romulus, Saturnin, Grostl, Whirlpool, and hashing modes with AES-256. As a result, we identify the first 23-round key-recovery attack on SKINNY-$n$-$3n$ and the first 24-round key-recovery attack on ForkSkinny-$n$-$3n$ in the single-key model with extremely low memories. Moreover, improved (pseudo) preimage or collision attacks on round-reduced Whirlpool, Grostl, and hashing modes with AES-256 are obtained. In particular, employing the new representation of the AES key schedule due to Leurent and Pernot (EUROCRYPT 2021), we identify the first preimage attack on 10-round AES-256.
CSURF (CSIDH on the surface) was recently proposed by Castryck, and Decru in PQCrypto-2020, and then improved by the radical isogeny formulae in Asiacrypt-2020. The main advantage of using CSURF and radical isogenies is the possibility of using isogenies of degree two and radical isogeny chains of odd degree requiring only a single random sampling of points. This work addresses the practical implications of a constant-time implementation of CSURF and the radical isogeny procedures. In particular, this paper introduces the first constant-time formulation and implementation of the radical isogenies using projective representation, which are twice as efficient as the original radical isogeny formulae. Nevertheless, the overhead introduced by going to constant-time is significant: in terms of finite field operations, our experiments illustrate that the speed-up of using a constant-time CSURF-512 is reduced to 1.64% in comparison to the fastest state-of-the-art constant-time CSIDH-512 implementation. Furthermore, these savings disappear when using constant-time radical isogenies and when moving to higher parameter sets. This negatively answers the open question from Castryck and Decru: constant-time CSIDH implementations outperform both CSURF and radical isogenies.
Trusted execution enviroments (TEEs) enable secure execution of program on untrusted hosts and cryptographically attest the correctness of outputs. As these are complex systems, it is hard to capture the exact security achieved by protocols employing TEEs. Crucially TEEs are typically employed in multiple protocols at the same time, thus composable security (with global subroutines) is a natural goal for such systems. We show that under an attested execution setup G_att we can realise cryptographic functionalities that are unrealizable in the standard model. We propose a new primitive of Functional Encryption for Stateful and Randomised functionalities (FESR) and an associated protocol, Steel, that realizes it. We show that Steel UC-realises FESR in the universal composition with global subroutines model (TCC 2020). Our work is also a validation of the compositionality of earlier work (Iron), CCS 2017) capturing (non-stateful) hardware-based functional encryption. As the existing functionality for attested execution of Pass et al. (Eurocrypt 2017) is too strong for real world use, we propose a weaker functionality that allows the adversary to conduct rollback and forking attacks. We show that the stateful variant of Steel, contrary to the stateless variant corresponding to Iron, is not secure in this setting and propose several mitigation techniques.
In a public-key threshold encryption scheme, the sender produces a single ciphertext, and any $t+1$ out of $n$ intended recipients can combine their partial decryptions to obtain the plaintext. Ad hoc threshold encryption (ATE) schemes require no correlated setup, enabling each party to simply generate its own key pair. In this paper, we initiate a systematic study of the possibilities and limitations of ad-hoc threshold encryption, and introduce a key application to scalable multiparty computation (MPC). Assuming indistinguishability obfuscation (iO), we construct the first ATE that is sender-compact - that is, with ciphertext length independent of $n$. This allows for succinct communication once public keys have been shared. We also show a basic lower bound on the extent of key sharing: every sender-compact scheme requires that recipients of a message know the public keys of other recipients in order to decrypt. We then demonstrate that threshold encryption that is ad hoc and homomorphic can be used to build efficient large-scale fault-tolerant multiparty computation (MPC) on a minimal (star) communication graph. We explore several homomorphic schemes, in particular obtaining one iO-based ATE scheme that is both sender-compact and homomorphic: each recipient can derive what they need for evaluation from a single short ciphertext. In the resulting MPC protocol, once the public keys have been distributed, all parties in the graph except for the central server send and receive only short messages, whose size is independent of the number of participants. Taken together, our results chart new possibilities for threshold encryption and raise intriguing open questions.
In the quantum random oracle model, the adversary may make quantum superposition queries to the random oracle. Since even a single query can potentially probe exponentially many points, classical proof techniques are hard to be applied. For example, recording the oracle queries seemed difficult. In 2018, Mark Zhandry showed that, despite the apparent difficulties, it is in fact possible to ‘record’ the quantum queries. He has defined the compressed oracle, which is indistinguishable from the quantum random oracle, and records information the adversary has gained through the oracle queries. It is a technically subtle work, which we believe to be a challenging work to grasp fully. Our aim is to obtain a mathemathically clean, simple reinterpretation of the compressed oracle technique. For each partial function, we define what we call the formation and the completion of that partial function. The completions describe what happens to the real quantum random oracle, and the formations describe what happens to the compressed oracle. We will show that the formations are 'isomorphic' to the completions, giving an alternative proof that the compressed oracle is indistinguishable from the quantum random oracle.
In recent years, the conventional power grid system has been streamlined towards Smart grid infrastructure that empowers two-way communication between the consumers and the utility providers. This however also makes the grid more susceptible towards faults as well as physical and cyber attacks. In this work, we propose a Physically Unclonable Function (PUF) and Blockchain based detection and prevention mechanism to secure the Smart grid system against such faults and adversarial threats. In this context, we discuss a recently proposed Manipulation of demand via IoT (MadIoT) attacks, False Data Injection Attacks (FDIA) via Smart meters and Electric Fault Attacks (EFA) on Smart grid which can lead to localized blackout, falsified load forecasting, imbalance in demand-response, generator tripping, frequency instability and loss of equipment. To detect these threats and to trace back to the source of such attacks, we inspect the potential of the promising blockchain technology which gives a mechanism to authenticate and ensure the integrity of real power consumption information. However, the blockchain needs to be augmented with a root-of-trust, to bind the Smart meter with a unique hardware fingerprint. This can be achieved through Physically Unclonable Functions (PUFs) which is considered to be an unconventional cryptographic primitive and used for keyless authentication. The proposed PUF based authentication scheme would further prevent the system from injection of any false data by an illegitimate Smart meter that aids to false power estimation. The novelty of the proposed work is to blend these two technologies in developing a robust and secure framework which detects and prevents all of the above mentioned security vulnerabilities and can be easily integrated with the Smart grid infrastructure. Finally an end-to-end demonstration of the attack has been presented using MATLAB and Power World simulator and the proposed framework has been prototyped using commercial off-the-shelf products such as Raspberry Pi and Artix 7 FPGA along with an in-house blockchain simulator.
Proxy signature is a kind of digital signature, in which a user called original signer can delegate his signing rights to another user called proxy signer and the proxy signer can sign messages on behalf of the original signer. Certificateless proxy signature (CLPS) means proxy signature in the certificateless setting in which there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. Up to now, a number of CLPS schemes have been proposed, but some of those schemes either lack formal security analysis or turn out to be insecure and others are less efficient because of using costly operations including bilinear pairings and map-to-point hashing on elliptic curve groups. In this paper, we formalize the definition and security model of CLPS schemes. We then construct a pairing-free CLPS scheme from the standard ECDSA and prove its security in the random oracle model under the discrete semi-logarithm problem’s hardness assumption as in the provable security result of ECDSA.
Newly designed block ciphers are required to show resistance against known attacks, e.g., linear and differential cryptanalysis. Two widely used methods to do this are to employ an automated search tool (e.g., MILP, SAT/SMT, etc.) and/or provide a wide-trail argument. In both cases, the core of the argument consists of bounding the transition probability of the statistical property over an isolated non-linear operation, then multiply it by the number of such operations (e.g., number of active S-boxes). In this paper we show that in the case of linear cryptanalysis such strategies can sometimes lead to a gap between the claimed security and the actual one, and that this gap can be exploited by a malicious designer. We introduce RooD, a block cipher with a carefully crafted backdoor. By using the means of the wide-trail strategy, we argue the resistance of the cipher against linear and differential cryptanalysis. However, the cipher has a key-dependent iterative linear approximation over 12 rounds, holding with probability 1. This property is based on the linear hull effect although any linear trail underlying the linear hull has probability smaller than 1.
A software watermarking scheme enables one to embed a ``mark " (i.e., a message) into a program without significantly changing the functionality. Moreover, any removal of the watermark from a marked program is futile without significantly changing the functionality of the program. At present, the construction of software watermarking mainly focuses on watermarking pseudorandom functions (PRFs), watermarking public key encryption, watermarking signature, etc. In this work, we construct new watermarking PRFs from lattices which provide collusion resistant and public extraction. Our schemes are the first to simultaneously achieve all of these properties. The key to the success of our new constructions lies in two parts. First, we relax the notion of functionality-preserving. In general, we require that a marked program (approximately) preserve the input/output behavior of the original program. For our scheme, the output circuit is divided into two parts, one for PRF output and the other for auxiliary functions. As a result, we only require the PRF output circuit to satisfy functionality-preserving. Second, the marking method we use is essentially different form the previous scheme. In general, the mark program will change the output of some special point. The extraction algorithm determines whether the circuit is marked by determining whether the output of some special points has been changed. In our schemes, we use the constrained signature to mark a PRF circuit.
Grain-128AEAD is one of the second-round candidates of the NIST lightweight cryptography standardization process. There is an existing body of third-party analysis on the earlier versions of the Grain family that provide insights on the security of Grain-128AEAD. Different from the earlier versions, Grain-128AEAD reintroduces the key into the internal state during the initialization. The designers claim that internal state recovery no longer results in key recovery, due to this change. In this paper, we analyze this claim under different scenarios.
Efficient shuffle arguments are essential in mixnet-based e-voting solutions. Terelius and Wikström (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the TW characterization of permutation matrices; this enables us to reduce the communication without adding too much to the computation. We make the TW shuffle argument computationally more efficient by using Groth's coefficient-product argument (JOC, 2010). Additionally, we use batching techniques. The resulting shuffle argument is the fastest known $\leq 5$-message shuffle argument, and, depending on the implementation, can be faster than Groth's argument (the fastest 7-message shuffle argument).
Zero-knowledge proofs allow a prover to convince a verifier of the veracity of a statement without revealing any other information. An interesting class of zero-knowledge protocols are those following the MPC-in-the-head paradigm (Ishai et al., STOC ’07) which use secure multiparty computation (MPC) protocols as the basis. Efficient instances of this paradigm have emerged as an active research topic in the last years, starting with ZKBoo (Giacomelli et al., USENIX ’16). Zero-knowledge protocols are a vital building block in the design of privacy-preserving technologies as well as cryptographic primitives like digital signature schemes that provide post-quantum security. This work investigates the security of zero-knowledge protocols following the MPC-in-the-head paradigm. We provide the first machine-checked security proof of such a protocol on the example of ZKBoo. Our proofs are checked in the EasyCrypt proof assistant. To enable a modular security proof, we develop a new security notion for the MPC protocols used in MPC-in-the-head zero-knowledge protocols. This allows us to recast existing security proofs in a black-box fashion which we believe to be of independent interest.
An algebraic differential fault attack (ADFA) is an attack in which an attacker combines a differential fault attack and an algebraic technique to break a targeted cipher. In this paper, we present three attacks using three different algebraic techniques combined with a differential fault attack in the bit-flip fault model to break the SIMON block cipher. First, we introduce a new analytic method that is based on a differential trail between the correct and faulty ciphertexts. This method is able to recover the entire master key of any member of the SIMON family by injecting faults into a single round of the cipher. In our second attack, we present a simplified Grobner basis algorithm to solve the faulty system. We show that this method could totally break SIMON ciphers with only 3 to 5 faults injected. Our third attack combines a fault attack with a modern SAT solver. By guessing some key bits and with only a single fault injected at the round T - 6, where T is the number of rounds of a SIMON cipher, this combined attack could manage to recover a master key of the cipher. For the last two attacks, we perform experiments to demonstrate the effectiveness of our attacks. These experiments are implemented on personal computers and run at very reasonable timing
Anonymous routing is one of the most fundamental online privacy problems and has been studied extensively for decades. Almost all known approaches for anonymous routing (e.g., mix-nets, DC-nets, and others) rely on multiple servers or routers to engage in some {\it interactive} protocol; and anonymity is guaranteed in the {\it threshold} model, i.e., if one or more of the servers/routers behave honestly. Departing from all prior approaches, we propose a novel {\it non-interactive} abstraction called a Non-Interactive Anonymous Router (NIAR), which works even with a {\it single untrusted router}. In a NIAR scheme, suppose that $n$ senders each want to talk to a distinct receiver. A one-time trusted setup is performed such that each sender obtains a sending key, each receiver obtains a receiving key, and the router receives a {\it token} that ``encrypts'' the permutation mapping the senders to receivers. In every time step, each sender can encrypt its message using its sender key, and the router can use its token to convert the $n$ ciphertexts received from the senders to $n$ {\it transformed ciphertexts}. Each transformed ciphertext is delivered to the corresponding receiver, and the receiver can decrypt the message using its receiver key. Imprecisely speaking, security requires that the untrusted router, even when colluding with a subset of corrupt senders and/or receivers, should not be able to compromise the privacy of honest parties, including who is talking to who, and the message contents. We show how to construct a communication-efficient NIAR scheme with provable security guarantees based on the standard Decisional Linear assumption in suitable bilinear groups. We show that a compelling application of NIAR is to realize a Non-Interactive Anonymous Shuffler (NIAS), where an untrusted server or data analyst can only decrypt a permuted version of the messages coming from $n$ senders where the permutation is hidden. NIAS can be adopted to construct privacy-preserving surveys, differentially private protocols in the shuffle model, and pseudonymous bulletin boards. Besides this main result, we also describe a variant that achieves fault tolerance when a subset of the senders may crash. Finally, we further explore a paranoid notion of security called full insider protection, and show that if we additionally assume sub-exponentially secure Indistinguishability Obfuscation and as sub-exponentially secure one-way functions, one can construct a NIAR scheme with paranoid security.
The random probing model is a leakage model in which each wire of a circuit leaks with a given probability $p$. This model enjoys practical relevance thanks to a reduction to the noisy leakage model, which is admitted as the right formalization for power and electromagnetic side-channel attacks. In addition, the random probing model is much more convenient than the noisy leakage model to prove the security of masking schemes. In a recent work, Ananth, Ishai and Sahai (CRYPTO 2018) introduce a nice expansion strategy to construct random probing secure circuits. Their construction tolerates a leakage probability of $2^{-26}$, which is the first quantified achievable leakage probability in the random probing model. In a follow-up work, Bela\"id, Coron, Prouff, Rivain and Taleb (CRYPTO 2020) generalize their idea and put forward a complete and practical framework to generate random probing secure circuits. The so-called expanding compiler can bootstrap simple base gadgets as long as they satisfy a new security notion called random probing expandability (RPE). They further provide an instantiation of the framework which tolerates a $2^{-8}$ leakage probability in complexity $\mathcal{O}(\kappa^{7.5})$ where $\kappa$ denotes the security parameter. In this paper, we provide an in-depth analysis of the RPE security notion. We exhibit the first upper bounds for the main parameter of a RPE gadget, which is known as the amplification order. We further show that the RPE notion can be made tighter and we exhibit strong connections between RPE and the strong non-interference (SNI) composition notion. We then introduce the first generic constructions of gadgets achieving RPE for any number of shares and with nearly optimal amplification orders and provide an asymptotic analysis of such constructions. Last but not least, we introduce new concrete constructions of small gadgets achieving maximal amplification orders. This allows us to obtain much more efficient instantiations of the expanding compiler: we obtain a complexity of $\mathcal{O}(\kappa^{3.9})$ for a slightly better leakage probability, as well as $\mathcal{O}(\kappa^{3.2})$ for a slightly lower leakage probability.
We present a novel protocol XORBoost for both training gradient boosted tree models and for using these models for inference in the multiparty computation (MPC) setting. Similarly to [AEV20], our protocol is the first one supporting training for generically split datasets (vertical and horizontal splitting, or combination of those) while keeping all the information about the features and thresholds associated with the nodes private, thus, having only the depths and the number of the binary trees as public parameters of the model. By using optimization techniques reducing the number of oblivious permutation evaluations as well as the quicksort and real number arithmetic algorithms from the recent Manticore MPC framework [CDG+21], we obtain a scalable implementation operating under information-theoretic security model in the honest-but-curious setting with a trusted dealer. On a training dataset of 25,000 samples and 300 features in the 2-player setting, we are able to train 10 regression trees of depth 4 in less than 5 minutes per tree (using histograms of 128 bins).
We consider the problem of round-optimal unbounded MPC: in the first round, parties publish a message that depends only on their input. In the second round, any subset of parties can jointly and securely compute any function $f$ over their inputs in a single round of broadcast. We do not impose any a-priori bound on the number of parties nor on the size of the functions that can be computed. Our main result is a semi-malicious two-round protocol for unbounded MPC in the plain model from the hardness of the standard learning with errors (LWE) problem. Prior work in the same setting assumes the hardness of problems over bilinear maps. Thus, our protocol is the first example of unbounded MPC that is post-quantum secure. The central ingredient of our protocol is a new scheme of attribute-based secure function evaluation (AB-SFE) with public decryption. Our construction combines techniques from the realm of homomorphic commitments with delegation of lattice basis. We believe that such a scheme may find further applications in the future.
The Kannan-Fincke-Pohst lattice enumeration algorithm is the classical method for solving the shortest vector problem in lattices. It is also a fundamental tool for most lattice reduction algorithms that provide speed-length tradeoffs. As this algorithm allows efficient parallel implementations, it is likely that implementing it on modern graphics processing units (GPUs) can significantly improve performance. We provide such an implementation that is compatible with the fplll lattice reduction library [fplll16] and achieves a considerable speedup in higher lattice dimensions, compared to current, multithreaded versions. For this, we use the CUDA technology that provides an abstract language for programming GPUs. [fplll16] The FPLLL development team. “fplll, a lattice reduction library”. 2016. URL: https://github.com/fplll/fplll
Multivariate cryptography is dominated by schemes supporting various tweaks, or ``modifiers,'' designed to patch certain algebraic weaknesses they would otherwise exhibit. Typically these modifiers are linear in nature--- either requiring an extra composition with an affine map, or being evaluated by a legitimate user via an affine projection. This description applies to the minus, plus, vinegar and internal perturbation modifiers, to name a few. Though it is well-known that combinations of various modifiers can offer security against certain classes of attacks, cryptanalysts have produced ever more sophisticated attacks against various combinations of these linear modifiers. In this article, we introduce a more fundamentally nonlinear modifier, called Q, that is inspired from relinearization. The effect of the Q modifier on multivariate digital signature schemes is to maintain inversion efficiency at the cost of slightly slower verification and larger public keys, while altering the algebraic properties of the public key. Thus the Q modifier is ideal for applications of digital signature schemes requiring very fast signing and verification without key transport. As an application of this modifier, we propose new multivariate digital signature schemes with fast signing and verification that are resistant to all known attacks.
We formally prove that the C implementation of the X25519 key-exchange protocol in the TweetNaCl library is correct. We prove both that it correctly implements the protocol from Bernstein's 2006 paper, as standardized in RFC 7748, as well as the absence of undefined behavior like arithmetic overflows and array out-of-bounds errors. We also formally prove, based on the work of Bartzia and Strub, that X25519 is mathematically correct, i.e., that it correctly computes scalar multiplication on the elliptic curve Curve25519. The proofs are all computer-verified using the Coq theorem prover. To establish the link between C and Coq we use the Verified Software Toolchain (VST).
Given two ciphertexts generated with a public-key encryption scheme, the problem of plaintext equality consists in determining whether the ciphertexts hold the same value. Similarly, the problem of plaintext inequality consists in deciding whether they hold a different value. Previous work has focused on building new schemes or extending existing ones to include support for plaintext equality/inequality. We propose generic and simple zero-knowledge proofs for both problems, which can be instantiated with various schemes. First, we consider the context where a prover with access to the secret key wants to convince a verifier, who has access to the ciphertexts, on the equality/inequality without revealing information about the plaintexts. We also consider the case where the prover knows the encryption’s randomness instead of the secret key. For plaintext equality, we also propose sigma protocols that lead to non-interactive zero-knowledge proofs. To prove our protocols’ security, we formalize notions related to malleability in the context of public-key encryption and provide definitions of their own interest.
We extend the prior provable related-key security analysis of (generalized) Feistel networks (Barbosa and Farshim, FSE 2014; Yu et al., Inscrypt 2020) to the setting of expanding round functions, i.e., n-bit to m-bit round functions with n < m. This includes Expanding Feistel Networks (EFNs) that purely rely on such expanding round functions, and Alternating Feistel Networks (AFNs) that alternate expanding and contracting round functions. We show that, when two independent keys $K_1,K_2$ are alternatively used in each round, (a) $2\lceil\frac{m}{n}\rceil+2$ rounds are sufficient for related-key security of EFNs, and (b) a constant number of 4 rounds are sufficient for related-key security of AFNs. Our results complete the picture of provable related-key security of GFNs, and provide additional theoretical support for the AFN-based NIST format preserving encryption standards FF1 and FF3.
As people become more and more privacy conscious, the need for end-to-end encryption (E2EE) has become widely recognized. We study the security of SFrame, an E2EE mechanism recently proposed to IETF for video/audio group communications over the Internet. Although a quite recent project, SFrame is going to be adopted by a number of real-world applications. We inspected the original specification of SFrame. We found a critical issue that will lead to an impersonation (forgery) attack by a malicious group member with a practical complexity. We also investigated the several publicly-available SFrame implementations, and confirmed that this issue is present in these implementations.
Large semigroups and groups of transformations of finite affine space of dimension n with the option of computability of the composition of n arbitrarily chosen elements in polynomial time are described in the paper. Constructions of such families are given together with effectively computed homomorphisms between members of the family. These algebraic platforms allow us to define protocols for several generators of subsemigroup of affine Cremona semigroups with several outputs. Security of these protocols rests on the complexity of the word decomposition problem, It allows to introduce algebraic protocols expanded to cryptosystems of El Gamal type which are not a public key system. In particular symbiotic combination of these protocol of Noncommutative cryptography with one time pad encryption is given. Some of these nonclassical multivariate cryptosystems are implemented with platforms of cubical transformations.
Recently, a light-weight authenticated key-exchange (AKE) scheme has been proposed. The scheme provides mutual authentication. It is asymmetric in nature by delegating complex cryptographic operations to resource-equipped servers, and carefully managing the workload on resource-constrained Smart meter nodes by using Physically Unclonable Functions. The prototype Smart meter built using commercial-off-the-shelf products is enabled with a low-cost countermeasure against load-modification attacks, which goes side-by-side with the proposed protocol. An attack against this AKE scheme has been recently proposed claiming that the server can be breached to mount spoofing attacks. It relies on the assumption that the result of an attack against authenticated key-exchange protocol is determined before the attacker learns the session key. In this short paper, we discuss the attack’s validity and describe the misinterpretation of the AKE protocol’s security definition.
Anonymous identity-based identification scheme in the ad-hoc group is a multi-party cryptographic primitive that allows participants to form an ad-hoc group and prove membership anonymously in such a group. In this paper, we cryptanalyze an ad-hoc anonymous identity-based identification scheme proposed by Barapatre and Rangan and show that the scheme is not secure against key-only universal impersonation attack. We note that anyone can impersonate as a valid group member to convince the honest verifier successfully, even without knowing the group secret key. Moreover, we proposed a fix on the scheme and provide a security proof for our fixed scheme. The fixed scheme we proposed fulfills the security requirements of an ad-hoc anonymous identity-based identification scheme that are correctness, soundness, and anonymity.
The comparison operation for two numbers is one of the most commonly used operations in several applications, including deep learning. Several studies have been conducted to efficiently evaluate the comparison operation in homomorphic encryption schemes, termed homomorphic comparison operation. Recently, Cheon et al. (Asiacrypt 2020) proposed new comparison methods that approximate the sign function using composite polynomial in homomorphic encryption and proved that these methods have optimal asymptotic complexity. In this paper, we propose a practically optimal method that approximates the sign function by using compositions of minimax approximate polynomials. It is proved that this approximation method is optimal with respect to depth consumption and the number of non-scalar multiplications. In addition, a polynomial-time algorithm that determines the optimal compositions of minimax approximate polynomials for the proposed homomorphic comparison operation is proposed by using dynamic programming. The numerical analysis demonstrates that the proposed homomorphic comparison operation reduces running time by approximately 45\% (resp. 41\%) on average, compared with the previous algorithm if running time (resp. depth consumption) is to be minimized. In addition, when $N$ is $2^{17}$, and the precision parameter $\alpha$ is 20, the previous algorithm does not achieve 128-bit security, while the proposed algorithm achieves 128-bit security due to small depth consumption.
In this work, we show how to garble arithmetic circuits with full active security in the general multiparty setting, secure in the full-threshold setting (that is, when only one party is assumed honest). Our solution allows interfacing Boolean garbled circuits with arithmetic garbled circuits. Previous works in the arithmetic circuit domain focused on the 2-party setting, or on semi-honest security and assuming an honest majority -- notably, the work of Ben-Efraim (Asiacrypt 2018) in the semi-honest, honest majority security model, which we adapt and extend. As an additional contribution, we improve on Ben-Efraim's selector gate. A selector gate is a gate that given two arithmetic inputs and one binary input, outputs one of the arithmetic inputs, based on the value of the selection bit input. Our new construction for the selector gate reduces the communication cost to almost half of that of Ben-Efraim's gate. This result applies both to the semi-honest and to the active security model.
Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b} \in \mathbb{F}_{\!q}$ and $q \not\equiv 1 \: (\mathrm{mod} \ 27)$. For example, these conditions are fulfilled for the group $\mathbb{G}_1$ of the curves BLS12-381 ($b=4$) and BLS12-377 ($b=1$) and for the group $\mathbb{G}_2$ of the curve BW6-761 ($b=4$). The curves mentioned are a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ indifferentiable from a random oracle. Its main advantage is the fact that $H$ computes only one exponentiation in $\mathbb{F}_{\!q}$. In comparison, the previous fastest constant-time indifferentiable hash functions to $E_b(\mathbb{F}_{\!q})$ compute two exponentiations in $\mathbb{F}_{\!q}$. In particular, applying $H$ to the widely used BLS multi-signature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.
What is the funniest number in cryptography? 0. The reason is that for all x, x*0 = 0, i.e., the equation is always satisfied no matter what x is. This article discusses crypto bugs in four BLS signatures’ libraries (ethereum/py ecc, supranational/blst, herumi/bls, sigp/milagro bls) that revolve around 0. Furthermore, we develop ”splitting zero” attacks to show a weakness in the proof-of-possession aggregate signature scheme standardized in BLS RFC draft v4. Eth2 bug bounties program generously awarded $35,000 in total for the reported bugs.
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.
This paper presents a new protocol 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 our protocol 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. Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect 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 our heavy-hitters protocol 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, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.
Cyclic logic encryption is a newly proposed circuit obfuscation technique in hardware security. It was claimed to be SAT-unresolvable because feedback cycles were intentionally inserted under keys into the encryption. We show in the paper that even though feedback cycles introduce extra difficulty for an attacker, they can still be overcome with SAT- based techniques. Specifically, we propose CycSAT Algorithms based on SAT with different acyclic conditions that can efficiently decrypt cyclic encryptions. Experimental results have shown that our CycSAT is efficient and effective to decrypt cyclic encryptions, and we need to develop new encryptions with better security properties.
Attribute-based encryption received widespread attention as soon as it was proposed. However, due to its specific characteristics, some restrictions on attribute set in attribute-based encryption are not flexible enough in actual operation. In addition, since access authorities are determined according to users' attributes, users sharing the same attributes are difficult to be distinguished. Once a malicious user makes illicit gains by their decryption authorities, it is difficult to track down specific users. This paper follows practical demands to propose a more flexible key-policy attribute-based encryption scheme with black-box traceability. The scheme has a constant size of public parameters which can be utilized to construct attribute-related parameters flexibly, and the method of traitor tracing in broadcast encryption is introduced to achieve effective malicious user tracing. In addition, the security and feasibility can be proved by the security proofs and performance evaluation in this paper.
Secure comparison has been a fundamental challenge in privacy-preserving computation, since its inception as the Yao's millionaires' problem (FOCS 1982). In this work, we present a novel construction for general n-party private comparison, secure against an active adversary, in the dishonest majority setting. For the case of comparisons over fields, our protocol is more efficient than the best prior work (edaBits: Crypto 2020), with ~1.5x better throughput in most adversarial settings, over 2.3x better throughput in particular in the passive, honest majority setting, and lower communication. Our comparisons crucially eliminate the need for bounded inputs as well as the need for statistical security that prior works require. An important consequence of removing this "slack" (a gap between the bit-length of the input and the MPC representation) is that multi-party computation (MPC) protocols can be run in a field of smaller size, reducing the overhead incurred by privacy-preserving computations. We achieve this novel construction using the commutative nature of addition over rings and fields. This makes the protocol both simple to implement and highly efficient and we provide an implementation in MP-SPDZ (CCS 2020).
This paper presents Checklist, a system for private blocklist lookups. In Checklist, a client can determine whether a particular string appears on a server-held list of blocklisted strings, without leaking its string to the server. Checklist is the first blocklist-lookup system that (1) leaks no information about the client’s string to the server and (2) allows the server to respond to the client’s query in time sublinear in the blocklist size. To make this possible, we construct a new two-server private-information-retrieval protocol that is both asymptotically and concretely faster, in terms of server-side time, than those of prior work. We evaluate Checklist in the context of Google’s “Safe Browsing” blocklist, which all major browsers use to prevent web clients from visiting malware-hosting URLs. Today, lookups to this blocklist leak partial hashes of a subset of clients’ visited URLs to Google’s servers. We have modified Firefox to perform Safe-Browsing blocklist lookups via Checklist servers, which eliminate the leakage of partial URL hashes from the Firefox client to the blocklist servers. This privacy gain comes at the cost of increasing communication by a factor of 3.3×, and the server-side compute costs by 9.8×. Use of our new PIR protocol reduces server-side costs by 6.7×, compared to what would be possible prior state-of-the-art two-server PIR.
Most efficient zero-knowledge arguments lack a concrete security analysis, making parameter choices and efficiency comparisons challenging. This is even more true for non-interactive versions of these systems obtained via the Fiat-Shamir transform, for which the security guarantees generically derived from the interactive protocol are often too weak, even when assuming a random oracle. This paper initiates the study of state-restoration soundness in the algebraic group model (AGM) of Fuchsbauer, Kiltz, and Loss (CRYPTO '18). This is a stronger notion of soundness for an interactive proof or argument which allows the prover to rewind the verifier, and which is tightly connected with the concrete soundness of the non-interactive argument obtained via the Fiat-Shamir transform. We propose a general methodology to prove tight bounds on state-restoration soundness, and apply it to variants of Bulletproofs (Bootle et al, S&P '18) and Sonic (Maller et al., CCS '19). To the best of our knowledge, our analysis of Bulletproofs gives the first non-trivial concrete security analysis for a non-constant round argument combined with the Fiat-Shamir transform.
A sequence of recent works by Heath and Kolesnikov have explored modifying existing interactive protocols for privacy-preserving computation (secure multiparty computation, private function evaluation and zero-knowledge proofs) to be more communication efficient when applied to disjunctive statements, such that the cost only depends on the size of the largest clause in the disjunction. In this work, we focus on the specific case of zero-knowledge proofs for disjunctive statements. We design a general framework that compiles a large class of unmodified $\Sigma$-protocols, each for an individual statement, into a new $\Sigma$-protocol that proves a disjunction of these statements. Our framework can be used both when each clause is proved with the same $\Sigma$-protocol and when different $\Sigma$-protocols are used for different clauses. The resulting $\Sigma$-protocol is concretely efficient and has communication complexity proportional to the communication required by the largest clause, with additive terms that are only logarithmic in the number of clauses. We show that our compiler can be applied to many well-known $\Sigma$-protocols, including classical protocols (e.g. Schnorr and Guillou-Quisquater) and modern MPC-in-the-head protocols such as the recent work of Katz, Kolesnikov and Wang and the Ligero protocol of Ames et al. Finally, since all of the protocols in our class can be made non-interactive in the random oracle model using the Fiat-Shamir transform, our result yields the first non-interactive zero-knowledge protocol for disjunctions where the communication only depends on the size of the largest clause.
We present a construction of indistinguishability obfuscation for null quantum circuits (null-iO) with respect to a classical oracle, assuming the quantum hardness of the learning with errors (LWE) problem. Heuristically instantiating the classical oracle with quantum-secure indistinguishability obfuscation for classical circuits gives us the first candidate construction of null-iO for quantum circuits. This scheme establishes the feasibility of a series of new cryptographic primitives that, prior to our work, were unknown to exist even making heuristic assumptions. Specifically, we obtain (in some cases additionally assuming indistinguishability obfuscation for classical circuits): * A witness encryption (WE) scheme for QMA. * A publicly-verifiable non-interactive zero-knowledge (NIZK) argument for QMA. * A two-message publicly-verifiable witness-indistinguishable (ZAPR) argument for QMA. * An attribute-based encryption (ABE) scheme for BQP. * A secret sharing scheme for monotone QMA.
Payment channel networks have been introduced to mitigate the scalability issues inherent to permissionless decentralized cryptocurrencies such as Bitcoin. Launched in 2018, the Lightning Network (LN) has been gaining popularity and consists today of more than 5000 nodes and 30000 payment channels that jointly hold 895 bitcoins (7.6M USD as of February 2020). This adoption has motivated research from both academia and industry. Payment channels suffer from security vulnerabilities, such as the wormhole attack, anonymity issues, and scalability limitations related to the upper bound on the number of concurrent payments per channel, which have been pointed out by the scientific community but never quantitatively analyzed. In this work, we first analyze the proneness of the LN to the wormhole attack and attacks against anonymity. We observe that an adversary needs to control only 2% of LN nodes to learn sensitive payment information (e.g., sender, receiver and payment amount) or to carry out the wormhole attack. Second, we study the management of concurrent payments in the LN and quantify its negative effect on scalability. We observe that for micropayments, the forwarding capability of up to 50% of channels is restricted to a value smaller than the overall channel capacity. This phenomenon not only hinders scalability but also opens the door for DoS attacks: We estimate that a network-wide DoS attack costs within 1.5M USD, while isolating the biggest community from the rest of the network costs only 225k USD. Our findings should prompt the LN community to consider the security, privacy and scalability issues of the network studied in this work when educating users about path selection algorithms, as well as to adopt multi-hop payment protocols that provide stronger security, privacy and scalability guarantees.
Forward secrecy is an important feature for modern cryptographic systems and is widely used in secure messaging such as Signal and WhatsApp as well as in common Internet protocols such as TLS, IPSec, or SSH. The benefit of forward secrecy is that the damage in case of key-leakage is mitigated. Forward-secret encryption schemes provide security of past ciphertexts even if a secret key leaks, which is interesting in settings where cryptographic keys often reside in memory for quite a long time and could be extracted by an adversary, e.g., in cloud computing. The recent concept of puncturable encryption (PE; Green and Miers, IEEE S&P'15) provides a versatile generalization of forward-secret encryption: it allows to puncture secret keys with respect to ciphertexts to prevent the future decryption of these ciphertexts. We introduce the abstraction of allow-list/deny-list encryption schemes and classify different types of PE schemes using this abstraction. Based on our classification, we identify and close a gap in existing work by introducing a novel variant of PE which we dub Dual-Form Puncturable Encryption (DFPE). DFPE significantly enhances and, in particular, generalizes previous variants of PE by allowing an interleaved application of allow- and deny-list operations. We present a construction of DFPE in prime-order bilinear groups, discuss a direct application of DPFE for enhancing security guarantees within Cloudflare's Geo Key Manager, and show its generic use to construct forward-secret IBE and forward-secret digital signatures.
Ledger-based systems that support rich applications often suffer from two limitations. First, validating a transaction requires re-executing the state transition that it attests to. Second, transactions not only reveal which application had a state transition but also reveal the application's internal state. We design, implement, and evaluate ZEXE, a ledger-based system where users can execute offline computations and subsequently produce transactions, attesting to the correctness of these computations, that satisfy two main properties. First, transactions *hide all information* about the offline computations. Second, transactions can be *validated in constant time* by anyone, regardless of the offline computation. The core of ZEXE is a construction for a new cryptographic primitive that we introduce, *decentralized private computation* (DPC) schemes. In order to achieve an efficient implementation of our construction, we leverage tools in the area of cryptographic proofs, including succinct zero knowledge proofs and recursive proof composition. Overall, transactions in ZEXE are 968 bytes regardless of the offline computation, and generating them takes less than a minute plus a time that grows with the offline computation. We demonstrate how to use ZEXE to realize privacy-preserving analogues of popular applications: private decentralized exchanges for user-defined fungible assets and regulation-friendly private stablecoins.
RSA key generation requires devices to generate large prime numbers. The na\"ive approach is to generate candidates at random, and then test each one for (probable) primality. However, it is faster to use a sieve method, where the candidates are chosen so as not to be divisible by a list of small prime numbers $\{p_i\}$. Sieve methods can be somewhat complex and time-consuming, at least by the standards of embedded and hardware implementations, and they can be tricky to defend against side-channel analysis. Here we describe an improvement on Joye et al.'s sieve based on the Chinese Remainder Theorem (CRT). We also describe a new sieve method using quadratic residuosity which is simpler and faster than previously known methods, and which can produce values in desired RSA parameter ranges such as $(2^{n-1/2}, 2^n)$ with minimal additional work. The same methods can be used to generate strong primes and DSA moduli. We also demonstrate a technique for RSA private key operations using the Chinese Remainder Theorem (RSA-CRT) without $q^{-1}$ mod $p$. This technique also leads to inversion-free batch RSA and inversion-free RSA mod $p^k q$. We demonstrate how an embedded device can use our key generation and RSA-CRT techniques to perform RSA efficiently without storing the private key itself: only a symmetric seed and one or two short hints are required.
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.
We propose an efficient quantum algorithm for a specific quantum state discrimination problem. An immediate corollary of our result is a polynomial time quantum algorithm for the Dihedral Coset Problem with a smooth modulus. This, in particular, implies that $\text{poly}(n)$-unique-SVP is in BQP.
Our main result in this work is the extension of the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. We prove that our generalization for Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the addition of a new parameter, the torsion factor defining the twisted embedding, does not affect the asymptotic approximation factors in the worst-case to average-case reductions. Thus, Twisted Ring-LWE maintains the consolidated hardness guarantee of Ring-LWE and increases the existing scope of algebraic lattices that can be considered for cryptographic applications. Additionally, we expand on the results of Ducas and Durmus (Public-Key Cryptography, 2012) on spherical Gaussian distributions to the proposed class of lattices under certain restrictions. Thus, sampling from a spherical Gaussian distribution can be done directly in the respective number field, while maintaining its shape and standard deviation when seen in $\mathbb{R}^n$ via twisted embeddings.
Modern implementations of homomorphic encryption (HE) rely heavily on polynomial arithmetic over a finite field. This is particularly true of the CKKS, BFV, and BGV HE schemes. Two of the biggest performance bottlenecks in HE primitives and applications are polynomial modular multiplication and the forward and inverse number- theoretic transform (NTT). Here, we introduce Intel® Homomorphic Encryption Acceleration Library (Intel® HEXL), a C++ library which provides optimized implementations of polynomial arithmetic for Intel® processors. Intel HEXL takes advantage of the recent Intel® Advanced Vector Extensions 512 (Intel® AVX512) instruction set to provide state- of-the-art implementations of the NTT and modular multiplication. On the forward and inverse NTT, Intel HEXL provides up to 7.2x and 6.7x speedup, respectively, over a native C++ implementation. Intel HEXL also provides up to 6.0x speedup on the element-wise vector-vector modular multiplication, and 1.7x speedup on the element-wise vector- scalar modular multiplication. Intel HEXL is available open-source at https://github.com/intel/hexl under the Apache 2.0 license.
Automated contact tracing leverages the ubiquity of smartphones to warn users about an increased exposure risk to COVID-19. In the course of only a few weeks, several cryptographic protocols have been proposed that aim to achieve such contract tracing in a decentralized and privacy-preserving way. Roughly, they let users' phones exchange random looking pseudonyms that are derived from locally stored keys. If a user is diagnosed, her phone uploads the keys which allows other users to check for any contact matches. Ultimately this line of work led to Google and Apple including a variant of these protocols into their phones which is currently used by millions of users. Due to the obvious urgency, these schemes were pushed to deployment without a formal analysis of the achieved security and privacy features. In this work we address this gap and provide the first formal treatment of such decentralized cryptographic contact tracing. We formally define three main properties in a game-based manner: pseudonym and trace unlinkability to guarantee the privacy of users during healthy and infectious periods, and integrity ensuring that triggering false positive alarms is infeasible. A particular focus of our work is on the timed aspects of these schemes, as both keys and pseudonyms are rotated regularly, and we specify different variants of the aforementioned properties depending on the time granularity for which they hold. We analyze a selection of practical protocols (DP-3T, TCN, GAEN) and prove their security under well-defined assumptions.
The Ring-LWE over two-to-power cyclotomic integer rings has been the hard computational problem for lattice cryptographic constructions. Its hardness and the conjectured hardness of approximating ideal SIVP for ideal lattices in two-to-power cyclotomic fields have been the fundamental open problems in lattice cryptography and the complexity theory of computational problems of ideal lattices. In this paper we present a general theory of sublattice attack on the Ring-LWE with not only the Gaussian error distribution but also general error distributions. By the usage of our sublattice attack we prove that the decision Ring-LWE over two-to-power cyclotomic integer rings with certain polynomially bounded modulus parameters when degrees d_n = 2^{n&#8722;1} going to the infinity can be solved by a polynomial (in d_n) time algorithm for wide error distributions with widths in the range of Peikert-Regev-Stephens-Davidowitz hardness reduction results in their STOC 2017 paper. Hence we also prove that approximating idealSIV Ppoly(dn) with some polynomial factors for ideal lattices in two-to-power cyclotomic fields can be solved within quantum polynomial time. Therefore the lattice cryptographic constructions can not be based on the ”hardness” of Ring-LWE over two-to-power cyclotomic integer rings even in the classical computational model.
Digital signatures are used to verify the authenticity of digital messages, that is, to know with a high level of certainty, that a digital message was created by a known sender and was not altered in any way. This is usually achieved by using asymmetric cryptography, where a secret key is used by the signer, and the corresponding public key is used by those who wish to verify the signed data. In many use-cases, such as blockchain, the history and order of the signed data, thus the signatures themselves, are important. In blockchains specifically, the threat is forks, where one can double-spend its crypto-currency if one succeeds to publish two valid transactions on two different branches of the chain. We introduce a single private/public key pair signature scheme using verifiable random function, that binds a signer to its signature history. The scheme enforces a single ordered signatures' history using a deterministic verifiable chain of signature functions that also reveals the secret key in case of misbehaviors.
Blockchain-based cryptocurrencies offer an appealing alternative to Fiat currencies, due to their decentralized and borderless nature. However the decentralized settings make the authentication process more challenging: Standard cryptographic methods often rely on the ability of users to reliably store a (large) secret information. What happens if one user's key is lost or stolen? Blockchain systems lack of fallback mechanisms that allow one to recover from such an event, whereas the traditional banking system has developed and deploys quite effective solutions. In this work, we develop new cryptographic techniques to integrate security policies (developed in the traditional banking domain) in the blockchain settings. We propose a system where a smart contract is given the custody of the user's funds and has the ability to invoke a two-factor authentication (2FA) procedure in case of an exceptional event (e.g., a particularly large transaction or a key recovery request). To enable this, the owner of the account secret-shares the answers of some security questions among a committee of users. When the 2FA mechanism is triggered, the committee members can provide the smart contract with enough information to check whether an attempt was successful, and nothing more. We then design a protocol that securely and efficiently implements such a functionality: The protocol is round-optimal, is robust to the corruption of a subset of committee members, supports low-entropy secrets, and is concretely efficient. As a stepping stone towards the design of this protocol, we introduce a new threshold homomorphic encryption scheme for linear predicates from bilinear maps, which might be of independent interest. To substantiate the practicality of our approach, we implement the above protocol as a smart contract in Ethereum and show that it can be used today as an additional safeguard for suspicious transactions, at minimal added cost. We also implement a second scheme where the smart contract additionally requests a signature from a physical hardware token, whose verification key is registered upfront by the owner of the funds. We show how to integrate the widely used universal two-factor authentication (U2F) tokens in blockchain environments, thus enabling the deployment of our system with available hardware.
Code that is highly optimized poses a problem for program-level verification: programmers can employ various clever tricks that are non-trivial to reason about. For cryptography on low-power devices, it is nonetheless crucial that implementations be functionally correct, secure, and efficient. These are usually crafted in hand-optimized machine code that eschew conventional control flow as much as possible. We have formally verified such code: a library which implements elliptic curve cryptography on 8-bit AVR microcontrollers. The chosen implementation is the most efficient currently known for this microarchitecture. It consists of over 3000 lines of assembly instructions. Building on earlier work, we use the Why3 platform to model the code and prove verification conditions, using automated provers. We expect the approach to be re-usable and adaptable, and it allows for validation. Furthermore, an error in the original implementation was found and corrected, at the same time reducing its memory footprint. This shows that practical verification of cutting-edge code is not only possible, but can in fact add to its efficiency—and is clearly necessary.
Uncloneable encryption, introduced by Broadbent and Lord (TQC'20), is an encryption scheme with the following attractive feature: an adversary cannot create multiple ciphertexts which encrypt to the same message as the original ciphertext. The constructions proposed by Broadbent and Lord have the disadvantage that they only guarantee one-time security; that is, the encryption key can only be used once to encrypt the message. In this work, we study uncloneable encryption schemes, where the encryption key can be re-used to encrypt multiple messages. We present two constructions from minimal cryptographic assumptions: (i) a private-key uncloneable encryption scheme assuming post-quantum one-way functions and, (ii) a public-key uncloneable encryption scheme assuming a post-quantum public-key encryption scheme.
We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided.
Secure-channel establishment allows two endpoints to communicate confidentially and authentically. Since they hide all data sent across them, good or bad, secure channels are often subject to mass surveillance in the name of (inter)national security. Some protocols are constructed to allow easy data interception . Others are designed to preserve data privacy and are either subverted or prohibited to use without trapdoors. We introduce LIKE, a primitive that provides secure-channel establishment with an exceptional, session-specific opening mechanism. Designed for mobile communications, where an operator forwards messages between the endpoints, it can also be used in other settings. LIKE allows Alice and Bob to establish a secure channel with respect to n authorities. If the authorities all agree on the need for interception, they can ensure that the session key is retrieved. As long as at least one honest authority prohibits interception, the key remains secure; moreover LIKE is versatile with respect to who learns the key. Furthermore, we guarantee non-frameability: nobody can falsely incriminate a user of taking part in a conversation; and honest-operator: if the operator accepts a transcript as valid, then the key retrieved by the authorities is the key that Alice and Bob should compute. Experimental results show that our protocol can be efficiently implemented.
We push a little further the study of two characterizations of almost perfect nonlinear (APN) functions introduced in our recent monograph. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to new results about APN power functions and more general APN polynomials with coefficients in a subfield F_{2^k} , which ease the research of such functions and of differentially uniform functions, and simplifies the related proofs by avoiding tedious calculations. In a second part, we give slightly simpler proofs than in the same monograph, of two known results on Boolean functions, one of which deserves to be better known but needed clarification, and the other needed correction.
Identifiable abort is the strongest security guarantee that is achievable for secure multi-party computation in the dishonest majority setting. Protocols that achieve this level of security ensure that, in case of an abort, all honest parties agree on the identity of at least one corrupt party who can be held accountable for the abort. It is important to understand what computational primitives must be used to obtain secure computation with identifiable abort. This can be approached by asking which oracles can be used to build perfectly secure computation with identifiable abort. Ishai, Ostrovsky, and Zikas (Crypto 2014) show that an oracle that returns correlated randomness to all $n$ parties is sufficient; however, they leave open the question of whether oracles that return output to fewer than $n$ parties can be used. In this work, we show that for $t \leq n - 2$ corruptions, oracles that return output to $n - 1$ parties are sufficient to obtain information-theoretically secure computation with identifiable abort. Using our construction recursively, we see that for $t \leq n - \ell - 2$ and $\ell \in \mathcal{O}(1)$, oracles that return output to $n - \ell - 1$ parties are sufficient. For our construction, we introduce a new kind of secret sharing scheme which we call unanimously identifiable secret sharing with public and private shares (UISSwPPS). In a UISSwPPS scheme, each share holder is given a public and a private shares. Only the public shares are necessary for reconstruction, and the knowledge of a private share additionally enables the identification of at least one party who provided an incorrect share in case reconstruction fails. The important new property of UISSwPPS is that, even given all the public shares, an adversary should not be able to come up with a different public share that causes reconstruction of an incorrect message, or that avoids the identification of a cheater if reconstruction fails.
This work presents a hardware accelerator, for the optimization of latency and area at the same time, to improve the performance of point multiplication process in Elliptic Curve Cryptography. In order to reduce the overall computation time in the proposed 2-stage pipelined architecture, a rescheduling of point addition and point doubling instructions is performed along with an efficient use of required memory locations. Furthermore, a 41-bit multiplier is also proposed. Consequently, the FPGA and ASIC implementation results have been provided. The performance comparison with state-of-the-art implementations, in terms of latency and area, proves the significance of the proposed accelerator.
The choice of activation functions can have a significant effect on the performance of a neural network. Although the researchers have been developing novel activation functions, Rectified Linear Unit ($ReLU$) remains the most common one in practice. This paper shows that evolutionary algorithms can discover new activation functions for side-channel analysis (SCA) that outperform $ReLU$. Using Genetic Programming (GP), candidate activation functions are defined and explored (neuroevolution). As far as we know, this is the first attempt to develop custom activation functions for SCA. The ASCAD database experiments show this approach is highly effective compared to the state-of-the-art neural network architectures. While the optimal performance is achieved when activation functions are evolved for the particular task, we also observe that these activation functions show the property of generalization and high performance for different SCA scenarios.
A cryptographic primitive, called encryption switching protocol (ESP), has been proposed recently. This two-party protocol enables interactively converting values encrypted under one scheme into another scheme without revealing the plaintexts. Given two additively and multiplicatively homomorphic encryption schemes, parties can now encrypt their data and convert underlying encryption schemes to perform different operations simultaneously. Due to its efficiency, ESP becomes an alternative to fully homomorphic encryption schemes in some privacy-preserving applications. In this paper, we propose an improvement in ESP. In particular, we consider the multi-exponentiation with encrypted bases argument ({\sf MEB}) protocol. This protocol is not only the essential component and efficiency bottleneck of ESP, but also has tremendous potential in many applications and can be used to speed up many intricate cryptographic protocols, such as proof of knowledge of a double logarithm. According to our theoretical analysis and experiments, our proposed {\sf MEB} protocol has lower communication and computation cost. More precisely, it reduces the communication cost by roughly $29\%$ compared to the original protocol. The computation cost of the verifier is reduced by $19\% - 42\%$, depending on the settings of experimental parameters. This improvement is particularly useful for verifiers with weak computing power in some applications. We also provide a formal security proof to confirm the security of the improved {\sf MEB} protocol.
A Statistical Information Theoretic Secure (SITS) system utilizing the Chinese Remainder Theorem (CRT), coupled with Fully Homomorphic Encryption (FHE) for Distributed Communication-less Secure Multiparty Computation (DCLSMPC) of any Distributed Unknown Finite State Machine (DUFSM) is presented. Namely, secret shares of the input(s) and output(s) are passed to/from the computing parties, while there is no communication between them throughout the computation. We propose a novel approach of transition table representation and polynomial representation for arithmetic circuits evaluation, joined with a CRT secret sharing scheme and FHE to achieve SITS communication-less within computational secure execution of DUFSM. We address the severe limitation of FHE implementation over a single server to cope with a malicious or Byzantine server. We use several distributed memory-efficient solutions that are significantly better than the majority vote in replicated state machines, where each participant maintains an FHE replica. A Distributed Unknown Finite State Machine (DUFSM) is achieved when the transition table is secret shared or when the (possible zero value) coefficients of the polynomial are secret shared, implying communication-less SMPC of an unknown finite state machine.
We study uncloneable quantum encryption schemes for classical messages as recently proposed by Broadbent and Lord. We focus on the information-theoretic setting and give several limitations on the structure and security of these schemes: Concretely, 1) We give an explicit cloning-indistinguishable attack that succeeds with probability $\frac12 + \mu/16$ where $\mu$ is related to the largest eigenvalue of the resulting quantum ciphertexts. 2) For a uniform message distribution, we partially characterize the scheme with the minimal success probability for cloning attacks. 3) Under natural symmetry conditions, we prove that the rank of the ciphertext density operators has to grow at least logarithmically in the number of messages to ensure uncloneable security. 4) The \emph{simultaneous} one-way-to-hiding (O2H) lemma is an important technique in recent works on uncloneable encryption and quantum copy protection. We give an explicit example which shatters the hope of reducing the multiplicative "security loss" constant in this lemma to below 9/8.
The k-XOR problem can be generically formulated as the following: given many n-bit strings generated uniformly at random, find k distinct of them which XOR to zero. This generalizes collision search (two equal elements) to a k-tuple of inputs. This problem has become ubiquitous in cryptanalytic algorithms. Applications include variants in which the XOR operation is replaced by a modular addition (k-SUM) or other non-commutative operations (e.g., the composition of permutations). The case where a single solution exists on average is of special importance. The generic study of quantum algorithms k-XOR (and variants) was started by Grassi et al. (ASIACRYPT 2018), in the case where many solutions exist. At EUROCRYPT 2020, Naya-Plasencia and Schrottenloher defined a class of "quantum merging algorithms" obtained by combining quantum search. They represented these algorithms by a set of "merging trees" and obtained the best ones through linear optimization of their parameters. In this paper, we give a new, simplified representation of merging trees that makes their analysis easier. As a consequence, we improve the quantum time complexity of the Single-solution k-XOR problem by relaxing one of the previous constraints, and making use of quantum walks. Our algorithms subsume or improve over all previous quantum generic algorithms for Single-solution k-XOR. For example, we give an algorithm for 4-XOR (or 4-SUM) in quantum time $\widetilde{\mathcal{O}}(2^{7n/24})$.
In this work, we study disappearing cryptography in the bounded storage model. Here, a component of the transmission, say a ciphertext, a digital signature, or even a program, is streamed bit by bit. The stream is so large for anyone to store in its entirety, meaning the transmission effectively disappears once the stream stops. We first propose the notion of online obfuscation, capturing the goal of disappearing programs in the bounded storage model. We give a negative result for VBB security in this model, but propose candidate constructions for a weaker security goal, namely VGB security. We then demonstrate the utility of VGB online obfuscation, showing that it can be used to generate disappearing ciphertexts and signatures. All of our applications are NOT possible in the standard model of cryptography, regardless of computational assumptions used.
Outsourcing computation allows a resource limited client to expand its computational capabilities by outsourcing computation to other nodes or clouds. A basic requirement of outsourcing is providing assurance that the computation result is correct. We consider a smart contract based outsourcing system that achieves assurance by replicating the computation on two servers and accepts the computation result if the two responses match. Correct computation result is obtained by using incentivization to instigate correct behaviour in servers. We show that all previous replication based incentivized outsourcing protocols with proven correctness, fail when automated by a smart contract because of the copy attack where a contractor simply copies the submitted response of the other contractor. We then design an incentivization mechanism that uses two lightweight challenge-response protocols that are used when the submitted results are compared, and employs monetary rewards, fines, and bounties to incentivize correct computation. We use game theory to model and analyze our mechanism, and prove that with appropriate choices of the mechanism parameters, there is a single Nash equilibrium corresponding to the contractors’ strategy of correctly computing the result. Our work provides a foundation for replicated incentivized computation in the smart contract setting and opens new research directions.