Here you can see all recent updates to the IACR webpage. These updates are also available:

5
May
2017

ePrint Report
On Instance Compression, Schnorr/Guillou-Quisquater, and the Security of Classic Protocols for Unique Witness Relations
Yi Deng, Xuyang Song, Jingyue Yu, Yu Chen

We revisit the problem of whether the witness hiding property of classic 3-round public-coin proof systems for languages/distributions with unique witnesses are still witness hiding. Though
strong black-box impossibility results are known for them, we provide some less unexpected positive results on the witness hiding security of classic protocols:

1. We develop an embedding technique and prove that the witness hiding property of the standalone Schnorr protocol based on a weaker version of one-more like discrete logarithm (DL) assumption asserting that, for an arbitrary constant $\ell$, it is infeasible for a PPT algorithm to solve $l$ DL instances with being restricted to query the DL oracle only once. Similar result holds for the Guillou-Quisquater protocol.

This improves over the positive result of Bellare and Palacio in that when applying their technique to the standalone setting, the underlying assumption is stronger and required to hold only for $\ell=2$.

2. Following the framework of Harnik and Naor, we introduce the notion of tailored instance compression to capture the essence of the known one-more like assumptions, which provides new insight into the hardness of one-more DL/RSA problems and allows us to reveal some strong consequences of breaking our weaker version of one-more like assumption,including zero knowledge protocols for the AND-DL and AND-RSA languages with extremely efficient communication and non-trivial hash combiner for hash functions based on DL problem.

These consequences can be viewed as positive evidences for the security of Schnorr and Guillou-Quisquater protocols.

3. We observe that the previously known impossibility results on the witness hiding of public-coin protocols for unique witness relation make certain restriction on the reduction. By introducing an input-distribution-switching technique, we bypass these known impossibility results and prove that, for any hard language $L$, if a distribution $(\mathbb{X}, \mathbb{W})$ over unique witness relation $R_{L}$ has an indistinguishable counterpart distribution over some multiple witnesses relation, then any witness indistinguishable protocols (including ZAPs and all known 3-round public-coin protocols, such as Blum protocol and GMW protocol) are indeed witness hiding for the distribution $(\mathbb{X}, \mathbb{W})$.

We also show a wide range of cryptographic problems with unique witnesses satisfy the ``if condition'' of this result, and thus admit constant-round public-coin witness hiding proof system.

This is the first positive result on the witness-hiding property of the classic protocols for non-trivial unique witness relations.

1. We develop an embedding technique and prove that the witness hiding property of the standalone Schnorr protocol based on a weaker version of one-more like discrete logarithm (DL) assumption asserting that, for an arbitrary constant $\ell$, it is infeasible for a PPT algorithm to solve $l$ DL instances with being restricted to query the DL oracle only once. Similar result holds for the Guillou-Quisquater protocol.

This improves over the positive result of Bellare and Palacio in that when applying their technique to the standalone setting, the underlying assumption is stronger and required to hold only for $\ell=2$.

2. Following the framework of Harnik and Naor, we introduce the notion of tailored instance compression to capture the essence of the known one-more like assumptions, which provides new insight into the hardness of one-more DL/RSA problems and allows us to reveal some strong consequences of breaking our weaker version of one-more like assumption,including zero knowledge protocols for the AND-DL and AND-RSA languages with extremely efficient communication and non-trivial hash combiner for hash functions based on DL problem.

These consequences can be viewed as positive evidences for the security of Schnorr and Guillou-Quisquater protocols.

3. We observe that the previously known impossibility results on the witness hiding of public-coin protocols for unique witness relation make certain restriction on the reduction. By introducing an input-distribution-switching technique, we bypass these known impossibility results and prove that, for any hard language $L$, if a distribution $(\mathbb{X}, \mathbb{W})$ over unique witness relation $R_{L}$ has an indistinguishable counterpart distribution over some multiple witnesses relation, then any witness indistinguishable protocols (including ZAPs and all known 3-round public-coin protocols, such as Blum protocol and GMW protocol) are indeed witness hiding for the distribution $(\mathbb{X}, \mathbb{W})$.

We also show a wide range of cryptographic problems with unique witnesses satisfy the ``if condition'' of this result, and thus admit constant-round public-coin witness hiding proof system.

This is the first positive result on the witness-hiding property of the classic protocols for non-trivial unique witness relations.

4
May
2017

ePrint Report
Decentralized Blacklistable Anonymous Credentials with Reputation
Rupeng Yang, Man Ho Au, Qiuliang Xu, Zuoxia Yu

