International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service 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).

2012-09-03
15:17 [Pub][ePrint] Desynchronization Attack on RAPP Ultralightweight Authentication Protocol, by Zahra Ahmadian, Mahmoud Salmasizadeh, and Mohammad Reza Aref

  RAPP (RFID Authentication Protocol with Permutation) is a recently proposed efficient ultralightweight authentication protocol. The operation used in this protocol is totally different from the other existing ultralightweight protocols due to the use of new introduced data dependent permutations and avoidances of modular arithmetic operations and biased logical operations such as AND and OR. The designers of RAPP claimed that this protocol resists against desynchronization attacks since the last messages of the protocol is sent by the reader and not by the tag. This letter challenges this assumption and shows that RAPP is vulnerable against desynchronization attack. This attack has a remarkable probability of success and is effective whether Hamming weight-based or modular-based rotations are used by the protocol.



15:17 [Pub][ePrint] On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown, by Lidong Han and Wei Wei and Mingjie Liu

  In CHES 2009, Coron, Joux, Kizhvatov, Naccache and

Paillier(CJKNP) introduced a fault attack on

RSA signatures with partially unknown messages. They

factored RSA modulus $N$ using a single faulty signature and

increased the bound of unknown messages by multiple fault attack,

however, the complexity multiple fault attack is exponential in the

number of faulty signatures. At RSA 2010, it was improved which run

in polynomial time in number of faults.

Both previous multiple fault attacks deal with the general case that

the unknown part of message is in the middle. This paper handles a

special situation that some least significant bits of messages are

unknown. First, we describe a sample attack by utilizing the

technique of solving simultaneous diophantine approximation problem,

and the bound of unknown message is $N^{\\frac1{2}-\\frac1{2\\ell}}$

where $\\ell$ is the number of faulty signatures. Our attacks are

heuristic but very efficient in practice. Furthermore, the new bound

can be extended up to $N^{\\frac1{2}^{1+\\frac1{\\ell}}}$ by the

Cohn-Heninger technique. Comparison between previous attacks and new

attacks with LSBs of message unknown will be given by simulation

test.



15:17 [Pub][ePrint] A Method for Generating Full Cycles by a Composition of NLFSRs, by Elena Dubrova

  Non-Linear Feedback Shift Registers (NLFSR) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are usually hard to break with existing cryptanalytic methods. However, it is still not known how to construct large $n$-stage NLFSRs which generate full cycles of $2^n$ possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an $n*k$-stage register with period $O(2^{2n})$ can be constructed from $k$ $n$-stage NLFSRs by adding to their feedback functions a logic block of size $O(n*k)$. This logic block implements Boolean functions representing the set of pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size $O(n*k^2)$ and an extra time step. The presented method is feasible for generating very large full cycles.



15:17 [Pub][ePrint] Efficient Query Integrity for Outsourced Dynamic Databases, by Qingji Zheng, Shouhuai Xu, Giuseppe Ateniese

  As databases are increasingly outsourced to the cloud, data owners

require various security assurances. This paper investigates one

particular assurance, query integrity, by which a database querier

(either the data owner or a third party) can verify that its queries

were faithfully executed by the cloud server with respect to the outsourced database. Query integrity is investigated in the setting of

dynamic databases, where the outsourced databases can be updated

by the data owners as needed. We present a formal security definition

of query integrity and a provably-secure efficient construction.

Our solution improves upon the state-of-the-art solutions by additionally allowing aggregate queries and more flexible join queries. In addition, we provide better performance by eliminating a linear factor in the extra storage complexity for security purpose. Our solution also achieves a trade-off between computational and communication complexities.



15:17 [Pub][ePrint] Format-Transforming Encryption: More than Meets the DPI, by Kevin P. Dyer and Scott E. Coull and Thomas Ristenpart and Thomas Shrimpton

  Nation-states and other organizations are increasingly deploying deep-packet inspection (DPI) technologies to censor Internet traffic based on application-layer content. We introduce a new DPI circumvention approach, format-transforming encryption (FTE), that cryptographically transforms the format of arbitrary plaintext data (e.g. packet contents) into specified formats that are designed to bypass DPI tests. We show how to build a general-purpose FTE system, in which these formats are defined compactly by families of regular expressions. Moreover, we specify and implement a full FTE record-layer protocol.

We exhibit formats that are guaranteed to avoid known filters, and give a framework for learning formats from non-censored HTTP traffic. These formats are put to use in our FTE record layer, to explore trade-offs between performance and steganographic capabilities. As one example, we visit the top 100 Alexa webpages through an FTE tunnel, incurring an average overhead of roughly 5%.



15:17 [Pub][ePrint] \"Metaproofs\" (and their Cryptographic Applications), by Alfredo De Santis and Moti Yung

  We develop a non-interactive proof-system which we call \"Metaproof\"

(mu-NIZK proof system); it provides a proof of \"the existence of a proof to a statement\". This meta-mathematical notion indeed seems redundant when we deal with proving NP statements, but in

the context of zero-knowledge theory and cryptography it has a large variety of applications.

