International Association
for Cryptologic Research

One-time signatures (OTS) are called one-time, because the accompanying reductions only guarantee security under single-message attacks. However, this does not imply that efficient attacks are possible under two-message attacks. Especially in the context of hash-based OTS (which are basic building blocks of recent standardization proposals) this leads to the question if accidental reuse of a one-time key pair leads to immediate loss of security or to graceful degradation.

In this work we analyze the security of the most prominent hash-based OTS, Lamport's scheme, its optimized variant, and WOTS, under different kinds of two-message attacks. Interestingly, it turns out that the schemes are still secure under two message attacks, asymptotically. However, for typical parameters this does not mean anything. Our results show that for Lamport's scheme, security only slowly degrades in the relevant attack scenarios and typical parameters are still somewhat secure, even in case of a two-message attack. As we move on to optimized Lamport and its generalization WOTS, security degrades faster and faster, and typical parameters do not provide a reasonable level security under two-message attacks.

Besides this destructive context, we also analyze two-message attacks in a constructive context that appears for example when OTS are used to prevent double-spending in bitcoin.

Data deduplication, aiming to eliminate duplicate data, has been widely used in cloud storage to reduce the amount of storage space and save bandwidth. Unfortunately, as an increasing number of sensitive data are stored remotely, the encryption, the simplest way for data privacy, is not compatible with data deduplication. Though many research efforts have been devoted to securing deduplication, they all are subject to performance, security, and applicability limitations. Here, we propose two encrypted deduplication schemes, SDedup and XDedup, both based on Merkle puzzle. To the best of our knowledge, XDedup is the first brute-force resilient encrypted deduplication with only symmetrically cryptographic two-party interactions. The analysis and numerical simulations are conducted to demonstrate the performance and practicality of SDedup and XDedup.

It is widely understood that we are just human beings rather than being almighty; as a result, when utilizing cryptographic technology in practice, we have always to rely on imperfect randomness to various extent. For ordinary cryptography (e.g., encryption), if a person misuses a random number generator (e.g., generating a vulnerable ciphertext), then the person him/herself will suffer the damage caused by the misuse (e.g., leakage of his/her sensitive plaintext). In contrast, in this paper we give \emph{a concrete example} of the following serious situation for multiparty (in particular, two-party) computation in the semi-honest model: Imagine that a party replaces the party's (uniform and independent) internal random tape with an output of some random function. Then, even if the original two-party protocol is \emph{statistically} (i.e., almost perfectly) secure and the output of the random function is \emph{statistically} (i.e., almost perfectly) indistinguishable from uniform, \emph{it may still happen} that the party with the replaced random tape can now get \emph{the other party's secret input}. Due to the unavoidable imperfect randomness mentioned above, statistical indistinguishability would be the \lq\lq best possible'' quality of the random tape in practice, but then, our example may mean that the semi-honest security alone of a two-party protocol can guarantee nothing about security for a party's input in real situations.

A technical remark is that, the output of the random function in our example depends also on the party's input for our two-party protocol. But the author thinks that the true reason of such a paradoxical phenomenon is at another point. Namely, there is a famous \lq\lq clever'' technique for security proofs of two-party protocols, where a simulator for a party's view emulates a transcript during the protocol first, and then emulates the party's random tape depending consistently on the transcript. This is actually in the opposite order from real, where the transcript does depend on the random tape; and, in fact, we prove that such a problem caused by \lq\lq manipulated'' random tapes is prevented (at least under the two conditions for statistical security mentioned above) \emph{provided the simulator in the original security proof is constructed without this \lq\lq order-reversing'' technique}, even if the output of the random function still depends on the party's local input.

Event date: 1 May to 5 May 2017
Submission deadline: 15 November 2016
Notification: 31 January 2017

The Coding Theory, Cryptography, and Number Theory group at Clemson University has an RTG postdoctoral position in areas of mathematics related to interests of the members of the RTG group. To be eligible applicants must be a US citizen or permanent resident and no more than two years past completion of the doctoral degree. This position is renewable annually to a maximum of three years and carries a two course per year teaching load. This position also includes summer support for two summers and a research allowance. Along with teaching duties, RTG postdocs will also be expected to participate in some of the other activities associated to the grant that can be found on the grant webpage (http://www.math.clemson.edu/ccnt). Applications should include an AMS cover sheet, cover letter, curriculum vitae, research statement, teaching statement, and four letters of reference at least one of which addresses the applicant’s teaching. The cover letter should indicate how the applicant\'s work relates to the research of one or more members of the RTG group. Applications must be completed through the website http://www.mathjobs.org, and will be accepted until the position(s) have been filled. Completed applications for the postdoctoral position received before November 1 will receive full consideration. The Department of Mathematical Sciences at Clemson University includes the areas of algebra and discrete mathematics, analysis, computational mathematics, operations research, statistics and probability, and applied statistics. For further information regarding the department and its programs, please visit the website http://www.math.clemson.edu. Clemson University is an AA/EEO employer and does not discriminate against any person or group on the basis of age, color, disability, gender, pregnancy, national origin, race, religion, sexual orientation, veteran status or genetic information. Clemson University is building a culturally diverse faculty committed to working in a multicultural environment and encourages applications from minorities and women.

Closing date for applications: 15 November 2016

More information: https://www.mathjobs.org/jobs/jobs/9423

The Department of Computer Science at the University of Surrey invites applications for two posts of Lecturer in Secure Systems.

Both posts are part of a strategic drive to strengthen and integrate our core safety and security activities within the Secure Systems group. One of the posts will aim to complement the recent appointment of Professor Liqun Chen.

We aim to attract candidates that will conduct research in areas such as trusted computing, safety verification, security verification, data privacy, cyber-physical and internet of things security, cloud or mobile security, machine learning and data analytics applied to security, human aspects of cyber security, formal methods and applied cryptography. We are seeking individuals that can contribute to fundamental research and turn it into practice. We welcome applications from candidates whose research areas complement the existing research of the group.

Closing date for applications: 2 December 2016

Contact: Helen Treharne,

Head of Department, Computer Science, University of Surrey

h.treharne (at) surrey.ac.uk

More information: http://jobs.surrey.ac.uk/083116

The proceedings for TCC 2016-B are now available via SpringerLink. Through our agreement with Springer, IACR members can access these proceedings for free by logging into this access page. The conference was held this week in Beijing, China.

In the Micali-Shamir paper improving the efficiency of the original Fiat-Shamir protocol, the authors state that

"(...) not all of the $v_i$'s will be quadratic residues mod $n$. We overcome this technical difficulty with an appropriate perturbation technique (...)"

This perturbation technique is made more explicit in the associated patent application: "Each entity is allowed to modify the standard $v_j$ which are QNRs. A particularly simple way to achieve this is to pick a modulus $n=pq$ where $p=3 \bmod 8$ and $q=7 \bmod 8$, since then exactly one of $v_j,-v_j,2v_j,-2v_j$ is a QR mod $n$ for any $v_j$. The appropriate variant of each $v_j$ can be (...) deduced by the verifier himself during the verification of given signatures."

In this short note we clarify the way in which the verifier can infer by himself the appropriate variant of each $v_j$ during verification.

Motivated by the recent searchable symmetric encryption protocol of Cash et al., we propose a new multi-client searchable encryption protocol in this work. By tactfully leveraging the RSA-function, our protocol avoids the per-query interaction between the data owner and the client, thus reducing the communication overhead significantly and eliminating the need of the data owner to provide the online services to clients at all times. Furthermore, our protocol manages to protect the query privacy of clients to some extent, meaning that our protocol hides the exact queries from the data owner. In terms of the leakage to server, it is exactly the same as Cash et al., thus achieving the same security against the adversarial server. In addition, by employing attribute-based encryption technique, our protocol also realizes the fine-grained access control on the stored data. To be compatible with our RSA-based approach, we also present a deterministic and memory-efficient `keyword to prime' hash function, which may be of independent interest.

Event date: 3 July to 5 July 2017
Submission deadline: 26 February 2017
Notification: 7 April 2017

Event date: 26 July to 28 July 2017
Submission deadline: 9 March 2017
Notification: 3 May 2017

We present security vulnerabilities in the remote voting system Helios. We propose Apollo, a modified version of Helios, which addresses these vulnerabilities and could improve the feasibility of internet voting.

In particular, we note that Apollo does not possess Helios' major known vulnerability, where a dishonest voting terminal can change the vote after it obtains the voter's credential. With Apollo-lite, votes not authorized by the voter are detected by the public and prevented from being included in the tally.

The full version of Apollo enables a voter to prove that her vote was changed. We also describe a very simple protocol for the voter to interact with any devices she employs to check on the voting system, to enable frequent and easy auditing of encryptions and checking of the bulletin board.

As a core component of Substitution-Permutation Networks, diffusion layer is mainly introduced by matrices from maximum distance separable (MDS) codes. Surprisingly, up to now, most constructions of MDS matrices require to perform an equivalent or even exhaustive search. Especially, not many MDS proposals are known that obtain an excellent hardware efficiency and simultaneously guarantee a remarkable software implementation.

In this paper, we study the cyclic structure of rotational-XOR diffusion layer, one of the commonly used linear layers over ${(\mathbb{F}_{\rm{2}}^b)^n}$, which consists of only rotation and XOR operations. First, we provide novel properties on this class of matrices, and prove the a lower bound on the number of rotations for $n \ge 4$ and show the tightness of the bound for $n=4$. Next, by precisely characterizing the relation among sub-matrices for each possible form, we can eliminate all the other non-optimal cases. Finally, we present a direct construction of such MDS matrices, which allows to generate $4 \times 4$ perfect instances for arbitrary $b \ge 4$. Every example contains the fewest possible rotations, so under this construction strategy, our proposal costs the minimum gate equivalents (resp. cyclic shift instructions) in the hardware (resp. software) implementation. To the best of our knowledge, it is the first time that rotational-XOR MDS diffusion layers have been constructed without any auxiliary search.

We revisit the problem of estimating Renyi Entropy from samples, focusing on the important case of collision entropy.

With $n$ samples we approximate the collision entropy of $X$ within an additive factor of $O\left( 2^{2\Delta}\log^{\frac{1}{2}}(1/\epsilon) \right)$ with probability $1-\epsilon$, where $\Delta$ is a known (a priori) upper bound on the difference between Renyi entropies of $X$ of order 2 and 3 respectively.

In particular, we simplify and improve the previous result on estimating collision entropy due to Acharya et al. (SODA'15) up to a factor exponential in the entropy gap.

We also discuss applications of our bound in anomaly analysis, namely (a) detection of attacks against stateless sources in TRNGs, and (b) detection of DDoS attacks at network firewalls.

Event date: 26 April to 28 April 2017
Submission deadline: 15 January 2017
Notification: 10 February 2017

Event date: 30 April 2017
Submission deadline: 10 December 2016
Notification: 20 January 2017

Event date: 22 April to 24 April 2017
Submission deadline: 1 March 2017
Notification: 15 March 2017

ChaCha and Salsa are two software oriented stream ciphers that have attracted serious attention in academic as well as commercial domain. The most important cryptanalysis of reduced versions of these ciphers was presented by Aumasson et al. in FSE 2008. One part of their attack was to apply input difference(s) to investigate biases after a few rounds. So far there have been certain kind of limited exhaustive searches to obtain such biases. For the first time, in this paper, we show how to theoretically choose the combinations of the output bits to obtain significantly improved biases. The main idea here is to consider the multi-bit differentials as extension of suitable single-bit differentials with linear approximations, which is essentially a differential-linear attack. As we consider combinations of many output bits (for example 19 for Salsa and 21 for ChaCha), exhaustive search is not possible here. By this method we obtain very high biases for linear combinations of bits in Salsa after 6 rounds and in ChaCha after 5 rounds. These are clearly two rounds of improvement for both the ciphers over the existing works. Using these biases we obtain several significantly improved cryptanalytic results for reduced round Salsa and ChaCha that could not be obtained earlier. In fact, with our results it is now possible to cryptanalyse 6-round Salsa and 5-round ChaCha in practical time.

Micropayments (payments worth a few pennies) have numerous potential applications. A challenge in achieving them is that payment networks charge fees that are high compared to “micro” sums of money.

Wheeler (1996) and Rivest (1997) proposed probabilistic payments as a technique to achieve micropayments: a merchant receives a macro-value payment with a given probability so that, in expectation, he receives a micro-value payment. Despite much research and trial deployment, micropayment schemes have not seen adoption, partly because a trusted party is required to process payments and resolve disputes.

The widespread adoption of decentralized currencies such as Bitcoin (2009) suggests that decentralized micropayment schemes are easier to deploy. Pass and Shelat (2015) proposed several micropayment schemes for Bitcoin, but their schemes provide no more privacy guarantees than Bitcoin itself, whose transactions are recorded in plaintext in a public ledger.

We formulate and construct *decentralized anonymous micropayment* (DAM) schemes, which enable parties with access to a ledger to conduct offline probabilistic payments with one another, directly and privately. Our techniques extend those of Zerocash (2014) with a new probabilistic payment scheme; we further provide an efficient instantiation based on a new fractional message transfer protocol.

Double spending in our setting cannot be prevented. Our second contribution is an economic analysis that bounds the additional utility gain of any cheating strategy, and applies to virtually any probabilistic payment scheme with offline validation. In our construction, this bound allows us to deter double spending by way of advance deposits that are revoked when cheating is detected.

Covert computation (of general functions) strengthens the notion of secure computation, so that the computation hides not only everything about the participants' inputs except for what is revealed by the function output, but it also hides the very fact that the computation is taking place, by ensuring that protocol participants are indistinguish-able from random beacons, except when the function output explicitly reveals the fact that a computation took place. General covert computation protocols proposed before have non-constant round complexity [16,4] and their eciency is orders of magnitude away from known non-covert secure computation protocols. Furthermore, [8] showed that constant-round covert computation of non-trivial functionalities with black-box simulation is impossible in the plain model.

However, the lower-bound of [8] does not disallow constant-round covert computation given some relaxation in the computation model. Indeed, in this work we propose the rst constant-round protocol for covert Two-Party Computation (2PC) of general functions, secure against malicious adversaries under concurrent composition, assuming the Common Reference String (CRS) model. Our protocol is a covert variant of a well-known paradigm in standard, i.e. non-covert, secure 2PC, using cut-and-choose technique over O(security parameter) copies of Yao's garbled circuit, and its efficiency is only a constant factor away from non-covert secure 2PC protocols that use cut-and-choose over garbled circuits.