Blacklistable anonymous credential systems provide service providers with a way to authenticate users according to their historical behaviors, while guaranteeing that all users can access services in an anonymous and unlinkable manner, thus are potentially useful in practice. Traditionally, to protect services from illegal access, the credential issuer, which completes the registration with users, must be trusted by the service provider. However, in practice, this trust assumption is usually unsatisfied. Besides, to better evaluate users, it is desired to use blacklists, which record historical behaviors of users, of other service providers, but currently, this will threaten the security unless a strong trust assumption is made. Another potential security issue in current blacklistable anonymous credential systems is the blacklist gaming attack, where the service provider attempt to compromise the privacy of users via generating blacklist maliciously.

In this paper, we solve these problems and present the decentralized blacklistable anonymous credential system with reputation, which inherits nearly all features of the BLACR system presented in Au et.al. (NDSS'12). However, in our new system, no trusted party is needed to register users. Moreover, blacklists from other service providers can be used safely in the new system assuming a minimal trust assumption holds. Besides, the new system is also partially resilient to the blacklist gaming attack. Technically, the main approach to solving these problems is a novel use of the blockchain technique, which serve as a public append-only ledger and are used to store credentials and blacklists. To simplify the construction, we also present a generic framework for constructing our new system. The general framework can be instantiated from three different types of cryptographic systems, including the RSA system, the classical DL system, and the pairing based system, and all these three types of instantiations can be supported simultaneously in the framework. To demonstrate the practicability of our system, we also give a proof of concept implementation for the instantiation under the RSA system. The experiment results indicate that when authenticating with blacklists of reasonable size, our implementation can fulfill practical efficiency demands, and when authenticating with empty blacklists, it is more efficient than that of Garman et al. (NDSS'14), which presents a decentralized anonymous credential system without considering revocation.

In this paper, we solve these problems and present the decentralized blacklistable anonymous credential system with reputation, which inherits nearly all features of the BLACR system presented in Au et.al. (NDSS'12). However, in our new system, no trusted party is needed to register users. Moreover, blacklists from other service providers can be used safely in the new system assuming a minimal trust assumption holds. Besides, the new system is also partially resilient to the blacklist gaming attack. Technically, the main approach to solving these problems is a novel use of the blockchain technique, which serve as a public append-only ledger and are used to store credentials and blacklists. To simplify the construction, we also present a generic framework for constructing our new system. The general framework can be instantiated from three different types of cryptographic systems, including the RSA system, the classical DL system, and the pairing based system, and all these three types of instantiations can be supported simultaneously in the framework. To demonstrate the practicability of our system, we also give a proof of concept implementation for the instantiation under the RSA system. The experiment results indicate that when authenticating with blacklists of reasonable size, our implementation can fulfill practical efficiency demands, and when authenticating with empty blacklists, it is more efficient than that of Garman et al. (NDSS'14), which presents a decentralized anonymous credential system without considering revocation.

ePrint Report
Post-Quantum Key Exchange on ARMv8-A -- A New Hope for NEON made Simple
Silvan Streit, Fabrizio De Santis

NewHope and NewHope-Simple are two recently proposed post-quantum key exchange protocols based on the hardness of the Ring-LWE problem. Due to their high security margins and performance, there have been already discussions and proposals for integrating them into Internet standards, like TLS, and anonymity network protocols, like Tor. In this work, we present time-constant and vector-optimized implementations of NewHope and NewHope-Simple for ARMv8-A 64-bit processors which target high-speed applications. This architecture is implemented in a growing number of smart phone and tablet processors, and features powerful 128-bit SIMD operations provided by the NEON engine. In particular, we propose the use of three alternative modular reduction methods, which allow to better exploit NEON parallelism by avoiding larger data types during the Number Theoretic Transform (NTT) and remove the need to transform input coefficients into Montgomery domain during pointwise multiplications. The NEON vectorized NTT uses a 16-bit unsigned integer representation and executes in only 18, 909 clock cycles on an ARM Cortex-A53 core. Our implementation improves previous assembly-optimized results on ARM NEON platforms by a factor
of 3.4 and outperforms the C reference implementation on the same platform by a factor of 8.3. The total time spent on the key exchange was reduced by more than a factor of 3.5 for both protocols.

ePrint Report
Homomorphically Encrypted Arithmetic Operations over the Integer Ring
Chen Xu, Jingwei Chen, Wenyuan Wu, Yong Feng

Fully homomorphic encryption allows cloud servers to evaluate any computable functions for clients without revealing any information. It attracts much attention from both of the scientific community and
the industry since Gentry’s seminal scheme. Currently, the Brakerski-
Gentry-Vaikuntanathan scheme with its optimizations is one of the most
potentially practical schemes and has been implemented in a homomorphic encryption C++ library HElib. HElib supplies friendly interfaces for
arithmetic operations of polynomials over finite fields. Based on HElib, Chen and Gong (2015) implemented arithmetic over encrypted integers. In this paper, we revisit the HElib-based implementation of homomorphically arithmetic operations on encrypted integers. Due to several optimizations and more suitable arithmetic circuits for homomorphic encryption evaluation, our implementation is able to homomorphically evaluate 64-bit addition/subtraction and 16-bit multiplication for encrypted integers without bootstrapping. Experiments show that our implementation outperforms Chen and Gong’s significantly.

