Updated: 2 hours 34 min ago

### Covert Security with Public Verifiability: Faster, Leaner, and Simpler

Fri, 11/16/2018 - 09:34
The notion of covert security for secure two-party computation serves as a compromise between the traditional semi-honest and malicious security definitions. Roughly, covert security ensures that cheating behavior is detected by the honest party with reasonable probability. It provides more realistic guarantees than semi-honest security with significantly less overhead than is required by malicious security. The rationale for covert security is that it dissuades cheating by parties that care about their reputation and do not want to risk being caught. Further thought, however, shows that a much stronger disincentive is obtained if the honest party can generate a publicly verifiable certificate of misbehavior when cheating is detected. While the corresponding notion of publicly verifiable covert (PVC) security has been explored, existing PVC protocols are complex and less efficient than the best-known covert protocols, and have impractically large certificates. We propose a novel PVC protocol that significantly improves on prior work. Our protocol uses only off-the-shelf'' primitives (in particular, it avoids signed oblivious transfer) and, for deterrence factor 1/2, has only 20-40% overhead (depending on the circuit size and network bandwidth) compared to state-of-the-art semi-honest protocols. Our protocol also has, for the first time, constant-size certificates of cheating (e.g., 354 bytes long at the 128-bit security level). As our protocol offers strong security guarantees with low overhead, we suggest that it is the best choice for many practical applications of secure two-party computation.

### Further observations on SIMON and SPECK families of block ciphers

Fri, 11/16/2018 - 09:33
SIMON and SPECK families of block ciphers are well-known lightweight ciphers designed by NSA. In this note, based on the previous investigations on SIMON, a closed formula for the squared correlations and differential probabilities of the mapping $\phi(x) = x \odot S^1(x)$ on $\mathbb{F}_2^n$ is given. From the aspects of linear and differential cryptanalysis, this mapping is equivalent to the core quadratic mapping of SIMON via rearrangement of coordinates and EA-equivalence. Based upon the proposed explicit formula, a full description of DDT and LAT of $\phi$ is provided. In the case of SPECK, as the only nonlinear operation in this family of ciphers is, addition mod $2^n$, after reformulating the formula for linear and differential probabilities of addition mod $2^n$, straightforward algorithms for finding the output masks with maximum squared correlation, given the input masks as well as the output differences with maximum differential probability, given the input differences, are presented.

### P4TC---Provably-Secure yet Practical Privacy-Preserving Toll Collection

Fri, 11/16/2018 - 09:32
Electronic toll collection (ETC) is widely used all over the world not only to finance our road infrastructures, but also to realize advanced features like congestion management and pollution reduction by means of dynamic pricing. Unfortunately, existing systems rely on user identification and allow tracing a user's movements. Several abuses of this personalized location data have already become public. In view of the planned European-wide interoperable tolling system EETS and the new EU General Data Protection Regulation, location privacy becomes of particular importance. In this paper, we propose a flexible cryptographic model and protocol framework designed for privacy-preserving toll collection in the most dominant setting, i.e., Dedicated Short Range Communication (DSRC) ETC. As opposed to our work, most related cryptographic proposals target a less popular type of toll collection based on Global Navigation Satellite Systems (GNSS), and do not come with a thorough security model and proof. In fact, to the best of our knowledge, our system is the first in the DSRC setting with a (rigorous) security model and proof. A major challenge in designing the framework at hand was to combine provable security and practicality, where the latter includes practical performance figures and a suitable treatment of real-world issues, like broken on-board units etc. For our ETC system, we make use of and significantly extend a payment protocol building block, called Black-Box Accumulators, introduced at ACM CCS 2017. Additionally, we provide a prototypical implementation of our system on realistic hardware. This implementation already features fairly practical performance figures, even though there is still room for optimizations. An interaction between an on-board unit and a road-side unit is estimated to take less than a second allowing for toll collection at full speed assuming one road-side unit per lane.

### Proof-of-Stake Protocols for Privacy-Aware Blockchains

Fri, 11/16/2018 - 09:31
Proof-of-stake (PoS) protocols are emerging as one of the most promising alternative to the wasteful proof-of-work (PoW) protocols for consensus in Blockchains (or distributed ledgers). However, current PoS protocols inherently disclose both the identity and the wealth of the stakeholders, and thus seem incompatible with privacy-preserving cryptocurrencies (such as ZCash, Monero, etc.). In this paper we initiate the formal study for PoS protocols with privacy properties. Our results include: - A (theoretical) feasibility result showing that it is possible to construct a general class of private PoS (PPoS) protocols; and to add privacy to a wide class of PoS protocols, - A privacy-preserving version of a popular PoS protocol, Ouroboros Praos. Towards our result, we define the notion of anonymous verifiable random function, which we believe is of independent interest.

### Tropical cryptography II: extensions by homomorphisms

