Submitter Variables Constraints Density Status Group Objective MPS File
Siwei Sun 2945 8418 1.80069e-03 open SiweiSun 34 s1234.mps.gz

These models come from my cryptographic research and are used to search for the best differential characteristics of the round-reduced versions of the block cipher Serpent with the mixed-integer programming technique. For all the models, including S1234.lp, S56701.lp, S456701.lp, I have found a feasible solution in the corresponding mst file. The challenge is that can we find better solutions or can we find the best solutions.

Instance Statistics

Detailed explanation of the following tables can be found here.

Size Related Properties
Original Presolved
Variables 2945 2944
Constraints 8418 8337
Binaries 2945 2944
Integers 0 0
Continuous 0 0
Implicit Integers 0 0
Fixed Variables 0 0
Nonzero Density 0.00180069 0.00180899
Nonzeroes 44641 44400
Constraint Classification Properties
Original Presolved
Total 8418 8337
Empty 0 0
Free 0 0
Singleton 1 0
Aggregations 0 0
Precedence 3072 3032
Variable Bound 0 0
Set Partitioning 0 0
Set Packing 0 0
Set Covering 1 1
Cardinality 0 0
Invariant Knapsack 1024 984
Equation Knapsack 0 0
Bin Packing 0 72
Knapsack 0 4248
Integer Knapsack 0 0
Mixed Binary 4320 0
General Linear 0 0
Indicator 0 0

Structure

Available nonzero structure and decomposition information. Further information can be found here.

value min median mean max
Components 0.7781512
Constraint % 0.0119947 12.0931 15.1134 15.1134
Variable % 4.3478300 18.2609 21.7391 21.7391
Score 0.4732280

Best Known Solution(s)

No solution available for s1234 .

Similar instances in collection

The following instances are most similar to s1234 in the collection. This similarity analysis is based on 100 scaled instance features describing properties of the variables, objective function, bounds, constraints, and right hand sides.

Instance Variables Binaries Integers Continuous Constraints Nonz. Submitter Group Status Objective
bnatt400 3600 3600 0 0 5614 21698 Tatsuya Akutsu bnatt easy 1
bnatt500 4500 4500 0 0 7029 27203 Tatsuya Akutsu bnatt hard Infeasible
circ10-3 2700 2700 0 0 42620 307320 M. Winkler open 378*
supportcase4 3162 3162 0 0 9492 38036 Michael Winkler easy 0
neos-2075418-temuka 122304 122304 0 0 349602 7610260 Hans Mittelmann neos-pseudoapplication-62 easy Infeasible

Reference

@inproceedings{DBLP:conf/asiacrypt/SunHWQMS14,
  author    = {Siwei Sun and
               Lei Hu and
               Peng Wang and
               Kexin Qiao and
               Xiaoshuang Ma and
               Ling Song},
  title     = {Automatic Security Evaluation and (Related-key) Differential Characteristic
               Search: Application to SIMON, PRESENT, LBlock, {DES(L)} and Other
               Bit-Oriented Block Ciphers},
  booktitle = {Advances in Cryptology - {ASIACRYPT} 2014 - 20th International Conference on the Theory and Application of Cryptology and Information Security,
               Kaoshiung, Taiwan, R.O.C., December 7-11, 2014. Proceedings, Part
               {I}},
  pages     = {158--178},
  year      = {2014},
  crossref  = {DBLP:conf/asiacrypt/2014-1},
  url       = {http://dx.doi.org/10.1007/978-3-662-45611-8_9},
  doi       = {10.1007/978-3-662-45611-8_9},
  timestamp = {Mon, 10 Nov 2014 13:41:59 +0100},
  biburl    = {http://dblp.uni-trier.de/rec/bib/conf/asiacrypt/SunHWQMS14},
  bibsource = {dblp computer science bibliography, http://dblp.org}
}

@misc{cryptoeprint:2014:747,
    author = {Siwei Sun, Lei Hu, Meiqin Wang, Peng Wang, Kexin Qiao, Xiaoshuang Ma, Danping Shi, Ling Song, Kai Fu},
    title = {Towards Finding the Best Characteristics of Some Bit-oriented Block Ciphers and Automatic Enumeration of (Related-key) Differential and Linear Characteristics with Predefined Properties},
    howpublished = {Cryptology ePrint Archive, Report 2014/747},
    year = {2014},
    note = {\url{http://eprint.iacr.org/2014/747}},
}

Last Update Nov 09, 2018 by Gregor Hendel
generated with R Markdown
© 2018 by Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
Imprint