*15:17* [Pub][ePrint]
On Generalized First Fall Degree Assumptions, by Yun-Ju Huang and Christophe Petit and Naoyuki Shinohara and Tsuyoshi Takagi
The first fall degree assumption provides a complexity approximation of Gr\\\"obner basis algorithms when the degree of regularity of a polynomial system cannot be precisely evaluated. Most importantly, this assumption was recently used by Petit and Quisquater\'s to conjecture that the elliptic curve discrete logarithm problem can be solved in subexponential time for binary fields (binary ECDLP). The validity of the assumption may however depend on the systems in play.In this paper, we theoretically and experimentally study the first fall degree assumption for a class of polynomial systems including those considered in Petit and Quisquater\'s analysis. In some cases, we show that the first fall degree assumption seems to hold and we deduce complexity improvements on previous binary ECDLP algorithms. On the other hand, we also show that the assumption is unlikely to hold in other cases where it would have very unexpected consequences.

Our results shed light on a Gr\\\"obner basis assumption with major consequences on several cryptanalysis problems, including binary ECDLP.

*15:17* [Pub][ePrint]
Higher-Order Side Channel Security and Mask Refreshing, by Jean-Sebastien Coron and Emmanuel Prouff and Matthieu Rivain and Thomas Roche
Masking is a widely used countermeasure to protect block cipher implementations against side-channel attacks. The principle is to split every sensitive intermediate variable occurring in the computation into d + 1 shares, where d is called the masking order and plays therole of a security parameter. A masked implementation is then said to achieve dth-order security if any set of d (or less) intermediate variables does not reveal key-dependent information. At CHES 2010, Rivain and Prouff have proposed a higher-order masking scheme for AES that works for any arbitrary order d. This scheme, and its subsequent extensions, are based on an improved version of the shared multiplication processing published by Ishai et al. at CRYPTO 2003. This improvement enables better memory/timing performances but its security relies on the refreshing of the masks at some points in the algorithm. In this paper, we show that the method proposed at CHES 2010 to do such mask refreshing introduces a security flaw in the overall masking scheme. Specically, we show that it is vulnerable to an attack of order d/2 + 1 whereas the scheme is supposed to achieve dth-order security. After exhibiting and analyzing the flaw, we propose a new solution which avoids the use of mask refreshing, and we prove its security. We also provide some implementation trick that makes our proposed solution, not only secure, but also faster than the original scheme.

*15:17* [Pub][ePrint]
Achieving Differential Privacy with New Imperfect Randomness, by Yanqing Yao and Zhoujun Li
We revisit the question of achieving differential privacy with realistic imperfect randomness. In the design of differentially private mechanisms, it\'s usually assumed that uniformly random source is available. However, in many situations it seems unrealistic, and one must deal with various imperfect random sources. Dodis et al. (CRYPTO\'12) proposed that differential privacy can be achieved with Santha-Vazirani(SV) source via adding a stronger property called SV-consistent sampling and left open the question if differential privacy is possible with more realistic(i.e., less structured) sources than SV source. A new source, called

Bias-Control Limited (BCL) source, introduced by Dodis (ICALP\'01),

as a generalization of the SV source and sequential bit-fixing source, is

more realistic. Unfortunately, if we nationally expand SV-consistent sampling to the BCL source, the expansion is hopeless to achieve differential privacy. One main reason is that SV-consistent sampling requires \"consecutive\"strings, while some strings can\'t be generated from \"non-trivial\"BCL source.

Motivated by this question, we introduce a new appealing property, called

compact BCL-consistent sampling, the degeneration of which is different

from SV-consistent sampling proposed by Dodis et al. We prove that if

the mechanism based on the BCL source satisfies this property, then it\'s

differentially private. Even if the BCL source is degenerated into the SV source,our proof is much more intuitive and simpler than that of Dodis

et al. Further, we construct explicit mechanisms using a new truncation

technique as well as arithmetic coding. We also propose its concrete

results for differential privacy and accuracy. While the results of [DY14]imply that if there exist differentially private mechanisms for imperfect randomness, then some parameters should have some constraints, ours show explicit construction of such mechanisms whose parameters match

the prior constraints.

*15:17* [Pub][ePrint]
Computationally binding quantum commitments, by Dominique Unruh
We present a new definition of computationally binding commitmentschemes in the quantum setting, which we call \"collapse-binding\". The

definition applies to string commitments, composes in parallel, and

works well with rewinding-based proofs. We give simple constructions

of collapse-binding commitments in the random oracle model, giving

evidence that they can be realized from hash functions like SHA-3. We

evidence the usefulness of our definition by constructing three-round

statistical zero-knowledge quantum arguments of knowledge for all NP

languages.

*15:17* [Pub][ePrint]
A random zoo: sloth, unicorn, and trx, by Arjen K. Lenstra and Benjamin Wesolowski
Many applications require trustworthy generation of public random numbers. It is shown how this can be achieved using a hash functionthat is timed to be as slow as desired (sloth), while the correctness

of the resulting hash can be verified quickly. It is shown how sloth

can be used for uncontestable random number generation (unicorn),

and how unicorn can be used for a new trustworthy random elliptic

curves service (trx) and random-sample voting.

*15:17* [Pub][ePrint]
Improved Higher-Order Differential Attacks on MISTY1, by Achiya Bar-On
MISTY1 is a block cipher designed by Matsui in 1997. It is widelydeployed in Japan, and is recognized internationally as an European

NESSIE-recommended cipher and an ISO standard. Since its introduction,

MISTY1 was subjected to extensive cryptanalytic

efforts, yet no attack significantly faster than exhaustive key search is

known on its full version. The best currently

known attack is a higher-order differential attack presented by Tsunoo

et al. in 2012 which breaks a reduced variant of MISTY1 that contains

7 of the 8 rounds and 4 of the 5 $FL$ layers in $2^{49.7}$ data and $2^{116.4}$

time.

In this paper, we present improved higher-order differential attacks on

reduced-round MISTY1. Our attack on the variant considered by Tsunoo et al.

requires roughly the same amount of data and only $2^{100.4}$ time

(i.e., is $2^{16}$ times faster). Furthermore, we present the first attack

on a MISTY1 variant with 7 rounds and all 5 $FL$ layers, requiring

$2^{51.4}$ data and $2^{121}$ time. To achieve our results, we use a new

higher-order differential characteristic for 4-round MISTY1, as well as

enhanced key recovery algorithms based on the {\\it partial sums} technique.