In bilateral negotiations with multiple issues, it is difficult to reach Pareto optimal outcome when the agents' preferences and relative importance of the issues are not known to each other. Self-interested agents often end up in inefficient agreements. Existing negotiation frameworks suggest solutions using trusted mediator, where agents will reveal their true preferences to the mediator. But in real life situations, a mediated solution is not always preferable, e.g., agents may not trust a third party to reveal their preferences. Without preference revelation, agents cannot improve the efficiency of the outcome. This paper presents an extended protocol for bilateral multi-issue negotiation. We show that with this protocol self-interested agents are able to explore and reach win-win agreements without revealing its complete preference.