Smart city is an urban development vision to integrate multiple information and communication technology (ICT) solutions in a secure fashion to manage a city's assets. It includes E-home, E-office, E-health, E-traffic and so on. All of these depend on the data collecting from multifarious devices and the following data processing and analyzing. So, communication between various devices (such as smartphone and so on) will be very frequent. In such an environment, the trust relationship between devices will be an important premise to guarantee an interaction can be carried on successfully. In this paper, we propose an attribute-based trust negotiation scheme for communication between devices (D2D communication) in a smart city. In this paper, we modeled the trust negotiation process as a 0/1 knapsack problem. We adopt the secure two-party computation technique based on the homomorphic encryption to guarantee its security. The proposed protocol can make sure that a device satisfies its counterparty’s access policy while disclosing minimal privacy due to the credential disclosing. The theoretical analysis shows that our protocol is complete and secure in the semi-honest environment. Furthermore, there is no disclosure of credentials before both participants can ensure a success negotiation strategy exists. Moreover, devices cannot obtain the policies of their counterparty in the negotiation process. Finally, we did some simulations to analyze the computation cost of our protocol under different credential scales and resource access thresholds.