We introduce a novel approach for designing symmetric ciphers to resist fault injection. The approach is fairly generic and applies to round functions of block ciphers, cryptographic permutations and stream ciphers. We showcase our method with a new permutation called FRIT and perform fault analysis on a simulated hardware and actual software implementation. We present performance results for software and hardware implementations with and without the fault detection mechanism. On a Cortex-M4 platform the overhead of the countermeasure in cycles is 83%. The penalty on resources for hardware implementations depends on the hardware and can be as low as 56%.

A $k$-out-of-$n$ ring signature is a kind of anonymous signature that can be performed by any member in a group. This signature allows the creation of valid signatures if and only if actual signers more than or equal to $k$ sign the message among $n$ possible signers. In this paper, we present a new $k$-out-of-$n$ ring signature. Our signature has a remarkable property: When the signature is updated from $k$-out-of-$n$ to $(k+\alpha)$-out-of-$n$, the previous signers do not need to sign a message again. Our scheme can ``reuse'' the old signature, whereas the previous schemes revoke it and create a signature from scratch. We call this property ``{{flexibility}}'' and formalize it rigorously. Our signature scheme has a multiple ring structure, each ring of which is based on $1$-out-of-$n$ ring signature. The structure of our scheme is completely different from that of conventional schemes, such as a secret-sharing type. The signers' keys are mostly independent of each user, thanks to a part of keys which use a special hash function. We give the results of provable security for our scheme.

Threshold cryptography provides a mechanism for protecting secret keys by sharing them among multiple parties, who then jointly perform cryptographic operations. An attacker who corrupts upto a threshold number of parties cannot recover the secrets or violate security. Prior works in this space have mostly focused on definitions and constructions for public-key cryptography and digital signatures, and thus do not capture the security concerns and efficiency challenges of symmetric-key based applications which commonly use long-term (unprotected) master keys to protect data at rest, authenticate clients on enterprise networks, and secure data and payments on IoT devices. We put forth the first formal treatment for distributed symmetric-key encryption, proposing new notions of correctness, privacy and authenticity in presence of malicious attackers. We provide strong and intuitive game-based definitions that are easy to understand and yield efficient constructions. We propose a generic construction of threshold authenticated encryption based on any distributed pseudorandom function (DPRF). When instantiated with the two different DPRF constructions proposed by Naor, Pinkas and Reingold (Eurocrypt 1999) and our enhanced versions, we obtain several efficient constructions meeting different security definitions. We implement these variants and provide extensive performance comparisons. Our most efficient instantiation uses only symmetric-key primitives and achieves a throughput of upto 1 million encryptions/decryptions per seconds, or alternatively a sub-millisecond latency with upto 18 participating parties.

Reduced-round AES has been a popular underlying primitive to design new cryptographic schemes and thus its security including distinguishing properties deserves more attention. At Crypto'16, a key-dependent integral distinguisher on 5-round AES was put forward, which opened up a new direction to take more insights into the distinguishing properties of AES. After that, two key-dependent impossible differential (ID) distinguishers on 5-round AES were proposed at FSE'16 and CT-RSA'18, respectively. It is strange that the current key-dependent integral distinguisher requires significantly higher complexities than the key-dependent ID distinguishers, even though they are constructed with the same property of MixColumns ($2^{128} \gg 2^{98.2}$). Proposers of the 5-round key-dependent distinguishers claimed that the corresponding integral and ID distinguishers can only work under chosen-ciphertext and chosen-plaintext settings, respectively, which is very different from the situations of traditional key-independent distinguishers. In this paper, we first construct a novel key-dependent integral distinguisher on 5-round AES with $2^{96}$ chosen plaintexts, which is much better than the previous key-dependent integral distinguisher that requires the full codebook proposed at Crypto'16. Secondly, we show that both distinguishers are valid under either chosen-plaintext setting or chosen-ciphertext setting, which is different from the claims of previous cryptanalysis. However, under different settings, complexities of key-dependent integral distinguishers are very different while those of the key-dependent ID distinguishers are almost the same. We analyze the reasons for it.

Standardization bodies such as NIST and ETSI are currently seeking quantum resistant alternatives to vulnerable RSA and elliptic curve-based public-key algorithms. In this context, we present Round5, a lattice-based cryptosystem providing a key encapsulation mechanism and a public-key encryption scheme. Round5 is based on the General Learning with Rounding problem, unifying non-ring and ring lattice rounding problems into one. Usage of rounding combined with a tight analysis leads to significantly reduced bandwidth and randomness requirements. Round5's reliance on prime-order cyclotomic rings offers a large design space allowing fine-grained parameter optimization. The use of sparse-ternary secret keys improves performance and significantly reduces decryption failure rates at minimal additional cost. The use of error-correcting codes, in combination with ring multiplications in $\mathbb{Z}[x]/(x^{n+1}-1)$ that ensures non-correlated errors, further improves the latter. Round5 parameters have been carefully optimized for bandwidth, while the design facilitates efficient implementation. As a result, Round5 has leading performance characteristics among all NIST post-quantum candidates, and at the same time attains conservative security levels that fully fit NIST's security categories. Round5's schemes share common building blocks, simplifying (security and operational) analysis and code review. Finally, Round5 proposes various approaches of refreshing the system public parameter A, which efficiently prevent precomputation and back-door attacks. Disclaimer: This is a draft version, not all sections are included.

This work proposes the first fine-grained configurable cell array specifically tailored for cryptographic implementations. The proposed architecture can be added to future FPGAs as an application-specific configurable building block, or to an ASIC as an embedded FPGA (eFPGA). The goal is to map cryptographic ciphers on combinatorial cells that are more efficient than general purpose lookup tables in terms of silicon area, configuration memory and combinatorial delay. As a first step in this research direction, we focus on block ciphers and we derive the most suitable cell structure for mapping state-of-the-art algorithms. We develop the related automated design flow, exploiting the synthesis capabilities of Synopsys Design Compiler and the routing capabilities of Xilinx ISE. Our solution is the first cryptography-oriented fine-grained architecture that can be configured using common hardware description languages. We evaluate the performance of our solution by mapping a number of well-known block ciphers onto our new cells. The obtained results show that our proposed architecture drastically outperforms commercial FPGAs in terms of silicon area and configuration memory resources, while obtaining a similar throughput.

Round5 is a Public Key Encryption and Key Encapsulation Mechanism (KEM) based on General Learning with Rounding (GLWR), a lattice problem. We argue that the ring variant of GLWR is better suited for embedded targets than the more common RLWE (Ring Learning With Errors) due to significantly shorter keys and messages. Round5 incorporates GLWR with error correction, building on design features from NIST Post-Quantum Standardization candidates Round2 and Hila5. The proposal avoids Number Theoretic Transforms (NTT), allowing more flexibility in parameter selection and making it simpler to implement. We discuss implementation techniques of Round5 ring variants and compare them to other NIST PQC candidates on lightweight Cortex M4 platform. We show that the current development version of Round5 offers not only the shortest key and ciphertext sizes among Lattice-based candidates, but also has leading performance and implementation size characteristics.

Blockchain technology like Bitcoin is a rapidly growing field of research which has found a wide array of applications. However, the power consumption of the mining process in the Bitcoin blockchain alone is estimated to be at least as high as the electricity consumption of Ireland which constitutes a serious liability to the widespread adoption of blockchain technology. We propose a novel instantiation of a proof of human-work which is a cryptographic proof that an amount of human work has been exercised, and show its use in the mining process of a blockchain. Next to our instantiation there is only one other instantiation known which relies on indistinguishability obfuscation, a cryptographic primitive whose existence is only conjectured. In contrast, our construction is based on the cryptographic principle of multiparty computation (which we use in a black box manner) and thus is the first known feasible proof of human-work scheme. Our blockchain mining algorithm called uMine, can be regarded as an alternative energy-efficient approach to mining.

Transparency logs allow users to audit a potentially malicious service, paving the way towards a more accountable Internet. For example, Certificate Transparency (CT) enables domain owners to audit Certificate Authorities (CAs) and detect impersonation attacks. Yet, to achieve their full potential, transparency logs must be bandwidth-efficient when queried by users. Specifically, everyone should be able to efficiently look up log entries by their key and efficiently verify that the log remains append-only. Unfortunately, without additional trust assumptions, current transparency logs cannot provide both small-sized lookup proofs and small-sized append-only proofs. In fact, one of the proofs always requires bandwidth linear in the size of the log, making it expensive for everyone to query the log. In this paper, we address this gap with a new primitive called an append-only authenticated dictionary (AAD). Our construction is the first to achieve (poly)logarithmic size for both proof types and helps reduce bandwidth consumption in transparency logs. This comes at the cost of increased append times and high memory usage, both of which remain to be improved to make practical deployment possible.

We present HBSH, a simple construction for tweakable length-preserving encryption which supports the fastest options for hashing and stream encryption for processors without AES or other crypto instructions, with a provable quadratic advantage bound. Our composition Adiantum uses NH, Poly1305, XChaCha12, and a single AES invocation. On an ARM Cortex-A7 processor, Adiantum decrypts 4096-byte messages at 10.6 cycles per byte, over five times faster than AES-256-XTS, with a constant-time implementation. We also define HPolyC which is simpler and has excellent key agility at 13.6 cycles per byte.

Recent works by Kellaris et al. (CCS’16) and Lacharite et al. (SP’18) demonstrated attacks of data recovery for encrypted databases that support rich queries such as range queries. In this paper, we develop the first data recovery attacks on encrypted databases supporting one-dimensional k-nearest neighbor (k-NN) queries, which are widely used in spatial data management. Our attacks exploit a generic k-NN query leakage profile: the attacker observes the identifiers of matched records. We consider both unordered responses, where the leakage is a set, and ordered responses, where the leakage is a k-tuple ordered by distance from the query point. As a first step, we perform a theoretical feasibility study on exact reconstruction, i.e., recovery of the exact plaintext values of the encrypted database. For ordered responses, we show that exact reconstruction is feasible if the attacker has additional access to some auxiliary information that is normally not available in practice. For unordered responses, we prove that exact reconstruction is impossible due to the infinite number of valid reconstructions. As a next step, we propose practical and more realistic approximate reconstruction attacks so as to recover an approximation of the plaintext values. For ordered responses, we show that after observing enough query responses, the attacker can approximate the client’s encrypted database with considerable accuracy. For unordered responses we characterize the set of valid reconstructions as a convex polytope in a k-dimensional space and present a rigorous attack that reconstructs the plaintext database with bounded approximation error. As multidimensional spatial data can be efficiently processed by mapping it to one dimension via Hilbert curves, we demonstrate our approximate reconstruction attacks on privacy-sensitive geolocation data. Our experiments on real-world datasets show that our attacks reconstruct the plaintext values with relative error ranging from 2.9% to 0.003%.

Randomness is an essential resource for cryptography. For practical randomness generation, the security notion of pseudorandom generators (PRGs) intends to automatically preserve (computational) security of cryptosystems when used in implementation. Nevertheless, some opposite case such as in computational randomness extractors (Barak et al., CRYPTO 2011) is known (but not yet systematically studied so far) where the security can be lost even by applying secure PRGs. The present paper aims at pushing ahead the observation and understanding about such a phenomenon; we reveal such situations at layers of primitives and protocols as well, not just of building blocks like randomness extractors. We present three typical types of such cases: (1) adversaries can legally see the seed of the PRGs (including the case of randomness extractors); (2) the set of "bad'' randomness may be not efficiently recognizable; (3) the formulation of a desired property implicitly involves non-uniform distinguishers for PRGs. We point out that the semi-honest security of multiparty computation also belongs to Type 1, while the correctness with negligible decryption error probability for public key encryption belongs to Types 2 and 3. We construct examples for each type where a secure PRG (against uniform distinguishers only, for Type 3) does not preserve the security/correctness of the original scheme; and discuss some countermeasures to avoid such an issue.

