International Association
for Cryptologic Research

In 2005, Lin and Tzeng proposed a solution to Yao\'s Millionaires problem in the setting of semi-honest parties. At the end of the protocol only the party (Alice) who is responsible for setting up the system parameters knows the outcome. It does not specify how to have the other party (Bob) know the result. In this note, we present an improvement of the Lin-Tzeng solution. It requires that Alice and Bob alternately perform the original protocol twice. Under the reasonable assumption that a participator does not deviate from the prescribed steps before he/she obtains the outcome, Alice and Bob can almost simultaneously obtain the result. To the best of our knowledge, it is the first time to show that one participator has only an advantage of $\\mbox{ln}\\,n/n$ possibility to cheat the other in the reasonable setting.

Proofs of Data Possession (PoDP) scheme is essential to data outsourcing. It provides an efficient audit to convince a client that his/her file is available at the storage server, ready for retrieval when needed. An updated version of PoDP is Proofs of Retrievability (PoR), which proves the client\'s file can be recovered by interactions with the storage server. We propose a PoDP/PoR scheme based on Maximum Rank Distance (MRD) codes. The client file is encoded block-wise to generate homomorphic tags with help of an MRD code. In an audit, the storage provider is able to aggregate the blocks and tags into one block and one tag, due to the homomorphic property of tags. The algebraic structure of MRD codewords enables the aggregation to be operated over a binary field, which simplifies the computation of storage provider to be the most efficient XOR operation. We also prove two security notions, unforgeability served for PoDP and soundness served for PoR with properties of MRD codes. Meanwhile, the storage provider can also audit itself to locate and correct errors in the data storage to improve the reliability of the system, thanks to the MRD code again.

Online ciphers encrypt an arbitrary number of plaintext blocks and output ciphertext blocks which only depend on the preceding plaintext blocks. All online ciphers proposed so far are essentially serial, which significantly limits their performance on parallel architectures such as modern general-purpose CPUs or dedicated hardware. We propose the first parallelizable online cipher, COPE. It performs two calls to the underlying block cipher per plaintext block and is fully parallelizable in both encryption and decryption. COPE is proven secure against chosen-plaintext attacks assuming the underlying block cipher is a strong PRP. We then extend COPE to create COPA, the first parallelizable, online authenticated cipher with nonce-misuse resistance. COPA only requires two extra block cipher calls to provide integrity. The privacy and integrity of the scheme is proven secure assuming the underlying block cipher is a strong PRP. Our implementation with Intel AES-NI on a Sandy Bridge CPU architecture shows that both COPE and COPA are about \\textit{5 times faster} than their closest competition: TC1, TC3, and McOE-G. This high factor of advantage emphasizes the paramount role of parallelizability on up-to-date computing platforms.

The domain of lightweight cryptography focuses on cryptographic algorithms for extremely constrained devices. It is very costly to avoid nonce reuse in such environments, because this requires either a secure pseudorandom number generator (PRNG), or non-volatile memory to store a counter. At the same time, a lot of cryptographic schemes actually require the nonce assumption for their security. In this paper, we propose APE as the first permutation-based authenticated encryption scheme that is resistant against nonce misuse. We formally prove that APE is secure, based on the security of the underlying permutation. To decrypt, APE processes the ciphertext blocks in reverse order, and uses inverse permutation calls. APE therefore requires a permutation that is both efficient for forward and inverse calls. We instantiate APE with the permutations of three recent lightweight hash function designs: \\quark, \\photon, and \\spongent. For any of these permutations, an implementation that supports both encryption and decryption requires less than 1.9~kGE and 2.8~kGE for 80-bit and 128-bit security levels, respectively.

EAX is a mode of operation for blockciphers to implement an authenticated encryption. The original paper of EAX proved that EAX is unforgeable up to $O(2^{n/2})$ data with one verification query. However, this generally guarantees a rather weak bound for the unforgeability under multiple verification queries, i.e., only $(2^{n/3})$ data is acceptable.

This paper provides an improvement over the previous security proof, by showing that EAX is unforgeable up to $O(2^{n/2})$ data with multiple verification queries. Our security proof is based on the techniques appeared in a paper of FSE 2013 by Minematsu et al. which studied the security of a variant of EAX called EAX-prime.

We also provide some ideas to reduce the complexity of EAX while keeping our new security bound. In particular, EAX needs three blockcipher calls and keep them in memory as a pre-processing, and our proposals can effectively reduce three calls to one call. This would be useful when computational power and memory are constrained.

In view of the problems that the plaintext space is too small in the existing schemes. In this paper, a new improved scheme is presented by improving the DGHV scheme. The plaintext space of the improved scheme is extended from finite prime field $F_{2}$ in the original scheme to finite prime field $F_{p}$. Combine and apply the method of encryption in the batch encryption scheme was proposed in 2013, and the plaintext space is further extended to finite fields $F_{q}$.

The new improved scheme encrypts the message by applying the modular mathematical operation

and the Chinese remainder theorem, and the security of the scheme is based on the the difficulty of approximate greatest common divisor problem and the spare subset sum problem. The improved scheme we got has the advantages of encrypt fast, and the size of ciphertext is small. So compared with the original scheme, it is better for practical application.

Recently, researchers have proposed many non-interactive deniable authentication (NIDA) protocols. Most of them claim that their protocols possess full deniability. However, after reviewing, we found that they either cannot achieve full deniability, or suffer KCI or SKCI attack; moreover, lack efficiency, because they are mainly based on DLP, factoring problem, or bilinear pairings. Due to this observation, and that ECC provides the security equivalence to RSA and DSA by using much smaller key size, we used Fiat-Shamir heuristic to propose a novel ECC-based NIDA protocol for achieving full deniability as well as getting more efficient than the previous schemes. After security analyses and efficiency comparisons, we confirmed the success of the usage. Therefore, the proposed scheme was more suitable to be implemented in low power mobile devices than the others.

itCoin is a decentralized digital currency, introduced in 2008, that has recently gained noticeable popularity. Its main features are: (a) it lacks a central authority that controls the transactions, (b) the list of transactions is publicly available, and (c) its syntax allows more advanced transactions than simply transferring the money. The goal of this paper is to show how these properties of BitCoin can be used in the area of secure multiparty computation protocols (MPCs).

Firstly, we show that the BitCoin system provides an attractive way to construct a version of \"timed commitments\", where the committer has to reveal his secret within a certain time frame, or to pay a fine. This, in turn, can be used to obtain fairness in some multiparty protocols. Secondly, we introduce a concept of multiparty protocols that work \"directly on BitCoin\". Recall that the standard definition of the MPCs guarantees only that the protocol \"emulates the trusted third party\". Hence ensuring that the inputs are correct, and the outcome is respected is beyond the scope of the definition. Our observation is that the BitCoin system can be used to go beyond the standard \"emulation-based\" definition, by constructing protocols that link their inputs and the outputs with the real BitCoin transactions.

As an instantiation of this idea we construct protocols for secure multiparty lotteries using the BitCoin currency, without relying on a trusted authority (one of these protocols uses the BitCoin-based timed commitments mentioned above). Our protocols guarantee fairness for the honest parties no matter how the looser behaves. For example: if one party interrupts the protocol then her money is lost and transferred to the honest participants. Our protocols are practical (to demonstrate it we performed their transactions in the actual BitCoin system), and can be used in real life as a replacement for the online gambling sites. We think that this paradigm can have also other applications. We discuss some of them.

We extend the techniques of Kiltz et al. (in ASIACRYPT 2010) and Galindo et al. (in SAC 2012) to construct two efficient leakage-resilient signature schemes. Our schemes based on Boneh-Lynn-Shacham (BLS) short signature and Waters signature schemes, respectively. Both of them are more efficient than Galindo et al.\'s scheme, and can tolerate leakage of (1-o(1))/2 of the secret key at every signature invocation. The security of the proposed schemes are proved in the generic bilinear group model (additionally, in our first scheme which based on the BLS short signature, a random oracle is needed for the proof).

Submission: 3 March 2014
Notification: 14 April 2014
From June 5 to June 6
Location: Moscow, Russia
More Information: http://www.tc26.ru/en/CTCryptEN/CTCrypt2014/

Submission: 3 February 2014
Notification: 11 April 2014
From July 19 to July 22
Location: Vienna, Austria
More Information: http://csf2014.di.univr.it/index

A 4 year position as Senior Assistant (postdoc) is available at the Mathematics Department in Neuchatel (Switzerland). Little teaching duties (in French). Preference will be given to candidates who reinforce one of the research directions of the department (among which we have coding theory and cryptography). The starting date is Aug-Sept 2014.

