International Association for Cryptologic Research

# IACR News Central

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-10-29
15:17 [Pub][ePrint]

Embedding an element of a finite field into auxiliary groups such as elliptic curve groups or extension fields of finite fields has been useful tool for analysis of cryptographic problems such as establishing the equivalence between the discrete logarithm problem and Diffie-Hellman problem or solving the discrete logarithm problem with auxiliary inputs (DLPwAI). Actually, Cheon\'s algorithm solving the DLPwAI can be regarded as a quantitative version of den Boer and Maurer. Recently, Kim showed in his dissertation that the generalization of Cheon\'s algorithm using embedding technique including Satoh\'s \\cite{Sat09} is no faster than Pollard\'s rho algorithm when $d\\nmid (p\\pm 1)$.

In this paper, we propose a new approach to solve DLPwAI concentrating on the behavior of function mapping between the finite fields rather than using an embedding to auxiliary groups. This result shows the relation between the complexity of the algorithm and the number of absolutely irreducible factors of the substitution polynomials, hence enlightens the research on the substitution polynomials.

More precisely, with a polynomial $f(x)$ of degree $d$ over $\\mathbf{F}_p$, the proposed algorithm shows the complexity $O\\left(\\sqrt{p^2/R}\\log^2d\\log p\\right)$ group operations to recover $\\alpha$ with $g, g^{\\alpha}, \\dots, g^{\\alpha^{d}}$, where $R$ denotes the number of pairs $(x, y)\\in\\mathbf{F}_p\\times \\mathbf{F}_p$ such that $f(x)-f(y)=0$. As an example using the Dickson polynomial, we reveal $\\alpha$ in $O(p^{1/3}\\log^2{d}\\log{p})$ group operations when $d|(p+1)$. Note that Cheon\'s algorithm requires $g, g^{\\alpha}, \\dots, g^{\\alpha^{d}}, \\dots, g^{\\alpha^{2d}}$ as an instance for the same problem.

15:17 [Pub][ePrint]

We describe plausible lattice-based constructions with properties that

approximate the sought-after multilinear maps in hard-discrete-logarithm

groups, and show that some applications of such multi-linear maps can

be realized using our approximations.

The security of our constructions relies on seemingly hard problems in

ideal lattices, which can be viewed as extensions of the assumed

hardness of the NTRU function.

08:26 [Event][New]

Submission: 1 April 2013
From May 23 to May 24
Location: Ankara, Turkey

08:25 [Event][New]

Submission: 5 August 2013
From September 23 to September 25
Location: Lodz, Poland

2012-10-27
00:17 [Pub][JoC]

Abstract  We present the first information-theoretic steganographic protocol with an asymptotically optimal ratio of key length to message length that operates on arbitrary covertext distributions with constant min-entropy. Our results are also applicable to the computational setting: our stegosystem can be composed over a pseudorandom generator to send longer messages in a computationally secure fashion. In this respect our scheme offers a significant improvement in terms of the number of pseudorandom bits generated by the two parties in comparison to previous results known in the computational setting. Central to our approach for improving the overhead for general distributions is the use of combinatorial constructions that have been found to be useful in other contexts for derandomization: almost t-wise independent function families.

• Content Type Journal Article
• Pages 1-22
• DOI 10.1007/s00145-012-9135-4
• Authors

• Aggelos Kiayias, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA
• Yona Raekow, Fraunhofer Institute for Algorithms and Scientific Computing, St. Augustin, Germany
• Alexander Russell, Department of Computer Science and Engineering, University of Connecticut, Storrs, CT, USA
• Narasimha Shashidhar, Department of Computer Science, Sam Houston State University, Huntsville, TX, USA

• Journal Journal of Cryptology
• Online ISSN 1432-1378
• Print ISSN 0933-2790

From: Wed, 24 Oct 2012 17:55:35 GMT

2012-10-26
15:17 [Pub][ePrint]