Thermal laser stimulation (TLS) is a failure analysis technique, which can be deployed by an adversary to localize and read out stored secrets in the SRAM of a chip. To this date, a few proof-of-concept experiments based on TLS or similar approaches have been reported in the literature, which do not reflect a real attack scenario. Therefore, it is still questionable whether this attack technique is applicable to modern ICs equipped with side-channel countermeasures. The primary aim of this work is to assess the feasibility of launching a TLS attack against a device with robust security features. To this end, we select a modern FPGA, and more specifically, its key memory, the so-called battery-backed SRAM (BBRAM), as a target. We demonstrate that an attacker is able to extract the stored 256-bit AES key used for the decryption of the FPGA’s bitstream, by conducting just a single non-invasive measurement. Moreover, it becomes evident that conventional countermeasures are incapable of preventing our attack since the FPGA is turned off during key recovery. Based on our time measurements, the required effort to develop the attack is shown to be less than 7 hours. To avert this powerful attack, we propose a low-cost and CMOS compatible countermeasure circuit, which is capable of protecting the BBRAM from TLS attempts even when the FPGA is powered off. Using a proof-of-concept prototype of our countermeasure, we demonstrate its effectiveness against TLS key extraction attempts.

We provide lattice-based protocols allowing to prove relations among committed integers. While the most general zero-knowledge proof techniques can handle arithmetic circuits in the lattice setting, adapting them to prove statements over the integers is non-trivial, at least if we want to handle exponentially large integers while working with a polynomial-size modulus $q$. For a polynomial $L$, we provide zero-knowledge arguments allowing a prover to convince a verifier that committed $L$-bit bitstrings $x$, $y$ and $z$ are the binary representations of integers $X$, $Y$ and $Z$ satisfying $Z=X+Y$ over $\mathbb{Z}$. The complexity of our arguments is only linear in $L$. Using them, we construct arguments allowing to prove inequalities $X<Z$ among committed integers, as well as arguments showing that a committed $X$ belongs to a public interval $[\alpha,\beta]$, where $\alpha$ and $\beta$ can be arbitrarily large. Our range arguments have logarithmic cost (i.e., linear in $L$) in the maximal range magnitude. Using these tools, we obtain zero-knowledge arguments showing that a committed element $X$ does not belong to a public set $S$ using $\widetilde{\mathcal{O}}(n \cdot \log |S|)$ bits of communication, where $n$ is the security parameter. We finally give a protocol allowing to argue that committed $L$-bit integers $X$, $Y$ and $Z$ satisfy multiplicative relations $Z=XY$ over the integers, with communication cost subquadratic in $L$. To this end, we use our protocol for integer addition to prove the correct recursive execution of Karatsuba's multiplication algorithm. The security of our protocols relies on standard lattice assumptions with polynomial modulus and polynomial approximation factor.

Searchable symmetric encryption (SSE) schemes are commonly proposed to enable search in a protected unstructured documents such as email archives or any set of sensitive text files. However, some SSE schemes have been recently proposed in order to protect relational databases. Most of the previous attacks on SSE schemes have only targeted its common use case, protecting unstructured data. In this work, we propose a new inference attack on relational databases protected via SSE schemes. Our inference attack enables a passive adversary with only basic knowledge about the meta-data information of the target relational database to recover the attribute names of some observed queries. This violates query privacy since the attribute name of a query is secret.

In this document, we introduce PKP-DSS: a Digital Signature Scheme based on the Permuted Kernel Problem (PKP). PKP is a simple NP-hard combinatorial problem that consists of finding a kernel for a publicly known matrix, such that the kernel vector is a permutation of a publicly known vector. This problem was used to develop an Identification Scheme which has a very efficient implementation on low-cost smart cards. From this zero-knowledge identification scheme, we derive PKP-DSS with the traditional Fiat-Shamir transform. Thus, PKP-DSS has security that can be provably reduced, in the classical random oracle model, to the hardness of random instances of PKP (or, if wanted, to any specific family of PKP instances). We propose parameter sets following the analysis of State-of-the-art attacks on PKP. We show that PKP-DSS is competitive with other signatures derived from Zero-Knowledge identification schemes. In particular, PKP-DSS-128 gives a signature size of approximately 20 KBytes for 128 bits of classical security, which is approximately 30% smaller than MQDSS. Moreover, our proof-of-concept implementation shows that PKP-DSS-128 is an order of magnitude faster than MQDSS which in turn is faster than Picnic2, SPHINCS,... Since the PKP is NP-hard and since there are no known quantum attacks for solving PKP significantly better than classical attacks, we believe that our scheme is post-quantum secure.

Two vectorial Boolean functions are ``CCZ-equivalent'' if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a CCZ-equivalence class into its Extended-Affine (EA) equivalence classes; EA-equivalence being a simple particular case of CCZ-equivalence. In this paper, we characterize CCZ-equivalence as a property of the zeroes in the Walsh spectrum of a function $F : \mathbb{F}_2^{n} \to \mathbb{F}_2^{m}$ or, equivalently, of the zeroes in its Difference Distribution Table. We use this framework to show how to efficiently upper bound the number of distinct EA-equivalence classes in a given CCZ-equivalence class. More importantly, we prove that it is possible to go from a specific member of any EA-equivalence class to a specific member of another EA-equivalence class in the same CCZ-equivalence class using an operation called \emph{twisting}; so that CCZ-equivalence can be reduced to the association of EA-equivalence and twisting. Twisting a function is a simple process and its possibility is equivalent to the existence of a particular decomposition of the function considered. Using this knowledge, we revisit several results from the literature on CCZ-equivalence and show how they can be interpreted in light of our new framework. Our results rely on a new concept, the ``thickness'' of a space (or linear permutation), which can be of independent interest.

A verifiable delay function (VDF) is an important tool used for adding delay in decentralized applications. This short note briefly surveys and compares two recent beautiful Verifiable Delay Functions (VDFs), one due to Pietrzak and the other due to Wesolowski. We also provide a new computational proof of security for one of them, and compare the complexity assumptions needed for both schemes.

Group key distribution protocol is a mechanism in which a group key is generated and distributed by KGC to a set of communicating parties in a group. This group key generally ensures secure communication among communicating parties in an unsecure channel. Harn and Lin protocol is one such. It is based on Shamir's secret sharing scheme. Nam et al. exposed the vulnerability in Harn and Lin protocol through their replay attack and proposed a countermeasure using nonce mechanism. In this paper, we are generalizing the replay attack proposed by Nam et al. and proposing an alternative countermeasure without using nonce mechanism. Novelty of our countermeasure is that KGC is not required to detect replay messages and hence each user doesn't need to compute authentication message as in Nam et al. Proposed countermeasure thereby brings down the computational complexity of the scheme.

Secure Multi-Party Computation (MPC) with small number of parties is an interesting area of research, primarily due to its ability to model most real-life MPC applications and the simplicity and efficiency of the resulting protocols. In this work, we present efficient, constant-round 3-party (3PC) and 4-party (4PC) protocols in the honest-majority setting that achieve strong security notions of fairness (corrupted parties receive their output only if all honest parties receive output) and guaranteed output delivery (corrupted parties cannot prevent honest parties from receiving their output). Being constant-round, our constructions are suitable for Internet-like high-latency networks and are built from garbled circuits (GC). Assuming the minimal model of pairwise-private channels, we present two protocols that involve computation and communication of a single GC-- (a) a 4-round 3PC with fairness, (b) a 5-round 4PC with guaranteed output delivery. Empirically, our protocols are on par with the best known 3PC protocol of Mohassel et al. [CCS 2015] that only achieves security with selective abort, in terms of the computation time, LAN runtime, WAN runtime and communication cost. In fact, our 4PC outperforms the 3PC of Mohassel et al. significantly in terms of per-party computation and communication cost. With an extra GC, we improve the round complexity of our 4PC to four rounds. The only 4PC in our setting, given by Ishai et al. [CRYPTO 2015], involves 12 GCs. Assuming an additional broadcast channel, we present a 5-round 3PC with guaranteed output delivery that involves computation and communication of a single GC. A broadcast channel is inevitable in this setting for achieving guaranteed output delivery, owing to an impossibility result in the literature. The overall broadcast communication of our protocol is nominal and most importantly, is independent of the circuit size. This protocol too induces a nominal overhead compared to the protocol of Mohassel et al.

The key exchange protocol of Diffie and Hellman, which can be defined for any group, has the special feature of using only exponentiations. In particular, it can also be instantiated in Kummer varieties, which are not groups, and in the post-quantum isogeny-based setting with the supersingular isogeny DH scheme of De Feo, Jao and Plût (SIDH). In this article, we propose a new simple oblivious transfer (OT) protocol, based on the Diffie-Hellman key exchange, that only uses exponentiations; we also revisit the older Wu-Zhang-Wang scheme. Both protocols can be directly instantiated on fast Kummer varieties; more importantly, they can also be transposed in the post-quantum SIDH setting. The semantic security of our proposals relies on the hardness of non-standard versions of the (supersingular) Diffie-Hellman problem, that are investigated within this article. To the best of our knowledge, these protocols are the simplest secure discrete-log based OT schemes using only exponentiations, and the first isogeny-based OT schemes.

The ongoing CAESAR competition aims at finding authenticated encryption schemes that offer advantages over AES-GCM for several use-cases, including lightweight applications. ACORN and Ascon are the two finalists for this profile. Our paper compares these two candidates according to their resilience against differential power analysis and their ability to integrate countermeasures against such attacks. Especially, we focus on software implementations and provide benchmarks for several security levels on an ARM Cortex-M3 embedded microprocessor.

Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secret-sharing a function from a given function family $\mathcal F$. More concretely, an $m$-party FSS scheme splits a function $f:\{0,1\}^n\to \mathbb G$, for some abelian group $\mathbb G$, into functions $f_1,\ldots,f_m$, described by keys $k_1,\ldots,k_m$, such that $f=f_1+\ldots+f_m$ and every strict subset of the keys hides $f$. A Distributed Point Function (DPF) is a special case where $\mathcal F$ is the family of point functions, namely functions $f_{\alpha,\beta}$ that evaluate to $\beta$ on the input $\alpha$ and to 0 on all other inputs. FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for large-scale anonymous messaging. We improve and extend previous results in several ways: - Simplified FSS constructions. We introduce a tensoring operation for FSS which is used to obtain a conceptually simpler derivation of previous constructions and present our new constructions. - Improved 2-party DPF. We reduce the key size of the PRG-based DPF scheme of Boyle et al. roughly by a factor of 4 and optimize its computational cost. The optimized DPF significantly improves the concrete costs of 2-server PIR and related primitives. - FSS for new function families. We present an efficient PRG-based 2-party FSS scheme for the family of decision trees, leaking only the topology of the tree and the internal node labels. We apply this towards FSS for multi-dimensional intervals. We also present a general technique for obtaining more expressive FSS schemes by increasing the number of parties. - Verifiable FSS. We present efficient protocols for verifying that keys $(k^*_1,\ldots,k^*_m)$, obtained from a potentially malicious user, are consistent with some $f\in\mathcal F$. Such a verification may be critical for applications that involve private writing or voting by many users.

Distributed Oblivious RAM (DORAM) protocols---in which parties obliviously access a shared location in a shared array---are a fundamental component of secure-computation protocols in the RAM model. We show here an efficient, 3-party DORAM protocol with semi-honest security for a single corrupted party. To the best of our knowledge, ours is the first protocol for this setting that runs in constant rounds, requires sublinear communication and linear work, and makes only black-box use of cryptographic primitives. We believe our protocol is also concretely more efficient than existing solutions. As a building block of independent interest, we construct a 3-server distributed point function with security against two colluding servers that is simpler and has better concrete efficiency than prior work.

We put forward the notion of subvector commitments (SVC): An SVC allows one to open a committed vector at a set of positions, where the opening size is independent of length of the committed vector and the number of positions to be opened. We propose two constructions under variants of the root assumption and the CDH assumption, respectively. We further generalize SVC to a notion called linear map commitments (LMC), which allows one to open a committed vector to its images under linear maps with a single short message, and propose a construction over pairing groups. Equipped with these newly developed tools, we revisit the ``CS proofs'' paradigm [Micali, FOCS 1994] which turns any arguments with public-coin verifiers into non-interactive arguments using the Fiat-Shamir transform in the random oracle model. We propose a compiler that turns any (linear, resp.) PCP into a non-interactive argument, using exclusively SVCs (LMCs, resp.). For an approximate $80$ bits of soundness, we highlight the following new implications: - There exists a succinct non-interactive argument of knowledge (SNARK) with public-coin setup with proofs of size 5360 bits, under the adaptive root assumption over class groups of imaginary quadratic orders against adversaries with runtime $2^{128}$. At the time of writing, this is the shortest SNARK with public-coin setup. - There exists a non-interactive argument with private-coin setup, where proofs consist of 2 group elements and 3 field elements, in the generic bilinear group model.

