Certified defenses against adversarial examples are very important in safety-critical applications of machine learning. However, existing certified defense strategies only safeguard against perturbation-based adversarial attacks, where the attacker is only allowed to modify normal data points by adding small perturbations. In this paper, we provide certified defenses under the more general threat model of unrestricted adversarial attacks. We allow the attacker to generate arbitrary inputs to fool the classifier, and assume the attacker knows everything except the classifiers' parameters and the training dataset used to learn it. Lack of knowledge about the classifiers parameters prevents an attacker from generating adversarial examples successfully. Our defense draws inspiration from differential privacy, and is based on intentionally adding noise to the classifier's outputs to limit the attacker's knowledge about the parameters. We prove concrete bounds on the minimum number of queries required for any attacker to generate a successful adversarial attack. For a simple linear classifiers we prove that the bound is asymptotically optimal up to a constant by exhibiting an attack algorithm that achieves this lower bound. We empirically show the success of our defense strategy against strong black box attack algorithms.
Although this paper's title contains "certified defense" and "unrestricted adversarial attack",  what I believe this paper is doing is analyzing the query complexity of query-based black-box attacks under simple linear models such as logistic regressions (or kernelized versions). The authors considered a binary classifier with the additional capability of giving "no response" when the confidence is low.  In addition, the output of the classifier has to be perturbed by a random Gaussian vector. The authors then define several metrics including defensibility and query privacy to develop the query complexity on the considered model. The authors tested the query performance on two attacks: (1) the sign attack proposed by the authors and (2) the simba attack proposed by Guo et al. 
I have several concerns regarding this paper:
1. In my perspective, the title is very misleading and does not properly justify the claims made in this paper. "Certified defense" usually refers to consistent top-1 prediction of a perturbed data sample under a defined threat model. The paper reads like the authors are actually certifying the defined defensibility metric but without a threat model to certify. In addition, the attack setting is limited to black-box attacks (i.e. zero-order adversary), whereas in certified defense the attack assumption is white-box. 
2. It is also very unclear how unrestricted attack plays a role in the studied problem.  In the introduction, the authors' definition of adversarial examples is "any input is considered a valid adversarial example as long as it induces the classifier to predict a different label than an oracle classifier." But what is the oracle classifier? How do we justify the credibility of the "adversarial examples" in the experiments?
3. Only two black-box attacks were compared in this paper, one is the sign attack proposed by the authors, the other is the simba attack proposed by Guo et al. To my knowledge, simba attack paper has not been published at any peer-reviewed venue. In other words, both attacks are not widely recognized attacks or methods from published papers. Therefore, the performance evaluation is not fully justified. Since there are many black-box attacks from published papers, why not do performance analysis on those attacks?
4. Similar to 3, the classifier setting is also uncommon. Although I am happy to see classifiers have the ability to give no-response,  admittedly this type of classifier is rarely used in practice, not to mention the analysis is tied with Gaussian perturbation on the output. The technical contributions can be limited if the main contribution of this paper is characterizing the query complexity (or defensibility) of an uncommon classifier with Gaussian perturbation on the output. I believe providing more insights on how the analysis can be useful to mainstream classifiers are critical and necessary.
***Post-rebuttal comments
I thank the authors for the response. I hope the comments areuseful for preparing a future version of this work.
***