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-07-25
21:17 [Pub][ePrint] MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes, by Rafael Misoczki and Jean-Pierre Tillich and Nicolas Sendrier and Paulo S. L. M. Barreto

  Recently, several variants of the McEliece cryptosystem based on low-density parity-check (LDPC) codes have been proposed. When combined with quasi-cyclic structure, these proposals provide much smaller key sizes than the original McEliece cryptosystem. LDPC codes are characterized by the existence of low weight dual codewords, used to perform an efficient iterative decoding. In order to avoid attacks aimed at recovering such codewords, these last proposals suggested to replace the permutation matrix used by McEliece by a matrix of small constant row and column weight, in order to increase the dual codeword weight. In this paper, we introduce the moderate density parity-check codes (MPDC, for short), which provide a better decoding process than the aforementioned LDPC variants. It also recovers the possibility to use permutation equivalent private and public codes. As a result, we present two new McEliece variants (one using quasi-cyclic MDPC codes and other employing generic MDPC codes). One of the main benefits of our variants is that both key-recovery and message decoding attacks boil down to the same coding-theory problem: low weight codeword finding. Therefore we present a security reduction much closer to the general decoding problem than any other code-based encryption scheme. Regarding each variant separately, while the QC-MDPC variant is mainly focused on allowing smaller public keys (e.g., for 80-bits of security, only 4800 bits), the MDPC variant further reduces the ways for structural attacks. Finally, we evaluate several kind of attacks, resulting in practical parameters quite competitive to conventional cryptography.



21:17 [Pub][ePrint] Cryptanalysis of an Identity-Based Multiple Key Agreement Scheme, by Qingfeng Cheng

  Multiple key agreement (MKA) protocols allow two parties to generate two or more session keys in one session, which will be used for future secure communications in public network. In recent years, many MKA protocols have been proposed. However, most of them do not

consider ephemeral key compromise resilience, and some of them still exists security flaws. In this paper, we analyze the scheme proposed by Dehkordi and Alimoradi in 2011, which is announced with stronger security. We will present ephemeral key compromise attack and impersonation attack against Dehkordi and Alimoradi\'s protocol. For overcoming these security flaws, we also propose an improvement of Dehkordi and Alimoradi\'s protocol.



21:17 [Pub][ePrint] Infinite Secret Sharing -- Examples, by Alexander Dibert and Laszlo Csirmaz

  The motivation for extending secret sharing schemes to cases when either the

set of players is infinite or the domain from which the secret and/or the

shares are drawn is infinite or both, is similar to the case when switching

to abstract probability spaces from classical combinatorial probability. It

might shed new light on old problems, could connect seemingly unrelated

problems, and unify diverse phenomena.

Definitions equivalent in the finitary case could be very much different

when switching to infinity, signifying their difference. The standard

requirement that qualified subsets should be able to determine the secret

has different interpretations in spite of the fact that, by assumption, all

participants have infinite computing power. The requirement that unqualified

subsets should have no, or limited information on the secret suggests that

we also need some probability distribution. In the infinite case events with

zero probability are not necessarily impossible, and we should decide

whether bad events with zero probability are allowed or not.

In this paper, rather than giving precise definitions, we enlist an abundance

of hopefully interesting infinite secret sharing schemes. These

schemes touch quite diverse areas of mathematics such as projective

geometry, stochastic processes and Hilbert spaces. Nevertheless our main

tools are from probability theory. The examples discussed here serve as

foundation and illustration to the more theory oriented companion paper ``Probabilistic Infinite Secret Sharing.\'\'



21:17 [Pub][ePrint] Probabilistic Infinite Secret Sharing, by Laszlo Csirmaz

  The study of probabilistic secret sharing schemes using arbitrary

probability spaces and possibly infinite number of participants lets us

investigate abstract properties of such schemes. It highlights important

properties, explains why certain definitions work better than others,

connects this topic to other branches of mathematics, and might yield new

design paradigms.

A {\\em probabilistic secret sharing scheme} is a joint probability

distribution of the shares and the secret together with a collection of {\\em

secret recovery functions} for qualified subsets. The scheme is measurable

if the recovery functions are measurable. Depending on how much information

an unqualified subset might have, we define four scheme types: {\\em

perfect}, {\\em almost perfect}, {\\em ramp}, and {\\em almost ramp}. Our main

results characterize the access structures which can be realized by schemes