The success of the Ethereum blockchain as a decentralized application platform with a distributed consensus protocol has made many organizations start to invest into running their business on top of it. Technically, the most impressive feature behind the success of Ethereum is its support for a Turing complete language.On the other hand, the inherent transparency and, consequently, the lack of privacy poses a great challenge for many financial applications. In this paper, we tackle this challenge and present a smart contract for a verifiable sealed-bid auction on the Ethereum blockchain. In a nutshell, initially, the bidders submit homomorphic commitments to their sealed-bids on the contract. Subsequently, they reveal their commitments secretly to the auctioneer via a public key encryption scheme. Then, according to the auction rules, the auctioneer determines and claims the winner of the auction. Finally, we utilize interactive zero-knowledge proof protocols between the smart contract and the auctioneer to verify the correctness of such a claim. The underlying protocol of the proposed smart contract is partially privacy-preserving. To be precise, no information about the losing bids is leaked to the bidders. We provide an analysis of the proposed protocol and the smart contract design, in addition to the estimated gas costs associated with the different transactions.

Cramer and Damg\aa{}rd were the first to propose a constant-rounds protocol for securely solving a linear system of unknown rank over a finite field in multiparty computation (MPC). For $m$ linear equations and $n$ unknowns, and for the case $m\leq n$, the computational complexity of their protocol is $O(n^5)$. Follow-up work (by Cramer, Kiltz, and Padró) proposes another constant-rounds protocol for solving this problem, which has complexity $O(m^4+n^2 m)$. For certain applications, such asymptotic complexities might be prohibitive. In this work, we improve the asymptotic computational complexity of solving a linear system over a finite field, thereby sacrificing the constant-rounds property. We propose two protocols: (1) a protocol based on pivoting-free Gaussian elimination with computational complexity $O(n^3)$ and linear round complexity, and (2) a protocol based on block-recursive matrix decomposition, having $O(n^2)$ computational complexity (assuming ``cheap'' secure inner products as in Shamir's secret-sharing scheme) and $O(n^{1.585})$ (super-linear) round complexity.

We construct a concretely practical proof-of-space (PoS) with arbitrarily tight security based on stacked depth robust graphs and constant-degree expander graphs. A proof-of-space (PoS) is an interactive proof system where a prover demonstrates that it is persistently using space to store information. A PoS is arbitrarily tight if the honest prover uses exactly N space and for any $\epsilon > 0$ the construction can be tuned such that no adversary can pass verification using less than $1-\epsilon N$ space. Most notably, the degree of the graphs in our construction are independent of $\epsilon$, and the number of layers is only $O(\log(1/\epsilon))$. The proof size is $O(d/\epsilon)$. The degree $d$ depends on the depth robust graphs, which are only required to maintain $\Omega(N)$ depth in subgraphs on 80% of the nodes. Our tight PoS is also secure against parallel attacks. Tight proofs of space are necessary for proof-of-replication (PoRep), which is a publicly verifiable proof that the prover is dedicating unique resources to storing one or more retrievable replicas of a file. Our main PoS construction can be used as a PoRep, but data extraction is as inefficient as replica generation. We present a second variant of our construction called ZigZag PoRep that has fast/parallelizable data extraction compared to replica generation and maintains the same space tightness while only increasing the number of levels by roughly a factor two.

Secure sketch produces public information of its input $w$ without revealing it, yet, allows the exact recovery of $w$ given another value $w'$ that is close to $w$. Therefore, it can be used to reliably reproduce any error-prone a secret sources (i.e., biometrics) stored in secret storage. However, some sources have lower entropy compared to the error itself, formally called ``more error than entropy", a standard secure sketch cannot show its security promise perfectly to these kind of sources. This paper focuses on secure sketch. We propose a concrete construction for secure sketch. We show security to all noisy sources, including the trivial source with zero min-entropy. In addition, our construction comes with efficient recovery algorithm operates in polynomial time in the sketch size, which can tolerate high number of error rate arbitrary close to 1/2. Above result act in conjunction to our derivation on the solution to a well-known NP-complete coding problem, implying $P=NP$.

We present high-speed implementations of the post-quantum supersingular isogeny Diffie-Hellman key exchange (SIDH) and the supersingular isogeny key encapsulation (SIKE) protocols for 32-bit ARMv7-A processors with NEON support. The high performance of our implementations is mainly due to carefully optimized multiprecision and modular arithmetic that finely integrates both ARM and NEON instructions in order to reduce the number of pipeline stalls and memory accesses, and a new Montgomery reduction technique that combines the use of the UMAAL instruction with a variant of the hybrid-scanning approach. In addition, we present efficient implementations of SIDH and SIKE for 64-bit ARMv8-A processors, based on a high-speed Montgomery multiplication that leverages the power of 64-bit instructions. Our experimental results consolidate the practicality of supersingular isogeny-based protocols for many real-world applications. For example, a full key-exchange execution of SIDHp503 is performed in about 176 million cycles on an ARM Cortex-A15 from the ARMv7-A family (i.e., 88 milliseconds @2.0GHz). On an ARM Cortex-A72 from the ARMv8-A family, the same operation can be carried out in about 90 million cycles (i.e., 45 milliseconds @1.992GHz). All our software is protected against timing and cache attacks. The techniques for modular multiplication presented in this work have broad applications to other cryptographic schemes.

In this paper, we propose a novel cryptanalytic technique called correlated sequence attack on block ciphers. Our attack exploits the properties of given key dependent sequences of length $t$ to obtain other keyed sequences of same length with $\sigma$ ($0\le \sigma < t$) computations of the non-linear function. We call these sequences $(\sigma,t)$-correlated sequences, and utilize them in a meet-in-the-middle attack for $2t$ rounds. We apply this technique on Simon-32/64 and Simeck-32/64 block ciphers, construct $(1, 8)$-correlated sequences and present the first 25-round attack on both ciphers. Next, we analyze the 8-th element of these sequences by considering the key scheduling algorithms and differential properties, and show that the attack can be improved by two rounds with the same complexities as of the 25-round attack. Overall, our technique is used to attack up to 27 rounds of both Simon-32/64 and Simeck-32/64 with a time complexity less than that of average exhaustive search and data complexity of 3. Our attack extends the number of previously attacked rounds by 4 and has a success probability 1. This reduces the security margin of both these ciphers to 16%. Up to our knowledge, this is currently the best attack on Simon-32/64 and Simeck-32/64.

Order-revealing encryption (ORE) is a popular primitive for outsourcing encrypted databases, as it allows for efficiently performing range queries over encrypted data. Unfortunately, a series of works, starting with Naveed et al. (CCS 2015), have shown that when the adversary has a good estimate of the distribution of the data, ORE provides little protection. In this work, we consider the case that the database entries are drawn identically and independently from a distribution of known shape, but for which the mean and variance are not (and thus the attacks of Naveed et al. do not apply). We define a new notion of security for ORE, called parameter-hiding ORE, which maintains the secrecy of these parameters. We give a construction of ORE satisfying our new definition from bilinear maps.

The US federal court system is exploring ways to improve the accountability of electronic surveillance, an opaque process often involving cases sealed from public view and tech companies subject to gag orders against informing surveilled users. One judge has proposed publicly releasing some metadata about each case on a paper cover sheet as a way to balance the competing goals of (1) secrecy, so the target of an investigation does not discover and sabotage it, and (2) accountability, to assure the public that surveillance powers are not misused or abused. Inspired by the courts' accountability challenge, we illustrate how accountability and secrecy are simultaneously achievable when modern cryptography is brought to bear. Our system improves configurability while preserving secrecy, offering new tradeoffs potentially more palatable to the risk-averse court system. Judges, law enforcement, and companies publish commitments to surveillance actions, argue in zero-knowledge that their behavior is consistent, and compute aggregate surveillance statistics by multi-party computation (MPC). We demonstrate that these primitives perform efficiently at the scale of the federal judiciary. To do so, we implement a hierarchical form of MPC that mirrors the hierarchy of the court system. We also develop statements in succinct zero-knowledge (SNARKs) whose specificity can be tuned to calibrate the amount of information released. All told, our proposal not only offers the court system a flexible range of options for enhancing accountability in the face of necessary secrecy, but also yields a general framework for accountability in a broader class of "secret information processes."

Inner product functional encryption (IPFE), introduced by Abdalla et al. (PKC2015), is a kind of functional encryption supporting only inner product functionality. All previous IPFE schemes are bounded schemes, meaning that the vector length that can be handled in the scheme is fixed in the setup phase. In this paper, we propose the first unbounded IPFE schemes, in which we do not have to fix the lengths of vectors in the setup phase and can handle (a priori) unbounded polynomial lengths of vectors. Our first scheme is private-key based and fully function hiding. That is, secret keys hide the information of the associated function. Our second scheme is public-key based and provides adaptive security in the indistinguishability based security definition. Both our schemes are based on SXDH, which is a well-studied standard assumption, and secure in the standard model. Furthermore, our schemes are quite efficient, incurring an efficiency loss by only a small constant factor from previous bounded function hiding schemes.

Password managers (aka stores or vaults) allow a user to store and retrieve (usually high-entropy) passwords for her multiple password-protected services by interacting with a "device" serving the role of the manager (e.g., a smartphone or an online third-party service) on the basis of a single memorable (low-entropy) master password. Existing password managers work well to defeat offline dictionary attacks upon web service compromise, assuming the use of high-entropy passwords is enforced. However, they are vulnerable to leakage of all passwords in the event the device is compromised, due to the need to store the passwords encrypted under the master password and/or the need to input the master password to the device (as in smartphone managers). Evidence exists that password managers can be attractive attack targets. In this paper, we introduce a novel approach to password management, called SPHINX, which remains secure even when the password manager itself has been compromised. In SPHINX the information stored on the device is information theoretically independent of the user's master password --- an attacker breaking into the device learns no information about the master password or the user's site-specific passwords. Moreover, an attacker with full control of the device, even at the time the user interacts with it, learns nothing about the master password --- the password is not entered into the device in plaintext form or in any other way that may leak information on it. Unlike existing managers, SPHINX produces strictly high-entropy passwords and makes it compulsory for the users to register these randomized passwords with the web services, hence fully defeating offline dictionary attack upon service compromise. The design and security of SPHINX is based on the device-enhanced PAKE model of Jarecki et al. that provides the theoretical basis for this construction and is backed by rigorous cryptographic proofs of security. While SPHINX is suitable for different device and online platforms, in this paper, we report on its concrete instantiation on smartphones given their popularity and trustworthiness as password managers (or even two-factor authentication). We present the design, implementation and performance evaluation of SPHINX, offering prototype browser plugins, smartphone apps and transparent device-client communication. Based on our inspection analysis, the overall user experience of SPHINX improves upon current managers. We also report on a lab-based usability study of SPHINX, which indicates that users' perception of SPHINX security and usability is high and satisfactory when compared to regular password-based authentication. Finally, we discuss how SPHINX may be extended to an online service for the purpose of back-up or as an independent password manager.

In the last decade, location information became easily obtainable using off-the-shelf mobile devices. This gave a momentum to developing Location Based Services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need of protecting privacy of these users. In this work, we address this issue by designing, implementing, and evaluating multiple algorithms for Privacy-Preserving Location Proximity (PPLP) that are based on different secure computation protocols. Our PPLP protocols are well-suited for different scenarios: for saving bandwidth, energy/computational power, or for faster runtimes. Furthermore, our algorithms have runtimes of a few milliseconds to hundreds of milliseconds and bandwidth of hundreds of bytes to one megabyte. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in our protocols, such that the input-dependent online phase runs in just a few milliseconds.

The current state of the art of Boolean masking for the modular addition operation in software has a very high performance overhead. Firstly, the instruction count is very high compared to a normal addition operation. Secondly, until recently, the entropy consumed by such protections was also quite high. Our paper significantly improves both aspects, by applying the Threshold Implementation (TI) methodology with two shares and by reusing internal values as randomness source in such a way that the uniformity is always preserved. Our approach performs considerably faster compared to the previously known masked addition and subtraction algorithms by Coron et al. and Biryukov et al. improving the state of the art by 36%, if we only consider the number of ARM assembly instructions. Furthermore, similar to the masked adder from Biryukov et al. we reduce the amount of randomness and only require one bit additional entroy per addition, which is a good trade-off for the improved performance. We applied our improved masked adder to ChaCha20, for which we provide two new first-order protected implementations and achieve a 36% improvement over the best published result for ChaCha20 using an ARM Cortex-M4 microprocessor.

eSTREAM brought to the attention of the cryptographic community a number of stream ciphers including Grain v0 and its revised version Grain v1. The latter was selected as a finalist of the competition's hardware-based portfolio. The Grain family includes two more instantiations, namely Grain 128 and Grain 128a. The scope our paper is to provide an insight on how to obtain secure configurations of the Grain family of stream ciphers. We propose different variants for Grain and analyze their security with respect to slide attacks. More precisely, as various attacks against initialization algorithms of Grain were discussed in the literature, we study the security impact of various parameters which may influence the LFSR's initialization scheme.

Recently there has been much academic and industrial interest in practical implementations of *zero knowledge proofs*. These techniques allow a party to *prove* to another party that a given statement is true without revealing any additional information. In a Bitcoin-like system, this allows a payer to prove validity of a payment without disclosing the payment's details. Unfortunately, the existing systems for generating such proofs are very expensive, especially in terms of memory overhead. Worse yet, these systems are "monolithic", so they are limited by the memory resources of a single machine. This severely limits their practical applicability. We describe DIZK, a system that *distributes* the generation of a zero knowledge proof across machines in a compute cluster. Using a set of new techniques, we show that DIZK scales to computations of up to billions of logical gates (100x larger than prior art) at a cost of 10$\mu$s per gate (100x faster than prior art). We then use DIZK to study various security applications.

Lattice-based cryptographic primitives are believed to have the property against attacks by quantum computers. In this work, we present a KEA-style authenticated key exchange protocol based on the ring learning with errors problem whose security is proven in the BR model with weak perfect forward secrecy. With properties of KEA such as implicit key authentication and simplicity, our protocol also enjoys many properties of lattice-based cryptography, namely asymptotic efficiency, conceptual simplicity, worst-case hardness assumption, and resistance to attacks by quantum computers. Our lattice-based authenticated key exchange protocol is more efficient than the protocol of Zhang et al. (EUROCRYPT 2015) with more concise structure, smaller key size and lower bandwidth. Also, our protocol enjoys the advantage of optimal online efficiency and we improve our protocol with pre-computation.

Resistance against differential cryptanalysis is an important design criteria for any modern block cipher and most designs rely on finding some upper bound on probability of single differential characteristics. However, already at EUROCRYPT'91, Lai et al. comprehended that differential cryptanalysis rather uses differentials instead of single characteristics. In this paper, we consider exactly the gap between these two approaches and investigate this gap in the context of recent lightweight cryptographic primitives. This shows that for many recent designs like Midori, Skinny or Sparx one has to be careful as bounds from counting the number of active S-boxes only give an inaccurate evaluation of the best differential distinguishers. For several designs we found new differential distinguishers and show how this gap evolves. We found an 8-round differential distinguisher for Skinny-64 with a probability of $2^{-56.93}$, while the best single characteristic only suggests a probability of $2^{-72}$. Our approach is integrated into publicly available tools and can easily be used when developing new cryptographic primitives. Moreover, as differential cryptanalysis is critically dependent on the distribution over the keys for the probability of differentials, we provide experiments for some of these new differentials found, in order to confirm that our estimates for the probability are correct. While for Skinny-64 the distribution over the keys follows a Poisson distribution, as one would expect, we noticed that Speck-64 follows a bimodal distribution, and the distribution of Midori-64 suggests a large class of weak keys.

The division property method is a technique to determine integral distinguishers on block ciphers. While the complexity of finding these distinguishers is higher, it has recently been shown that MILP and SAT solvers can efficiently find such distinguishers. In this paper, we provide a framework to automatically find those distinguishers which solely requires a description of the cryptographic primitive. We demonstrate that by finding integral distinguishers for 30 primitives with different design strategies. We provide several new or improved bit-based division property distinguishers for ChaCha, Chaskey, DES, GIFT, LBlock, Mantis, Qarma, RoadRunner, Salsa and SM4. Furthermore, we present an algorithm to find distinguishers with lower data complexity more efficiently.

Lattice-based schemes are among the most promising post-quantum schemes, yet the effect of both parameter and implementation choices on their side-channel resilience is still poorly understood. Aysu et al. (HOST'18) recently investigated single-trace attacks against the core lattice operation, namely multiplication between a public matrix and a "small" secret vector, in the context of a hardware implementation. We complement this work by considering single-trace attacks against software implementations of "ring-less" LWE-based constructions. Specifically, we target Frodo, one of the submissions to the standardisation process of NIST, when implemented on an (emulated) ARM Cortex M0 processor. We confirm Aysu et al.'s observation that a standard divide-and-conquer attack is insufficient and instead we resort to a sequential, extend-and-prune approach. In contrast to Aysu et al. we find that, in our setting where the power model is far from being as clear as theirs, both profiling and less aggressive pruning are needed to obtain reasonable key recovery rates for SNRs of practical relevance. Our work drives home the message that parameter selection for LWE schemes is a double-edged sword: the schemes that are deemed most secure against (black-box) lattice attacks can provide the least security when considering side-channels. Finally, we suggest some easy countermeasures that thwart standard extend-and-prune attacks.

Lattice-based cryptography is one of the most promising candidates being considered to replace current public-key systems in the era of quantum computing. In 2016, Bos et al. proposed the key exchange scheme FrodoCCS, that is also a submission to the NIST post-quantum standardization process, modified as a key encapsulation mechanism (FrodoKEM). The security of the scheme is based on standard lattices and the learning with errors problem. Due to the large parameters, standard lattice-based schemes have long been considered impractical on embedded devices. The FrodoKEM proposal actually comes with parameters that bring standard lattice-based cryptography within reach of being feasible on constrained devices. In this work, we take the final step of efficiently implementing the scheme on a low-cost FPGA and microcontroller devices and thus making conservative post-quantum cryptography practical on small devices. Our FPGA implementation of the decapsulation (the computationally most expensive operation) needs 7,220 look-up tables (LUTs), 3,549 flip-flops (FFs), a single DSP, and only 16 block RAM modules. The maximum clock frequency is 162 MHz and it takes 20.7 ms for the execution of the decapsulation. Our microcontroller implementation has a 66% reduced peak stack usage in comparison to the reference implementation and needs 266 ms for key pair generation, 284 ms for encapsulation, and 286 ms for encapsulation. Our results contribute to the practical evaluation of a post-quantum standardization candidate.

This paper takes a critical look at the recent trend of building electronic voting systems on top of block chain technology. Even though being very appealing from the election integrity perspective, block chains have numerous technical, economical and even political drawbacks that need to be taken into account. Selecting a good trade-off between desirable properties and restrictions imposed by different block chain implementations is a highly non-trivial task. This paper aims at bringing some clarity into performing this task. We will mostly be concentrating on public permissionless block chains and their applications as bulletin board implementations as these are the favourite choices in majority of the recent block chain based voting protocol proposals.

We present a new primitive supporting file replication in distributed storage networks (DSNs) called a Public Incompressible Encoding (PIE). PIEs operate in the challenging public DSN setting where files must be encoded and decoded with public randomness—i.e., without encryption—and retention of redundant data must be publicly verifiable. They prevent undetectable data compression, allowing DSNs to use monetary rewards or penalties in incentivizing economically rational servers to properly replicate data. Their definition also precludes critical, demonstrated attacks involving parallelism via ASICs and other custom hardware. Our PIE construction is the first to achieve experimentally validated near-optimal performance—within a factor of 4 of optimal by one metric. It also allows decoding orders of magnitude faster than encoding, unlike other comparable constructions. We achieve this high security and performance using a graph construction called a Dagwood Sandwich Graph (DSaG), built from a novel interleaving of depth-robust graphs and superconcentrators. PIEs' performance makes them appealing for DSNs, such as the proposed Filecoin system and Ethereum data sharding. Conversely, their near-optimality establishes concerning bounds on the practical financial and energy costs of DSNs allowing arbitrary data.

A well-known issue in electronic voting is the risk of manipulation of the cast vote. For countering this risk, a number of methods have been proposed that enable the voter to verify that their cast vote actually represents their intention, the so-called cast-as-intended verification. Yet, the empirical studies on the voter's behaviour towards using these methods show that often only a small amount of voters attempts the verification or succeeds in performing it. Poor usability of the verification procedure has been often named as the main reason for such a failure of the voters to verify. Research into human factors in other security domains, however, reveals other reasons aside from poor usability, that hinder the proper adoption of security practices among end users. In this paper we discuss these factors with respect to their applicability to cast-as-intended verification. Our results indicate, that many of these factors are potentially relevant in the electronic voting context, too. Correspondingly, we conclude that additional measures aside from ensuring the usability of the cast as intended verification mechanisms are required in order to make sure that the voters successfully verify the integrity of their votes. As such, corresponding mechanisms are proposed.

The CCA-secure lattice-based post-quantum key encapsulation scheme Saber is a candidate in the NIST's post-quantum cryptography standardization process. In this paper, we study the implementation aspects of Saber in resource-constrained microcontrollers from the ARM Cortex-M series which are very popular for realizing IoT applications. In this work, we carefully optimize various parts of Saber for speed and memory. We exploit digital signal processing instructions and efficient memory access for a fast implementation of polynomial multiplication. We also use memory efficient Karatsuba and just-in-time strategy for generating the public matrix of the module lattice to reduce the memory footprint. We also show that our optimizations can be combined with each other seamlessly to provide various speed-memory trade-offs. Our speed optimized software takes just 1,147K, 1,444K, and 1,543K clock cycles on a Cortex-M4 platform for key generation, encapsulation and decapsulation respectively. Our memory efficient software takes 4,786K, 6,328K, and 7,509K clock cycles on an ultra resource-constrained Cortex-M0 platform for key generation, encapsulation, and decapsulation respectively while consuming only 6.2 KB of memory at most. These results show that lattice-based key encapsulation schemes are perfectly practical for securing IoT devices from quantum computing attacks.

After the concept of a Fuzzy Extractor (FE) was rst introduced by Dodis et al. , it has been regarded as one of the candidate solutions for key management utilizing biometric data. With a noisy input such as biometrics, FE generates a public helper value and a random secret key which is reproducible given another input similar to the original input. However, "helper values" may cause some leakage of information when generated repeatedly by correlated inputs, thus reusability should be considered as an important property. Recently, Canetti et al. (Eurocrypt 2016) proposed a FE satisfying both reusability and robustness with inputs from low-entropy distributions. Their strategy, the so-called Sample-then-Lock method, is to sample many partial strings from a noisy input string and to lock one secret key with each partial string independently. In this paper, modifying this reusable FE, we propose a new FE with size-reduced helper data hiring a threshold scheme. Our new FE also satises both reusability and robustness, and requires much less storage memory than the original. To show the advantages of this scheme, we analyze and compare our scheme with the original in concrete parameters of the biometric, IrisCode. As a result, on 1024-bit inputs, with false rejection rate 0.5 and error tolerance 0.25, while the original requires about 1TB for each helper value, our scheme requires only 300MB with an additional 1.35GB of common data which can be used for all helper values.

Deoxys-BC is the internal tweakable block cipher of Deoxys, a third-round authenticated encryption candidate at the CAESAR competition. In this study, by adequately studying the tweakey schedule, we seek a six-round related-tweakey impossible distinguisher of Deoxys-BC-256, which is transformed from a 3.5-round single-key impossible distinguisher of AES, by application of the mixed integer linear programming (MILP) method. We present a detailed description of this interesting transformation method and the MILP-modeling process. Based on this distinguisher, we mount a key-recovery attack on 10 (out of 14) rounds of Deoxys-BC-256. Compared to previous results that are valid only when the key size $>204$ and the tweak size $<52$, our method can attack 10-round Deoxys-BC-256 as long as the key size $\geq174$ and the tweak size $\leq82$. For the popular setting in which the key size is 192 bits, we can attack one round more than previous works. This version gives the distinguisher and the attack differential which follows the description of the $h$ permutation in the Deoxys document, instead of that in the Deoxys reference implementation in the SUPERCOP package, which is wrong confirmed by the designers. Note that this work only gives a more accurate security evaluation and does not threaten the security of full-round Deoxys-BC-256.

Deep learning can achieve higher accuracy than traditional machine learning algorithms in a variety of machine learning tasks. Recently, privacy-preserving deep learning has drawn tremendous attention from information security community, in which neither training data nor the training model is expected to be exposed. Federated learning is a popular learning mechanism, where multiple parties upload local gradients to a server and the server updates model parameters with the collected gradients. However, there are many security problems neglected in federated learning, for example, the participants may behave incorrectly in gradient collecting or parameter updating, and the server may be malicious as well. In this paper, we present a distributed, secure, and fair deep learning framework named DeepChain to solve these problems. DeepChain provides a value-driven incentive mechanism based on Blockchain to force the participants to behave correctly. Meanwhile, DeepChain guarantees data privacy for each participant and provides auditability for the whole training process. We implement a DeepChain prototype and conduct experiments on a real dataset for different settings, and the results show that our DeepChain is promising.

A proof-of-replication (PoRep) is an interactive proof system in which a prover defends a publicly verifiable claim that it is dedicating unique resources to storing one or more retrievable replicas of a data file. In this sense a PoRep is both a proof of space (PoS) and a proof of retrievability (PoR). This paper is a foundational study of PoReps, exploring both their capabilities and their limitations. While PoReps may unconditionally demonstrate possession of data, they fundamentally cannot guarantee that the data is stored redundantly. Furthermore, as PoReps are proofs of space, they must rely either on rational time/space tradeoffs or timing bounds on the online prover's runtime. We introduce a rational security notion for PoReps called epsilon-rational replication based on the notion of an epsilon-Nash equilibrium, which captures the property that a server does not gain any significant advantage by storing its data in any other (non-redundant) format. We apply our definitions to formally analyze two recently proposed PoRep constructions based on verifiable delay functions and depth robust graphs. Lastly, we reflect on a notable application of PoReps---its unique suitability as a Nakamoto consensus mechanism that replaces proof-of-work with PoReps on real data, simultaneously incentivizing and subsidizing the cost of file storage.

Following the development of quantum computing, the demand for post-quantum alternatives to current cryptosystems has firmly increased recently. The main disadvantage of those schemes is the amount of resources needed to implement them in comparison to their classical counterpart. In conjunction with the growth of the Internet of Things, it is crucial to know if post-quantum algorithms can evolve in constraint environments without incurring an unacceptable performance penalty. In this paper, we propose an instantiation of a module-lattice-based KEM working over a ring of dimension 128 using a limited amount of memory at runtime. It can be seen as a lightweight version of Kyber or a module version of Frodo. We propose parameters targeting popular 8-bit AVR microcontrollers and security level 1 of NIST. Our implementation fits in around 2 KB of RAM while still providing reasonable efficiency and 128 bits of security, but at the cost of a reduced correctness.

The static power consumption of modern CMOS devices has become a substantial concern in the context of the side-channel security of cryptographic hardware. Its continuous growth in nanometer-scaled technologies is not only inconvenient for effective low power designs, but does also create a new target for power analysis adversaries. Additionally, it has to be noted that several of the numerous sources of static power dissipation in CMOS circuits exhibit an exponential dependency on environmental factors which a classical power analysis adversary is in control of. These factors include the operating conditions temperature and supply voltage. Furthermore, in case of clock control, the measurement interval can be adjusted arbitrarily. Our experiments on a 150nm CMOS ASIC reveal that with respect to the signal-to-noise ratio in static power side-channel analyses, stretching the measurement interval decreases the noise exponentially and even more importantly that raising the working temperature increases the signal exponentially. Control over the supply voltage has a far smaller, but still noticeable, positive impact as well. In summary, a static power analysis adversary can physically force a device to leak more information by controlling its operating environment and furthermore measure these leakages with arbitrary precision by modifying the interval length.

In a recent paper the authors and their collaborators proposed a new hard problem, called the finite field isomorphism problem, and they used it to construct a fully homomorphic encryption scheme. In this paper, we investigate how one might build a digital signature scheme from this new problem. Intuitively, the hidden field isomorphism allows us to convert short vectors in the underlying lattice of one field into generic looking vectors in an isomorphic field.

The majority of currently deployed cryptographic public-key schemes are at risk of becoming insecure once large scale quantum computers become practical. Therefore, substitutes resistant to quantum attacks楊nown as post-quantum cryptography預re required. In particular, hash-based signature schemes appear to be the most conservative choice for post-quantum digital signatures. In this work, we mount the first practical fault attack against hash-based cryptography. The attack was originally proposed by Castelnovi, Martinelli, and Prest [9] and allows the creation of a universal signature forgery that applies to all current standardisation candidates (XMSS, LMS, SPHINCS+, and Gravity-SPHINCS). We perform the attack on an Arduino Due board featuring an ARM Cortex-M3 microprocessor running the original stateless scheme SPHINCS with a focus on practicality. We describe how the attack is mountable with a simple voltage glitch injection on the targeted platform, which allowed us to collect enough faulty signatures to create a universal forgery within seconds. As the attack also applies to stateful schemes, we show how caching one-time signatures can entirely prevent the attack for stateful schemes, such as XMSS and LMS. However, we discuss how protecting stateless schemes, like SPHINCS, SPHINCS+, and Gravity-SPHINCS, is more challenging, as this countermeasure does not apply as efficiently as in stateful schemes.

Quantum computing threatens conventional public-key cryptography. In response, standards bodies such as NIST increasingly focus on post-quantum cryptography. In particular, hash-based signature schemes are notable candidates for deployment. No rigorous side-channel analysis of hash-based signature schemes has been conducted so far. This work bridges this gap. We analyse the stateful hash-based signature schemes XMSS and XMSS^MT, which are currently undergoing standardisation at IETF, as well as SPHINCS — the only practical stateless hash-based scheme. While timing and simple power analysis attacks are unpromising, we show that the differential power analysis resistance of XMSS can be reduced to the differential power analysis resistance of the underlying pseudorandom number generator. This first systematic analysis helps to further increase confidence in XMSS, supporting current standardisation efforts. Furthermore, we show that at least a 32-bit chunk of the SPHINCS secret key can be recovered using a differential power analysis attack due to its stateless construction. We present novel differential power analyses on a SHA-2-based pseudorandom number generator for XMSS and a BLAKE-256-based pseudorandom function for SPHINCS-256 in the Hamming weight model. The first attack is not threatening current versions of XMSS, unless a customised pseudorandom number generator is used. The second one compromises the security of a hardware implementation of SPHINCS-256. Our analysis is supported by a power simulator implementation of SHA-2 for XMSS and a hardware implementation of BLAKE for SPHINCS. We also provide recommendations for XMSS implementers.

In this work, we consider the ring- and module- variants of the LWE problem and investigate cold boot attacks on cryptographic schemes based on these problems, wherein an attacker is faced with the problem of recovering a scheme's secret key from a noisy version of that key. The leakage resilience of cryptography based on the learning with errors (LWE) problem has been studied before, but there are only limited results considering the parameters observed in cold boot attack scenarios. There are two main encodings for storing ring- and module-LWE keys, and, as we show, the performance of cold boot attacks can be highly sensitive to the exact encoding used. The first encoding stores polynomial coefficients directly in memory. The second encoding performs a number theoretic transform (NTT) before storing the key, a commonly used method leading to more efficient implementations. We first give estimates for a cold boot attack complexity on the first encoding method based on standard algorithms; this analysis confirms that this encoding method is vulnerable to cold boot attacks only at very low bit-flip rates. We then show that, for the second encoding method, the structure introduced by using an NTT is exploitable in the cold boot setting: we develop a bespoke attack strategy that is much cheaper than our estimates for the first encoding when considering module-LWE keys. For example, at a \(1\%\) bit-flip rate (which corresponds roughly to what can be achieved in practice for cold boot attacks when applying cooling), a cold boot attack on Kyber KEM parameters has a cost of \(2^{43}\) operations when the second, NTT-based encoding is used for key storage, compared to \(2^{70}\) operations with the first encoding. On the other hand, in the case of the ring-LWE-based KEM, New Hope, the cold boot attack complexities are similar for both encoding methods.

Belief propagation, or the sum-product algorithm, is a powerful and well known method for inference on probabilistic graphical models, which has been proposed for the specific use in side channel analysis by Veyrat-Charvillon et al. We define a novel metric to capture the importance of variable nodes in factor graphs, we propose two improvements to the sum-product algorithm for the specific use case in side channel analysis, and we explicitly define and examine different ways of combining information from multiple side channel traces. With these new considerations we systematically investigate a number of graphical models that "naturally" follow from an implementation of AES. Our results are unexpected: neither a larger graph (i.e. more side channel information) nor more connectedness necessarily lead to significantly better attacks. In fact our results demonstrate that in practice the (on balance) best choice is to utilise an acyclic graph in an independent graph combination setting, which gives us provable convergence to the correct key distribution. We provide evidence using both extensive simulations and a final confirmatory analysis on real trace data.

We formalize the notion of a constrained linear trapdoor as an abstract strategy for the generation of signature schemes, concrete instantiations of which can be found in MQ-based, code-based, and lattice-based cryptography. Moreover, we revisit and expand on a transformation by Szepieniec et al. to shrink the public key at the cost of a larger signature while reducing their combined size. This transformation can be used in a way that is provably secure in the random oracle model, and in a more aggressive variant whose security remained unproven. In this paper we show that this transformation applies to any constrained linear trapdoor signature scheme, and prove the security of the first mode in the quantum random oracle model. Moreover, we identify a property of constrained linear trapdoors that is sufficient (and necessary) for the more aggressive variant to be secure in the quantum random oracle model. We apply the transformation to an MQ-based scheme, a code-based scheme and a lattice-based scheme targeting 128-bits of post quantum security, and we show that in some cases the combined size of a signature and a public key can be reduced by more than a factor 300.

This paper introduces a novel implementation of the elliptic curve factoring method specifically designed for medium-size integers such as those arising by billions in the cofactorization step of the number field sieve. In this context, our algorithm requires fewer modular multiplications than any other publicly available implementation. The main ingredients are: the use of batches of primes, fast point tripling, optimal double-base decompositions and Lucas chains, and a good mix of Edwards and Montgomery representations.

In this paper, we analyze the security of an end-to-end encryption scheme (E2EE) of LINE, a.k.a Letter Sealing. LINE is one of the most widely-deployed instant messaging applications, especially in East Asia. By a close inspection of their protocols, we give several attacks against the message integrity of Letter Sealing. Specifically, we propose forgery and impersonation attacks on the one-to-one message encryption and the group message encryption. All of our attacks are feasible with the help of an end-to-end adversary, who has access to the inside of the LINE server (e.g. service provider LINE themselves). We stress that the main purpose of E2EE is to provide a protection against the end-to-end adversary. In addition, we found some attacks that even do not need the help of E2E adversary, which shows a critical security flaw of the protocol. Our results reveal that the E2EE scheme of LINE do not sufficiently guarantee the integrity of messages compared to the state-of-the-art E2EE schemes such as Signal, which is used by WhatApp and Facebook Messenger. We also provide some countermeasures against our attacks. We have shared our findings with LINE corporation in advance. The LINE corporation has confirmed our attacks are valid as long as the E2E adversary is involved, and officially recognizes our results as a vulnerability of encryption break.

In this paper, we investigate the hardware circuit complexity of the class of Boolean functions recently introduced by Tang and Maitra (IEEE-TIT 64(1): 393 402, 2018). While this class of functions has very good cryptographic properties, the exact hardware requirement is an immediate concern as noted in the paper itself. In this direction, we consider different circuit architectures based on finite field arithmetic and Boolean optimization. An estimation of the circuit complexity is provided for such functions given any input size n. We study different candidate architectures for implementing these functions, all based on the finite field arithmetic. We also show different implementations for both ASIC and FPGA, providing further analysis on the practical aspects of the functions in question and the relation between these implementations and the theoretical bound. The practical results show that the Tang-Maitra functions are quite competitive in terms of area, while still maintaining an acceptable level of throughput performance for both ASIC and FPGA implementations.

In this paper we study structured linear block codes, starting from well known examples and generalizing them to a wide class of codes that we call reproducible codes. These codes have the property that can be entirely generated from a small number of signature vectors, and consequently admit matrices that can be described in a very compact way. We then show some cryptographic applications of this class of codes and explain why the general framework we introduce may pave the way for future developments of code-based cryptography based on structured codes.

We describe a framework for constructing an efficient non-interactive key exchange (NIKE) protocol for n parties for any n >= 2. Our approach is based on the problem of computing isogenies between isogenous elliptic curves, which is believed to be difficult. We do not obtain a working protocol because of a missing step that is currently an open problem. What we need to complete our protocol is an efficient algorithm that takes as input an abelian variety presented as a product of isogenous elliptic curves, and outputs an isomorphism invariant of the abelian variety. Our framework builds a cryptographic invariant map, which is a new primitive closely related to a cryptographic multilinear map, but whose range does not necessarily have a group structure. Nevertheless, we show that a cryptographic invariant map can be used to build several cryptographic primitives, including NIKE, that were previously constructed from multilinear maps and indistinguishability obfuscation.

Post 9/11, journalists, scholars and activists have pointed out that secret laws --- a body of law whose details and sometime mere existence is classified as top secret --- were on the rise in all three branches of the US government due to growing national security concerns. Amid heated current debates on governmental wishes for exceptional access to encrypted digital data, one of the key issues is: which mechanisms can be put in place to ensure that government agencies follow agreed-upon rules in a manner which does not compromise national security objectives? This promises to be especially challenging when the rules, according to which access to encrypted data is granted, may themselves be secret. In this work we show how the use of cryptographic protocols, and in particular, the use of zero-knowledge proofs can ensure accountability and transparency of the government in this extraordinary, seemingly deadlocked, setting. We propose an efficient record-keeping infrastructure with versatile publicly verifiable audits that preserve perfect (information-theoretic) secrecy of record contents as well as of the rules by which the records are attested to abide. Our protocol is based on existing blockchain and cryptographic tools including commitments and zero-knowledge SNARKs, and satisfies the properties of indelibility (i.e., no back-dating), perfect data secrecy, public auditability of secret data with secret laws, accountable deletion, and succinctness. We also propose a variant scheme where entities can be required to pay fees based on record contents (e.g., for violating regulations) while still preserving data secrecy. Our scheme can be directly instantiated on the Ethereum blockchain (and a simplified version with weaker guarantees can be instantiated with Bitcoin).

Secure matrix computation is one of the most fundamental and useful operations for statistical analysis and machine learning with protecting the confidentiality of input data. Secure computation can be achieved by homomorphic encryption, supporting meaningful operations over encrypted data. HElib is a software library that implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic scheme, in which secure matrix-vector multiplication is proposed for operating matrices. Recently, Duong et al. (Tatra Mt. Publ. 2016) proposed a new method for secure single matrix multiplication over a ring-LWE-based scheme. In this paper, we generalize Duong et al.'s method for secure multiple matrix multiplications over the BGV scheme. We also implement our method using HElib and show that our method is much faster than the matrix-vector multiplication in HElib for secure matrix multiplications.

Machine learning on encrypted data is a cryptographic method for analyzing private and/or sensitive data while keeping privacy. In the training phase, it takes as input an encrypted training data and outputs an encrypted model without using the decryption key. In the prediction phase, it uses the encrypted model to predict results on new encrypted data. In each phase, no decryption key is needed, and thus the privacy of data is guaranteed while the underlying encryption is secure. It has many applications in various areas such as finance, education, genomics, and medical field that have sensitive private data. While several studies have been reported on the prediction phase, few studies have been conducted on the training phase due to the inefficiency of homomorphic encryption (HE), leaving the machine learning training on encrypted data only as a long-term goal. In this paper, we propose an efficient algorithm for logistic regression on encrypted data, and evaluate our algorithm on real financial data consisting of 422,108 samples over 200 features. Our experiment shows that an encrypted model with a sufficient Kolmogorov Smirnow statistic value can be obtained in $\sim$17 hours in a single machine. We also evaluate our algorithm on the public MNIST dataset, and it takes $\sim$2 hours to learn an encrypted model with 96.4% accuracy. Considering the inefficiency of HEs, our result is encouraging and demonstrates the practical feasibility of the logistic regression training on large encrypted data, for the first time to the best of our knowledge.

In response to upcoming performance and security challenges of anonymity networks like Tor, it will be of crucial importance to be able to develop and deploy performance improvements and state-of-the-art countermeasures. In this paper, we therefore explore different deployment strategies and review their applicability to the Tor network. In particular, we consider flag day, dual stack, translation, and tunneling strategies and discuss their impact on the network, as well as common risks associated with each of them. In a simulation based evaluation, which stems on historical data of Tor, we show that they can practically be applied to realize significant protocol changes in Tor. However, our results also indicate that during the transitional phase a certain degradation of anonymity is unavoidable with current viable deployment strategies.

In this paper, we consider a scenario where a bitcoin liquidity provider sells bitcoins to clients. When a client pays for a bitcoin online, the provider is able to link the client's payment information to the bitcoin sold to that client. To address the clients' privacy concern, it is desirable for the provider to perform the bitcoin transaction with blind signatures. However, existing blind signature schemes are incompatible with the Elliptic Curve Digital Signature Algorithm (ECDSA) which is used by most of the existing bitcoin protocol, thus cannot be applied directly in Bitcoin. In this paper, we propose a new blind signature scheme that allows generating a blind signature compatible with the standard ECDSA. Afterwards, we make use of the new scheme to achieve bitcoin transaction anonymity. The new scheme is built on a variant of the Paillier cryptosystem and its homomorphic properties. As long as the modified Paillier cryptosystem is semantically secure, the new blind signature scheme has blindness and unforgeability.

In 2003, Alfred Menezes, Edlyn Teske and Annegret Weng presented a conjecture on properties of the solutions of a type of quadratic equation over the binary extension fields, which had been convinced by extensive experiments but the proof was unknown until now. We prove that this conjecture is correct. Furthermore, using this proved conjecture, we have completely determined the null space of a class of linear polynomials.

Inspired by the blockchain architecture and existing Merkle tree based signature schemes, we propose BPQS, an extensible post-quantum (PQ) resistant digital signature scheme best suited to blockchain and distributed ledger technologies (DLTs). One of the unique characteristics of the protocol is that it can take advantage of application-specific chain/graph structures in order to decrease key generation, signing and verification costs as well as signature size. Compared to recent improvements in the field, BPQS outperforms existing hash-based algorithms when a key is reused for reasonable numbers of signatures, while it supports a fallback mechanism to allow for a practically unlimited number of signatures if required. To our knowledge, this is the first signature scheme that can utilise an existing blockchain or graph structure to reduce the signature cost to one OTS, even when we plan to sign many times. This makes existing many-time stateful signature schemes obsolete for blockchain applications. We provide an open source implementation of the scheme and benchmark it.

Cryptographic techniques are employed to ensure the security of voting systems in order to increase its wide adoption. However, in such electronic voting systems, the public bulletin board that is hosted by the third party for publishing and auditing the voting results should be trusted by all participants. Recently a number of blockchain-based solutions have been proposed to address this issue. However, these systems are impractical to use due to the limitations on the voter and candidate numbers supported, and their security framework, which highly depends on the underlying blockchain protocol and suffers from potential attacks (e.g., force-abstention attacks). To deal with two aforementioned issues, we propose a practical platform-independent secure and verifiable voting system that can be deployed on any blockchain that supports an execution of a smart contract. Verifiability is inherently provided by the underlying blockchain platform, whereas cryptographic techniques like Paillier encryption, proof-of-knowledge, and linkable ring signature are employed to provide a framework for system security and user-privacy that are independent from the security and privacy features of the blockchain platform. We analyse the correctness and coercion-resistance of our proposed voting system. We employ Hyperledger Fabric to deploy our voting system and analyse the performance of our deployed scheme numerically.

In this paper a ‘FPGA cluster’ based framework for high performance Cryptanalysis has been proposed. The framework abstracts underlying networked FPGA cluster into a unified acceleration resource. It does so by implementing requested amount of computation kernels (cryptographic modules) and managing efficient distribution of the network band-width between the inter-FPGA and intra-FPGA computation kernels. Further agile methodology for developing such networked computation kernels with use of a high level language (Python) based HDL library and seamless integration with a user space crypt analysis application have been discussed. 40-bit partial key attack over AES256 has been demonstrated as a capability demonstration. Performance higher than clustered CPUs and GPUs at lower costs and power is reported.

Currently, the blockchain technology is experiencing an exponential growth in the academia and industry. Blockchain may provide the fault-tolerance, tamper-resistance, credibility and privacy to users. In this paper, we propose a blockchain-based residual loanable-limit query system, called Loamit. Firstly, to the best of our knowledge, it is the first work to prevent that a client, who lacks the ability to repay, borrows an un-repayable amount of money from independent banks without releasing the personal privacy of client. Specifically, if a client wants to borrow a certain amount of money from a bank, then the bank can get the client's residual loanable-limit in the alliance of banks without knowing details of the client's previous loans and repayments. Secondly, most of data in Loamit is verifiable. Therefore, malicious banks can be checked out. Thirdly, Loamit is fault-tolerant since it may work smoothly as long as a certain number of banks are active and honest. Finally, we deploy the Loamit system on the Ethererum private blockchain and give the corresponding performance evaluation.

In this paper we provide a formal treatment of proof of replicated storage, a novel cryptographic primitive recently proposed in the context of a novel cryptocurrency, namely Filecoin. In a nutshell, proofs of replicated storage is a solution to the following problem: A user stores a file $m$ on $n$ different servers to ensure that the file will be available even if some of the servers fail. Using proof of retrievability, the user could check that every server is indeed storing the file. However, what if the servers collude and, in order to save on resources, decide to only store one copy of the file? A proof of replicated storage guarantees that, unless the server is indeed reserving the space necessary to store $n$ copies of the file, the user will not accept the proof. While some candidate proofs of replicated storage have already been proposed, their soundness relies on timing assumptions i.e., the user must reject the proof if the prover does not reply within a certain time-bound. In this paper we provide the first construction of a proof of replication which does not rely on any timing assumptions.

Optimizing performance of Fully Homomorphic Encryption (FHE) is nowadays an active trend of research in cryptography. One way of improvement is to use a hybrid construction with a classical symmetric encryption scheme to transfer encrypted data to the Cloud. This allows to reduce the bandwidth since the expansion factor of symmetric schemes (the ratio between the ciphertext and the plaintext length) is close to one, whereas for FHE schemes it is in the order of 1,000 to 1,000,000. However, such a construction requires the decryption circuit of the symmetric scheme to be easy to evaluate homomorphically. Several works have studied the cost of homomorphically evaluating classical block ciphers, and some recent works have suggested new homomorphic oriented constructions of block ciphers or stream ciphers. Since the multiplication gate of FHE schemes significantly increases the noise of the ciphertext, we cannot afford too many multiplication stages in the decryption circuit. Consequently, FHE-friendly symmetric encryption schemes have a decryption circuit with small multiplication depth. We aim at minimizing the cost of the homomorphic evaluation of the decryption of symmetric encryption schemes. To do so, we focus on schemes based on learning problems: Learning With Errors (LWE), Learning Parity with Noise (LPN) and Learning With Rounding (LWR). We show that they have lower multiplicative depth than usual block ciphers, and hence allow more FHE operations before a heavy bootstrapping becomes necessary. Moreover, some of them come with a security proof. Finally, we implement our schemes in HElib. Experimental evidence shows that they achieve lower amortized and total running time than previous performance from the literature: our schemes are from 10 to 10,000 more efficient for the time per bit and the total running time is also reduced by a factor between 20 to 10,000. Of independent interest, the security of our LWR-based scheme is related to LWE and we provide an efficient security proof that allows to take smaller parameters.

RIPEMD-160 is an ISO/IEC standard and has been applied to generate the Bitcoin address with SHA-256. Due to the complex dual-stream structure, the first collision attack on reduced RIPEMD-160 presented by Liu, Mendel and Wang at Asiacrypt 2017 only reaches 30 steps, having a time complexity of $2^{70}$. Apart from that, several semi-free-start collision attacks have been published for reduced RIPEMD-160 with the start-from-the-middle method. Inspired from such start-from-the middle structures, we propose two novel efficient collision attack frameworks for reduced RIPEMD-160 by making full use of the weakness of its message expansion. Those two frameworks are called dense-left-and-sparse-right (DLSR) framework and sparse-left-and-dense-right (SLDR) framework. As it turns out, the DLSR framework is more efficient than SLDR framework since one more step can be fully controlled, though with extra $2^{32}$ memory complexity. To construct the best differential characteristics for the DLSR framework, we carefully build the linearized part of the characteristics and then solve the corresponding nonlinear part using a guess-and-determine approach. Based on the newly discovered differential characteristics, we provide colliding messages pairs for the first practical collision attacks on 30 and 31 (out of 80) steps of RIPEMD-160 with time complexity $2^{35.9}$ and $2^{41.5}$ respectively. In addition, benefiting from the partial calculation, we can attack 33 and 34 (out of 80) steps of RIPEMD-160 with time complexity $2^{67.1}$ and $2^{74.3}$ respectively. When applying the SLDR framework to the differential characteristic used in the Asiacrypt 2017 paper, we significantly improve the time complexity by a factor of $2^{13}$. However, it still cannot compete with the results obtained from the DLSR framework. To the best of our knowledge, these are the best collision attacks on reduced RIPEMD-160 with respect to the number of steps, including the first colliding message pairs for 30 and 31 steps of RIPEMD-160.

SM2 is a public key cryptography suite originating from Chinese standards, including digital signatures and public key encryption. Ahead of schedule, code for this functionality was recently mainlined in OpenSSL, marked for the upcoming 1.1.1 release. We perform a security review of this implementation, uncovering various deficiencies ranging from traditional software quality issues to side-channel risks. To assess the latter, we carry out a side-channel security evaluation and discover that the implementation hits every pitfall seen for OpenSSL's ECDSA code in the past decade. We carry out remote timings, cache timings, and EM analysis, with accompanying empirical data to demonstrate secret information leakage during execution of both digital signature generation and public key decryption. Finally, we propose, implement, and empirically evaluate countermeasures.

Cryptographic primitives from coding theory are some of the most promising candidates for NIST's Post-Quantum Cryptography Standardization process. In this paper, we introduce a variety of techniques to improve operations on dyadic matrices, a particular type of symmetric matrices that appear in the automorphism group of certain linear codes. Besides the independent interest, these techniques find an immediate application in practice. In fact, one of the candidates for the Key Exchange functionality, called DAGS, makes use of quasi-dyadic matrices to provide compact keys for the scheme.

In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for polynomial-time deterministic computation, i.e., a PCP system for P such that (1) the honest PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who is allowed to answer each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously. As an application of our PCP system, we obtain a 2-message delegating computation scheme by using a known transformation. Compared with the existing 2-message delegating computation schemes that are based on standard cryptographic assumptions, our scheme requires preprocessing but has a simpler structure and makes use of different (possibly cheaper) standard cryptographic primitives, namely additive/multiplicative homomorphic encryption schemes.

We define semi-commutative invertible masking structures which aim to capture the methodology of exponentiation-only protocol design (such as discrete logarithm and isogeny-based cryptography). We discuss two instantiations: the first is based on commutative group actions and captures both the action of exponentiation in the discrete logarithm setting and the action of the class group of commutative endomorphism rings of elliptic curves, in the style of the CSIDH key-exchange protocol; the second is based on the semi-commutative action of isogenies of supersingular elliptic curves, in the style of the SIDH key-exchange protocol. We then construct two oblivious transfer protocols using this new structure and prove that these UC-securely realise the oblivious transfer functionality in the random-oracle-hybrid model against passive adversaries with static corruptions. Moreover, by starting from one of these two protocols and using the compiler introduced by Döttling et al. (Eurocrypt 2020), we achieve the first fully UC-secure two-round OT protocol based on supersingular isogenies.

A new proof is given for the correctness of the powers of two descent method for computing discrete logarithms. The result is slightly stronger than the original work, but more importantly we provide a unified geometric argument, eliminating the need to analyse all possible subgroups of $\mathrm{PGL}_2(\mathbb{F}_q)$. Our approach sheds new light on the role of $\mathrm{PGL}_2$, in the hope to eventually lead to a complete proof that discrete logarithms can be computed in quasi-polynomial time in finite fields of fixed characteristic.

We introduce Pseudo Flawed-smudging Generators (PFGs). A PFG is an expanding function whose outputs $\mathbf Y$ satisfy a weak form of pseudo-randomness. Roughly speaking, for some polynomial bound $B$, and every distribution $\chi$ over $B$-bounded noise vectors, it guarantees that the distribution of $(\mathbf e,\ \mathbf Y + \mathbf e)$ is indistinguishable from that of $(\mathbf e', \mathbf Y + \mathbf e)$, where $\mathbf e \gets \chi$ is a random sample from $\chi$, and $\mathbf e'$ is another independent sample from $\chi$ conditioned on agreeing with $\mathbf e$ at a few, $o(\lambda)$, coordinates. In other words, $\mathbf Y$ "hides" $\mathbf e$ at all but a few coordinates. We show that assuming LWE and the existence of constant-locality Pseudo-Random Generators (PRGs), there is a construction of IO from 1) a PFG that has polynomial stretch and polynomially bounded outputs, and 2) a Functional Encryption (FE) scheme able to compute this PFG. Such FE can be built from degree $d$ multilinear map if the PFG is computable by a degree $d$ polynomial. Toward basing IO on bilinear maps, inspired by [Ananth et. al. Eprint 2018], we further consider PFGs with partial pubic input --- they have the form $g(\mathbf{x}, \mathbf{y})$ and satisfy the aforementioned pseudo flawed-smudging property even when $\mathbf{x}$ is public. When using such PFGs, it suffices to replace FE with a weaker notion of partially hiding FE (PHFE) whose decryption reveals the public input $\mathbf{x}$ in addition to the output of the computation. We construct PHFE for polynomials $g$ that are quadratic in the private input $\mathbf{y}$, but have up to polynomial degree in the public input $\mathbf{x}$, subject to certain size constraints, from the SXDH assumption over bilinear map groups. Regarding candidates of PFGs with partial public input, we note that the family of cubic polynomials proposed by Ananth et. al. can serve as candidate PFGs, and can be evaluated by our PHFE from bilinear maps. Toward having more candidates, we present a transformation for converting the private input $\mathbf{x}$ of a constant-degree PFG $g(\mathbf{x}, \mathbf{y})$ into a public input, by hiding $\mathbf{x}$ as noises in LWE samples, provided that $\mathbf{x}$ is sampled from a LWE noise distribution and $g$ satisfies a stronger security property.

We present a key-policy attribute-based encryption scheme that is adaptively secure under a static assumption and is not directly affected by an attribute "one-use restriction." Our construction improves upon the only other such scheme (Takashima '17) by mitigating its downside of a ciphertext size that is dependent on the maximum size of any supported attribute set.

Security protocols using public-key cryptography often requires large number of costly modular exponentiations (MEs). With the proliferation of resource-constrained (mobile) devices and advancements in cloud computing, delegation of such expensive computations to powerful server providers has gained lots of attention. In this paper, we address the problem of verifiably secure delegation of MEs using two servers, where at most one of which is assumed to be malicious (the OMTUP-model). We first show verifiability issues of two recent schemes: We show that a scheme from IndoCrypt 2016 does not offer full verifiability, and that a scheme for $n$ simultaneous MEs from AsiaCCS 2016 is verifiable only with a probability $0.5909$ instead of the author's claim with a probability $0.9955$ for $n=10$. Then, we propose the first non-interactive fully verifiable secure delegation scheme by hiding the modulus via Chinese Remainder Theorem (CRT). Our scheme improves also the computational efficiency of the previous schemes considerably. Hence, we provide a lightweight delegation enabling weak clients to securely and verifiably delegate MEs without any expensive local computation (neither online nor offline). The proposed scheme is highly useful for devices having (a) only ultra-lightweight memory, and (b) limited computational power (e.g. sensor nodes, RFID tags).

Building trustless cross-blockchain trading protocols is challenging. Centralized exchanges thus remain the preferred route to execute transfers across blockchains. However, these services require trust and therefore undermine the very nature of the blockchains on which they operate. To overcome this, several decentralized exchanges have recently emerged which offer support for atomic cross-chain swaps (ACCS). ACCS enable the trustless exchange of cryptocurrencies across blockchains, and are the only known mechanism to do so. However, ACCS suffer significant limitations; they are slow, inefficient and costly, meaning that they are rarely used in practice. We present XCLAIM: the first generic framework for achieving trustless and efficient cross-chain exchanges using cryptocurrency-backed assets (CbAs). XCLAIM offers protocols for issuing, transferring, swapping and redeeming CbAs securely in a non-interactive manner on existing blockchains. We instantiate XCLAIM between Bitcoin and Ethereum and evaluate our implementation; it costs less than USD 0.50 to issue an arbitrary amount of Bitcoin-backed tokens on Ethereum. We show XCLAIM is not only faster, but also significantly cheaper than atomic cross-chain swaps. Finally, XCLAIM is compatible with the majority of existing blockchains without modification, and enables several novel cryptocurrency applications, such as cross-chain payment channels and efficient multi-party swaps.

Current permissionless blockchains suffer from scalability limitations. To scale without changing the underlying blockchain, one avenue is to lock funds into blockchain smart-contracts (collateral) and enact transactions outside, or off- the blockchain, via accountable peer-to-peer messages. Disputes among peers are resolved with appropriate collateral redistribution on the blockchain. In this work we lay the foundations for commit-chains, a novel off-chain scaling solution for existing blockchains where an untrusted and non-custodial operator commits the state of its user account balances via constant-sized, periodic checkpoints. Users dispute operator misbehavior via a smart contract. The commit-chain paradigm enables for the first time that off-chain users can receive payments while being offline. Moreover, locked funds can be managed efficiently at constant communication costs, alleviating collateral fragmentation. We instantiate two account-based commit-chain constructions: NOCUST, based on a cost-effective challenge-response dispute mechanism; and NOCUST-ZKP, which provides provably correct operation via zkSNARKs. These constructions offer a trade-off between correctness, verification, and efficiency while both are practical and ensure key properties such as balance safety; that is, no honest user loses coins. We implemented both constructions on a smart contract enabled blockchain. Our evaluation demonstrates that NOCUST's operational costs in terms of computation and communication scale logarithmically in the number of users and transactions, and allow very efficient lightweight clients (a user involved in e.g. 100 daily transactions only needs to store a constant 46 kb of data, allowing secure payments even on mobile devices). NOCUST is operational in production since March 2019.

Group signatures present a trade-off between the traditional goals of digital signatures and the signer's desire for privacy, allowing for the creation of unforgeable signatures in the name of a group which reveal nothing about the actual signer's identity beyond their group membership. Considering the desired properties formally opens up a possibility space of different security goals under various assumptions on trust placed in the designated entities of any scheme. Many models differ in their consideration of the variability of group membership as well, yet a formal treatment of the privacy of group membership status is lacking in all models, thus far. We address this issue, starting from the vantage point of the comprehensive model due to Bootle et al. (ACNS'16), who prove that any scheme secure in their model is also secure in the previous models. Their model allows for fully dynamic management of group membership by segmenting the scheme's lifetime into epochs during which group membership is static but between which users may join or leave the group. We extend the model of Bootle et al. by introducing formal notions of membership privacy. We then propose an efficient generic construction for a fully dynamic group signature scheme with membership privacy that is based on signatures with flexible public key (SFPK) and signatures on equivalence classes (SPSEQ). We instantiate the construction using a SFPK scheme based on the bilinear decisional Diffie-Hellman assumption and SPSEQ scheme by Fuchsbauer and Gay (PKC'18). The resulting scheme provides shorter signatures than existing schemes from standard assumption, while at the same time achieving stronger security guarantees.

Lower bounds for structure-preserving signature (SPS) schemes based on non-interactive assumptions have only been established in the case of unilateral messages, i.e. schemes signing tuples of group elements all from the same source group. In this paper, we consider the case of bilateral messages, consisting of elements from both source groups. We show that, for Type-III bilinear groups, SPS’s must consist of at least 6 group elements: many more than the 4 elements needed in the unilateral case, and optimal, as it matches a known upper bound from the literature. We also obtain the first non-trivial lower bounds for SPS’s in Type-II groups: a minimum of 4 group elements, whereas constructions with 3 group elements are known from interactive assumptions.

In cloud computing, delegated computing raises the security issue of guaranteeing data authenticity during a remote computation. Existing solutions do not simultaneously provide fast correctness verification, strong security properties, and information-theoretic confidentiality. We introduce a novel approach, in the form of function-dependent commitments, that combines these strengths. We also provide an instantiation of function-dependent commitments for linear functions that is unconditionally, i.e. information-theoretically, hiding and relies on standard hardness assumptions. This powerful construction can for instance be used to build verifiable computing schemes providing information-theoretic confidentiality. As an example, we introduce a verifiable multi-party computation scheme for shared data providing public verifiability and unconditional privacy towards the servers and parties verifying the correctness of the result. Our scheme can be used to perform verifiable computations on secret shares while requiring only a single party to compute the audit data for verification. Furthermore, our verification procedure is asymptotically even more efficient than performing operations locally on the shared data. Thus, our solution improves the state of the art for authenticated computing, verifiable computing and multi-party computation.

Dissidents, journalists, and others require technical means to protect their privacy in the face of compelled access to their digital devices (smartphones, laptops, tablets, etc.). For example, authorities increasingly force disclosure of all secrets, including passwords, to search devices upon national border crossings. We therefore present the design, implementation, and evaluation of a new system to help victims of compelled searches. Our system, called BurnBox, provides self-revocable encryption: the user can temporarily disable their access to specific files stored remotely, without revealing which files were revoked during compelled searches, even if the adversary also compromises the cloud storage service. They can later restore access. We formalize the threat model and provide a construction that uses an erasable index, secure erasure of keys, and standard cryptographic tools in order to provide security supported by our formal analysis. We report on a prototype implementation, which showcases the practicality of BurnBox.

Since Gentry discovered in 2009 the first fully homomorphic encryption scheme, the last few years have witnessed dramatic progress on designing more efficient homomorphic encryption schemes, and some of them have been implemented for applications. The main bottlenecks are in bootstrapping and large cipher expansion (the ratio of the size of ciphertexts to that of messages). Ducas and Micciancio (2015) show that homomorphic computation of one bit operation on LWE ciphers can be done in less than a second, which is then reduced by Chillotti et al. (2016, 2017) to 13ms. This paper presents a compact fully homomorphic encryption scheme that has the following features: (a) its cipher expansion is 6 with private-key encryption and 20 with public-key encryption; (b) all ciphertexts after any number (unbounded) of homomorphic bit operations have the same size and are always valid with the same error size; (c) its security is based on the LWE and RLWE problems (with binary secret keys) and the cost of breaking the scheme by the current approaches is at least $2^{160}$ bit operations. The scheme protects function privacy and provides a simple solution for secure two-party computation and zero knowledge proof of any language in NP.

Dual receiver encryption (DRE), proposed by Diament et al. at ACM CCS 2004, is a special extension notion of public-key encryption, which enables two independent receivers to decrypt a ciphertext into a same plaintext. This primitive is quite useful in designing combined public key cryptosystems and denial of service attack-resilient protocols. Up till now, a series of DRE schemes are constructed from bilinear pairing groups and lattices. In this work, we introduce a construction of lattice-based DRE. Our scheme is indistinguishable against chosen-ciphertext attacks (IND-CCA) from the standard Learning with Errors (LWE) assumption with a public key of bit-size about $2nm\log q$, where $m$ and $q$ are small polynomials in $n$. Additionally, for the DRE notion in the identity-based setting, identity-based DRE (IB-DRE), we also give a lattice-based IB-DRE scheme that achieves chosen-plaintext and adaptively chosen identity security based on the LWE assumption with public parameter size about $(2\ell +1)nm\log q$, where $\ell$ is the bit-size of the identity in the scheme.

At Indocrypt 2016, Ashur et al. showed that linear hulls are sometimes formed in a single round of a cipher (exemplifying on Simon ciphers) and showed that the success rate of an attack may be influenced by the quality of the estimation of one-round correlations. This paper improves the understanding regarding one-round linear hulls and trails, being dedicated to the study of one-round linear hulls of the DES cipher, more exactly of its $f$-function. It shows that, in the case of DES, the existence of one-round hulls is related to the number of active Sboxes and its correlation depends on a fixed set of key bits. All the ideas presented in this paper are followed by examples and are verified experimentally.

We advance the study of secure stream-based channels (Fischlin et al., CRYPTO ’15) by considering the multiplexing of many data streams over a single channel, an essential feature of real world protocols such as TLS. Our treatment adopts the definitional perspective of Rogaway and Stegers (CSF ’09), which offers an elegant way to reason about what standardizing documents actually provide: a partial specification of a protocol that admits a collection of compliant, fully realized implementations. We formalize partially specified channels as the component algorithms of two parties communicating over a channel. Each algorithm has an oracle that provides specification details; the algorithms abstract the things that must be explicitly specified, while the oracle abstracts the things that need not be. Our security notions, which capture a variety of privacy and integrity goals, allow the adversary to respond to these oracle queries; security relative to these notions implies that the channel withstands attacks in the presence of worst-case (i.e., adversarial) realizations of the specification details. We apply this framework to a formal treatment of the TLS 1.3 record and, in doing so, show that its security hinges crucially upon details left unspecified by the standard.

Constructing indistinguishability obfuscation (iO) [BGI+01] is a central open question in cryptography. We provide new methods to make progress towards this goal. Our contributions may be summarized as follows: 1. {\textbf Bootstrapping}. In a recent work, Lin and Tessaro [LT17] (LT) show that iO may be constructed using i) Functional Encryption (FE) for polynomials of degree $L$ , ii) Pseudorandom Generators (PRG) with blockwise locality $L$ and polynomial expansion, and iii) Learning With Errors (LWE). Since there exist constructions of FE for quadratic polynomials from standard assumptions on bilinear maps [Lin17, BCFG17], the ideal scenario would be to set $L = 2$, yielding iO from widely believed assumptions. Unfortunately, it was shown soon after [LV17,BBKK17] that PRG with block locality $2$ and the expansion factor required by the LT construction, concretely $\Omega(n\cdot 2^{b(3+\epsilon)})$, where $n$ is the input length and $b$ is the block length, do not exist. In the worst case, these lower bounds rule out 2-block local PRG with stretch $\Omega(n \cdot 2^{b(2+\epsilon)})$. While [LV17,BBKK17] provided strong negative evidence for constructing iO based on bilinear maps, they could not rule out the possibility completely; a tantalizing gap has remained. Given the current state of lower bounds, the existence of 2 block local PRG with expansion factor $\Omega(n\cdot 2^{b(1+\epsilon)})$ remains open, although this stretch does not suffice for the LT bootstrapping, and is hence unclear to be relevant for iO. In this work, we improve the state of affairs as follows. (a) Weakening requirements on PRGs: In this work, we show that the narrow window of expansion factors left open by lower bounds do suffice for iO. We show a new method to construct FE for $NC_1$ from i) FE for degree L polynomials, ii) PRGs of block locality $L$ and expansion factor $\Omega(n\cdot2^{b(2+\epsilon)})$, and iii) LWE (or RLWE). Our method of bootstrapping is completely different from all known methods and does not go via randomizing polynomials. This re-opens the possibility of realizing iO from $2$ block local PRG, SXDH on Bilinear maps and LWE. (b) Broadening class of sufficient PRGs: Our bootstrapping theorem may be instantiated with a broader class of pseudorandom generators than hitherto considered for iO, and may circumvent lower bounds known for the arithmetic degree of iO -sufficient PRGs [LV17,BBKK17]; in particular, these may admit instantiations with arithmetic degree $2$, yielding iO with the additional assumptions of SXDH on Bilinear maps and LWE. In more detail, we may use the following two classes of PRG: i) Non-Boolean PRGs: We may use pseudorandom generators whose inputs and outputs need not be Boolean but may be integers restricted to a small (polynomial) range. Additionally, the outputs are not required to be pseudorandom but must only satisfy a milder indistinguishability property. We tentatively propose initializing these PRGs using the multivariate quadratic assumption (MQ) which has been widely studied in the literature [MI88,Wol05,DY09] and against the general case of which, no efficient attacks are known. We note that our notion of non Boolean PRGs is qualitatively equivalent to the notion of $\Delta$ RGs defined in the concurrent work of Ananth, Jain, Khurana and Sahai [AJKS18] except that $\Delta$ RG are weaker, in that they allow the adversary to win the game with $1/poly$ probability whereas we require that the adversary only wins with standard negligible probability. By relying on the security amplification theorem of [AJKS18] in a black box way, our construction can also make do with the weaker notion of security considered by [AJKS18]. ii) Correlated Noise Generators: We introduce an even weaker class of pseudorandom generators, which we call correlated noise generators (CNG) which may not only be non-Boolean but are required to satisfy an even milder (seeming) indistinguishability property. (c) Assumptions and Efficiency. Our bootstrapping theorems can be based on the hardness of the Learning With Errors problem (LWE) or its ring variant (RLWE) and can compile FE for degree $L$ polynomials directly to FE for $NC_1$. Previous work compiles FE for degree $L$ polynomials to FE for $NC_0$ to FE for $NC_1$ to iO [LV16,Lin17,AS17,GGHRSW13]. 2. Instantiating Primitives. In this work, we provide the first direct candidate of FE for constant degree polynomials from new assumptions on lattices. Our construction is new and does not go via multilinear maps or graded encoding schemes as all previous constructions. In more detail, let $\mathcal{F}$ be the class of circuits with depth $d$ and output length $\ell$. Then, for any $f \in \mathcal{F}$, our scheme achieves ${\sf Time({keygen})} = O\big(poly(\kappa, |f|)\big)$, and ${\sf Time({encrypt})} =O(|\vecx|\cdot 2^d \cdot \poly(\kappa))$ where $\kappa$ is the security parameter. This suffices to instantiate the bootstrapping step above. Our construction is based on the ring learning with errors assumption (RLWE) as well as new untested assumptions on NTRU rings. We provide a detailed security analysis and discuss why previously known attacks in the context of multilinear maps, especially zeroizing attacks and annihilation attacks, do not appear to apply to our setting. We caution that the assumptions underlying our construction must be subject to rigorous cryptanalysis before any confidence can be gained in their security. However, their significant departure from known multilinear map based constructions make them, we feel, a potentially fruitful new direction to explore. Additionally, being based entirely on lattices, we believe that security against classical attacks will likely imply security against quantum attacks. Note that this feature is not enjoyed by instantiations that make any use of bilinear maps even if secure instances of weak PRGs, as defined by the present work, the follow-up by Lin and Matt [LM18] and the independent work by Ananth, Jain, Khurana and Sahai [AJKS18] are found.

