Updated: 3 hours 39 min ago

Improved Quantum Multicollision-Finding Algorithm

Tue, 11/20/2018 - 03:14
The current paper improves the number of queries of the previous quantum multi-collision nding algorithms presented by Hosoyamada et al. at Asiacrypt 2017. Let $l$-collision be $l$ distinct inputs that result in the same output of a target function. The previous algorithm finds $l$-collisions by recursively calling the algorithm for finding $(l-1)$-collisions, and it achieves the query complexity of $O(N^{(3^{l-1}-1) / (2 \cdot 3^{l-1})})$. The new algorithm removes the redundancy of the previous recursive algorithm so that computations among different recursive calls can share a part of computations. The new algorithm achieves the query complexity of $\tilde{O}(N^{(2^{l-1}-1) / (2^{l}-1)})$. Moreover, it finds multiclaws for random functions, which are harder to find than multicollisions.

Secure Opportunistic Multipath Key Exchange

Mon, 11/19/2018 - 23:38
The security of today's widely used communication security protocols is based on trust in Certificate Authorities (CAs). However, the real security of this approach is debatable, since certificate handling is tedious and many recent attacks have undermined the trust in CAs. On the other hand, opportunistic encryption protocols such as Tcpcrypt, which are currently gaining momentum as an alternative to no encryption, have similar security to using untrusted CAs or self-signed certificates: they only protect against passive attackers. In this paper, we present a key exchange protocol, Secure Multipath Key Exchange (SMKEX), that enables all the benefits of opportunistic encryption (no need for trusted third parties or pre-established secrets), as well as proven protection against some classes of active attackers. Furthermore, SMKEX can be easily extended to a trust-on-first-use setting and can be easily integrated with TLS, providing the highest security for opportunistic encryption to date while also increasing the security of standard TLS. We show that SMKEX is made practical by the current availability of path diversity between different AS-es. We also show a method to create path diversity with encrypted tunnels without relying on the network topology. These allow SMKEX to provide protection against most adversaries for a majority of Alexa top 100 web sites. We have implemented SMKEX using a modified Multipath TCP kernel implementation and a user library that overwrites part of the socket API, allowing unmodified applications to take advantage of the security provided by SMKEX.

When Theory Meets Practice: A Framework for Robust Profiled Side-channel Analysis

Mon, 11/19/2018 - 23:37
Profiled side-channel attacks are the most powerful attacks and they consist of two steps. The adversary first builds a leakage model, using a device similar to the target one, then it exploits this leakage model to extract the secret information from the victim's device. These attacks can be seen as a classification problem, where the adversary needs to decide to what class (corresponding to the secret key) the traces collected from the victim's devices belong. For a number of years, the research community studied profiled attacks and proposed numerous improvements. Despite a large number of empirical works, a framework with strong theoretical foundations to address profiled side-channel attacks is still missing. In this paper, we propose a framework capable of modeling and evaluating all profiled analysis attacks. This framework is based on the expectation estimation problem that has strong theoretical foundations. Next, we quantify the effects of perturbations injected at different points in our framework through robustness analysis. Finally, we experimentally validate our framework using publicly available traces, several classifiers, and performance metrics.

An Analysis of the ProtonMail Cryptographic Architecture

Mon, 11/19/2018 - 23:28
ProtonMail is an online email service that claims to offer end-to-end encryption such that "even [ProtonMail] cannot read and decrypt [user] emails." The service, based in Switzerland, offers email access via webmail and smartphone applications to over five million users as of November 2018. In this work, we provide the first independent analysis of ProtonMail's cryptographic architecture. We find that for the majority of ProtonMail users, no end-to-end encryption guarantees have ever been provided by the ProtonMail service and that the "Zero-Knowledge Password Proofs" are negated by the service itself. We also find and document weaknesses in ProtonMail's "Encrypt-to-Outside" feature. We justify our findings against well-defined security goals and conclude with recommendations.

Organizational Cryptography for Access Control

Mon, 11/19/2018 - 23:28
A cryptosystem for granting/rescinding access permission is proposed, based on elliptic curve cryptography. The Organizational Cryptosystem' grants access permission not by giving secret (decription) key to the corresponding user but by converting the ciphertext so that the user can decript with their secret key. The conversion key' for the document, which is created from the secret key which the ciphertext has been originally encrypted for, the public key of the member who shall be permitted to read the ciphertext, and a part of the ciphertext. Therefore it is not possible to decrypt the ciphertext with the conversion key. Nor, for the administrator who issues the conversion key, to obtain any information about the plaintext.