of these types.

We show that every access structure can be realized by a non-measurable

perfect probabilistic scheme. The construction is based on a paradoxical

pair of independent random variables which determine each other.

For measurable schemes we have the following complete characterization. An

access structure can be realized by a (measurable) perfect, or almost

perfect scheme if and only if the access structure, as a subset of the

Sierpi\\\'nski space $\\{0,1\\}^P$, is open, if and only if it can be realized

by a span program. The access structure can be realized by a (measurable)

ramp or almost ramp scheme if and only if the access structure is a

$G_\\delta$ set (intersection of countably many open sets) in the

Sierpi\\\'nski topology, if and only if it can be realized by a Hilbert-space

program.



21:17 [Pub][ePrint] Highly Secure Strong PUF based on Nonlinearity of MOSFET Subthreshold Operation, by Mukund Kalyanaraman and Michael Orshansky

  Silicon physical unclonable functions (PUFs) are security primitives relying on intrinsic randomness of IC manufacturing. Strong PUFs have a very large input-output space which is essential for secure authentication. Several proposed strong PUFs use timing races to produce a rich set of responses. However, these PUFs are vulnerable to machine-learning attacks due to linear separability of the output function resulting from the additive nature of timing delay along timing paths. We introduce a novel strong silicon PUF based on the exponential current-voltage behavior in subthreshold region of FET operation which injects strong nonlinearity into the response of the PUF. The PUF, which we term subthreshold current array (SCA) PUF, is implemented as a two-dimensional nxk transistor array with all devices subject to stochastic variability operating in subthreshold region. Our PUF is fundamentally different from earlier attempts to inject nonlinearity via digital control techniques, which could also be used with SCA-PUF. Voltages produced by nominally identical arrays are compared to produce a random binary response.

SCA-PUF shows excellent security properties. The average inter-class Hamming distance, a measure of uniqueness, is 50.3%. The average intra-class Hamming distance, a measure of response stability, is 0.6%. Crucially, we demonstrate that the introduced PUF is much less vulnerable to modeling attacks. Using a machine-learning technique of support-vector machine with radial basis function kernel for best nonlinear learnability, we observe that \"information leakage\" (rate of error reduction with learning) is much lower than for delay-based PUFs. Over a wide range of the number of observed challenge-response pairs, the error rate is 3-35X higher than for earlier designs.



05:22 [Job][New] M.Sc. and Ph.D. in Cryptography, Security, and Privacy, Koç University, Turkey

  Want to store your data online securely? Want a fair Internet? What about outsourcing your job while still being assured of the result? Want to work on cryptography, game theory, peer-to-peer networks, or similar fields?

If you want to secure the cloud through the use of provable cryptographic techniques, then you should definitely apply to the Cryptography, Security & Privacy Research Group at Koç University, Istanbul, Turkey. We have multiple openings for both M.Sc. and Ph.D. level applications. All accepted applicants will receive competitive scholarships.

For more information about our group, visit

http://crypto.ku.edu.tr

For application material, visit

http://gsse.ku.edu.tr/application-procedure

The application deadline has passed, but top-quality candidates will still be considered as long as open positions remain. TOEFL and GRE scores must be submitted. Do NOT apply online, since the deadline has passed. Send your documents via email, specifically indicating our research group as your interest.

05:19 [Event][New] IPICS 2012: IPICS Summer School 2012

  From September 3 to September 14
Location: Vienna, Austria
More Information: http://ipics2012.sba-research.org/