The Internet of Things (IoT) technology has expanded widely across the world, promising new data management opportunities for industries, companies and individuals in different sectors, such as health services or transport logistics. This trend relies on connecting devices/things to collect, exchange and store data. The exponentially increasing number of IoT devices, their origin diversity, their limited capabilities in terms of resources, as well as the ever-increasing amount of data, raise new challenges for security and privacy protection, precluding traditional access control solutions to be integrated to this new environment. In this paper, we propose a reliable server-aided policy-based access control mechanism, named CHARIOT, that enables an IoT platform to verify credentials of different devices requesting access (read/write) to the data stored within it. CHARIOT permits IoT devices to authenticate themselves to the platform without compromising their privacy by using attribute-based signatures. Our solution also allows secure delegation of costly computational operations to a cloud server, hence relieving the workload at IoT devices' side.

Recently, the Boomerang Connection Table was introduced by Cid et al. as a tool to better evaluate the probability of a boomerang distinguisher. To compute the BCT of an $n$-bit to $n$-bit S-box, the inventors of the BCT proposed an algorithm that takes $O(2^{3n})$ time. We show that one can construct the same table in only $O(2^{2n})$ time.

Overstretched NTRU, an NTRU variant with a large modulus, has been used as a building block for several cryptographic schemes in recent years. Recently, two lattice \emph{subfield attacks} and a \emph{subring attack} were proposed that broke some suggested parameters for overstretched NTRU. These attacks work by decreasing the dimension of the lattice to be reduced, which improves the performance of the lattice basis reduction algorithm. However, there are a number of conflicting claims in the literature over which of these attacks has the best performance. These claims are typically based on experiments more than analysis. Furthermore, the metric for comparison has been unclear in some prior work. In this paper, we argue that the correct metric should be the lattice dimension. We show both analytically and experimentally that the subring attack succeeds on a smaller dimension lattice than the subfield attack for the same problem parameters, and also succeeds with a smaller modulus when the lattice dimension is fixed.