Fri, 11/16/2018 - 09:29
We use extensions of tropical algebras as platforms for very efficient public key exchange protocols.

### Some Properties of Modular Addition

Fri, 11/16/2018 - 09:29
In this paper we study a problem which emerged during an attempt to apply a differential cryptanalysis method to the <<Magma>> algorithm. We obtained a general formula of distribution in the difference distribution table of addition modulo $2^n$ and provided an efficient method for computing the distribution in a row with given index. Moreover, an exact formula that may be used to solve the task of counting all the distributions was obtained, and an asymptotically accurate approximation of number of distinct distributions was proved. Finally, we designed an algorithm to generate all distributions in $2^{O(\sqrt{(n)})}$ operations (whereas the corresponding brute-force method takes $2^{\Omega(n)}$).

### A fully distributed revocable ciphertext-policy hierarchical attribute-based encryption without pairing

Fri, 11/16/2018 - 09:28
Several appealing features of cloud computing such as cost-effectiveness and user-friendliness have made many users and enterprises interested to outsource their sensitive data for sharing via cloud. However, it causes many new challenges toward data confidentiality, access control , scalability, and flexibility. Ciphertext-policy Hierarchical attribute-based encryption (CP-HABE) can be a promising solution to the mentioned problems. But, the existing HABE schemes have several limitations in their key delegation and user revocation mechanisms. In this work, to solve these problems, we introduce the concept of \textit{fully distributed revocable } CP-HABE (FDR-CP-HABE) system and propose the first FDR-CP-HABE scheme. The proposed scheme provides a high level of flexibility and scalability in the key delegation and user revocation mechanisms. Moreover, our proposed system is pairing-free and realizes lightweight computing in decryption phase. Indeed, by exploiting the computational operation outsourcing technique, most of the operations have been done by the powerful cloud service provider and very few computations have been leaved to the data user. Also, in our scheme the storage cost on the data user side has been decreased, compared to the other similar works. Moreover, using the hardness assumption of Decisional Bilinear Diffie-Hellman (DBDH) problem, we show that the proposed scheme is adaptively semantically secure in the standard model.

### Insecurity of a provably secure and lightweight certificateless signature scheme for IIoT environments

Fri, 11/16/2018 - 09:26
Recently, Karati et al. presented a lightweight certificateless signature scheme for industrial Internet of Things (IIoT) environments, and claimed the scheme was provably secure in the standard model. In this paper, it is indicated that the scheme is not secure by showing two concrete attacks.

### Correction to "Improving the DGK comparison protocol"

Fri, 11/16/2018 - 09:25
At the IEEE Workshop on Information Forensics and Security in 2012, Veugen introduced two ways of improving a well-known secure comparison protocol by Damg{\aa}rd, Geisler and Kr{\o}igaard, which uses additively homomorphic encryption. The first new protocol reduced the computational effort of one party by roughly $50\%$. The second one showed how to achieve perfect security towards one party without additional costs, whereas the original version with encrypted inputs only achieved statistical security. However, the second protocol contained a mistake, leading to incorrect outputs in some cases. We show how to correct this mistake, without increasing its computational complexity.

### Machine-Learning Attacks on PolyPUFs, OB-PUFs, RPUFs, LHS-PUFs, and PUF-FSMs

Fri, 11/16/2018 - 04:34
A physically unclonable function (PUF) is a circuit of which the input–output behavior is designed to be sensitive to the random variations of its manufacturing process. This building block hence facilitates the authentication of any given device in a population of identically laid-out silicon chips, similar to the biometric authentication of a human. The focus and novelty of this work is the development of efficient impersonation attacks on the following five Arbiter PUF–based authentication protocols: (1) the so-called PolyPUF protocol of Konigsmark, Chen, and Wong, as published in the IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems in 2016, (2) the so-called OB-PUF protocol of Gao, Li, Ma, Al-Sarawi, Kavehei, Abbott, and Ranasinghe, as presented at the IEEE conference PerCom 2016, (3) the so-called RPUF protocol of Ye, Hu, and Li, as presented at the IEEE conference AsianHOST 2016, (4) the so-called LHS-PUF protocol of Idriss and Bayoumi, as presented at the IEEE conference RFID-TA 2017, and (5) the so-called PUF–FSM protocol of Gao, Ma, Al-Sarawi, Abbott, and Ranasinghe, as published in the IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems in 2018. The common flaw of all five designs is that the use of lightweight obfuscation logic provides insufficient protection against machine learning attacks.

### Scalable One-Time Pad --- From Information Theoretic Security to Information Conservational Security