Further information soon available at http://www2.unine.ch/sciences/cms/op/edit/lang/fr/emploi

The Information Security Group at Royal Holloway, University of London is seeking to recruit a post-doctoral research assistant to work in the area of “Cryptography: Bridging Theory and Practice”. The position is available immediately and will run until February 28th 2015.

The post-doc will join a team of post-docs and PhD students working under the leadership of Prof. Kenny Paterson. The aim of the project is to find weaknesses in cryptographic specifications and implementations, to understand how these weaknesses can be addressed in practical ways, and to develop extensions of current cryptographic theory that permit more realistic modelling of cryptographic primitives as they are used in fielded systems. The position will also involve activities designed to engage both the theory community and practitioners in the research.

Applicants should have already completed, or be close to completing, a PhD in a relevant discipline. Applicants should have an outstanding research track record in Cryptography, in either theoretical or applied aspects of the subject, and, ideally, in both aspects. Applicants should be able to demonstrate scientific creativity, research independence, and the ability to communicate their ideas effectively in written and verbal form.

Salary is in the range £32,862 to £34,724 per annum inclusive of London Allowance

Informal enquiries can be made to Kenny Paterson at kenny.paterson (at) rhul.ac.uk.

To view further details of this post and to apply please visit http://www.rhul.ac.uk/aboutus/jobvacancies/home.aspx . The RHUL Recruitment Team can be contacted with queries by email at: recruitment (at) rhul.ac.uk or via telephone on: +44 (0)1784 41 4241.

Please quote the reference: X1113/7450

Closing Date: Midnight, Sunday 22nd December 2013

Interview Date: To be confirmed

The Ethics Committee of the IACR is responsible for providing recommendations to editors, program chairs, program-committee members, and reviewers concerning fairness and ethical aspects of all matters under the influence of the IACR, such as its operations, its events, and its publications.

The mission of the Ethics Committee is described in the "IACR Policy for the Ethics Committee", available at http://www.iacr.org/docs/

The Ethics committee has discussed only a handful of cases in 2013. In the interest of raising awareness for ethical matters among the researchers in cryptology, the Ethics Committee may occasionally inform the IACR members about its work. An account of one case follows.

A team of authors submitted a paper to a non-IACR conference in the field of cryptology and information security. After submitting the work, the authors developed their method further and discovered other ways to attack the problem. Before receiving an acceptance or rejection notification from the conference, the authors had written another paper on the second method and submitted this to a second conference, this one sponsored by the IACR. The second paper did not cite or mention the first paper.

Some reviewers in the overlap of the two program committees spotted a similarity of the works, and, in line with the IACR Policy on Irregular Submissions, they shared this information with the program chairs of the two venues. The program chair of the first conference then rejected the first paper declaring that it was a "potential double submission" and informed the program chair of the IACR conference about this. The authors then reached out to the IACR Ethics Committee and explained their case. They wanted to obtain a clarification that there was no double submission.

The Ethics Committee reviewed the situation and examined the submitted papers superficially. The committee then concluded that there was no obvious case of "parallel submissions" as described in the IACR Policy and that the second paper should enter the regular reviewing process of the IACR conference. The committee also remarked that it cannot make any statement towards the first conference because it is not an IACR venue. To the committee, it seemed that there was a misunderstanding because the existence and nature of technical links between the contributions of the two papers were not mentioned by the authors.

Last but not least, the committee recommended to the authors that, in the interest of being transparent in scientific work, authors should always cite existing known related work, even when a new contribution would not directly build on it. Furthermore, considering the delicate issues around double submissions, this point was particularly important with related work from the same authors.

IACR Ethics Committee (2013)

• Josh Benaloh
• Thomas Berson
• Christian Cachin (chair)

Submission: 14 April 2014
Notification: 9 June 2014
From September 3 to September 5
Location: Amalfi, Italy
More Information: http://scn.dia.unisa.it/