Attribute-based signature (ABS) is a useful variant of digital signature, which enables users to sign messages over attributes without revealing any information other than the fact that they have attested to the messages. However, heavy computational cost is required during signing in existing work of ABS, which grows linearly with the size of the predicate formula. As a result, this presents a significant challenge for resource-limited users (such as mobile devices) to perform such heavy computation independently. Aiming at tackling the challenge above, we propose and formalize a

new paradigm called OABS, in which the computational overhead at user side is greatly reduced through outsourcing such intensive computation to an untrusted signing-cloud service provider (S-CSP). Furthermore, we apply this novel paradigm to existing ABS to reduce complexity and present two schemes, i) in the first OABS scheme, the number of exponentiations involving in signing is reduced from $O(d)$ to $O(1)$ (nearly three), where $d$ is the upper bound of threshold value defined in the predicate; ii) our second scheme is built on Herranz et al\'s construction with constant-size signatures. The number of exponentiations in signing is reduced from $O(d^2)$ to $O(d)$ and the communication overhead is $O(1)$. Security analysis demonstrates that both OABS schemes are secure in terms of the unforgeability and attribute-signer privacy definitions specified in the proposed security model. Finally, to allow for high efficiency and flexibility, we discuss extensions of OABS and show how to achieve accountability and outsourced verification as well.

2012-10-25
15:17 [Pub][ePrint]

Not surprisingly, the common use of any public key crypto system involves publishing the public key and keeping the private key secret. There are however a few applications where both the private and public key are kept secret, thereby effectively converting a public key crypto algorithm to a symmetric algorithm.

We show that if the RSA cryptosystem is used in such a symmetric application, it is possible to determine the public RSA modulus if the public exponent is known and short, such as 3 or F4=65537, and two or more plaintext/ciphertext (or, if RSA is used for signing, signed value/signature) pairs are known.

15:17 [Pub][ePrint]

In the conventional signature scheme, the sender will sign the message and send it to the receiver, who is verify based on the certificate of the sender (provided by trusted third party prior to communication). However, this lead to a certificate management problem as third party need to maintain all certificates and if there are many third parties (hierarchical). The solution to this problem lead to a certificateless signature scheme in which receiver only requires ID (unique identity) of the sender. The approaches in literatures are based on the bilinear map. However, the time for pairing is more as that of the exponent operation of the RSA (Public Key Cryptography) scheme. Recently, Zhang et al, proposed the RSA-based certificateless scheme. We show that this scheme is insecure and proposed the scheme that overcomes the attack on Zhang et al\'s scheme.

15:17 [Pub][ePrint]

In the three party authentication key exchange

(3PAKE) protocol, more than two parties can communicate and

set up common shared secret key using the server. Recently,

Tan et al. proposed an enhanced 3PAKE scheme based on

elliptic curve cryptography (ECC) to minimize the operations and

make compatible for mobile commerce environments. However,

Nose showed the scheme of Tan et al. is susceptible to the

impersonation attack and the man-in-middle attack. However, in

this paper we have shown that Tan et al. protocol is susceptible to

the known session-speciﬁc temporary information attack and the

clock synchronization attack too. Afterwards, we have proposed

the protocol that withstands against the above mentioned attacks.

In addition, our proposed approach is based on the hash function

in place of the encryption/decryption function that was used in

Tan et al. scheme.

15:17 [Pub][ePrint]

In this paper, we propose the first full-round attacks on the PRESENT and LED lightweight ciphers. In our attacks, we use the independent-biclique approach which has been developed recently. The proposed attacks on PRESENT-80 and PRESENT-128 require $2^{60}$ and $2^{56}$ chosen plaintexts, and have time complexities of $2^{79.54}$ and $2^{127.42}$, respectively. Our attacks on LED-64 and LED-128 need $2^{56}$ and $2^{64}$ chosen plaintexts and the time complexities are equivalent to $2^{63.40}$ and $2^{127.25}$ encryptions.

15:17 [Pub][ePrint]

In this work, we provide the first construction of Attribute-Based

Encryption (ABE) for general circuits. Our construction is based on

the existence of multilinear maps. We prove selective security of

our scheme in the standard model under the natural multilinear

generalization of the BDDH assumption. Our scheme achieves both

Key-Policy and Ciphertext-Policy variants of ABE.