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).

2013-02-06
19:17 [Pub][ePrint] On FHE without bootstrapping, by Aayush Jain

  In this work we come up with two fully homomorphic schemes.

First, we propose an IND-CPA secure symmetric key homomorphic encryption scheme using multivariate polynomial ring over finite fields. This scheme gives a method of constructing a CPA secure homomorphic encryption scheme from another symmetric deterministic CPA secure scheme. We base the security of the scheme on information theoretic arguments and prove the scheme to be IND-CPA secure, rather than basing security on hard problems like Ideal Membership and Gr\\\"obner basis as seen in most polly cracker based schemes which also use multivariate polynomial rings. This scheme is not compact but has many interesting properties. Second, we also describe another similar symmetric key scheme which is compact, fully homomorphic and doesn\'t require bootstrapping. The scheme is on the lines of the work of Albrecht et.al. (Asiacrypt-2011) and is proven to be bounded CPA secure. Proof is based on Ideal Membership/ Ideal Remainder/Gr\\\"obner basis problem.



19:17 [Pub][ePrint] On the Indifferentiability of Key-Alternating Ciphers, by Elena Andreeva and Andrey Bogdanov and Yevgeniy Dodis and Bart Mennink and John P. Steinberger

  The Advanced Encryption Standard (AES) is the most widely used block cipher. The high level structure of AES can be viewed as a (10-round) key-alternating cipher, where a t-round key-alternating cipher KA_t consists of a small number $t$ of fixed permutations P_i on n bits, separated by key addition:

KA_t(K,m)= k_t + P_t(... k_2 + P_2(k_1 + P_1(k_0 + m))...),

where (k_0,...,k_t) are obtained from the master key K using some key derivation function.

For t=1, KA_1 collapses to the well-known Even-Mansour cipher, which is known to be indistinguishable from a (secret) random permutation, if P_1 is modeled as a (public) random permutation. In this work we seek for stronger security of key-alternating ciphers --- indifferentiability from an ideal cipher --- and

ask the question under which conditions on the key derivation function and for how many rounds t is the key-alternating cipher KA_t indifferentiable from the ideal cipher, assuming P_1,...,P_t are (public) random permutations?

As our main result, we give an affirmative answer for t=5, showing that the 5-round key-alternating cipher KA_5 is indifferentiable from an ideal cipher, assuming P_1,...,P_5 are five independent random permutations, and the key derivation function sets all rounds keys

k_i=f(K), where 0

16:53 [Job][New] PhD Positions, Vernam Lab at WPI, Worcester, MA

  PhD Positions in Applied Cryptology

The Vernam Lab at WPI in Worcester, MA has open PhD positions in applied cryptology. In particular there are two openings in side channel analysis and countermeasure design and implementation.

Candidates should have a Master’s degree in electronics, computer science or applied mathematics, with strong interest in algorithms and signal processing. Prior experience in side channel analysis and embedded software or hardware design is an asset.

We offer a competitive salary and an international cutting-edge research program in an attractive working environment in the greater Boston area. WPI is one of the highest-ranked technical colleges in the US.

16:17 [Pub][ePrint] Cryptanalysis and Improvement of Akleylek et al.\'s cryptosystem, by Roohallah Rastaghi

  Akleylek et al. [S. Akleylek, L. Emmungil and U. Nuriyev, Algorithm for peer-to-peer security, journal of Appl. Comput. Math., Vol. 6(2), pp.258-264, 2007.], introduced a modified algorithm with steganographic approach for security in peer-to-peer (P2P) network. In this cryptosystem, Akleylek et al. attempt to increase the security of P2P network by connecting the ElGamal cryptosystem with knapsack problem. We show that this combination leak the security and makes the hybrid cryptosystem‎ vulnerable to \"ciphertext only attack\". Thus, in the network, an attacker can apply this attack and simply can recover the original message (plaintext) from any {\\it challenge ciphertext}. Moreover, we show that the receiver cannot decrypt the ciphertext in polynomial time and so, the proposed cryptosystem is completely impractical. We modify this cryptosystem to increase security and efficiency.



16:17 [Pub][ePrint] Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation , by Payman Mohassel and Ben Riva

  Applying cut-and-choose techniques to Yao\'s garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and definitions that are more suitable for use in practice.