The authenticated encryptions which resist misuse of initial value (or nonce) at some desired level of privacy are two-pass or Mac-then-Encrypt constructions (inherently inefficient but provide full privacy) and online constructions, e.g., McOE, sponge-type authenticated encryptions (such as duplex, AEGIS) and COPA. Only the last one is almost parallelizable with some bottleneck in processing associated data. In this paper, {\\em we design a new online secure authenticated encryption, called \\tx{ELmE} or Encrypt-Linear mix-Encrypt, which is completely (two-stage) {\\bf parallel} (even in associated data) and {\\bf pipeline implementable}}. It also provides full privacy when associated data (which includes initial value) is not repeated. The basic idea of our construction and COPA are based on \\tx{EME}, an Encrypt-Mix-Encrypt type SPRP constructions (secure against chosen plaintext and ciphertext). Unlike \\tx{EME}, we consider (so does COPA) online computable {\\bf linear mixing}. In addition with getting rid of bottleneck, our construction optionally supports {\\bf intermediate tags} which can be verified faster with less buffer size. Intermediate tag provides security against block-wise adversaries which is meaningful in low-end device implementation.

We present a new Cryptographically Secure Pseudo-Random Number Generator. It uses permutations as its internal state, similarly to the RC4 stream cipher. We describe a statistical test which revealed non-random patterns in a sample of $2^{16.6}$ outputs of a 3-bit RC4.

Our new algorithm produced $2^{46.8}$ undistinguishable from random 3-bit outputs in the same test. We probed $2^{51}$ outputs of the algorithm in different statistical tests with different word sizes

and found no way of distinguishing the keystream from a random source. The size of the algorithm\'s internal state is $2^{3424}$ (for an 8-bit implementation). The algorithm is cryptographically secure to the extent we were able to analyse it. Its design is simple and easy to implement. We present the generator along with a key scheduling algorithm processing both keys and initialization vectors.

A $d$-broadcast primitive is a communication primitive that allows a

sender to send a value from a domain of size $d$ to a set of parties.

A broadcast protocol emulates the $d$-broadcast primitive using only

point-to-point channels, even if some of the parties cheat, in

the sense that all correct recipients agree on the same value $v$

(consistency), and if the sender is correct, then $v$ is the value

sent by the sender (validity). A celebrated result by Pease, Shostak

and Lamport states that such a broadcast protocol exists if and only if $t 3$ no broadcast amplification

is possible, i.e., $\\phi_n(d)=d$ for any $d$.

However, if other parties than the sender can also broadcast some

short messages, then broadcast amplification is possible for

\\emph{any}~$n$. Let $\\phi^*_n(d)$ denote the minimal $d\'$ such that

$d$-broadcast can be constructed from primitives $d\'_1$-broadcast,

\\ldots, $d\'_k$-broadcast, where $d\'=\\prod_i d\'_i$ (i.e., $\\log

d\'=\\sum_i \\log d\'_i$). Note that $\\phi^*_n(d)\\leq\\phi_n(d)$.

We show that broadcasting $8n\\log n$ bits in

total suffices, independently of $d$, and that at least $n-2$ parties,

including the sender, must broadcast at least one bit. Hence

$\\min(\\log d,n-2) \\leq \\log \\phi^*_n(d) \\leq 8n\\log n$.

Template attacks remain a powerful side-channel technique to

eavesdrop on tamper-resistant hardware. They model the probability

distribution of leaking signals and noise to guide a

search for secret data values. In practice, several numerical

obstacles can arise when implementing such attacks

with multivariate normal distributions.

We propose

efficient methods to avoid these. We also demonstrate how to achieve

significant performance improvements, both in terms of information

extracted and computational cost, by pooling covariance estimates

across all data values. We provide a detailed and systematic

overview of many different options for implementing such

attacks. Our experimental evaluation of all these methods based on

measuring the supply current of a byte-load instruction executed in

an unprotected 8-bit microcontroller leads to practical guidance for

choosing an attack algorithm.

In this paper, we design a novel one-way trapdoor function, and then propose a new multivariate public key cryptosystem called $\\rm TOT$, which can be used for encryption, signature and authentication. Through analysis, we declare that $\\rm TOT$ is secure, because it can resist current known algebraic attacks if its parameters are properly chosen. Some practical implementations for $\\rm TOT$ are also given, and whose security level is at least $2^{90}$. The comparison shows that $\\rm TOT$ is more secure than $\\rm HFE$, $\\rm HFEv$ and $\\rm Quartz$ (when $n \\ge 81$ and $D_{HFE} \\ge 129$, $\\rm HFE$ is still secure), and it can reach almost the same speed of computing the secret map by $\\rm C^\\ast$ and $\\rm Sflash^{v2}$ (even though $\\rm C^\\ast$ was broken, its high speed has been affirmed).