Last fall degree, HFE, and Weil descent attacks on ECDLP, by Ming-Deh A. Huang and Michiel Kosters and Sze Ling Yeo
Weil descent methods have recently been applied to attack the Hidden Field Equation (HFE) public key systems and solve the elliptic curve discrete logarithm problem (ECDLP) in small characteristic. However the claims of quasi-polynomial time attacks on the HFE systems and the subexponential time algorithm for the ECDLP depend on various heuristic assumptions.
In this paper we introduce the notion of the last fall degree of a polynomial system, which is independent of choice of a monomial order. We then develop complexity bounds on solving polynomial systems based on this last fall degree.
We prove that HFE systems have a small last fall degree, by showing that one can do division with remainder after Weil descent. This allows us to solve HFE systems unconditionally in polynomial time if the degree of the defining polynomial and the cardinality of the base field are fixed.
For the ECDLP over a finite field of characteristic 2, we provide computational evidence that raises doubt on the validity of the first fall degree assumption, which was widely adopted in earlier works and which promises sub-exponential algorithms for ECDLP. In addition, we construct a Weil descent system from a set of summation polynomials in which the first fall degree assumption is unlikely to hold. These examples suggest that greater care needs to be exercised when applying this heuristic assumption to arrive at complexity estimates.
These results taken together underscore the importance of rigorously bounding last fall degrees of Weil descent systems, which remains an interesting but challenging open problem.
Fair and Robust Multi-Party Computation using a Global Transaction Ledger, by Aggelos Kiayias and Hong-Sheng Zhou and Vassilis Zikas
Classical results on secure multi-party computation (MPC) imply that fully secure computation, including fairness (either all parties get output or none) and robustness (output delivery is guaranteed), is impossible unless a majority of the parties is honest. Recently, cryptocurrencies like Bitcoin where utilized to leverage the fairness loss in MPC against a dishonest majority. The idea is that when the protocol aborts in an unfair manner (i.e., after the adversary receives output) then honest parties get compensated by the adversarially controlled parties.
Our contribution is three-fold. First, we put forth a new formal model of secure MPC with compensation and we show how the introduction of suitable ledger and synchronization functionalities makes it possible to express completely such protocols using standard interactive Turing machines (ITM) circumventing the need for the use of extra features that are outside the standard model as in previous works. Second, our model, is expressed in the universal composition setting with global setup and is equipped with a composition theorem that enables the design of protocols that compose safely with each other and within larger environments where other protocols with compensation take place; a composition theorem for MPC protocols with compensation was not known before. Third, we introduce the first robust MPC protocol with compensation, i.e., an MPC protocol where not only fairness is guaranteed (via compensation) but additionally the protocol is guaranteed to deliver output to the parties that get engaged and therefore the adversary, after an initial round of deposits, is not even able to mount a denial of service attack without having to suffer a monetary penalty. Importantly, our robust MPC protocol requires only a constant number of (coin-transfer and communication) rounds.
Twist Insecurity, by Manfred Lochter, Andreas Wiemers
Several authors suggest that the use of twist secure Elliptic Curves automatically leads to secure implementations. We argue that even for twist secure
curves a point validation has to be performed.
We illustrate this with examples where the security of EC-algorithms is strongly degraded, even for twist secure curves.
We show that the usual blindig countermeasures against SCA are insufficient
(actually they introduce weaknesses)
if no point validation is performed,
or if an attacker has access to certain intermediate points.
In this case the overall security of the system is reduced to the length of the blinding parameter. We emphazise that our methods work even in the case of a very high identification error rate during the SCA-phase.
Tampering with the Delivery of Blocks and Transactions in Bitcoin, by Arthur Gervais and Hubert Ritzdorf and Ghassan O. Karame and Srdjan Capkun
Given the increasing adoption of Bitcoin, the number of transactions and the block sizes within the system are only expected to increase. To sustain its correct operation in spite of its ever-increasing use, Bitcoin implements a number of necessary optimizations and scalability measures. These measures limit the amount of information broadcast in the system to the minimum necessary.
In this paper, we show that current scalability measures adopted by Bitcoin come at odds with the security of the system. More specifically, we show that an adversary can exploit these measures in order to effectively delay the propagation of transactions and blocks to specific nodes--without causing a network partitioning in the system. We show that this allows the adversary to easily mount Denial-of-Service attacks, considerably increase its mining advantage in the network, and double-spend transactions in spite of the current countermeasures adopted by Bitcoin. Based on our results, we propose a number of countermeasures in order to enhance the security of Bitcoin without deteriorating its scalability.
PUA - Privacy and Unforgeability for Aggregation, by Iraklis Leontiadis and Kaoutar Elkhiyaoui and Refik Molva and Melek Önen
Existing work on data collection and analysis for aggregation is mainly
focused on confidentiality issues. That is, the untrusted Aggregator learns only
the aggregation result without divulging individual data inputs. In this paper we
extend the existing models with stronger security requirements. Apart from the
privacy requirements with respect to the individual inputs we ask for unforge-
ability for the aggregate result. We first define the new security requirements of
the model. We also instantiate a protocol for private and unforgeable aggregation
for a non-interactive multi-party environment. I.e, multiple unsynchronized users
owing to personal sensitive information without interacting with each other con-
tribute their values in a secure way: The Aggregator learns the result of a function
without learning individual values and moreover it constructs a proof that is for-
warded to a verifier that will let the latter be convinced for the correctness of the
computation. The verifier is restricted to not communicate with the users. Our
protocol is provably secure in the random oracle model.
Sanctum: Minimal RISC Extensions for Isolated Execution, by Victor Costan and Ilia Lebedev and Srinivas Devadas
Sanctum is a set of minimal extensions to a standard RISC architecture that offers strong provable isolation of software modules running concurrently and sharing resources. Sanctum is similar to
SGX in its API, but protects against an important class of additional software attacks, including cache timing and memory access pattern attacks. It does so via a principled approach to eliminating entire attack surfaces through isolation rather than plugging attack-specific privacy leaks.
Sanctum\'s hardware changes over a standard RISC architecture do not impact the cycle time, as they do not extend critical execution paths. Sanctum does not change any major CPU building block (e.g., ALU, MMU, cache), and only requires additional hardware at the interfaces between these building blocks corresponding to less than two percent chip area overhead. Over a set of benchmarks, Sanctum\'s worst observed overhead for isolated execution is 14.6% over an idealized insecure baseline.
A Framework for Identity-Based Encryption with Almost Tight Security, by Nuttapong Attrapadung, Goichiro Hanaoka, Shota Yamada
We show a framework for constructing identity-based encryption (IBE) schemes that are (almost) tightly secure in the multi-challenge and multi-instance setting. In particular, we formalize a new notion called broadcast encoding, analogously to encoding notions by Attrapadung (Eurocrypt \'14) and Wee (TCC \'14). We then show that it can be converted into such an IBE. By instantiating the framework using several encoding schemes (new or known ones), we obtain the following:
- We obtain (almost) tightly secure IBE in the multi-challenge, multi-instance setting, both in composite and prime-order groups. The latter resolves the open problem posed by Hofheinz et al (PKC \'15).
- We obtain the first (almost) tightly secure IBE with sub-linear size public parameters (master public keys). In particular, we can set the size of the public parameters to constant at the cost of longer ciphertexts. This gives a partial solution to the open problem
posed by Chen and Wee (Crypto \'13).
By applying (a variant of) the Canetti-Halevi-Katz transformation to our schemes, we obtain several CCA-secure PKE schemes with tight security in the multi-challenge, multi-instance setting. One of our schemes achieves very small ciphertext overhead, consisting of less than 12 group elements. This significantly improves the state-of-the-art construction by Libert et al.~(in ePrint Archive) which requires 47 group elements. Furthermore, by modifying one of our IBE schemes obtained above, we can make it anonymous. This gives the first anonymous IBE whose security is almost tightly shown in the multi-challenge setting.