Thu, 11/15/2018 - 16:33
Whereas it is widely deemed an impossible task to scale One-Time Pad (OTP) without sacrificing information theoretic security or network traffic, this paper presents a paradigm of Scalable OneTime Pad (S-OTP) ciphers based on information conservational computing/cryptography (ICC). Applicability of the new paradigm is analysed. It is shown that ICC enables data compression with quantumfuzzy collective precision to reduce key length to a minimum that used to be deemed impossible. Based on ICC, it is shown that, with a local IEEE binary64 standard computer associated with quantum key distribution (QKD), S-OTP enables secure transmission of long messages or large data sets with significant traffic reduction for post-quantum cryptography. Quantum crypto machinery is proposed. Some open topics are identified for further investigation

### SoK: Modular and Efficient Private Decision Tree Evaluation

Thu, 11/15/2018 - 12:22
Decision trees and random forests are widely used classifiers in machine learning. Service providers often host classification models in a cloud service and provide an interface for clients to use the model remotely. While the model is sensitive information of the server, the input query and prediction results are sensitive information of the client. This motivates the need for private decision tree evaluation, where the service provider does not learn the client's input and the client does not learn the model except for its size and the result. In this work, we identify the three phases of private decision tree evaluation protocols: feature selection, comparison, and path evaluation. We systematize protocols for each of these phases to identify the best available instantiations using the two main paradigms for secure computation: garbling techniques and homomorphic encryption. There is a natural tradeoff between runtime and communication considering these two paradigms: garbling techniques use fast symmetric-key operations but require a large amount of communication, while homomorphic encryption is computationally heavy but requires little communication. Our contributions are as follows: Firstly, we systematically review and analyse state-of-the-art protocols for the three phases of private decision tree evaluation. Our methodology allows us to identify novel combinations of these protocols that provide better tradeoffs than existing protocols. Thereafter, we empirically evaluate all combinations of these protocols by providing communication and runtime measures, and provide recommendations based on the identified concrete tradeoffs.

### MARVELlous: a STARK-Friendly Family of Cryptographic Primitives

Thu, 11/15/2018 - 12:09
The ZK-STARK technology, published by Ben-Sasson et al. in ePrint 2018/046 is hailed by many as being a viable, efficient solution to the scaling problem of cryptocurrencies. In essence, a ZK-STARK proof uses a Merkle-tree to compress the data that needs to be verified, thus greatly reduces the communication overhead between the prover and the verifier. We propose MARVELlous a family of cryptographic algorithms specifically designed for STARK efficiency. The family currently includes the block cipher Jarvis and the hash function Friday. The design of Jarvis is inspired by the design of Rijndael, better known as the AES. By doing so we create a cipher with similar properties to those of Rijndael which allows us to reuse the wide-trail strategy to argue the resistance of the design against differential and linear cryptanalysis and focus our efforts on resistance against algebraic attacks. Friday is a Merkle-Damgard based hash function instantiated with Jarvis as its compression function thus it inherits its security properties up to the birthday bound. Jarvis and Friday have been suggested to be used in the Ethereum protocol by Ben-Sasson in Ethereum's Devcon IV. In this paper, we instantiate versions of Jarvis offering 128, 160, 192 and 256-bit security (both state- and key-size) which are used to implement Friday. We warmly invite the community to study and assess the security of the designs.

### End-to-End Secure Mobile Group Messaging with Conversation Integrity and Deniability

Thu, 11/15/2018 - 12:05
In this paper, we describe Mobile CoWPI, a deployable, end-to-end secure mobile group messaging application with proofs of security. Mobile CoWPI allows dynamic groups of users to participate in, join, and leave private, authenticated conversations without requiring the participants to be simultaneously online or maintain reliable network connectivity. We identify the limitations of mobile messaging and how they affect conversational integrity and deniability. We define strong models of these security properties, prove that Mobile CoWPI satisfies these properties, and argue that no protocol that satisfies these properties can be more scalable than Mobile CoWPI. We also describe an implementation of Mobile CoWPI and show through experiments that it is suitable for use in real-world messaging conditions.

### On Finding Quantum Multi-collisions

Thu, 11/15/2018 - 12:04
A $k$-collision for a compressing hash function $H$ is a set of $k$ distinct inputs that all map to the same output. In this work, we show that for any constant $k$, $\Theta\left(N^{\frac{1}{2}(1-\frac{1}{2^k-1})}\right)$ quantum queries are both necessary and sufficient to achieve a $k$-collision with constant probability. This improves on both the best prior upper bound (Hosoyamada et al., ASIACRYPT 2017) and provides the first non-trivial lower bound, completely resolving the problem.

### CertLedger: A New PKI Model with Certificate Transparency Based on Blockchain