* We design an efficient fully-secure malicious 2PC protocol for two-output functions that only requires $O(t|C|)$ symmetric-key operations (with small constant factors) where $|C|$ is the circuit size and $t$ is a statistical security parameter. This is essentially the {\\em optimal} complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject.

Our protocol utilizes novel techniques for enforcing \\emph{garbler\'s input consistency} and handling \\emph{two-output functions} that are more efficient than all prior solutions.

* Motivated by the goal of eliminating the \\emph{all-or-nothing} nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard covert model, and offers a smoother security vs. efficiency tradeoff to protocol designers in choosing the \\emph{right deterrence factor}. In our new notion, correctness is always guaranteed, privacy is fully guaranteed with probability ($1-\\epsilon$), and with probability $\\epsilon$ (i.e. the event of undetected cheating), privacy is only ``partially compromised\" with at most a {\\em single bit} of information leaked, in \\emph{case of an abort}.

We present two efficient 2PC constructions achieving our new notion. Both protocols are competitive with the previous 2PC based on cut-and-choose. E.g., the price of strengthening a covert 2PC to satisfy our notion (to obtain full correctness and maximum leakage of a single bit), is only $\\frac{1}{\\epsilon}$ additional garbled circuits.

A distinct feature of the techniques we use in all our constructions is to check consistency of inputs and outputs using new gadgets that are themselves \\emph{garbled circuits}, and to verify validity of these gadgets using \\emph{multi-stage} cut-and-choose openings.

These techniques may be of an independent interest.



16:17 [Pub][ePrint] Some Improved Results for uSVP and GapSVP, by Kuan Cheng

  In this paper, first, it is proved that finding the approximate shortest vector could be Karp-reduced to GapSVP.

Second, it is proved that shortest vector problem itself could be reduced to GapSVP with a quite small gap.

Third, we improve the complexity results of uSVP, proving uSVP could be reduced from SVP (our results are better than any known result). What\'s more, we prove that the search version of uSVP could be reduced to decisional version of uSVP with almost the same gap.



16:17 [Pub][ePrint] A revocable certificateless signature scheme, by Yinxia Sun and Futai Zhang and Limin Shen and Robert H. Deng

  Certificateless public key cryptography (CLPKC), with properties of no key escrow and no certificate, has received a lot of attention since its invention. However, membership revocation in certificateless cryptosystem still remains a non-trivial problem: the existing solutions are not practical for use due to either a costly mediator or enormous computation (secret channel). In this paper, we present a new approach to revocation in CLPKC with a concrete construction of a revocable certificateless signature (RCLS) scheme. In our scheme, a user\'s private key is composed of three parts: an initial partial private key, a time key and a secret value. The transmission of updated-key requires only a public channel, which makes our RCLS scheme more efficient than other methods. We first provide formal definition and security model for a RCLS scheme. The new scheme is proved secure in the random oracle model, based on the Computational Diffie-Hellman problem.



16:17 [Pub][ePrint] Joint Compartmented Threshold Access Structures, by Ali Aydın Selçuk and Ramazan Yılmaz

  In this paper, we introduce the notion of a joint compartmented threshold access structure (JCTAS). We study the necessary conditions for the existence of an ideal and perfect secret sharing scheme and give a characterization of almost all ideal JCTASes. Then we give an ideal and almost surely perfect construction that realizes such access structures. We prove the asymptotic perfectness of this construction by the Schwartz-Zippel Lemma.



16:17 [Pub][ePrint] Secrecy without one-way functions, by Dima Grigoriev and Vladimir Shpilrain

  We show that some problems in information security can be solved without using one-way functions. The latter are usually regarded as a central concept of cryptography, but the very existence of one-way functions depends on difficult conjectures in complexity theory, most notably on the notorious \"$P \\ne NP$\" conjecture.

In this paper, we suggest protocols for secure computation of the sum, product, and some other functions, without using any one-way functions. A new input that we offer here is that, in contrast with other proposals, we conceal \"intermediate results\" of a computation. For example, when we compute the sum of $k$ numbers, only the final result is known to the parties; partial sums are not known to anybody. Other applications of our method include voting/rating over insecure channels and a rather elegant and efficient solution of Yao\'s \"millionaires\' problem\".

Then, while it is fairly obvious that a secure (bit) commitment between two parties is impossible without a one-way function, we show that it is possible if the number of parties is at least 3. We also show how our (bit) commitment scheme for 3 parties can be used to arrange an unconditionally secure (bit) commitment between just two parties if they use a \"dummy\" (e.g., a computer) as the third party. We explain how our concept of a \"dummy\" is different from a well-known concept of a \"trusted third party\".

We also suggest a protocol, without using a one-way function, for \"mental poker\", i.e., a fair card dealing (and playing) over distance. We also propose a secret sharing scheme where an advantage over Shamir\'s and other known secret sharing schemes is that nobody, including the dealer, ends up knowing the shares owned by any particular player.

It should be mentioned that computational cost of our protocols is negligible to the point that all of them can be executed without a computer.



16:17 [Pub][ePrint] On Constructions of MDS Matrices from Companion Matrices for Lightweight Cryptography, by Kishan Chand Gupta and Indranil Ghosh Ray

  Maximum distance separable (MDS) matrices have applications not only in coding theory but also are

of great importance in the design of block ciphers and hash functions. It is highly nontrivial

to find MDS matrices which could be used in lightweight cryptography.

In a crypto 2011 paper, Guo et. al. proposed a new MDS matrix $Serial(1,2,1,4)^4$ over $\\mathbb{F}_{2^8}$.

This representation has a compact hardware implementation of the AES MixColumn operation.

No general study of MDS properties of this newly introduced construction of the form

$Serial(z_0,\\ldots,z_{d-1})^d$ over $\\mathbb{F}_{2^n}$

for arbitrary $d$ and $n$ is available in the literature.

In this paper we study some properties of MDS matrices and provide an insight of

why $Serial(z_0,\\ldots,z_{d-1})^d$ leads to an MDS matrix.

For efficient hardware implementation, we aim to restrict the values of $z_i$\'s in

$\\{1,\\alpha,\\alpha^2,\\alpha+1\\}$, such that $Serial(z_0,\\ldots,z_{d-1})^d$ is MDS for $d = 4 \\mbox{ and } 5$, where

$\\alpha$ is the root of the constructing polynomial of $\\mathbb{F}_{2^n}$.

We also propose more generic constructions of MDS matrices e.g.

we construct lightweight $4 \\times 4$ and $5 \\times 5$ MDS matrices over $\\mathbb{F}_{2^n}$ for all $n \\ge 4$.

An algorithm is presented to check if a given matrix is MDS. The algorithm

directly follows from the basic properties of MDS matrix and is easy to implement.



16:17 [Pub][ePrint] CRT-based Fully Homomorphic Encryption over the Integers, by Jinsu Kim and Moon Sung Lee and Aaram Yun and Jung Hee Cheon

  In 1978, Rivest, Adleman and Dertouzos introduced the basic concept of privacy homomorphism that allows computation on encrypted data without decryption.

It was elegant work that precedes the recent development of fully homomorphic encryption schemes although there were found some security flaws, e.g., ring homomorphic schemes are broken by the known-plaintext attacks.

In this paper, we revisit one of their proposals, in particular the third scheme which is based on the Chinese Remainder Theorem and is ring homomorphic.

The previous result is that only a single pair of known plaintext/ciphertext can break this scheme.

However, by exploiting the standard technique to insert an error to a message before encryption, we can cope with this problem.

We present a secure modification of their proposal by showing that the proposed scheme is

fully homomorphic and secure against the chosen plaintext attacks under the decisional approximate GCD assumption {{and the sparse subset sum assumption}} when the message space is restricted to $\\Z_2^k$.

Interestingly, the proposed scheme can be regarded as a generalization of the DGHV scheme with larger plaintext.

Our scheme has $\\tilde{O}(\\lambda^5)$ overhead while the DGHV has ${\\tilde{O}}(\\lambda^8)$ for the security parameter $\\lambda$.

When restricted to the homomorphic encryption scheme with depth-$O(\\log \\lambda)$, the overhead is reduced to $\\tilde{O}(\\lambda)$.

Our scheme can be used

in applications requiring a large message space $\\Z_Q$ for $\\log Q=O(\\lambda^4)$ or SIMD style operations on $\\Z_Q^k$ for $\\log Q=O(\\lambda), k=O(\\lambda^3)$, with $\\tilde{O}(\\lambda^5)$ ciphertext size as in the DGHV.