ePrint Report
Four Round Secure Computation without Setup
Zvika Brakerski, Shai Halevi, Antigoni Polychroniadou

We construct a 4-round multi-party computation protocol for any functionality, which is secure against a malicious adversary. Our protocol relies on the sub-exponential hardness of the Learning with Errors (LWE) problem with polynomial noise ratio, and on the existence of adaptively secure commitments.
Our round complexity matches a lower bound of Garg et al. (EUROCRYPT '16), and outperforms the state of the art of 6-rounds based on similar assumptions to ours, and 5-rounds relying on indistinguishability obfuscation.

Our construction takes after the multi-key FHE approach of Mukherjee-Wichs (EUROCRYPT '16) who constructed a 2-round semi-malicious protocol from LWE in the common random string (CRS) model. We show how to use a preliminary round of communication to replace the CRS, thus achieving 3-round semi-malicious security without setup. Adaptive commitments and zero-knowledge proofs are then used to compile the protocol into the fully malicious setting.

Our construction takes after the multi-key FHE approach of Mukherjee-Wichs (EUROCRYPT '16) who constructed a 2-round semi-malicious protocol from LWE in the common random string (CRS) model. We show how to use a preliminary round of communication to replace the CRS, thus achieving 3-round semi-malicious security without setup. Adaptive commitments and zero-knowledge proofs are then used to compile the protocol into the fully malicious setting.

Yao's garbled circuit construction is a central cryptographic tool with numerous applications. In this tutorial, we study garbled circuits from a foundational point of view under the framework of randomized encoding (RE) of Functions. We review old and new constructions of REs, present some lower-bounds, and describe some applications. We will also discuss new directions and open problems in the foundations of REs.

This is a survey that appeared in a book of surveys in honor of Oded Goldreich's 60th birthday.

This is a survey that appeared in a book of surveys in honor of Oded Goldreich's 60th birthday.

ePrint Report
Time-Memory-Data Tradeoff Attacks against Small-State Stream Ciphers
Matthias Hamann, Matthias Krause, Willi Meier, Bin Zhang

Time-memory-data (TMD) tradeoff attacks limit the security level of many classical stream ciphers (like $E_0$, A5/1, Trivium, Grain) to $\frac{1}{2}n$, where $n$ denotes the inner state length of the underlying keystream generator. This implies that to withstand TMD tradeoff attacks, the state size should be at least double the key size. In 2015, Armknecht and Mikhalev introduced a new line of research, which pursues the goal of reducing the inner state size of lightweight stream ciphers below this boundary by deploying a key-dependent state update function in a Grain-like stream cipher. Although their design Sprout was broken soon after publication, it has raised interest in the design principle, and a number of related ciphers have been suggested since, including Plantlet, a follow-up of Sprout, and the cipher Fruit.

In this paper, existing TMD tradeoff attacks are revisited, and new insights on distinguishers and key recovery related to small-state stream ciphers are derived. A particular result is the transfer of a generic distinguishing attack suggested in 2007 by Englund, Hell, and Johansson to this new class of lightweight ciphers. Our analysis shows that the initial hope of achieving full security against TMD tradeoff attacks by continuously using the secret key has failed. In particular, we demonstrate that there are generic distinguishing attacks against Plantlet and Fruit with complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, we are able to come up with a new design idea for small-state stream ciphers which might allow to finally achieve full security against TMD tradeoff attacks.

Another contribution of this paper is the first key recovery attack against the most recent version of Fruit. We show that there are at least $2^{64}$ weak keys, each of which does not provide 80-bit security as promised by designers. This new attack against Fruit, together with previous attacks against Sprout, raises the question whether a more complicated key schedule than the basic one used in Plantlet is actually beneficial for the security of such ciphers.

In this paper, existing TMD tradeoff attacks are revisited, and new insights on distinguishers and key recovery related to small-state stream ciphers are derived. A particular result is the transfer of a generic distinguishing attack suggested in 2007 by Englund, Hell, and Johansson to this new class of lightweight ciphers. Our analysis shows that the initial hope of achieving full security against TMD tradeoff attacks by continuously using the secret key has failed. In particular, we demonstrate that there are generic distinguishing attacks against Plantlet and Fruit with complexity significantly smaller than that of exhaustive key search. However, by studying the assumptions underlying the applicability of these attacks, we are able to come up with a new design idea for small-state stream ciphers which might allow to finally achieve full security against TMD tradeoff attacks.

Another contribution of this paper is the first key recovery attack against the most recent version of Fruit. We show that there are at least $2^{64}$ weak keys, each of which does not provide 80-bit security as promised by designers. This new attack against Fruit, together with previous attacks against Sprout, raises the question whether a more complicated key schedule than the basic one used in Plantlet is actually beneficial for the security of such ciphers.

We call a simple abelian variety over $\mathbb{F}_p$ super-isolated if its ($\mathbb{F}_p$-rational) isogeny class contains no other varieties. The motivation for considering these varieties comes from concerns about isogeny based attacks on the discrete log problem. We heuristically estimate that the number of super-isolated elliptic curves over $\mathbb{F}_p$ with prime order and $p \leq N$, is roughly $\tilde{\Theta}(\sqrt{N})$. In contrast, we prove that there are only 2 super-isolated surfaces of cryptographic size and near-prime order.

ePrint Report
A General Degenerate Grouping Power Attack with Specific Application to SIMON and SPECK
Steven Cavanaugh

A Degenerate Grouping Power Attack (DGPA) is a type of Partitioning Power Analysis (PPA) used to extract secret keys from the power sidechannel signal of an encryption algorithm running on a device along with some known and varying information such as the associated plaintext or ciphertext associated with each encryption. The DGPA is applied to SIMON and SPECK implementations on MSP430, PIC16F, and Spartan 6 platforms in this work. While keys are successfully recovered from unprotected implementations, guidance is given on a minimum number of rounds, $d$, to perform per clock cycle in FPGAs and ASICs as to mitigate against such attacks for a deployment dependent maximum quantity of data which is to be encrypted with a given key.
On the Spartan 6, full key recovery of SIMON 64/128 $d\leq4$ and SPECK 64/128 $d\leq3$ is trivially achieved in seconds with no more than one million random plaintexts, requiring the use of larger $d$ for most implementations.
The amount of work to recover a key as a function of the amount of collected data encrypted with that key is explored.
To ensure security when performing most modes of block cipher operation with an algorithm having block size $2n$, a particular key should be used to perform no more than $2^n$ encryptions.
A feasible key recovery requiring less than 80-bits of work and data from less than $2^{32}$ encryptions is excluded for SIMON 64/128 implementations having $d\geq 9$ and for SPECK 64/128 implementations having $d\geq5$.
The DGPA attack method is demonstrated to succeed against a limited data set consisting of one power sample per device clock cycle against a specifically targeted instruction. This provides a basis for a low power field deployed power side channel signal capture hardware for embedded key recovery and exfiltration.

1
May
2017

In quantum cryptography, a one-way permutation is a bounded unitary operator $U: H \mapsto H$ on a Hilbert space $H$ that is easy to compute on every input, but hard to invert given the image of a random input. Levin [Probl. Inf. Transm., vol. 39 (1): 92-103 (2003)] has conjectured that the unitary transformation $g(a,x) = (a,f(x)+ax)$, where $f$ is any length-preserving function and $a,x \in GF_{2^{||x||}}$, is an information-theoretically secure operator within a polynomial factor. Here, we show that Levin’s oneway permutation is provably secure because its output values are four maximally entangled two-qubit states, and whose probability of factoring them approaches zero faster than the multiplicative inverse of any positive polynomial $poly(x)$ over the Boolean ring of all subsets of $x$. Our results demonstrate through well-known theorems that existence of classical one-way functions implies existence of a universal quantum one-way permutation that cannot be inverted in subexponential time in the worst case.

ePrint Report
Watermarking Cryptographic Functionalities from Standard Lattice Assumptions
Sam Kim, David J. Wu

A software watermarking scheme allows one to embed a “mark” into a program without significantly altering the behavior of the program. Moreover, it should be difficult to remove the watermark without destroying the functionality of the program. Recently, Cohen et al. (STOC 2016) and Boneh et al. (PKC 2017) showed how to watermark cryptographic functions such as PRFs using the full power of general-purpose indistinguishability obfuscation. Notably, in their constructions, the watermark remains intact even against arbitrary removal strategies. A natural question is whether we can build watermarking schemes from standard assumptions that achieve this strong mark-unremovability property.

We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.

We give the first construction of a watermarkable family of PRFs that satisfy this strong mark-unremovability property from standard lattice assumptions (namely, the learning with errors (LWE) and the one-dimensional short integer solution (SIS) problems). As part of our construction, we introduce a new cryptographic primitive called a translucent PRF. Next, we give a concrete construction of a translucent PRF family from standard lattice assumptions. Finally, we show that using our new lattice-based translucent PRFs, we obtain the first watermarkable family of PRFs with strong unremovability against arbitrary strategies from standard assumptions.

We present the first fault attack on cryptosystems based on supersingular isogenies.
During the computation of the auxiliary points, the attack aims to change the base point to a random point on the curve via a fault injection. We will show that this would reveal the secret isogeny with one successful perturbation with high probability. We will exhibit the attack by placing it against signature schemes and key-exchange protocols with validations in place.
Our paper therefore demonstrates the need to incorporate checks in implementations of the cryptosystem.

ePrint Report
Faster Secure Multi-Party Computation of AES and DES Using Lookup Tables
Marcel Keller, Emmanuela Orsini, Dragos Rotaru, Peter Scholl, Eduardo Soria-Vazquez, Srinivas Vivek

We present an actively secure protocol for secure multi-party computation based on lookup tables, by extending the recent, two-party `TinyTable' protocol of Damgard et al. (ePrint 2016).
Like TinyTable, an attractive feature of our protocol is a very fast and simple online evaluation phase. We also give a new method for efficiently implementing the preprocessing material required for the online phase using arithmetic circuits over characteristic two fields. This improves over the suggested method from TinyTable by at least a factor of 50.

As an application of our protocol, we consider secure computation of the Triple DES and the AES block ciphers, computing the S-boxes via lookup tables. Additionally, we adapt a technique for evaluating (Triple) DES based on a polynomial representation of its S-boxes that was recently proposed in the side-channel countermeasures community. We compare the above two approaches with an implementation. The table lookup method leads to a very fast online time of over 230,000 blocks per second for AES and 45,000 for Triple DES. The preprocessing cost is not much more than previous methods that have a much slower online time.

As an application of our protocol, we consider secure computation of the Triple DES and the AES block ciphers, computing the S-boxes via lookup tables. Additionally, we adapt a technique for evaluating (Triple) DES based on a polynomial representation of its S-boxes that was recently proposed in the side-channel countermeasures community. We compare the above two approaches with an implementation. The table lookup method leads to a very fast online time of over 230,000 blocks per second for AES and 45,000 for Triple DES. The preprocessing cost is not much more than previous methods that have a much slower online time.

ePrint Report
Privacy-Preserving Multi-Party Bartering Secure Against Active Adversaries
Stefan Wüller, Ulrike Meyer, Susanne Wetzel

A majority of electronic bartering transactions is carried out via online platforms. Typically, these platforms require users to disclose sensitive information about their trade capabilities which might restrict their room for negotiation. It is in this context that we propose a novel decentralized and privacy-preserving bartering protocol for multiple parties that offers the same privacy guarantees as provided by traditional bartering and by cash payments. The proposed protocol is even secure against an active attacker who controls a majority of colluding parties.

ePrint Report
Determining the Minimum Degree of an S-box
P. R. Mishra, Sumanta Sarkar, Indivar Gupta

S-boxes are important building blocks in block ciphers. For secure design one should not choose an S-box that has low degree. In this work we consider minimum degree of an S-box which is the minimum value of the degree of the nonzero component functions of the S-box. For an S-box $F : {F_2}^n \rightarrow {F_2}^m$, there are $2^m - 1$ nonzero component functions, we show that there is a better way to determine the minimum degree of an S-box which does not require to check all the $2^m - 1$ component functions. To the best of our knowledge, this is the best algorithm for determining the minimum degree of an S-box in the literature.

Blockchain is being praised as a technological innovation which allows to revolutionize how society trades and interacts. This reputation is in particular attributable to its properties of allowing mutually mistrusting entities to exchange financial value and interact without relying on a trusted third party. A blockchain moreover provides an integrity protected data storage and allows to provide process transparency.

In this article we critically analyze whether a blockchain is indeed the appropriate technical solution for a particular application scenario. We differentiate between permissionless (e.g., Bitcoin/Ethereum) and permissioned (e.g. Hyperledger/Corda) blockchains and contrast their properties to those of a centrally managed database. We provide a structured methodology to determine the appropriate technical solution to solve a particular application problem. Given our methodology, we analyze in depth three use cases --- Supply Chain Management, Interbank and International Payments, and Decentralized Autonomous Organizations and conclude the article with an outlook for further opportunities.

In this article we critically analyze whether a blockchain is indeed the appropriate technical solution for a particular application scenario. We differentiate between permissionless (e.g., Bitcoin/Ethereum) and permissioned (e.g. Hyperledger/Corda) blockchains and contrast their properties to those of a centrally managed database. We provide a structured methodology to determine the appropriate technical solution to solve a particular application problem. Given our methodology, we analyze in depth three use cases --- Supply Chain Management, Interbank and International Payments, and Decentralized Autonomous Organizations and conclude the article with an outlook for further opportunities.

ePrint Report
Loop-abort faults on supersingular isogeny cryptosystems
Alexandre Gélin, Benjamin Wesolowski

Cryptographic schemes based on supersingular isogenies have become an active area of research in the field of post-quantum cryptography. We investigate the resistance of these cryptosystems to fault injection attacks. It appears that the iterative structure of the secret isogeny computation renders these schemes vulnerable to loop-abort attacks. Loop-abort faults allow to perform a full key recovery, bypassing all the previously introduced validation methods. Therefore implementing additional countermeasures seems unavoidable for applications where physical attacks are relevant.

ePrint Report
Fully Dynamic Multi Target Homomorphic Attribute-Based Encryption
Ryo Hiromasa, Yutaka Kawai

We propose multi target homomorphic attribute-based encryption (MT-HABE) with fully dynamic homomorphic evaluation: it can take as input arbitrary additional ciphertexts during homomorphic computation. In the previous MT-HABE of Brakerski et al. (TCC 2016-B), the output of homomorphic computation, which is related to a policy set, cannot be computed with a fresh ciphertext whose attribute does not satisfy any policy in the set. This is because the underlying multi-key fully homomorphic encryption (MKFHE) is single-hop: some keys are related to the output of homomorphic computation, which cannot be combined with ciphertexts encrypted under other keys. To implement fully dynamic homomorphic evaluations, we construct MT-HABE from the multi-hop MKFHE proposed by Peikert and Shiehian (TCC 2016-B).

28
April
2017

ePrint Report
A crossbred algorithm for solving Boolean polynomial systems
Antoine Joux, Vanessa Vitse

We consider the problem of solving multivariate systems of Boolean polynomial equations: starting from a system of $m$ polynomials of degree at most $d$ in $n$ variables, we want to find its solutions over $\F_2$. Except for $d=1$, the problem is known to be NP-hard, and its hardness has been used to create public cryptosystems; this motivates the search for faster algorithms to solve this problem. After reviewing the state of the art, we describe a new algorithm and show that it outperforms previously known methods in a wide range of relevant parameters. In particular, the first named author has been able to solve all the Fukuoka Type~I MQ challenges, culminating with the resolution of a system of 148 quadratic equations in 74 variables in less than a day (and with a lot of luck).

ePrint Report
On the Efficient Construction of Lightweight Orthogonal MDS Matrices
Lijing Zhou, Licheng Wang, Yiru Sun

In present paper, we mainly investigate the problem of efficiently constructing lightweight orthogonal MDS matrices over the matrix polynomial residue ring. Surprisingly, this problem did not receive much attention previously. We propose a necessary-and-sufficient condition, which is more efficient than the traditional method, about judging whether an orthogonal matrix is MDS. Although it has been proved that the circulant orthogonal MDS matrix does not exist over the finite field, we discuss anew this problem and get a new method to judge which polynomial residue ring can be used to construct the circulant orthogonal MDS matrix. According to this method, the minimum polynomials of non-singular matrices over $\FF$ are factorized. With these results of factorizations, finally, we propose an extremely efficient algorithm for constructing lightweight circulant orthogonal MDS matrices. By using this algorithm, a lot of new lightweight circulant orthogonal MDS matrices are constructed for the first time.

ePrint Report
Too Simple to be UC-Secure: On the UC-Insecurity of the ``Simplest Protocol for Oblivious Transfer'' of Chou and Orlandi
Ziya Alper Genç, Vincenzo Iovino, Alfredo Rial

In 2015, Chou and Orlandi presented an oblivious transfer protocol that already drew a lot of attention both from theorists and practitioners due to its extreme simplicity and high efficiency. Chou and Orlandi claimed that their protocol is UC-secure under dynamic corruptions, which is a very strong security guarantee. Unfortunately, in this work we point out a serious flaw in their security proof. Moreover, we show that their protocol cannot be proven UC-secure even under static corruptions unless some computational assumption, which we conjecture to hold, is false.

ePrint Report
Enforcing Input Correctness via Certification in Garbled Circuit Evaluation
Yihua Zhang, Marina Blanton, Fattaneh Bayatbabolghani

Secure multi-party computation allows a number of participants to securely
evaluate a function on their private inputs and has a growing number of
applications. Two standard adversarial models that treat the participants as
semi-honest or malicious, respectively, are normally considered for showing
security of constructions in this framework. In this work, we go beyond the
standard security model in the presence of malicious participants and treat
the problem of enforcing correct inputs to be entered into the computation.
We achieve this by having a certification authority certify user's
information, which is consequently used in secure two-party computation
based on garbled circuit evaluation. The focus of this work on enforcing
correctness of garbler's inputs via certification, as prior work already
allows one to achieve this goal for circuit evaluator's input. Thus, in
this work, we put forward a novel approach for certifying user's input and
tying certification to garbler's input used during secure function
evaluation based on garbled circuits. Our construction achieves notable
performance of adding only one (standard) signature verification and
$O(n\rho)$ symmetric key/hash operations to the cost of garbled circuit
evaluation in the malicious model via cut-and-choose, in which $\rho$
circuits are garbled and $n$ is the length of the garbler's input in bits.
Security of our construction is rigorously proved in the standard model.

This work considers the problem of constructing efficient MDS matrices over the field $\F_{2^m}$. Efficiency is measured by the metric XOR count which was introduced by Khoo et al. in CHES 2014. Recently Sarkar and Syed (ToSC Vol. 1, 2016) have shown the existence of $4\times 4$ Toeplitz MDS matrices with optimal XOR counts. In this paper, we present some characterizations of Toeplitz matrices in light of MDS property. Our study leads to improving the known bounds of XOR counts of $8\times 8$ MDS matrices by obtaining Toeplitz MDS matrices with lower XOR counts over $\F_{2^4}$ and $\F_{2^8}$.

ePrint Report
Forking-Free Hybrid Consensus with Generalized Proof-of-Activity
Shuyang Tang, Zhiqiang Liu, Sherman S. M. Chow, Zhen Liu, Yu Long, Shengli Liu

Bitcoin and its underlying blockchain mechanism have been attracting much attention. One of their core innovations, Proof-of-Work (PoW), is notoriously inefficient and potentially motivates a centralization of computing power, which defeats the original aim of decentralization. Proof-of-Stake (PoS) is later proposed to replace PoW. However, both PoW and PoS have different inherent advantages and disadvantages, so does Proof-of-Activity (PoA) of Bentov et al. (SIGMETRICS 2014) which only offers limited combinations of two mechanisms. On the other hand, the hybrid consensus protocol of Pass
and Shi (ePrint 2016/917) aims to improve the efficiency by dynamically maintaining a rotating committee. Yet, there are unsatisfactory issues including selfish mining and fair committee election.
In this paper, we firstly devise a generalized variant of PoW. After that, we leverage our newly proposed generalized PoW to construct forking-free hybrid consensus, which addresses issues faced by a regular hybrid consensus mechanism. We further combine our forking-free hybrid consensus mechanism with PoS for a generalization of PoA. Compared with PoA, our generalized PoA improves the efficiency and provides more flexible combinations of PoW and PoS, resulting in a more powerful and applicable consensus scheme.

We present a cipher that represents a novel strategy: replacing algorithmic complexity with computational simplicity while generating cryptographic efficacy through large as desired quantities of randomness. The BitFlip cipher allows its user to defend herself with credibly appraised mathematical intractability, well-hinged on solid combinatorics. This is the situation when the amount of randomness is small relative to the accumulated amount of processed plaintext. Deploying more randomness, BitFlip will frustrate its cryptanalyst with terminal equivocation among two or more plausible message candidates. This equivocation defense can be increased by simply increasing the amount of deployed randomness, coming at-will close to Vernam’s perfect secrecy. BitFlip is structured as a super polyalphabetic cipher where a letter comprised of 2n bits is pointed-to by any 2n bits string with a Hamming distance of n from it. When a passed 2n bits string is found to have no n-valued Hamming distance from any letter in the reader’s alphabet, it is regarded as null. This allows for co-encryption of several messages each over its respective alphabet; thereby offering a powerful equivocation defense because the ciphertext does not indicate which alphabet the intended reader is using. BitFlip becomes increasingly timely and practical, exploiting the advent of high quality non-algorithmic randomness, as well as the effect of Moore’s law on the cost of handling large amounts of memory. BitFlip is a natural fit for what fast emerges as the biggest customer of cryptography: the Internet of Things

We survey the computational foundations for public-key cryptography. We discuss the computational assumptions that have been used as bases for public-key encryption schemes, and the types of evidence we have for the veracity of these assumptions.

This survey/tutorial was published in the book "Tutorials on the Foundations of Cryptography", dedicated to Oded Goldreich on his 60th birthday.

This survey/tutorial was published in the book "Tutorials on the Foundations of Cryptography", dedicated to Oded Goldreich on his 60th birthday.

26
April
2017

ePrint Report
Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols
Ran Cohen, Sandro Coretti, Juan Garay, Vassilis Zikas

An important benchmark for multi-party computation protocols (MPC) is their round complexity. For several important MPC tasks, (tight) lower bounds on the round complexity are known. However, for some of these tasks, such as broadcast, the lower bounds can be circumvented when the termination round of every party is not a priori known, and simultaneous termination is not guaranteed. Protocols with this property are called \emph{probabilistic-termination (PT)} protocols.

Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of $m$ protocols with constant expected round complexity might take $O(\log m)$ rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing '03) developed a technique for parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al.(CRYPTO '16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is "privacy free," and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity.

In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, secure against a dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying \emph{protocols}. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the \emph{functionalities} realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol.

To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.

Running PT protocols in parallel affects the round complexity of the resulting protocol in somewhat unexpected ways. For instance, an execution of $m$ protocols with constant expected round complexity might take $O(\log m)$ rounds to complete. In a seminal work, Ben-Or and El-Yaniv (Distributed Computing '03) developed a technique for parallel execution of arbitrarily many broadcast protocols, while preserving expected round complexity. More recently, Cohen et al.(CRYPTO '16) devised a framework for universal composition of PT protocols, and provided the first composable parallel-broadcast protocol with a simulation-based proof. These constructions crucially rely on the fact that broadcast is "privacy free," and do not generalize to arbitrary protocols in a straightforward way. This raises the question of whether it is possible to execute arbitrary PT protocols in parallel, without increasing the round complexity.

In this paper we tackle this question and provide both feasibility and infeasibility results. We construct a round-preserving protocol compiler, secure against a dishonest minority of actively corrupted parties, that compiles arbitrary protocols into a protocol realizing their parallel composition, while having a black-box access to the underlying \emph{protocols}. Furthermore, we prove that the same cannot be achieved, using known techniques, given only black-box access to the \emph{functionalities} realized by the protocols, unless merely security against semi-honest corruptions is required, for which case we provide a protocol.

To prove our results, we utilize the language and results by Cohen et al., which we extend to capture parallel composition and reactive functionalities, and to handle the case of an honest majority.

ePrint Report
TOPPSS: Cost-minimal Password-Protected Secret Sharing based on Threshold OPRF
Stanislaw Jarecki, Aggelos Kiayias, Hugo Krawczyk, Jiayu Xu

We present TOPPSS, the most efficient Password-Protected Secret Sharing (PPSS) scheme to date. A (t; n)-threshold PPSS, introduced
by Bagherzandi et al, allows a user to share a secret among n servers so that the secret can later be reconstructed by the user from any subset of t+1 servers with the sole knowledge of a password. It is guaranteed that any coalition of up to t corrupt servers learns nothing about the secret (or the password). In addition to providing strong protection to secrets stored online, PPSS schemes give rise to efficient Threshold PAKE (T-PAKE) protocols that armor single-server password authentication against the inherent vulnerability to offline dictionary attacks in
case of server compromise.

TOPPSS is password-only, i.e. it does not rely on public keys in reconstruction, and enjoys remarkable efficiency: A single communication round, a single exponentiation per server and just two exponentiations per client regardless of the number of servers. TOPPSS satises threshold security under the (Gap) One-More Diffie-Hellman (OMDH) assumption in the random-oracle model as in several prior efficient realizations of PPSS/TPAKE. Moreover, we show that TOPPSS realizes the Universally Composable PPSS notion of Jarecki et al under a generalization of OMDH, the Threshold One-More Diffie-Hellman (T-OMDH) assumption. We show that the T-OMDH and OMDH assumptions are both hard in the generic group model.

The key technical tool we introduce is a universally composable Threshold Oblivious PRF which is of independent interest and applicability.

TOPPSS is password-only, i.e. it does not rely on public keys in reconstruction, and enjoys remarkable efficiency: A single communication round, a single exponentiation per server and just two exponentiations per client regardless of the number of servers. TOPPSS satises threshold security under the (Gap) One-More Diffie-Hellman (OMDH) assumption in the random-oracle model as in several prior efficient realizations of PPSS/TPAKE. Moreover, we show that TOPPSS realizes the Universally Composable PPSS notion of Jarecki et al under a generalization of OMDH, the Threshold One-More Diffie-Hellman (T-OMDH) assumption. We show that the T-OMDH and OMDH assumptions are both hard in the generic group model.

The key technical tool we introduce is a universally composable Threshold Oblivious PRF which is of independent interest and applicability.

Since its introduction the UC framework by Canetti has received a lot of attention. A
contributing factor to its popularity is that it allows to capture a large number of common cryptographic primitives using ideal functionalities and thus can be used to give modular proofs for many cryptographic protocols. However, an important member of the cryptographic family has not yet been captured by an ideal functionality, namely the zero-knowledge proof of membership. We give the first formulation of a UC zero-knowledge proof of membership and show that it is closely related to the notions of straight-line zero-knowledge and simulation soundness.

ePrint Report
Indistinguishability Obfuscation for All Circuits from Secret-Key Functional Encryption
Fuyuki Kitagawa, Ryo Nishimaki, Keisuke Tanaka

We show that indistinguishability obfuscation (IO) for all circuits can be constructed solely from secret-key functional encryption (SKFE). In the construction, SKFE need to be able to issue a-priori unbounded number of functional keys, that is, collusion-resistant.

Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE. Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE is constructed from ordinary SKFE.

In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is also sufficient for constructing IO.

Our strategy is to replace public-key functional encryption (PKFE) in the construction of IO proposed by Bitansky and Vaikuntanathan (FOCS 2015) with puncturable SKFE. Bitansky and Vaikuntanathan introduced the notion of puncturable SKFE and observed that the strategy works. However, it has not been clear whether we can construct puncturable SKFE without assuming PKFE. In particular, it has not been known whether puncturable SKFE is constructed from ordinary SKFE.

In this work, we show that a relaxed variant of puncturable SKFE can be constructed from collusion-resistant SKFE. Moreover, we show that the relaxed variant of puncturable SKFE is also sufficient for constructing IO.