2012-07-24
18:17 [Pub][ePrint] Forward-Secure Hierarchical Predicate Encryption, by Juan Manuel Gonz{\\\'a}lez Nieto and Mark Manulis and Dongdong Sun

  Secrecy of decryption keys is an important pre-requisite for security of any encryption scheme and compromised private keys must be immediately replaced. \\emph{Forward Security (FS)}, introduced to Public Key Encryption (PKE) by Canetti, Halevi, and Katz (Eurocrypt 2003), reduces damage from compromised keys by guaranteeing confidentiality of messages that were encrypted prior to the compromise event. The FS property was also shown to be achievable in (Hierarchical) Identity-Based Encryption (HIBE) by Yao, Fazio, Dodis, and Lysyanskaya (ACM CCS 2004). Yet, for emerging encryption techniques, offering flexible access control to encrypted data, by means of functional relationships between ciphertexts and decryption keys, FS protection was not known to exist.\\smallskip

In this paper we introduce FS to the powerful setting of \\emph{Hierarchical Predicate Encryption (HPE)}, proposed by Okamoto and Takashima (Asiacrypt 2009). Anticipated applications of FS-HPE schemes can be found in searchable encryption and in fully private communication. Considering the dependencies amongst the concepts, our FS-HPE scheme implies forward-secure flavors of Predicate Encryption and (Hierarchical) Attribute-Based Encryption.\\smallskip

Our FS-HPE scheme guarantees forward security for plaintexts and for attributes that are hidden in HPE ciphertexts. It further allows delegation of decrypting abilities at any point in time, independent of FS time evolution. It realizes zero-inner-product predicates and is proven adaptively secure under standard assumptions. As the ``cross-product\" approach taken in FS-HIBE is not directly applicable to the HPE setting, our construction resorts to techniques that are specific to existing HPE schemes and extends them with what can be seen as a reminiscent of binary tree encryption from FS-PKE.



18:17 [Pub][ePrint] Fully Private Revocable Predicate Encryption, by Juan Manuel Gonz{\\\'a}lez Nieto and Mark Manulis and Dongdong Sun

  We introduce the concept of \\emph{Revocable Predicate Encryption (RPE)}, which extends the previous PE setting with revocation support: private keys can be used to decrypt an RPE ciphertext only if they match the decryption policy (defined via attributes encoded into the ciphertext and predicates associated with private keys) and were not revoked by the time the ciphertext was created.

The first challenge in RPE schemes is to preserve privacy for RPE ciphertexts, namely to ensure the \\emph{attribute-hiding} property, which is inherent to traditional PE constructions, and which implies the more basic property of payload hiding, used in the context of Attribute-Based Encryption (ABE). We formalize the notion of attribute hiding in the presence of revocation and propose our first RPE construction, called AH-RPE, which is attribute-hiding under the Decision Linear assumption in the standard model. In the AH-RPE scheme we deploy the revocation system of Lewko, Sahai, and Waters (IEEE S\\&P 2010), introduced for a simpler setting of broadcast encryption, which we modify for integration with the payload-hiding ABE scheme of Okamoto and Takashima (CRYPTO 2010), after making the latter attribute-hiding by borrowing additional techniques from Lewko, Okamoto, Sahai, Takashima, and Waters (Eurocrypt 2010).

As a second major step we show that RPE schemes may admit more stringent privacy requirements in comparison to PE schemes, especially when it comes to the revocation of private keys. In addition to attribute-hiding, RPE ciphertexts should ideally not leak any information about the revoked keys and by this about the revoked users. We formalize this stronger privacy notion, termed \\emph{full hiding}, and propose another RPE scheme, called FH-RPE, which achieves this notion in the setting of ``sender-local revocation\'\' of Attrapadung and Imai (Cryptography and Coding 2009), under the same assumptions as our AH-RPE construction. Our FH-RPE scheme is also based on the attribute-hiding variant of Okamoto and Takashima\'s ABE scheme, yet with a different revocation method, in which we integrate the Subset-Cover Framework of Naor, Naor, and Lotspiech (CRYPTO 2001) for better efficiency.



18:17 [Pub][ePrint] Secret Sharing Schemes for Very Dense Graphs, by Amos Beimel and Oriol Farràs and Yuval Mintz

  A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph ``hard\'\' for secret-sharing schemes (that is, require large shares), we study very dense graphs, that is, graphs whose complement contains few edges. We show that if a graph with $n$ vertices contains $\\binom{n}{2}-n^{1+\\beta}$ edges for some constant $0\\leq\\beta

18:17 [Pub][ePrint] Secure Computation on Floating Point Numbers, by Mehrdad Aliasgari and Marina Blanton and Yihua Zhang and Aaron Steele

  Secure computation undeniably received a lot of attention in the recent years, with the shift toward cloud computing offering a new incentive for secure computation and outsourcing. Surprisingly little attention, however, has been paid to computation with non-integer data types. To narrow this gap, in this work we develop efficient solutions for computation with real numbers in floating point representation, as well as more complex operations such as square root, logarithm, and exponentiation. Our techniques are information-theoretically secure, do not use expensive cryptographic techniques, and can be applied to a variety of settings. Our experimental results also show that the techniques exhibit rather fast performance and in some cases outperform operations on integers.