Parallel Chains: Improving Throughput and Latency of Blockchain Protocols via Parallel Composition

Mon, 11/19/2018 - 23:27
Two of the most significant challenges in the design of blockchain protocols is increasing their transaction processing throughput and minimising latency in terms of transaction settlement. In this work we put forth for the first time a formal execution model that enables to express transaction throughput while supporting formal security arguments regarding safety and liveness. We then introduce parallel-chains, a simple yet powerful non-black-box composition technique for blockchain protocols. We showcase our technique by providing two parallel-chains protocol variants, one for the PoS and one for PoW setting, that exhibit optimal throughput under adaptive fail-stop corruptions while they retain their resiliency in the face of Byzantine adversity assuming honest majority of stake or computational power, respectively. We also apply our parallel-chains composition method to improve settlement latency; combining parallel composition with a novel transaction weighing mechanism we show that it is possible to scale down the time required for a transaction to settle by any given constant while maintaining the same level of security.

Non-Interactive Non-Malleability from Quantum Supremacy

Mon, 11/19/2018 - 23:23
We construct non-interactive non-malleable commitments without setup in the plain model, under well-studied assumptions. First, we construct non-interactive non-malleable commitments with respect to commitment for $\epsilon \log \log n$ tags for a small constant $\epsilon > 0$, under the following assumptions: - Sub-exponential hardness of factoring or discrete log. - Quantum sub-exponential hardness of learning with errors (LWE). Second, as our key technical contribution, we introduce a new tag amplification technique. We show how to convert any non-interactive non-malleable commitment with respect to commitment for $\epsilon\log \log n$ tags (for any constant $\epsilon>0$) into a non-interactive non-malleable commitment with respect to replacement for $2^n$ tags. This part only assumes the existence of sub-exponentially secure non-interactive witness indistinguishable (NIWI) proofs, which can be based on sub-exponential security of the decisional linear assumption. Interestingly, for the tag amplification technique, we crucially rely on the leakage lemma due to Gentry and Wichs (STOC 2011). For the construction of non-malleable commitments for $\epsilon \log \log n$ tags, we rely on quantum supremacy. This use of quantum supremacy in classical cryptography is novel, and we believe it will have future applications. We provide one such application to two-message witness indistinguishable (WI) arguments from (quantum) polynomial hardness assumptions.

A Note on Transitional Leakage When Masking AES with Only Two Bits of Randomness

Mon, 11/19/2018 - 23:19
Recently, Gross et al. demonstrated a first-order probing-secure implementation of AES using only two bits of randomness for both the initial sharing and the entire computation of AES. In this note, we recall that first-order probing security may not be sufficient for practical first-order security when randomness is re-cycled. We demonstrate that without taking the transitional leakage into account, the expected security level in a serialized design based on their concept might not be achieved in practice.

Fly, you fool! Faster Frodo for the ARM Cortex-M4

Mon, 11/19/2018 - 23:19
We present an efficient implementation of FrodoKEM-640 on an ARM Cortex-M4 core. We leverage the single instruction, multiple data paradigm, available in the instruction set of the ARM Cortex-M4, together with a careful analysis of the memory layout of matrices to considerably speed up matrix multiplications. Our implementations take up to 79.4% less cycles than the reference. Moreover, we challenge the usage of a cryptographically secure pseudorandom number generator for the generation of the large public matrix involved. We argue that statistically good pseudorandomness is enough to achieve the same security goal. Therefore, we propose to use xoshiro128** as a PRNG instead: its structure can be easily integrated in FrodoKEM-640, it passes all known statistical tests and greatly outperforms previous choices. By using xoshiro128** we improve the generation of the large public matrix, which is a considerable bottleneck for embedded devices, by up to 96%.

Short Group Signature in the Standard Model

