<?xml version="1.0" encoding="iso-8859-1" ?>
<rss version="2.0">
  <channel>
    <title>2005 Reports</title>
    <link>http://eprint.iacr.org/forum/list.php?5</link>
    <description><![CDATA[Discussion forum for Cryptology ePrint Archive reports posted in 2005.
Please put the report number in the subject.

]]></description>
    <language>EN</language>
    <pubDate>Sun, 09 Sep 2012 06:18:15 -0600</pubDate>
    <lastBuildDate>Sun, 09 Sep 2012 06:18:15 -0600</lastBuildDate>
    <category>2005 Reports</category>
    <generator>Phorum 5.1.22</generator>
    <ttl>600</ttl>
    <item>
      <title>2005/077 and HFE inversion attacks</title>
      <link>http://eprint.iacr.org/forum/read.php?5,883,883#msg-883</link>
      <author>ncourtois</author>
      <description><![CDATA[The authors have already integrated my earlier remarks however few details are still not quite right and need to be corrected. 
The bottom line is that many inversion attacks were developed much earlier than Faugčre and Joux who brought them to the next level, and Cou01 [in fact written in 1999 and submitted to Crypto 1999 but published in another LNCS volume in 2001]. This paper Cou01 does not only improve KS99 as it is said here but presents powerful inversion attacks which already break the HFE Challenge 1 and already break the general basic HFE in polynomial time. Inversion attacks should not be confused with attacks from Crypto 1999 [KS99] which do recover the key, while inversion attacks are MUCH faster and do not recover the key [Cou01,FJ03]. 
See detailed comments below. 

=======================================

http://eprint.iacr.org/2005/077.pdf

In Section 3.4. we read: 
==================================================================
From a cryptanalytic point of view, basic HFE are broken: an efficient key inversion attack, using the MinRank-problem (cf Section 2.6.2), has been demonstrated in [KS99]. An inversion attack which uses both GrÄobner bases and general linearization methods has been shown in [FJ03]. In [SG03] we find an attack which works better if n is not a prime, i.e., we have splitting fields. 
A more detailed discussion of HFE can be found in [Pat96b, Cou01, WP04a]. Here, [Pat96b] gives some general considerations of HFE after its development, e.g., a general linearization attack against all
multivariate schemes (cf Section 2.4.5), while [Cou01] summarised the situation of HFE in 2001 and also improves over the attack from [KS99]. The latest such summary of attacks can be found in [WP04a].

Let me correct this text: 

From a cryptanalytic point of view, basic HFE are broken: a key recovery attack, using the MinRank-problem (cf Section 2.6.2), has been demonstrated in [KS99] and further discussed in [Cou01]. Then more efficient and more practical inversion attacks with multivariate algebraic input/output relations have been developed in [Cou01]. This paper already shows that HFE Challenge 1 can be broken and that HFE can be broken in in polynomial time if the hidden polynomial degree is fixed. Subsequent inversion attacks allow to enhance and optimize this process of solving through GrÄobner bases [FJ03]. In [SG03] we find an attack which works better if n is not a prime, i.e., we have splitting fields. 
A more detailed discussion of HFE can be found in [Pat96b, Cou01, WP04a]. Here, [Pat96b] gives some general considerations of HFE after its development, e.g., a general linearization attack against all
multivariate schemes (cf Section 2.4.5), while [Cou01] summarised the situation of HFE in 2001 and also improves over the attack from [KS99]. The latest summary of attacks can be found in [WP04a]. 

==============
end of section 4.3. 

&quot;In particular,
the attacks from [KS99, FJ03] are no longer effective against this variation.&quot;
=&gt;
&quot;In particular,
the attacks from [KS99, Cou01,FJ03] are no longer effective against this variation.&quot;


================
In Section 5.1. we read: 

&quot;Hidden field equations were mainly used with the minus and the \v&quot; modification so far. The cryptanalysis of [KS99] becomes ineffective if any variation is applied. However, the later work of Faugµere and Joux [FJ03] proves very efficient against HFE, HFE+, and also to some extent against HFEv. 


&quot;Hidden field equations were mainly used with the minus and the &quot;v&quot; modification so far. The cryptanalysis of [KS99] becomes ineffective if any variation is applied. The inversion attacks in [Cou01] it also seemed ineffective agaisnt variations, however in [CDF03] it is first (experimentally) shown that some variations can be broken. This is  greatly expanded and fully justified in later work by Faugµere and Joux [FJ03] which proves very efficient against HFE, HFE+, and also to some extent against HFEv. 

reference to be added: 

[CDF03]
Nicolas Courtois, Magnus Daum and Patrick Felke: 
&quot;On the Security of HFE, HFEv- and Quartz,&quot; 
PKC 2003, LNCS 2567, Springer, pp. 337-350.
YG Desmedt, editor. Public Key Cryptography, 
PKC 2003, 6th International Workshop on Practice and Theory in Public Key Cryptography


==================

However, the method HFE- proves a very efficient way to counter this attack.&quot;
=&gt;
I am NOT so sure about it, but will offer no correction.]]></description>
      <category>2005 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?5,883,883#msg-883</guid>
      <pubDate>Sun, 09 Sep 2012 06:18:15 -0600</pubDate>
    </item>
    <item>
      <title>Re: 2005/422 Is ACJT group signature fully anonymous?</title>
      <link>http://eprint.iacr.org/forum/read.php?5,44,733#msg-733</link>
      <author>victorwilson</author>
      <description><![CDATA[Yes, ACJT is fully anonymous.]]></description>
      <category>2005 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?5,44,733#msg-733</guid>
      <pubDate>Mon, 06 Aug 2012 07:56:40 -0600</pubDate>
    </item>
    <item>
      <title>2005/422 Is ACJT group signature fully anonymous?</title>
      <link>http://eprint.iacr.org/forum/read.php?5,44,44#msg-44</link>
      <author>qlq</author>
      <description><![CDATA[''On Anonymity of Group Signatures ''
http://eprint.iacr.org/2005/422
this paper answers the question, and the result is that ACJT is fully anonymous (CCA2-secure) in ROM.
Is it right?
Since I couldn't totally agree with the proof.]]></description>
      <category>2005 Reports</category>
      <guid isPermaLink="true">http://eprint.iacr.org/forum/read.php?5,44,44#msg-44</guid>
      <pubDate>Fri, 18 Jan 2008 00:20:58 -0700</pubDate>
    </item>
  </channel>
</rss>