Combined with another tool we develop which we call \"on-line simulatable NIZK proof system\", it is the key tool used to solve the open problem of the existence of a many prover non-interactive zero-knowledge system (MP-NIZK proof system). This problem was presented

by Micali when the important notion of non-interactive zero-knowledge proofs (NIZK) was rst suggested and implemented for a sole prover.

The solution immensely enlarges the domain of applications of the NIZK model. The work also provides a new connection between bounded (single-theorem) non-interactive zero-knowledge proofs and the unbounded (multi-theorem) one. This may help in reducing

the complexity assumption upon which to base NIZK systems.

Remark: This is a full version (with more details, more material, and with new proofs) of the Crypto 1990 paper on Metaproof. Over the years, the concept has been used and reinvented for specic settings beyond the original ones, by others; (which has made it more useful). Recently, we were asked about this paper and about details, so here they are! For historical reasons, except for this remark, this version is presented as it was in the above mentioned date under the above

aliations, though we did not pursue publication before!



15:17 [Pub][ePrint] Updating attribute in CP-ABE: A New Approach, by Nishant Doshi and Devesh Jinwala

  In Ciphertext-Policy Attribute Based Encryption (CP-ABE), attributes are attached to the user‟s secret key and access policy is at-tached to the ciphertext. If attributes in the secret key of a user satisfy the policy then only the genuine user can decrypt the ciphertext. How-ever, such scenario also necessitates periodic updating of the secret key with the changing attributes. According to our observations, the existing attempts at doing so are not efficient. In this paper, we propose a newer approach to add, update or delete the value of particular attribute effi-ciently without the knowledge of the other attributes.



15:17 [Pub][ePrint] The low-call diet: Authenticated Encryption for call counting HSM users, by Mike Bond and George French and Nigel P. Smart and Gaven J. Watson

  We present a new mode of operation for obtaining authenticated encryption suited for use in banking and government environments where cryptographic services are only available via a Hardware Security Module (HSM) which protects the keys but offers a limited API. The practical problem is that despite the existence of better modes of operation, modern HSMs still provide nothing but a basic (unauthenticated) CBC mode of encryption, and since they mediate all access to the key, solutions must work around this. Our mode of operation makes only a single call to the HSM, yet provides a secure authenticated encryption scheme; authentication is obtained by manipulation of the plaintext being passed to the HSM via a call to an unkeyed hash function. The scheme offers a considerable performance improvement compared to more traditional authenticated encryption techniques which must be implemented using multiple calls to the HSM. Our new mode of operation is provided with a proof of security, on the assumption that the underlying block cipher used in the CBC mode is a strong pseudorandom permutation, and that the hash function is modelled as a random oracle.



15:17 [Pub][ePrint] On the immunity of Boolean functions against fast algebraic attacks using bivariate polynomial representation, by Meicheng Liu and Yin Zhang and Dongdai Lin

  In the last decade, algebraic and fast algebraic attacks are regarded as the most successful attacks on LFSR-based stream ciphers. Since the notion of algebraic immunity was introduced, the properties and constructions of Boolean functions with maximum algebraic immunity have been researched in a large number of papers. However, it is unclear whether these functions behave well against fast algebraic attacks. In this paper, we study the immunity of Boolean functions against fast algebraic attacks using bivariate polynomial representation. Based on bivariate polynomial representation, we present a sufficient and necessary condition for a Boolean function to achieve good immunity against fast algebraic attacks, propose an efficient method for estimating the immunity of a large class of Boolean functions, including the functions of Q. Jin et al., and prove that the functions of D. Tang et al. achieve (almost) optimal immunity against fast algebraic attacks.



15:17 [Pub][ePrint] Authenticity, Integrity and Proof-of-Existence for Long-Term Archiving: a Survey, by Martín A. G. Vigil and Daniel Cabarcas and Alexander Wiesmaier and Johannes Buchmann

  Digital archives that store electronic data for long periods are increasingly necessary for applications such as libraries, land registers, and medical records. Archived data is useful if protected from tampering to ensure authenticity, integrity and a date on which the existence of archived data was witnessed. We survey solutions that protected archived data using cryptography. We describe them and verify whether they successfully provide indefinite protection despite of current cryptography schemes\' limitations. Solutions are compared in regard to their goals, trust assumptions and efficiency. Based on our analysis, we elucidate open problems and promising research directions.



15:17 [Pub][ePrint] Constant Ciphertext Length in CP-ABE, by Nishant Doshi and Devesh Jinwala

  Ciphertext policy attribute based encryption (CP-ABE) is a technique

in which user with secret key containing attributes, only able to decrypt the message if the attributes in the policy match with the attributes in secret key. The existing methods that use reasonably computable decryption policies produce the ciphertext of size at least linearly varying with the number of attributes with additional pairing operations during encryption and decryption. In this paper, we propose a scheme in which ciphertext remains constant in length, irrespective of the number of attributes. Our scheme works for a threshold case: the number of attributes in a policy must be a subset of attributes in a secret key. The security of propose scheme is based on Decisional Bilinear Diffie-Hellman (DBDH) problem.