Mon, 11/19/2018 - 23:19
Group signature is a central tool for privacy-preserving protocols, ensuring authentication, anonymity and accountability. It has been massively used in cryptography, either directly or through variants such as direct anonymous attestations. However it remains a complex tool, especially in the standard model where each of its building blocks is quite costly to instantiate. In this work, we propose a new group signature scheme proven secure in the standard model which significantly decreases the complexity with respect to the state-of-the-art. More specifically, we halve both the size and the computational cost compared to the most efficient alternative in the standard model. Moreover, our construction is also competitive against the most efficient ones in the random oracle model, thus closing the traditional efficiency gap between these two models. Our construction is based on a tailored combination of two popular signatures, which avoids the explicit use of encryption schemes or zero-knowledge proofs. It is flexible enough to achieve security in different models and is thus suitable for most contexts.

Reducing Complexity of Pairing Comparisons using Polynomial Evaluation

Mon, 11/19/2018 - 07:43
We propose a new method for reducing complexity of the pairing comparisons based on polynomials. Thought the construction introduces uncertainty into (usually deterministic) checks, it is easily quantifiable and in most cases extremely small. The application to CL-LRSW signature verification under n messages and group order q allows to reduce the number of computed pairings from 4n down to just 4, while the introduced uncertainty is just (2n-1)/q.

Standard Lattice-Based Key Encapsulation on Embedded Devices

Mon, 11/19/2018 - 06:51
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.

An Improved RNS Variant of the BFV Homomorphic Encryption Scheme

Sun, 11/18/2018 - 23:19
We present an optimized implementation of the Fan-Vercauteren variant of Brakerski's scale-invariant homomorphic encryption scheme. Our algorithmic improvements focus on optimizing decryption and homomorphic multiplication in the Residue Number System (RNS), using the Chinese Remainder Theorem (CRT) to represent and manipulate the large coefficients in the ciphertext polynomials. In particular, we propose efficient procedures for scaling and CRT basis extension that do not require translating the numbers to standard (positional) representation. Compared to the previously proposed RNS design due to Bajard et al., our procedures are simpler and faster, and introduce a lower amount of noise. We implement our optimizations in the PALISADE library and evaluate the runtime performance for the range of multiplicative depths from 1 to 100. For example, homomorphic multiplication for a depth-20 setting can be executed in 62 ms on a modern server system, which is already practical for some outsourced-computing applications. Our algorithmic improvements can also be applied to other scale-invariant homomorphic encryption schemes, such as YASHE.

No-signaling Linear PCPs

Sun, 11/18/2018 - 21:52
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 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 scheme for delegating computation by using a known transformation. Compared with existing 2-message delegation schemes 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.

Cryptanalysis of the Wave Signature Scheme

Fri, 11/16/2018 - 14:37
In this paper, we cryptanalyze the signature scheme Wave, which has recently appeared as a preprint. First, we show that there is a severe information leakage occurring from honestly-generated signatures. Then, we illustrate how to exploit this leakage to retrieve an alternative private key, which enables efficiently forging signatures for arbitrary messages. Our attack manages to break the proposed 128-bit secure Wave parameters in just over a minute, most of which is actually spent collecting genuine signatures. Finally, we explain how our attack applies to generalized versions of the scheme which could potentially be achieved using generalized admissible $(U,U+V)$ codes and larger field characteristics.

Minting Mechanisms for Blockchain -- or -- Moving from Cryptoassets to Cryptocurrencies

Fri, 11/16/2018 - 14:20
Permissionless blockchain systems, such as Bitcoin, rely on users using their computational power to solve a puzzle in order to achieve a consensus. To incentivise users in maintaining the system, newly minted coins are assigned to the user who solves this puzzle. A hardware race that has hence ensued among the users, has had a detrimental impact on the environment, with enormous energy consumption and increased global carbon footprint. On the other hand, proof of stake systems incentivise coin hoarding as players maximise their utility by holding their stakes. As a result, existing cryptocurrencies do not mimic the day-to-day usability of a fiat currency, but are rather regarded as cryptoassets or investment vectors. In this work we initiate the study of minting mechanisms in cryptocurrencies as a primitive on its own right, and as a solution to prevent coin hoarding we propose a novel minting mechanism based on waiting-time first-price auctions. Our main technical tool is a protocol to run an auction over any blockchain. Moreover, our protocol is the first to securely implement an auction without requiring a semi-trusted party, i.e., where every miner in the network is a potential bidder. Our approach is generically applicable and we show that it is incentive-compatible with the underlying blockchain, i.e., the best strategy for a player is to behave honestly. Our proof-of-concept implementation shows that our system is efficient and scales to tens of thousands of bidders.

