Updated: 9 hours 33 min ago

### Distributed SSH Key Management with Proactive RSA Threshold Signatures

Tue, 05/01/2018 - 09:13
SSH is a security network protocol that uses public key cryptography for client authentication. SSH connections are designed to be run between a client and a server and therefore in enterprise networks there is no centralized monitoring of all SSH connections. An attractive method for enforcing such centralized control, audit or even revocation is to require all clients to access a centralized service in order to obtain their SSH keys. Doing this will introduce security and availability issues. The benefits of centralized control come with new challenges in security and availability. In this paper we present ESKM - a \emph{distributed enterprise SSH key manager}. ESKM is a secure and fault-tolerant logically-centralized SSH key manager. ESKM leverages $k$-out-of-$n$ threshold security to provide a high level of security. SSH private keys are never stored \emph{at any single node}, not even when they are used for signing. On a technical level, the system uses $k$-out-of-$n$ threshold RSA signatures, which are enforced with new methods that refresh the shares in order to achieve proactive security and prevent many side-channel attacks. In addition, we support password-based user authentication with security against offline dictionary attacks, that is achieved using threshold oblivious pseudo-random evaluation. ESKM does not require modification in the server side or of the SSH protocol. We implemented the ESKM system, and a patch for OpenSSL libcrypto for client side services. We show that the system is scalable and that the overhead in the client connection setup time is marginal.

### Security Analysis of Fan et al. Lightweight RFID Authentication Protocol for Privacy Protection in IoT

Tue, 05/01/2018 - 09:13
The designers of Radio-Frequency IDentification (RFID) systems have a challenging task for proposing secure mutual authentication protocols for Internet of Things (IoT) applications. Recently, Fan et al. proposed a new lightweight RFID mutual authentication protocol in the journal of IEEE Transactions on Industrial Informatics. They claimed that their protocol meets necessary security properties for RFID systems and can be applied for IoT. In this paper, we analyze the security of this protocol and show that it is vulnerable against secret disclosure, reader impersonation and tag traceability attacks. Additionally, we show that in their protocol the anonymity of the tag does not held.

### Arithmetic Considerations for Isogeny Based Cryptography

Tue, 05/01/2018 - 04:37
In this paper we investigate various arithmetic techniques which can be used to potentially enhance the performance in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. Firstly, we give a systematic overview of techniques to compute efficient arithmetic modulo $2^xp^y\pm 1$. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the approaches based on Montgomery reduction for such primes of a special shape are to be preferred. Moreover, the outcome of our investigation reveals that there exist moduli which allow even faster implementations. Secondly, we investigate if it is beneficial to use other curve models to speed-up the elliptic curve scalar multiplication. The use of twisted Edwards curves allows one to search for efficient addition-subtraction chains for fixed scalars while this is not possible with the differential addition law when using Montgomery curves. Our preliminary results show that despite the fact that we found such efficient chains, using twisted Edwards curves does not result in faster scalar multiplication arithmetic in the setting of SIDH.

### Certificateless Public Key Signature Schemes from Standard Algorithms

Tue, 05/01/2018 - 00:58
Certificateless public key cryptography (CL-PKC) is designed to have succinct public key management without using certificates at the same time avoid the key-escrow attribute in the identity-based cryptography. Security mechanisms employing implicit certificates achieve same goals. In this work, we first unify the security notions of these two types of mechanisms with a modified CL-PKC formulation. We further present a general key-pair generation algorithm for CL-PKC schemes and uses it to construct certificateless public key signature (CL-PKS) schemes from standard algorithms. The technique, which we apply, helps defeat known-attacks against existing constructions, and the resulting schemes could be quickly deployed based on the existing standard algorithm implementations. The proposed schemes are particularly useful to provide security services such as authentication, data integrity and non-repudiation in the Internet of Things because of their high efficiency of computation cost, bandwidth consumption and storage requirement.

### Efficient Bit-Decomposition and Modulus-Conversion Protocols with an Honest Majority

