International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

04:17 [Pub][ePrint] Obfuscation-based Non-black-box Simulation and Four Message Concurrent Zero Knowledge for NP, by Omkant Pandey and Manoj Prabhakaran and Amit Sahai

  As recent studies show, the notions of *program obfuscation* and *zero

knowledge* are intimately connected. In this work, we explore this connection further, and prove the following general result. If there exists *differing input obfuscation* (diO) for the class of all polynomial time Turing machines, then there exists a *four message, fully concurrent zero-knowledge* proof system for all languages in NP with negligible soundness error. This result is constructive: given diO, our reduction yields an explicit protocol along with an *explicit* simulator that is ``straight line\'\' and runs in strict

polynomial time.

Our reduction relies on a new non-black-box simulation technique which does not use the PCP theorem. In addition to assuming diO, our reduction also assumes (standard and polynomial time) cryptographic assumptions such as collision-resistant hash functions.

The round complexity of our protocol also sheds new light on the *exact* round complexity of concurrent zero-knowledge. It shows, for the first time, that in the realm of non-black-box simulation, concurrent zero-knowledge may not necessarily require more rounds than *stand alone* zero-knowledge!

04:17 [Pub][ePrint] Improving security and efficiency for multi-authority access control system in cloud storage, by Qi Li and Jianfeng Ma and Rui Li and Ximeng Liu and Jinbo Xiong

  Multi-Authority Attribute-Based Encryption (MA-ABE) is an emerging cryptographic primitive for enforcing fine-grained attribute-based access control on the outsourced data in cloud storage. However, most of the previous multi-authority attribute-based systems are either proven security in a weak model or lack of efficiency in user revocation. In this paper, we propose a novel multi-authority attribute-based data access control system for cloud storage. We construct a new multi-authority CP-ABE scheme with decryption outsourcing. We largely eliminate the decryption overhead for users by outsourcing the undesirable bilinear pairing operations to the cloud servers. The proposed scheme is proven adaptively secure in the standard model and supports any monotone access policy. We also design an efficient attribute-level user revocation approach with less computation cost. The security analysis, numeral comparisons indicate that the proposed system is secure, efficient and scalable.

04:17 [Pub][ePrint] A Meet-in-the-middle Attack on Round-Reduced mCrypton, by Yonglin Hao, Dongxia Bai

  The meet-in-the-middle (MITM) attack on AES is a great success.

In this paper, we apply the method to the lightweight SPN block cipher mCrypton.

We prove that the multiset technique used to analyze AES can not be applied directly to mCrypton due to the scarcity of information. As a solution, we replace the unordered multiset with the ordered sequence. We lower the memory requirement from $2^{100}$ to $2^{44}$ using the efficient differential enumeration technique.

Based on these modifications, we construct a MITM attack on 7-round mCrypton-64/96/128 with complexities

of $2^{44}$ 64-bit blocks and $2^{57}$ encryptions.

We further extend the attack to 8 and 9 rounds for mCrypton-128 by adding some key-bridging techniques. The 8-round attack requires $2^{44}$ blocks and $2^{96}$ encryptions while the 9-round attack needs $2^{120}$ blocks and $2^{116}$ encryptions.

04:17 [Pub][ePrint] Practical Signatures from the Partial Fourier Recovery Problem, by Jeff Hoffstein and Jill Pipher and John Schanck and Joseph H. Silverman and William Whyte

  Abstract. We present PASSSign, a variant of the prior PASS and PASS-2 proposals, as a candidate for a practical post-quantum signature scheme. Its hardness is based on the problem of recovering a ring element with small norm from an incomplete description of its Chinese remainder representation. For our particular instantiation, this corresponds to the recovery of a signal with small infinity norm from a limited set of its Fourier coefficients.

The key improvement over previous versions of PASS is the introduction of a rejection sampling technique from Lyubashevsky (2009) which assures that transcript distributions are completely decoupled from the keys that generate them.

Although the scheme is not supported by a formal security reduction, we present extensive arguments for its security and derive concrete parameters based on the performance of state of the art lattice reduction and enumeration techniques.

04:17 [Pub][ePrint] A Revocable Online-Offline Certificateless Signature Scheme without Pairing, by Karthik Abinav and Saikrishna Badrinarayanan and C. Pandu Rangan and S. Sharmila Deva Selvi and S. Sree Vivek and Vivek

  Certificateless Public key Cryptography is a widely studied paradigm due to its advantages of not

having the key-escrow problem and the lack of use of certificates. Online-Offline signature schemes are

extremely relevant today because of their great practical applications. In an online-offline signature

scheme all the heavy computation is done on powerful processors and stored securely in the offline

phase, and the online component requires only light computation. Hence, it is widely used in several

low-resource devices like mobile phones, etc. Revocation is another important problem of wide interest

as it helps to keep a check on misbehaving users. Currently, there are very few revocable certificateless

signature schemes in the literature. We have addressed some of the limitations of the previously existing

schemes and designed a new model for the same that involves periodic time generated keys. We present

a revocable online-offline certificateless signature scheme without pairing. Pairing, though a very useful

mathematical function, comes at the cost of heavy computation. Our scheme is proved secure in the