Lightweight Circuits with Shift and Swap

Fri, 11/16/2018 - 09:39
In CHES 2017, Moradi et al. presented a paper on Bit-Sliding'' in which the authors proposed lightweight constructions for SPN based block ciphers like AES, Present and SKINNY. The main idea behind these constructions was to reduce the length of the datapath to 1 bit and to reformulate the linear layer for these ciphers so that they require fewer scan flip-flops (which have built-in multiplexer functionality and so larger in area as compared to a simple flip-flop). In this paper we take the idea forward: is it possible to construct the linear layer using only 2 scan flip-flops? Take the case of Present: in the language of mathematics, the above question translates to: can the Present permutation be generated by some ordered composition only two types of permutations? The question can be answered in the affirmative by drawing upon the theory of permutation groups. However straightforward constructions would require that the ordered composition'' consist of a large number of simpler permutations. This would naturally take a large number of clock cycles to execute in a flip-flop array having only two scan flip-flops and thus incur heavy loss of throughput. In this paper we try to analyze SPN ciphers like Present and Gift that have a bit permutation as their linear layer. We tried to construct the linear layer of the cipher using as little clock cycles as possible. As an outcome we propose smallest known constructions for Present and Gift block ciphers for both encryption and combined encryption+decryption functionalities. We extend the above ideas to propose the first known construction of the Flip stream cipher.

Private Function Evaluation with Cards

Fri, 11/16/2018 - 09:39
Card-based protocols allow to evaluate an arbitrary fixed Boolean function $f$ on a hidden input to obtain a hidden output, without the executer learning anything about either of the two (e.g. Crépeau and Kilian, CRYPTO 1993). We explore the case where $f$ implements a universal function, i.e. $f$ is given the encoding $\langle P\rangle$ of a program $P$ and an input $x$ and computes $f(\langle P\rangle, x) = P(x)$. More concretely, we consider universal circuits, Turing machines, RAM machines, and branching programs, giving secure and conceptually simple card-based protocols in each case. We argue that card-based cryptography can be performed in a setting that is only very weakly interactive, which we call the “surveillance” model. Here, when Alice executes a protocol on the cards, the only task of Bob is to watch that Alice does not illegitimately turn over cards and that she shuffles in a way that nobody knows anything about the total permutation applied to the cards. We believe that because of this very limited interaction, our results can be called program obfuscation. As a tool, we develop a useful sub-protocol $\mathsf{sort}_{\Pi}X\mathop{\uparrow}Y$ that couples the two equal-length sequences $X, Y$ and jointly and obliviously permutes them with the permutation $\pi\in\Pi$ that lexicographically minimizes $\pi(X)$. We argue that this generalizes ideas present in many existing card-based protocols. In fact, AND, XOR, bit copy (Mizuki and Sone, FAW 2009), coupled rotation shuffles (Koch and Walzer, ePrint 2017) and the “permutation division” protocol of (Hashimoto et al., ICITS 2017) can all be expressed as “coupled sort protocols”.

DEXON: A Highly Scalable, Decentralized DAG-Based Consensus Algorithm

Fri, 11/16/2018 - 09:38
A blockchain system is a replicated state machine that must be fault tolerant. When designing a blockchain system, there is usually a trade-off between decentralization, scalability, and security. In this paper, we propose a novel blockchain system, DEXON, which achieves high scalability while remaining decentralized and robust in the real-world environment. We have two main contributions. First, we present a highly scalable sharding framework for blockchain. This framework takes an arbitrary number of single chains and transforms them into the blocklattice data structure, enabling high scalability and low transaction confirmation latency with asymptotically optimal communication overhead. Second, we propose a single-chain protocol based on our novel verifiable random function and a new Byzantine agreement that achieves high decentralization and low latency.

Faster SeaSign signatures through improved rejection sampling

Fri, 11/16/2018 - 09:34
We speed up the isogeny-based SeaSign'' signature scheme recently proposed by De Feo and Galbraith. The core idea in SeaSign is to apply the Fiat–Shamir with aborts'' transform to the parallel repeated execution of an identification scheme based on CSIDH. We optimize this general transform by allowing the prover to not answer a limited number of said parallel executions, thereby lowering the overall probability of rejection. The performance improvement ranges between factors of approximately 4.4 and 65.7 for various instantiations of the scheme, at the expense of roughly doubling the signature sizes.