Wed, 11/14/2018 - 18:36
In conventional PKI, CAs are assumed to be fully trusted. However, in practice, CAs' absolute responsibility for providing trustworthiness caused major security and privacy issues. To prevent such issues, Google introduced the concept of Certificate Transparency (CT) in 2013. Later, several new PKI models (e.g., AKI, ARPKI, and DTKI) are proposed to reduce the level of trust to the CAs. However, all of these proposals are still vulnerable to split-world attacks if the adversary is capable of showing different views of the log to the targeted victims. In this paper, we propose a new PKI architecture with certificate transparency based on blockchain, what we called CertLedger, to eliminate the split-world attacks and to provide certificate/revocation transparency. All TLS certificates' validation, storage, and entire revocation process are conducted in CertLedger as well as Trusted CA certificate management. During a TLS connection, TLS clients get an efficient proof of existence of the certificate directly from its domain owners. Hence, privacy is now perfectly preserved by eliminating the traceability issue of OCSP servers. It also provides a unique, efficient, and trustworthy certificate validation process eliminating the conventional inadequate and incompatible certificate validation processes implemented by different software vendors. TLS clients in CertLedger also do not require to make certificate validation and store the trusted CA certificates anymore. We analyze the security and performance of CertLedger and provide a comparison with the previous proposals.

### Quantum Security Analysis of CSIDH and Ordinary Isogeny-based Schemes

Wed, 11/14/2018 - 13:14
CSIDH is a recent proposal by Castryck, Lange, Martindale, Panny and Renes for post-quantum non-interactive key-exchange, to be presented at ASIACRYPT~2018. It is similar in design to a scheme by Couveignes, Rostovtsev and Stolbunov, but it replaces ordinary elliptic curves by supersingular elliptic curves, in order to make significant gains in time and key lengths. Isogeny-based key-exchange on ordinary elliptic curves can be targeted by a quantum subexponential hidden shift algorithm found by Childs, Jao and Soukharev. Although CSIDH uses supersingular curves, it is analog to the case of ordinary curves, hence this algorithm applies. In the proposal, the authors suggest a choice of parameters that should ensure security against this. In this paper, we reassess these security parameters. Our result relies on two steps: first, we propose a new quantum algorithm for the hidden shift problem and analyze precisely its complexity. This reduces the number of group actions to compute w.r.t the authors' estimation; second, we show how to compute efficiently this group action. For example, we show that only $2^{35}$ quantum equivalents of a key-exchange are sufficient to break the 128-bit classical, 64-bit quantum security parameters proposed, instead of $2^{62}$. Finally, we extend our analysis to ordinary isogeny computations, and show that an instance proposed by De Feo, Kieffer and Smith (also accepted at ASIACRYPT 2018) and expected to offer $56$ bits of quantum security can be attacked in $2^{38}$ quantum evaluations of a key exchange.

### Reusable Authentication from the Iris

Wed, 11/14/2018 - 10:37
Biometrics exhibit noise between repeated readings. Due to the noise, devices store a plaintext template of the biometric. This stored template is an appetizing target for an attacker. Due to this risk, the primary use case for biometrics is mobile device authentication (templates are stored within the mobile device’s secure processor). There has been little adoption in client-server applications. Fuzzy extractors derive a stable cryptographic key from biometrics (Dodis et al., Eurocrypt 2004). In this work we describe an iris key derivation system with 32 bits of security even when multiple keys are derived from the same iris. We are fully aware that 32 bits of security is insufficient for a secure system. The goal of this work is to inspire researchers to design multi-factor authentication systems that uses our scheme as one component. Our system is based on repeated hashing which simplifies incorporating multiple factors (such as a password). Our starting point a recent fuzzy extractor due to Canetti et al.(Eurocrypt 2016). Achieving satisfactory parameters requires modifying and coupling the image processing and cryptographic algorithms. Our scheme is implemented in C and Python and is open-sourced. On a moderately powerful server, authentication usually completes within .30s.

### Key Prediction Security of Keyed Sponges

Wed, 11/14/2018 - 00:07
The keyed sponge is a well-accepted method for message authentication. It processes data at a certain rate by sequential evaluation of an underlying permutation. If the key size $k$ is smaller than the rate, currently known bounds are tight, but if it exceeds the rate, state of the art only dictates security up to $2^{k/2}$. We take closer inspection at the key prediction security of the sponge and close the remaining gap in the existing security analysis: we confirm key security up to close to $2^k$, regardless of the rate. The result impacts all applications of the keyed sponge and duplex that process at a rate smaller than the key size, including the STROBE protocol framework, as well as the related constructions such as HMAC-SHA-3 and the sandwich sponge.

### PanORAMa: Oblivious RAM with Logarithmic Overhead

Tue, 11/13/2018 - 10:47
We present PanORAMa, the first Oblivious RAM construction that achieves communication overhead $O(\log N \cdot \log \log N)$ for a 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 \emph{new oblivious hash table construction} with improved amortized $O\left( \log N + \text{poly}(\log \log \lambda) \right)$ communication overhead for security parameter $\lambda$ and $N = \text{poly}(\lambda)$, assuming its input is randomly shuffled; and a complementary \emph{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.