Mon, 04/30/2018 - 22:53
We propose secret-sharing-based bit-decomposition and modulus conversion protocols for a prime order ring $\mathbb{Z}_p$ with an honest majority: an adversary can corrupt $k-1$ parties of $n$ parties and $2k-1 \le n$. Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an $\ell$-bit element and $2^{\ell+\lceil \log m \rceil} < p$, where $m= k$ in the passive security and $m= \binom{n}{k-1}$ in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are $\ell$ tuple of shares in $\mathbb{Z}_2$ and a share in $\mathbb{Z}_{p'}$, respectively, where $p'$ is the modulus to be converted. If $k$ and $n$ are small, the communication complexity of our passively secure bit-decomposition and modulus-conversion protocols are $O(\ell)$ bits and $O(\lceil \log p' \rceil)$ bits, respectively. Our key observation is that a quotient of additive shares can be computed from the \emph{least} significant $\lceil \log m \rceil$ bits. If a secret $a$ is shifted'' and additively shared by $x_i$ in $\mathbb{Z}_p$ as $2^{\lceil \log m \rceil}a = \sum_{i=0}^{m-1} x_i = 2^{ \lceil \log m \rceil} a + qp$, the least significant $\lceil \log m \rceil$ bits of $\sum_{i=0}^{m-1} x_i$ determines $q$ since $p$ is an odd prime and the least significant $\lceil \log m \rceil$ bits of $2^{\lceil \log m \rceil} a$ are $0$s.

### Applications of Multilinear Forms to Cryptography

Mon, 04/30/2018 - 19:30
We study the problem of finding efficiently computable non-degenerate multilinear maps from $G_1^n$ to $G_2$, where $G_1$ and $G_2$ are groups of the same prime order, and where computing discrete logarithms in $G_1$ is hard. We present several applications to cryptography, explore directions for building such maps, and give some reasons to believe that finding examples with $n>2$ may be difficult.

### Cryptographic Hashing From Strong One-Way Functions

Mon, 04/30/2018 - 18:11
Constructing collision-resistant hash families (CRHFs) from one-way functions is a long-standing open problem and source of frustration in theoretical cryptography. In fact, there are strong negative results: black-box separations from one-way functions that are $2^{-(1-o(1))n}$-secure against polynomial time adversaries (Simon, EUROCRYPT '98) and even from indistinguishability obfuscation (Asharov and Segev, FOCS '15). In this work, we formulate a mild strengthening of exponentially secure one-way functions, and we construct CRHFs from such functions. Specifically, our security notion requires that every polynomial time algorithm has at most $2^{-n - \omega(\log(n))}$ probability of inverting two independent challenges. More generally, we consider the problem of simultaneously inverting $k$ functions $f_1,\ldots, f_k$, which we say constitute a one-way product function'' (OWPF). We show that sufficiently hard OWPFs yield hash families that are multi-input correlation intractable (Canetti, Goldreich, and Halevi, STOC '98) with respect to all sparse (bounded arity) output relations. Additionally assuming indistinguishability obfuscation, we construct hash families that achieve a broader notion of correlation intractability, extending the recent work of Kalai, Rothblum, and Rothblum (CRYPTO '17). In particular, these families are sufficient to instantiate the Fiat-Shamir heuristic in the plain model for a natural class of interactive proofs. An interesting consequence of our results is a potential new avenue for bypassing black-box separations. In particular, proving (with necessarily non-black-box techniques) that parallel repetition amplifies the hardness of specific one-way functions -- for example, all one-way permutations -- suffices to directly bypass Simon's impossibility result.

### Fine-Grained and Application-Ready Distance-Bounding Security

Mon, 04/30/2018 - 18:10
Distance-bounding (DB) protocols are being adopted in different applications, e.g., contactless payments, keyless entries. For DB to be application-ready, "pick-and-choose" corruption models and clear-cut security definitions in DB are needed. Yet, this is virtually impossible using the four existing formalisms for distance-bounding (DB), whereby each considers around five different security properties, arguably intertwined and hard to compare amongst each other. In particular, terrorist-fraud resistance has been notoriously problematic to formalise in DB. Also, achieving this property, often weakness a protocol's general security. We demonstrate that --in fact-- terrorist-fraud resistance cannot be achieved, under standard assumptions made for DB protocols. Our result wraps up terrorist-fraud resistance in provable-security in DB. As a consequence of terrorist-fraud resistance being made irrelevant, and to address application-ready DB, we present a new, provable-security model for distance-bounding. It formalises fine-grained corruption-modes (i.e., white-box and black-box corrupted provers) and this allows for clearer security definitions driven by the separation in corruption-modes. Also, our model explicitly includes a security-property generalising key-leakage, which per se --before this-- was studied only implicitly or as a by-product of other DB-security properties. In all, our formalism only requires three, clear-cut security definitions which can be "picked and chosen" based on the application-driven prover-corruption modes.

### CSIDH: An Efficient Post-Quantum Commutative Group Action

Mon, 04/30/2018 - 18:07
We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes-Rostovtsev-Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field ${\mathbb F_p}$, rather than to ordinary elliptic curves. The Diffie-Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at the AES-128 security level, matching NIST's post-quantum security category I.

### Revocable Identity-based Encryption from Codes with Rank Metric

Mon, 04/30/2018 - 18:07
In this paper, we present an identity-based encryption scheme from codes with efficient key revocation. Recently, in Crypto 2017, Gaborit et al. proposed a first identity-based encryption scheme from codes with rank metric, called RankIBE. To extract the decryption key from any public identity, they constructed a trapdoor function which relies on RankSign, a signature scheme proposed by Gaborit et al. in PQCrypto 2014. We adopt the same trapdoor function to add efficient key revocation functionality in the RankIBE scheme. Our revocable IBE scheme from codes with rank metric makes use of a binary tree data structure to reduce the amount of work in terms of key updates for the key authority. The total size of key updates requires logarithmic complexity in the maximum number of users and linear in the number of revoked users. We prove that our revocable IBE scheme is selective-ID secure in the random oracle model, under the hardness of three problems: the Rank Syndrome Decoding (RSD) problem, the Augmented Low-Rank Parity Check Code (LRPC+) problem, and the Rank Support Learning (RSL) problem.

### Masking the GLP Lattice-Based Signature Scheme at Any Order

Mon, 04/30/2018 - 18:06
Abstract. Recently, numerous physical attacks have been demonstrated against lattice- based schemes, often exploiting their unique properties such as the reliance on Gaussian distributions, rejection sampling and FFT-based polynomial multiplication. As the call for concrete implementations and deployment of postquantum cryptography becomes more pressing, protecting against those attacks is an important problem. However, few counter- measures have been proposed so far. In particular, masking has been applied to the decryp- tion procedure of some lattice-based encryption schemes, but the much more difficult case of signatures (which are highly non-linear and typically involve randomness) has not been considered until now. In this paper, we describe the first masked implementation of a lattice-based signature scheme. Since masking Gaussian sampling and other procedures involving contrived prob- ability distribution would be prohibitively inefficient, we focus on the GLP scheme of Gu &#776;neysu, Lyubashevsky and Po &#776;ppelmann (CHES 2012). We show how to provably mask it in the Ishai–Sahai–Wagner model (CRYPTO 2003) at any order in a relatively efficient man- ner, using extensions of the techniques of Coron et al. for converting between arithmetic and Boolean masking. Our proof relies on a mild generalization of probing security that supports the notion of public outputs. We also provide a proof-of-concept implementation to assess the efficiency of the proposed countermeasure.

### Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution

Mon, 04/30/2018 - 18:05
There have been tremendous advances in reducing interaction, communication and verification time in zero-knowledge proofs but it remains an important challenge to make the prover efficient. We construct the first zero-knowledge proof of knowledge for the correct execution of a program on public and private inputs where the prover computation is nearly linear time. This saves a polylogarithmic factor in asymptotic performance compared to current state of the art proof systems. We use the TinyRAM model to capture general purpose processor computation. An instance consists of a TinyRAM program and public inputs. The witness consists of additional private inputs to the program. The prover can use our proof system to convince the verifier that the program terminates with the intended answer within given time and memory bounds. Our proof system has perfect completeness, statistical special honest verifier zero-knowledge, and computational knowledge soundness assuming linear-time computable collision-resistant hash functions exist. The main advantage of our new proof system is asymptotically efficient prover computation. The prover's running time is only a superconstant factor larger than the program's running time in an apples-to-apples comparison where the prover uses the same TinyRAM model. Our proof system is also efficient on the other performance parameters; the verifier's running time time and the communication are sublinear in the execution time of the program and we only use a log-logarithmic number of rounds.

### Post-Quantum One-Time Linkable Ring Signature and Application to Ring Confidential Transactions in Blockchain (Lattice RingCT v1.0)

Mon, 04/30/2018 - 18:04
In this paper, we construct a Lattice-based one-time Linkable Ring Signature (L2RS) scheme, which enables the public to verify if two or more signatures were generated by same signatory, whilst still preserving the anonymity of the signatory. The L2RS provides unconditional anonymity and security guarantees under the Ring Short Integer Solution (Ring-SIS) lattice hardness assumption. The proposed L2RS scheme is extended to be applied in a protocol that we called Lattice Ring Con dential transaction (Lattice RingCT) RingCT v1.0, which forms the foundation of the privacy-preserving protocol in any post-quantum secure cryptocurrency such as Hcash.

### Composable Proof-of-Stake Blockchains with Dynamic Availability

Mon, 04/30/2018 - 18:04
Proof-of-stake-based (in short, PoS-based) blockchains aim to overcome scalability, effi- ciency, and composability limitations of the proof-of-work paradigm, which underlies the security of several mainstream cryptocurrencies including Bitcoin. Our work puts forth the first (global universally) composable (GUC) treatment of PoS-based blockchains in a setting that captures—for the first time in GUC—arbitrary numbers of parties that may not be fully operational, e.g., due to network problems, reboots, or updates of their OS that affect all or just some of their local resources including their network interface and clock. This setting, which we refer to as dynamic availability, naturally captures decentralized environments within which real-world deployed blockchain protocols are assumed to operate. We observe that none of the existing PoS-based blockchain protocols can realize the ledger functionality under dynamic availability in the same way that bitcoin does (using only the information available in the genesis block). To address this we propose a new PoS-based protocol, “Ouroboros Genesis”, that adapts one of the latest cryptographically-secure PoS-based blockchain protocols with a novel chain selection rule. The rule enables new or offline parties to safely (re-)join and bootstrap their blockchain from the genesis block without any trusted advice—such as checkpoints—or assumptions regarding past availability. We say that such a blockchain protocol can “bootstrap from genesis.” We prove the GUC security of Ouroboros Genesis against a fully adaptive adversary controlling less than half of the total stake. Our model allows adversarial scheduling of messages in a network with delays and captures the dynamic availability of participants in the worst case. Importantly, our protocol is effectively independent of both the maximum network delay and the minimum level of availability— both of which are run-time parameters. Proving the security of our construction against an adaptive adversary requires a novel martingale technique that may be of independent interest in the analysis of blockchain protocols.

### ALGORAND AGREEMENT: Super Fast and Partition Resilient Byzantine Agreement

Mon, 04/30/2018 - 18:03
We present a simple Byzantine agreement protocol with leader election, that works under > 2/3 honest majority and does not rely on the participants having synchronized clocks. When honest messages are delivered within a bounded worst-case delay, agreement is reached in expected constant number of steps when the elected leader is malicious, and is reached after two steps when the elected leader is honest. Our protocol is resilient to arbitrary network partitions with unknown length, and recovers fast after the partition is resolved and bounded message delay is restored. We will briefly discuss how the protocol applies to blockchains in a permissionless system. In particular, when an honest leader proposes a block of transactions, the first voting step happens in parallel with the block propagation. Effectively, after the block propagates, a certificate is generated in just one step of voting.

### Monotone Batch NP-Delegation with Applications to Access Control

Mon, 04/30/2018 - 18:02
Consider an access policy for some resource which only allows access to users of the system who own a certain set of attributes. Specifically, we consider the case where such an access structure is defined by a monotone formula (or logarithmic depth circuit) $F:\{0,1\}^N\rightarrow\{0,1\}$, where $N$ is the number of possible attributes. In this work we present two results, which we believe to be of individual interest even regardless of the above application, and show how to combine them to achieve a succinct single-round private access control protocol. That is, a verifier can be convinced that an approved user (i.e. one which holds an approved set of attributes) is accessing the system, without learning any additional information about the user or the set of attributes. First, assuming a computational PIR scheme (which can be based, for example, on the polynomial hardness of the LWE assumption), we construct for any $NP$ language $L$, a succinct single-round (2-message) protocol for delegating \monotone batch $L$ computations. Explicitly, for every $N\in \mathbb{N}$, every $x_1,\ldots,x_N\in \{0,1\}^n$, and every monotone formula $F:\{0,1\}^N\rightarrow \{0,1\}$, a prover can succinctly prove that $F(1_{x_1\in L},\ldots,1_{x_N\in L})=1$, where $1_{x_i\in L}=1$ if and only if $x_i\in L$, and where the communication complexity is $m \cdot polylog(N)$ where $m$ is the length of a single witness. Second, assuming a quasi-polynomially secure two-message oblivious transfer scheme with statistical sender privacy (which can be based on quasi-polynomial hardness of the DDH, QR or DCR assumptions), we show how to convert any single-round protocol into a witness indistinguishable one, with similar communication complexity.

### Functional Graphs and Their Applications in Generic Attacks on Iterated Hash Constructions

Mon, 04/30/2018 - 18:02
We provide a survey about generic attacks on cryptographic hash constructions including hash-based message authentication codes and hash combiners. We look into attacks involving iteratively evaluating identical mappings many times. The functional graph of a random mapping also involves iteratively evaluating the mapping. These attacks essentially exploit properties of the functional graph. We map the utilization space of those properties from numerous proposed known attacks, draw a comparison among classes of attacks about their advantages and limitations. We provide a systematic exposition of concepts of cycles, deep-iterate images, collisions and their roles in cryptanalysis of iterated hash constructions. We identify the inherent relationship between these concepts, such that case-by-case theories about them can be unified into one knowledge system, that is, theories on the functional graph of random mappings. We show that the properties of the cycle search algorithm, the chain evaluation algorithm and the collision search algorithm can be described based on statistic results on the functional graph. Thereby, we can provide different viewpoints to support previous beliefs on individual knowledge. In that, we invite more sophisticated analysis of the functional graph of random mappings and more future exploitations of its properties in cryptanalysis.

### PanORAMa: Oblivious RAM with Logarithmic Overhead

Mon, 04/30/2018 - 17:58
We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead $O(\log N \cdot \log \log N)$ for database of N blocks and for any block size $B = \Omega(\log N)$ while requiring client memory of only a constant number of memory blocks. Our scheme can be instantiated in the ”balls and bins” model in which Goldreich and Ostrovsky [JACM 96] showed an $\Omega(\log N)$ lower bound for ORAM communication. Our construction follows the hierarchical approach to ORAM design and relies on two main building blocks of independent interest: a new oblivious hash table construction with improved amortized $O(\log N + poly(\log \log \lambda))$ communication overhead for security parameter $\lambda$ and $N = \mathsf{poly}(\lambda)$, assuming its input is randomly shuffled; and a complementary new oblivious random multi-array shuffle construction, which shuffles N blocks of data with communication $O(N \log \log \lambda + \frac{N \log N}{\log \lambda})$ when the input has a certain level of entropy. We combine these two primitives to improve the shuffle time in our hierarchical ORAM construction by avoiding heavy oblivious shuffles and leveraging entropy remaining in the merged levels from previous shuffles. As a result, the amortized shuffle cost is asymptotically the same as the lookup complexity in our construction.

### Secure Computation using Leaky Correlations (Asymptotically Optimal Constructions)

Mon, 04/30/2018 - 17:57
Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by adversarial parties, which can compromise the security of the entire secure computation protocol. The objective, therefore, is to preserve the security of the honest party despite the leakage performed by the adversary on her share. Prior solutions, starting with $n$-bit leaky shares, either used 4 messages or enabled the secure computation of only sub-linear size circuits. Our work presents the first 2-message secure computation protocol for 2-party functionalities that have $\Theta(n)$ circuit-size despite $\Theta(n)$-bits of leakage, a qualitatively optimal result. We compose a suitable 2-message secure computation protocol in parallel with our new 2-message correlation extractor. Correlation extractors, introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai (FOCS--2009) as a natural generalization of privacy amplification and randomness extraction, recover fresh'' correlations from the leaky ones, which are subsequently used by other cryptographic protocols. We construct the first 2-message correlation extractor that produces $\Theta(n)$-bit fresh correlations even after $\Theta(n)$-bit leakage. Our principal technical contribution, which is of potential independent interest, is the construction of a family of multiplication-friendly linear secret sharing schemes that is simultaneously a family of small-bias distributions. We construct this family by randomly twisting then permuting'' appropriate Algebraic Geometry codes over constant-size fields.