random oracle model using a tight security reduction to the computational Diffie-Hellman problem.


  In this paper, we propose a new signature scheme connecting two private keys and two public keys based on general non-commutative division semiring. The key idea of our technique engrosses three core steps. In the first step, we assemble polynomials on additive structure of non-commutative division semiring and take them as underlying work infrastructure. In the second step, we generate first set of private and public key pair using polynomial symmetrical decomposition problem. In the third step, we generate second set of private and public key pair using discrete logarithm. We use factorization theorem to generate the private key in discrete logarithm problem. By doing so, we can execute a new signature scheme on multiplicative structure of the semiring using multiple private keys. The security of the proposed signature scheme is based on the intractability of the Polynomial Symmetrical Decomposition Problem and discrete logarithm problem over the given non-commutative division semiring. Hence, this signature scheme is so much strong in security point of view.

01:17 [Pub][ePrint] An efficient FHE proposal based on the hardness of solving systems of nonlinear multivariate equations (II), by Gérald Gavin

  We propose a general framework to develop fully homomorphic encryption schemes (FHE) without using Gentry\'s technique. Initially, a private-key cryptosystem

is built over $\\mathbb{Z}_n$

($n$ being an RSA modulus). An encryption of $x\\in \\mathbb{Z}_n$

is a randomly chosen vector $e$ such that $\\Phi(e)=x$ where $\\Phi$ is a secret multivariate polynomial.

This private-key cryptosystem is not homomorphic in the sense that the vector sum is not a homomorphic operator. Non-linear homomorphic operators are then

developed. The security relies on the difficulty of solving systems of nonlinear equations (which is a $\\mathcal{NP}$-complete problem). While the security of our scheme has not been reduced to a provably hard instance of this problem,

its security is globally investigated.

10:45 [Event][New] CloudCom 2013: IEEE CloudCom 2013 (5th IEEE International Conference on Cloud Computing)

  Submission: 2 December 2013
From December 2 to December 5
Location: Bristol, United Kingdom
More Information:

19:17 [Pub][ePrint] On the Resilience and Uniqueness of CPA for Secure Broadcast, by Chris Litsas and Aris Pagourtzis and Giorgos Panagiotakos and Dimitris Sakavalas

  We consider the Secure Broadcast problem in incomplete networks. We study the resilience of the Certified Propagation Algorithm (CPA),

which is particularly suitable for ad hoc networks. We address the issue of determining the maximum number of corrupted players $t^{\\mathrm{CPA}}_{\\max}$ that CPA can tolerate under the $t$-locally bounded adversary model, in which the adversary may corrupt at most

$t$ players in each player\'s neighborhood. For any graph $G$ and dealer-node $D$ we provide upper and lower bounds on $t^{\\mathrm{CPA}}_{\\max}$ that can be efficiently computed in terms of a graph theoretic parameter that we introduce in this work. Along the way we obtain an efficient 2-approximation algorithm for $t^{\\mathrm{CPA}}_{\\max}$. We further introduce two more graph parameters, one of which matches $t^{\\mathrm{CPA}}_{\\max}$exactly. Our approach allows to provide an affirmative answer to the open problem of CPA Uniqueness posed by Pelc and Peleg in 2005.

12:18 [Job][New] Tenure-track Assistant/Associate Professor, University of Connecticut, USA


The Computer Science and Engineering (CSE) Department at the University of Connecticut invites applications for a tenure-track faculty position at the assistant or associate professor level, with an expected start date of August 23, 2014. The research specialties of interest are:

  1. Machine Learning,

  2. Privacy, Cryptography or Computer Security, or

  3. Techniques for the analysis of Big Data with applications in diverse areas including biomedical informatics.

The successful candidate will:

  • Develop and sustain an internationally-recognized, externally-funded research program in one of these areas of interest;

  • Teach undergraduate and graduate courses that meet the curricular needs of our CSE department;

  • Advise and mentor undergraduate and graduate students;

  • Provide service and leadership to all units of the University of Connecticut, to external academic and scientific communities, and to the general public.

Minimum Qualifications:

  1. Completed all requirements for a Ph.D. in computing or a related discipline by the time of the appointment—equivalent foreign degrees are acceptable;

  2. Research credentials in Computer Science, with a specialty in one of the topics prescribed above.

Preferred Qualifications:

  1. A record of consistent, outstanding research contributions in one of the topics prescribed above;

  2. Significant relevant teaching experience.

This is a 9-month, tenure-track position with an expected start date of August 23, 2014. The successful candidate`s primary academic

appointment will be at the Storrs campus with the option to work at UConn`s regional campuses across the state. Salary and rank will be

commensurate with qualifications.

To apply, applications must be submitted using Acade

07:17 [Pub][ePrint] SSS-V2: Secure Similarity Search, by Hyun-A Park

  Encrypting information has been regarded as one of the most substantial approaches to protect users\' sensitive information in radically changing internet technology era. In prior research, researchers have considered similarity search over encrypted documents infeasible, because the single-bit difference of a plaintext would result in an enormous bits difference in the corresponding ciphertext. However, we propose a novel idea of Security Similarity Search (SSS) over encrypted documents by applying character-wise encryption with approximate string matching to keyword index search systems. In order to do this, we define the security requirements of similarity search over encrypted data, propose two similarity search schemes, and formally prove the security of the schemes. The first scheme is more efficient, while the second scheme achieves perfect similarity search privacy. Surprisingly, the second scheme turns out to be faster than other keyword index search schemes with keywordwise encryption, while enjoying the same level of security. The schemes of SSS support \"like query(\'ab%\')\" and a query with misprints in that

the character-wise encryption preserves the degree of similarity between two plaintexts, and renders approximate string matching between the corresponding ciphertexts possible without decryption.