*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.

*15:17* [Pub][ePrint]
On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation, by Nir Bitansky and Omer Paneth
The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak\'s technique has given rise to various powerful applications and it is a key component in all known protocols with non-black-box simulation.We present the first non-black-box simulation technique that does not rely on Barak\'s technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity.

A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals as: simultaneously-resettable zero-knowledge, proofs of knowledge, and resettable-security from one-way functions. While previous works required tailored modifications to Barak\'s technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions.

The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality; thus, settling a question left open by Barak et al..

In the converse direction, we show a generic transformation from any resettably-sound zero-knowledge protocol to a family of functions that cannot be obfuscated.