Kipnis-Shamir Attack on Unbalanced Oil-Vinegar Scheme

Weiwei Cao State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China Lei Hu State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, Beijing 100049, China Jintai Ding University of Cincinnati, OH 45221, USA; South China University of Technology, Guangzhou 510640, China Zhijun Yin University of Cincinnati, OH 45221, USA

TBD mathscidoc:2207.43056

ISPEC 2011, 168-180, 2011.5
The public key of the Oil-Vinegar scheme consists of a set of m quadratic equations in m + n variables over a finite field F_q. Kipnis and Shamir broke the balanced Oil-Vinegar scheme where d = n − m = 0 by finding equivalent keys of the cryptosytem. Later their method was extended by Kipnis et al to attack the unbalanced case where 0 < d < m and d is small with a complexity of O(q^{d−1} m^4). This method uses the matrices associated with the quadratic polynomials in the public key, which needs to be symmetric and invertible. In this paper, we give an optimized search method for Kipnis el al’s attack. Moreover, for the case that the finite field is of characteristic 2, we find the situation becomes very subtle, which, however, was totally neglected in the original work of Kipnis et al. We show that the Kipnis-Shamir method does not work if the field characteristic is 2 and d is a small odd number, and we fix the situation by proposing an alternative method and give an equivalent key recovery attack of complexity O(q^{d+1} m^4). We also prove an important experimental observation by Ding et al for the Kipnis-Shamir attack on balanced Oil-Vinegar schemes in characteristic 2.
No keywords uploaded!
[ Download ] [ 2022-07-14 13:52:13 uploaded by dingjt ] [ 359 downloads ] [ 0 comments ]
@inproceedings{weiwei2011kipnis-shamir,
  title={Kipnis-Shamir Attack on Unbalanced Oil-Vinegar Scheme},
  author={Weiwei Cao, Lei Hu, Jintai Ding, and Zhijun Yin},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714135213738317633},
  booktitle={ISPEC 2011},
  pages={168-180},
  year={2011},
}
Weiwei Cao, Lei Hu, Jintai Ding, and Zhijun Yin. Kipnis-Shamir Attack on Unbalanced Oil-Vinegar Scheme. 2011. In ISPEC 2011. pp.168-180. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714135213738317633.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved